Беседы об АСУ

Данное условие, совместно с другим естественным условием: 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 руб. При этом мы используем и всю древесину, и все обивочные материалы. И никаких противоречий с уголовным кодексом!»

«Конгениально…» — прошептал экс-предводитель.

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

Задача «линейного программирования» («ЛП-задача», как говорят и пишут для сокращения) заключается в том, чтобы найти допустимый план, то есть план, удовлетворяющий ограничениям и который в то же время максимизирует значение целевой функции.

Для решения «ЛП-задачи» вовсе нет необходимости рисовать области допустимых решений и по ним искать точку оптимума. Разработанный стандартный метод, называемый симплексным алгоритмом, позволяет по записанной в специальном виде модели «линейного программирования» («ЛП-модели») отыскать оптимальное решение.

Симплексный алгоритм очень трудоемок, и решение сколь-нибудь значительных «ЛП-задач» возможно только на ЭВМ. В библиотеках стандартных программ современных вычислительных центров, как правило, есть и симплексный алгоритм. Поэтому решение управленческой задачи практически заканчивается после того, как модель построена и получена необходимая для решения информация. Дальше следует чисто техническая работа: вызов программы симплексного алгоритма и работа ее на ЭВМ.

Широкая область применения «ЛП-модели» объясняется в первую очередь вычислительными удобствами. Но главная причина их распространенности кроется в другом: в них заложено решение широко распространенной задачи планирования — задачи о балансировке ресурсов. Возникает она вот почему.