|
Очень нуждаюсь в помощи сообщества. Преподаватель дал задачу (на 2 недели) под написание программы по формированию графика рабочих. N рабочих, M дней, несколько суточных рабочих периодов (с 7 утра, с 9 и т.д. квантованием по часу). Масса ограничений (не менее и не более определенного числа рабочих дней, не менее и не более активных рабочих, не более 3 дней работы подряд и еще десяток типов ограничений). Решил "в лоб" свести все к задаче BIP, т.е. воспользоваться линейным программированием, вести бинарные 0-1 переменные "вышел в данный период/не вышел" и прорешать в том же MatLab. Проблема в росте размерности (получается N*M*число_периодов переменных). Сначала использовал bintprog и генетические алгоритмы из MatLab. Дохлый номер, т.к. эти методы не расчитаны на такое количество переменных. Затем были по цепочке открытые и не очень проекты: LP_Solve (решает, но ОЧЕНЬ долго), GPLK (пришлось ставить Linux, т.к. WinGPLK отказывался работать), Symphony и, наконец, ломаный IBM CPLEX (сверхбыстрая штука). Последние два решают задачи более-менее быстро, но неспособны переварить ПОЛОВИНУ ограничений, так сказать, problem is infeasible, как ты ни играйся с настройками. А это неприемлимо. Почитал книжку Кристофидеса, свел частично задачу к поиску максимального потока минимальной стоимости на мультиграфе. Но, во-первых, неизвестно как добавить три типа ограничений (т.е. не то что неизвестно, а очень много дуг получается однако), во-вторых производительность еще хуже, если решать тем же MatLab. Кто знает похожие программы с исходниками, или алгоритмы, или темы, или учебники (подойдет на англ. или немецком)? В каком направлении копать? Стыдно было постить здесь такую задачу (учитывая, насколько серьезные вопросы здесь задаются), но уже несколько суток почти непрерывно сижу, не знаю что и делать. Вроде чуются еще какие-то способы решения, но единственно полный в плане описания задачи - в лоб с бинарными переменными. Очень прошу извинить, если не тот раздел, хотел запостить в разделе "Численные методы и оптимизация", но сижу с сотового и не могу половину форума открыть.
|
