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

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

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

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

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

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

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

, (8)

, (9)

, (10)

, (11)

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

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

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

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

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

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

,

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

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

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

Пример 4.4.1.

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

Bj

Рис.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
Bj	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.

Vj Ui		-1
-1

Рис. 8.

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

Vj Ui		-1
	-2	-5	-2
		-6
-1		-6	-5	-3

Рис. 9.

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

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

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

Рис. 10.

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

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

Vj Ui	-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.

Vj Ui	-2	-1	-1		-3
	-7	-5	-4		-5
	-2	-4			-3
	1-	-1	-2
	7+		-1	3-	-5

Рис. 13.

1-				9
7+			3-

Рис. 14.

Vj Ui	-2	-1	-1		-1
	-7	-5	-4		-3
	-2	-4			-1
	-2	-3	-4
			-1		-3

Рис. 15.

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

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

.

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