Алгоритм 3 Симплекс преобразования на основе укороченных симплекс таблиц для решения двойственной задачи Линейного программирования

 

Изначально имеем систему неравенств и целевую функцию , для которой необходимо определит максимум для заданной системы неравенств. Переменные - Свободные Переменные (СП).

Данная постановка задачи Линейного программирования называется Прямой задачей Линейного программирования.

Укороченная симплекс таблица для прямой задачи линейного программирования следующая:

CП БП		…		B
		…
…	…	…	…	…
		…
Z		…

 

 

Для любой Прямой задачи Линейного программирования можно построить Двойственную задачу Линейного программирования, которая выглядит так: дана система неравенств и целевая функция , для которой необходимо определить минимум для заданной системы неравенств.

При этом решение двойственной задачи Линейного программирования будет решением Прямой задачи Линейного Программирования.

 

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

 

Тогда укороченная симплекс таблица примет вид для двойственной задачи Линейного программирования:

 

СП БП		…		C
		…
…	…	…	…	…
		…
T		…

Замечание 1: Все элементы столбца свободных членов C должны быть отрицательны.

Замечание 2: Для дальнейшего удобства обозначим элемент в T строке и C столбце .

 

1 Выбирается разрешающую строку k, соответствующую наименьшему отрицательному элементу в С столбце

2. Выбирается разрешающий столбец l, который соответствует наименьшему положительному из отношений элементов T-строки на соответствующие элементы разрешающей строки:

Замечание: Если все отношения , значит, целевая функция T неограниченно уменьшается, и решения нет. Необходимо прекратить симплекс преобразование.

 

1. Элемент стоящий на пересечении разрешающего столбца и разрешающей строки называется разрешающим элементом:
2. Переходим к новой симплекс таблице по следующим правилам:
1. Меняем местами СП и БП соответствующие разрешающему элементу.
2. На месте разрешающего элемента в новой таблице стоит величина ему обратная:
   

 

c. Все элементы разрешающей строки делятся на разрешающее число с обратным знаком, включая элемент последнего столбца:

 

1. Все элементы разрешающего столбца делятся на разрешающее число, включая элемент последней строки:

 

1. Все остальные элементы матрицы вычисляются по формулам:

5. Если все элементы в C столбце симплекс таблицы положительны, следовательно, оптимальное решение найдено, которое равно .

6. Если в C столбце симплекс таблицы найдется хотя бы один отрицательный элемент, то необходимо выполнить еще одно симплекс преобразование к симплекс таблице , согласно п.1-6 приведенного выше алгоритма.

7. Решив Двойственную задачу Линейного Программирования, можно получить решение Прямой задачи Линейного программирования, введя следующее соответствие между СП и БП Прямой и Двойственных задач Линейного программирования:

СП			БП
		….						….
↕	↕		↕			↕	↕		↕
		…						…
БП			СП

 

 

И при этом T_min=Z_max=z^*

Транспонируя симплекс таблицу для двойственной задачи ЛП и вводя переменный x_i вместо переменных (±y_i), получим оптимальный план решения прямой задачи – необходимо смотреть соответствующие значения в столбце свободных членов.