Постановка транспортной задачи
Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления A1, A2, . . . , Am в n пунктов назначения B1, B2, . . . , Bn. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через cij тарифы перевозок единицы груза из i-го пункта отправления в j-й пункт назначения, через ai - запасы груза в i-м пункте отправления, через bj - потребности в грузе в j-м пункте назначения, а через xij - количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка транспортной задачи состоит в определении минимального значения функции
(1.1)
Поскольку переменные xij (i=1,m; j=1,n) удовлетворяют системам линейных уравнений и условию неотрицательности, обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки.
Определение 1
.1
Всякое неотрицательное решение систем линейных уравнений, определяемое матрицей X=(xij) (i=1,m; j=1,n), называется планом транспортной задачи.
Определение 1.2.
План X*=(xij*)(i=1,m; j=1,n), при котором целевая функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи.
Обычно исходные данные транспортной задачи записываются в виде таблицы , как показано в таблице 1.
Таблица 1
|
Пункты отправления |
Пункты назначения |
Запасы | ||||
|
B1 |
. . . |
Bj |
. . . |
Bn | ||
|
A1 |
c11 x11 |
. . . |
c1j x1j |
. . . |
c1n x1n |
a1 |
|
Ai |
ci1 xi1 |
. . . |
cij xij |
. . . |
cin xin |
ai |
|
Am |
cm1 xm1 |
. . . |
cmj xmj |
. . . |
cmn xmn |
am |
|
Потребности |
b1 |
. . . |
bj |
. . . |
bn | |
Очевидно, общее наличие груза у поставщиков равно 
, а общая потребность в грузе в пунктах назначения равна 
. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е.
= (1.2)
то модель такой транспортной задачи называется закрытой
. Если же указанное условие не выполняется, то модель транспортной задачи называется открытой
.
Теорема 1.1.
Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, т. е. чтобы выполнялось равенство.
В случае превышения запаса над потребностью, т. е. при >, вводят фиктивный (n+1)-й пункт назначения с потребностью bn+1=- и соответствующие тарифы считают равными нулю: cin+1=0 (i=1,m). Полученная задача является транспортной задачей, для которой выполняется равенство закрытости.