Лекция 9. Транспортная задача

План.

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

9.2. Нахождение первоначального базисного распределения поставок.

9.3. Решение транспортной задачи методом потенциалов.

6.4. Вырожденность в транспортных задачах.

6.5. Открытая модель транспортной задачи.

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

Транспортная задача – одна из распространенных задач линейного программирования. Ее цель – разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.

В общем виде транспортную задачу можно представить следующим образом: в m пунктах производства А₁, А_2, ¼, А_m имеется однородный груз в количествах соответственно а₁, а_2, ¼, а_m. Этот груз необходимо доставить в n пунктов назначения В₁, В₂, ¼, В_n в количествах, соответственно b₁, b₂, ¼, b_n. Стоимость перевозки 1 ед. груза (тариф) из пункта А_i в пункт B_j равна с_ij ден. ед.

Требуется составить план перевозок, позволяющий вывезти все грузы, полностью удовлетворить потребителей, и имеющий минимальную стоимость.

В зависимости от соотношения между суммарными запасами груза и суммарными потребностями в нем транспортные задачи могут быть закрытыми и открытыми.

Определение 1. Если сумма запасов груза равна суммарной потребности в нем:

,

то транспортная задача называется закрытой.

Определение 2. Если сумма запасов груза не равна суммарной потребности в нем:

,

то транспортная задача называется открытой.

Рассмотрим закрытую транспортную задачу. Обозначим x_ij – количество груза, перевозимого из пункта А_i в пункт B_j.

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

при ограничениях:

.

Оптимальным решением является матрица

,

удовлетворяющая системе ограничений и доставляющая минимум целевой функции.

Транспортная задача как задача линейного программирования, может быть решена симплексным методом, однако наличие большого числа переменных и ограничений делает вычисления громоздкими. Поэтому для решения транспортных задач разработан специальный метод, имеющий те же этапы, что и симплексный метод, а именно:

1) нахождение исходного опорного решения;

2) проверка этого решения на оптимальность;

3) переход от одного опорного решения к другому.

Рассмотри каждый из этапов.