Критерій оптимальності плану перевезень
Якщо серед оцінок оптимальності всі від’ємні, то опорний план є оптимальним і єдиним.
Якщо серед оцінок оптимальності є тільки від’ємні і нульові, то опорний план є оптимальним, але не єдиним.
Якщо серед оцінок оптимальності є хоч би одна додатна, то опорний план не є оптимальним.
Перехід від одного опорного плану до іншого проводять заповненням клітини, для якої порушено умову оптимальності. Таким чином, для побудови циклу перерозподілу вантажу потрібно вибирати клітину з найбільшою додатною оцінкою оптимальності.
Зауваження. Якщо є декілька найбільших додатних оцінок оптимальності, то вибирають клітину з меншим тарифом.
Для цієї вибраної клітини будуємо цикл перерозподілу поставок. Цикл зображують ламаною лінією, всі кути повороту якої прямі, одна вершина його знаходиться у вибраній клітині, а інші – в заповнених. Для перерозподілу поставок у вибраній клітині ставимо знак “+”, потім знаки чергуємо. Серед клітин із знаком “– ” вибираємо найменшу кількість вантажу і в клітини із знаком “+” додаватимемо це число, а в клітинах із знаком “– ” це число відніматимемо. В результаті такого перерозподілу поставок отримуємо новий опорний план транспортної задачі.
Зауваження. Цикл перерозподілу поставок може мати різний вигляд, наприклад, як на рисунку 4.1.
Рисунок 4.1 – Цикли перерозподілу поставок
Зауваження. Вантажі, які не брали участь в перерозподілі, переписуються без змін.
Розв’язання транспортної задачі розглянемо на прикладі.
Приклад 4.2.1. Знайти оптимальний план перевезень.
-
B
A
B1
B2
B3
10
20
20
А1
20
А2
40
А3
35
Розв’язання.
Спочатку необхідно перевірити наявність балансу між попитом і пропозицією: 20 + 40 + 35 = 95; 10 + 20 + 30 = 50. Балансу немає.
Для того, щоб дане транспортну задачу закрити, необхідно ввести фіктивного споживача В4 з потребою 45 одиниць вантажу (95 – 50 = 45) і нульовими тарифами.
Для побудови початкового опорного плану транспортної задачі скористаємося методом північно-західного кута.
Таблиця 4.1.1
Перша таблиця транспортної задачі
-
B
A
B1
B2
B3
B4
10
20
20
45
А1
20
10
10
А2
40
10
20
10
А3
35
35
У нашому випадку число заповнених кліток повинне бути
т + п – 1 = 3 + 4 – 1 = 6.
Все 6 кліток є заповненими, тобто опорний план транспортної задачі є невиродженим.
Опорний план, що відповідає таблиці 4.1.1, має вигляд
.
У таблиці 4.1.1 сума витрат на перевезення складає
z1 = 10 · 6 + 10 · 3 + 10 · 2 + 20 · 6 + 10 · 0 + 35 · 0 = 230.
Знайдемо оцінки оптимальності для кожної клітини таблиці 4.1.1 і запишемо їх в таблицю 4.1.2.
Таким чином, таблиця 4.1.1 прийме вигляд:
Таблиця 4.1.2
Перша таблиця транспортної задачі
-
B
A
B1
B2
B3
B4
ui
10
20
20
45
А1
20
– 10
+ 10
(3)
(-)
0
А2
40
(2)
– 10
20
+ 10
-1
А3
35
(5) +
(-)
(-)
– 35
1
vj
6
3
5
–1
Опорний план Х1, який відповідає таблиці 4.1.2, не є оптимальним.
Для побудови циклу перерозподілу вантажу потрібно вибирати клітину з найбільшою додатною оцінкою. У нашому випадку це (А3, В1). Таким чином цикл починається в клітині (А3, В1), потім він продовжується до клітини (А3, В4), в якій повертає в клітину (А2, В4), потім – в клітину (А1, В2), потім – в клітину (А1, В1), і повертається в початкову клітину (А3, В1).
У клітині (А3, В1) ставимо знак “+”, далі чергуємо знаки: у клітині (А3, В4) – знак “–”, в клітині (А2, В4) – знак “+”, в клітині (А2, В2) – знак “–”, в клітині (А1, В2) – знак “+”, в клітині (А1, В1) – знак “–”.
У нашому випадку найменша кількість вантажу в клітинах із знаком “–” це 10, яке клітини із знаком “+” додаватимемо, а від кліток із знаком “–” відніматимемо.
Кількість вантажів, які не брали участь в циклі, переписуємо без змін. У нашому випадку це клітина (А2, В3).
Таким чином, таблиця 4.1.3 має вигляд:
Таблиця 4.1.3
Друга таблиця транспортної задачі
-
B
A
B1
B2
B3
B4
ui
10
20
20
45
А1
20
(-)
- 20
(5) +
(1)
0
А2
40
(-)
+
0
–
20
20
-1
А3
35
10
(2)
(-)
25
-1
vj
3
3
7
1
У таблиці 4.1.3 число заповнених клітин дорівнює 5, що менше ніж т + п – 1 = 6, тобто потрібно заповнити порожню клітину нулем, тоді їх буде 6. У клітину (А2, В2) з найменшим тарифом 2 поставимо нуль і вважатимемо її заповненою.
Далі розписуємо потенціали і знаходимо оцінки оптимальності, відображаючи ці дії в таблиці 4.1.3.
Опорний план, що відповідає таблиці 4.1.3, має вигляд
.
Опорний план Х2 не є оптимальним, сума витрат на перевезення складає при цьому
z2 = 20 · 3 + 0 · 2 + 20 · 6 + 20 · 0 + 10 · 2 + 25 · 0 = 200.
Для побудови циклу перерозподілу вантажу потрібно вибирати клітину з найбільшою позитивною оцінкою (А1, В3).
У нашому випадку цикл починається в клітині (А1, В3), потім він йде до клітини (А1, В2), в якій повертає в клітину (А2, В2), потім – в клітину (А2, В3), і повертається в початкову клітину (А1, В3).
У клітині (А1, В3) ставимо знак “+”, далі чергуємо знаки: у клітині (А1, В2) – знак “–”, в клітині (А2, В2) – знак “+”, в клітині (А2, В3) – знак “–”.
У нашому випадку найменша кількість вантажу в клітинах із знаком “–” це 20. Тоді в клітинах із знаком “+” це кількість вантажу додаватимемо до того, що вже є, а в клітинах із знаком “– ” відніматимемо.
Вантажі, які не брали участь в циклі перерозподілу вантажу, переписують без змін.
У нашому випадку це вантажі, що знаходяться в клітинах (А1, В3), (А2, В4), (А3, В4).
Таким чином, таблиця 4.1.4 має вигляд:
Таблиця 4.1.4
Третя таблиця транспортної задачі
-
B
A
B1
B2
B3
B4
ui
10
20
20
45
А1
20
(-)
(-)
20
0
0
А2
40
(-)
20
(-)
20
0
А3
35
10
(-)
(-)
25
0
vj
2
2
2
0
У таблиці 4.1.4 число заповнених клітин дорівнює 5, що менше 6, тобто потрібно заповнити незавантажену клітину нулем, тоді їх буде 6. У клітину (А1, В4) з найменшим тарифом 0 поставимо нуль і вважатимемо її заповненою.
Далі розписуємо потенціали і знаходимо оцінки оптимальності, відображаючи ці дії в таблиці 4.1.4. Опорний план, що відповідає таблиці 4.1.4, має вигляд
.
Опорний план Х3 є оптимальним, сума витрат на перевезення в цьому випадку дорівнює
z3 = 20 · 2 + 0 · 0 + 20 · 2 + 20 · 0 + 10 · 2 + 25 · 0 = 60.