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

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

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

Для этого необходимо рассмотреть сначала одну из строк, имеющую наименьшее число нулей табл. 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.

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

Дата добавления: 2014-01-05