Цели использования


Линейное программирование используется для оптимизации решения (детерминистских — то есть имеющих точное решение) задач. За этой формулировкой скрывается удобный инструмент, с помощью которого компании решают целый ряд задач. Какие же задачи чаще всего решаются с его помощью? Определение «product mix» — набора выпускаемой продукции. Большинство производственных компаний могут производить целый набор продуктов. Однако каждый продукт требует различного количества исходных материалов и трудовых затрат. Разумеется, прибыль, генерируемая каждым продуктом, также отличается. Соответственно, менеджер такой компании должен принять решение о том, какие продукты производить, — с целью максимизировать прибыль или удовлетворить возможный спрос при минимальных расходах.

Производство. Например, в некоторых специальных печатных платах приходится проделывать сотни или тысячи отверстий, чтобы разместить все компоненты, которые должны быть на ней размещены. Чтобы изготовить такие платы, сверлильный станок с программным управлением нужно запрограммировать на сверление в первом заданном месте, затем передвинуть сверло к месту следующего отверстия и просверлить его. Так как отверстий много, процесс повторяется сотни и тысячи раз; поэтому производители

печатных плат существенно выиграют от определения порядка сверления, который минимизирует время позиционирования инструмента (вообще говоря, необходимо минимизировать общее время обработки; но мы считаем, что на скорость сверления мы повлиять не можем). Финансовое планирование. Например, вы хотите оптимизировать ваши вложения, перенося результаты, полученные в прошлом, на будущее. При этом возникает следующая задача: поскольку уровень вашего потенциального дохода связан с уровнем риска, вы, задавшись определенным уровнем риска, хотели бы получить максимально возможный при данном уровне риска доход.

2.2. Постановка задачи

Математическая постановка задачи выглядит следующим образом: Найти max {F (X1,X2,X3,..Xn)} при условиях: f1 (X1,X2,X3,..Xn) ≥ 0 f2 (X1,X2,X3,..Xn) ≥ 0 f3 (X1,X2,X3,..Xn) ≥ 0 . . . fn (X1,X2,X3,..Xn) ≥ 0, где X1…Xn — некие переменные (например, набор может быть таким: количество продукции по видам, расход материалов, трудовые затраты; то есть наш «ответ», вообще говоря, входит в число переменных), а F, f1…fn — функции от этих переменных. При этом функция F носит название целевой функции (например: прибыль, пройденное расстояние, ожидаемый доход и т.д.). Условие fk (X1,X2,X3,..Xn) ≥ 0 иногда называют ограничением; жесткие условия вида fk (X1,X2,X3,..Xn) = 0 мы рассматривать не будем — главным образом, ввиду того, что данные условия плохо воспринимаются надстройкой Excel «Поиск решения» (мы, однако, рассмотрим способ заставить Excel поверить в то, что он работает с «мягким» условием, заменяющим жесткое для наших целей). Понятно, что в такой постановке общность задачи не ограничена: так, например, для того чтобы найти min {F (X1,X2,X3,..Xn)}, нужно искать max {- F (X1,X2,X3,..Xn)}. Аналогичным образом мы можем поступить и с другими функциями, производя алгебраические действия, не изменяющие равенств.

Пример постановки задачи

Теперь сформулируем типичную задачу. Компания «Русские джакузи» производит и продает (разумеется, производство не может быть самоцелью — во всяком случае, в капиталистической экономике) два вида ванн-джакузи: Аква-Спа и Гидро-Люкс. Руководитель компании должен принять решение в отношении количества ванн, которые нужно произвести в следующем квартале. При этом производство устроено следующим образом: компания покупает отформованные пластиковые ванны у местного поставщика и добавляет насос, трубы и форсунки, чтобы превратить обычную ванну в джакузи. Поставщик может продать любое, сколь угодно большое количество ванн. Для экономии издержек, в обоих типах ванн используется один и тот же тип насоса. В следующем квартале поставщик насосов может поставить только 200 штук насосов требуемого типа. С точки зрения производства, главное отличие между джакузи заключается в количестве рабочего времени и длине используемых труб.

Количество рабочего времени достаточно жестко регулируется профсоюзом, поэтому максимальное число рабочих часов составит не более 1566. Еще одно ограничение накладывается поставщиком труб: он не может поставить более 2000 метров (плюс 880 метров есть на складе; в дальнейшем поставки возобновятся). Вся выпускаемая продукция находит своего покупателя. Менеджер уверен, что это продлится и в будущем. Вопрос: какое количество ванн Аква-Спа и Гидро-Люкс нужно произвести, чтобы максимизировать прибыль за период? (Обратите внимание: прямые затраты уже учтены в операционной прибыли, то есть нам нет нужды знать стоимость рабочего часа и метра трубы). Распишем порядок решения задачи подробно.

1. Понимаем задачу. В данном случае, задача достаточно очевидна. В большинстве ситуаций, с которыми вам придется столкнуться, само формулирование задачи —

во-первых, процесс непростой, а во-вторых — уже половина решения; что уж говорить о понимании.

2. Определяем переменные в решении. В нашем случае, такими переменными будут X1 и X2 — количество Аква-Спа и Гидро-Люкс соответственно.

3. Определяем целевую функцию. Поскольку мы назвали наши переменные X1 и X2, целевая функция будет выглядеть следующим образом:

i. F(X1,X2) = 350X1 + 300X2, а задача — найти max { F(X1,X2) = 350X1 + 300X2}.

4. Определяем налагаемые ограничения.

i. Ограничение по количеству насосов будет выглядеть следующим образом: X1 + X2 ≤ 200 Ограничение по количеству рабочих часов: 9X1 + 6X2 ≤ 1566 Ограничение по длине трубы: 12X1 + 16X2 ≤ 2880

5. Определяем (возможные) ограничения на решение. В частности, очевидно, что количество произведенных ванн должно быть положительно (для пытливых умов: отрицательное количество произведенных ванн значило бы, что вы покупаете готовые джакузи на рынке и разбираете их на составляющие с тем, чтобы использовать трубы и насос для производства продукции с наибольшей маржой).

i. X1 ≥ 0 X2 ≥ 0

ii. Такие условия обычно называют условиями «неотрицательности».

Решение задач линейного программирования в Excel

Как выглядит решение нашей задачи на графике? Каждое ограничение представляет собой прямую, отсекающую часть плоскости. Таким образом, область возможных решений ограничена снизу и слева осями OX и OY, а сверху — ломаной линией, образованной, в свою очередь, линиями, проведенными в соответствии с нашими ограничениями. См. рис. 7.

Итак, мы (графически) определили область возможных решений. Как поступить дальше? Если наша функция линейна (то есть содержит переменные только в первой степени — в частности, не содержит произведений переменных между собой), не сложно догадаться, что максимума она может достигать либо в одной из вершин, образованных пересечением линий ограничений, либо на одном из отрезков, образованных этими

32/42

вершинами (и тогда в любой точке отрезка достигается максимум). Таким образом, в нашем случае мы можем, не мудрствуя лукаво, перебрать все 5 вершин с тем, чтобы найти оптимальное решение.

Однако далеко не всегда мы сможем обойтись всего двумя переменными; здесь возникает та же проблема, что и во множественной регрессии, — нам все сложнее и сложнее будет представить область возможных решений; и даже поиск точек пересечения — если мы решим отказаться от графического построения таких областей — будет становиться все более непростой задачей. К счастью, нам на помощь, как всегда, придет Excel — с его надстройкой (add-in) «Поиск решения» (Solver — в англоязычном варианте). Комментарий: Надстройка «Поиск решения», хотя и входит в стандартный инсталляционный комплект, не устанавливается автоматически; для установки надстройки необходимо совершить следующие действия.

1. Выбрать пункт меню «Сервис» (Tools).

2. Выбрать подпункт «Надстройки» (Add-ins).

3. В появившемся списке отметить нужные надстройки (в ваших интересах установить, как минимум, «Поиск решения» — Solver).

Чтобы сократить таблицу, для подсчета в колонке «Итого» — во всех строках, кроме строки количество, где использовалась обычная сумма — мы воспользовались функцией СУММПРОИЗВ (в англоязычном варианте, соответственно, SUMPRODUCT). Эта функция вычисляет сумму попарных произведений двух векторов равной длины (скалярное произведение, если угодно). То есть, например, СУММПРОИЗВ(A1:A2;B1:B2) = A1×B1 + A2×B2. Таким образом, в строке «Маржа» в колонке «Итого» стоит сумма попарных произведений количества и маржи — а это и есть операционная прибыль, наша целевая функция. Теперь можно вызвать «Поиск решения», выбрав в меню «Сервис» пункт «Поиск решения». В появившемся окне диалога необходимо сделать следующее.

1. Указать целевую ячейку (в нашем случае — итоговая маржа).

2. В подстрочке «Равной» выбрать необходимый пункт (в нашем случае, разумеется, максимум).

3. В окошке «Изменяя ячейки» выбрать те ячейки, которые мы собираемся изменять (в нашем случае — количество джакузи разных видов).

4. В окошке «При условии» нажать «Добавить» и по одному ввести наши условия (объяснение см. выше):

X1 + X2 ≤ 200 9X1 + 6X2 ≤ 1566 12X1 + 16X2 ≤ 2880 Кроме того, не стоит забывать условия неотрицательности (X1 ≥ 0 и X2 ≥ 0) — мы же не хотим разбирать готовые джакузи на составные части.

Неограниченное решение. Например, если единственное существующее ограничение X1 ≤ 200, мы сможем сколь угодно далеко продвинуться вдоль оси X2. Невозможные (несовместные) условия. Например, X1 + X2 ≤ 200 и X1 + X2 ≥ 500. Очевидно, что возможные области лежат по разные стороны от полосы, разделяющей плоскость X1X2. Альтернативные решения. Как уже отмечалось, в случае, если оптимальное решение приходится не на вершину, а на ребро (а в многомерном случае — на часть плоскости или гиперплоскости), то мы вправе выбирать из множества решений. В этом случае разумно установить дополнительный критерий. Рекомендации

1. «Поиск решения» — отнюдь не идеальное средство. Если нет возможности приобрести альтернативы, относитесь к результатам с осторожностью, если не сказать — с предубеждением.

2. Не используйте жесткие равенства. Вместо X1=10 лучше использовать, например, такое ограничение: (X1 – 10)2 ≤ 0.5. Затем это ограничение можно (постепенно!) ужесточать.

3. Заметьте: в предыдущем случае был использован квадрат, а не модуль (абсолютная величина). Решая нелинейные задачи, вы сэкономите на этом массу времени — и себе, и компьютеру.

4. С особой осторожностью следует использовать ограничения типа ЦЕЛОЕ и ДВОИЧНОЕ. Эти ограничения существенно повышают порядок задачи — и, соответственно, увеличивают время расчета.

5. Если «Поиск решения» сообщает о том, что решение не найдено, первым делом проверьте ваши ограничения. Затем попробуйте поменять стартовые величины.

6. Даже если «Поиск решения» сообщает о том, что решение найдено, попробуйте «сдвинуть» решение. Шанс, что таким образом вы найдете лучшее решение, довольно велик.

7. Чтобы окончательно убедиться, что решение оптимально, можно воспользоваться методом Монте-Карло. Его-то мы и будем изучать в следующем разделе.



Категория: управление. Дата публикации: 1 Март, 2010.