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

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

Частным случаем задачи линейного программирования является транспортная задача.
ТЗ в общем виде состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А, А, ..., Аm в n пунктов назначения B, B, ..., Bn. В качестве критерия оптимальности можно взять минимальную стоимость перевозок всего груза, либо минимальное время его доставки.
Рассмотрим задачу с первым критерием, обозначив через сn тарифы перевозок единицы груза из i-го пункта отправления в j-й пункт назначения, через ai - запасы груза в пункте Аi через bj - потребности в грузе пункта B, xij - количество единиц груза, перевозимого из i-го пункта в j-й пункт.
Составим математическую модель задачи. Так как от i-гo поставщика к j-му потребителю запланировано к перевозке xij единиц груза.

Таблица 2.2

Поставщики
Потребители
Запасы
B B2
...
Bn
А1

C11

X11

C12

X12

...

C1n

X1n

a1
А2

C21

X21

C22

X22

...

C2n

X2n

a2
...
...
...
...
...
...
Аm

Cm1

Xm1

Cm2

Xm2

...

Cmn

Xmn

am
Потребности
b1
b2
...
bn
∑ai=∑bj

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

(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=(xij ), называют опорным планом ТЗ, а план X*=(xij ), при котором функция Z принимает минимальное значение - называется оптимальным планом ТЗ.
Все данные, а затем и опорный план, удобно занести в распределительную таблицу (см, в примерах параграфа).
Если общее количество груза в пунктах отправления и общая потребность в нем в пунктах назначения совпадают, т.е.

(2.21)

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

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

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

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

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

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

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

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

Hosted by uCoz