Метод указания к лаб работам ИСО, страница 6

Заявки:

18

27

42

12

26

125

Остановимся теперь на одной особенности плана перевозок. Речь идет о так называемом «вырожденном» плане, в котором некоторые из базисных перевозок оказываются равными 0.

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

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

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

Сток Исток											Запасы:
		10		8		5		6		9	20

10		10				e
					6				7				8				6			5	30

						20-e				10+e
					8				7				10				8			7	25

										25-e				e
					7				5				4				6			8	20

20+e

Заявки:

10

10

20

35

20

95

Особенностью этого опорного плана является то, что в нем только 6 , а не 8 отличных от нуля перевозок (r = m + n – 1 = 4 + 5 – 1 = 8).

В дальнейшем нам удобно будет всегда иметь в транспортной таблице r базисных клеток, хотя в некоторых из них, может быть, будут стоять нулевые значения перевозок. Для этого можно ничтожно мало изменить запасы или заявки, например, на величину e, а после нахождения оптимального решения положить e = 0.

Улучшение плана перевозок. Цикл пересчета

Метод «северо-западного» угла позволяет отыскать допустимый план перевозок, который мы назвали опорным планом. Очевидно, что в общем случае опорный план, являясь допустимым, не является оптимальным. Для нахождения оптимального плана перевозок необходимо последовательно, пока это возможно, улучшать опорный план. В этом параграфе мы рассмотрим термины и определения, используемые при улучшении опорного плана, которые нам в дальнейшем потребуются при рассмотрении алгоритмов решения транспортной задачи.

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

Сток Исток											Запасы:
		10		8		5		6		9	48

18		27				3
					6				7				8				6			5	30

						30
					8				7				10				8			7	27

						9				12				6
					7				5				4				6			8	20

20

Заявки:

18

27

42

12

26

125

Стоимость этого плана равна:

L = 18×10 + 27×8 + 3×5 + 30×8 + 9×10 + 12×8 + 6×7 + 20×8 = 1039.

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

Сток Исток											Запасы:
		10		8		5		6		9	48
			27		21
		6		7		8		6		5	30
	18				12
		8		7		10		8		7	27
					9		12		6
		7		5		4		6		8	20
									20
Заявки:	18		27		42		12		26		125

Таким образом, мы получили новый допустимый план, стоимость которого равна:

L = 18×6 + 27×8 + 21×5 + … = 913.