Таблиця 3.1
Вихідний допустимий план перевезення картоплі
ГОПГППІтого з вивезення, тоннБ 1 Б 2 Б 3 Б 4 Б 5 V1=1V2=5V3=2V4=2 V5=- 2 А 1 U1=06630 230 2560 А 2 U2=31320 8960 5880 А 3 U3=645735 1120 5420 4120 Разом з ввезення, тонн4555509020260
Обчислюємо транспортну роботу, яка дорівнюватиме
Р=45.7 + 35.11 + 30.2 + 30.2 + 20.8 + 20.5 +20 · 4 +60 · 5=1460 тонно-км.
Перевіряємо заповненість матриці за критерієм m + n - 1,
де m - число вантажовідправників (ГОП); - число вантажоодержувачів (ДПП).
Дана умова виконується.
Перевірка розробленого плану на оптимальність складається з двох етапів: на першому етапі обчислюються допоміжні індекси ui і vj, а на другому етапі досліджуються незайняті клітини на потенційність з метою визначення суми індексів - ui + vj? lij. Розраховуємо на матриці спеціальні індекси u і v і заносимо їх в рядок і стовпець матриці.
Для визначення індексів використовуються наступні правила:
допоміжний індекс u1 завжди дорівнює нулю,
для кожної зайнятої клітини матриці сума, відповідних їй індексів u і v дорівнює відстані в даній клітині, тобто
+ vj=lij, (4)
де lij - відстань у клітці.
Це дає можливість при відомому одному індексі визначити значення іншого.
=lij - vj;=lij - ui. (5)
Досліджуємо допустимий вихідний план на оптимальність, для чого порівнюємо у всіх незайнятих клітинах відстань lij з сумою відповідних їй індексів за критерієм
+ vj? lij,
тобто відстані повинні бути більше або дорівнюють сумі індексів.
Запишемо в матрицю (табл. 3.1) u1=0, тоді відповідно до формулами (5):
u1=0;=l13-u1=2-0=2;=l14-u1=2-0=2;=l35-u3=4-6=- 2;=l24-v4 =5-2=3;=l31-u3=7-6=1;=l22-u=8-3=5;=l32-V2=11-6=5.
Перевіряємо незайняті клітини на оптимальність, тобто чи виконується умова ui + vj? lij.
А1Б1 (0 +1)=1 < 6;
А2Б1 (3 +1)=4 < 13;
А1Б2 (0 +5)=5 < 6;
А1Б5 ((- 2) +0)=- 2 < 5;
А2Б5 (3 + (- 2))=1 < 8;
А2Б3 (3 +2)=5 < 9;
А3Б4 (6 +2)=8> 4.
У незайнятої клітини А3Б4 відстань менше суми індексів, тобто допустимий план не оптимальний. Виявлені клітини є резервом поліпшення плану, тому вони називаються потенційними. Отримані потенціали позначимо в кружечок (цифра перевищення індексу над відстанню). Будуємо ланцюжок для клітини, з найбільшим потенціалом з горизонтальних і вертикальних ліній (одна вершина в потенційній клітці, а інші вершини в зайнятих клітинах). Позначаю знаком (+) її непарні вершини, знаком (-) - парні. Найменша з парних завантажень визначає величину переміщуваної завантаження - 20т. Перемістивши це завантаження з клітки із знаком (-), в клітку зі знаком (+), отримаємо новий варіант плану з меншою транспортної роботою (табл. 3.2).
Таблиця 3.2
