4.4. Правило вычеркивания

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

1. Все элементы вычеркнуты.

2. В каждой из невычеркнутых строк и столбцов содержатся не менее двух выделенных элементов.

Имеют место следующие утверждения.

Утверждение 1. Столбцы , соответствующие вычеркнутым элементам, линейно независимы.

Утверждение 2. Допустимое решение транспортной задачи, построенное с помощью метода северо-западного угла или метода минимального элемента, является базисным.

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

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

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

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

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

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

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

,

,

,

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

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

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

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

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

Пример 4.2. Имеем транспортную задачу (рис. 4.6).

	5	4	3	1	2	7
	3	6	2	4	3	8
	2	4	5	3	1	10
	1	2	3	4	5	20
Bj	8	10	7	11	9

Рис. 4.6

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

										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

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

Занесем полученные результаты в таблицу (рис. 4.8)

Vj Ui	3	-1	1	1	2
0				7
1			7		1
-1	8				2
3		10		4	6

Рис. 4.8

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

Vj Ui	3	-1	1	1	2
0	-2	-5	-2	7	0
1	1	-6	7	6	1
-1	8	-6	-5	-3	2
3	5	10	1	4	6

Рис. 4.9

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

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

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

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

Рис. 4.10

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

Vj Ui	-2	-1	-4	1	-3
0	-7	-5	-7	7	-5
6	1	-1	7	3	1^-
4	2^-	-1	-5	2	8^+
3	6^+	10	-4	4^-	-5

Рис. 4.11

			7
		7		1^-
2^-				8^+
6^+	10		4^-

Рис. 4.12

Vj Ui	-2	-1	-1	1	-3
0	-7	-5	-4	7	-5
3	-2	-4	7	1	-3
4	1^-	-1	-2	2	9
3	7^+	10	-1	3^-	-5

Рис. 4.13

			7
		7	1
1^-				9
7^+	10		3^-

Рис. 4.14

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

Vj Ui	-2	-1	-1	1	-1
0	-7	-5	-4	7	-3
3	-2	-4	7	1	-1
2	-2	-3	-4	1	9
3	8	10	-1	2	-3

Рис. 4.15

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

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

.