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

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

Исходная матрица

45	14	40	53	38	57
51	48	81	35	43	37
8	60	44	39	13	94
34	99	62	6	75	12
87	23	32	72	19	5
18	33	52	89	77	10

 

Шаг 1. В матрице стоимостей в каждой строке определим минимальную стоимость.

						min
45	14	40	53	38	57	14
51	48	81	35	43	37	35
8	60	44	39	13	94	8
34	99	62	6	75	12	6
87	23	32	72	19	5	5
18	33	52	89	77	10	10

 

Отнимем минимальную стоимость от всех элементов соответствующей строки. Получим новую матрицу.

31	0	26	39	24	43
16	13	46	0	8	2
0	52	36	31	5	86
28	92	56	0	69	6
82	18	27	67	14	0
8	23	42	79	67	0

 

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

	31	0	26	39	24	43
	16	13	46	0	8	2
	0	52	36	31	5	86
	28	92	56	0	69	6
	82	18	27	67	14	0
	8	23	42	79	67	0
min	0	0	26	0	5	0

 

Отнимем минимальный элемент от всех элементов соответствующего столбца. Получим новую матрицу.

31	0	0	39	19	43
16	13	20	0	3	2
0	52	10	31	0	86
28	92	30	0	64	6
82	18	1	67	9	0
8	23	16	79	62	0

 

Шаг 3. Проверка допустимых решений.

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

31	0	0	39	19	43
16	13	20	0	3	2
0	52	10	31	0	86
28	92	30	0	64	6
82	18	1	67	9	0
8	23	16	79	62	0

 

Так как у меня решение не допустимо, то мне необходимо выполнить шаг 4.

Шаг 4. Если решение не допустимо.

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

31	0	0	39	19	43
16	13	20	0	3	2
0	52	10	31	0	86
28	92	30	0	64	6
82	18	1	67	9	0
8	23	16	79	62	0

 

 Шаг 4.2.  Из не вычеркнутых элементов находим минимальное  его значение вычитаем из не вычеркнутых элементов и прибавляем к элементам стоящим на пересечении проведенных прямых. Получаем новую матрицу.

 

31	0	0	40	19	44
15	12	19	0	2	2
0	52	10	32	0	87
27	91	29	0	36	6
81	17	0	67	8	0
7	22	15	79	61	0

 

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

31	0	0	40	19	44
15	12	19	0	2	2
0	52	10	32	0	87
27	91	29	0	36	6
81	17	0	67	8	0
7	22	15	79	61	0

 

Матрица, в которой есть допустимое и оптимальное решение.

31	0	2	42	19	46
13	10	19	0	0	2
0	52	12	34	0	89
25	89	29	0	61	6
79	15	0	67	6	0
5	20	15	79	59	0

 

А теперь смотрим на назначения и  в исходные данные и находим суммарное время.

F=14+8+32+6+43+10=113