Транспортная задача

Транспортная задача является частным случаем задачи линейного программирования и может

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок

Рассмотрим транспортную задачу, в которой в качестве критерия оптимальности берется

Математическая модель транспортной задачи

Найти
при ограничениях

Первое ограничение
означает, что все потребности должны быть удовлетворены ,

Определение. Всякое неотрицательное решение системы ограничений транспортной задачи, определяемое матрицей

Определение.
План ,
при котором целевая функция принимает минимальное

Тарифы или стоимости перевозок единицы груза также задаются матрицей, которая

Транспортная таблица

Необходимое и достаточное условие разрешимости транспортной задачи
Для разрешимости транспортной задачи

При выполнении этого условия модель транспортной задачи называется закрытой. Если

В случае открытой транспортной задачи выполнение балансового условия достигается введением

Любое решение транспортной задачи представляет собой распределение перевозок в транспортной

Пример

Все грузы должны быть перевезены, поэтому
Это три первых уравнения.

А целевую функцию составили по матрице С - матрице тарифов

Пример. Задача организации оптимального снабжения .

Три фермерских хозяйства ежедневно могут

Таблица

Экономико-математическая модель задачи.

Переменные :
- количество молока , поставляемое

Эта задача является задачей открытого типа, так как запасы молока

Функциональные ограничения:

По поставщикам (их 3)

по потребителям (их 5)

Этапы решения транспортной задачи

Составляют математическую модель задачи.
Находят исходное опорное решение.
Проверяют это

Будем называть переменные , стоящие в занятых клетках распределительной или

Определение исходного допустимого решения

1. Метод «северо-западного угла»
Метод заключается

2. Метод «наименьшей стоимости»
Метод заключается в том, что заполнение

Найти опорный план транспортной задачи методом наименьшей стоимости

Минимальный тариф, равный 1 , находится в клетке .
Положим

В оставшейся части таблицы с двумя строками и и c

Временно исключим из рассмотрения столбец и будем считать запасы пункта

Заполним описанным выше способом эту клетку и аналогично заполним (

В результате получим опорный план
При данном плане перевозок общая стоимость

Условие невырожденности плана

Если число заполненных клеток равно
m + n

В нашей задаче число заполненных клеток равно m + n

Метод потенциалов проверки решения на оптимальность

Предположим, что каждый пункт отправления

Совокупность уравнений , составленных для всех базисных переменных, представляет совместную

Обозначим через , где назовем псевдостоимостями или косвенными стоимостями (тарифами).

Теорема «о платежах».

Для заданной совокупности платежей
и суммарная косвенная стоимость

Теорема оптимальности.

Если для всех базисных клеток
а для всех свободных

Пример

Найти опорное решение методом минимальной стоимости
и проверить оптимальность

Находим потенциалы базисных клеток

Положим и решим систему.
Получим
Найдем псевдостоимости пустых

Пример 2.

На складах имеются запасы продукции 90, 400 и 110

Расходы на перевозки 1 т продукции заданы матрицей (у.е.)
Сумма потребностей

План

2)Проверим план на оптимальность методом потенциалов.
В таблице занято клеток

Внесем в таблицу потенциалы занятых клеток

Найдем оценки свободных клеток.
Решение не оптимально, т.к. имеется отрицательная оценка.

3)Переход к другому решению.
Перераспределим грузы, перемещая их из занятых

Около свободной клетки цикла ставится (+), а затем поочередно(-) ,

Получили новое решение
Проверим его на оптимальность, вычислив потенциалы базисных

Потенциалы заполненных клеток

Оценки свободных клеток
План не оптимален, т.к. оценка клетки (21) отрицательна.

Новый план
Снова проверяем его на оптимальность. Для занятых клеток

Для свободных клеток псевдостоимости равны

Оценки свободных клеток