Алгоритм обратной матрицы
Опишем алгоритм применительно к решению ЗЛП, записанной в канонической форме с односторонними ограничениями:
Пусть известен начальный опорный план с базисом , т.е. - базисные компоненты, - небазисные компоненты.
В данном методе все параметры итерации, необходимые для оценки плана на оптимальность и перехода к лучшему плану, вычисляются через элементы обратной матрицы . Поэтому второй алгоритм симплекс-метода также называют алгоритмом обратной матрицы.
Вычисления удобно выполнять, используя две симплекс-таблицы:
Основная таблица
№ |
P |
… |
t |
|||||
1 |
… |
… |
||||||
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
||||||||
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
… |
|||||||
|
|
… |
|
Вспомогательная таблица
№ |
… |
|||
1 |
… |
|||
… |
… |
… |
… |
… |
… |
||||
|
… |
|||
0 |
… |
|||
1 |
… |
|||
2 |
… |
|||
… |
… |
… |
… |
… |
Порядок вычислений по второму алгоритму
Шаг 1. Найти обратную матрицу и заполнить её элементами столбцы , основной симплекс-таблицы.
Шаг 2. Вычислить значение линейной формы как скалярное произведение столбцов и основной таблицы. Результат занести в строку столбца основной симплекс-таблицы.
Шаг 3. Вычислить значения элементов вектора-строки по формуле , как скалярное произведение столбцов и основной симплекс-таблицы. Полученными значениями заполнить -ю строку основной симплекс-таблицы.
Шаг 4. Найти значения оценок векторов условий относительно базиса по формуле , , как произведение вектора-строки основной таблицы на соответствующий столбец вспомогательной таблицы минус соответствующий коэффициент линейной формы, записанный в -ой строке вспомогательной таблицы. Полученные значения занести в строку вспомогательной таблицы с номером, соответствующим номеру выполняемой итерации.
Шаг 5. Проверить оптимальность опорного плана.
-
Если все оценки неотрицательные (), то - оптимальный опорный план и, тогда, в столбце основной симплекс-таблицы записано решение ЗЛП, а именно, значения базисных компонент оптимального опорного плана и соответствующее ему максимальное значение линейной формы. На этом процесс решения ЗЛП завершается.
-
Если среди оценок найдутся отрицательные (), то для построения нового опорного плана необходимо найти вектор, который будет вводиться в базис. Он определяется по номеру наименьшей отрицательной оценки и, таким образом, устанавливается разрешающий столбец .
Шаг 6. Вычислить коэффициенты разложения вектора по базису , используя формулу , как произведение -ой строки обратной матрицы из основной таблицы на столбец вспомогательной таблицы. Полученные значения занести в столбец основной симплекс-таблицы.
Шаг 7. Определить вектор, выводимый из базиса. Для этого необходимо заполнить столбец основной таблицы значениями путем деления элементов столбца основной таблицы на соответствующие им по номеру элементы столбца основной таблицы.
-
Если все , то исходная задача неразрешима в силу неограниченности сверху линейной формы . На этом процесс решения ЗЛП завершается.
-
Если , то необходимо выбрать . Пусть им оказался элемент с номером , т.е. . Тогда соответствующий этому индексу вектор должен выводиться из базиса. Элемент является «разрешающим». На этом нулевая итерация завершена и надлежит приступить к выполнению следующей итерации.
Шаг 8. Для заполнения новой основной таблицы вычислить по рекуррентным формулам новые значения параметров итерации.
-
Заполнить -тую строку новой основной таблицы элементами ,, получающимися делением соответствующих элементов () -той строки старой основной таблицы на разрешающий элемент , т.е. по формулам .
-
Все остальные -тые строки главной части новой основной симплекс-таблицы получить как результат вычитания из -той строки старой основной симплекс-таблицы -той строки новой симплекс-таблицы, умноженной на соответствующий -тый элемент разрешающего столбца старой основной симплекс-таблицы, т.е. в соответствии с рекуррентными формулами . По аналогичным формулам могут быть вычислены также и элементы -й строки: .
Описанный процесс построения симплекс-таблиц повторяется до получения оптимального опорного плана или до установления неограниченности линейной формы, т.е. неразрешимости ЗЛП.
О конечности симплекс - метода
Пусть ЗЛП является невырожденной. Тогда на каждом шаге симплекс – метода будем иметь . Процесс расчета будет состоять в переходе
,
где два соседних базиса отличаются лишь одним вектором. Например, переход от к осуществлен введением вектора . При этом линейная форма изменится так:
,
т.к. и .
Таким образом, при переходе от одного опорного плана к другому в невырожденной задаче линейная форма возрастает. Поэтому невозможен возврат к старому опорному плану, т.е. каждый шаг симплекс – метода приводит к новому, ранее не встречавшемуся, опорному плану. И поскольку число опорных планов (вершин многогранного множества ) конечно, то в невырожденной задаче через конечное число шагов либо устанавливается неограниченность линейной формы, либо получается оптимальный план.
Пусть ЗЛП является вырожденной. Тогда у вырожденного опорного плана может быть (но не обязательно) и поэтому может быть .
Не приведет ли это к бесконечному числу шагов? В силу конечности числа вершин множества это может быть лишь тогда, когда через несколько шагов мы вернемся к исходному базису. Следовательно, должны встречаться цепочки
в которых начальное и конечное звенья совпадают, т.е. . Такие цепочки называются циклами. Для них . Но так как любые соседние опорные планы доставляют значение линейной формы , то, очевидно,
.
Таким образом, цикл означает переход от одного базиса опорного плана к другому базису того же вырожденного опорного плана. Причем, через некоторое число таких переходов имеет место возвращение к ранее встретившемуся базису. В случае образования цикла, т.е. зацикливания, всегда можно выйти из него, специальным образом выбрав «разрешающий элемент».