Решение транспортной задачи распределительным методом

В общем виде транспортная задача формулируется следующим образом. Имеется m_i поставщиков (А₁, А₂, А₃, … А_m), располагающих определенным количеством некоторого продукта a_i (где i = 1, 2, … m). Указанный продукт потребляется в пунктах В₁, В₂, …В_n, причем объемы потребления составляют b_j (где j = 1, 2, … n) единиц, а затраты на перевозку единицу продукта из пункта i в пункт j выражены эквивалентным параметром стоимости – расстояния между двумя пунктами l_ij.

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

Условия задачи могут быть представлены в виде матрицы (табл. 1).

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

Х₁₁ + Х₁₂ + Х₁₃ + … + Х_1n = а₁;

Х₂₁ + Х₂₂ + Х₂₃ + … + Х_2n = а₂;

Х₃₁ + Х₃₂ + Х₃₃ + … + Х_3n = а₃;

××××××××××××××××××××××××××××××××××××××××××××××××××;

Х_m1 + Х_m2 + Х_m3 + … + Х_mn = а_m.

Второе условие предусматривает поставку каждому потребителю продукции в пределах его потребности:

Х₁₁ + Х₂₁ + Х₃₁ + … + Х_m1 = b₁;

Х₁₂ + Х₂₂ + Х₃₂ + … + Х_m2 = b₂;

Х₁₃ + Х₂₃ + Х₃₃ + … + Х_m3 = b₃;

××××××××××××××××××××××××××××××××××××××××××××××××××;

Х_1n + Х_2n + Х_3n + … + Х_mn = b_n.

Кроме этого должно соблюдаться условие неотрицательности переменных Х_ij ³ 0.

Требование минимума суммарных транспортных издержек выражается уравнением

P = l₁₁×X₁₁ + l₁₂×X₁₂ + … + l_m1×X_m1 + l_m2×X_m2 + … + l_mn×X_mn = min.

Приведенная модель соответствует условию .

Если нет условия равенства ресурсов и потребителей, то строится открытая модель, ограничения которой выражаются неравенством. При этом возможны два варианта:

1) , т.е. ресурсы превышают потребность. Задача сводится к тому, чтобы определить, у кого из поставщиков и какое количество продукции следует оставить с точки зрения минимизации суммарных транспортных задач;

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

В первом случае математическая модель будет иметь вид

при условии		(i = 1, 2, … m),
		(j = 1, 2, … n).

Во втором случае

при условии		(i = 1, 2, … m),
		(j = 1, 2, … n).

Решение указанных условий транспортной задачи рассмотрим на конкретном примере.

Имеется m_i предприятий на определенном удалении друг от друга с годовой производственной программой выпуска продукции (табл. 2) и предприятий-потребителей, расположенных в различных районах, спрос на продукцию которых полностью удовлетворяется. Расстояния между потребителями и поставщиками (l_ij, км) приведены в исходной матрице (табл. 2.)

Если общие ресурсы предприятий-поставщиков превышают суммарный спрос потребителей, то в таблицу отдельным столбцом следует ввести условного (фиктивного) потребителя, на долю которого и падает превышение ресурсов над спросом.

Если общие ресурсы предприятий поставщиков меньше суммарного спроса потребителей, то необходимо ввести фиктивного поставщика. Ему отводится отдельная строка в таблице.

Таблица 2

Необходимо решить задачу, используя распределительный метод линейного программирования.

Для этого требуется составить первоначальный план перевозки продукции и определить транспортные затраты.

2. 1. Способ «северо-западного угла»

Применение способа «северо-западного угла» начинается с составления плана перевозок для первого предприятия-поставщика (в верхнем углу матрицы). При этом потребности предприятий-потребителей записываются последовательно, начиная с левого верхнего угла матрицы и до полного исчерпания запасов продукции у первого предприятия-поставщика. Затем составляется план перевозок для второго и последующего предприятия-поставщика и так до тех пор, пока не будут удовлетворены все потребности предприятий-потребителей и полностью использованы все запасы продукции у предприятий-поставщиков.

Первоначальное распределение по методу «северо-западного угла» показано в таблице 3.

Таблица 3

Если план перевозок по правилу «северо-западного угла» составлен верно, то в результате получается ступенчатая фигура, начинающаяся в первом верхнем углу таблицы. Число клеток равно числу m + n – 1. В процессе

решения задачи может быть получена вырожденная матрица, т.е. число заполненных клеток в таблице будет меньше m + n – 1 (где m – число строк, n – число столбцов).

Для устранения вырожденности число занятых клеток необходимо увеличить до m + n – 1. С этой целью одну из свободных клеток условно загружают нулевой загрузкой (0) и считают ее занятой. В качестве условно занятой выбирается клетка, которой соответствует наименьшая длина участка l_ij.

Транспортная работа при таком способе распределения

Р = 800×280 + 400×220 + 800×190 + 400×330 + 600×340 + 800×300 =

= 1040000 тыс.км.

2. 2. Способ выбора минимальной длины участка l_ij

По этому способу выбирают минимальную длину участка в матрице l_ij. В клетку с минимальной длиной участка направляют такое количество товара, которое равно минимуму из объемов производства по данной строке или объем производства по данному столбцу. Если минимальным оказался объем производства, то из дальнейшего рассмотрения исключают строку, в которой находится эта клетка. Если же минимальным окажется объем потребления, то из дальнейшего рассмотрения исключают соответствующий столбец. Затем из всех клеток, не исключенных из рассмотрения к настоящему моменту, берут клетку с минимальной величиной l_ij, заполняют ее по тому же правилу и так далее до тех пор, пока весь заданный объем производства не будет полностью распределен.

Покажем использование этого способа на нашем примере (таблица 4).

Таблица 4

Транспортная работа при составлении плана по способу выбора минимальной стоимости

Р = 200×280 + 1000×170 + 400×190 + 800×180 + 600×390 + 800×210 =

= 848000 тыс. км.