Все было бы просто, если бы мы могли доставить весь товар с «дешевого» южного склада. Но, к сожалению, там всего 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 продуктов должны входить в потребительскую корзину одного человека (скажем, мужчины среднего веса), чтобы он получил необходимую норму девяти питательных веществ (включая калории) и при этом стоимость продуктов была минимальной? Это очень важная задача в экономике, потому что ее решение определяет минимальную потребительскую стоимость полноценного питания.
2
Канторович Л. В. Об одном эффективном методе решения некоторых классов экстремальных проблем // Докл. АН СССР. 1940. Том 28. С. 212–215.