 |
 |
 |
 |
|
 |
 |
28
базисного плана, переносится в таблицу T2
(1)
.
4. Полагаем номер текущей итерации q равным 1 и переходим к I-этапу.
1-этап. Стандартная итерация алгоритма — выполняется для очередного базисного плана x(?
(q)
).
1°. Проверка оптимальности текущего базисного плана. Содержимое нулевой строки таблицы T2
(q)
— ?
0
(?
(q)
) переписывается в соответствующую графу таблицы T1. По формуле (1.42) рассчитываем и
заполняем строку a
0
(?
(q)
). Осуществляем просмотр строки оценок a
0
(?
(q)
). Возможны два варианта:
1?. a
0
(?
(q)
)
?0
—план, соответствующий текущему базису задачи, оптимален. Вычислительный
процесс закончен. Согласно формулам (1.33) и (1.32) выписываются оптимальный план задачи х* =
x(?
(q)
) и оптимальное значение целевой функции f(х*) = f(x(?
(q)
)).
1". В строке оценок a
0
(?
(q)
)
существует по меньшей мере один элемент a
0,j
(?
(q)
)<0, т. е. имеющий
отрицательную оценку. Следовательно, план x(?
(q)
) —
неоптимален. Выбирается номер l,
соответствующий элементу, имеющему минимальную (максимальную по абсолютной величине)
отрицательную оценку:
l-й столбец матрицы A становится ведущим и должен быть введен в очередной базис. Переходим к
пункту 2° алгоритма.
2°. Определение столбца, выводимого из базиса. Переписываем ведущий столбец а
l
из таблицы T1 в
текущую таблицу Т2
(q)
. По формуле а
l
(?
(q)
) = ?
-1
(?
(q)
)а
l
заполняем соответствующий столбец в таблице
Т2
(q)
. Возможны два варианта:
2'. Для всех i
1: m а
i,l
(?
(q)
)
?
0. Делается вывод о неограниченности целевой функции и завершается
вычислительный процесс.
2". Существует по крайней мере один индекс
i
1: m, для которого а
i,l
(?
(q)
)>0. Согласно правилу
(1.27) определяются место r и номер Nr(?
(q)
) для столбца, выводимого из базиса. Переходим к пункту 3°
алгоритма.
3°. Пересчет относительно нового базиса элементов столбца b и матрицы
?
-1
. Переход к новому
базису
?
(q+1)
, который получается введением в базис
?
(q)
столбца а
l
и выводом из него столбца а®,
осуществляется по формулам, аналогичным формулам (1.28)-(1.31). Они имеют вид:
Полагаем номер текущей итерации q: =q+l и переходим к первому пункту алгоритма.
В завершение подчеркнем, что в силу приведенных выше преимуществ именно модифицированный
симплекс-метод реально применяется в программном обеспечении, предназначенном для решения
канонических задач линейного программирования.
1.5.2. Пример решения ЗЛП модифицированным симплекс-методом. Приведем решение
рассмотренной ранее задачи (1.34)-(1.35), основанное на использовании процедуры модифицированного
симплекс-метода. По аналогии с п. 1.4.3 оно начинается с выбора очевидного исходного базиса, обра-
зуемого столбцами {5,2,3}. Для него уже были вычислены ?
-1
(?
(q)
) и b(?
(q)
), поэтому заполнение
начальных таблиц T1 и Т2
(1)
не представляет труда.
На первой итерации мы переписываем нулевую строку