Материал: Основы математического моделирования. курс лекций. Перова А.В

Допустим, что оптимальные решения задач ЛП-2 и ЛП- 3 также содержат дробные значения целочисленных переменных и поэтому не являются допустимыми для исходной задачи.

На следующем шаге необходимо выбрать задачу ЛП-2 или ЛП-3 и произвести ветвление в соответствующей вершине, вводя новое ограничение. Выбор вершины (задачи ЛП) для дальнейшего ветвления осуществляется с помощью специальных правил. Приведем некоторые из них.

1. Использование оптимального значения целевой функции. Для дальнейшего ветвления следует выбирать вершину, соответствующую наибольшему оптимальному значению целевой функции задачи ЛП. Некоторым обоснованием этого правила служит то соображение, что допустимая область задачи ЛП с наибольшим значением Z может содержать и хорошее целочисленное решение. Например, любое целочисленное решение, полученное ветвлением задачи ЛП-2, не может давать значение Z, лучше, чем оптимальное значение Z в задаче ЛП-2.

2. Правило "последним пришел - первым обслужен". Для дальнейшего ветвления выбирается (произвольным образом) задача ЛП, решавшаяся последней.

После выбора вершины для дальнейшего ветвления выбирается целочисленная переменная, которая имеет в оптимальном решении соответствующей задачи ЛП дробное значение, и производится ветвление по этой переменной. Процесс ветвления и решения задачи продолжается до получения целочисленного оптимального решения одной из задач ЛП. Значение Z в полученной точке представляет собой нижнюю границу оптимального значения целевой функции исходной задачи ЦЛП. На этом этапе определяются прозондированные верши-

120

ны, т.е. вершины, в которых дальнейшее ветвление невозможно или нецелесообразно. Вершина является прозондированной, если она удовлетворяет одному из следующих условий:

1.Оптимальное решение, соответствующее данной вершине, целочисленно. В этом случае полученное решение допустимо для исходной задачи ЦЛП.

2.Задача ЛП, соответствующая рассматриваемой вершине, не имеет допустимых решений.

3.Оптимальное значение Z соответствующей задачи ЛП не превосходит текущей нижней границы.

Во втором и третьем случаях прозондированные вершины отбрасываются. Процесс решения задачи продолжается до тех пор, пока все вершины не будут прозондированы. Прозондированная вершина, соответствующая целочисленному решению с наилучшим (наибольшим) значением целевой функции дает оптимальное решение исходной задачи.

Пример 6. Для иллюстрации основных принципов ме-

x1,x2 0,x1,x2 целочисленные

Начальный шаг решения этой задачи состоит в нахождении решения задачи линейного программирования, получаемой при отбрасывании условия целочисленности x1 и x2. Обозначим эту задачу через ЛП-1. Ее оптимальное решение имеет вид x1=1, x2=7.5, оптимальное значение целевой функции Z1=29.5. Поскольку x2 принимает дробное значение, найденное решение не может быть оптимальным решением исходной целочисленной задачи. Найденное значение Z1 представляет собой верхнюю границу истинного оптимального целочисленного значения, поскольку при выполнении требования целочисленности x2 значение Z может лишь уменьшиться.

121

Следующий шаг метода ветвей и границ состоит в разбиении задачи ЛП-1 на две подзадачи , первая из которых (ЛП- 2) образуется в результате добавления к задаче ЛП-1 ограни-

x2 7(новоеограничение)

x1, x2 0

7x1 3x2 max

5x1 2x2 20

8x1 4x2 38

x2 8(новоеограничение)

x1, x2 0

Дерево возможных вариантов представлено на рис. 33. Оптимальное решение задачи ЛП-3 - точка х1=0.75, х2=8, где Z2=29,25. Оптимальное решение задачи ЛП-2 точка х1=1.2, х2=7, где Z3=29,4. Для дальнейшего ветвления выберем задачу ЛП-2, т.к. значение целевой функции в ней больше. К задаче ЛП-2 добавим ограничения x1 1, (задача ЛП-4) и x1 2

(задача ЛП-5). Результаты решения задачи ЛП-4: х1=1, х2=7, где Z4=28. Результаты решения задачи ЛП-5: х1=2, х2=5, где

Z5=29.

Таким образом, получены два допустимых (целочисленных) решения исходной задачи целочисленного программирования, причем значение Z4=29 представляет собой нижнюю границу максимального значения Z для задачи целочисленного программирования. Даже если исходная задача имеет другие целочисленные решения, значение целевой функции в них не может быть больше 29. Таким образом, значение Z4=29

122

представляет собой нижнюю границу максимального значения Z для исходной целочисленной задачи. Вершины ЛП-4 и ЛП-5 являются прозондированными (так как в них получено целочисленное решение, а в процессе дальнейшего ветвления оно может лишь ухудшаться). Ветвление вершины ЛП-3 также нецелесообразно в связи с тем, что целевая функция исходной задачи может принимать только целочисленные значения (т.к. все переменные и коэффициенты целочисленны), а при дальнейшем ветвлении ее значения будут увеличиваться (т.е., станут больше 29). Следовательно, оптимальное решение задачи х1=2, х2=5, где Z5=29.

Метод ветвей и границ может применяться для решения не только линейных, но и нелинейных целочисленных задач. Он также может использоваться для решения задач с дискретными переменными.

Рис. 40

123

Решение задач целочисленного программирования средствами EXCEL

Задачи целочисленного линейного программирования в среде EXCEL решаются аналогично обычным задачам линейного программирования. Основное отличие заключается во вводе требования целочисленности.

Рассмотрим решение задачи производственного планирования, скорректировав исходные данные так, как представлено на рис. 41 и добавив к ней условие целочисленности всех переменных.

Рис. 41

Дальнейшая работа выполняется в диалоговом окне Поиск решения. В нем устанавливается целевая ячейка (F7), изменяемые ячейки (B3:E3), указывается направление поиска (максимизация). Далее выбирается команда Добавить и в появившемся диалоговом окне Добавление ограничения вво-

дятся ограничения: F9<=H9, F10<=H10, F11<=H11. Определя-

ются требования целочисленности переменных (для этого в данном диалоговом окне для всех переменных из списка условных операторов (между ссылкой и ограничением) выбираетсяя целое). Условия неотрицательности переменных можно ввести в диалоговом окне Параметры поиска решения. В окне Параметры поиска решения устанавливается также флажок Линейная модель, после чего осуществляется запуск

124