GRNTI 67.01 Общие вопросы строительства
BBK 38 Строительство
This article describes of use of the operations research for modeling of building crew optimization in civil engineering. The optimization of the crew is determined from the condition of the highest possible quality of the construction works, which is determined by the qualifications and skills of the workers. The problem of finding the optimal composition of the crew is posed in the form of a linear programming problem. To solve the problem, a simplex algorithm is used in combination with the branch and boundary method to obtain an integer solution
quality of the construction works, crew, worker, linear programming, simplex algorithm, branch and boundary method
Введение. На сегодняшний день качество строительно-монтажных и отделочных работ является одним из факторов влияющих на стоимость производства работ. Чем выше требование к качеству строительства, тем выше себестоимость работ. Поэтому в условиях рыночной конкуренции производитель работ стремиться получить большую прибыль за счет оптимизации качества строительства. Одним из способов решения данной проблемы является использование математических методов моделирования.
Основная часть. В большинстве случаев при назначение рабочих на определенные виды строительно-монтажных и отделочных работ выполняется инженерами-проектировщиками в основном «в ручную» исходя из своих профессиональных навыков и опыта. Однако этот подход к решению данной задачи в условиях строительства крупных объектов становиться неуместным, так как проектировщикам приходится иметь дело с анализом больших объемов данных, которые необходимо учитывать для принятия наилучшего решения.
В самом деле, при увеличении количества однотипных видов работ увеличивается количество вариантов назначения рабочих на эти работы, которое в определенный момент достигает такого количества, когда проектировщики не могут решить задачу корректно, с точки зрения оптимального решения с учетом максимизации качества выполнения работ. Решением данной проблемы является автоматизация назначения рабочих на строительные работы с помощью ЭВМ.
Главной целью автоматизации назначения рабочих является помощь проектировщику при назначении рабочих с учетом наилучшего решения. Автоматизации позволит более качественно выполнить анализ данных, сократить время для выполнения решения задачи о назначении, учесть требования к квалификации (разряд рабочего, стаж работы, опыт работы и др.) рабочих при формировании на отельные виды работ.
Автору известны исследования о назначении оптимальных составов рабочих групп в таких отраслях как железнодорожные и авиаперевозки [1–4].
Составим математическую модель задачи оптимального назначения рабочих в звенья на строительные работы. Пусть необходимо составить звенья на строительно-монтажные работы с определенным количеством рабочих, так чтобы качество работ на объекте было максимально возможным. Работы звеньями выполняются последовательно.
Постановка задачи:
1) в штате строительной организации N типов рабочих – членов звеньев, назначаемых на отдельные виды работ;
2) имеется ni рабочих i-го типа, (рабочие различных разрядов (2-5)), так что каждый конкретный рабочий определяется парой (i,j), где i – тип рабочего, j – порядковый номер рабочего среди рабочих i-го типа, ;
3) qij – квалификация рабочего (i,j) (сюда входят опыт работы, умения рабочего др.), может принимать значение из отрезка [0,1];
4) учет квалификации должен зависеть от разряда рабочего, поэтому вводится вес ai, с которым учитывается квалификация i-го типа рабочего (ai может принимать только натуральные значения), так что квалификация рабочего (i,j), которой оперирует проектировщик, вычисляется по формуле aiqij, , ;
5) количество звеньев k задается равным M, таким образом, .
6) в звено под номером k необходимо назначить рабочих i-го типа; двоичная переменная принимает значение 1, если рабочий (i,j) назначен в звено k, и принимает значение 0 в противном случае, таким образом, в постановке задачи присутствует ограничение:
7) некоторые рабочие могут быть закреплены за какими-либо видом работ по желанию проектировщика; некоторым рабочим может быть запрещено работать на каком-либо виде работ по желанию проектировщика, т.е. в постановке задачи возможны ограничения вида для некоторых наборов i,j,k и ограничение вида для некоторых для некоторых наборов i,j,k;
8) должна быть предусмотрена возможность некоторых рабочих в обязательном порядке работать вместе в каком-либо звене, т.е. возможны ограничения вида:
для некоторых значений k и некоторых пар (i1,j1), (i2,j2).
Абсолютное качество k-ого звена, определяется выражением:
Максимальное качество k-ого звена, которое возможно достичь, задается формулой:
(4)
Поскольку численность звеньев может быть разная, для сравнения качества звеньев нужно использовать не абсолютное, а относительное качество, которое для k-ого звена определяется соотношением:
(5)
Цель – сформировать составы звенья так, чтобы обеспечить по возможности максимальное качество всех звеньев. То есть необходимо рассмотреть следующую целевую функцию:
(6)
Поставленная выше задача оптимального назначения составов рабочих звеньев в описанной постановке является задачей линейного программирования.
Некоторые виды задач линейного программирования применяются при планировании и организации строительного производства [5]. А именно транспортная задача, задача оптимального размещения строительной базы, распределительная задача и другие.
Рассмотрим пример задачи линейного программирования для назначения составов рабочих звеньев в вышеописанной постановке.
Пусть N=3 (три типа (5,3,2 разряды) рабочих), n1=4 (в первом типе 4 рабочих), n2=6, n3=8 (во втором и третьем типе 6 и 8 рабочих соответственно). Необходимо назначить составы для трех звеньев (k=3) с учетом максимизации качества работ.
Векторы квалификации для рабочих следующие:
– вектор квалификации для рабочих 5 разряда;
– вектор квалификации для рабочих 3 разряда;
– вектор квалификации для рабочих 2 разряда.
Таким образом, матрица квалификаций выглядит следующим образом:
Весовой вектор квалификаций: a = [3 2 1]
Вектор ограничений выглядит следующим образом:
Целевая функция определяется по формуле (6). С учетом заранее вычисленных коэффициентов при неизвестных переменных (показаны первые и последние три членов) функция выглядит следующим образом:
Система ограничений из пункта 6 постановки задачи (формула (1)):
Система ограничений из пункта 7 постановки задачи:
(2-й рабочий 1-го типа не может быть назначен в 1-е звено);
(2-й рабочий 1-го типа обязан быть назначен в 2-е звено);
(4-й рабочий 2-го типа не может быть назначен в 1-е звено);
(3-й рабочий 3-го типа не может быть назначен в 3-е звено).
Система ограничений из пункта 8 постановки задачи (формула (2)):
(2-й и 4-й рабочие 2-го типа обязаны быть назначены во 2-е звено);
(1-й и 5-й рабочие 2-го типа обязаны быть назначены во 3-е звено).
Требование целочисленности:
Z
Для решения данной задачи использовался симплекс-метод в совокупности с методом ветвей и границ для получения целочисленных решений [6, 7].
Симплекс-метод является общим методом решения оптимизационных задач линейного программирования. Процесс решения симплекс-методом имеет итерационный характер. Суть симплекс-метода состоит в переходе от одной угловой точки (одного базиса) многогранника допустимых решений к другой (другому базису) с целью оптимизации целевой функции. Целевая функция соответствует гиперплоскости (в заданном базисе), которая проходит через угловую точку. Оценки оптимальности соответствуют отклонениям относительно гиперплоскости. Когда все оценки оптимальности положительны, тогда целевая функция достигает максимума.
Метод ветвей и границ – один из наиболее эффективных методов решения различных задач комбинаторного типа, алгоритмы решений которых заключаются не в полном, а частичном переборе вариантов, в организованном поиске оптимума. Суть метода заключается в разбиении множества допустимых решений на подмножества, для каждого из которых определенным образом может быть установлена оценка (граница) достижения экстремума. Поиск решения продолжается каждый раз в том подмножестве (по той ветке), в котором потенциально может лежать лучшее решение. Как только, полученное допустимое целочисленное решение одной из подзадач оказывается лучше имеющегося, оно фиксируется вместо зафиксированного ранее (происходит изменение границы задачи). Процесс ветвления продолжается до тех пор, пока каждая из подзадача не приведет к целочисленному решению или пока не будет установлена невозможность улучшения имеющегося решения.
На языке математического пакета Matlab была написана реализации симплекс-метода и метода ветвей и границ для решения задачи о назначении состава рабочих звеньев методом линейного программирования. В результате решения были получены составы звеньев с учетом ограничений указанных примере. Составы рабочих звеньев приведены в таблице 1.
Таблица 1
Составы рабочих звеньев
|
Тип рабочего |
Номер (j) рабочего из квалификационного вектора |
||
|---|---|---|---|
|
Номер звена |
|||
|
1 |
2 |
3 |
|
|
рабочий 5 разряда |
1 |
2 |
1 |
|
рабочий 3 разряда |
1 |
2 |
1 |
|
рабочий 3 разряда |
2 |
4 |
5 |
|
рабочий 2 разряда |
3 |
3 |
4 |
|
рабочий 2 разряда |
4 |
4 |
5 |
Заключение. Поставлена математическая задача для назначения состава рабочих звеньев при выполнении строительно-монтажных или отделочных работ. Данная постановка задачи является задачей линейного программирования. Задача решалась симплекс-методом в совокупности с методом ветвей и границ для получения целочисленного решения. В результате решения задачи были найдены оптимальные составы рабочих звеньев с точки зрения максимального показателя качества работ. Данная постановка задачи может найти практическое применение при планировании и организации строительного производства.
1. Caprara A., Fischetti M., Toth P., Vigo D., Guida P. Algorithms for railway crew man-agement// Mathematical Programming. October 1997. Volume 79. Issue 1. P. 125–141.
2. Suyabatmaz A., Sahin G. Railway crew capacity planning problem with connectivity of schedules // Transportation research. Part E. 2015. Volume 84. P.88-100.
3. Klabjan D., Johnson E., Nemhauser G., Gelman E., Ramaswamy S. Solving large airline crew scheduling problems: random pairing gen-eration and strong branching // Computational Optimization and Applications. October 2001. Volume 20. Issue 1. P. 73–91.
4. Hoffman K., Padberg M. Solving airline crew scheduling problems by branch-and-cut // Management Science. June 1993. Volume 39. Issue 6. P. 657–682.
5. Syrcova E.D. Matematicheskie metody v planirovanii i upravlenii stroitel'nym proizvodstvom. Uchebnoe posobie. M., «Vys-shaya shkola», 1972. 336 s.
6. Volkov I.K., Zagoruyko E.A. Issledo-vanie operaciy. Uchebnik dlya vuzov. Pod red. B.C. Zarubina, A.P. Krischenko. M.: Izd-vo MGTU im. N.E. Baumana, 2000. 436 s.
7. Ventcel' E.S. Issledovanie operaciy: zadachi, principy, metodologiya. 2-e izd., ster. M.: Nauka. Gl. red. fiz. mat. lit., 1998. 208 s.
