Гроссмейстер еще не знает, что его идея уже известна под названием «линейного программирования» и что он получил очередной удар со стороны классиков. Он бодро продолжает:
«Допустим, что мы решим выпускать X гарнитуров „Мадам Петухова“ и Y гарнитуров „Генеральша Попова“. Поскольку на каждый гарнитур первого типа надо 10 кубометров древесины, а на каждый гарнитур второго типа — 5 кубометров, то всего нам понадобится 10 · X + 5 · Y.
Понятно, что это количество не должно превышать 110 кубометров. Запишем это так: 10x + 5y < 110.
Данное условие, совместно с другим естественным условием: x и у не могут быть отрицательными — на графике изображается в виде некоторой области (на приведенном справа рисунке она заштрихована). Наклонная граница представляет собой график линейной зависимости: 10x + 5y = 110. Неравенство в предыдущем выражении означает, что данному условию удовлетворяют все внутренние и граничные точки области. В этом легко убедиться. Точка с координатами x = 4, y = 8 удовлетворяет неравенству, так как 10 · 4 + 5 · 8 < 110. При подстановке координат любой внутренней или граничной точки неравенство будет справедливо.
Аналогичное соотношение можно составить по обивочным материалам: 40x + 80y < 800. Этому неравенству соответствует заштрихованная область на втором рисунке справа.
Поскольку оба неравенства должны выполняться одновременно — на каждый гарнитур необходимо и дерево, и обивочные материалы — обе области надо совместить. Это сделано на рисунке слева. Разберемся, что собой представляет область с двойной штриховкой.
Во-первых, вспомним, что каждая точка на графике — это план производства. Так, точка с координатами x = 4; y = 6 означает план, при котором будет произведено 4 гарнитура „Мадам Петухова“ и 6 гарнитуров „Генеральша Попова“.
Во-вторых, каждая точка в заштрихованной области первого рисунка — это план, который обеспечен древесиной, каждая точка в заштрихованной области второго рисунка — это план, который обеспечен обивкой. Таким образом, точки области третьего рисунка с двойной штриховкой — это планы производства, обеспеченные и древесиной и обивкой, то есть область допустимых планов. Из них необходимо выбрать оптимальный план, при котором прибыль будет максимальной. Величина прибыли выражается просто. Если выпустить x гарнитуров первого типа, получив по 400 рублей прибыли за каждый, и у гарнитуров второго типа, получив по 500 рублей прибыли за гарнитур, то всего будет получено 400x + 500у рублей прибыли.
Так вот — триумфально заключил великий комбинатор — величина прибыли достигает максимума в точке пересечения наклонных границ. На третьем рисунке она обозначена буквой О. Ее координаты легко вычислить, решив совместно уравнения этих прямых. Получим: x = 8, y = 6. Итак, оптимальный план выпуска: восемь „мадам“ и шесть „генеральш“. Прибыль составит 400 · 8 + 500 · 6 = 6200 руб. При этом мы используем и всю древесину, и все обивочные материалы. И никаких противоречий с уголовным кодексом!»
«Конгениально…» — прошептал экс-предводитель.
Выражаясь современным языком исследования операций, талантливый сын турецкого подданного для принятия решения о плане производства построил модель «линейного программирования». Неравенства, ограничивающие заштрихованные области на первых двух рисунках, называются ограничениями модели. Формула, выражающая прибыль, называется целевой функцией. А совокупность ограничений и целевой функции — это и есть модель «линейного программирования».
Задача «линейного программирования» («ЛП-задача», как говорят и пишут для сокращения) заключается в том, чтобы найти допустимый план, то есть план, удовлетворяющий ограничениям и который в то же время максимизирует значение целевой функции.
Для решения «ЛП-задачи» вовсе нет необходимости рисовать области допустимых решений и по ним искать точку оптимума. Разработанный стандартный метод, называемый симплексным алгоритмом, позволяет по записанной в специальном виде модели «линейного программирования» («ЛП-модели») отыскать оптимальное решение.
Симплексный алгоритм очень трудоемок, и решение сколь-нибудь значительных «ЛП-задач» возможно только на ЭВМ. В библиотеках стандартных программ современных вычислительных центров, как правило, есть и симплексный алгоритм. Поэтому решение управленческой задачи практически заканчивается после того, как модель построена и получена необходимая для решения информация. Дальше следует чисто техническая работа: вызов программы симплексного алгоритма и работа ее на ЭВМ.