Тема 2.5. Транспортная задача.

Оглавление | Назад | Далее | Глоссарий понятий

Частным случаем задачи линейного программирования является транспортная задача.
ТЗ в общем виде состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А₁ , А₂ , ..., А_m в n пунктов назначения B₁ , B₂ , ..., B_n. В качестве критерия оптимальности можно взять минимальную стоимость перевозок всего груза, либо минимальное время его доставки.
Рассмотрим задачу с первым критерием, обозначив через сn тарифы перевозок единицы груза из i-го пункта отправления в j-й пункт назначения, через a_i - запасы груза в пункте А_i через b_j - потребности в грузе пункта B_j , x_ij - количество единиц груза, перевозимого из i-го пункта в j-й пункт.
Составим математическую модель задачи. Так как от i-гo поставщика к j-му потребителю запланировано к перевозке x_ij единиц груза.

Таблица 2.2

Соответственно математическая постановка задачи состоит в определении минимума целевой функции

(2.17)

при условиях:

	(i = l, ..., m),	(2.18)
	(j = 1, ..., n),	(2.19)
xij ≥ 0	(i = l, ..., m; j = l, ..., n).	(2.20)

Всякое неотрицательное решение систем уравнений (2.18)-(2.20), определяемое матрицей X=(x_ij ), называют опорным планом ТЗ, а план X*=(x_ij ), при котором функция Z принимает минимальное значение - называется оптимальным планом ТЗ.
Все данные, а затем и опорный план, удобно занести в распределительную таблицу (см, в примерах параграфа).
Если общее количество груза в пунктах отправления и общая потребность в нем в пунктах назначения совпадают, т.е.

(2.21)

то модель ТЗ называется закрытой.

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

Доказательство:

Тогда величины x_ij = a_ib_j /M (i = 1, 2, ..., m; j = 1, 2, ..., n) являются планом, так как они удовлетворяют, системе ограничений (2.18), (2.19). Действительно, подставляя значения x_ij в (2.18) и (2.19), имеем

Выберем из значений C_ij наибольшее С'= mах C_ij и заменим в линейной функции (2.17) все коэффициенты на С' тогда, учитывая (2.18), получаем

Выберем из значений C_ij наименьшее С''=min C_ij и заменим в линейной функции все коэффициенты на С'' тогда, имеем

Объединяя два последних неравенства в одно двойное, окончательно получаем C"M ≤ Z ≤ C'M, т. е. линейная функция ограничена на множестве планов транспортной задачи.
Ч.Т.Д.
Если общее количество груза в пунктах отправления и общая потребность в нем в пунктах назначения не совпадают ТЗ называется открытой. Введением фиктивного потребителя (если ), или фиктивного отправителя (если , любая задача приводится к закрытой модели (во всех фиктивных ячейках таблицы полагают c_ij= 0). Для разрешимости задачи равенство (2.21) является необходимым и достаточным условием.
Нахождение опорных и оптимального планов ТЗ можно вести симплексным методом, но, ввиду специфики ТЗ, и большого ее прикладного значения, разработаны специальные методы.
Нахождение опорных планов ТЗ можно осуществить одним из пяти методов: северо-западного угла, минимальной стоимости, аппроксимации Фогеля, двойного предпочтения и дельта-метода.

Оглавление | Назад | Далее | Глоссарий понятий