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

В общем виде транспортная задача формулируется следующим образом. Имеется 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

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

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