Автор работы: Пользователь скрыл имя, 11 Мая 2012 в 10:02, контрольная работа
Симлекс-метод - это характерный пример итерационных вычислений. используемых при решении большинства оптимизационных задач.
В вычислительной схеме симплекс-метода реализуется упорядоченный процесс, при котором, начиная с некоторой исходной допустимой угловой точки ( обычно начало координат ), осуществляются последовательные переходы от одной допустимой экстремальной точки к другой до тех пор, пока не будет найдена точка, соответствующая оптимальному решению.
Введение. 3
1. Общая характеристика симплекс метода. 4
2. Решение различных задач симплекс методом. 11
3. Табличный симплекс метод. 21
3. Заключение. 29
Список использованной литературы. 31
Если в качестве начального базиса выбирают базис из свободных переменных, для которых ci=0, то оценки для всех небазисных переменных равны Dj = a0j = -cj, а соответствующее значение целевой функции
a00= cixi=0, iÎIб.
Отсутствие векторов с отрицательными оценками при решении задач максимизации является признаком оптимальности соответствующего базисного решения.
Если существует такой небазисный вектор, для которого оценка отрицательна, а все элементы этого столбца неположительны, то целевая функция задачи в области допустимых решений неограничена.
При решении задач минимизации в базис вводится вектор с наибольшей положительной оценкой, а отсутствие таких векторов является признаком оптимальности последнего базисного решения.
Пример
3.4.
Максимизировать 4x1+3x2
при ограничениях
x1 £ 4000;
x2 £ 6000;
x1 + x2 £ 6000;
x1, x2 ³ 0.
Расширенная форма задачи имеет такой вид:
при ограничениях
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.
|
Поскольку -4<-3<0, то направляющий столбец - первый.
Составив отношение вида ,определим направляющую строку.Для этого находим
.
Итак, направляющая строка -первая, направляющий элемент a11=1.
Выполнив первую итерацию симплекс-метода, получим табл. 3.4.
Таблица 3.4.
|
В
т
о
р
а
я
и
т
е
р
а
ц
и
я.
К
а
к
в
и
д
и
м
с
т
а
б
л.
3.
4.,
н
а
п
р
а
в
л
я
ю
щ
и
й
с
т
о
л
б
е
ц
-
в
т
о
р
о
й
,
а
н
а
п
р
а
в
л
я
ю
щ
а
я
с
т
р
о
к
а
-
т
р
е
т
ь
я
,
т
а
к
к
а
к
В
ы
п
о
л
н
и
в
о
ч
е
р
е
д
н
у
ю
и
т
е
р
а
ц
и
ю
с
и
м
п
л
е
к
с-
м
е
т
о
д
а,
п
о
л
у
ч
и
м
с
и
м
п
л
е
к
с-
т
а
б
л
и
ц
у
3.
5.
Т
а
б
л
и
ц
а
3.
5.
|
Третья итерация. Так как a03= -1/2 <0, то направляющий столбец A3, а направляющая строка - вторая, поскольку a23=3/3. Выполнив очередную итерацию с направляющим элементом a23=3/2, получим симплекс-таблицу 3.6.
Таблица 3.6.
|
Поскольку в индексной строке табл. 3.6. все оценки положительны, то найдено оптимальное решение: x1опт=2000, x2опт=6000, x3опт=2000.
Соответствующее значение целевой функции:
max
(4x1+3x2)=a00=26000=4x1опт+
Заключение.
Симплекс-метод,
известный также в нашей
Симплекс-метод прост как для математического интуитивного понимания, так и для реализации, и преподается ныне в базовых вузовских курсах оптимальных задач.
Симплекс-метод был прост и понятен, но оказался экспоненциальным - для разных эвристик выбора следующей вершины обхода исследователи сумели построить набор задач, для решения которых симплекс-методу было необходимо экспоненциально большое число итераций. И все же долгое время симплекс-метод был даже теоретически лучшим известным алгоритмом для решения задач линейного программирования. Однако в конце 1970-х годов здесь состоялся один из самых знаменитых прорывов в теории сложности: Л. Г. Хачиян (везло нашим соотечественникам на фундаментальные открытия в этой области) построил алгоритм, который решает задачу линейного программирования за полиномиальное число шагов - так называемый метод эллипсоидов Хачияна. Суть алгоритма в том, чтобы окружить данный многогранник эллипсоидом, а затем постепенно сжимать этот эллипсоид; оказывается, на каждом этапе объем эллипсоида уменьшается в константное число раз.
Казалось
бы, радость практиков должна быть
беспредельной: полиномиальный алгоритм
мог бы стать новым стандартом программирования.
Но увы. Алгоритм Хачияна не просто плох,
он безнадежен на практике. Существуют
задачи размером в 50 переменных, для которых
требуются более 24 тысяч итераций метода
Хачияна, причем итерации эти отнюдь не
тривиальны (хоть и полиномиальны, конечно).
Количество итераций симплекс-метода
в таких случаях исчисляется сотнями,
если не десятками, и пересчет каждой из
них гораздо проще. Метод эллипсоидов
несравним с симплекс-методом: последний
хоть и экспоненциален в худшем случае,
однако на практике справляется с задачами
ЛП многократно лучше. Все промышленные
(да и кустарные) реализации решения ЛП
основаны на симплекс-методе и его вариантах.