|
Обещанная комедия в 3-ч частях.
Часть 1: расписание для школ.
Как раз ко мне обратился студент, который написал программу для составления школьных расписаний. Только возникла у него одна проблемка – программа не может расставить все занятия. Т.е. не составляет расписание. Он спрашивал меня, в чем тут может быть дело. За условия задачи ручался головой (не своей – завуча) – они де все правильные и обязательно должны выполняться.
Я составил математическую модель задачи и попробовал составить расписание. Сразу же обнаружил противоречие в условиях. Все клятвы завуча оказались пустым звуком. У студента, видимо, был шок. Он верил завучу как себе, а она!
Но не этом дело. Подобная постановка задачи – насмешка над здравым смыслом. Если задача не имеет решения, это что значит? Школу закрываем? Если не закрываем, то что делать дальше? Перебирать отключение/включение ограничений по посинения и пытаться рассчитывать расписание каждый раз?
Все эти вопросы решаются довольно просто – каждое требование имеет свою «цену». Решение есть всегда – нужно максимизировать суммарный «цену» требований. Разумеется, выполнение учебного плана – самое ценное. Так как решение есть при «любых» требованиях, всегда можно получить расписание. Далее нужно анализировать само расписания и нарушенные требования. В подавляющем числе случаев этот анализ подсказывает, что делать дальше и РЕАЛЬНО позволяет получать очень хорошее расписание.
Я пытаюсь представить вашу организацию, у которой 10000 задач в день, чтобы в ней все было гладко. Вероятность того, что случится срыв сроков равна 1. Не бывает такого, чтобы сроки не срывались. Опаздывают самолеты, поезда, военные, милиция, скорая, педанты и т.д. Т.е. в вашей постановке задачи точно такие же проблемы, как и студента в составлении расписания.
Часть 2: расписание для ВУЗов
Пара студентов решила написать диплом на тему составления расписания для ВУЗов. Я им посоветовал для простоты не связываться с под/над чертой. Чтобы они могли что-либо продемонстрировать, я предложил им решать последовательно задачи распределения занятий по дням, а потом для каждого дня отдельно найти время проведения занятий. И использовать пакет линейной оптимизации для решения этих задач.
Эти балбесы создали одну огромную двухнедельную модель (вместо семи маленьких) для расписания на потоке. А потом меня спрашивают, а почему оптимизатор долго считает, а полученный результат плохой?
Хотелось ответить «да потому что слушать надо, что вам говорят». При распределении занятий по дням недели надо дополнительно включать условие устойчивости. Это в некоторой степени гарантирует в дальнейшем возможность получения хорошего расписания в течение каждого дня. При этом такой подход – задачи вполне решаемые, а результат практически оптимальный. Для получения двухнедельного расписания есть еще один трюк, но не суть.
Мораль сей басни такова – хотите получить решение низкого качества при огромных вычислительных затратах? Это очень просто! Составьте одну большую модель. Не много времени пройдет от воодушевленного энтузиазма до полного уныния. Весело было наблюдать, как менялся тон студенческих писем от «страстного желания создать вожделенную программу» до «быстрее отделаться от этой задачи и больше к ней никогда не возвращаться».
Если бить задачу на части - но это уже акт другой комедии...
Часть 3: расписание для производства.
Не буду утомлять деталями, но суть такова. Ситуация была примерно как с вашей задачей. Обратившемуся товарищу я сразу сказал – не сможешь составить адекватную, применимую в реальности модель. Говорю, пойдем к вашему руководству, заключим договор, и будем работать. «Вы быстро научитесь, я получу деньги, а предприятие – снижение издержек». Он выразился в том смысле, что надо сначала показать модель, пусть «медленную», - чтобы было доверие руководства. Я заподозрил неладное, и составил модель так, что она могла работать только на малых объемах данных. Товарищ решил, что я больше ему не нужен, и он сам дальше решит все вопросы. Как я понял, ему было важно доказать руководству, что он может решать задачи адской сложности. Ну, а я бы подпортил его имидж. На этом и расстались.
Примерно через года полтора на форуме линейного программирования вижу сообщение примерно такого содержания. «Сами мы не местные, но очень нужен БЕСПЛАТНЫЙ пакет оптимизации, которые быстро решает такую то задачу с суть астрономическим объемом данных. И далее следовала моя «подлая» постановка задачи...».
К гадалке ходить не нужно, чтобы догадаться, каков будет финал этой истории. Только убытки на зарплату этого товарища за время его деятельности составят несколько десятков тысяч долларов. И это не считая, сколько времени он отнял у остальных и сколько составят неоптимальных издержки компании.
На этом можно закрывать занавес. Хотите решить задачу сами – присылайте по завершении материал для четвертой части комедии... Хотя, можете позвать французов из бывшего ILOG, будет недорого. Думаю, на 1500 евро в день сторгуетесь.
P.S. Что-то никто не классифицирует, что описанная задача NP-полна. Что происходит?
|
где 
-- состояние, а 
-- управление.