Через конечное число шагов симплекс-метод позволяет также установить неразрешимость задачи.
Рассмотрим каждый этап более подробно.
Этап 1.
Вычислительная схема симплекс-метода применима лишь к задачам, записанным в канонической базисной форме. Для таких задач известен начальный опорный план и соответствующий ему базис. Для рассматриваемых задач с “первыми” базисными переменными вида (2.5) или (2.12) начальный опорный план с n компонентами имеет вид
X = ( b1, b2, … , bm , 0, …, 0) или X = ( b¢1, b¢2, … , b¢m , 0, …, 0) .
Если задача ЛП поставлена в другой форме, то существуют различные способы перехода к требуемой форме, изложенные в подразделе 2.2.
Напомним, что если задача ЛП записана в стандартной форме (2.1), то переход от системы неравенств к системе уравнений осуществляется путем введения m дополнительных неотрицательных переменных xn+i ³ 0 (i=1, …, m) , которые входят также и в целевую функцию с нулевыми коэффициентами. Эти m переменных, являющиеся “пос-ледними” в векторе переменных оптимизации, будут одновременно и базисными (соответствующие им векторы Aj образуют начальный еди-ничный базис системы).
Начальный опорный план для этого случая имеет n+m компонент и имеет следующий вид
X = (0, 0, …, 0 , b1, b2, … , bm ) . (2.16)
З а м е ч а н и е 2.15. Для задачи ЛП, записанной в канонической форме, не имеющей начального единичного базиса, используется специальный прием определения начального базисного решения, рассматриваемый ниже.
Этап 2.
На этом этапе используются специальные выражения, рассчитав значения которых можно судить о том, является ли рассматриваемый план оптимальным. Такими выражениями являются разности
Dj = zj - cj, j =1, …, n; (2.17)
подсчитываемые для всех переменных задачи оптимизации. Такие разности называются оценками переменных xj (оценками плана).
В выражении (2.17)
zj = 
ci aij,
j =1, …, n ; (2.18)
где IB – множество индексов (номеров) базисных переменных. (Можно сказать, что в (2.18) суммирование производится по всем базисным переменным).
В [4…6] приводятся доказательства теорем, позволяющих сформулировать для задачи максимизации следующий критерий оптимальности (критерий оценки оптимальности плана): опорный план (допустимое базисное решение) является оптимальным, если для всех j=1,.., n выполняется условие
Dj = zj - cj ³ 0 (2.19)
(такое условие часто называют условием неотрицательности оценок).
Для задачи минимизации аналогичное условие имеет вид
Dj = zj - cj £ 0 . (2.20)
Если исходная задача ЛП имела стандартную форму, то после нахождения оптимального плана преобразованной задачи с дополнительными переменными необходимо перейти к плану исходной задачи. Такой переход базируется на следующем положении [4]: если оптимальный план канонической задачи имеет вид
(x*1, x*2, …, x*n , x*n+1, …, x*n+m) , то оптимальный план стандартной задачи будет иметь вид
(x*1, x*2, …, x*n ).
(Можно сказать, что оптимальный план стандартной задачи получается из оптимального плана канонической задачи путем удаления из него дополнительных переменных).
Этап 3.
Переход к новому опорному плану в симплекс-методе осуществляется посредством перехода от одного единичного базиса системы к другому. Такой переход осуществляется путем исключения из базиса одного вектора As и включенияв базис вместо него другого вектора Ar. При этом в базис вводится тот вектор, который обеспечивает наибольшее «приращение» ЦФ, а выводится тот вектор, для которого ранее других векторов нарушается условие неотрицательности, т.е выполняется соотношение xr = 0). Необходимый перерасчет коэффициентов системы уравнений, вызванный сменой базиса, осуществляется с помощью рассмотренного выше метода Жордана – Гаусса.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.