Задача и её решение

Задача

Хабаровское аэрогеодезическое предприятие  выиграло тендеры по 5 госбюджетным объектам на 200_г. Для составления  текущего плана предприятия требуется  распределить объекты по 3 комплексным  экспедициям предприятия. Распределение  объектов произвести под условием минимизации  издержек на внешний и внутренний транспорт.

Исходные  данные:

Решение

                                                                                                           ∑ b_j =3072 

1. Суммарная возможность экспедиций превышает  на 322 единицу УПН потребность ( ∑b_j=3072), то задача открыта. Для закрытия задачи вводим дополнительного потребителя D с потребностью 322 УПН.  

Составляем  опорный план используя исходные данные и метод минимального элемента. Осуществляем контроль сумм по столбцам и строкам. 
 
 
 
 

Опорный план.

2. Отыскиваем целевую функцию без дополнительной неизвестной

F=304*570*0,03+324*30*0,05+264*450*0,05+444*598*0,02+264*202*0,05+884*400*0,07+154*500*0,05+0*322=48202руб.

Исследуем F на оптимальность, для этого составляем уравнение потенциалов для базовых клеток , примем V₂=0

V₂+U₁=324   U₁=324-0=324                         V₃+U₃=264       V₃=264-444=-180

V₂ +U₃=444   U₃=444-0=444                       V₁+U₁=304      V₁=304-324=-20

V₂+U₄=0       U₄=884-0=884                              

V₃+U₅=154    U₅=154-(-180)=334

V₂+U₆=0        U₆=0-0=0

V₁+U₂=264    U₂=264-(-20)=284

3. Составляем уравнение невязок для небазовых клеток

▲₁₃=с₁₃-(U₁+V₃)=844-(324+(-180))=700

▲₂₂=с₂₂-(U₂+V₂)=364-(284+0)=80

▲₂₃=с₂₃-(U₂+V₃)=944-(284+(-180)=840

▲₃₁=с₃₁-(U₃+V₁)=594-(444+(-20))=170

▲₄₁=с₄₁-(U₄+V₁)=953-(884+(-20))=89

▲₄₃=с₄₃-(U₄+V₃)=444-(884+(-180)0=-260

▲₅₁=с₅₁-(U₅+V₁)=844-(334+(-20))=530

▲₅₂=с₅₂-(U₅+V₂)=664-(334+0)=330

▲₆₁=с₆₁-(U₆+V₁)=0-(0+(-20))=20

▲₆₃=с₆₃-(U₆+V₃)=0-(0+(-180))=180

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

4. Выбираем  отрицательную невязку (-260) и образуем контур клетки, которому принадлежит данная невязка и производим перераспределение:

             598+202                              202-202

            400-202                                   +202 

5. Произведем  оценку полученного решения.

Примем  V₂=0

V₂+U₁=324   U₁=324-0=324                         V₃+U₄=444      V₃=44-884=-440

V₂ +U₃=444   U₃=444-0=444                       V₁+U₁=304      V₁=304-324=-20

V₂+U₄=0       U₄=884-0=884                              

V₃+U₅=154    U₅=154-(-440)=594

V₂+U₆=0        U₆=0-0=0

V₁+U₂=264    U₂=264-(-20)=284

Составляем  уравнение невязок для небазовых  клеток

▲₁₃=с₁₃-(U₁+V₃)=844-(324+(-440))=960

▲₂₂=с₂₂-(U₂+V₂)=364-(284+0)=80

▲₂₃=с₂₃-(U₂+V₃)=944-(284+(-440)=1100

▲₃₁=с₃₁-(U₃+V₁)=594-(444+(-20))=170

▲₃₃=с₃₃-(U₃+V₃)=264-(444+(-440))=260

▲₄₁=с₄₁-(U₄+V₁)=953-(884+(-20))=89

▲₅₁=с₅₁-(U₅+V₁)=844-(594+(-20))=270

▲₅₂=с₅₂-(U₅+V₂)=664-(594+0)=70

▲₆₁=с₆₁-(U₆+V₁)=0-(0+(-20))=20

▲₆₃=с₆₃-(U₆+V₃)=0-(0+(-440))=440 

Все оценки свободных ячеек положительные, следовательно, найдено оптимальное  решение. 

S_min=304*570*0,03+324*30*0,05+264*450*0,05+444*800*0,02+884*198*0,07+444*202*0,06+154*500*0,05+0*322=40211 руб

Общие затраты для оптимального решения  составляют 40211руб.

В экспедиции №2 имеются резервы производственных ресурсов, достаточных для выполнения 322 тыс.единиц условно-натуральной продукции. Данные резервы могут быть использованы для выполнения договорных работ или утилизации.