3. При условии построения всех безызбыточных покрытий

В этом случае п.4 не выполняется – нельзя вычеркивать никакие поглощаемые строки.

2.5. Алгоритм приближенного решения задачи о покрытии

Покрытие, близкое к кратчайшему, даёт следующий алгоритм преобразования ТП; основанный на методе “минимальный столбец – максимальная строка”.

0. Исходная таблица считается текущей преобразуемой ТП, множество строк покрытий – пусто;

1. В текущей таблице выделяется столбец с наименьшим числом единиц. Среди строк, содержащих единицы в этом столбце, выделяется одна с наибольшим числом единиц. Эта строка включается в покрытие, текущая таблица сокращается вычеркиванием всех столбцов, в которых выбранная строка имеет единицу.

2. Если в таблице есть невычеркнутые столбцы, то выполняется п. 1, иначе – покрытие построено.

Примечание. При подсчёте числа единиц в строке учитываются единицы в невычеркнутых столбцах.

2.6. Задачи для самостоятельной работы

1. Сократить до циклического остатка (ЦО) заданную ТП с помощью теорем 2.3-2.7 с гарантией построения одного кратчайшего покрытия.

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

3. Решить задачу о покрытии методом минимального столбца - максимальной строки.

4. Сравнить полученные решения и сделать выводы.

1	1	2	3	4	5	6	7	8	9	10		2	1	2	3	4	5	6	7	8	9	10
А		1					1	1				А	1	1						1
Б	1			1								Б					1		1	1
В						1			1			В	1				1	1			1
Г		1	1						1	1		Г		1		1
Д				1				1				Д						1		1	1	1
Е	1					1				1		Е			1				1			1
Ж			1		1				1			Ж				1			1
З	1				1		1					З			1			1

3	1	2	3	4	5	6	7	8	9	10		4	1	2	3	4	5	6	7	8	9	10
А	1	1						1				А	1			1
Б		1			1		1					Б	1				1		1		1
В				1			1					В				1	1	1
Г				1				1				Г		1								1
Д		1				1			1	1		Д			1			1		1
Е			1				1			1		Е		1	1				1
Ж	1				1	1			1			Ж	1							1	1
З			1			1						З						1				1

5	1	2	3	4	5	6	7	8	9	10		6	1	2	3	4	5	6	7	8	9	10
А						1	1	1				А		1					1	1
Б	1		1		1				1			Б	1					1				1
В				1	1	1						В	1								1
Г		1								1		Г		1	1						1	1
Д	1			1								Д				1				1
Е		1	1				1					Е				1		1
Ж	1							1	1			Ж			1		1				1
З						1				1		З					1	1	1

23