Завдання 3. Варіант-3
Знайти оптимальний план транспортної задачі.
Розв’язання
Розв’язуємо цю транспортну задачу. Визначимо, до якого типу належить дана задача.
Для цього обчислимо суму запасів: Σ ai = 30 + 70 + 50 = 150.
Сума потреб: Σ bj = 10 + 40 + 20 + 60 = 130.
Так як Σ ai ≠ Σ bj , то маємо задачу відкритого типу.
Для зведення її до закритої введемо фіктивного споживача:
a4ф= Σaj - Σbi = 150 – 130 = 20 з нульовою вартістю перевезень до нього.
Побудуємо опорний план методом подвійної переваги. Складемо транспортну таблицю (Табл. 1). У кожному рядку таблиці відбираємо по одній клітині з найменшим тарифом і позначаємо її *. Також позначаємо клітинки з найменшими тарифами в усіх стовпчиках. Завантажуємо клітинки з двома відмітками, вибираючи спочатку таку, яка має найменший тариф, потім наступну і т. д. Аналогічно завантажуємо клітинки з однією відміткою. Після цього залишки записуємо у клітинки без відміток.
Таблиця 1
| Обсяги постачальників, ai | Потреби споживачів, bj | |||||
| В1 | В2 | В3 | В4 | В5ф | ||
| 10 | 40 | 20 | 60 | 20 | ||
| A1 | 30 | 2 | 7 | 3 | 6 | 0 |
| **10 | | *20 | | | ||
| A2 | 70 | 9 | 4 | 5 | 7 | 0 |
| | **40 | | 10 | 20 | ||
| A3 | 50 | 5 | 7 | 6 | 2 | 0 |
| | | | **50 | | ||
Перевіримо цей план на оптимальність, використовуючи метод потенціалів. План буде оптимальним, якщо виконані умови:
Ui + Vj = Cij (Xij > 0) (1)
Ui + Vj ≤ Cij (Xij = 0) (2)
Нехай UA1=0, тоді з (1) :VB1=2; VB3=3 і т.д.
Перевіримо виконання умови (2) для вільних клітин – (Xij = 0).
Таблиця 2
| Обсяги постачальників, ai | Потреби споживачів, bj | Ui | ||||||
| В1 | В2 | В3 | В4 | В5ф | ||||
| 10 | 40 | 20 | 60 | 20 | | |||
| A1 | 30 | 2 | 4<7 | 3 | 7>6 | 0 | 0 | |
| 10 | | 20 | | | | |||
| A2 | 70 | 2<9 | 4 | 3<5 | 7 | 0 | 0 | |
| | 40 | | 10 | 20 | | |||
| A3 | 50 | -3<5 | -1<7 | -2<6 | 2 | -5<0 | -5 | |
| | | | 50 | | | |||
| Vj | | 2 | 4 | 3 | 7 | 0 | | |
Ця умова виконується для всіх таких клітин, крім клітини x14, тому план не є оптимальним. Організувати цикл перерозподілу перевезень, який покрашує план, не вдається.
Тому отриманий план можна вважати оптимальним.
Вартість перевезень за цим планом: Zmin = 410 ум. одиниць.