Головна |
Ознакою наявності альтернативного оптимуму в транспортній задачі є рівність нулю хоча б однієї з оцінок вільних змінних в оптимальному рішенні (Xопт1).Зробивши перерозподіл вантажів щодо клітини, що має ?ij = 0, отримаємо нове оптимальне рішення (Хопт2), При цьому значення цільової функції (транспортних витрат) не зміниться. Якщо одна оцінка вільних змінних дорівнює нулю, то оптимальне рішення знаходиться в вигляді
де 0 ? t ? 1.
Розглянемо конкретне завдання, що має альтернативний оптимум.
Приклад 1. На трьох складах є борошно в кількості 60, 130 і 90 т, яка повинна бути протягом місяця доставлена ??чотирьом хлібозаводам в кількості: 30, 80, 60, 110 т відповідно. Скласти оптимальний план перевезень, що має мінімальні транспортні витрати, якщо вартість доставки 1 т борошна на хлібозаводи задана матрицею
Рішення. Складемо розподільну таблицю у вигляді табл. 23.6.
За методом мінімального тарифу знайдемо вихідне рішення. Визначимо потенціали рядків і стовпців. Знайдемо оцінки вільних клітин:
Так як ?12 = 4> 0, то перерозподілили вантажі щодо клітини (1,2):
Занесемо отримане перерозподіл вантажів в розподільну таблицю і обчислимо потенціали зайнятих і оцінки вільних клітин (табл. 23.7).
отримаємо
Так як ?33 = 0, то завдання має альтернативний оптимум і одне з рішень одно
Вартість транспортних витрат становить: L (Xопт1) = 1550 ум. од.
Зробимо перерозподіл вантажів щодо клітини (3,3):
Занесемо в розподільну таблицю отримане перерозподіл вантажів, обчислимо потенціали зайнятих і оцінки вільних клітин (табл. 23.8):
Так як ?14 = 0, отримали ще одне рішення:
Вартість транспортних витрат складе L (Хопт2) = 1550 ум. од.
Дане завдання має два оптимальних рішення Хопт1 и Xопт2, Загальне рішення знаходиться за формулою
де 0 ? t ? 1.
Знайдемо елементи матриці спільного рішення:
Отже,
Вартість транспортних витрат становить 1550 ум. од.
Поняття про М-методі (методі штучного базису) | Економічна інтерпретація завдання, двоїстої задачі про використання ресурсів | Взаємно двоїсті задачі лінійного програмування і їх властивості | Перша теорема подвійності | Друга теорема подвійності | Об'єктивно обумовлені оцінки та їх зміст | ГЛАВА 7. ТРАНСПОРТНА ЗАВДАННЯ | Знаходження початкового базисного розподілу поставок | Критерій оптимальності базисного розподілу поставок | Розподільчий метод вирішення транспортної задачі |