Алгоритм перестроения базисного решения

Шаг 1. Выбираем ,

Шаг 2. Полагаем ,

Шаг 3. К транспортной таблице, со всеми выделенными базисными и добавленными к ним , применяется правило вычеркивания. Оставшиеся невычеркнутыми элементы образуют цикл.

Шаг 4. При движении по циклу от расставляются знаки минус и плюс поочередно,

Шаг 5. Полагаем ,

Шаг 6. Перестраивается базисное решение по формулам:

, (8)

, (9)

, (10)

, (11)

для невычеркнутых элементов,

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

Шаг 8. Переход к этапу 1.

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

Утверждение 3. Если в транспортной задаче все и являются целыми числами, то любое допустимое базисное решение также целое.

Доказательство. При построении начального базисного решения вычисляется по формуле

,

так как начальное базисное решение имеет только целые компоненты ( и – целые числа), то также целое.

При перестроении начального базисного решения из чего следует, что целое число. Остальные базисные компоненты, вычисляемые по формулам (8)-(11), также целые.

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

Пример 4.4.1.

Имеем транспортную задачу.

B j

Рис.6.

 

Матрица Х – начальное базисное решение, найденное с помощью произвольного выбора .

			7(1)		7
		7(2)		1(3)	8	1
8(4)					2(5)	10	2
		10(6)			4(7)	6(8)	20	10	6
B j	8	10	7	11	9
			4	8
6

Рис. 7.

 

Вычисление потенциалов:

U ₁+ V ₄ =1, U ₃+ V ₅ = 1, U ₁ = 0, V ₁ = 3,

U ₂+ V ₃ = 2, U ₄+ V ₂ = 2, U ₂ = 1, V ₂ = -1,

U ₂+ V ₅ = 3, U ₄+ V ₄ = 4, U ₃ = -1, V ₃ = 1,

U ₃+ V ₁ = 2, U ₄+ V ₅= 5, U ₄ = 3, V ₄ = 1,

V ₅ = 2.

 

 

V j U i		-1
-1

Рис. 8.

 

Для небазисных мест (вычисление оценок и проверка на оптимальность).

V j U i		-1
	-2	-5	-2
		-6
-1		-6	-5	-3

Рис. 9.

 

Для введения в базис выбираем клетку (4;1) т.к. (решение неоптимальное) и поставим .

Определяется цикл, связывающий с базисными элементами по правилу вычеркивания.

					(1)
		7			(5)
8-				2+
				6-
(2)	(3)	(4)

Рис. 10.

 

Расставим знаки при элементах цикла. .

Продолжаем перестраивать базисное решение.

 

V j U i	-2	-1	-4		-3
	-7	-5	-7		-5
		-1			1-
	2-	-1	-5		8+
	6+		-4	4-	-5

Рис. 11.

 

Новое базисное решение и новые оценки представлены на рис. 12.

				1-
2-				8+
6+			4-

Рис. 12.

 

V j U i	-2	-1	-1		-3
	-7	-5	-4		-5
	-2	-4			-3
	1-	-1	-2
	7+		-1	3-	-5

Рис. 13.

 

1-				9
7+			3-

Рис. 14.

 

 

V j U i	-2	-1	-1		-1
	-7	-5	-4		-3
	-2	-4			-1
	-2	-3	-4
			-1		-3

Рис. 15.

 

Все оценки , значит решение оптимальное.

Вычисляем значение целевой функции

.

 

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