Симлекс-метод (стр. 4 из 4)
Значение целевой функции a00 определяется из соотношения
.В столбце Bx записываем базисные переменные {xi} i= 1, ..., т. Их значения определяются столбиком свободных членов ai0, то есть
xi=ai0, i=1, 2,.,m.
Направляющие строка Ai и столбец Aj указываются стрелками. Если в качестве направляющего элемента выбран aij, то переход от данной симплекс таблицы к следующей определяется соотношениями (3.3.16) - (3.3.18).
Итак, алгоритм решения задачи ЛП табличным симплексом-методом состоит из этапов.
1. Рассчитывают и заполняют начальную симплекс-таблицу с допустимым единичным базисом, включая индексную строку.
3. В качестве направляющего столбца выбирают Aj, для которого
.3. Направляющая строка Aі выбирают из условия
4. Делают один шаг (итерацию) метода полного исключения Гаусса с направляющим элементом aij, для чего используют соотношения (3.3.16) - (3.3.18). В частности, элементы индексной строки новой таблицы вычисляют в соответствии с формулой
l=1,2, ..., n.Правильность вычислений контролируют по формулам непосредственного счета:
(3.3.23) 
(3.3.24)В столбце Bx новой таблицы заменяют xi на xj, а в столбце С ci на cj.
5. Если все a0l(k+1)³0, l=1,.,n, то новое базисное решение xi= ai0(k+1), iÎIб(k+1) - оптимально. В противном случае переходят к этапу 2 и выполняют очередную итерацию.
6. Второй, третий и четвертый этапы повторяют до тех пор, пока одна из итераций не закончится одним из двух исходов:
а) все a0l ³0. Это признак (критерий) оптимальности базисного решения последней симплекс-таблицы;
б) найдется такой a0j=Dj<0, что все элементы этого столбца arj£0,
r = 1, ., m. Это признак неограниченности целевой функции z=
cjxj на множестве допустимых решений задачи.Назовем некоторые особенности применения табличного симплекс-метода.
Если в качестве начального базиса выбирают базис из свободных переменных, для которых ci=0, то оценки для всех небазисных переменных равны Dj = a0j = -cj, а соответствующее значение целевой функции
a00=
cixi=0, iÎIб.Отсутствие векторов с отрицательными оценками при решении задач максимизации является признаком оптимальности соответствующего базисного решения.
Если существует такой небазисный вектор, для которого оценка отрицательна, а все элементы этого столбца неположительны, то целевая функция задачи в области допустимых решений неограничена.
При решении задач минимизации в базис вводится вектор с наибольшей положительной оценкой, а отсутствие таких векторов является признаком оптимальности последнего базисного решения.
Пример 3.4.
Максимизировать 4x1+3x2
при ограничениях
x1 £ 4000;
x2 £ 6000;
x1 +
x2 £ 6000;x1, x2 ³ 0.
Расширенная форма задачи имеет такой вид:
максимизировать 4x1+3x2
при ограничениях
1x1 + 0x2 + 1x3 + 0x4 + 0x5 = 4000;
0x1 + 1x2 + 0x3 + 1x4 + 0x5 = 6000;
1x1 + 2/3x2 + 0x3 + 0x4 + 1x5 = 6000;
Так как A0>0, а векторы A3, A4, A5 образуют единичный базис, то задачу можно решать методом симплекс-таблиц.
Первая итерация. Составляем и заполняем начальную симплекс-таблицу (табл.3.3).
Таблица 3.3. | Ci | 4 | 3 | 0 | 0 | 0 | ||
| Bx | Ai0 | A1 | A2 | A3 | A4 | A5 | |
 0 | X3 | 4000 | 1 | 0 | 1 | 0 | 0 |
| 0 | X4 | 6000 | 0 | 1 | 0 | 1 | 0 |
| 0 | X5 | 6000 | 1 | 1/3 | 0 | 0 | 1 |
| D | 0 | -4 | -3 | 0 | 0 | 0 |
Поскольку -4<-3<0, то направляющий столбец - первый.
Составив отношение вида
,определим направляющую строку.Для этого находим 
.Итак, направляющая строка -первая, направляющий элемент a11=1.
Выполнив первую итерацию симплекс-метода, получим табл. 3.4.Таблица 3.4.
| Ci | 4 | 3 | 0 | 0 | 0 | ||
| Bx | ai0 | A1 | A2 | A3 | A4 | A5 | |
| 4 | X1 | 4000 | 1 | 0 | 1 | 0 | 0 |
| 0 | X4 | 6000 | 0 | 1 | 0 | 1 | 0 |
 0 | X5 | 2000 | 0 | 2/3 | -1 | 0 | 1 |
| D | 160000 | 0 | -3 | 4 | 0 | 0 |
Вторая итерация. Как видим с табл. 3.4.,направляющий столбец - второй, а направляющая строка - третья, так как
Выполнив очередную итерацию симплекс-метода, получим симплекс-таблицу 3.5.
Таблица 3.5. | Ci | 4 | 3 | 0 | 0 | 0 | ||
| Bx | ai0 | A1 | A2 | A3 | A4 | A5 | |
| 4 | X1 | 4000 | 1 | 0 | 1 | 0 | 0 |
 0 | X4 | 3000 | 0 | 0 | 3/2 | 1 | -3/2 |
| 3 | X2 | 3000 | 0 | 1 | -3/2 | 0 | 3/2 |
| D | 250000 | 0 | 0 | -1/2 | 0 | 9/2 |
Третья итерация. Так как a03= -1/2 <0, то направляющий столбец A3, а направляющая строка - вторая, поскольку a23=3/3. Выполнив очередную итерацию с направляющим элементом a23=3/2, получим симплекс-таблицу 3.6.
Таблица 3.6.
| Ci | 4 | 3 | 0 | 0 | 0 | ||
| Bx | ai0 | A1 | A2 | A3 | A4 | A5 | |
| 4 | X1 | 2000 | 1 | 0 | 0 | -2/3 | 1 |
| 0 | X3 | 2000 | 0 | 0 | 1 | 2/3 | -1 |
| 3 | X2 | 6000 | 0 | 1 | 0 | 1 | 0 |
| D | 260000 | 0 | 0 | 0 | 1/3 | 4 |
Поскольку в индексной строке табл. 3.6. все оценки положительны, то найдено оптимальное решение: x1опт=2000, x2опт=6000, x3опт=2000.
Соответствующее значение целевой функции:
max (4x1+3x2)=a00=26000=4x1опт+3x2опт.
Симплекс-метод, известный также в нашей литературе под названием метода последовательного улучшения плана, впервые разработал Г.Данциг в 1947 г. Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов.
Симплекс-метод прост как для математического интуитивного понимания, так и для реализации, и преподается ныне в базовых вузовских курсах оптимальных задач.
Симплекс-метод был прост и понятен, но оказался экспоненциальным - для разных эвристик выбора следующей вершины обхода исследователи сумели построить набор задач, для решения которых симплекс-методу было необходимо экспоненциально большое число итераций. И все же долгое время симплекс-метод был даже теоретически лучшим известным алгоритмом для решения задач линейного программирования. Однако в конце 1970-х годов здесь состоялся один из самых знаменитых прорывов в теории сложности: Л. Г. Хачиян (везло нашим соотечественникам на фундаментальные открытия в этой области) построил алгоритм, который решает задачу линейного программирования за полиномиальное число шагов - так называемый метод эллипсоидов Хачияна. Суть алгоритма в том, чтобы окружить данный многогранник эллипсоидом, а затем постепенно сжимать этот эллипсоид; оказывается, на каждом этапе объем эллипсоида уменьшается в константное число раз.
Казалось бы, радость практиков должна быть беспредельной: полиномиальный алгоритм мог бы стать новым стандартом программирования. Но увы. Алгоритм Хачияна не просто плох, он безнадежен на практике. Существуют задачи размером в 50 переменных, для которых требуются более 24 тысяч итераций метода Хачияна, причем итерации эти отнюдь не тривиальны (хоть и полиномиальны, конечно). Количество итераций симплекс-метода в таких случаях исчисляется сотнями, если не десятками, и пересчет каждой из них гораздо проще. Метод эллипсоидов несравним с симплекс-методом: последний хоть и экспоненциален в худшем случае, однако на практике справляется с задачами ЛП многократно лучше. Все промышленные (да и кустарные) реализации решения ЛП основаны на симплекс-методе и его вариантах.
Список использованной литературы.
1. Лищенко «Линейное и нелинейное программирование», М. 2003
2. А.Н. Карасев, Н.Ш. Кремер, Т.Н. Савельева «Математические методы в экономике», М. 2000
3. Мину М. Математическое программирование. Теория и алгоритмы. М. 2004