Беседы об АСУ - [32]

Чтобы от слов о «линейном программировании» перейти к нему самому, стоит рассмотреть такой пример планирования.

Пусть руководство уже упоминавшейся фирмы по выпуску мебели «Двенадцать стульев» решает проблему, какую мебель выпускать в следующем месяце. Фирма, как известно, умеет делать гарнитуры «Мадам Петухова» и «Генеральша Попова». Каждый вид продукции характеризуется, во-первых, затратами высококачественных пород древесины и импортных обивочных материалов, а во-вторых, размерами получаемой прибыли. Естественно, что ресурсы фирмы, дерево и материалы ограничены. Необходимо составить план производства, при котором прибыль была бы максимальна.

Итак, правление фирмы сидит перед таблицей, в которую сведены все данные, и думает, как лучше решить эту задачу.

Табл. 13.

Заместитель председателя правления фирмы И. Воробьянинов берет слово:

«Учитывая, что за „генеральшу“ платят больше, — говорит он, — считаю, что необходимо выпускать названный гарнитур в количестве 10 штук, а оставшиеся неиспользованными 60 кубометров древесины продать налево дружественной фирме „Милости просим“. Тем самым мы получим 5 тысяч рублей прибыли плюс…»

«Не надо, Киса, — жестом останавливает его председатель правления О. Бендер, — сегодня ночью мне пришла в голову плодотворная дебютная идея. Сейчас я вам ее изложу…»

Гроссмейстер еще не знает, что его идея уже известна под названием «линейного программирования» и что он получил очередной удар со стороны классиков. Он бодро продолжает:

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

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

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

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

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