Методичні вказівки до виконання курсового проекту 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).