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

17. ДВОЙСТВЕННЫЙ  СИМПЛЕКСНЫЙ МЕТОД

План :

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

Иногда для получения оптимального решения исходной задачи переходят к двойственной и, используя оценки её оптимального плана,  определяют оптимальное решение исходной задачи. Переход к двойственной задаче не обязателен, так как если рассмотреть первую симплексную таблицу с m единичным базисом, то легко заметить, что в столбцах записана исходная задача, а в строках - двойственная. Причём оценками плана исходной задачи являются  [pic 1], а оценками плана  двойственной  задачи - [pic 2].

Решим двойственную задачу по симплексной таблице, в которой записана исходная задача. Найдём оптимальный план двойственной задачи, а вместе с ним и оптимальный план исходной задачи. Этот метод называется двойственным симплексным методом.

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

[pic 3]

выбирают вектор подлежащий исключению из базиса,  затем определяют вектор, который необходимо включить в базис. Для  этого находят

[pic 4].

Если этот минимум достигается при [pic 5], тогда вектор [pic 6] включают в базис, т.е. [pic 7]будет разрешающим элементом.  Симплексная    таблица преобразовывается как в обычном симплексном методе. Этот процесс продолжают до тех пор, пока из столбца вектора [pic 8] не будут исключены отрицательные элементы. В результате находим оптимальный план исходной задачи, а следовательно, и двойственной.

Если на некотором шаге окажется,  что в   [pic 9]- й строке симплексной таблицы в столбце вектора  [pic 10] стоит отрицательное число  [pic 11],  а среди остальных элементов  этой строки нет отрицательных, то  исходная задача не имеет решения.

Пример.     Следующую задачу

[pic 12]

[pic 13]

[pic 14]

[pic 15]

[pic 16],  [pic 17],  [pic 18]

решить двойственным симплексным методом.

 Решение. Эту задачу не трудно привести к следующему виду:

[pic 19]

[pic 20]

[pic 21]

[pic 22]

[pic 23],  [pic 24],  [pic 25],  [pic 26],  [pic 27]

[pic 28]Выбрав в качестве базиса векторы  [pic 29], [pic 30] и [pic 31]  составим   первоначальную симплексную таблицу для исходной задачи:

В столбце вектора [pic 43]  имеются два отрицательных числа (-4 и -6)  и в строках векторов [pic 44] и [pic 45] имеются отрицательные числа.  ( Если бы они отсутствовали, то задача была бы неразрешима). Вектор, подлежащий  исключению выбираем из условия