2015-05-13
929
Задание
Используя метод ветвей и границ, решить следующую задачу линейного целочисленного программирования (ЦЛП):
(5.3)
Сначала формируется задача ЛП-1, полученная из задачи ЦЛП путем исключения требования целочисленности независимых переменных. Таким образом, модель задачи ЛП-1 выглядит следующим образом:
(5.4)
Полученное решение, а также модель задачи ЛП-1 представлены ниже (рис. 5.1).
Рис.5.1. Решение ЛП-1 средствами MS Excel
В результате решения задачи ЛП-1 получается решение: x1 = 4, x2 = 1,5, при этом Z1=15. Так как решение нецелочисленно, то осуществляются последовательно формирование и решение двух порожденных задач ЛП-2 и ЛП-3. Последние формируются в результате ветвления по переменной x2 и представляет собой задачу ЛП-1 с введёнными дополнительными ограничениями: соответственно для ЛП-2 x2£1 и для ЛП-3 x2³2 (рис 5.2).
Рис.5.2. Ветвление при решении задачи ЦЛП методом «ветвей и границ»
Модели задач ЛП-2 и ЛП-3 представлены ниже:
ЛП-2:
(5.5)
ЛП-3:
(5.6)
Модели задач ЛП-2 и ЛП-3, а также полученные решения представлены ниже (рис. 5.3 и рис. 5.4).
|
|
|
В результате решения задачи ЛП-2 получается решение: x1=4, x2=1, при этом Z2=14; а в результате решения задачи ЛП-3 получается решение: x1=3,5, x2=2, при этом Z3=14,5.
В вершине 2 определена нижняя граница значения целевой функции в оптимальном решении задачи (рис. 5.2). Вершина 2 прозондирована. Поскольку значение целевой функции в оптимальном решении задачи ЛП-3 больше нижней границы, то осуществляется дальнейшее ветвление по переменной x1. Последовательно формируются и решаются задачи ЛП-4 и ЛП-5. Последние формируются в результате ветвления по переменной x1 и представляет собой задачу ЛП-3 с введёнными дополнительными ограничениями: соответственно для ЛП-4 x1£3 и для ЛП-5 x1³4 (рис 5.2).
Рис.5.3. Решение ЛП-2 средствами MS Excel
Рис.5.4. Решение ЛП-3 средствами MS Excel
Модели задач ЛП-4 и ЛП-5 представлены ниже:
ЛП-4:
(5.7)
ЛП-5:
(5.8)
Модели задач ЛП-4 и ЛП-5, а также полученное решение ЛП-4 представлены ниже (рис. 5.5 и рис. 5.6).
Рис.5.5. Решение ЛП-4 средствами MS Excel
Рис.5.6. Решение ЛП-5 средствами MS Excel
Как видим, для ЛП-5 не выполняются ограничения
(5.9)
и поэтому MS Exсel не может найти подходящего решения данной задачи линейного программирования (рис. 5.7).
Рис.5.7. «Поиск решения» MS Exсel не может найти оптимальное решение задачи ЛП
Итак, в результате решения задачи ЛП-4 получается: x1=3, x2=2,5, Z4=14. Так как значение целевой функции не превышает установленной нижней границы (14), то вершина 4 прозондирована. Вершина 5 является также прозондированной, так как в результате решения задачи ЛП-5 установлена несовместность системы ограничений.
Таким образом, все вершины дерева прозондированы. Анализ прозондированных вершин позволяет определить решение исходной целочисленной задачи. Просматриваются все полученные целочисленные решения и выбирается вершина (и решение), обеспечивающая наилучшее значение целевой функции. В нашем случае получено только одно целочисленное решение (в вершине 2), следовательно, оно и является оптимальным, при этом x1 = 4, x2 = 1, а Z=14.
|
|
|
MS Excel позволяет устанавливать непосредственно при формировании системы ограничений требование целочисленности переменных (рис 5.8).
Рис.5.8.Установка требования целочисленности независимых переменных в MS Excel
Используем эту возможность для проверки полученного нами целочисленного решения задачи.
Полученное решение в результате добавления к модели, представленной на рис.5.1 подобных ограничений на независимые переменные, подтверждает правильность решения задачи ЦЛП по методу Лэнда и Дойга.
Варианты для выполнения лабораторной работы №5
Задание
Используя метод ветвей и границ, решите с помощью MS Excel линейную целочисленную задачу, математическая модель которой имеет следующий вид:
(5.10)
Проверьте полученное методом ветвей и границ решение прямым заданием требования целочисленности независимых переменных при построении модели в MS Excel.
Значения параметров модели представлены в соответствии с номером варианта индивидуального задания в таблице 5.1.
Таблица 5.1
| Вариант № | c1 | c2 | a11 | a12 | b1 | a21 | a22 | b2 | a31 | a32 | b3 |
| -1 | -1 | -2 | -1 | 1,5 | -1 | 2,7 | |||||
| -1 | -1 | -1 | -1 | 3,5 | |||||||
| -1 | -2 | -1 | -1 | -1 | -1 | 3,5 | |||||
| -1 | -1 | -1 | -1 | 3,5 | |||||||
| -2 | -1 | -2 | -2 | 1,5 | |||||||
| -2 | -3 | -5 | -4 | -1 | |||||||
| -1 | -3 | -1 | -2 | ||||||||
| -1 | -1 | -1 | -1 | 5,5 | |||||||
| -1 | -1 | -4 | -1 | -1 | 2,5 | ||||||
| -1 | -1 | -1 | -1 | 4,5 | |||||||
| -0,5 | 0,5 | -1 | -1 | 0,5 | 0,5 | -1 | -1 | -1 | 2,7 | ||
| -5 | -7 | -4 | -9 | ||||||||
| -3 | -1 | -3 | 6,5 | -1 | -2 | ||||||
| -2 | -5 | -6 | -5 | ||||||||
| -5 | -1 | -1 | 3,4 | -3,4 | |||||||
| -2 | -3 | -5 | -4 | -1 | -1,5 | ||||||
| -1 | -1 | -2 | 3,2 | -1 | -1 | ||||||
| -2 | -11 | -4 | -5 | -1 | -1 | ||||||
| -3 | -2 | -2 | 12,3 | -1 | -2,3 | ||||||
| -2 | -1 | -1 | -2 | ||||||||
| -1 | -4 | -2 | -1 | 7,4 | |||||||
| -2 | -4 | -1 | -3 | ||||||||
| -2 | -1 | -1 | -3 | ||||||||
| -1 | -2 | -1 | 5,4 | -2 | |||||||
| -2 | -11 | -4 | -1 | -1 |
5.Рекомендуемая литература
1. Ашихмин А.А., Подольский М.П. Методические указания к практическим занятиям по дисциплине «Математическое программирование и моделирование». – М.:МГГУ, 1986. – С.10-35.
2. Резниченко С.С., Ашихмин А.А. Математические методы и моделирование в горной промышленности. – М.: МГГУ, 1997. – С.140-186.
3. Резниченко С.С., Ашихмин А.А., Подольский М.П. Методические указания по выполнению лабораторных работ на ЭВМ по дисциплинам «Экономико-математические методы и модели» и «Теория вероятностей и математическое программирование». – М.:МГГУ,1989.–С.45-51.
