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

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

Пусть некоторый однородный груз сосредоточен у m поставщиков ,,…,в количествеединиц соответственно. Его необходимо перевезтиn потребителям ,,…,, потребности которых в грузе равны. Известны:

- запасы груза у поставщиков ();

- потребности в этом грузе потребителей ();

- стоимость перевозки одной единицы груза от поставщикапотребителю(тариф); тарифы представлены в виде матрицы стоимостей перевозок или матрицы удельных затрат

.

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

Обозначим через - количество груза (перевозка), запланированного к перевозке от поставщикапотребителю.

Очевидно, что оптимальный план перевозок является решением следующей ЗЛП:

,

Транспортная задача, как частный случай общей задачи линейного программирования, может быть решена обычным симплекс – методом, который был рассмотрен нами выше. Однако, ввиду большого числа переменных (их количество равно m×n) практическая его реализация представляет серьезные трудности. С другой стороны, специфика ограничений ТЗ позволяет модифицировать симплекс метод, существенно упростив его реализацию. Все рассмотренные выше планы перевозок по – прежнему будем называть опорными планами, т.к. они соответствуют вершинам многогранника допустимых решений.

4.2. Алгоритм решения транспортной задачи методом потенциалов

Рассмотрим алгоритм решения ТЗ на следующем примере.

Пример 4.1. От трех поставщиков ,инеобходимо перевезти некий однородный груз пяти потребителям,,,и. Известны запасы груза поставщиков

А = (,,)=(14,16,20)

и потребности потребителя

В =(,,,,)= (8,12,7,12,11).

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

.

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

Алгоритм решения транспортной задачи методом потенциалов

Шаг 1. Определение типа транспортной задачи.

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

.

В противном случае, задача открытая. Тогда ее необходимо привести к закрытому типу путем введения фиктивного поставщика или фиктивного потребителя, а именно: если

,

то вводится фиктивный потребитель , потребность которого в грузе равна

.

Если же

,

То вводится фиктивный поставщик , запасы которого составляют

.

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

В примере

, ,

задача имеет закрытый тип.

Шаг 2. Составление матрицы планирования.

Запишем исходные данные в таблицу – матрицу планирования (таблица 4.1):

Таблица 4.1.

			7			5			4			3			4	14
			6			3			5			5			2	16
			5			7			4			3			3	20
	8			12			7			12			11			Σ = 50

В ней в крайнем правом столбце ставим запасы, в нижней строке – потребности, в правом верхнем углу каждой из 15 клеток – соответствующие стоимости перевозок.

Шаг 3. Построение начального опорного плана.

Методом минимальной стоимости (методом наилучшего (минимального) элемента матрицы удельных затрат) составляем начальный опорный план (таблица 4.2).

Таблица 4.2.

			7			5					4			3			4	14
									2				12
			6			3				5				5			2	16
					5											11
			5			7				4				3			3	20
		8			7			5
	8			12			7					12			11			50

1) сначала выбираем клетку, которая имеет минимальную стоимость перевозки (в данном случае – это клетка ) и помещаем в нее максимально возможную перевозку, а именно, при этом из дальнейшего рассмотрения исключаем остальные клетки столбца;

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

В результате будут последовательно заполнены следующие клетки:

(),(),(),() и().

Шаг. 4. Определение невырожденности плана.

План транспортной задачи считается невырожденным, если он содержит ровно m+n-1 занятую перевозкой клетку в матрице планирования. В противном случае план вырожденный. Вырожденный опорный план необходимо привести к невырожденному типу путем введения фиктивных (нулевых) перевозок в том количестве, чтобы число компонентов плана удовлетворяло условию невырожденности. Имеет экономический смысл вводить перевозки в клетках (из незанятых) с минимальным тарифом.

В примере план является невырожденным, т.к. содержит ровно 7 ненулевых перевозок и 7=3+5-1.

Шаг. 5. Составление системе потенциалов.

Каждому поставщику ставим в соответствие число, которое называется потенциалом поставщика, а каждому потребителю- потенциал потребителя. Система потенциалов строится, исходя из условия: для всех занятых клеток сумма потенциалов поставщика и потребителя равна тарифу,

.

Составляем систему потенциалов для рассматриваемой задачи и помещаем ее в таблицу 4.3. Заметим, что порядок вычисления потенциалов зависит от того, какие из семи клеток заняты перевозками.

Таблица 4.3.

			7			5					4			3			4	0
									2				12
			6			3				5				5			2	-4
					5											11
			5			7				4				3			3	0
		8			7			5								*
	5			7			4					3			6

В данном случае порядок такой:

1) сначала любой из потенциалов полагаем равным нулю, например

;

2) поскольку в первой строке заняты две клетки, то находим еще два потенциала:

, ;

3) в третьем столбце есть еще одна занятая клетка, откуда находим

;

4) теперь в третьем столбце есть еще две занятых клетки, значит

, ;

5) далее находим

;

6) наконец, находим последний потенциал

.

Шаг 6. Проверка оптимальности плана.

Для всех пустых клеток матрицы планирования должно выполняться условие: сумма потенциалов поставщика и потребителя не превосходит тарифа,

.

Другими словами, условием оптимальности опорного плана ТЗ является требование для всех незанятых клеток матрицы планирования:

, (4.1)

причем величина оценки

.

В нашем случае получаем такие оценки:

, ,,

, ,,

, .

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

Шаг 7. Определение клетки, в которую посылается перевозка.

Загрузке подлежит та из незанятых клеток, которой соответствует максимальное нарушение оптимальности плана

, .

Эту клетку отмечаем знаком . В нашем случае это клетка , так как

.

Если максимуму соответствует несколько клеток, то выбираем ту из них, которой соответствует минимальный тариф.

Шаг 8. Составление цикла.

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

Рис. 3

Более сложные циклы могут быть такими, как на рисунках 4 и 5.

Рис. 4

Рис. 5

Шаг 9. Определение величины перераспределения.

Найдем минимальную перевозку среди вершин цикла, помеченных, ,

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

Рис. 6

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

В результате получаем новый опорный план (таблица 4.4)

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

Таблица 4.4.

			7			5					4			3			4	0
									2				12
			6			3				5				5			2	-1
					12											4
			5			7				4				3			3	0
		8						5								7
	5			4			4					3			3

Шаг 5’. Построение новой системы потенциалов:

, ,,,,,,.

Шаг 6’. Вычисление оценок и проверка оптимальности:

, ,,,,,,.

Так как все оценки , то это план является оптимальным, а его стоимость

(ден. ед.).