Реферат: Симлекс-метод

Так как 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опт.

3. Заключение.

Симплекс-метод, известный также в нашей литературе под названием метода последовательного улучшения плана, впервые разработал Г.Данциг в 1947 г. Этот метод позволяет переходить от одного допустимого базисного решения к другому, причем так, что значения целевой функции непрерывно возрастают. В результате оптимальное решение находят за конечное число шагов.

Симплекс-метод прост как для математического интуитивного понимания, так и для реализации, и преподается ныне в базовых вузовских курсах оптимальных задач.

Симплекс-метод был прост и понятен, но оказался экспоненциальным - для разных эвристик выбора следующей вершины обхода исследователи сумели построить набор задач, для решения которых симплекс-методу было необходимо экспоненциально большое число итераций. И все же долгое время симплекс-метод был даже теоретически лучшим известным алгоритмом для решения задач линейного программирования. Однако в конце 1970-х годов здесь состоялся один из самых знаменитых прорывов в теории сложности: Л. Г. Хачиян (везло нашим соотечественникам на фундаментальные открытия в этой области) построил алгоритм, который решает задачу линейного программирования за полиномиальное число шагов - так называемый метод эллипсоидов Хачияна. Суть алгоритма в том, чтобы окружить данный многогранник эллипсоидом, а затем постепенно сжимать этот эллипсоид; оказывается, на каждом этапе объем эллипсоида уменьшается в константное число раз.

Казалось бы, радость практиков должна быть беспредельной: полиномиальный алгоритм мог бы стать новым стандартом программирования. Но увы. Алгоритм Хачияна не просто плох, он безнадежен на практике. Существуют задачи размером в 50 переменных, для которых требуются более 24 тысяч итераций метода Хачияна, причем итерации эти отнюдь не тривиальны (хоть и полиномиальны, конечно). Количество итераций симплекс-метода в таких случаях исчисляется сотнями, если не десятками, и пересчет каждой из них гораздо проще. Метод эллипсоидов несравним с симплекс-методом: последний хоть и экспоненциален в худшем случае, однако на практике справляется с задачами ЛП многократно лучше. Все промышленные (да и кустарные) реализации решения ЛП основаны на симплекс-методе и его вариантах.

Список использованной литературы.

1. Лищенко «Линейное и нелинейное программирование», М. 2003