Шпаргалка по "Программированию и компьютерам"

 

1.Симплекс 

Min f=-3X1-2X2 

{X1+2X2+X3=6

{2X1+X2+X4=8

{-X1+X2+X5=1

{X2+X6=2

{Xi>=0 

f+3X1+2X2=0

Алгоритм:

1.Составляем  первоначальную симплекс-таблицу

2.Находим  разрешающий столбец

Минимизация:

Выбираем  максимальный (+)

Максимизация:

Выбираем  максимальный (–) ПО МОДУЛЮ!!!

3.Находим  разрешающую строчку

Строчку выбираем ту для которой отношение  Св.член/Xij будет минимально, но БОЛЬШЕ 0!!!

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

5.Пересчитываем  остальные элементы

A B    то A’=(D*A-B*C)/D

C D    D-разрешающий

6.Проверяем  на оптимальность

Минимизация:

Выбираем  максимальный (+)

Если  есть (+) оценки решение можно улучшить,

но если оценка (+), а все коэффициенты в  этом столбце

(–)  то решения нет

Конец: все оценки (–) или 0 

Максимизация:

Выбираем  максимальный (–) ПО МОДУЛЮ!!!

Если  есть (-)оценки решение можно улучшить, но если

оценка (-), а все коэффициенты в этом столбце (-) то решения нет

Конец: все оценки (+) или 0  
 
 
 
 
 
 
 
 
 

2.Двухэтапный 

Max f=8X1+X2-X3 

{-X1+X2+X3+2X4+X5=4

{2X1+X3-3X4+5X5=3

{3X1-X3+6X4+X5=6

{Xi>=0 

//добавляем искусственные переменные

{-X1+X2+X3+2X4+X5+Y1=4

{2X1+X3-3X4+5X5+Y2=3

{3X1-X3+6X4+X5+Y3=6

{Xi>=0, Yi>=0 

T=Y1+Y2+Y3->min(всегда минимизация!)

//складываем строчки и переносим

T+4X1+X2+X3+5X4+7X5=13

f-8X1-X2+X3 

 

//находим ИОР для Т (все должно стать = 0, иначе ИОР нет). Сначала решаем задачу минимизации и смотрим только по Т, когда все оценки в строке Т=0 решаем исходную задачу для F. 

Альтернативный  оптимум:

Если  в симплекс-таблице соответствующей  оптимальному решению найдется свободная переменная, оценка которой=0, то данная задача имеет множество решений. Для их получения достаточно выполнить одну итерацию по включению этой переменной в базис и получить новое решение. 

Вырожденное решение: 
Если при включении свободной переменной в базис первыми в 0 обращаются две или более базисных переменных, то в качестве исключаемой выбирается любая из них, остальные базисные переменные при этом станут равными 0. 

3. Найти ИОР 

Алгоритм:

1.В качестве  разрешающего элемента выбираем  любой не равный 0

2.Если  после выполнения шага 1 оказалось  что все свободные члены ограничений (+), то ИОР получено, иначе переходим к шагу 3

3.Если  среди свободных членов ограничений  имеются 

(-), то  выбираем из них наибольший  по модулю, предположим это Bs 
 
 

4.Вычтем S-ое уравнение из всех уравнений с (-) свободными членами. В результате эти уравнения останутся разрешенными относительно тех же базисных переменных, но свободные члены станут (+). S-ое уравнение уже не будет разрешено относительно базисной переменной.

5.Умножим S-ое уравнение на -1

6.Выберем  в S-ой строке любой (+) коэффициент и объявим соответствующий столбец разрешающим. Если

(+) коэффициент  в S-ой строке не найдется, то это означает что ИОР нет 

7.Выберем  разрешающую строчку как в  симплекс-методе и выполним одну  итерацию

1 случай:

В качестве разреш. строчки выбрана S строка т.е. Р= S

То в  результате выполнения одной итерации получим ИОР.

2 случай:

В качестве разреш. строчки выбрана Q строчка и Q не равно S. Если Bq не равно 0, то в результате выполнения итерации S-ая строчка останется не разрешенной относительно базисной переменной, но свободный член B’s уменьшится B’s<Bs. При повторном выполнении итерации мы можем перейти к 1 случаю.

3 случай:

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

{5X1-X2+2X3-X5-X6=6

{X1+2X2+X5=5

{X1+X2+X3-X4=4

{Xi>=0

//разрешим систему  ограничений относительно базисных переменных

{-5X1+X2-2X3+X5-6=X6

{X1+2X2+X5=5

{-X1-X2-X3-4=X4