качестве переменной, на базе которой строится отсечение, переменную хх. Тогда, добавляя новую неотрицательную переменную , получаем
согласно (6.3) дополнительное ограничение следующего вида: -{1/7}х4-{-1/7}х5+х,=-{32/7}
-1/7x4-6/7x5=-4/7.
(6.7)
Добавляя новое ограничение (6.7) к ограничениям задачи, рассмотренной на предьщущем шаге, получаем модифицированную задачу линейного программирования со следующей исходной симплекс-таблицей (табл. 6.4).
Таблица 6.4
| | | | | | | Решение |
| | | | | | | |
| | | | | | | |
| | | | | -1/7 | | 32/7 |
| | | | | -22/7 | | 11/7 |
| | | | -1/7 | -6/7 | | -4/7 |
Продолжая решение симплекс-методом, приходим к следующей заключительной симплекс-таблице (табл. 6.5).
Таблица 6.5
X =(х1,Х2,Хз,Х4,Х5,Хб) С координатами х =4, Xj = 3, Х3 = 1, Х4 =4,
х; = О, х; = 0.
Поскольку оптимальное решение задачи с ослабленными ограничениями является целочисленным, то процесс поиска оптимального решения исходной задачи (6.4) завершен- оптимальной точкой является точка (4, 3) со значением целевой функции 55.
В ходе решения задачи по методу Гомори было построено два дополнительных линейных отсечения. Для того чтобы представить себе геометрический смысл построенных отсечений, преобразуем ограничение
(6.6), выразив переменные Х3 и через исходные переменные х и Х2 из уравнений (6.5). А именно:
ИЛИ 2 + = 3, ЧТО эквивалентно, учитывая неотрицательность переменной X.
Х2<3.
(6.8)
Аналогичным образом преобразуем линейное отсечение (6.7), выразив переменную Х3 и Х4 из уравнений (6.5) и переменную х5 из уравнения (6.6), а именно:
1(35-7x1-X2)-(~4-(6 + Xi-3x2)4-(35-7x1-Х2)) + Х
или X, + Х2 + Хб = 7, что эквивалентно, учитывая неотрицательность переменной Х,
Х1+Х2 <7.(6.9)
Изобразив ограничения (6.8) и (6.9) эквивалентные, как мы показали, линейным отсекающим ограничениям (6.6) и (6.7), мы получим геометрическую интерпретацию метода отсекающих плоскостей (рис. 6.2).
Новое допустимое множество решений, получившееся после отсечений, есть многоугольник ABCDEF.
6.2.2. Метод ветвей и границ.
Методы типа ветвей и границ широко используются для решения не только задач линейного целочисленного и частично целочисленного программирования, но и для решения многих других дискретных оптимизационных задач (например, задача коммивояжера). Поэтому первоначально мы рассмотрим схему метода в общем виде, а затем конкретизируем ее для задач ЦЛП.
Пусть требуется решить некоторую оптимизационную задачу, записанную в общем виде, как
Идея метода ветвей и границ
состоит в разбиении допустимого множества на подмножества (правило ветвления) и вычислении оценок целевой функции на этих подмножествах, которые позволяют исключать из рассмотрения подмножества, заведомо не содержащие оптимальных точек.
В настоящее время алгоритмы метода ветвей и границ являются наиболее надежным средством решения целочисленных задач, встречающихся в практических исследованиях.
шах F(x) хеХ.
(6.10)
Метод предполагает наличие некоторого способа вычисления оценок сверху целевой функции F(x) на подмножествах множества X, X аХ ,
Эту оценку на подмножестве будем обозначать как R{ X ). Оценка сверху предполагает выполнение следующего соотношения:
F(x)<R{X),x еУ.
Способ оценивания зависит от специфики решаемой задачи, однако
весьма часто в основе оценивания функции F{x) на множестве X лежит решение задачи максимизации на некотором более широком множестве. Как правило, задача максимизации функции на расширенном множестве оказывается проще с вычислительной точки зрения. Сразу поясним, что для задач ЦЛП это расширение заключается в отбрасывании требования целочисленности переменных, что, с одной стороны, расширяет допустимое множество, а с другой- сводит задачу максимизации к задаче линейного программирования, которая существенно проще с вычислительной точки зрения.