3. Распределение машин (комплектов машин) по объектам строительства
3.1. При распределении машин по объектам строительства перед инженерно-техническими работниками может возникнуть несколько задач, которые имеют рациональные решения. Часто встречающейся задачей может быть распределение количества машин, равного количеству строящихся объектов по различным критериям (минимальные суммарные затраты, минимальное суммарное время на строительство всех объектов в течение года и другие показатели).
Для решения данной задачи наиболее приемлем Венгерский метод.
Пример решения задачи
Условие задачи. В строительной организации имеются пять башенных кранов : КБ-307А – 2 шт.; КБ-306 – 2 шт.; и КБ - 401Б ( А1 ÷ А5). В планируемом году принято к строительству 5 объектов (В1, В2, В3, В4, В5).
Время на монтаж каждого объекта соответствующим краном подсчитано при разработке проекта производства работ.
Необходимо расставить краны по объектам строительства так, чтобы суммарное время производства работ было минимальным. Исходные данные представлены в табл. 1.
Таблица 1
Марка кранов |
Затраты времени Сij работы кранов по объектам Bj, час. |
||||
В1
|
В2 |
В3 |
В4 |
В5 |
|
А1 - КБ – 307А |
80 |
70 |
90 |
100 |
60 |
А2 - КБ – 308 |
50 |
40 |
30 |
60 |
70 |
А3 - КБ – 401Б |
30 |
40 |
50 |
60 |
70 |
А4 - КБ – 307А |
80 |
70 |
90 |
100 |
60 |
А5 - КБ – 308 |
50 |
40 |
30 |
60 |
70 |
Решение
Критерий оптимизации: суммарное время монтажа 5-и объектов математически можно записать так:
min
. (14)
Задача решается при условии ограничения:
1) каждый кран работает на одном объекте;
;
2) на каждом объекте может работать 1 кран, т.е.
.
Алгоритм метода включает следующие этапы:
1. Получение нулей в каждой строке
Для этого в строке выбирается наименьшее значение времени и записывается в столбец di табл. 2.
Таблица 2
Марка машины |
Затраты времени на монтаж Сij по объектам Вj, час. |
di |
||||
В1 |
В2 |
В3 |
В4 |
В5 |
||
A1 |
80 |
70 |
90 |
100 |
60 |
60 |
А2 |
50 |
40 |
30 |
60 |
70 |
30 |
А3 |
30 |
40 |
50 |
60 |
70 |
30 |
А4 |
80 |
70 |
90 |
100 |
60 |
60 |
A5 |
50 |
40 |
30 |
60 |
70 |
30 |
di – минимальный элемент строки, вычисляется из всех элементов и получаем новую матрицу, табл. 3.
Таблица 3
Марка машины |
Затраты времени на монтаж Сij по объектам Bj, час. |
di |
||||
В1 |
В2 |
В3 |
В4 |
В5 |
||
A1 |
20 |
10 |
30 |
40 |
0 |
- |
А2 |
20 |
10 |
0 |
30 |
40 |
- |
А3 |
0 |
10 |
20 |
30 |
40 |
- |
А4 |
20 |
10 |
30 |
40 |
0 |
- |
A5 |
20 |
I0 |
0 |
30 |
40 |
- |
di |
0 |
10 |
0 |
30 |
0 |
- |
Аналогично выполняется операция для столбцов Bj, и получаем результаты, представленные в табл. 4.
Таблица 4
Машины |
Затраты времени на монтаж С ij по объектам Вj, час. |
||||
В1 |
В2 |
В3 |
В4 |
В5 |
|
КБ - 307А |
20 |
0* |
30 |
10 |
0X |
КБ - 308 |
20 |
0X |
0* |
0X |
40 |
КБ - 401Б |
0* |
0X |
20 |
0X |
40 |
КБ - 307А |
20 |
0X |
30 |
10 |
0* |
КБ - 308 |
20 |
0X |
0X |
0* |
40 |
В каждой строке и столбце есть 0 (нули).
2. Поиск оптимального решения
Рассматриваем одну из строк табл. 4 с наименьшим количеством нулей и отмечаем нуль звездочкой *, а остальные нули зачеркиваем в строке и столбце. Аналогично для всех строк. Получили пять звездочек по одной в каждой строке. Решение оптимально!
На 1-м объекте работать должен кран А3 КБ-401Б; на 2-м –A1 КБ-307А; на 3-м – A2 КБ - 308; на 4-м – А5 КБ - 308; на 5-м – A4 КБ - 307А.
Суммарное время на монтаж объектов:
ΣY= 70 + 30 + 30 + 60 + 60 = 250 ч.
Если назначения, которые получены при всех нулях отмеченных звездочкой, не являются полными (т.е. число нулей, отмеченных звездочкой, не соответствует количеству машин и объектов), то решение не является оптимальным. В таком случае следует переходить к следующему этапу.
3. Поиск минимального набора строк и столбцов, содержащих нули
Необходимо отметить звездочкой:
- все строки, в которых не имеется ни одного отмеченного звездочкой нуля;
- все столбцы, содержащие перечеркнутый нуль хотя бы в одной из отмеченных звездочкой строк;
- все строки, содержащие отмеченные звездочкой нули из отмеченных звездочкой столбцов.
Два последних действия повторяются поочередно до тех пор, пока есть что отмечать. После этого необходимо зачеркнуть каждую непомеченную строку и каждый помеченный столбец (цель – провести минимальное число горизонтальных и вертикальных прямых, зачеркивающих все нули).
4. Перестановка некоторых нулей
Выберем наименьшее число из тех клеток, через которые не проведены прямые, зачеркивающие все нули. Вычтем это число из каждого числа не вычеркнутых столбцов и прибавим к каждому числу вычеркнутых строк. Получим следующую таблицу.
Эта операция не изменяет оптимального решения, после чего весь цикл расчета начинается с этапа 2. и продолжается до получения оптимального решения.