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

Симплекс-метод решения задачи линейного программирования является универсальным и применим для решения любых таких задач. Однако существуют некоторые частные типы задач линейного программирования, которые, в силу некоторых особенностей своей структуры, допускают решение более простыми методами. К ним относится, в частности, так называемая транспортная задача.

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

Имеется m пунктов отправления: А ₁, А ₂,..., A_m, в которых сосредоточены запасы какого-то однородного товара (груза) в количестве соответственно a ₁, a ₂,..., a_m единиц. Кроме того, имеется n пунктов назначения: B ₁, B ₂,..., B_n, подавших заявки соответственно на b ₁, b ₂,..., b_n единиц товара.

Предполагается, что сумма всех заявок равна сумме всех запасов:

(3.28)

Известна стоимость c_ij перевозки единицы товара от каждого пункта отправления A_i до каждого пункта назначения B_j. Таблица (матрица) стоимостей перевозки с_ij задана:

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

При такой постановке задачи показателем эффективности плана перевозок является стоимость; поэтому поставленную задачу точнее называют транспортной задачей по критерию стоимости.

Дадим этой задаче математическую формулировку. Обозначим x_ij - количество груза, отправляемого из i -го пункта отправления А_i в j -й пункт назначения В_j (i = 1,..., m; j = 1,..., n). Неотрицательные переменные x ₁₁, x ₁₂,..., x_mn (число которых, очевидно, равно m x n) должны удовлетворять следующим условиям:

1. Суммарное количество груза, направляемое из каждого пункта отправления во все пункты назначения, должно быть равно запасу груза в данном пункте. Это даст нам m условий-равенств:

x 11 + x 12 +... + x 1 n = a 1, x 21 + x 22 +... + x 2 n = a 2, .......................... xm 1 + xm 2 +... + xmn = am,

или, короче,

(3.29)

2. Суммарное количество груза, доставляемое в каждый пункт назначения изо всех пунктов отправления, должно быть равно заявке, поданной данным пунктом. Это даст n условий-равенств:

x 11 + x 21 +... + xm 1 = b 1, x 12 + x 22 +... + xm 2 = b 2, ..................................... x 1 n + x 2 n +... + xmn = bn,

или, короче,

(3.30)

 

3. Суммарная стоимость всех перевозок, т.е. сумма величин x_ij, умноженных на соответствующие стоимости c_ij должна быть минимальной:

L = c ₁₁ x ₁₁ + c ₁₂ x ₁₂ +... + c _{1 n} x _{1 n} +

+ c ₂₁ x ₂₁ + c ₂₂ x ₂₂ +... + c _{2 n} x _{2 n} +... +

+ c_{m 1} x_{m 1} + c_{m 2} x_{m 2} +... + c_mnx_mn = min,

или, гораздо короче,

(3.31)

где знак двойной суммы означает, что суммирование производится по всем комбинациям индексов (i = 1,..., m; j = 1,..., n), т.е. по всем комбинациям пунктов отправления с пунктами назначения.

Функция (3.31) линейна, ограничения - равенства (3.29), (3.30) также линейны. Перед нами - типичная задача линейного программирования с ограничениями-равенствами (ОЗЛП).

Как и всякую другую задачу линейного программирования, ее можно было бы решить симплекс-методом, но данная задача имеет некоторые особенности, позволяющие решить ее более просто. Причиной является то, чтовсе коэффициенты при переменных в уравнениях (3.29), (3.30) равны единице. Кроме того, имеет значение структура связей между условиями. Нетрудно убедиться, что не все m+n уравнений нашей задачи являются независимыми. Действительно, складывая между собой все уравнения (3.29) и все уравнения (3.30), мы должны получить одно и то же, в силу условия (3.28). Таким образом, условия (2), (3) связаны одной линейной зависимостью, и фактически из этих уравнений только m+n -1, а не m+n являются линейно независимыми. Значит, ранг системы уравнений (3.29), (3.30) равен

r = m+n - 1,

а, следовательно, можно разрешить эти уравнения относительно m+n -1 базисных переменных, выразив их через остальные, свободные.

Подсчитаем количество свободных переменных. Оно равно:

k = mn - (m + n - 1) = mn - m - (n - 1) = m (n - 1) - (n - 1) = (m - 1) (n - 1).

Мы знаем, что в задаче линейного программирования оптимальное решение достигается в одной из вершин ОДР, где по крайней мере(m -1) (n -1 ) значений x_ij должны быть равны нулю.

Условимся о терминологии. Значения x_ij количества единиц груза, направляемых из пункта A_i в пункт B_j мы будем называть перевозками.

Любую совокупность значений (x_ij) (i = 1,..., m; j = 1,..., n) будем называть планом перевозок, или просто планом.

План (x_ij) будем называть допустимым, если он удовлетворяет условиям (3.29), (3.30) (так называемым «балансовым условиям»): все заявки удовлетворены, все запасы исчерпаны.

Допустимый план будем называть опорным, если в нем отличны от нуля не более r = m+n -1 базисных перевозок x_ij, а остальные перевозки равны нулю.

План (x_ij) будем называть оптимальным, если он, среди всех допустимых планов, приводит к наименьшей стоимости всех перевозок.

Перейдем к изложению методов решения транспортной задачи (ТЗ). Эти методы не требуют манипуляций с симплекс-таблицами, а сводятся к более простым операциям непосредственно с таблицей, где в определенном порядке записаны все условия ТЗ. Такую таблицу мы будем называть транспортной таблицей.

В транспортной таблице записываются

- пункты отправления и назначения,

- запасы, имеющиеся в пунктах отправления,

- заявки, поданные пунктами назначения,

- стоимости перевозок из каждого пункта отправления в каждый пункт назначения.

Стоимости перевозок мы будем помещать в правом верхнем углу каждой ячейки, с тем чтобы в самой ячейке при составлении плана помещать перевозки x_ij.

Образец транспортной таблицы дан в табл.3.8.

Для краткости в дальнейшем будем обозначать пункты отправления - ПО, пункты назначения - ПН. В правом верхнем углу каждой клетки проставлены стоимости перевозки единицы товара (груза) из ПО А_i в ПН B_j. В правом столбце помещены запасы товара в каждом ПО, в нижней строке - заявки, поданные каждым ПН. Для ТЗ сумма запасов равна сумме заявок; общее значение этой суммы записывается в правой нижней ячейке таблицы.

Таблица 3.8

ПН ПО	B 1	B 2	.......	Bn	Запасы аi
A 1	C 11	C 12	.......	C 1 n	a 1
A 2	C 21	C 22	.......	C 2 n	a 2
: :	....	....	.......	....	: :
Am	Cm 1	Cm 2	.......	Cmn	am
Заявки bj	b 1	b 2	.......	bn

 

Выше мы показали, что ранг системы уравнений-ограничений ТЗ равен r = m+n -1, где m - число строк, а n - число столбцов транспортной таблицы. Значит, в каждом опорном плане, включая оптимальный, будут отличны от нуля не более, чем m+ n -1 перевозок.

Ячейки (клетки) таблицы, в которых мы будем записывать эти отличные от нуля перевозки, условимся называть базисными, а остальные (пустые) свободными.

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

- сумма перевозок в каждой строке таблицы должна быть равна запасу данного ПО;

- сумма перевозок в каждом столбце должна быть равна заявке данного ПН;

- общая стоимость перевозок - минимальная.

В дальнейшем все действия по нахождению решения ТЗ будут сводиться к преобразованию транспортной таблицы 3.8.

При описании этих преобразований нам удобно будет пользоваться нумерацией клеток таблицы (подобной нумерации клеток шахматной доски). Клеткой (А_i,B_j) или, короче, клеткой (i,j) мы будем называть клетку, стоящую в i -й строке и j -м столбце транспортной таблицы. Например, самая верхняя левая клетка будет обозначаться (1,1), стоящая под ней (2,1) и т.д.

3.5.2. Нахождение опорного плана

Решение транспортной задачи, как и всякой задачи линейного программирования, начинается с нахождения опорного решения, или, как мы будем говорить, опорного плана. В отличие от общего случая ОЗЛП с произвольными ограничениями и минимизируемой функцией, решение ТЗ всегда существует.

Построение опорного плана.

Воспользуемся так называемым «способом северо-западного угла». Пояснить его проще всего будет на конкретном примере.

Пример 1. Условия ТЗ заданы транспортной таблицей (см. табл.3.9)

 

Таблица 3.9

ПН ПО	B 1	B 2	В 3	B 4	В 5	Запасы аi
A 1
A 2
А 3
A 4
Заявки bj

 

Требуется найти опорное решение ТЗ (построить опорный план).

Решение.

Перепишем табл.2 и будем заполнять ее перевозками постепенно, начиная с левой верхней ячейки (1,1) («северо-западного угла» таблицы). Будем рассуждать при этом следующим образом. Пункт B₁ подал заявку на 18 единиц груза. Удовлетворим эту заявку за счет запаса 48, имеющегося в пункте А ₁, и запишем перевозку 18 в клетке (1,1). После этого заявка пункта В ₁ удовлетворена, а в пункте А ₁ осталось еще 30 единиц груза. Удовлетворим за счет них заявку пункта В ₂ (27 единиц), запишем 27 в клетке (1,2); оставшиеся 3 единицы пункта А ₁ назначим пункту В ₃ В составе заявки пункта В ₃ остались неудовлетворенными 39 единиц. Из них 30 покроем за счет пункта А ₂, чем его запас будет исчерпан, и еще 9 возьмем из пункта А₃. Из оставшихся 18 единиц пункта А ₃ 12 выделим пункту В ₄; оставшиеся 6 единиц назначим пункту В ₅, что вместе со всеми 20 единицами пункта А ₄ покроет заявку (см. табл.3.10).

На этом распределение запасов закончено: каждый пункт назначения получил груз согласно своей заявке. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце - заявке.

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

Таблица 3.10

ПН ПО	B 1	B 2	В 3	B 4	В 5	Запасы аi
A 1
A 2
А 3
A 4
Заявки bj

 

Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными, их число удовлетворяет условию r = m+n - 1 = 8. Остальные клетки - свободные (пустые), в них стоят ненулевые перевозки, их число равно (n - 1)(m - 1) = 12. Значит, наш план - опорный и поставленная задача построения опорное плана решена.