Симплекс метод

   Если  в качестве начального базиса выбирают базис из свободных переменных, для  которых 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опт.

 

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

    
   

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

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

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

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

    
   

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

   1. Лищенко «Линейное  и нелинейное программирование», М. 2003
   2. А.Н. Карасев, Н.Ш. Кремер, Т.Н. Савельева «Математические методы в экономике», М. 2000
   3. Мину М. Математическое программирование. Теория и алгоритмы. М. 2004