23.01. Транспортная задача. Общая постановка задачи

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

В общем виде задачу можно представить следующим об­разом: в Т. пунктах производства A1, A2, ..., Am имеется од­нородный груз в количестве соответственно A1, A2,…, Am. Этот груз необходимо доставить в П пунктов назначения B1, В2, …., Вп в количестве соответственно B1, B2,..., Bп. Сто­имость перевозки единицы груза (тариф) из пункта Ai в пункт Bj равна Cij.

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

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

Определение 1. Если

То задача называется Закрытой. Если

То Открытой.

Обозначим через Xij количество груза, перевозимого из пункта Ai в пункт Bj. Рассмотрим закрытую транспорт­ную задачу. Ее условия запишем в распределительную таблицу, которую будем использовать для нахождения решения (табл. 23.1).

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

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

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

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

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

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

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

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

< Предыдущая		Следующая >