Формулировка задачи линейного программирования

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

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

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

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

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

402 Ч. 4. Моделирование в бизнесе

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

Р = 0,10 р + 0,30 m (ф. ст. в день).

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

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

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

0,02 р + 0,04 m £ 24 ч/день.

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

0,01 р + 0,04 m Z 16 кг/день.

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

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

р Z 0, m Z 0.

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

Р = 0,10 р + 0,30 m (ф. ст. в день)

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

время работы оборудования: 0,02 р + 0,04 m < 24 ч/день;
специальный ингредиент: 0,01 р + 0,04 m £ 16 кг/день;

р, m £ 0.

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

Гл. 12. Линейное программирование 403

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

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

Решение

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

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

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

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

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

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

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

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

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

Р = 30 х + 40 у (ф. ст. в неделю).

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

Требуемый фонд рабочего времени: 1 х + 2 у £ 4000 чел.-ч.

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

у £ 1750 деталей

404 Ч. 4. Моделирование в бизнесе

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

стержней: 2 х + 5 у £ 10000 кг

Требуемое количество листового металла: 5 х + 2 у £ 10000 кг

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

Профсоюзное соглашение: х + у £ 1500 деталей

Условие неотрицательности: х, у £ 0.

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

Производится х деталей типа X и у деталей типа У в неделю.

Максимизировать:

Р = 30 х + 40 у (ф. ст.)

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

Фонд рабочего времени: 1 х + 2 у £ 4000 чел.-ч.

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

у й 1750 деталей

Металлические стержни: 2 х + 5 у й 10000 кг

Листовой металл: 5 х + 2 у й 10000 кг

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

Профсоюзное соглашение: х + у 2: 1500 деталей

Условие неотрицательности: х, у £ 0.

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

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

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

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

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

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

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

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

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

v единиц "Венеры" в месяц,

m единиц "Марса" в месяц,

s единиц "Сатурна" в месяц.

	Таблица 12.1. Время,требуемое наобработку каждой модели • каждом цехе
Цех	Время на единицу продукции, ч	Максимальная
"Юпитер"	"Венера"	"Марс"	"Сатурн"	производственная мощность, ч/мес.
Узловой сборки Сборочный Испытательный	5 2 0,1	8 3 0,2	20 8 2	25 14 4	800 420 150
Максимальное прогнозное значение спроса, за месяц
Доход, ф.ст.

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

Р = 15 j + 30 v + 120 m + 130 s (ф. ст. в месяц).

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

Цех узловой сборки	5j + 8v +20m + 25s	£ 800 (ч/мес.)
Сборочный цех:	2 j + 3v + 8m + 14s	£420 (ч/мес.)
Испытательный цех:	0,lj +0,2v + 2m+ 4s	£ 150 (ч/мес.)
Спрос на "Юпитер":	j	£ 100 (ед./мес.)
Спрос на "Венеру":	V	£ 45 (ед./мес)
Спрос на "Марс":	m	£ 25 (ед./мес.)
Спрос на "Сатурн":	s	£ 20 (ед./мес.)
Условие неотрицательности:	j, v, ra, s	;> о

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

Р = 15 j + 30 v + 120 m + 130 s (ф. ст. в месяц)

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

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

лдб Ч. 4. Моделирование в бизнесе

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

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

R = 0,06 а + 0,08 Ь + 0,10 с + 0,09 d (ф. ст. в год).

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

Общую сумму инвестиций: a + b + c + di 100000 ф. ст.

Отсутствие риска: а+Ьг 0,05 (а + b + с + d)

Ликвидность: d i. 0,25 (а + b + с + d)

Правительственную политику: с S 0,2 (а + b + с + d)

Систему налогообложения: а £ 0,3 (а + b + с + d)

Неотрицательность: а, Ь, с, d £ 0.

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

Вкладывается а ф. ст. в объект А,

b ф. ст. в объект В,

с ф. ст. в объект С,

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

R=0,06 а + 0,08 b + 0,10 с + 0,09 d (ф. ст. в год)

в условиях следующих ограничений (ф. ст.):

Общая сумма инвестиций: а + b+ c+ d £ 100000

Отсутствие риска: 0,5 а + 0,5 b - 0,5 с - 0,5 d £ 0

Ликвидность: -0,25 а -0,25Ь -0,25 с + 0,75d £ 0

Правительственная

политика: -0,2 а - 0,2 Ь + 0,8 с - 0,2 d SO

Система налогообложения: 0,7 а - 0,3 b - 0,3 с - 0,3 d > 0

Условие неотрицательности: а, Ь, с, d £ 0

Гл. 12. Линейное программирование 407

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