Перестановка некоторых нулей.

Поиск минимального набора строк и столбцов, содержащих нули.

Поиск оптимального решения.

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

Аналогичные операции последовательно проводим для всех строк. Если назначения, которые получены при всех нулях, отмеченных звез­дочкой, являются полными (т.е. число нулей, отмеченных звездоч­кой, равно (n=4)) то решение является оптимальным. В нашем случае табл. 3 (n =3) следует переходить к следую­щему этапу.

Для этого необходимо отметить звездочкой:

- все строки, в которых не имеется ни одного отмеченного звездочкой
нуля, (смотри строка 4 таблицы 3.)

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

- все строки, содержащие отмеченные звездочкой нули, из отмеченных
звездочкой столбцов (см.строка 3 ).

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

Выберем наименьшее число из тех клеток, через которые не про­ведены прямые, зачеркивающие все нули. ( в табл. 3 это число - 2). Вычтем число 2 из каждого числа не вычеркнутых столбцов и при­бавим к каждому числу вычеркнутых строк. Получим табл. 4

Таблица 4

Машины А i	Затраты времени на монтаж С i j по объектам В j	аi
В1	В2	В3	В4
А1	0 *1
А2	0	0 *3		0
А3	0		0 *2	1
А4		0	0	0 *4
b j					-

Эта операция не изменяет оптимального решения, после чего весь цикл расчета начинается с этапа 2. и продолжается до получе­ния оптимального решения. В нашем случае число нулей, отмеченных звездочкой оказалось равным n =4, значит решение является полным и оптимальным. Клетки, отмеченные звездочками, указывают на объекты монтажа для каждого крана.

Суммарное время на монтаж объектов равно: У = 3 + 4 + 2 + 8 = 17

( минимальное значение таблицы 1).

Задача на дом.

Расставить пять комплектов машин по пяти объектам, так чтобы суммарные затраты на выполнение работ были минимальны! Матрица исходных данных

Ответ: у = 4 + 5 + 4 + 8 + 5 = 26.

Таблица 1.