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