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

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