Лекция 9. Транспортная задача
План.
9.1.Экономико-математическая модель транспортной задачи.
9.2. Нахождение первоначального базисного распределения поставок.
9.3. Решение транспортной задачи методом потенциалов.
6.4. Вырожденность в транспортных задачах.
6.5. Открытая модель транспортной задачи.
Экономико-математическая модель транспортной задачи
Транспортная задача – одна из распространенных задач линейного программирования. Ее цель – разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.
В общем виде транспортную задачу можно представить следующим образом: в m пунктах производства А1, А2, ¼, Аm имеется однородный груз в количествах соответственно а1, а2, ¼, аm. Этот груз необходимо доставить в n пунктов назначения В1, В2, ¼, Вn в количествах, соответственно b1, b2, ¼, bn. Стоимость перевозки 1 ед. груза (тариф) из пункта Аi в пункт Bj равна сij ден. ед.
Требуется составить план перевозок, позволяющий вывезти все грузы, полностью удовлетворить потребителей, и имеющий минимальную стоимость.
В зависимости от соотношения между суммарными запасами груза и суммарными потребностями в нем транспортные задачи могут быть закрытыми и открытыми.
Определение 1. Если сумма запасов груза равна суммарной потребности в нем:
,
то транспортная задача называется закрытой.
Определение 2. Если сумма запасов груза не равна суммарной потребности в нем:
,
то транспортная задача называется открытой.
Рассмотрим закрытую транспортную задачу. Обозначим xij – количество груза, перевозимого из пункта Аi в пункт Bj.
Математическая модель транспортной задачи имеет вид
при ограничениях:
.
Оптимальным решением является матрица
,
удовлетворяющая системе ограничений и доставляющая минимум целевой функции.
Транспортная задача как задача линейного программирования, может быть решена симплексным методом, однако наличие большого числа переменных и ограничений делает вычисления громоздкими. Поэтому для решения транспортных задач разработан специальный метод, имеющий те же этапы, что и симплексный метод, а именно:
1) нахождение исходного опорного решения;
2) проверка этого решения на оптимальность;
3) переход от одного опорного решения к другому.
Рассмотри каждый из этапов.