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

Автор: Пользователь скрыл имя, 20 Октября 2011 в 14:34, контрольная работа

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

Распределение объектов произвести под условием минимизации издержек на внешний и внутренний транспорт.

Скачать в ZIP (25.13 Кб) Сколько стоит заказать работу?
Файлы: 1 файл

плниров задача мой 1 вариант.docx

— 28.38 Кб (Скачать)

Задача

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

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

экспедиции Наименование  объектов и расстояние до экспедиций и стоимость транспортных издержек на едеиницу км2 /км(j)
(i)M,k Mi ki 1.Угольный 2.Иманский 3.Боровой 4.Холмский 5.Лазаревский
Ц/ ij Sij Ц/ ij Sij Ц/ ij Sij Ц/ ij Sij Ц/ ij Sij
1 1200 0,85 0,03 304 0,05 264 0,04 594 0,06 953 0,04 844
2 1500 0,90 0,05 324 0,03 264 0,02 444 0,07 884 0,05 664
3 900 0,78 0,02 844 0,02 964 0,05 264 0,06 444 0,05 154
Потребность (bj) 600 450 800 400 500
 

Решение

Объекты (потребители),

( j)

 Подразделения (i) (bj)
В1 В2 В3
1 304 324 844 600
2 264 364 944 450
3 594 444 264 800
4 953 884 444 400
5 844 664 154 500
Mikj (ai) 1020 1350 702 ∑a=2750

                                                                                                           ∑ bj =3072 

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

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

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

                               

Объекты (потребители),

( j)

 Подразделения (i) (bj)
В1 В2 В3
1 304                570 324             30 844 600
2 264                450 364 944 450
3 594 444            598 264            202 800
4 953 884            400 444 400
5 844 664 154             500 500
D 0                 0               322 0 322
Mikj (ai) 1020 1350 702  

 

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

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 на оптимальность, для этого составляем уравнение потенциалов для базовых клеток , примем V2=0

V2+U1=324   U1=324-0=324                         V3+U3=264       V3=264-444=-180

V2 +U3=444   U3=444-0=444                       V1+U1=304      V1=304-324=-20

V2+U4=0       U4=884-0=884                              

V3+U5=154    U5=154-(-180)=334

V2+U6=0        U6=0-0=0

V1+U2=264    U2=264-(-20)=284

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

▲13=с13-(U1+V3)=844-(324+(-180))=700

▲22=с22-(U2+V2)=364-(284+0)=80

▲23=с23-(U2+V3)=944-(284+(-180)=840

▲31=с31-(U3+V1)=594-(444+(-20))=170

▲41=с41-(U4+V1)=953-(884+(-20))=89

▲43=с43-(U4+V3)=444-(884+(-180)0=-260

▲51=с51-(U5+V1)=844-(334+(-20))=530

▲52=с52-(U5+V2)=664-(334+0)=330

▲61=с61-(U6+V1)=0-(0+(-20))=20

▲63=с63-(U6+V3)=0-(0+(-180))=180

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

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

             598+202                              202-202

      3,2       3,3
         
      4,2     4,3

            400-202                                   +202 

Объекты (потребители),

( j)

 Подразделения (i) (bj)
В1 В2 В3
1 304                570 324             30 844 600
2 264                450 364 944 450
3 594 444            800 264            800
4 953 884            198 444             202 400
5 844 664 154             500 500
D 0                 0                322 0 322
Mikj (ai) 1020 1350 702  
 
  1. Произведем  оценку полученного решения.

Примем  V2=0

V2+U1=324   U1=324-0=324                         V3+U4=444      V3=44-884=-440

V2 +U3=444   U3=444-0=444                       V1+U1=304      V1=304-324=-20

V2+U4=0       U4=884-0=884                              

V3+U5=154    U5=154-(-440)=594

V2+U6=0        U6=0-0=0

V1+U2=264    U2=264-(-20)=284

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

▲13=с13-(U1+V3)=844-(324+(-440))=960

▲22=с22-(U2+V2)=364-(284+0)=80

▲23=с23-(U2+V3)=944-(284+(-440)=1100

▲31=с31-(U3+V1)=594-(444+(-20))=170

▲33=с33-(U3+V3)=264-(444+(-440))=260

▲41=с41-(U4+V1)=953-(884+(-20))=89

▲51=с51-(U5+V1)=844-(594+(-20))=270

▲52=с52-(U5+V2)=664-(594+0)=70

▲61=с61-(U6+V1)=0-(0+(-20))=20

▲63=с63-(U6+V3)=0-(0+(-440))=440 

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

Объекты (потребители),

( j)

 Подразделения (i) контроль
В1 В2 В3
1 570 30 0 600
2 450 0 0 450
3 0 800 0 800
4 0 198 202 400
5 0 0 500 500
D 0 322 0 (3072)
контроль 1020 1350 702 ∑a=2750

Информация о работе Задача и её решение