2015-04-01
822
Часто на практике при решении задачи оптимизации условие целочисленности решений очень важно, например, для производства неделимой продукции. Однако простое округление может катастрофически повлиять на качество полученного решения, поэтому выделяют целый класс задач, в которых условие целочисленности учитывается непосредственно при решении, тогда задача линейного программирования называется целочисленной (ЦЗЛП).
Если решается ЦЗЛП, но условие целочисленности временно не учитывается, то задача называется ослабленной.
Методы решения ЦЗЛП:
1. Метод ветвей и границ. Применяется при использовании геометрического решения: находится решение ослабленной задачи, если получено целочисленное решение оно и является решением основной ЦЗЛП. В случае дробной компоненты xi строят две новых ЦЗЛП:
ослабленная первоначальная ослабленная первоначальная
xi≥[xi] xi≤[xi]
2. Метод Гомори (метод отсечения).
Решаем ослабленную задачу. Если получено дробное решение, то для дробной компоненты xi строим правильное отсечение по i-ой строке симплекс- таблицы (соответствующей оптимальному решению)
|
|
|
(ai1-[ai1])*x1+(ai2-[ai2])*x2+…+(ain-[ain])*xn≥bi-[bi], которое считаем дополнительным ограничением и решаем полученную задачу пока все компоненты не будут целочисленными или не будет установлено, что задача неразрешима. Этот алгоритм конечен.
Пример.
ƒ=3x1+2x2→max
x1+x2+x3=13
x1-x2+x4=6
-3x1+x2+x5=9
xi≥0
1. 
Метод ветвей и границ.
ƒ=3x1+2x2→max x2
x1+x2≤13
x1-x2≤6 Ω
-3x1+x2≤9αопт(9,5; 3,5)
xi≥0
 |
9 10 x1
Точки с целочисленными координатами (10; 4); (10; 3) не принадлежат области допустимых решений. Точки (9;3); (9;4) принадлежат области, сравнивая соответствующие им значения целевой функции, получим:
αопт(9;4;0;1;32) ƒ(αопт)=35
2. Метод правильных отсечений.
