double arrow

Пример.. Отбрасывая требование целочисленности, решим заданную задачу как обычную задачу линейного программирования. БП СЧ


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

БП СЧ CO
3 20/3
40/7
F -2 -4 -3  

БП СЧ
20/7 -13/7 -3/7 -23/7
40/7 9/7 1/7 10/7
F 160/7 22/7 4/7 19/7

В полученном оптимальном решении задачи имеем нецелочисленное значение неизвестной х2 . Дополнительное ограничение формируем по элементам второй строки:

БП СЧ CO
20/7 -13/7 -3/7 -23/7 -
40/7 9/7 1/7 10/7
-5/7 -2/7 -1/7 -3/7 5
F 160/7 22/7 4/7 19/7  

БП СЧ
     
     
     
F

Ответ:

Метод ветвей и границ

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




Если, например, дополнительные ограничения строить по переменной , то первое ограничение будет а второе этим мы исключаем из ОДР исходной задачи промежуток с дробными значениями неизвестной . Этот промежуток разбивает ОДР на две части

ОДР

ОДЗ1 ОДЗ2

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

Поскольку множество всех решений задачи ЦЛО конечно, то после конечного числа разбиений исходной задачи на подзадачи оптимальное решение будет найдено.



Проиллюстрируем применение метода ветвей и границ на следующем примере.

Пример. Найти максимум функции

при ограничениях

Решение. Для наглядности решение осуществим графическим методом. ОДР задачи является многоугольник ОАВС (рис. 1). В точке В находится максимальное значение функции: при и

Рис. 1

Поскольку значения неизвестных дробные, то разобьём по неизвестной ОДР задачи на две части. Одна будет содержать множество точек, у которых , а вторая — у которых . В результате получаем две новые задачи линейной оптимизации: №2 и № 3 (исходная задача имеет № 1).

Задача № 2 Задача № 3

Области допустимых решений задач представлены на рис. 2.

Из рис. 2 видно, что ни одна целочисленная точка исходной ОДР не потеряна. ОДР задачи № 2 является многоугольник OADEC. В точке Е с координатами и функция достигает максимального значения

Рис. 2

Решение задачи № 2 не является целочисленным. Что касается задачи № 3, то ее ОДР пустая. Ограничения этой задачи противоречивы, и она не имеет решения.

Продолжая решение, разобьем ОДР задачи № 2 на два подмножества по неизвестной . В результате получим две новые задачи № 4 и № 5 с соответствующими дополнительными ограничениями : и .

Задача № 4 Задача № 5

ОДР этих задач представлены на рис. 3.

ОДР задачи № 4 является многоугольник OADFK. Максимальное значение функции достигается в точке F с координатами и . . Таким образом, получено целочисленное решение задачи № 4.



ОДР задачи № 5 является треугольник LMC. Максимальное значение функция достигает в точке L с координатами ; ;

Так как значение функции целочисленного решения задачи № 4 меньше , то дальнейшему разбиению на две задачи № 6 и № 7 подлежит задача № 5 по нецелочисленной неизвестной . Не проводя дополнительных построений, отметим, что ОДР задачи № 6 с дополнительным ограничением не существует, а значение функции в оптимальном целочисленном решении задачи № 7 с дополнительным ограничением равно 7, что меньше . Таким образом, целочисленное решение исходной задачи следующее: , , .

Рис. 3







Сейчас читают про: