Лекция 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. Если сумма запасов груза равна суммарной потребности в нем:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наши рекомендации