12.2. ФОРМУЛИРОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Основная процедура является общей для формулирования всех задач линейного программирования:

Шаг 1. Определение переменных задачи, значения которых нужно получить в пределах существующих ограничений.

Шаг 2. Определение цели и ограничений на ресурсы.

Шаг 3? Описание цели через переменные задачи.

Шаг 4. Описание ограничений через переменные задачи.

Хотя на применение данной процедуры не влияет число переменных в задаче линейного программирования, рассмотрим сначала задачу с двумя переменными.

Пример 12.1. Небольшая семейная фирма производит два широко популярны безалкогольных напитка — "Pink Fizz" Фирма может продать всю продукцию, которая будет произведена, однако объем производства ограничен количеством основного ингредиента и производственной мощностью имеющегося оборудования. Для производства требуется работы оборудования, а для производства Расход специального ингредиента составляет 0,01 кг и 0,04 кг на соответственно. Ежедневно в распоряжении фирмы имеется времени работы оборудования и 16 кг специального ингредиента. Доход фирмы составляет 0,10 ф. ст. за ст. за Сколько продукции каждого вида следует производить ежедневно, если цель фирмы состоит в максимизации ежедневного дохода?

Решение

Шаг 1. Определение переменных. В рамках заданных ограничений фирма должна принять решение о том, какое количество каждого вида напитков следует выпускать. Пусть — число литров "Pink Fizz", производимое за день. Пусть число литров "Mint Pop", производимое за день.

Шаг 2. Определение цели и ограничений. Цель состоит в максимизации ежедневного дохода. Пусть Р — ежедневный доход, ф. ст. Он максимизируется в рамках ограничений на количество часов работы оборудования и наличие специального ингредиента.

Шаг 3. Выразим цель через переменные:

Это целевая функция задачи — количественное соотношение, которое подлежит оптимизации.

Шаг 4. Выразим ограничения через переменные. Существуют следующие ограничения на производственный процесс:

а) Время работы оборудования. Для производства литров "Pink Fizz" и литров "Mint Pop" требуется: часов работы оборудована ежедневно. Максимальное время работы оборудования в день составляет следовательно, объем производства должен быть таким, чтобы число затраченных часов работы оборудования было меньше либо равно ежедневно. Таким образом,

б) Специальный ингредиент. Производство литров "Pink Fizz" и литров требует кг ингредиента ежедневно. Максимальный расход ингредиента составляет 16 кг в день, следовательно, объем производства должен быть таким, чтобы требуемое количество специального ингредиента составляло не более 16 кг в день. Таким образом,

Других ограничений нет, однако разумно предположить, что фирма не может производить напитки в отрицательных количествах, поэтому:

в) Условие неотрицательности:

Окончательная формулировка задачи линейного программирования имеет следующий вид. Максимизировать:

при ограничениях:

время работы оборудования:

специальный ингредиент:

Пример 12.2. Завод-производитель высокоточных элементов для автомобилей выпускает два различных типа деталей: X и Завод располагает фондом рабочего времени в в неделю. Для производства одной детали типа X

требуется а для производства одной детали типа Производственные мощности завода позволяют выпускать максимум 2250 деталей типа X и 1750 деталей типа Y в неделю. Каждая деталь типа X требует 2 кг металлических стержней и 5 кг листового металла, а для производства одной детали типа Y необходимо 5 кг металлических стержней и 2 кг листового металла. Уровень запасов каждого вида металла составляет 10000 кг в неделю. Кроме того, еженедельно завод поставляет 600 деталей типа X своему постоянному заказчику. Существует также профсоюзное соглашение, в соответствии с которым общее число производимых в течение одной недели деталей должно составлять не менее 1500 штук.

Сколько деталей каждого типа следует производить, чтобы максимизировать общий доход за неделю, если доход от производства одной детали типа X составляет ст., а от производства одной детали типа ст.?

Решение

Сначала необходимо сформулировать задачу линейного программирования.

Шаг 1. Идентификация переменных. Необходимо произвести х деталей типа X и у деталей типа Y в неделю.

Шаг 2. Какова цель задачи? Каковы ограничения на процесс производства? Цель состоит в максимизации общего дохода за неделю. Производственный процесс ограничивается уровнем:

а) фонда рабочего времени — максимально возможный фонд рабочего времени составляет 4000 чел. в неделю.

б) производственной мощности — для каждого типа деталей существует отдельное ограничение по производственной мощности. Оборудование позволяет выпускать не более 2250 деталей типа X и 1750 типа Y в неделю.

в) металлических стержней — максимальный их уровень составляет 10000 кг в неделю.

г) листового металла — максимальный уровень этого ресурса равен 10000 кг в неделю.

Кроме того, существуют ограничения на минимальный объем производства деталей каждого вида:

а) постоянные заказы — число произведенных деталей X должно быть достаточным для удовлетворения размера постоянных заказов.

б) Профсоюзное соглашение — общее число деталей не должно быть ниже объема, предусмотренного соглашением.

Шаг 3. Целевая функция. Пусть Р — общий доход за неделю, ф. ст., где

Шаг 4. Ограничения на производственный процесс. Для каждого ограничения на ресурсы, необходимые для производства х деталей типа X и у деталей типа Y в неделю, ниже приведены количества и соответствующие им максимальные уровни наличных ресурсов.

Требуемый фонд рабочего времени:

Требуемая производственная мощность: деталей

Требуемое количество металлических

стержней: кг

Требуемое количество листового металла: кг

Постоянные заказы: деталей

Профсоюзное соглашение: деталей

Условие неотрицательности:

Окончательная формулировка задачи линейного программирования имеет вид: Производится х деталей типа X и у деталей типа У в неделю. Максимизировать:

при ограничениях:

Фонд рабочего времени:

Производственная мощность: деталей

Металлические стержни: и 10000 кг

Листовой металл: и 10000 кг

Постоянные заказы: деталей

Профсоюзное соглашение: деталей

Условие неотрицательности:

Теперь рассмотрим задачу, число переменных в которой больше двух. Общая схема формулировки и в этом случае остается неизменной.

О Пример 12.3. Завод по производству электронного оборудования выпускает персональные компьютеры и системы подготовки текстов. В настоящее время освоены четыре модели:

а) "Юпитер" — объем памяти 512 Кбайт, одинарный дисковод;

б) "Венера" — объем памяти 512 Кбайт, двойной дисковод;

в) "Марс" — объем памяти 640 Кбайт, двойной дисковод;

г) "Сатурн" — объем памяти 640 Кбайт, жесткий диск.

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

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

Решение

Шаг 1. Выбор переменных. Производится: единиц "Юпитера" в месяц, единиц "Венеры" в месяц, единиц "Марса” в месяц, единиц "Сатурна" в месяц.

Таблица 12.1. Время, требуемое на обработку каждой модели каждом цехе

Шаг 2. Какова цель задачи? Каковы ограничения на производственный процесс? Цель состоит в максимизации общего дохода за месяц. Объем производства ограничен размером фонда рабочего времени по каждому цеху и возможностью продажи компьютеров каждой модели. -

Шаг 3. Целевая функция задачи. Пусть Р (ф. ст.) — общий доход в месяц, тогда:

Шаг 4. Ограничения на производственный процесс. Для каждого цеха время, требуемое для производства и единиц продукции соответствующих моделей увязывается с максимальной производственной мощностью данного цеха.

Цех узловой сборки

Сборочный Испытательный

Спрос на

Спрос на

Спрос на

Спрос на

Условие неотрицательности:

Окончательная формулировка задачи линейного программирования такова: каждый месяц производится и единиц компьютеров типа "Юпитер”, "Венера", "Марс" и "Сатурн" соответственно. Максимизировать:

в условиях ограничений, указанных выше.

Пример 12.4. Менеджер по ценным бумагам намерен разместить ст. капитала таким образом, чтобы получать максимальные годовые проценты с дохода. Его выбор ограничен четырьмя возможными объектами инвестиций: А, В, С и D. Объект А позволяет получать 6% годовых, объект годовых, объект

объект годовых. Для всех четырех объектов степень риска и условия размещения капитала различны. Чтобы не подвергать риску имеющийся капитал, менеджер принял решение, что не менее половины инвестиций необходимо вложить в объекты А и В. Чтобы обеспечить ликвидность, не менее 25% общей суммы капитала нужно поместить в объект Учитывая возможные изменения в политике правительства, предусматривается, что в объект С следует вкладывать не более 20% инвестиций, тогда как особенности налоговой политики требуют, чтобы в объект А было вложено не менее 30% капитала. Сформулируем для изложенной проблемы распределения инвестиций модель линейного программирования. Решение

Вкладывается а ф. ст. в объект ст. — в объект В, с ф. ст. — в объект С и ст. - в объект Целью является максимизация общей суммы годовых процентов с дохода. На распределение инвестиций наложены ограничения, связанные с отсутствием риска, ликвидностью, политикой правительства и системой налогообложения. Обозначим через общую сумму годового процентного дохода, тогда:

Максимизация целевой функции осуществляется в условиях ограничений на

Общую сумму инвестиций: ст.

Отсутствие риска:

Ликвидность:

Правительственную политику: с

Систему налогообложения:

Неотрицательность:

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

Вкладывается

Максимизируется общая сумма годового процентного дохода, т.е.:

в условиях следующих ограничений :

Общая сумма инвестиций:

Отсутствие риска:

Ликвидность:

Правительственная политика:

Система налогообложения:

Условие неотрицательности:

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