Альтернативный оптимум в транспортных задачах
Признаком наличия альтернативного оптимума в транспортной задаче является равенство нулю хотя бы одной из оценок свободных переменных в оптимальном решении (Xопт1).Сделав перераспределение грузов относительно клетки, имеющей Δij = 0, получим новое оптимальное решение (Хопт2), при этом значение целевой функции (транспортных расходов) не изменится.
Если одна оценка свободных переменных равна нулю, то оптимальное решение находится в виде
где 0 ≤ t ≤ 1.
Рассмотрим конкретную задачу, имеющую альтернативный оптимум.
Пример. На трех складах имеется мука в количестве 60, 130 и 90 т, которая должна быть в течение месяца доставлена четырем хлебозаводам в количестве: 30, 80, 60, 110 т соответственно.
Составить оптимальный план перевозок, имеющий минимальные транспортные расходы, если стоимость доставки 1 т муки на хлебозаводы задана матрицей
Решение. Составим распределительную таблицу в виде таблицы.
По методу минимального тарифа найдем исходное решение. Определим потенциалы строк и столбцов. Найдем оценки свободных клеток:
Так как Δ12 = 4 > 0, то перераспределим грузы относительно клетки (1,2):
Занесем полученное перераспределение грузов в распределительную таблицу и вычислим потенциалы занятых и оценки свободных клеток.
Получим
Так как Δ33 = 0, то задача имеет альтернативный оптимум и одно из решений равно
Стоимость транспортных расходов составляет: L(Xопт1) = 1550 усл.
ед.Произведем перераспределение грузов относительно клетки (3,3):
Занесем в распределительную таблицу полученное перераспределение грузов, вычислим потенциалы занятых и оценки свободных клеток:
Так как Δ14 = 0, получили еще одно решение:
Стоимость транспортных расходов составит L(Хопт2) = 1550 усл. ед.
Данная задача имеет два оптимальных решения Хопт1 и Xопт2, общее решение находится по формуле
где 0 ≤ t ≤ 1.
Найдем элементы матрицы общего решения:
Итак,
Стоимость транспортных расходов составляет 1550 усл. ед.