Метод отсечения производственно-транспортной задачи

Страницы работы

Содержание работы

Метод отсечения производственно-транспортной задачи.

 cirzir + {vijbjk - uijAij}= По +  Tj0    →min    

в оптимальном плане =  По 

где Tj0 – значение функционала  в транспортной задаче при  zi r оптимальном.

 (cir  - airui)zi r £ [По + Tj0 ] - vijbij -  ε называется отсечением для многопродуктовой модели

Однопродуктовая модель

Формальная постановка модели

airzir - yi ³ 0   "i             zir £ 1                  "i

yik ³ bk                "k           (cirzir + tikyik ) → min

Разобьем эту задачу на две: производственную задачу и транспортную.

Гипотеза:  если эти задачи не имеют решения, то и исходная не имеет решения тоже

Подпись: 2.  ТЗ (транспортная задача)
                                            двойственные оценки
 yik £ Aio                   "i
                      ui
 yik ³ bk                                "i
                     vk  
Q(y) =   tikyik  → min


Подпись: 1.  ПЗ (производственная задача)

  airzir  ³  bk
  zir £ 1    "i
 F(z) =    cirzir → min

Решая задачу, получаем оптимальное решение ziorairzior = Aio

Решая задачу, получаем оптимальное решение yiko.

План {zior, yiok} является не оптимальным, но допустимым в исходной задаче.


Пусть zo = (zior),  yo = (yiok)                 F(zo) = По      Q(yo) = То

Sо – суммарные затраты:  Sо = По + То =  cirzir+tikyik 

Составим соотношение:

 cirzir + {bkvk - Aiui}= Sо     ????

Заменим Aiui  на airzirui

Тогда  cirzir -airzirui + bkvk £ Sо (т.е. мы потребуем чтобы П1+Т1<S0)

То (cir - airui)zir £ Sо- bkvk – ε    (**)  Это есть отсечение, которое отсекает планы, которые с учетом транспортной оценки дает не оптимальный план (транспортные затраты не минимальные).          ПЗ + неравенство (**) = новая задача (решаем на второй итерации)

Похожие материалы

Информация о работе