Ограничения

Первым этапом формализации модели линейного программирования (ЛП) должно стать выявление ограничений на переменные решения. Ограничения сужают множество допустимых решений. Приведем конкретные примеры ограничений, возникающие в за­дачах управления.

1. Менеджер по инвестициям имеет в своем распоряжении определенный капитал. Инвестиционные решения ограничены суммой данного капитала и распоряжения­ми таких правительственных органов, как Комиссия по ценным бумагам и биржам.

2. Решения директора завода ограничены производственной мощностью завода и имею­щимися ресурсами.

3. Планы полетов авиакомпании ограничены необходимостью обслуживания само­летов и числом сотрудников.

4. Решение нефтяной компании использовать определенный тип нефти для производства бензина диктуется характеристиками бензина, пользующегося спросом на рынке.

В моделировании ограничения на допустимые значения переменных решения явля­ются очень важным понятием. Ограничения в реальных управленческих моделях выра­жаются в числовом виде, но в своей основе имеют физическую, экономическую или даже политическую природу.

Целевая функция

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

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

Модели линейного программирования являются примером более широкого класса моделей — моделей принятия решений при наличии ограничений, которые также назы­ваются моделями условной оптимизации. Эти модели можно охарактеризовать следующим образом. Модель условной оптимизации призвана так распределить ограниченные ресурсы, чтобы оптимизировать целевую функцию.

В этом определении под "ограниченными ресурсами" подразумеваются ресурс, на которые распространяются ограничения.

Хотя существуют модели принятия решений при наличии ограничений более общего вида, во многих приложениях наиболее полезными являются модели линейного про­граммирования. Эти модели успешно применялись для решения тысяч различных задач принятия решений, поэтому мы уделяем данной теме значительное внимание.

Данные для модели

При принятии решения в данной модели необходимо учитывать следующие факторы.

1. Стулья, произведенные компанией Oak Product, продаются на той же неделе, удельная валовая прибыль (доход минус расход) составляет S56 для каждого проданного стула мирки Captain и $40 для каждого стула марки Mate.

2. Для сборки стула нужны длинные штифты, короткие штифты и одно из двух типов сидений, которые имеются на складе в ограниченном количестве.

3. Запас длинных и коротких штифтов, которые можно будет использовать на сле­дующей неделе, составляет 1280 и 1600 штук соответственно. Для производства одного стула марки Captain требуется 8 длинных и 4 коротких штифта, а для про­изводства стула Mate — 4 длинных и 12 коротких штифтов (табл. 1).

3. Запас ножек на следующую неделю составляет 760 штук. Для производства одного стула любого типа требуется 4 ножки (табл. 2).

4. Запас прочных и облегченных сидений составляет 140 и 120 штук соответственно (табл. 3). Для производства стульев Captain используются прочные сиденья, а для Mate — облегченные.

5. Согласно договору между руководством компании и профсоюзом общее число произведенных стульев не может быть менее 100.

Задача состоит в том, чтобы в данных условиях определить, сколько стульев каждой марки необходимо произвести на следующей неделе. Используя терминологию моделирования, он должен найти оптимальный ассортимент продуктов, или составить оптимальный план производства. Покажем, как данную ситуацию можно представить в виде задачи линейного программирования, а затем — в виде оптимизационной модели Excel. Для этого необходимо определить ограничения и целевую функцию.

Определение ограничений

Как уже отмечалось, существует ограниченный запас деталей, из которых можно соби­рать стулья Captain и Mate. Это ограничивает суммарное количество стульев, которые мож­но собрать. Чтобы точно сформулировать ограничения, начнем с определения необходи­мого количества длинных штифтов. Длинные штифты требуются для производства обоих видов стульев. На изготовление одного стула Captain идет 8 длинных штифтов, a Mate — 4. Таким образом, для любого плана выпуска справедливо следующее равенство:

8 х (к-во произведенных Captain) + 4 х (к-во произведенных Mate) = суммарная потребность в длинных штифтах.

Введем обозначения: пусть С — количество произведенных стульев Captain. М — ко­личество произведенных стульев Mate. Тогда выражение для суммарной потребности в длинных штифтах примет следующий вид:

8С + 4M = суммарная потребность в длинных штифтах.

Однако запас длинных штифтов составляет 1280 штук. Поэтому переменные решения С и М должны соответствовать ограничению

8С+4M<==1280. (1)

Это ограничение на суммарную потребность в длинных штифтах. Условие (1) назы­вается ограничением в виде неравенства. Число 1280 называется правой частью неравенства. Левая часть неравенства, которая зависит от неизвестных С и М, называется функцией ограничения. Неравенство (1)— символический способ представления ограничения, требующего, чтобы суммарная потребность в длинных штифтах для производства С штук стульев Capitan и М штук стульев Mate не превышала имеющийся запас— 1280 штук длинных штифтов.

Для производства одного стула Captain требуется 4 коротких штифта, a Mate— 12. Поскольку запас коротких штифтов составляет 1600 штук, Си М должны также соответ­ствовать ограничению

4С + 12М<= 1600. (2)

Неравенства (1) и (2) — два ограничения данной модели. Есть ли другие ограниче­ния? В перечне пунктов, которые необходимо учесть, говорится о существовании согла­шения с профсоюзом. Оно касается общего выпуска стульев:

С + М >= 100. (3)

Отметим, что условие (3) является неравенством типа ">=" в отличие от условий (1) и (2), которые являются неравенствами типа "<=".

Еще одно ограничение отражает тот факт, что для сборки каждого стула требуется 4 ножки, а запас ножек составляет 760 штук.

4С+4М<=760. (4)

В пятом пункте списка говорится, что для изготовления стула Captain требуется проч­ное сиденье, а для Mate — облегченное. Указаны также запасы сидений обоих видов. Эта информация записывается в виде двух ограничений:

С<= 140 и М<= 120. (5)

Мы сформулировали в сжатой форме шесть ограничений в виде неравенств для упро­щенной модели Oak Products. Поскольку количество изготовленных изделий не может при­нимать отрицательное значение, необходимо включить два дополнительных ограничения

С>=0 и М>=0. (6)

Условие вида (6), которое требует, чтобы переменные принимали неотрицательные значения, называется условием неотрицательности. Следует помнить, что неотрицатель­ность не то же самое, что положительность. Неотрицательность допускает значение 0. в то время как положительность не допускает нулевого значения. Итак, сформулированы все ограничения и условие неотрицательности для упрошен­ной модели Oak Product.

Оценивание решений

Как и в предыдущих моделях, значение пары переменных Си М называется решени­ем; сами переменные С и М называются переменными решения. В данной задаче решение — это структура производства изделий (стульев). Например, С= 6, М= 5 — это решение сделать 6 стульев марки Captain и 5 стульев Mate. Некоторые неотрицательные решения будут соответствовать всем огра­ничениям модели (1)—(5), другие — нет. Так, решение С= 6, М= 5 удовлетворяет ог­раничениям (1), (2), (4), (5) и (6), но нарушает ограничение (3). Данное реше­ние недопустимо, поскольку нарушает одно из ограничений.

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

Поиск по сайту: