Методичні вказівки до виконання курсового проекту 5 страница

 

Таблиця49

Четверта СТ

 
cбі хбі bбі х1 х2 х3 х4 х5 х6 х7 х8 х9 х10 х11 х12 х13 х14 х15 х16 х17 х18
х13
х5 -1 -1 -1
х15 -1 -1 -1
х16 -1 -1 -1
х10
х7
0 = 12200 1= 2= -4 3= 4=51 5=0 6= -112 7=0 8= -61 9=103 10=0 11= 12=54 13=0 14=-109 15=0 16=0 17= -109 18= -2

У цій таблиці також присутні позитивні елементи в індексному рядку, тому переходимо до нового СТ із новим ключовим елементом –a3,12(див. табл. 51).

Таблиця50

П’ята СТ

 
cбі хбі bбі х1 х2 х3 х4 х5 х6 х7 х8 х9 х10 х11 х12 х13 х14 х15 х16 х17 х18
х13 -1 -1 -1 -1
х5 -1 -1 -1
х15 -1 -1 -1
х1 -1 -1 -1
х10
х7
0 = 4640 1= 2= -4 3= 4=51 5=0 6= -4 7=0 8= 9= -5 10=0 11= -4 12=54 13=0 14= -1 15=0 16= -108 17= -109 18= -110

У цій таблиці також присутні позитивні елементи в індексному рядку, тому переходимо до нового СТ із новим ключовим елементом –a1,4(див. табл. 52).

Отримана симплекс-таблиця містить усі , завдяки чому можна стверджувати, що отримане рішення є оптимальним, тобто: х1 = 70; х2 = 0; х3 = 0; х4 = 30; х5 = 10; х6 = 0; х7 = 110; х8 = 0; х9 = 0; х10 = 100; х11 = 0; х12 = 40; х13 = 0; х14 = 0; …; х18 = 0, що забезпечує Lopt = 950 у.г.о. (У додатку 5 наведений розрахунок цього ж самого прикладу у матричному процесорі Excel).

Представимо одержаний оптимальний план перевезень вантажу для нашого прикладу у вигляді ТТ (табл. 53).

Таблиця51

Шоста СТ

 
cбі хбі bбі х1 х2 х3 х4 х5 х6 х7 х8 х9 х10 х11 х12 х13 х14 х15 х16 х17 х18
х13 -1 -1 -1 -1
х5 -1 -1 -1
х12 -1 -1 -1
х1 -1 -1 -1
х10
х7
0 = 2480 1= 2= 3= 4=51 5=0 6= 7=0 8= 9= -59 10=0 11= -58 12=0 13=0 14= -1 15=-54 16= -108 17= -55 18= -110

Таблиця52

Сьома СТ

 
cбі хбі bбі х1 х2 х3 х4 х5 х6 х7 х8 х9 х10 х11 х12 х13 х14 х15 х16 х17 х18
х4 -1 -1 -1 -1
х5 -1 -1 -1
х12 -1 -1 -1
х1 -1 -1 -1
х10
х7
0 = 950 1= 2= -1 3= 4= 5=0 6= -1 7=0 8= -4 9= -8 10=0 11= -7 12=0 13=-51 14= -52 15=-54 16= -57 17= -55 18= -59

Таблиця53

Оптимальний план перевезень вантажу у вигляді ТТ

  B1 B2 B3 B4 Запаси ai
A1 c1 = 4 x1=70   c2 = 7 x2=0   c3 = 2 x3=0   c4 = 5 x4=30  
A2 c5 = 3 x5=10   c6 = 6 x6=0   c7 = 1 x7=110   c8 = 8 x8=0  
A3 c9 = 9 x9=0   c10 = 3 x10=100 c11 = 6 x11=0   c12 = 2 x12=40  
Заявки bj

 

 

4.2. Метод потенціалів оптимізації транспортних перевезень

Більш простим методом оптимізації плану перевезень є метод потенціалів, суть якого полягає у наступному.

1. Приймаємо будь-яке значення початкового потенціалу для i-го ряду транспортної таблиці; шукаємо заповнену клітку (ij), для якої і визначаємо відповідний потенціал по наступній формулі: Робимо аналогічні розрахунки для решти рядів і колонок таблиці, спираючись на вже розраховані транспортні потенціали.

2. Після визначення всіх i ( ; ) перевіряємо нерівність для всіх (ij) незайнятих клітинок таблиці (тобто для ). Якщо ця нерівність має місце для усіх без виключення незайнятих кліток, план перевезень є оптимальним.

3. Якщо у будь якій незайнятій клітинці , то складений план перевезень не є оптимальним і підлягає корегуванню. Корегування полягає в заповненні незайнятих клітинок, що мають , згідно правил перерозподілу вантажу по клітинках, що вже застосовувалась раніше, при розгляданні розподільчого методу оптимізації плану перевезень. У тому випадку, коли таких незайнятих клітинок виявиться декілька, то перевага віддається тієї з них, у якої добуток перевищення над на величину вантажу, що перерозподіляється по контуру, у цю клітинку виявиться більшим.

При умові для незайнятої клітинки ( ) означає, що перерозподіл вантажу в цю клітинку можливий, але це не поліпшує, ні погіршує план перевезень. Це означає, що є ще один план, еквівалентний по вартості перевезень. Тому в подальшому домовимось вважати, що клітинка залишається незайнятою при .

Наприклад, є певний опорний план перевезень (табл. 54). Відмітимо, що для отриманого плану маємо L1 = 30×7 + 70×2 + 80×3 + 40×1 + 70×3 + 70×2 = 980 у.г.о.

Розрахуємо потенціали і , використовуючи саме зайняті клітинки, і занесемо їх в додаткові стовпчик і рядок.

Приймаємо , тоді ; . Використовуючи вже отримані потенціали, визначаємо решту потенціалів:

; ;

; .

Перевіряємо опорний план на оптимальність, використовуючи отримані потенціали. Для цього перевіряємо умову оптимальності для всіх незайнятих клітинок плану, тобто :

; ; ;

; ; .

Таблиця54

Вихідна ТТ

  B1 B2 B3 B4 ui Запасиai
A1   30 - +  
A2         -1
A3   70 +     - 70   -4
vj    
Заявки bj  

Опорний план не є оптимальним, тому що для клітинки . Це означає, що ця клітинка, як кажуть, є потенційною і має бути завантажена.

Для цього шукаємо контур, що містить у решті кутів зайняті клітинки. Це контур: (див. табл. 54). Оскільки ми завантажуємо , присвоюємо їй знак “+”, потім, пересуваючись по контуру, послідовно міняємо знаки. Мінімальне абсолютне значення від'ємного обсягу знаходиться в клітинці і дорівнює xп = 30 в.о. Пересуваємо цей обсяг по контуру з урахуванням знаків і отримуємо новий план перевезень (див. табл. 55), при цьому вартість його реалізації буде дорівнювати:

L2 = 70×2 + 30×5 + 80×3 + 40×1 + 100×3 + 40×2 = 950 у.г.о.

Порахуємо для нового плану перевезень нові значення потенціалів і , для цього знову приймаємо , тоді ; . Використовуючи вже отримані потенціали, визначаємо решту потенціалів: ; ;

.

Перевіряємо побудований план на оптимальність, використовуючи отримані потенціали, а саме:

; ; ;

; ; .

Таблиця55

ТТ після розподілу вантажу у клітинку А1В4

  B1 B2 B3 B4 ui Запасиai
A1    
A2         -1
A3         -3
vj    
Заявки bj  

План оптимальний, тому що для всіх незайнятих клітинок виконується умова .(У додатку 6 наведений розрахунок цього ж самого прикладу у матричному процесорі Excel).