Двойственный симплекс-метод

Двойственный симплекс-метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами. В обычном симплексном алгоритме план всегда должен быть допустимым. Допустимый план — это такой план, который удовлетворяет всем ограничениям задачи при обязательном условии неотрицательности неизвестных, то есть любые числа в итоговом столбце положительны. План называется недопустимым (или условно-оптимальным), если в итоговом столбце имеются отрицательные числа, зато оценки целевой строки соответствуют целевой функции, то есть являются положительными при решении на максимум и отрицательными при решении на минимум. В процессе решения двойственным методом план является недопустимым. При использовании двойственного метода сначала применяют обычную симплекс-процедуру и добиваются того, чтобы все оценки соответствовали цели решения задачи, причем пока не обращают внимания на знаки чисел в итоговом столбце. Только когда такой условно-допустимый план достигнут, смотрят на эти знаки. Если в итоговом столбце оказались отрицательные числа, план изменяется так, чтобы недопустимость уменьшилась, а затем и исчезла, но чтобы двойственные оценки продолжали соответствовать при этом цели решения задачи. Возможность придавать в процессе решения отрицательные значения неизвестным, входящим в план, в случае, если ограничения заданы неравенствами, позволяет избавиться от искусственных неизвестных, это сокращает размеры задачи, а значит, и вычислений[21].

Рассмотрим алгоритм решения задач двойственным симплексным методом.

1. Математическая модель прямой задачи линейного программирования должна быть в стандартной форме записи. В противном случае ее надо привести к стандартной форме записи.

2. Для прямой задачи составляется двойственная.

3. Обе задачи приводят к каноническому виду.

4. Выражают базисные переменные обеих задач через основные переменные.

5. Находят исходное решение прямой и двойственной задач и проверяют его на оптимальность. Для этого заполняют симплекс-таблицу двойственного симплекс-метода. Строки таблицы 1-го шага (верхние части клеток) заполняют по данным системы ограничений и целевой функции прямой задачи. Столбцы таблицы 1-го шага (верхние части клеток) заполняют по данным системы ограничений и целевой функции двойственной задачи.

Симплексная таблица двойственного симплекс-метода имеет следующий вид:

yбаз ym+1 ym+2 ¼ ym+n Двойственный симплекс-метод - student2.ru  
yсв xсв xбаз - x1 - x2 ¼ - xn bi  
y1 xn+1 h11 h12 ¼ h1n l1  
 
y2 xn+2 h21 h22 ¼ h2n l2  
¼ ¼ ¼ ¼ ¼ ¼ ¼  
ym xn+m hm1 hm2 ¼ hmn lm  
cj Двойственный симплекс-метод - student2.ru - c1 - c2 ¼ - cn Двойственный симплекс-метод - student2.ru  

Решение является оптимальным, если в строке Двойственный симплекс-метод - student2.ru и столбце bi нет отрицательных элементов.

В противном случае следует провести изменения в базисных переменных.

6. Выбор разрешающей строки. Находят отрицательный элемент в строке Двойственный симплекс-метод - student2.ru . В столбце над этим найденным элементом выбирают любой положительный элемент, эта строка – разрешающая.

Если в столбце над найденным элементом нет положительных элементов, то ПЗЛП не имеет смысла (целевая функция не ограничена в области допустимых решений), а ДЗЛП не имеет решения.

7. Выбор разрешающего столбца. Элементы строки Двойственный симплекс-метод - student2.ru делят на соответствующие элементы разрешающей строки под переменными. Из полученных отношений выбирают максимальное отрицательное отношение, этот столбец – разрешающий (максимальным из отрицательных отношений может быть отношение Двойственный симплекс-метод - student2.ru – отрицательный ноль).

Если среди полученных отношений нет отрицательных, то ПЗЛП не имеет решения, ДЗЛП не имеет смысла или решения.

На пересечении разрешающей строки и разрешающего столбца получен разрешающий элемент.

8. Заполнение нижних частей клеток таблицы. Под разрешающим элементом всегда ставят «1». Остальные элементы разрешающей строки переписываются без изменений. Остальные элементы разрешающего столбца переписываются с противоположным знаком. Остальные элементы таблицы находят по правилу прямоугольника: искомый элемент умножают на разрешающий и из этого произведения вычитают произведение элементов, расположенных на противоположной диагонали прямоугольника, образуемого искомым и разрешающим элементами (все элементы из верхних клеток).

9. Построение новой симплекс-таблицы. Изменяют базисные переменные: меняют местами переменные из разрешающей строки и разрешающего столбца. Элементы из нижних клеток предыдущей симплекс-таблицы делят на верхний разрешающий элемент и записывают на соответствующие места в верхние клетки новой симплекс-таблицы.

Если в новой таблице в строке Двойственный симплекс-метод - student2.ru есть отрицательные элементы, то следует сделать следующий шаг симплекс-метода. (Нецелесообразно выбирать за разрешающую строку – те же строки, что и на предыдущих шагах).

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

Если в строке Двойственный симплекс-метод - student2.ru есть нулевой элемент, то это признак альтернативного оптимума для ПЗЛП. Для нахождения альтернативного решения выполняется еще один шаг симплекс-метода: Столбец с нулевым элементом в строке Двойственный симплекс-метод - student2.ru выбирается за разрешающий. Находят неотрицательные отношения столбца свободных членов к соответствующим элементам разрешающего столбца. Из полученных отношений выбирают минимальное неотрицательное отношение – это разрешающая строка, разрешающий элемент найден. Затем выполняют еще один шаг симплекс-метода.

Если в столбце Двойственный симплекс-метод - student2.ru есть нулевой элемент, то это признак альтернативного оптимума для ДЗЛП. Для нахождения альтернативного решения выполняется еще один шаг симплекс-метода. При этом строка с нулевым элементом в столбце Двойственный симплекс-метод - student2.ru выбирается за разрешающую.

Рассмотрим решение задачи из п. 4.3 двойственным симплекс-методом.

Канонический вид:

Двойственный симплекс-метод - student2.ru Двойственный симплекс-метод - student2.ru

Двойственный симплекс-метод - student2.ru Двойственный симплекс-метод - student2.ru

Выразим базисные переменные через свободные:

Двойственный симплекс-метод - student2.ru Двойственный симплекс-метод - student2.ru

Введем соответствие основных переменных прямой задачи и дополнительных переменных двойственной задачи, а также дополнительных переменных прямой задачи и основных переменных двойственной задачи:

х1 Двойственный симплекс-метод - student2.ru y4 х2 Двойственный симплекс-метод - student2.ru y5 х3 Двойственный симплекс-метод - student2.ru y1 х4 Двойственный симплекс-метод - student2.ru y2 х5 Двойственный симплекс-метод - student2.ru y3

Составим симплекс-таблицу

yбаз y4 y5 Двойственный симплекс-метод - student2.ru
yсв xсв xбаз - x1 - x2 bi
y1 x3 2 4
y2 x4 «1»
y3 x5 1 8
cj Двойственный симплекс-метод - student2.ru - 3 - 4 0

Решение ПЗЛП выписывается по строкам, значения базисных переменных берутся из столбца bi, если переменная с соответствующим индексом не входит в базис, то ее значение равно нулю: Двойственный симплекс-метод - student2.ru = (0, 0, 4, 3, 8), Двойственный симплекс-метод - student2.ru = 0.

Решение ДЗЛП выписывается по столбцам, значения базисных переменных берутся из строки cj, если переменная с соответствующим индексом не входит в базис, то ее значение равно нулю: Двойственный симплекс-метод - student2.ru = (0, 0, 0, -3, -4), Двойственный симплекс-метод - student2.ru = 0.

Данное решение не является оптимальным, поскольку решение не допустимое (не выполнено условие неотрицательности переменных), ему соответствуют отрицательные элементы в строке Двойственный симплекс-метод - student2.ru .

Над минимальным отрицательным элементом «-4» в строке Двойственный симплекс-метод - student2.ru выбираем положительный, например «1», в строке x4, следовательно, эта строка – разрешающая (выделена жирным шрифтом).

Находим максимальное отношение среди отношений элементов в строке целевой функции Двойственный симплекс-метод - student2.ru к соответствующим элементам разрешающей строки

Двойственный симплекс-метод - student2.ru .

Поскольку максимальное отношение соответствует первому столбцу, то – он разрешающий (выделен жирным шрифтом).

Разрешающий элемент «1» находится на пересечении разрешающей строки и разрешающего столбца.

Заполняем нижние части клеток. Под разрешающим элементом ставим «1». В разрешающей строке остальные элементы переписываем без изменения, а в разрешающем столбце остальные элементы записываем с противоположным знаком. Оставшиеся клетки заполняем по правилу прямоугольника:

клетка на пересечении первой строки и второго столбца:

2
«1»

2×1 - 1×1 = 1;

клетка на пересечении третьей строки и второго столбца:

«1»
1

1×1 - 2×1 = -1;

клетка на пересечении четвертой строки и второго столбца:

«1»
¼ ¼
- 3 - 4

- 4×1 - (-3)×1 = -1;

клетка на пересечении первой строки и третьего столбца:

¼ 4
«1» ¼

4×1 - 3×1 = 1;

клетка на пересечении третьей строки и третьего столбца:

«1» ¼
¼ 8

8×1 - 3×2 = 2;

клетка на пересечении четвертой строки и третьего столбца:

«1» ¼
¼ ¼ ¼
- 3 ¼ 0

0×1 - 3×(-3) = 9;

Таким образом, получаем следующую таблицу:

yбаз y4 y5 Двойственный симплекс-метод - student2.ru
yсв xсв xбаз - x1 - x2 bi
y1 x3 -1 2 1 4 1
y2 x4 «1»
y3 x5 -2 1 -1 8 2
cj Двойственный симплекс-метод - student2.ru - 3 - 4 -1 0 9

Переходим к следующей симплекс-таблице. При этом в базис включается пара переменных х1, у4, соответствующих разрешающему столбцу, а из базиса выводится пара переменных х4, у2, соответствующая разрешающей строке. В следующей таблице данные пары переменных меняются местами. Верхние части клеток заполняются элементами, полученными в результате деления соответствующих (стоящих на аналогичном месте) элементов из предыдущей таблицы в нижних частях клеток на разрешающий элемент «1»:

yбаз y2 y5 Двойственный симплекс-метод - student2.ru
yсв xсв xбаз - x4 - x2 bi
y1 x3 -1 1
y3 x1 1 3
y3 x5 -2 -1 2
cj Двойственный симплекс-метод - student2.ru 3 -1 9

Решение ПЗЛП на втором шаге двойственного симплекс-метода также выписывается по строкам: Двойственный симплекс-метод - student2.ru = (3, 0, 1, 0, 2), Двойственный симплекс-метод - student2.ru = 9, решение ДЗЛП выписывается по столбцам: Двойственный симплекс-метод - student2.ru = (0, 3, 0, 0, -1), Двойственный симплекс-метод - student2.ru = 9. Данное решение также не оптимальное, поскольку еще остался отрицательный элемент «-1». Необходим еще один шаг двойственного симплекс-метода.

Над отрицательным элементом «-1» в строке Двойственный симплекс-метод - student2.ru выбираем положительный, предпочтительнее «1», в строке x3, поскольку вторая строка была выбрана на предыдущем шаге метода, следовательно, первая строка – разрешающая (выделена жирным шрифтом).

Находим максимальное отношение среди отношений элементов в строке целевой функции Двойственный симплекс-метод - student2.ru к соответствующим элементам разрешающей строки

Двойственный симплекс-метод - student2.ru .

Поскольку максимальное отношение соответствует второму столбцу, то – он разрешающий (выделен жирным шрифтом).

Разрешающий элемент «1» находится на пересечении разрешающей строки и разрешающего столбца.

Заполняем нижние части клеток. Под разрешающим элементом ставим «1». В разрешающей строке остальные элементы переписываем без изменения, а в разрешающем столбце остальные элементы записываем с противоположным знаком. Оставшиеся клетки заполняем по правилу прямоугольника аналогично предыдущему шагу метода, получаем следующую таблицу:

yбаз y2 y5 Двойственный симплекс-метод - student2.ru
yсв xсв xбаз - x4 - x2 bi
y1 x3 -1 -1 «1» 1
y3 x1 1 2 -1 3 2
y3 x5 -2 -3 -1 1 2 3
cj Двойственный симплекс-метод - student2.ru 3 2 -1 1 9 10

Переходим к следующей симплекс-таблице. При этом в базис включается пара переменных х2, у5, соответствующих разрешающему столбцу, а из базиса выводится пара переменных х3, у2, соответствующая разрешающей строке. В следующей таблице данные пары переменных меняются местами. Клетки следующей таблицы заполняются элементами, полученными в результате деления соответствующих элементов из предыдущей таблицы в нижних частях клеток на разрешающий элемент «1». Поскольку в нижних частях клеток таблицы все элементы положительные и разрешающий элемент также положительный, то в следующей таблице будет получено оптимальное решение и нет необходимости делить на две части клетки в последней таблице:

yбаз y2 y1 Двойственный симплекс-метод - student2.ru
yсв xсв xбаз - x4 - x3 bi
y5 x2 -1 1 1
y3 x1 2 -1 2
y3 x5 -3 1 3
cj Двойственный симплекс-метод - student2.ru 2 1 10

Оптимальное решение ПЗЛП: Двойственный симплекс-метод - student2.ru = (2, 1, 0, 0, 3), Двойственный симплекс-метод - student2.ru = 10, оптимальное решение ДЗЛП: Двойственный симплекс-метод - student2.ru = (1, 2, 0, 0, 0), Двойственный симплекс-метод - student2.ru = 10.

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

Наши рекомендации