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

Для некоторых задач удается найти гарантированно лучший ответ относительно быстро. Но для целого разряда так называемых NP-трудных задач, как, например, упомянутая выше задача об упаковке, сложно придумать метод, который работал бы намного быстрее, чем тривиальный полный перебор всех вариантов. Удастся ли когда-нибудь? Это открытый вопрос, но большинство ученых считают, что нет, потому что таких методов просто не существует. Многие практические задачи NP-трудные. В этом случае математики стремятся к быстрым и «почти» оптимальным решениям. А на практике приходится мириться с тем, что ответ достаточно хороший, но не всегда самый выгодный из возможных.

Разных методик для разных задач придумано множество. Мы расскажем о линейном программировании. Это мощная и уже ставшая классической теория, которая невероятно успешно применяется на практике.

Линейное программирование

Как возникают задачи линейного программирования, мы объясним на еще одном простом примере.

Допустим, у нас есть два склада: на северном и на южном конце города. В офис поступили заказы от двух клиентов. Клиент А заказал 60 листов железа, а клиент Б – 40 листов. На южном складе у нас в наличии 70 листов железа, а на северном – 35, то есть общего запаса хватает. Но мы хотим свести расходы на доставку к минимуму. Цены доставки приведены в табл. 2.1.

Таблица 2.1. Пример цен доставки

Спрашивается: сколько листов отправить клиентам А и Б с южного склада, а сколько – с северного?

Все было бы просто, если бы мы могли доставить весь товар с «дешевого» южного склада. Но, к сожалению, там всего 70 листов, на обоих клиентов не хватит. А поскольку северный склад гораздо дороже, решение не очевидно.

Как же его найти? В нашем конкретном примере, в принципе, можно пойти путем перебора всех вариантов. Но если количество клиентов и складов увеличится, решить задачу вручную не удастся. Поэтому давайте посмотрим, как это сделать с помощью математики. Для начала, как учили в средней школе, введем переменные.

Клиенту А с южного склада доставлено АЮ листов железа. Тогда с северного склада клиенту А доставлено (60 – АЮ) листов. Аналогично клиенту Б с южного склада доставлено БЮ листов железа, а с северного – (40 – БЮ) листов. Теперь по табл. 2.1 можно рассчитать общую стоимость доставки:

5 × АЮ + 7 × (60 − АЮ) + 10 × БЮ + 15 × (40 − БЮ) (рублей)

Если раскрыть скобки, то получается:

общая стоимость доставки = 1020 − 2 × АЮ − 5 × БЮ (рублей) (2.1)

Нам нужно выбрать АЮ и БЮ так, чтобы стоимость была как можно меньше.

Но это еще не все. АЮ и БЮ нельзя выбрать просто так. В задаче есть существенные ограничения. Во-первых, мы не будем отправлять клиентам больше листов, чем они просили. Клиент А заказал 60 листов, а клиент Б – 40 листов. Поэтому в любом случае

АЮ ≤ 60, (2.2)

БЮ ≤ 40. (2.3)

Во-вторых, нужно учесть, что запас на каждом складе ограниченный. С южного склада мы отправляем АЮ + БЮ листов, а всего на этом складе 70 листов. Поэтому АЮ + БЮ не больше 70:

АЮ + БЮ ≤ 70. (2.4)

Аналогично с северного склада мы не можем отправить больше 35 листов:

(40 – АЮ) + (60 – БЮ) ≤ 35.

Раскрыв скобки в этом выражении, получаем:

АЮ + БЮ ≥ 65. (2.5)

Это ограничение можно интерпретировать еще и так: поскольку на северном складе 35 листов, а нам в совокупности необходимо доставить 100 листов, то как минимум 65 листов должны быть доставлены с южного склада.

Вот теперь все! Это и есть задача линейного программирования: нам нужно минимизировать стоимость, которая задана выражением (2.1), и при этом соблюсти ограничения (2.2) (2.5). Внизу, во врезке, задача приведена в окончательном варианте.

Задача линейного программирования

Выбрать АЮ и БЮ так, чтобы минимизировать:

1020 − 2 × АЮ − 5 × БЮ,

при ограничениях:

0 ≤ АЮ ≤ 60,

0 ≤ БЮ ≤ 40,

АЮ + БЮ ≤ 70,

АЮ + БЮ ≥ 65.

Мы добавили, что АЮ и БЮ либо ноль, либо больше нуля, потому что доставить клиенту отрицательное количество листов железа невозможно.

Программирование в данном контексте скорее «оптимизация», а не программирование на компьютере. Слово линейное употребляется потому, что используются исключительно линейные выражения, то есть переменные можно умножать на число, а также вычитать и складывать. И все. Никакие другие операции не применяются. Например, у нас нет выражений типа АЮ × БЮ или АЮ². Оказывается, в такой линейной формулировке можно представить очень многие задачи оптимизации.

В практических задачах переменных и ограничений намного больше. При этом всегда есть только одно выражение, так называемая целевая функция, которую следует либо минимизировать (если речь идет о стоимости), либо максимизировать (если речь идет о доходе). В данном случае наша целевая функция – стоимость (2.1), и ее нужно минимизировать.

Теория для практики

Пионер и основатель теории линейного программирования – советский ученый Леонид Витальевич Канторович. Над подобными проблемами он работал в конце 1930-х годов. В 1940-м вышла его фундаментальная статья «Об одном эффективном методе решения некоторых классов экстремальных проблем»{2}. В ней Канторович заложил математические основы линейного программирования (правда, тогда оно еще так не называлось).

Канторович интересовался этими проблемами прежде всего из-за их практической ценности. В 1975 году он получил Нобелевскую премию «за вклад в теорию оптимального распределения ресурсов», которую разделил с американским экономистом-математиком голландского происхождения Тьяллингом Купмансом, тоже занимавшимся разработкой теории линейного программирования и ее приложениями в экономике.

Одна из классических знаменитых задач линейного программирования – задача о диете Стиглера, датируемая 1945 годом. Звучит она примерно так: какие из 77 продуктов должны входить в потребительскую корзину одного человека (скажем, мужчины среднего веса), чтобы он получил необходимую норму девяти питательных веществ (включая калории) и при этом стоимость продуктов была минимальной? Это очень важная задача в экономике, потому что ее решение определяет минимальную потребительскую стоимость полноценного питания.

В математической формулировке переменные – это количество каждого продукта. Содержание белков, жиров, витаминов, минералов в каждом продукте известно. Ограничения – это минимальное количество питательных веществ. А минимизировать надо общую стоимость продуктов, которая складывается из количества каждого продукта, помноженного на его цену.

Уже к концу 1950-х линейное программирование достаточно широко использовалось в нефтяной индустрии. Сегодня оно лежит в основе огромного класса задач оптимизации, включая задачи менеджмента и микроэкономики: планирование, логистика, составление расписаний. Задачи, где нужно минимизировать стоимость или максимизировать доход при заданных ограничениях.

От задачи к решению

Несмотря на простую формулировку, решить задачу линейного программирования вовсе не просто. Самая большая сложность заключается в ограничениях. Это видно даже на нашем маленьком примере. Понятно, что выгоднее всего доставить товар обоим клиентам с дешевого южного склада. Трудность в том, что это невозможно, потому что там всего 70 листов, а нам нужно 100.

Чем больше переменных и ограничений, тем сложнее задача. В классической задаче о диете 77 переменных и 9 ограничений, и она уже представляет собой серьезную проблему с точки зрения вычислений. Линейное программирование стало рядовым инструментом менеджмента и планирования только благодаря тому, что математики придумали для таких задач множество совершенно нетривиальных методов решения.

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

Симплекс-метод, сильно улучшенный и усиленный другими методами, по-прежнему остается неотъемлемой частью современного программного обеспечения.

Идея симплекс-метода

Подробности симплекс-метода выходят за рамки этой книги, но мы постараемся объяснить его суть на нашем маленьком примере.

Для начала давайте посмотрим, какие в принципе значения могут принимать переменные, чтобы не нарушить наших ограничений. Например, мы можем взять АЮ = 58, БЮ = 8. В этом случае получается решение, которое мы записали в виде табл. 2.2.

Таблица 2.2. Пример решения, где АЮ = 58, БЮ = 8

Ограничения выполнены, и оба клиента получили заказанное количество листов.

Но это не единственное решение. Например, мы могли отправить больше листов с дешевого южного склада клиенту А, скажем 60 листов, и 10 листов клиенту Б. Легко увидеть, что доставка клиенту А теперь обойдется в

5×60=300 руб.,

а доставка клиенту Б будет стоить

10×10+30×15=550 руб.

Тогда общая стоимость получается не 864, а 850 рублей, то есть немного меньше, чем указано в табл. 2.2.

Чтобы не выбирать наугад, нужно посмотреть на все возможные решения, которые удовлетворяют ограничениям. Мы их изобразили на рис. 2.1. По оси х мы откладываем АЮ, а по оси у – БЮ. Любая точка в заштрихованной области удовлетворяет ограничениям. В том числе точка (58,8), как в таблице выше.

Рис. 2.1. Решения, удовлетворяющие ограничениям

Примечание: любая точка в заштрихованной области удовлетворяет всем ограничениям. Точка (58,8) это решение из таблицы выше. Угловые точки (25,40), (30,40), (60,10) и (60,5) кандидаты на оптимальное решение (см. объяснение в тексте).

Ниже во врезке мы объясняем, как получилась заштрихованная область. Объяснения соответствуют уровню средней школы. При желании их можно пропустить.

Как получена заштрихованная область на рис. 2.1

Все значения АЮ и БЮ положительные.

Вертикальная прямая линия АЮ = 60 обеспечивает ограничение АЮ ≤ 60. Все возможные значения находятся либо на ней, либо слева от нее.

Аналогично горизонтальная прямая линия БЮ = 40 обеспечивает ограничение БЮ ≤ 40. Все возможные значения находятся либо на ней, либо под ней. Выражение штрихпунктирной прямой АЮ + БЮ = 70 можно переписать в более привычном виде:

БЮ = 70 − АЮ,

поэтому прямая идет под отрицательным углом 45°. Заметьте, что она пересекает ось х (в нашем случае ось АЮ), когда БЮ = 0 и, соответственно, АЮ = 70. Нам нужно, чтобы выполнялось неравенство АЮ + БЮ ≤ 70, то есть

БЮ ≤ 70 − АЮ.

Значения, удовлетворяющие этому неравенству, расположены на штрихпунктирной прямой или под ней.

Аналогично пунктирная прямая АЮ + БЮ = 65 обеспечивает ограничение АЮ + БЮ ≥ 65. Значения, которые удовлетворяют этому неравенству, находятся на этой прямой или над ней.

Заштрихованная область, включая границы, удовлетворяет всем ограничениям.

Важно отметить, что заштрихованная область – это четырехугольник с прямыми сторонами, поскольку все наши ограничения линейные, то есть их можно изобразить с помощью прямых линий. Данная область называется областью допустимых значений, потому что все значения в ней удовлетворяют всем ограничениям. Иначе говоря, любое решение из этой области физически возможно или допустимо.

Фундаментальное свойство задач линейного программирования заключается в том, что оптимальное решение обязательно находится в углах области допустимых значений. Это происходит потому, что наша стоимость тоже линейная. Когда мы движемся по прямой – горизонтальной, вертикальной или наклонной, – стоимость может либо только уменьшаться, либо только увеличиваться, пока мы не наткнемся на угол и идти дальше по той же прямой станет невозможно.

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

В нашем маленьком примере углов всего четыре: (25,40), (30,40), (60,10) и (60,5). Мы можем легко подставить значения и подсчитать, что самое лучшее решение в точке (30,40), то есть с южного склада нужно отправить 30 листов клиенту А и 40 листов клиенту Б. Оставшиеся 30 листов клиенту А следует отправить с северного склада. Результат приведен в табл. 2.3:

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

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

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

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

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

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

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

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

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

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