Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Признаком наличия альтернативного оптимума в транспортной задаче является равенство нулю хотя бы одной из оценок свободных переменных в оптимальном решении (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 усл. ед.
Дата публикования: 2014-10-18; Прочитано: 2062 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!