Теорема 1.9.1 (о существовании решения)

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

Транспортная задача возникает при формализации множества различных прикладных задач. Здесь будет рассмотрена одна из наиболее простых прикладных задач. Пусть в m пунктах (складах) у поставщиков имеется однородный груз в количестве a ₁, a ₂,…, a _m единиц соответственно. Имеющийся груз необходимо доставить n потребителям, чьи потребности в грузе соответственно равны b ₁, b ₂,…, b _n. Известны стоимости c _ij перевозки одной единицы груза от i –го поставщика j –му потребителю. Требуется составить план перевозок, при котором у поставщиков будет вывезен весь груз, а потребителям доставлено ровно столько, сколько нужно. При этом требуется, чтобы суммарная стоимость перевозок была минимальной.

Обозначим x _ij – количество единиц груза, перевозимого от i –го поставщика j –му потребителю, i =1,…, m, j = 1,…, n. Естественно предположить, что x _ij ≥0 (Груз везут от поставщиков потребителям, а не наоборот). Обозначим

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

∑_i∑_j x _ij c _ij →min

x ₁₁ +…+ x _1n = a ₁,

……………….

x _m1 +…+ x _mn = a _m, (1.17)

x ₁₁ +…+ x _m1 = b ₁,

…………………

x _1n +…+ x _mn = b _n,

x _ij ≥0.

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

a ₁ +…+ a _m = b ₁ +…+ b _n (1.18)

Определение 1.9.1. Транспортная задача называется закрытой, если выполняется равенство (1.18), в противном случае она называется открытой.

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

a ₁ +…+ a _m > b ₁ +…+ b _n.

Тогда нужно ввести фиктивного n + 1 потребителя с потребностью

b _n+1 = a ₁ +…+ a _m – (b ₁ +…+ b _n).

Фиктивного потребителя нет в реальности, следовательно, никто ему груз не повезет. Поэтому стоимость перевозок фиктивному потребителю полагаем равной нулю c _in+1 =0, i = 1,…, m. Далее решается закрытая задача, а груз, поставляемый по оптимальному плану, фиктивному потребителю останется на складе у соответствующего поставщика.

Аналогично, в случае неравенства

a ₁ +…+ a _m < b ₁ +…+ b _n

вводится фиктивный m + 1 поставщик, с запасом на складе в объеме

a _m+1 = b ₁ +…+ b _n – (a ₁ +…+ a _m).

Стоимость перевозки единицы груза от фиктивного поставщика любому потребителю будет равна нулю c _m+1j =0, j = 1,…, n. Затем решается закрытая задача, а груз, который поставил фиктивный поставщик, соответствующий потребитель не дополучит. Транспортная задача является частным случаем задачи линейного программирования. Для нее разработан специальный алгоритм решения. Общая схема решения закрытой транспортной задачи выглядит следующим образом:

- находится начальный опорный план;

- план проверяется на оптимальность;

- если план оптимальный, то алгоритм работу закончил, если план не оптимальный, то нужно перейти к новому, более «хорошему» (т.е. меньшей стоимости) плану;

- новый план проверяется на оптимальность и т. д.

Построение начального опорного плана методом минимального элемента.

Запишем таблицу

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

Выберем среди клеток со стоимостями c_ij клетку с минимально стоимостью и заполняем ее максимальной допустимой поставкой. Вычитаем из соответствующих запасов поставщика и требуемой величины поставки у потребителя, найденную величину поставки. Если у поставщика после вычитания не осталось груза на складе, то все клетки соответствующей строки далее не рассматриваются. Если потребителю после найденной поставки доставлен весь требуемый груз, то все клетки соответствующего столбца далее не рассматриваются. Операция повторяется, пока остается не распределенный груз.

Определение 1.9.2. Будем говорить, что клетка является занятой, если в нее распределена некоторая поставка. В противном случае, клетка называется свободной.

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

Составленный по методу минимального элемента начальный план является опорным, т. е. в этом плане не более чем m + n – 1 занятая клетка. Кроме того, занятые клетки не образуют циклов.

Пример. Пусть задана транспортная задача: a ₁ = 50, a ₂ = 70, a ₃ = 90, b₁ = 50, b₂ = 40, b₃ = 70, b₄ = 40, а матрица стоимостей имеет вид

	b1 = 50	b2 = 40	b3 = 70	b4 = 40
a 1 = 50
a 2 = 70
a 3 = 90

Так как a ₁ + a ₂ + a ₃ =210> b ₁ + b₂ + b₃ + b ₄ =200, то задача не закрытая. Для выполнения равенства вводим фиктивного потребителя с объемом потребности b₅ = 10, а стоимости перевозок этому потребителю положим равными нулю. Получили матрицу

	b1 = 50	b2 = 40	b3 = 70	b4 = 40	b5 = 10
a 1 = 50
a 2 = 70
a 3 = 90

Построим начальный опорный план по методу минимального элемента. В первую очередь нас интересуют клетки соответствующие реальным поставщикам. Среди них (1;1) - клетка с минимальной стоимостью (8 единиц). Этой клетке соответствует потребность в 50 единиц груза, а у поставщика имеется 50 единиц груза. Значит, можем сделать в эту клетку поставку величиной min{50; 50} =50. Заполняем эту поставку. Новые потребности потребителей и возможности поставщиков указаны в скобках.

	b1 = 50(=0)	b2 = 40(=0)	b3 = 70	b4 = 40	b5 = 10
a 1 = 50 (=0)
a 2 = 70
a 3 =90

Так как первому потребителю доставлен весь необходимый груз, то клетки (2;1), (3;1) в дальнейшем поиске минимума не участвуют. У первого поставщика вывезен весь груз, поэтому клетки (1;2), (1;3), (1;4), (1;5) в дальнейшем поиске минимума не участвуют. Из оставшихся клеток реальных поставщиков и реальных потребителей минимальную стоимость имеет клетка (3;2) (9 единиц). В клетке (3;2) величина поставки будет min{90; 40}=40 Делаем поставку в клетку (3;2) величиной 40. Таблица приобретает вид

	b1 = 50(=0)	b2 = 40(=0)	b3 = 70	b4 = 40	b5 = 10
a 1 = 50 (=0)
a 2 = 70
a 3 =90 (=50)

Так как второму поставщику поставлено груза в объеме его потребности, то клетка (2;2) в дальнейшем поиске минимума не участвует (клетка (2;1) выбыла раньше). Из оставшихся реальных клеток минимальную стоимость имеет клетка (3;3) (10 единиц). Величина поставки в эту клетку равна min{50; 70}=50. Вписываем эту поставку.

	b1 = 50(=0)	b2 = 40(=0)	b3 = 70(20)	b4 = 40	b5 = 10
a 1 = 50 (=0)
a 2 = 70
a 3 =90 (=50)(0)

Так как у третьего поставщика вывезен весь груз, клетки (3;4) и (3;5) в дальнейшем поиске минимума не участвуют. Из оставшихся реальных клеток минимальную стоимость имеет клетка (2;3) (12 единиц). Величина поставки в эту клетку равна min{70; 20}=20. Вписываем эту поставку.

	b1 = 50(=0)	b2 = 40(=0)	b3 = 70(20)	b4 = 40	b5 = 10
a 1 = 50 (=0)
a 2 = 70 (50)
a 3 =90 (=50)(0)

Остались только две клетки (2;4) (2;5) в которые можно сделать поставки соответственно min{50; 40}=40 и 10. Записываем эти поставки.

	b1 = 50(=0)	b2 = 40(=0)	b3 = 70(20)	b4 = 40(0)	b5 = 10(0)
a 1 = 50 (=0)
a 2 = 70 (50)(10)(0)
a 3 =90 (=50)(0)

Начальный опорный план по методу минимального элемента составлен. Занятыми являются клетки: (1;1), (2;3), (2;4), (2;5), (3;2), (3;3). Всего занятых клеток 6 < 7=3+5-1.

Определение 1.9.3. Опорный план, в котором ровно m + n – 1 занятая клетка называется невырожденным. В случае, когда занятых клеток меньше величины m + n – 1, опорный план называется вырожденным.

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

	b1 = 50(=0)	b2 = 40(=0)	b3 = 70(20)	b4 = 40(0)	b5 = 10(0)
a 1 = 50 (=0)
a 2 = 70 (50)(10)(0)
a 3 =90 (=50)(0)

Составление начального опорного плана закончено. Все действия по составлению начального опорного плана, в целях экономии времени, можно проводить на одной матрице.

Перейдем к проверке плана на оптимальность. Для этой проверки используем следующую теорему.

Дата добавления: 2014-12-27