Пример 9.8. Дана прямая задача ЛП: найти max W(x) = x1 + 2x2
при ограничениях: x1 + x2 ≤ 8;
- x1 + x2 ≤ 2; x1 + x2 ≥ 4; x1, x2 ≥ 0.
Необходимо сформировать двойственную задачу ЛП.
Для построения ДЗЛП требуется прямую задачу привести к стандартной форме:
найти max W(x) = x1 + 2x2 + 0s1 + 0s2 + 0s3 − MR3
| при ограничениях: x1 + | x2 + | s1 | = 8 → y1; | |
| - x1 + | x2 + | s2 | = 2 → y2; | |
| x1 + | x2 − | s3 + R3 | = 4 → y3; | |
| x1, | x2 ≥ | 0, | s1, s2, | s3 ≥ 0. |
| ↓ | ↓ | ↓ | ↓ ↓ | ↓ ↓ |
| 1-е | 2-е | 3-е | 4-е 5-е | 6-е W(x) |
| огр. | огр. | огр. | огр. огр. | огр. |
В соответствии с приведенными выше правилами сформи- рованная ДЗЛП имеет вид:
найти min W(x) = 8y1 + 2y2 + 4y3
при ограничениях: y1 − y2 + y3 ≥ 1,
y1 + y2 + y3 ≥ 2,
y1 ≥ 0, y2 ≥ 0, -y3 ≥ 0 (y3 ≤ 0), y3 ≥ -M.
По правилам, приведенным в табл. 9.5, двойственные пере- менные y1, y2, y3 не ограничены в знаке, однако введение оста- точных переменных в ПЗЛП приводит к появлению более жес- тких условий: y1 ≥ 0, y2 ≥ 0 — неотрицательности переменных. Для переменной y3 условие неограниченности в знаке остается в силе. Дело в том, что величина М имеет большое положитель- ное значение, поэтому ограничение y3 ≥ -M равносильно неогра- ниченности переменной y3 как в знаке, так и в значении.
При решении ДЗЛП ее необходимо представить в виде раз-
ности двух неотрицательных переменных: y3 = y3′ − y3″, y3′ ≥ 0, y3″ ≥ 0.
Между оптимальными решениями прямой и двойственной
задачами ЛП существует тесная взаимосвязь. Это означает,
что решение одной из этих задач без каких-либо дополнитель- ных вычислений может быть получено из итоговой оптималь- ной симплекс-таблицы другой задачи.
Рассмотрим эту связь на прямой и двойственной задачах примера 9.8. В табл. 9.6 и 9.7 приведены оптимальные решения соответственно прямой и двойственной задач ЛП. Из сравнения таблиц можно установить следующее. Во-первых, в точке, со- ответствующей оптимальным решениям обеих задач, выполня- ется равенство: max W(x) = min W(x). В задаче максимизации ЦФ последовательно увеличивается от начального значения до оптимального W(x) = 13. В задаче минимизации ЦФ уменьшает- ся от начального значения до оптимального W(x) = 13. Из этого следует, что процессы максимизации и минимизации сходят- ся в некоторой “точке равновесия”, после достижения которой ЦФ задач улучшить невозможно. Такая точка достигается при равенстве значений ЦФ и соответствует их оптимальным зна- чениям. Во-вторых, базисные решения ПЗЛП можно получить непосредственно из оптимальной симплекс-таблицы ДЗЛП, и наоборот. В табл. 9.4 темным цветом выделены переменные начального базиса прямой задачи и коэффициенты при них в Z-строке. Этим переменным соответствуют 3-е, 4-е и 6-е огра- ничения ДЗЛП (y1 ≥ 0, y2 ≥ 0, y3 ≥ -M).
Двойственные переменные определяются по следующему
правилу: коэффициент при начальной базисной переменной в оптимальном Z-уравнении ПЗЛП равен разности между левой и правой частями ограничения ДЗЛП, ассоциированного с данной начальной переменной. В данном случае 3/2 = y1 − 0, 1/2 = y2 − 0, M = y3 + M. Отсюда, y1 = 3/2, y2 = 1/2 и y3 = 0, в справедливости чего можно убедиться, сравнив эти значения двойственных пе- ременных с оптимальным решением ДЗЛП в табл. 9.6.
Аналогичным образом могут быть получены значения пе-
ременных ПЗЛП из оптимальной симплекс-таблицы ДЗЛП. В табл. 9.7, где приведено оптимальное решение ДЗЛП, выде- лены темным цветом переменные начального базиса ДЗЛП и коэффициенты при них в оптимальной Z-строке. Очевидно, что двойственной к ДЗЛП будет являться исходная ПЗЛП. Поэтому
при построении двойственной к ДЗЛП задачи переменной R1 бу- дет соответствовать переменная x1 прямой задачи, а переменной R2 — переменная x2 прямой задачи с условиями x1 ≥ M и x2 ≥ M.
Таблица 9.6
| Базис | x 1 | x 2 | s 1 | s 2 | s 3 | R 3 | Решение |
| Z | 0 | 0 | 3/2 | 1/2 | 0 | M | 13 |
| s 3 | 0 | 0 | 1 | 0 | 1 | -1 | 4 |
| x 2 | 0 | 1 | 1/2 | 1/2 | 0 | 0 | 5 |
| x 1 | 1 | 0 | 1/2 | -1/2 | 0 | 0 | 3 |
Значения переменных ПЗЛП определяются по следующе- му правилу: коэффициенты в оптимальном Z-уравнении равны разности между левыми и правыми частями соответствующих ограничений прямой задачи, ассоциированных с начальными переменными ДЗЛП. В данном случае имеем: 3 − M = x1 − M, 5 − M = x2 − M, откуда x1 = 3 и x2 = 5, что соответствует опти- мальному решению ПЗЛП в табл. 9.7.
Таблица 9.7
| Базис | y 1 | y 2 | y 3′ | y 3″ | s 1 | R 1 | s 2 | R 2 | Решение |
| Z | 0 | 0 | 0 | 0 | -3 | 3 − M | -5 | 5 − M | 13 |
| y 1 | 1 | 0 | -1 | 0 | -1/2 | 1/2 | -1/2 | 1/2 | 3/2 |
| y 2 | 0 | 1 | 0 | -1 | 1/2 | -1/2 | -1/2 | 1/2 | 1/2 |
Соотношения двойственности задач ЛП позволили разрабо- тать двойственный симплекс-метод, при котором сначала по- лучается недопустимое, но лучшее, чем оптимальное решение, а затем осуществляется систематическое приближение его к об- ласти допустимых решений. Этот метод используется для опре- деленного класса задач ЛП, в которых уже на начальной итера- ции можно получить оптимальное, но недопустимое решение. Но еще важнее то, что он используется при анализе чувствитель- ности задач ЛП. Применение двойственного симплекс-метода предусматривает выполнение следующих действий:
1) преобразование всех ограничений задачи ЛП в ограни- чения типа ≤, при этом часть ограничений будет иметь отри-
цательные правые части; для всех ограничений вводятся оста- точные переменные;
2) проверка условий допустимости, которая заключается в выявлении переменной, исключаемой из состава базисных на очередной итерации. В качестве исключаемой выбирается наибольшая по абсолютной величине отрицательная базисная переменная. Если все базисные переменные неотрицательны, то это свидетельствует о получении оптимального и допусти- мого решения;
3) проверка условия оптимальности, которая заключается в выборе переменной, включаемой в состав базисных на очеред- ной итерации. Для этого вычисляются отношения коэффици- ентов Z-строки к соответствующим коэффициентам ведущей строки. Отношения с положительным или нулевым значени- ем знаменателя не учитываются. В задаче минимизации ЦФ вводимой переменной должно соответствовать наименьшее из указанных отношений, а в задачах максимизации ЦФ — от- ношение, наименьшее по абсолютной величине. Задача ЛП не имеет решения, если знаменатели всех отношений равны нулю или положительны;
4) после выбора включаемой и исключаемой переменных осуществляется обычная операция преобразования строк сим- плекс-таблицы.
Пример 9.9. Найти min W(x) = 2x1 + x2 при ограничениях 3x1 + x2 ≥ 3;
4x1 + 3x2 ≥ 6;
x1 + 2x2 ≤ 3; x1, x2 ≥ 0.
После преобразований получим следующую задачу:
|
x1, x2 ≥ 0, s1, s2, s3 ≥ 0.
Начальная симплекс-таблица представлена в табл. 9.8.
В соответствии с условием допустимости в качестве ис- ключаемой из состава базисных выбирается переменная s2, поскольку имеет наибольшее отрицательное значение.
Таблица 9.8
| Базис | x 1 | x 2 | s 1 | s 2 | s 3 | Решение |
| Z | -2 | -1 | 0 | 0 | 0 | 0 |
| s 1 | -3 | -1 | 1 | 0 | 0 | -3 |
| s 2 | -4 | -3 | 0 | 1 | 0 | -6 |
| s 3 | 1 | 2 | 0 | 0 | 1 | 3 |
Включаемой в состав базисных является переменная x2, для которой характерно минимальное отношение коэффици- ента Z-строки к коэффициенту ведущей строки — 1/3 (для пе- ременной x1 это отношение составляет 1/2 > 1/3). Далее выпол- няется процедура пересчета симплекс-таблицы.
|
| Поделиться: |
