Linear Programming Output summary 1 страница

Title: Trim Loss Model, Example 2.5-4 Final Iteration No.: 7 Objective Value = 262.5

Variable	Value	Obj Coeff	Obj Val Contrib
x1: stngl	0,00	1,00	0,00
x2: stng2	0,00	1,00	0,00
x3: stng3	0,00	1,00	0,00
x4: stng4	12,50	1,00	12,50
x5: stng5	100,00	1,00	100,00
x6: stng6	150,00	1,00	150,00
Constraint	RHS	Slack-/Surplus+
K>)	150,00	0,00
2(>)	200,00	0,00
3(>)	300,00	0,00
		"'Sensitivity Analysis'	It**
Variable	Current Obj Coeff	Min Obj Coeff	Max Obj Coeff	Reduced Cost
x1: stngl	1,00	0,88	infinity	-0,12
x2: stng2	1.00	0,88	infinity	-0,12
x3: stng3	1,00	1,00	infinity	0,00
x4: stng4	1,00	0,00	1,00	0,00
x5: stng5	1,00	0,25	1,25	0,00
x6: stng6	1,00	0,00	1,00	0,00
Constraint	Current RHS	Min RHS	Max RHS	Dual Price
1 (>)	150,00	100,00	infinity	0,25
2(>)	200,00	0,00	300,00	0,38
3(>)	300,00	0,00	infinity	0,50

Рис. 2.24. Выходной отчет программы TORA для задачи разрезания рулонов бумаги

При интерпретации результатов, полученных с помощью программы TORA, следу­ет учитывать требование целочисленности значений переменных, которое неявно присутствует в данной задаче. Например, двойственная цена 0,25, соответствую­щая первому ограничению, показывает, что увеличение на 1 количества заказных рулонов шириной 5 футов потребует дополнительно еще четверти стандартного ру­лона (шириной 20 футов). Но эта информация в данном случае не имеет практиче­ского смысла. Ее нужно переформулировать следующим образом (исходя из усло­вия целочисленности): потребуется дополнительный стандартный рулон при увеличении на 4 единицы количества заказных рулонов шириной 5 футов. Подоб­ные изменения следует внести при интерпретации других двойственных цен.

УПРАЖНЕНИЯ 2.5

1. Вернитесь к задаче из примера 2.5.1 (модель банковских инвестиций) и ее решению, приведенному на рис. 2.19.

а) Рассмотрим таблицу, в которой приведены результаты анализа чувстви­тельности правых частей неравенств ограничений. Объясните, почему

Глава 2. Введение в линейное программирование

минимальное и максимальное значения интервала изменений величины правой части первого неравенства равны соответственно 4,8 и 12 млн. долл.

b) Предположим, что банк решил вложить все 12 млн. долл. в сельскохозяй­ственные и коммерческие кредиты. Вычислите чистую прибыль банка.

c) Предположим, что объем капитала, предназначенного для инвестиций, возрос до 20 млн. долл., а лимит на сельскохозяйственные и коммерче­ские кредиты увеличился до 9 млн. долл. Будет ли новое оптимальное решение включать только кредиты на покупку жилья и коммерческие кредиты? Найдите это новое оптимальное решение.

2. Вернитесь к примеру 2.5.2 (модель освоения и использования земли). Пред­положим, что компания Birdeyes может купить дополнительные 100 акров земли за 450 ООО долл. Используя результаты анализа чувствительности по этой задаче (см. рис. 2.20), подскажите компании, стоит ли покупать эту землю.

3. Вернитесь к задаче из примера 2.5.3 (составление расписания движения автобу­сов). На основе оптимального решения, представленного на рис. 2.22, определите оптимальное количество используемых автобусов, предполагая, что минималь­ные потребности в автобусах для шести 4-часовых периодов (см. рис. 2.22) со­ставляют, во-первых, (4, 12, 10, 7, 12, 4) и, во-вторых, (4, 8, 7, 7, 12, 4).

4. Вернитесь к примеру 2.5.4 (задача минимизации потерь при разрезании ру­лонов бумаги) и ее оптимальному решению, показанному на рис. 2.24.

a) Определите потери бумаги при разрезании 200 стандартных рулонов по варианту 1 и 100 стандартных рулонов — по варианту 2.

b) Предположим, что ширина стандартного рулона равна 15 футам. Опреде­лите возможные варианты разрезки на рулоны шириной 5, 7 и 9 футов и укажите потери бумаги при использовании каждого варианта.

c) В исходной задаче (со стандартными рулонами шириной 20 футов) посту­пил новый заказ, где потребность в рулонах шириной 7 футов уменьши­лась до 80 штук, а необходимое число рулонов другой ширины (5 и 9 фу­тов) осталось неизменным. Сколько стандартных рулонов необходимо для выполнения нового заказа?

d) В исходной задаче требуемое количество рулонов шириной 9 футов воз­росло до 400 штук. Сколько дополнительных стандартных рулонов необ­ходимо для выполнения такого заказа?

5. Нефтедобывающая компания, расположенная на острове Аруба, добывает 600 000 баррелей сырой нефти в день. Нефтеперерабатывающий завод произ­водит два вида неэтилированного бензина: рядовой и высококачественный. Процесс нефтепереработки включает три стадии: 1) перегонка сырой нефти на перегонной колонне — на выходе бензиновый полуфабрикат, 2) часть по­луфабриката поступает на крекинг-установку, где производится бензиновый дистиллят, 3) смесительная установка смешивает полуфабрикат, получен­ный на выходе перегонной колонны, и бензиновый дистиллят. Как рядовой, так и высококачественный бензин, можно получить на основе либо бензино­вого полуфабриката, либо бензинового дистиллята (это зависит от того, что является основой смеси в смесительной установке), но стоимость таких видов бензина будет разной. Компания подсчитала, что чистая прибыль от одного барреля рядового бензина составляет 7,70 и 5,20 долл., в зависимости от то­го, будет ли основой бензина полуфабрикат или дистиллят. Аналогичная

2.5. Примеры моделей ЛП

чистая прибыль от одного барреля высококачественного бензина составляет соответственно 12,30 и 10,40 долл.

На производство одного барреля бензинового полуфабриката (получаемого на выходе перегонной колонны) идет 5 баррелей сырой нефти. Крекинг-установка за день не может переработать более 40 ООО баррелей полуфабри­ката. Весь остальной полуфабрикат идет на изготовление чистого бензина через смесительную установку. Ежедневно требуется производить не более 80 000 баррелей рядового и 50 000 баррелей высококачественного бензина.

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

b) Предположим, что появилась возможность увеличить производитель­ность перегонной колонны до 650 000 баррелей в день, для чего необходи­мо одноразовое вложение 3 500 000 долл., а после этого 15 000 долл. еже­дневно для поддержания такой производительности. Порекомендуете ли вы реализовать такую возможность? Обоснуйте свою рекомендацию.

6. Сахарный завод из сиропа сахарного тростника производит желтый сахар, обычный белый, сахарную пудру и мелассу (черную патоку). Компания еже­недельно закупает 4000 т сиропа и планирует производить не менее 25 т каж­дого сахарного продукта в неделю. Процесс производства начинается с пере­работки сахарного сиропа в желтый сахар и мелассу. Из одной тонны сиропа получается 0,3 т желтого сахара и 0,1т мелассы. Далее из желтого сахара вырабатывается белый: из тонны желтого сахара получается 0,8 т белого. Наконец, сахарная пудра получается из белого сахара путем размельчения на специальной мельнице. Производительность этой мельницы равна 95%, т.е. из тонны белого сахара получается 0,95 т сахарной пудры. Доход от од­ной тонны желтого и белого сахара, сахарной пудры и мелассы составляет 150, 200, 230 и 35 долл. соответственно.

a) Сформулируйте задачу линейного программирования и найдите ее опти­мальное решение.

b) Определите экономическую целесообразность расширения производства са­харного завода для переработки более 4000 т сахарного сиропа еженедельно.

7. Некая компания рассматривает возможность реализации шести проектов в течение 4 лет. Ожидаемые затраты на реализацию каждого проекта и доход от них приведены в следующей таблице. Компания может выполнить любой проект частично или полностью. При частичном выполнении проекта доход и затраты рассчитываются пропорционально реализованной доле проекта.

Проект	Затраты (на 1000 долл.) 1 -й год 2-й год 3-й год	4-й год	Доход (на 1000 долл.)
	10,5	14,4	2,2	2,4	32,40
	8,3	12,6	9,5	3,1	35,80
	10,2	14,2	5,6	4,2	17,75
	7,2	10,5	7,5	5,0	14,80
	12,3	10,1	8,3	6,3	18,20
	9,2	7,8	6,9	5,1	12,35
Возможное вложение (в 1000 долл.)	60,0	70,0	35,0	20,0

Глава 2. Введение в линейное программирование

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

b) Предположим, что никакая часть второго проекта не может быть выпол­нена без реализации такой же или большей части шестого проекта. Изме­ните формулировку задачи и найдите новое оптимальное решение.

c) Каков эффект от денег, вложенных на 4-м году?

d) Предположим, что деньги, оставшиеся в конце года, можно использовать в следующем году. Найдите новое оптимальное решение и определите, какую сумму каждый год может "занять" у предыдущего.

e) Предположим, что суммы, вкладываемые ежегодно в течение первых трех лет, при необходимости можно получить в виде займа у внешних за­емщиков. Переформулируйте задачи и найдите оптимальное решение. Будет ли новое решение требовать займов каждый год? Если да, то каков процент прибыли можно получить на заемные деньги?

8. Производственная компания "Прогресс" получила заказ на изготовление оконных блоков, рассчитанный на 6 месяцев. В течение этого срока надо ежемесячно поставлять 100, 250, 190, 140, 220 и 110 оконных блоков. Стои­мость оконных блоков в разные месяцы может быть разной, в зависимости от стоимости трудовых ресурсов, материалов и оконной фурнитуры. Компания подсчитала, что стоимость ее продукции на следующие 6 месяцев будет равна 50, 45, 55, 48, 52 и 50 долл. за один оконный блок. Учитывая изменения стоимости, компания может производить больше оконных блоков, чем необ­ходимо, и использовать ранее произведенную продукцию для покрытия по­требности следующих месяцев. Однако хранение одного оконного блока сто­ит 8 долл. в месяц, причем начисления за хранение происходят при инвентаризации продукции в конце каждого месяца.

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

b) Решите задачу, предполагая, что компания имеет в начале первого месяца в запасе 25 оконных блоков.

c) Объясните, почему двойственные цены для 1-, 2-, 4- и 5-го месяцев в точ­ности равны стоимостям производства единицы продукции в эти месяцы, тогда как в 3-й месяц этого не наблюдается.

d) Если стоимость хранения оконного блока возрастет до 9 долл., изменится ли полученное ранее оптимальное решение?

9. Некий инвестор имеет четыре проекта инвестирования суммы в размере 100 000 долл. В следующей таблице показаны денежные потоки для каждого инвестиционного проекта.

Проект		Денежные потоки (в 1000 долл.) на начало года
1-й год	2-й год	3-й год	4-й год	5-й год
	-1,00	0,50	0,30	1,80	1,20
	-1,00	0,60	0,20	1,50	1,30
	0,00	-1,00	0,80	1,90	0,80
	-1,00	0,40	0,60	1,80	0,95

2.5. Примеры моделей ЛП

Рассмотрим подробнее эту таблицу. Например, для проекта 1 вложение 1,00 долл. в начале первого года принесет 0,50 долл. в начале второго года, 0,30 долл. — вначале третьего года, 1,80долл. — в начале четвертого и 1,20долл. — в на­чале пятого. Для остальных проектов данные интерпретируются таким же об­разом. Значение 0,00 показывает, что поступления денег в этом году нет. Инве­стор также может положить деньги в банк под 6,5% годовых. Деньги, полученные по итогам года, можно реинвестировать в последующие годы.

a) Сформулируйте задачу линейного программирования и найдите решение, оптимизирующее размещение инвестиций.

b) Используя двойственные цены, определите доходность инвестиций.

c) Если в конце первого года вы планируете истратить 1000 долл. на удо­вольствия, то как это отразится на сумме, получаемой в начале пятого года?

10. Производственная компания Toolco заключила контракт с сетью магазинов авто­товаров AutoMate на поставку 1500 гаечных ключей и 1200 специальных отвер­ток еженедельно. Работая в одну смену, компания Toolco не может выполнить этот контракт, поэтому вынуждена ввести сверхурочные и воспользоваться ус­лугами субподрядчиков, в результате чего возрастает себестоимость ее инстру­ментов, как показано в следующей таблице. Отметим также, что рыночная це­на гаечных ключей более чем в два раза выше рыночной цены отверток.

Инструмент	Тип производства	Еженедельные производственные возможности (шт.)	Себестоимость единицы продукции (долл.)
Гаечный ключ	Обычный	0-550	2,00
	Использование сверхурочных	551 - 800	2,80
	Использование субподрядчиков	801 -■»	3,00
Отвертка	Обычный	0-620	2,10
	Использование сверхурочных	621 - 900	3,20
	Использование субподрядчиков	901 -~	4,20

a) Сформулируйте задачу линейного программирования и найдите опти­мальную схему производства каждого инструмента.

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

c) Как скажется на общей стоимости продукции увеличение на единицу произ­водственных возможностей обычной рабочей смены и сверхурочной работы?

11. Четыре изделия последовательно обрабатываются на двух станках. Данные, описывающие этот технологический процесс, приведены в следующей таблице.

Станок Стоимость часа		Время обработки (часы)	Максимальная
работы (долл.)	Изделие 1	Изделие 2 Изделие 3 Изделие 4	нагрузка (часы)
1 10		3 4 2
2 5		2 1 2
Цена единицы изделия (долл.)		70 55 45

Глава 2. Введение в линейное программирование

a) Сформулируйте задачу линейного программирования и найдите ее опти­мальное решение.

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

c) Какая максимальная стоимость машинного часа обработки третьего изде­лия позволит получить от него хоть какую-то прибыль?

12. Завод производит три типа (I, II и III) некоторого изделия, используя для это­го материал А и В. В следующей таблице приведены необходимые данные для этой задачи.

Материал	Расход материалов на единицу изделия 1 II III	Доступно
А
В
Надо произвести не менее (шт.)
Доход на единицу изделия (долл.)

На изготовление единицы изделия типа I тратится в два раза больше рабоче­го времени, чем на изготовление единицы изделия типа II, и в три раза боль­ше, чем на изготовление единицы изделия типа III. Рабочие ресурсы завода эквивалентны ресурсам, необходимым для изготовления 1500 шт. изделия типа I. Отдел маркетинга требует, чтобы объемы производства изделий типов I, II и III относились как 3:2:5.

a) Сформулируйте задачу линейного программирования и найдите ее опти­мальное решение.

b) Предположим, что завод имеет возможность приобрести дополнительный объем материала А по цене 12 долл. за единицу. Целесообразно ли делать такую покупку?

c) Порекомендуете ли вы заводу купить дополнительный объем материала В по цене 5 долл. за единицу?

13. Компания HiRise получила предложение участвовать в двух одногодичных проектах. Ежеквартальные денежные потоки для этих проектов показаны в следующей таблице.

Проект Объем денежных потоков (млн. долл.) на указанную дату

01.01.08 01.04.08 01.07.08 01.10.08 31.12.08

I -1,0 -3,1 -1,5 1,8 5,0

II -3,0 -2,5 1,5 1,8 2,8

Компания в начале каждого квартала может инвестировать 1 млн. долл., а также взять заем на сумму, не превышающую 10% совокупного годового дохода. Все займы должны быть возвращены в конце квартала. Прибавочные суммы могут ежеквартально приносить прибыль, равную 8% годовых. Все суммы, аккумулированные в конце квартала, можно инвестировать в следующем квартале.

2.5. Примеры моделей ЛП

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

b) Объясните, можно ли в каком-нибудь квартале использовать внешний за­ем и получить в конце этого же квартала чистый доход?

c) Дайте экономическую интерпретацию двойственным ценам в этой модели.

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

14. В предчувствии больших расходов на обучение своего ребенка в колледже семейная пара решила ежегодно откладывать определенную сумму в течение 10 лет, начиная с 8-летнего возраста ребенка. Они распределили эти суммы следующим образом.

Год 1	2 3					8 9
Сумма (долл.) 2000	2000 2500					4000 4000

Для предотвращения нежелательных финансовых сюрпризов, семейная пара решила вложить деньги в 1) страховой полис с 7,5% годовых; 2) шестилетние правительственные ценные бумаги с 7,9% годовых (их текущая рыночная цена равна 98% номинальной стоимости); 3) девятилетние муниципальные ценные бумаги с доходностью 8,5% и текущей рыночной стоимостью 1,02 от их номинальной стоимости.

a) Помогите этой семейной паре оптимально вложить свои деньги.

b) Вычислите их ежегодные доходы.

15. Бизнесмен имеет возможность вложить деньги в два инвестиционных про­екта: проект А гарантирует 0,70 долл. на каждый вложенный доллар еже­годно, проект В — 2 долл. на вложенный доллар по истечении двух лет. В проекте А вложения можно делать ежегодно, а в проекте В только в пе­риоды, кратные двум годам.

a) Как инвестировать 100 тыс. долл. для получения максимального дохода в конце третьего года инвестирования?

b) Стоит ли вкладывать еще деньги в эти проекты, т.е. можно ли получить больший процент прибыли при больших вложениях?

16. Рассмотрим задачу назначения трех типов самолетов на четыре маршрута в соответствии со следующими данными.

Тип	Вместимость	Количество	Число ежедневных полетов по маршруту
самолета	самолета (чел.)	самолетов
Ежедневное число пассажиров

Глава 2. Введение в линейное программирование

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

Тип самолета Стоимость одного полета по маршруту (в долл.)

Неустойка за одного "потерянного"

пассажира (долл.)

a) Определите оптимальное распределение самолетов по маршрутам.

b) Целесообразно ли увеличивать количество самолетов какого-либо типа?

c) Интерпретируйте двойственные цены, соответствующие ограничениям на количество пассажиров того или иного маршрута.

17. Сплавы А и В состоят из металлов I, И, III и IV согласно следующей специ­фикации.

Сплав		Спецификация		Рыночная цена (долл.)
А		Не более 80% металла I Не более 30% металла II Не менее 50% металла IV
В		От 40 до 60% металла II Не менее 30% металла III Не более 70% металла IV
Металлы, используемые для сплавов, получают из руды трех типов, как по­казано в следующей таблице.
Руда Максимум		Содержание металлов (%)
добычи (т)	I	II III IV	Другое Стоимость 1 т (долл.)
1 1000		10 30 30
2 2000		20 30 30
3 3000		5 70 20

a) Сколько сплавов каждого типа можно произвести? (Совет. Обозначьте через х_ш количество руды £, расходуемой на производство сплава ft, и через w_k — количество произведенного сплава ft.)

b) Сколько руды каждого типа расходуется на производство сплава А и сколько — на производство сплава В?

c) Какое из ограничений, связанных со спецификацией сплавов, самое не­благоприятное для оптимального решения?

d) Какую максимальную цену можно позволить при покупке руды 1? А руды 2 и 3?

Литература

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

Исход игры		Возврат на 1 долл., поставленный на поле
	-3		-7
		-3
		-9		-8

Игрок имеет 500 долл., которые он может поставить только один раз. Шансы какого-либо исхода игры неизвестны. В условиях этой неопределенности найдите стратегию, которая максимизировала бы минимальный возврат сде­ланной ставки при всех возможных исходах игры.

a) Как игрок должен разложить 500 долл. по четырем полям? (Подсказка. Чистая прибыль игрока может быть положительной, нулевой или отри­цательной.)

b) Ваш совет игроку о том, как сделать ставки, если появится дополнитель­ная сумма.

ЛИТЕРАТУРА

1. Bazaraa М., Jarvis J., Sherall М. Linear Programming and Network Flows, 2nd ed., Wiley, New York, 1990.

2. Schrage L. LINDO: An Optimization Modeling System, Text and Software, 4th ed., Boyd and Fraser, Danvers, Mass, 1991.

3. William H. Model Building in Mathematical Programming, 3rd ed., Wiley, New York, 1990.

Литература, добавленная при переводе

1. Гольштейн Е. Г., Юдин Д. Б. Линейное программирование: Теория, методы и приложения. — М.: Наука, 1969.

2. Кофман А. Методы и модели исследования операций. — М.: Мир, 1966.

3. Мур Дж., Уэдерфорд Л. Экономическое моделирование в Microsoft Excel. — М.: Издательский дом "Вильяме", 2004.

КОМПЛЕКСНЫЕ ЗАДАЧИ

2.1. ⁸ Компания Hi-C по переработке апельсинов производит три продукта: кон­центрат, обычный сок и джем, которые расфасовываются в 5-галонные бан­ки. Для джема используются апельсины только первого сорта, а для других

⁸ Материал для этой задачи взят из статьи "Red Brand Canners", Stanford Business Cases, 1965, Graduate School of Business, Stanford University (Высшая школа бизнеса Стэнфордско-го университета).

Глава 2. Введение в линейное программирование

продуктов — апельсины второго сорта. В следующей таблице показано, сколько апельсинов идет на производство продуктов, а также максималь­ный возможный объем их производства на следующий год.

Маркетинговые исследования показывают, что рыночные потребности в обычном соке более чем в два раза превосходят потребности в апельсино­вом концентрате.

Продукт С°РТ апельсинов	К-во апельсинов (фунты), необходимых для изготовления 5-галонной банки продукта	Возможности произ­водства (к-во банок)
Джем 1		10 000
Концентрат II		12 000
Сок II		40 000

В прошлом году компания закупала апельсины первого и второго сортов по отдельности по цене соответственно 25 и 20 центов за фунт. В этом году в силу ряда причин поставщики поставляют апельсины без сортировки. Подсчитано, что урожай текущего года (всего собрано 3 миллиона фунтов апельсинов) на 30% состоит из апельсинов первого сорта и на 60% — второ­го. Оптовая цена неотсортированных апельсинов опустилась до 19 центов за фунт. Компания Hi-C подсчитала, что сортировка апельсинов обойдется ей в 2,15 цента за фунт. Несортовые апельсины (10% от поставок) идут в отходы.

Для определения себестоимости продукции экономический отдел компании использует следующий способ вычисления стоимости фунта апельсинов первого и второго сортов. Поскольку 10% апельсинов идет в отходы, сред­няя стоимость сортовых апельсинов равна (19 + 2,15)/0,9 = 23,5 цента. Так как отношение объема апельсинов первого сорта к объему апельсинов вто­рого сорта составляет 1:2, средняя цена (на основе прошлогодних цен) должна быть равной (20 х 2 + 25 х 1)/3 = 21,67 цента. Итак, в этом году средняя цена апельсинов возросла на 1,83 цента (=23,5-21,67). Эту раз­ность надо "разбросать" на стоимость апельсинов первого и второго сортов, учитывая соотношения их объемов 1:2. В результате стоимость апельсинов первого сорта равна 25 + 1,83х(1/3) = 25,61 цента за фунт, а апельсинов второго сорта — 20 + 1,83х(2/3) = 21,22 цента за фунт. На основе этой ин­формации экономический отдел вычислил доходность всех трех произво­димых компанией продуктов.