1. Суть линейного программирования: как математика описывает поиск оптимальных решений в условиях ограничений
Суть линейного программирования: как математика описывает поиск оптимальных решений в условиях ограничений
Представьте, что вы управляете небольшой столярной мастерской. У вас на складе лежит 30 досок, а в неделю вы и ваши мастера готовы работать не более 40 часов. Вы делаете два вида товаров: массивные обеденные столы и изящные стулья. За каждый проданный стол вы получаете 3000 руб. чистой прибыли, а за стул — 1000 руб. Казалось бы, нужно делать только столы, ведь они приносят больше денег. Но на один стол уходит 2 доски и целых 4 часа кропотливой работы, тогда как на стул — всего 1 доска и 1 час времени. Если делать только столы, у вас быстро закончится время, а доски останутся лежать на складе. Если делать только стулья — закончится дерево, а мастера будут простаивать. Как найти ту самую идеальную комбинацию столов и стульев, которая принесет максимум денег при имеющихся ресурсах?
Именно на этот вопрос и отвечает линейное программирование. Это не написание кода на Python или C++. Слово «программирование» здесь используется в своем историческом значении — составление программы (плана) действий.
Линейное программирование — это математический метод поиска наилучшего (оптимального) способа распределить ограниченные ресурсы для достижения конкретной цели.
Чтобы решить нашу задачу со столами и стульями, нам нужно перевести ее с языка бизнеса на язык математики. Этот процесс называется математическим моделированием.
Три кита математической модели
Любая задача линейного программирования состоит из трех обязательных элементов, которые вытекают друг из друга.
1. Переменные решения (что мы ищем?) Это то, чем мы можем управлять. В нашем случае мы решаем, сколько произвести столов и стульев. Обозначим их математически: Пусть — количество произведенных столов. Пусть — количество произведенных стульев.
2. Целевая функция (какова наша цель?) Это математическое выражение того, что мы хотим максимизировать (прибыль, выручку, пропускную способность) или минимизировать (затраты, время, отходы). Мы знаем, что стол приносит 3000 руб., а стул 1000 руб. Значит, наша общая прибыль будет складываться из прибыли за столы и прибыли за стулья. Мы записываем это так:
3. Ограничения (что нас сдерживает?) Мы не можем произвести бесконечное количество мебели. У нас есть лимиты по ресурсам.
!Структура математической модели
Объединив эти элементы, мы получаем готовую математическую модель нашей бизнес-задачи. Теперь это не абстрактные рассуждения о том, «что выгоднее», а строгая система уравнений и неравенств.
!Отличие целевой функции от ограничений
Почему программирование «линейное»?
Слово «линейное» — ключевое ограничение метода. Оно означает, что все зависимости в нашей модели описываются только прямыми линиями. Математически это выражается в двух свойствах:
В формулах линейность означает, что переменные и могут умножаться только на числа. В линейном программировании категорически запрещены квадраты (), корни (), перемножение переменных между собой () или тригонометрия ().
> Линейность — это плата за простоту и скорость вычислений. Реальный мир часто бывает нелинейным, но линейные модели позволяют с огромной точностью аппроксимировать большинство экономических и производственных процессов.
От фабрики до Нобелевской премии
Может показаться, что мы составили простую школьную задачку. Но представьте, что у вас не мастерская, а национальная сеть заводов. У вас 5000 видов продукции, 10000 видов сырья, сложная логистика и сотни ограничений. Составить уравнения для такой системы — полдела. Главный вопрос: как найти те самые значения , которые дадут максимальную прибыль? Перебрать все варианты не сможет ни один суперкомпьютер в мире.
Именно эту проблему в 1939 году решил советский математик Леонид Канторович.
Ему поручили задачу фанерного треста: как распределить работу между станками, чтобы максимизировать выпуск продукции. Канторович не просто решил конкретную задачу, он разработал универсальный математический аппарат, который позже стал известен как линейное программирование. За этот вклад в 1975 году он получил Нобелевскую премию по экономике — единственный случай в истории советской и российской науки.
Наш пример со столами и стульями — это крошечная копия задач, которые ежедневно решают авиакомпании (составляя расписание экипажей), логистические центры (прокладывая маршруты доставки) и инвестиционные фонды (собирая портфель акций с минимальным риском).
Мы научились переводить реальную проблему на язык алгебры. У нас есть система:
,
Но как из этих формул извлечь ответ? Прежде чем мы перейдем к сухим алгоритмам и таблицам, нам нужно увидеть эту задачу. В следующей главе мы возьмем эти уравнения, нарисуем их на графике и своими глазами посмотрим, где именно прячется та самая точка максимальной прибыли и почему она находится именно там.