Учебное пособие 800278

Допустим, что оптимальные решения задач ЛП-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

задачи на решение. Результаты решения представлены на рис. 42.

Рис. 42

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

Прод1=1.67, Прод2=0, Прод3=14.33, Прод4=0. Получа-

емая прибыль при этом будет равна 1820. Это показывает, что требование целочисленности, как и любое другое дополнительное требование, ухудшает целевую функцию.

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

Таблица 1 содержит сведения о целевой функции. В столбце "Исходно" приведены значения целевой функции до начала вычислений.

Таблица 2 содержит сведения об изменяемых ячейках E13:E16 Здесь приведены значения искомых переменных, полученные в результате оптимального решения задачи.

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

В таблице для ограничений:

"формула" - зависимости для ограничений; "значение" - величина использованного ресурса; "разница" - величина неиспользованного ресурса.

125

Если ресурс используется полностью, то в графе "Состояние" указывается связанное. При неполном использовании ресурса в этой графе указывается не связан.

Величины для граничных условий состоят из двух групп. В первой группе - величины, аналогичные значениям для ограничений, при этом Разница показывает разность между найденным значением переменной и заданным граничным условием; во второй группе - значения для требований целочисленности, поэтому все они являются связанными.

Рис. 43

В диалоговом окне Параметры поиска решения есть возможность вводить различные значения Допустимого отклонения. Увеличение величины допустимого отклонения ухудшает точность решения, но ускоряет его. По умолчанию в Excel установлено допустимое отклонение, равное 5 %, что вполне приемлемо для большинства практических задач.

126

Решение задач с булевыми переменными с использованием EXCEL

Частным случаем задачи целочисленных переменных являются задачи, в результате решения которых искомые переменные xj могут принимать не любые целые значения, а только одно из двух: либо 0, либо 1. Эти переменные, чтобы их отличить от обычных, будем обозначать j вместо xj.

Решение задач с булевыми переменными рассмотрим на следующем примере. Пусть имеется 4 варианта использования ресурсов. Прибыль, которую приносит каждый вариант, и все виды ресурсов приведены на рис. 44.

Рис. 44

Требуется выбрать такие варианты, чтобы суммарная прибыль была максимальной.

1, если вариант принят

Введем булевы переменные j .

0 в противном случае

Тогда математическую модель задачи можно сформулировать в виде:

F 70 1 80 2 90 3 210 4 max

Таблица EXCEL с введенными исходными данными задачи приведена на рис. 45 ( при этом в ячейки F7, F10, F11 введены соответствующие функциональные зависимости).

127

Рис. 45

После создания таблицы с исходными данными осуществляется вызов программы Поиск решения, где в диалоговом окне вводятся:

- адрес и направление целевой функции (F7, макси-

мум);

-изменяя ячейки B3:E3;

-граничные условия: B3 B4, C3 C4, D3 D4, E3 E4;

-B3 B5, C3 C5, D3 D5, E3 E5;

-требования целочисленности: т.е. установить B3, D3, C3, E3 целыми;

-ограничения: F10 H10, F11 H11.

Далее осуществляется переход в диалоговое окно Параметры поиска решения, где устанавливается флажок Линейная модель, после чего задачу нужно запустить на решение. Результаты решения представлены на рис. 46.

Рис. 46

128

Следовательно, надо принимать варианты 3 и 4, при которых получаемая прибыль F=300 будет максимальной.

Применение булевых переменных дает возможность накладывать на решаемую задачу ряд логических условий типа “если..., то...”. Рассмотрим некоторые из них:

если в оптимальное решение должен входить один вариант ИЛИ другой, то условие записывается следующим обра-

зом: i+ j=1;

если в оптимальное решение может входить (или не входить один вариант И другой, то условие имеет вид:

i+ j 0;

в том случае, когда при принятии i-го варианта ДОЛЖЕН входить j-ый, следует записать i= j.

Аналогично можно записать логические условия для трех вариантов. Так, если в случае принятия k-го варианта должен быть принят либо вариант i, либо вариант j, условие записывается так i+ j= k.

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

К форме ввода исходных данных необходимо добавить логические условия, как это показано на рис. 47.

Далее в диалоговом окне Поиск решения вводятся все условия задачи и задача решается. При появлении на экране диалогового окна Результаты поиска решения сохраним данный сценарий под именем "без доп. усл".

После этого вызовем опять программу Поиск решения и добавим к задаче дополнительное условие F12=H12. Полученный при таких исходных данных сценарий решения сохраним под именем 2= 4.

129