<<
>>

Альтернативный оптимум в транспортных задачах

Признаком наличия альтернативного оптимума в транспортной задаче является равенство нулю хотя бы одной из оценок свободных переменных в оптимальном решении (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 усл. ед.

<< | >>
Источник: Архаров Евгений Валерьевич. Учебно–методический комплекс по дисциплине Математика Нижний Новгород, 2011. 2011

Еще по теме Альтернативный оптимум в транспортных задачах:

  1. 1.3. Проблемы реструктуризации отраслевых комплексов и разработка новых принципов управления.
  2. Критерии оптимальности.
  3. § 4. КРИТЕРИЙ КАЧЕСТВА РЕГУЛИРОВАНИЯ И НАДЕЖНОСТЬ ДЕЙСТВИЯ СИСТЕМЫ
  4. § 3. Экологические преступления комплексного характера
  5. Математические и логические "перлы" у Жана Тироля
  6. Альтернативный оптимум в транспортных задачах
  7. Экономический анализ транспортных задач