Решение задач линейной оптимизации симплекс – методом (стр. 5 из 6)
Таблица 6.1 Таблица 6.2
| N |  |  | B |  | … |  |  | t | N | B |  |  | … |  |
| 1 |  |  |  |  | … |  |  | 1 |  |  |  | … |  | |
 | | | | | | | | | | | | | | |
| l |  |  |  |  | … |  |  |  | m |  |  |  | … |  |
| | | | | | | | | | m+1 | C |  |  | … |  |
| M |  |  |  |  | … |  |  | 0 |  |  |  | … |  | |
| m+1 | – | – |  |  | … |  |  | – | 1 |  |  |  | … |  |
| 2 |  |  |  | … |  | |||||||||
| … | … | … | … | … | … |
Краткое описание алгоритма.
1. Нулевая итерация:
а) составляется вспомогательная табл. 6.2, в которую вносятся параметры задачи; дополнительная строка таблицы с номером ν заполняется по мере выполнения ν-й итерации;
б) составляется основная табл. 6.1 с номером 0, в которой заполняются первые m строк, за исключением последних двух столбцов Аk и t. Элементы
и 
определяются скалярными произведениями (Cx, ej) и (Cx, B) соответственно. Нулевая итерация заканчивается заполнением нулевой дополнительной строки вспомогательной таблицы с оценками 
.2. (ν+1)-я итерация.
Пусть ν-я итерация закончена. В результате заполнена ν-я основная таблица, за исключением двух последних столбцов, и ν-я дополнительная строка вспомогательной таблицы. Просматривается эта строка. Если все
, то опорный план 
- решение задачи. Если хотя бы одна 
, то в базис вводится вектор Аk с 
(обычно 
). После этого заполняется столбец 
основной таблицы. В позицию (m+1) этого столбца заносится оценка 
вектора Аk. Остальные элементы этого столбца равны 
.Возможны два случая:
1) все
- задача неразрешима;2)
хотя бы для одного i. В этом случае, также как и в первом алгоритме, заполняется столбец (t) основной таблицы ν, определяется разрешающий элемент 
. Главная часть заполняется по рекуррентной формуле (6.3). Заполняется (ν+1)-я дополнительная строка вспомогательной таблицы. На этом заканчивается (ν+1)-я итерация.