Кому нужна математика? Понятная книга о том, как устроен цифровой мир - [8]

Таблица 2.3. Оптимальный план поставки листов железа

Общая стоимость – 760 рублей, что гораздо меньше, чем 864 рубля – наше первое, выбранное наобум решение. Выгода – 12 %, и это очень существенно, особенно если таких доставок много.

То, что решение нужно искать «по углам», сказано уже на первой странице работы Канторовича. Это понятно любому математику.

Если же ограничений много, то у нас получается уже не четырехугольник, а многоугольник. А если много переменных, у нас будет не многоугольник, а многогранник! Найти и перебрать все углы многогранника невероятно сложно, на это может уйти очень много времени.

Заслуга Данцига состоит в том, что он придумал способ, основанный на линейной алгебре, который позволяет перемещаться от одного угла многогранника к другому не наобум, а в определенном порядке, чтобы при переходе от одного угла к другому стоимость только уменьшалась. Это и есть знаменитый симплекс-метод, применяемый практически во всех приложениях. Доказано, что в самых худших случаях искать решение придется очень долго. Тем не менее на практике симплекс-метод в его современных вариантах быстро находит оптимальное решение.

Составление расписаний

В планировании часто приходится оперировать с целыми числами. Нельзя отправить на объект «два землекопа и две трети», как в стихотворении Маршака. В этом случае мы имеем дело с задачей целочисленного линейного программирования.

Такие задачи часто встречаются при составлении расписаний. Например, посмотрим на самый первый наш пример, в котором один прибор должен выполнить 25 заданий и нужно найти самую выгодную последовательность. Тогда мы можем ввести переменные х для каждой комбинации (задание, очередность выполнения). Если задание 3 выполняется самым первым, то мы пишем

x(задание 3, очередность 1) = 1.

А если этого не происходит, то

x(задание 3, очередность 1) = 0.

Каждая переменная в решении – это целое число: 0 или 1.

С помощью этих переменных можно записать стоимость любой последовательности и практически любые ограничения. Типичное строгое ограничение: прибор не может выполнять два задания одновременно. Но можно добавить ограничения и посложнее. Например, «задание 3 нужно (или желательно) выполнить раньше, чем задание 10»[3].

В реальности даже для составления относительно небольшого расписания имеет смысл воспользоваться математической моделью. Например, несколько лет назад студенты факультета прикладной математики Университета Твенте разработали модель для расписания ежегодного фестиваля хоров. Там несколько десятков хоров, несколько сцен, не каждый хор может петь на любой сцене, и у некоторых хоров один и тот же дирижер. Раньше организаторы бились над расписанием не один день. А компьютерная программа, которую написали студенты, выдавала решение буквально за несколько минут. Восхищенные певцы пришли в университет на презентацию проекта и спели студентам благодарственную арию!

Почему целые числа сложнее дробных

Потребность в целочисленном решении кардинально усложняет задачу. Симплекс-метод не даст готового решения, потому что координаты углов многогранника вовсе не обязаны быть целыми и обычно целыми не будут. Целочисленное линейное программирование относится к разряду NP-трудных задач.

Классический подход к решению называется методом ветвей и границ. Он основан на «разветвлении» дробных решений на допустимые целочисленные и исключении неперспективных «веток»[4].

Для практического применения наивное использование метода ветвей и границ абсолютно не годится. Математики дополнили его многими другими методами. Например, сейчас на практике широко применяется метод «отсекающих плоскостей» (алгоритм Гомори), позволяющий эффективно отсекать дробные значения.

За относительно недолгий срок своего существования эта область математики достигла невероятного прогресса.

Математика, обогнавшая компьютер

Американский ученый Роберт Биксби написал целую серию статей об истории линейного программирования. В нашем рассказе мы воспользовались его статьей 2012 года{3}.

По словам Биксби, после нескольких усовершенствований симплекс-метода к 1953 году удалось решить вариант знаменитой задачи о диете с 71 переменной и 26 ограничениями.

Аппарат, на котором производились вычисления, не был компьютером в строгом смысле этого слова. Это был огромный численный прибор, программируемый с помощью перфокарт. Решение заняло 8 часов, большая часть которых ушла на то, чтобы вручную вставлять перфокарты в машину. Настойчивости и терпению ученых остается только удивляться.

Сегодня для решения задач линейного программирования на практике в основном используется коммерческое программное обеспечение. Среди самых известных пакетов – CPLEX и более недавний Gurobi.

В компьютерных технологиях действует одно эмпирическое правило, часто называемое законом Мура, согласно которому мощность процессоров удваивается каждые 18 месяцев. И хотя это не закон природы и Мур (один из основателей Intel) говорил не совсем об этом, все же данное утверждение примерно соответствует действительности.

Абсолютно очевидно, что любой алгоритм на современном компьютере будет работать гораздо быстрее, чем на давно устаревшей махине с перфокартами. Но и математика не стоит на месте. Старые алгоритмы совершенствуются, появляются новые. Как оценить роль математики в успехе коммерческих пакетов?