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

Транспортная задача

Рассмотрим простейшую постановку транспортной задачи. В m пунктах отправления А₁, А₂,..., А_т находится однородный груз, в количествах a₁, a₂,..., a_т единиц (ед.) (например, тонн) соответственно. Потребность в этом грузе в п пунктах назначения В₁, В ₂,..., В_т составляет соответственно b₁, b₂,..., b_т ед. груза. Стоимость перевозки ед. груза (удельная стоимость) из пункта А_i в пункт В_j (короче, из А_i в B_j) равна c_ij, i = 1, 2,..., т, j = 1, 2,..., n. Все эти данные можно свести в табл. 1, называемую матрицей перевозок, разграфив ее для удобства на клетки.

 

Таблица 1

ai / bj	b1	b2	…	bn
a1	c11	c12	…	c1n
a2	c21	c22	…	c2n
…	…	…	…	…
am	cm1	cm2	…	cmn

 

Можно считать, что сумма a запасов в пунктах отправления равна суммарным потребностям b в пунктах назначения, т.е.

. (1)

Такая модель транспортной задачи называется закрытой. Если условие (1) не выполняется, т.е. модель открытая, то в случае, когда а > b, вводят фиктивный пункт назначения B_n+1, полагая

b_n+1 = a-b, c_i,n+1 = 0, i=1, 2,..., m.

Если, наоборот, а < b, то вводят фиктивный пункт отправления A_m+1, полагая

a_m+1 = b-a, c_m+1,j = 0, j=1, 2,..., n.

Пусть x_ij — неизвестный пока объем груза, который по плану перевозок следует доставить из А_i в B_j, i = 1, 2,..., т, j = 1, 2,..., n. Зане­сем неизвестные x_ij в табл. 1 и приступим к составлению ограничений. Возьмем какой-нибудь пункт отправления, например А_i. Весь груз из него должен быть вывезен (это следствие того, что модель закрытая), поэтому сумма неизвестных в i -ой строке табл. 1 должна равняться a_i, т.е.

x_i1 + x_i2 +... + x_in = a_i, i = 1, 2,..., m.

Таким образом, получим систему линейных уравнении (2) для пунктов отправления. Аналогично, сумма неизвестных, стоящих в j -ом столбце табл. 1, должна равняться b_j, т.е.

x_1j + x_2j +... + x_mj = b_j, j = 1, 2,..., n.

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

x₁₁ + x₁₂ +... + x_1n = a₁,

x₂₁ + x₂₂ +... + x_2n = a₂, (2)

…

x_m1 + x_m2 +... + x_mn = a_m;

 

x₁₁ + x₂₁ +... + x_m1 = b₁,

x₁₂ + x₂₂ +... + x_m2 = b₂, (3)

…

x_1n + x_2n +... + x_mn = b_n.

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

. (4)

Итак, для решения поставленной задачи требуется среди неотрица­тельных решений системы линейных уравнений (2)-(3) найти реше­ние, дающееминимум форме z (4).

Система линейных уравнений (2)-(3), состоит из (т + n) уравнений с т • n неизвестными, причем эта система линейно зависима, так как в силу условия (1) сумма первых m уравнений (подсистема (2)) совпа­дает с суммой остальных n уравнений (подсистема (3)). Это означает, что ранг системы (2)-(3) меньше, чем (m+n). Можно показать, что он равен m+n- 1, следовательно, базис системы уравнений (2)-(3) содержит m + n -1 неизвестных.

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

Решение транспортной задачи начинается с нахождения какого-либо допустимого базисного решения.

Формирование начального плана методом северо-западного угла

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

Пример 1. Исходные данные транспортной задачи сведены в табл. 2. Найти базисное решение по правилу северо-западного угла.

Таблица 2.

ai \ bj	b1=25	b2=10	b3=35	b4=5	b5=35
a1 =20
a2 =30
a3 =45
a4 =15

 

Схема распределения груза по правилу северо-западного угла состоит в следующем. Попытаемся удовлетворить потребности пункта назначения В₁ в 25 ед. груза (1-ая колонка плана перевозок x_ij)

За счет пункта отправления А₁ можно удовлетворить только 20 ед., т.е. полагаем x₁₁ = 20. Недостающие 5 ед. для пункта В₁ берем из пункта А₂, т.е. х₂₁ = 5. После этого план перевозок x_ij примет вид

ai \ bj	b1=25	b2=10	b3=35	b4=5	b5=35	Остаток ai
a1 =20
a2 =30
a3 =45
a4 =15
Остаток bj

В нижней строке и правом столбце указываем остаток нераспределенного груза. В строке для А₁ и в столбце для В₁ остаток равен нулю, т.е груз полностью распределен.

За счет А₂, где осталось 25 ед., удовлетворяем также В₂, полагая x₂₂ = 10. В столбце для В₂ получаем остаток, равный нулю. Поэтому оставшиеся в А₂ 15 ед. отправляем в В₃. Продолжая аналогичным образом, получим следующий план перевозок (в числителе клетки показаны значения c_ij, а в знаменателе – x_ij):

Таблица 3.

ai \ bj	b1=25	b2=10	b3=35	b4=5	B5=35
a1 =20	5 / 20	6 / 0	2 / 0	3 / 0	1 / 0
a2 =30	3 / 5	7 / 10	8 / 15	6 / 0	8 / 0
a3 =45	9 / 0	8 / 0	1 / 20	4 / 5	3 / 20
a4 =15	9 / 0	3 / 0	6 / 0	10 / 0	7 / 15

 

Ненулевыми оказалось m+n -1= 4+5-1=8 клеток. Они соответствуют неизвестным

x₁₁, x₂₁, x₂₂, x₂₃, x₃₃, x₃₄, x₃₅, x₄₅. (5)

Можно показать, что систему уравнении вида (2)-(3) для данной задачи можно разрешить относительно указанных неизвестных (5), т.е. эти неизвестные образуют базис, а решение, полученное в табл. 3, является базисным для базиса (5). Клетки в матрице перевозок, от­вечающие базисным неизвестным, принято называть базисными, а остальные - свободными. Для того чтобы базисные клетки отличить от свобо­дных, будем выделять их более жирным шрифтом, помещая в знаменателе значение базисного неизвестного в базисном решении. В свободных клетках будем помещать в знаменателе нули.

Полученный план перевозок имеет стоимость

Z = 5*20+3*5+7*10+8*15+1*20+4*5+3*20+7*15 = 100+15+70+120+20+20+60+105 = 510

 

Формирование начального плана методом наименьшей стоимости

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

Рассмотрим метод на исходных данных примера 1. Укажем в знаменателе клеток – порядковый номер в упорядоченной по возрастанию последовательности c_ij. При одинаковых значениях c_ij приоритет устанавливаем по убыванию max(a_i, b_j) (значение приведено в скобках в числителе):

Таблица 4.

ai \ bj	b1=25	b2=10	b3=35	B4=5	B5=35
a1 =20	5(25) / 9	6(20) / 12	2(35) / 3	3(20) / 6	1(35) / 2
a2 =30	3(30) / 5	7(30) / 14	8(35) / 16	6(30) / 11	8(35) / 17
a3 =45	9(45) / 18	8(45) / 15	1(45) / 1	4(45) / 8	3(45) / 4
a4 =15	9(25) / 19	3(15) / 7	6(35) / 10	10(15) / 20	7(35) / 13

 

Начинаем распределение с элемента х₃₃ =35 (т.к. В₃ может принять только такое количество груза), затем x₁₅ = 20 и заносим в табл. 5. Так как запасы пункта A₁ исчерпаны, то 1-я строка исключа­ется из дальнейшего рассмотрения, так же как в 3-й столбец, поскольку потребности В₃ также удовлетворены. В табл. 5 они для дальнейшего удобства отмечены крестиками в самом правом столбце и самой нижней строке.

Таблица 5.

ai \ bj	b1=25	b2=10	b3=35	B4=5	B5=35
a1 =20	5 / 0	6 / 0	2 / 0	3 / 0	1 / 20	Х
a2 =30	3 / 0	7 / 0	8 / 0	6 / 0	8 / 0
a3 =45	9 / 0	8 / 0	1 / 35	4 / 0	3 / 0
a4 =15	9 / 0	3 / 0	6 / 0	10 / 0	7 / 0
			Х

 

В оставшихся клетках табл. 4 наименьший порядковый номер в знаменателе равен 4 в клетке (3,5). Для пункта В₅ остаток составляет 15 ед. груза, а в A₃ – 10. Присваиваем х₃₅ =10 и закрываем для распределения пункт A₃. Из оставшихся клеток табл. 4 наименьший порядковый номер в знаменателе равен 5 в клетке (2,1). Присваиваем х₂₁ =25 и закрываем для распределения пункт В₁. Полученный план представлен в табл. 6.

Таблица 5.

ai \ bj	b1=25	b2=10	b3=35	B4=5	B5=35
a1 =20	5 / 0	6 / 0	2 / 0	3 / 0	1 / 20	Х
a2 =30	3 / 25	7 / 0	8 / 0	6 / 0	8 / 0
a3 =45	9 / 0	8 / 0	1 / 35	4 / 0	3 / 10	Х
a4 =15	9 / 0	3 / 0	6 / 0	10 / 0	7 / 0
	Х		Х

 

В оставшихся клетках табл. 4 наименьший порядковый номер в знаменателе равен 7 в клетке (4,2). Для пункта В₂ остаток составляет 10 ед. груза. Присваиваем х₄₂ =10 и закрываем для распределения пункт В₂. Далее присваиваем х₂₄ =5 и закрываем для распределения пункт В₄ и A₂.

Таблица 6.

ai \ bj	b1=25	b2=10	b3=35	B4=5	B5=35
a1 =20	5 / 0	6 / 0	2 / 0	3 / 0	1 / 20	Х
a2 =30	3 / 25	7 / 0	8 / 0	6 / 5	8 / 0	Х
a3 =45	9 / 0	8 / 0	1 / 35	4 / 0	3 / 10	Х
a4 =15	9 / 0	3 / 10	6 / 0	10 / 0	7 / 0
	Х	Х	Х	Х

 

Единственная незакрытая клетка (4,5). Присваиваем ей х₄₅ =5. Окончательный план приведен в табл. 7.

Таблица 7.

ai \ bj	b1=25	b2=10	b3=35	B4=5	B5=35
a1 =20	5 / 0	6 / 0	2 / 0	3 / 0	1 / 20	Х
a2 =30	3 / 25	7 / 0	8 / 0	6 / 5	8 / 0	Х
a3 =45	9 / 0	8 / 0	1 / 35	4 / 0	3 / 10	Х
a4 =15	9 / 0	3 / 10	6 / 0	10 / 0	7 / 5	Х
	Х	Х	Х	Х	Х

 

Распределение груза закончено. Подученное в табл. 7 решение оказалось вырожден­ным, так как содержит 7 ненулевых значений неизвестных вместо нужных 8 = m+n –1=4+5-1. Дня того чтобы иметь 8 базисных клеток, нужно в одну из незаполненных клеток (но не любую), например, в клетку с индексами (3, 4), поместить нуль. Получим табл. 8. В ней.8 базисных клеток для наглядности отмечены цветом. Значения базисных неизвестных в базисном решении равны x₁₅ = 20, x₂₁ = 25, x₂₄ =5, x₃₃ = 35, x₃₄ = 0, x₃₅ = 10, x₄₂ = 10, x₄₅ = 5.

Таблица 8.

ai \ bj	b1=25	b2=10	b3=35	b4=5	B5=35
a1 =20	5 / 0	6 / 0	2 / 0	3 / 0	1 / 20
a2 =30	3 / 25	7 / 0	8 / 0	6 / 5	8 / 0
a3 =45	9 / 0	8 / 0	1 / 35	4 / 0	3 / 10
a4 =15	9 / 0	3 / 10	6 / 0	10 / 0	7 / 5

 

Стоимость перевозок

Z = 1*20+3*25+6*5+1*35+4*0+3*10+3*10+7*5 = 20+75+30+35+30+30+35 = 255,

Что в два раза меньше, чем для плана, полученного методом северо-западного угла.

 

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

Решая транспортную задачу распределительным методом, переходят от одного базисного решения к другому таким образом, что стоимость перевозок уменьшается (не увеличивается). Такой переход осуществляется с помощью цикла пересчета свободной клетки. Циклом в матрице перевозок называется замкнутая ломаная линия, составленная из горизонтальных и вертикальных отрезков, вершины которой находятся в клетках таблицы,

 

Рис. 1

 

Приведем некоторые свойства циклов.

Свойство 1. Число вершин в цикле четно.

Припишем каждой вершине цикла знак "+" или "–" таким образом,.чтобы две соседние вершины имели разные знаки. Такой цикл назовем означенным. Будем для краткости называть клетку, в которую попала вершина означенного цикла со знаком "+", положительной, а клетку с вершиной, помеченной знаком "–" — отрицательной.

Свойство 2. В любой строке (столбце) матрицы перевозок, где на­ходятся вершины означенного цикла, число положительных клеток равно числу отрицательных клеток.

Свойство 3. Если в матрице перевозок размеров т на п, т ³ 2, п ³ 2 указать произвольным образом (m + n) клеток, то существует цикл, все вершины которого находятся необязательно во всех указанных клетках.

Пусть дано некоторое решение системы уравнений (2)-(3). Вне­сем значения неизвестных, которые они принимают в этом решении, в соответствующие клетки матрицы перевозок. Построим в матрице перевозок некоторый цикл, означим его. Затем значения неизвестных, стоящие в положительных клетках, увеличим на некоторое число x₀, а значения не­известных, стоящие в отрицательных клетках, уменьшим на то же число x₀. Такое преобразование матрицы перевозок называется сдвигом по дан­ному циклу на число x₀.

Теорема 1. Сдвиг по циклу на некоторое число x₀ , отличное от нуля, переводит одно решение системы уравнений (2)-(3) в некоторое другое решение этой системы.

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

Пусть найдено некоторое базисное решение системы уравнений (2)-(3). Ему соответствует стоимость перевозок, определяемая формулой (4). Впишем значения базисных неизвестных в соответствующие клетки матрицы перевозок, отметив их цветом.

 

Теорема 2. Не существует цикла, все вершины которого находятся в базисных клетках.

Предположим обратное: пусть такой цикл существует. Означим его и произведем сдвиг по этому циклу на некоторое число x₀. Тогда базисные неизвестные изменят свои значения, т.е. по теореме 1 получим новое решение системы (2)-(3), в то время как свободные неизвестные не изменят свои значения (они по-прежнему равны нулю), что невозможно.

Теорема 3. Для каждой свободной клетки существует, и притом единственный, цикл, одна вершина которого находится в данной свободной клетке, а все остальные — в базисных, необязательно во всех.

Действительно, возьмем произвольную свободную клетку. Число бази­сных клеток вместе с взятой свободной равно (m+n). По свойству 3 циклов найдется цикл, все вершины которого находятся в этих (т +п) клетках, необязательно во всех, но по теореме 2 одна вершина обязательно попа­дет в данную свободную клетку. Покажем, что этот цикл единственный. Предположим, что нашелся другой цикл, одна вершина которого находится в данной свободной клетке, а остальные — в базисных. Тогда означим оба цикла так, чтобы их общая вершина в свободной клетке имела бы знак "+", и произведем по одному из циклов сдвиг на число x₀ ¹0, – а по другому циклу — на число (–x₀). В результате базисные неизвестные в тех клет­ках, где вершины циклов не совпадают, изменят свои значения, в то время как свободные неизвестные не изменят свои значения (они по-прежнему равны нулю), что невозможно.

Цикл, существование и единственность которого для данной свободной клетки следует из теоремы 3, будем всегда означивать так, чтобы свобо­дная клетка была положительной. Он называется циклом пересчета данной свободной клетки.

Пусть в матрицу перевозок внесено некоторое допустимое базисное решение. Возьмем произвольную свободную клетку, например с индексами (i, j) (короче, клетку (i, j)), и построим для нее цикл пересчета, см. рис. 2. Осуществим сдвиг по циклу на некоторое число x₀. Это приведет по теореме 1 к новому решению системы уравнений (2)-(3) и измене­нию стоимости перевозок, равному

Dz = c_ijx₀ – c_ikx₀ + c_lkx₀ – … + c_stx₀ – c_sjx₀ = S (c⁺_ij – c^–_ij) x₀ (5)

В формуле (5) через c⁺_ij и c^–_ij символически обозначены удельные стоимости, находящиеся соответственно в положительных и отрицатель­ных базисных клетках. Индексы i и j указывают на то, что в этих клетках находятся вершины цикла пересчета свободной клетки (i, j). Величина

d _ij = S (c⁺_ij – c^–_ij) = c_ij – c_ik + c_lk – … + c_st – c_sj (6)

называется оценкой свободной клетки (i, j) для данного базисного реше­ния. Она не зависит от величины сдвига x₀. Экономический смысл оценки d _ij свободной клетки (i, j) состоит в том, что она равна изменению стои­мости перевозок при сдвиге по циклу пересчета свободной клетки (i, j) на единицу груза.

Таблица 9.

ai \ bj	b1=25	b2=10	b3=35	b4=5	B5=35
+ a1 =20	5 / 0	6 / 0	2 / 0	3 / 0	1 / 20
a2 =30	3 / 25	7 / 0	8 / 0	6 / 5	8 / 0
A3 =45	9 / 0	8 / 0	1 / 35	4 / 0	3 / 10
A4 =15	9 / 0	3 / 10	6 / 0	10 / 0	7 / 5

 

Для примера обратимся к табл. 9. В ней построен цикл пересчета для свободной клетки (1, 1). Оценка этой клетки по формуле (6) равна

d _ij = c₁₁ – c₁₅ + c₃₅ – c₃₄ + c₂₄ – c₂₁ = 5 – 1 + 3 – 4 + 6 – 3 = 6.

Это означает, что при сдвиге по построенному циклу единицы груза стоимость перевозок по сравнению со стоимостью плана перевозок табл. 9 возрастет на 6 единиц.

Вернемся к общему случаю. Имеются три возможности для оценки свободной клетки.

1. Если d _ij > 0, то Dz > 0, т.е. сдвиг в рассматриваемую свободную клетку (i, j) приводит к удорожанию перевозок, что удаляет от оптималь­ного решения.

2. Если d _ij = 0, то Dz = 0, т.е. сдвиг по циклу пересчета не влияет на стоимость перевозок.

3. Если d _ij < 0, то Dz < 0, т.е. сдвиг в рассматриваемую свободную клетку (i, j) уменьшает стоимость перевозок. В этом случае следует опре­делить максимальное значение x₀, на которое можно произвести сдвиг по циклу пересчета. Оно находится из соображений неотрицательности ре­шений и равно минимальному из значений x^–_ij – так символически можно обозначить значения базисных неизвестных в отрицательных клетках, т.е.

x₀ =min { x^–_ij } (7)

Осуществим сдвиг по циклу пересчета данной свободной клетки на это число до (7). Базисную клетку, в которой достигается минимум (7), удалим из базиса и сделаем свободной. Ее место займет данная свободная клетка (i, j) со значением x₀ неизвестного x_ij.

Таким образом, подучим новое базисное решение. Значение формы z при переходе к новому решению уменьшится на величину – Dz = d _ij x₀.

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

12Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: