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

Автор работы: Пользователь скрыл имя, 11 Мая 2012 в 10:02, контрольная работа

Краткое описание

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

В вычислительной схеме симплекс-метода реализуется упорядоченный процесс, при котором, начиная с некоторой исходной допустимой угловой точки ( обычно начало координат ), осуществляются последовательные переходы от одной допустимой экстремальной точки к другой до тех пор, пока не будет найдена точка, соответствующая оптимальному решению.

Содержание

Введение. 3

1. Общая характеристика симплекс метода. 4

2. Решение различных задач симплекс методом. 11

3. Табличный симплекс метод. 21

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

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

Вложенные файлы: 1 файл

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

— 245.50 Кб (Скачать файл)

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

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

     

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

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

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

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

     

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

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

Информация о работе Симплекс метод