Заслуга Данцига состоит в том, что он придумал способ, основанный на линейной алгебре, который позволяет перемещаться от одного угла многогранника к другому не наобум, а в определенном порядке, чтобы при переходе от одного угла к другому стоимость только уменьшалась. Это и есть знаменитый симплекс-метод, применяемый практически во всех приложениях. Доказано, что в самых худших случаях искать решение придется очень долго. Тем не менее на практике симплекс-метод в его современных вариантах быстро находит оптимальное решение.
В планировании часто приходится оперировать с целыми числами. Нельзя отправить на объект «два землекопа и две трети», как в стихотворении Маршака. В этом случае мы имеем дело с задачей целочисленного линейного программирования.
Такие задачи часто встречаются при составлении расписаний. Например, посмотрим на самый первый наш пример, в котором один прибор должен выполнить 25 заданий и нужно найти самую выгодную последовательность. Тогда мы можем ввести переменные х для каждой комбинации (задание, очередность выполнения). Если задание 3 выполняется самым первым, то мы пишем
x(задание 3, очередность 1) = 1.
А если этого не происходит, то
x(задание 3, очередность 1) = 0.
Каждая переменная в решении – это целое число: 0 или 1.
С помощью этих переменных можно записать стоимость любой последовательности и практически любые ограничения. Типичное строгое ограничение: прибор не может выполнять два задания одновременно. Но можно добавить ограничения и посложнее. Например, «задание 3 нужно (или желательно) выполнить раньше, чем задание 10»[3].
В реальности даже для составления относительно небольшого расписания имеет смысл воспользоваться математической моделью. Например, несколько лет назад студенты факультета прикладной математики Университета Твенте разработали модель для расписания ежегодного фестиваля хоров. Там несколько десятков хоров, несколько сцен, не каждый хор может петь на любой сцене, и у некоторых хоров один и тот же дирижер. Раньше организаторы бились над расписанием не один день. А компьютерная программа, которую написали студенты, выдавала решение буквально за несколько минут. Восхищенные певцы пришли в университет на презентацию проекта и спели студентам благодарственную арию!
Почему целые числа сложнее дробных
Потребность в целочисленном решении кардинально усложняет задачу. Симплекс-метод не даст готового решения, потому что координаты углов многогранника вовсе не обязаны быть целыми и обычно целыми не будут. Целочисленное линейное программирование относится к разряду NP-трудных задач.