C

И
- +					31	0
-					48	-1
+					38	0
	22	34	41	20	117
	6	7	6	7

C

И
					31	0
					48	-1
					38	0
	22	34	41	20	117
	6	7	6	5

Пример 6. Решить методом потенциалов вырожденный случай ТЗ.

С

И
				40	0
				23	1
				20	2
	20	20	43	83
	10	5	4
				40	0
				23	1
				20	2
	20	20	43	83
	5	5	4
				40	0
				23	1
				20	-2
	20	20	43	83
	5	5	4

С

И
				40	0
				23	1
				20	0
	20	20	43	83
	5	3	4

Лабораторная работа № 5 (4 часа)

Задача о назначении

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

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

Специальный метод решения задачи о назначении основан на следующих теоремах.

Теорема 1. Если минимизирует по всем таким, что минимизирует также функционал

Доказательство:

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

Теорема 2. Если все и можно отыскать набор , такой, что , то это решение оптимально, т.е. .

Доказательство. (самостоятельно)

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

В 1912 году венгерский математик Кёниг (König D.) среди других утверждений доказал теорему, благодаря которой оказалось возможным построить алгоритм решения задач о назначении.

Пусть дана матрица , некоторые элементы которой являются нулями, а другие произвольны. Обозначим через - совокупность всех строк, а через - совокупность всех столбцов. Множество рядов матрицы (т.е. множество ее строк и столбцов) называется опорным, если удаление этих рядов приводит к исчезновению из нее всех нулей. Если минимальное опорное множество состоит из строк и столбцов, то можно утверждать, что .

Минимальное число рядов в опорном множестве матрицы назовем индексом рассредоточения – .

В качестве примера рассмотрим матрицу .

М=
	0					
						
			0	0
	

Как , так и являются опорными множествами, причем меньше из них состоит из четырех рядов . Можно найти опорное множество, состоящее из еще меньшего числа рядов . Для матрицы оказывается и .

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

.

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

Максимальной связкой называют ту связку, которая содержит наибольшее число нулей. Это число называют индексом квадратности матрицы  .

Теорема Кёнига формулируется следующим образом:

,

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

Для поиска максимальной связки можно предложить следующий алгоритм:

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

2. Повторить пункт 1, пока существуют непомеченные нули.

Алгоритм поиска минимального опорного множества:

1. пометить звездочкой (*) все строки, которые не содержат ни одного обведенного квадратной рамкой нуля;

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

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

4. повторять пункты 2 и 3, пока не останется строк или столбцов, которые ещё можно пометить;

5. перечеркнуть каждую непомеченную строку и каждый помеченный столбец.

Алгоритм решения задачи о назначении.

1. В каждом столбце таблицы выберем наименьший элемент и вычтем его из всех элементов этого столбца.

.

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

1. В каждой строке таблицы выберем наименьший элемент и вычтем его из всех элементов этой строки:

.

1. Найти максимальную связку и определить индекс квадратности матрицы.

2. Если индекс квадратности , решение найдено

1. Найти минимальное опорное множество.

2. Из всех непрочеркнутых элементов выбрать наименьшее число.

3. Вычесть это число из всех непрочеркнутых элементов и прибавить его ко всем дважды прочеркнутым элементам.

4. Перейти к пункту 3.

Пример. Для неоднородной сети ЭВМ перераспределить вычислительные ресурсы, если известны потери, связанные с функционированием -го ресурса в -ом узле.