 |
 |
 |
 |
|
 |
 |
22
Название метода произошло от понятия симплекса. Напомним, что m-симплексом называют
выпуклый многогранник, аффинная оболочка* которого есть аффинное множество размерности m. В
данном случае можно считать, что система расширенных базисных столбцов {а
j1
,а
j2
,..., а
jm
},
рассматриваемых как точки в R
m+1
, порождает (m -1)-мерный симплекс в пространстве R
m+1
.
*
Аффинной оболочкой множества называют наименьшее аффинное множество, в котором содержится данное
множество.
В заключение настоящего пункта обобщим изложенные вопросы и приведем схему алгоритма
симплекс-метода для решения задачи максимизации. Она включает однократно выполняемый 0-этап и
повторяемый конечное число раз I-этап (стандартную итерацию).
0-этап. Нахождение допустимого базисного плана
(см. п. 1.4.5). Результатом 0-этапа является
допустимый базисный план х(?
(1)
), а также соответствующие ему матрица A(?
(1)
) и вектор b(?
(1)
),
которые будут использованы на первой итерации. Полагаем номер текущей итерации
q равным 1 и
переходим к I-этапу.
I-этап. Стандартная итерация алгоритма — выполняется для очередного базисного плана x(?
(q)
).
1°. Проверка оптимальности текущего базисного плана:
осуществляется просмотр строки оценок
а
0
(?
(q)
). Возможны два варианта:
1
?
. a
0
(?
(q)
)
?
0
— план, соответствующий текущему базису задачи, оптимален. Вычислительный
процесс закончен. Согласно формулам (1.33) и (1.32) выписываются оптимальный план задачи х
*
=
x(?
(q)
) и значение целевой функции f(x
*
)
=
f(x(?
(q)
)).
1
?
. В строке оценок а
0
(?
(q)
) существует по меньшей мере один элемент а
0,j
(?
(q)
)<0, т. е. имеющий
отрицательную оценку. Следовательно, план x(?
(q)
) —неоптимален. Выбирается столбец с номером l,
имеющий минимальную (максимальную по абсолютной величине) отрицательную оценку
Он называется ведущим и должен быть введен в очередной базис. Переходим к пункту 2° алгоритма.
2°. Определение столбца, выводимого из базиса. Рассматривается ведущий столбец а
l
(?
(q)
) Возможны
два варианта:
2'. Для всех i
1:m
а
i,l
(?
(q)
)
?
0. Делается вывод о неограниченности целевой функции и завершается
вычислительный процесс.
2". Существует по крайней мере одна строка с номером i
1:m, для которой а
i,l
(?
(q)
)>0 . Согласно
правилу (1.27) определяются место r и номер Nr (?
(q)
)
=
jr для столбца, выводимого из базиса. Переходим
к пункту 3° алгоритма.
3°. Пересчет элементов матрицы А и столбца b относительно нового базиса. В соответствии с
формулами (1.28)-(1.31) осуществляем расчет элементов матрицы задачи А и вектора ограничений b
относительно базиса ?
(q+1)
, который получается после введения в базис ?
(q)
столбца а
l
и выводом из него
столбца а®. Полагаем номер текущей итерации q: = q+l и переходим к первому пункту алгоритма.
Рис.1.5
1.4.2. Табличная реализация симплекс-метода. С точки зрения обеспечения рациональности и
наглядности вычислительного процесса выполнение алгоритма симплекс-метода удобно оформлять в
виде последовательности таблиц. В различных источниках приводятся разные модификации симплекс-
таблиц, отличающиеся друг от друга расположением отдельных элементов. Однако это не должно
вызывать смущения у читателя, так как все они базируются на одних и тех же принципах. Остановимся
на структуре таблицы, показанной на рис. 1.5.*
* Настоящая структура симплекс-таблиц строится на идеях и принципах их организации, предложенных в [1].
Симплекс-таблица Т
(q)
, изображенная на рис. 1.5, соответствует допустимому базису КЗЛП ?
(q)
),