Автор: Пользователь скрыл имя, 03 Января 2012 в 13:37, задача
Задание 2 Решение открытой модели транспортной задачи в матричной форме ∆-методом.
Проверка на оптимальность.
| ОПТИМАЛЬНЫЙ ПЛАН | |||||||||
| Из | На | аi | |||||||
| В1 | В2 | В3 | В4 | В5 | В6 | В7 | |||
| V1=--34 | V2=73 | V3=69 | V4=59 | V5=59 | V6=73 | V7=19 | |||
| А1 | U1=--22 | 65 | 65 | ||||||
| А2 | U2=72 | 36 | 36 | ||||||
| А3 | U3=16 | 45 | 45 | ||||||
| А4 | U4=--6 | 60 | 60 | ||||||
| А5 | U5=118 | 0 | 130 | 130 | |||||
| А6 | U6=100 | 190 | 51 | 8 | 249 | ||||
| А7 | U7=40 | 115 | 115 | ||||||
| А8 | U8=118 | 116 | 116 | ||||||
| А9 | U9=76 | 84 | 19 | 103 | |||||
| А10 | U10=40 | 28 | 53 | 81 | |||||
| A11 | U11=--73 | 42 | 58 | 100 | |||||
| bj | 190 | 147 | 135 | 93 | 135 | 147 | 253 | ai=1000 bj=1100 | |
Данный план не является опорным. Поэтому ввожу фиктивную поставку С54=0. Полученный план распределения необходимо проверить на оптимальность. Для этого используется метод потенциалов. Присваиваю шестой строке потенциал U6=100. Тогда по условию:
V1=C61-U6=66-100=-34
V7=C67-U6=119-100=19
V4=C54-U5=177-118=59
U7=C77-V7=59-19=40
U9=C93-V3=145-69=76
U8=C85-V5=177-59=118
U11=C11 6-V6=0-73=-73
U4=C42-V2=67-73=-6
U2=C26-V6=145-73=72
Условие оптимальности:
U1+V1=-22-34=-56≤69(И) U5+V6=118+73=191≤ 295(И)
U1+V2=-22+73=51≤ 415(И) U6+V2=100+73=173≤ 178(И)
U1+V3=-22+69=47≤ 165(И) U6+V4=100+59=159≤ 295(И)
U1+V5=-22+59=37≤ 226(И) U6+V5=100+59=159≤ 188(И)
U1+V6=-22+73=51≤ 113(И) U6+V6=100+73=173≤ 314(И)
U1+V7=-22+19=3≤ 271(И) U7+V1=40-34=6≤ 410(И)
U2+V1=72-34=38≤113 (И) U7+V2=40+73=113≤ 307(И)
U2+V2=72+73=145≤ 156(И) U7+V3=40+69=109≤ 148(И)
U2+V3=72+69=141≤ 198(И) U7+V4=40+59=99≤ 166(И)
U2+V4=72+59=131≤ 385(И) U7+V5=40+59=99≤ 253(И)
U2+V5=72+59=131≤ 185(И) U7+V6=40+73=113≤ 365(И)
U2+V7=72+19=91≤ 218(И) U8+V1=118-34=84≤ 355(И)
U3+V1=16-34=18≤ 127(И) U8+V2=118+73=191≤367 (И)
U3+V3=16+69=85≤ 315(И) U8+V3=118+69=187≤ 197(И)
U3+V4=16+59=75≤ 225(И) U8+V4=118+59=177≤ 205(И)
U3+V5=16+59=75≤ 145(И) U8+V6=118+73=191≤ 408(И)
U3+V6=16+73=89≤ 168(И) U8+V7=118+19=137≤ 255(И)
U3+V7=16+19=35≤ 194(И) U9+V1=76-34=42≤ 302(И)
U4+V1=-6-34=-40≤ 256(И) U9+V2=76+73=149≤ 322(И)
U4+V3=-6+69=63≤ 308(И) U9+V4=76+59=135≤ 166(И)
U4+V4=-6+59=53≤ 318(И) U9+V6=76+73=149≤ 325(И)
U4+V5=-6+59=53≤ 219(И) U9+V7=76+19=95≤ 350(И)
U4+V6=-6+73=67≤ 229(И) U10+V1=40-34=6≤ 278(И)
U4+V7=-6+19=13≤167 (И) U10+V2=40+73=113≤ 125(И)
U5+V1=118-34=84≤ 111(И) U10+V3=40+69=109≤ 111(И)
U5+V2=118+73=191≤ 253(И) U10+V5=40+59=99≤ 115(И)
U5+V3=118+69=187≤ 275(И) U10+V7=40+19=59≤ 400(И)
U5+V5=118+59=177≤ 279(И) U11+V1=-73-34=-107≤ 0(И)
U11+V3=-73+69=-4≤ 0(И)
U11+V4=-73+59=-14≤ 0(И)
U11+V5=-73+59=-14≤ 0(И)
U11+V7=-73+19=-54≤ 0(И)
План является оптимальным. Тогда рассчитаю суммарный пробег порожних вагонов:
R=65*37+36*145+45*89+60*67+