LINEAR PROGRAMMING OUTPUT SUMMARY

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 цента за фунт. На основе этой ин­формации экономический отдел вычислил доходность всех трех произво­димых компанией продуктов.

	Джем	Концентрат	Сок
(для 5-галонных банок)
Отпускная цена, долл.	15,0	30,25	20,75
Стоимость сырья, долл.	9,85	21,05	13,28
Другие расходы, долл.	1,05	2,15	1,96
Себестоимость, долл.	10,90	23,20	15,24
Чистый доход, долл.	4,80	7,05	5,51

Составьте оптимальный производственный план для компании Hi-C.

Комплексные задачи 93

2.2. ⁹ Сталелитейная компания имеет литейный цех и два прокатных стана. Ли­тейный цех производит три типа стальных заготовок, которые, прежде чем попасть на прокатные станы, обрабатываются в механическом цехе.

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

т,.г, „_тт^_п,„. Длина заготовки Внутренняя цена Цена на рынке

j ип заготовки , . .

(футы) (в долл. на одну заготовку) (в долл. на одну заготовку)

1 800 90 108

2 1200 130 145

3 1650 180 194

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

Тип станка	Время обработки одной заготовки типа	Количество станков	Общее время работы станка в месяц
					(часы)
Потребности прокатных станов месяца.	в стальных заготовках на следующие три
Потребность в заготовках
	Первый прокатный стан	Второй прокатный стан
Месяц Заготовки типа 1	Заготовки типа 2	Заготовки типа 3	Заготовки типа 1	Зеготовки Заготовки типа 2 типа 3
					100 0
					200 200
					400 200

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

⁹ Взято из S. Jain, К. Stott, Е. Vasold. "Orderbook Balancing Using a Combination of Linear Pro­gramming and Heuristic Techniques", Interfaces, Vol. 9, No. 1, November 1978, pp. 55-67.

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

2.3. Фирма АгкТес собирает персональные компьютеры для частных клиентов. На следующие четыре квартала имеются заказы на 400, 700, 500 и 200 ком­пьютеров соответственно. Фирма может производить больше компьютеров, чем указано в заказах, но в таком случае приходится платить 100 долл. за хранение одного компьютера в течение квартала. Увеличение производства в следующем квартале, по сравнению с предыдущим, приводит к дополни­тельному набору работников, что повышает себестоимость одного компью­тера на 60 долл. При уменьшении производства в следующем квартале, по сравнению с предыдущим, придется прибегнуть к сокращению персонала, что также увеличивает себестоимость одного компьютера на 50 долл. Как организовать сборку компьютеров, чтобы удовлетворить все заказы?

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

Ежемесячная производительность заготовительного цеха составляет 3000 стульев, 1000 столов и 580 книжных полок (несобранных). В сбороч­ном цехе работают 150 рабочих в две 8-часовые смены 5 дней в неделю. Среднее время сборки одной единицы продукции равно 20, 40 и 15 минут соответственно для стульев, столов и книжных полок.

Количество рабочих в сборочном цехе колеблется в зависимости от того, сколько человек в настоящее время находится в ежегодном отпуске. В мае, июне и июле планируют уйти в отпуск соответственно 20, 25 и 45 человек.

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

Продукт	Май Июнь	Июль	Остаток на конец апреля
Стул	2800 2300
Стол	500 800
Книжная полка	320 300
Себестоимость продукции и ее отпускная цена показаны в следующей таблице.
Продукт	Себестоимость (долл.)	Отпускная цена (долл.)
Стул
Стол
Книжная полка

Если какая-либо продукция не продана в течение того месяца, в каком она произведена, то она может быть продана в следующем месяце. Хранение одной единицы стоит 2% от стоимости этой продукции.

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

ГЛАВА 3

СИМПЛЕКС-МЕТОД

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

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

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

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

3.1. СТАНДАРТНАЯ ФОРМА ЗАДАЧИ ЛП

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

1. Все ограничения (включая ограничения неотрицательности переменных) преобразуются в равенства с неотрицательной правой частью.

2. Все переменные неотрицательные.

3.1.1. Преобразование неравенств в равенства

Неравенства любого типа (со знаками неравенств < или >) можно преобразовать в равенства путем добавления в левую часть неравенств дополнительных перемен­ных — остаточных или избыточных¹, которые связаны с неравенствами типа "<" и ">" соответственно.

¹ Отметим, что в русской язычной математической литературе для этих типов переменных не ис­пользуются какие-либо специальные названия — они известны просто как дополнительные пере­менные (хотя иногда их также называют балансными). В неравенствах они различаются тем, что пе­ред остаточной переменной всегда стоит знак " плюс", а перед избыточной — " минус". — Прим. ред.

Глава 3. Симплекс-метод

Для неравенств типа "<" в левую часть неравенства вводится неотрицательная остаточная переменная. Например, в модели компании Reddy Mikks (пример 2.1.1) ограничение на количество сырья Ml задается в виде неравенства 6х, + 4х₂ < 24. Вво­дя новую неотрицательную переменную s,, которая показывает остаток (неспользованное количество) сырья Ml, это ограничение преобразуется в равенство

6x,+4x₂ + s₁ = 24, s,>0.

Неравенства типа ">" в задачах ЛП обычно устанавливают нижнюю границу че­го-либо. Избыточная переменная определяет превышение значения левой части неравенства над этой границей. Так, в модели "диеты" (пример 2.2.2) неравенство х_} + х₂ > 800 показывает, что суточное производство пищевой добавки не должно быть меньше 800 фунтов. Математически это неравенство эквивалентно равенству

х, + х₂ - S, = 800, S, > 0.

Положительное значение избыточной переменной S, показывает превышение суточного производства добавки над минимальным значением в 800 фунтов.

Важно еще раз подчеркнуть, что дополнительные переменные — остаточная s, и избыточная S, — всегда неотрицательные.

Правую часть равенства всегда можно сделать неотрицательной, умножив все равенство на -1. Кроме того, заметим, что неравенство типа "<" также преобразу­ется в неравенство типа ">" посредством умножения обеих частей неравенства на -1. Например, неравенство -х, + х₂ < -3 эквивалентно равенству

-х, + х₂ + s, = -3, s, > 0.

Теперь, умножая обе части этого равенства на -1, получим равенство с неотрица­тельной правой частью: х, - х₂ - s, = 3.

УПРАЖНЕНИЯ 3.1.1

1. В модели компании Reddy Mikks (пример 2.2.1) рассмотрите допустимое ре­шение х, = 3 т и х₂ = 1 т. Для этого решения найдите недоиспользование сы­рья Ml и М2.

2. В модели "диеты" (пример 2.2.2) определите превышение над минимальным допустимым объемом производства пищевой добавки, на которую расходует­ся 500 фунтов кукурузной муки и 600 фунтов — соевой.

3. Дано неравенство 10х,-Зх₂>-5. Покажите, что в результате преобразова­ния, когда сначала обе части неравенства умножаются на -1, а затем нера­венство преобразуется в равенство, получется такое же равенство, что и в ре­зультате преобразования, когда сначала исходное неравенство преобразуется в равенство, а затем умножается на -1.

4. Два изделия, Р1 и Р2, можно произвести на двух различных станках Ml и М2. Время изготовления любого изделия на любом станке одинаково. Про­изводительность станка Ml составляет 200 изделий за смену, а производи­тельность станка М2 — 250 изделий. Мастер планирует сбалансировать ра­бочее время таким образом, чтобы общее количество изделий, произведенных на одном станке, не превышало более чем на 5 единиц общее количество изделий, изготовленных на другом станке. Доход от одного изде­лия Р1 составляет 10, а от второго — 15 долл. Запишите эту задачу в стан­дартной форме линейного программирования.

3.1. Стандартная форма задачи ЛП 97

5. Покажите, как следующую целевую функцию можно записать в стандартной форме задачи ЛП.

Минимизировать z = maxflx, - х₂ + Зх₃, -х_х + Зх₂ - х₃},

х_х, х₂, х₃>0.

6. Покажите, что т равенств вида

Y,^a„^x,=^b,- ' = 1.2,...,ш,

7 = 1

эквивалентны следующим т + 1 неравенствам.

Ё^аЛ-*" ' = 1.2,...,m,

7 = 1

II f III III

3.1.2. Свободная переменная

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

Пример 3.1.1

Ресторан быстрого обслуживания McBurger торгует порционными мясными пиро­гами и чизбургерами. На порцию мясного пирога идет четверть фунта мяса, а на чизбургер — только 0,2 фунта. В начале рабочего дня в ресторане имеется 200 фун­тов мяса, можно еще прикупить мясо в течение дня, но уже с наценкой в 25 центов. Мясо, оставшееся в конце рабочего дня, жертвуется благотворительной организа­ции. Ресторан получает доход 20 центов от одной порции мясного пирога и 15 цен­тов — от одного чизбургера. Как и многие другие, этот ресторан не может продать в день более 900 бутербродов. Какова должна быть доля каждого блюда (т.е. сколь­ко порций мясного пирога и сколько чизбургеров) в ежедневном производстве рес­торана, чтобы максимизировать его доход?

Сначала рассмотрим ограничения. Обозначим через х_х и х₂ соответственно количество порций мясного пирога и чизбургеров, производимых рестораном. Для их производ­ства ресторан может либо ограничиться 200 фунтами мяса, либо прикупить еще. В первом случае получаем ограничение в виде неравенства 0,25х, + 0,2х, < 200, а во втором— 0,25л', + 0,2д:₂ > 200. Естественно, выбор одного из этих неравенств будет существенно влиять на возможное оптимальное решение. Так как мы не знаем, какое из них необходимо, логично заменить их одним равенством 0,25*, + 0,2д:₂+ дг₃ = 200, гдех, — свободная переменная. Фактически свободная переменная х₃ в данной ситуа­ции одновременно играет роли как остаточной, так и избыточной переменной.

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

Глава 3. Симплекс-метод

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

*з ^{= х}1 ~ ^х1> ^гД^{е х}1 > ^хз - °-Если л* > 0 и л₃ = 0, то переменная .v₃ играет роль остаточной. Если, напротив, х'_} > О и xl = 0, то переменная х₃ выступает в роли избыточной. (Теория задач ЛП гласит, что переменные х*₃ и .v₃~ не могут одновременно принимать положительные значе­ния.) Итак, теперь ограничение можно записать в виде равенства

0,25л-, +0,2х₂ + х; - х~ = 200. Целевая функция получает следующее выражение.

Максимизировать z = 0,20 + 0, [5х₂ - 0,25 х_}

УПРАЖНЕНИЯ 3.1.2

1. В некотором машинном центре производятся два изделия, причем на производ­ство одной единицы первого изделия затрачивается 10 минут рабочего времени, а на единицу второго изделия — 12 минут. Рабочее время машинного центра ог­раничено 2500 минут в день (некоторые операции центр может выполнять па­раллельно); возможно превышение этой величины, но каждая дополнительная минута работы машинного центра стоит 50 центов. В рабочий день допустимо производить от 150 до 200 единиц первого изделия, но не более 45 единиц второго.

a) Предполагая, что доход от единицы первого изделия составляет 6,00 долл., а второго — 7,50 долл., постройте модель и найдите оптимальное соотно­шение между объемами производства изделий, максимизирующее общий доход, а также дополнительное время работы машинного центра.

b) Если стоимость дополнительного времени работы машинного центра уве­личится до 1,50 долл., будет ли компания использовать это время?

2. Фирма производит три вида изделий, прибыль от которых составляет соот­ветственно 2, 5 и 3 долл. на единицу изделия. Для производства этих изделий фирма располагает 80 рабочими часами ручного труда и 65 часами машинно­го времени. Для производства одной единицы изделия каждого из трех видов требуется 2, 1 и 2 часа ручного труда и 1, 1 и 2 часов машинного времени со­ответственно. При необходимости фирма может увеличить количество рабо­чих часов ручного труда и количество часов машинного времени, но каждый дополнительный час ручного труда будет стоить 15, а машинного — 10 долл.

Сформулируйте задачу линейного программирования и найдите ее опти­мальное решение с помощью программы TORA.

3. В задачах ЛП, где есть несколько свободных переменных, преобразование типа *_;=.v*-.v~, х*, Xj>0, удваивает соответствующее число неотрицатель­ных переменных. Но при использовании подстановок х =x'j-w, x'j,w>0

можно к свободных переменных заменить на ft + 1 неотрицательных. Ис­пользуя программу TORA, покажите, что эти два метода приводят к одному и тому же решению следующей задачи ЛП.

Максимизировать z = -2x, + Зх₂ - 2х₃

3.2. Переход от графического решения к алгебраическому

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

4х, - х₂ - 5х₃ = 10,

2х, + Зх₂ + 2х₃ = 12,

я, > 0, х₂, х_ъ — свободные переменные.

3.2. ПЕРЕХОД ОТ ГРАФИЧЕСКОГО РЕШЕНИЯ К АЛГЕБРАИЧЕСКОМУ

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

Графический метод

Алгебраический метод

Графическое представление всех ограничений, включая условие неотрицательности

Пространство решений состоит из бесконечного количества допустимых точек

Определяются допустимые угловые точки пространства решений

Кандидатами на оптимальное решение будут конечное число угловых точек

Целевая функция используется для определения оптимальной угловой точки среди всех кандидатов

Задание пространства решений посредством системы из т линейных уравнений с п неотрицательными переменными, т<п

Задача имеет бесконечное количество допустимых решений

Находятся допустимые базисные решения системы уравнений

Кандидатами на оптимальное решение будут конечное число базисных допустимых решений

Целевая функция используется для определения оптимального базисного допустимого решения среди всех кандидатов

Рис. 3.1. Переход от графического решения к алгебраическому

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

Если количество уравнений т больше количества переменных п, тогда по крайней мере т - п уравнений должны быть избыточными.

Глава 3. Симплекс-метод

она имеет только одно решение³; если же т < п и система уравнений совместна, то она имеет бесконечное множество решений. Простая иллюстрация в качестве доказа­тельства: для уравнения х = 2 имеем т = п = 1, а его решение, очевидно, единствен­ное. Для уравнения х + у = 1 имеем т — 1 и п = 2, этому уравнению удовлетворяет бесконечное множество решений (любая точка на прямой х + у=1 будет решением).

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

Следующий пример иллюстрирует это положение.

Пример 3.2.1

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

Максимизировать z = 2л-, + Зл₂

при выполнении условий

2л-,+л-_г<4, л-, + 2х._г < 5, л-,,л-₂>0.

На рис. 3.2 показано пространство решений для этой задачи. ^х2

0 1 2 3 4 5

Рис. 3.2. Пространство решений для примера 3.2.1

Это не совсем верно: совместная система уравнений имеет единственное решение тогда, когда она невырождена. — Прим. ред.

3.2. Переход от графического решения к алгебраическому

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

Максимизировать z = 2х_х + Зх_г

при выполнении условий

2дг, + х₂ + s, = 4, л-, + 2х_г + s₂ = 5,

*^2' ^1' ^2 — ^*

Здесь имеем систему из т = 2 уравнений для л = 4 переменных. Согласно сформу­лированному выше правилу угловые точки можно определить алгебраически, при­своив я-т = 4- 2 = 2 переменным нулевых значений и решив затем систему урав­нений относительно оставшихся т = 2 переменных. Если, например, положить х_х = 0 и х₂ = 0, тогда решением системы будет s, = 4, s₂ = 5. Это решение соответству­ет точке Л на рис. 3.2 (убедитесь, что решение 5, = 4, s₂ = 5 действительно соответст­вует точке А). Другую угловую точку можно определить, если положить s, = 0 и 5₂ = 0. В этом случае надо найти решение системы

2х_х + х₂ = 4,

я, + 2x₂ = 5.

Решением в данном случае будет jt, = 1 и х, = 2, что соответствует точке С на рис. 3.2.

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

4'

В нашем примере мы имеем ^1 =-^- = 6 У^гловых точек. Но, глядя на рис. 3.2,

можно насчитать только 4 угловые точки —А, В, С nD. Где "спрятались" еще две точки? В действительности точки Е и F также являются угловыми точками, но это недопустимые угловые точки, поскольку они не удовлетворяют всем ограничени­ям задачи. Такие недопустимые угловые точки не рассматриваются как кандидаты на оптимальное решение.

Для полного перехода к алгебраическому методу решения задач ЛП необходимо как-то назвать угловые точки разного типа на "алгебраическом" языке. На этом языке п - т переменные, которые полагаются равными нулю, называются неба­зисными переменными. Если оставшиеся т переменные имеют единственное ре­шение, то в этом случае они называются базисными переменными, а совокупность значений, которые они получают в результате решения системы уравнений, со­ставляют базисное решение (см. рис. 3.1). Если при этом все переменные прини­мают неотрицательные значения, то такое базисное решение является допусти­мым. В противном случае — недопустимым.⁴

ⁱ В русскоязычной математической литературе также применяются термины "план", "опорный план" и "оптимальный опорный план" как эквиваленты для терминов "базисное ре­шение" , "допустимое базисное решение" и "оптимальное базисное решение". — Прим. ред.

102 Глава 3. Симплекс-метод

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

Небазисные	Базисные	Базисные	Соответствующие	Допустимо	Значение
(нулевые)	пере-	решения	угловые точки	ли решение?	целевой
переменные	менные				функции z
х2)	(Si, 8г)	(5, 4)	А	Да
Si)	(Хг, 8г)	(4, -3)	F	Нет	—
(X1. s2)	(Хг, Si)	(2,5, 1,5)	D	Да	7,5
(*2, Si)	(*1, s2)	(2, 3)	В	Да
(Хг, S>)	(Хь Si)	(5, -6)	Е	Нет	—
(Si, «г)	(Xi, x2)	(1,2)	С	Да	8 (оптимум)

Как видно из примера 3.2.1, при возрастании размера задачи (т.е. при увеличе­нии значений пит) процесс перечисления всех угловых точек становится отдель­ной чрезвычайно сложной задачей. Например, при п = 20 и т = 10, когда необхо­димо решить С'°₀ = 184756 систем уравнений порядка 10x10, получаем устрашающую, в вычислительном отношении, задачу. Здесь следует учесть, что за­дачи ЛП размерности 10x20 считаются небольшими — реальные задачи могут иметь сотни и даже тысячи переменных и ограничений. Однако симплекс-метод в значительной степени снимает эту проблему, поскольку он рассматривает не все возможные базисные решения (т.е. угловые точки пространства решений), а только часть всех допустимых базисных решений.

УПРАЖНЕНИЯ 3.2

1. Проверьте все базисные и небазисные решения, приведенные в конце при­мера 3.2.1.

2. Дана следующая задача ЛП.

Максимизировать z = 2х_х + Зх₂

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

х₁ + 3х₂<6, Зх₁ + 2х₂<6, x_v х_г>0.

a) Запишите задачу в стандартной форме.

b) Найдите все базисные решения этой задачи и определите, какие из них допустимые, а какие — нет.

c) Путем непосредственной подстановки решений в целевую функцию опре­делите наилучшее допустимое базисное решение.

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

e) Определите, чему на рисунке, где представлено пространство решений, соответствует недопустимое базисное решение.

3.2. Переход от графического решения к алгебраическому

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

a) Максимизировать z = 2х_х - 4х₂ + Ъх₃ - 6x_t при ограничениях

х_г + 4х₂ - 2х₃ + 8x_t < 2, -x_l + 2x₂ + 3x₃ + 4x_i<l,

^Х2* *^3' — О"

b) Минимизировать z = х_х + 2x₂ - 3jc₃ - 2x_t при ограничениях

л:, + 2x₂ - 3jc₃ + x₄ = 4, jc, + 2jc₂ + x₃ + 2x_t = 4, ^-p x₂, x₃, x₄ — 0.

4. Покажите, что все базисные решения следующей задачи ЛП недопустимы.

Максимизировать z = х_х + х₂

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

х, + 2х₂<6, 2х, + х₂ > 16, jc,, jc₂>0.

5. Дана следующая задача ЛП.

Максимизировать z = 2х_х + Зх₂ + Ъх₃

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

-бх, + 7х₂-9х₃>4, -х_х + х₂ + 4х₃ = 10, *„ *₃>0,

х₂ — свободная переменная. Приведите задачу к стандартной форме, используя для этого подстановку х, =х* Покажите, что в этой задаче не существует базисных решений, в

которые входили бы одновременно х, и х.

6. Рассмотрите следующую задачу ЛП.

Максимизировать z = х_х + Зх₂

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

х_х + х₂< 2, -jc, + х₂ < 4,

х_х — свободная переменная, х₂>0.

a) Найдите все допустимые базисные решения этой задачи.

b) С помощью подстановки решений в целевую функцию определите наи­лучшее базисное решение.

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

Глава 3. Симплекс-метод

3.3. АЛГОРИТМ СИМПЛЕКС-МЕТОДА

Основываясь на определениях из раздела 3.2, мы можем найти оптимальное решение задачи линейного программирования, записанной в стандартной форме, путем простого перебора всех базисных (допустимых) решений. Но, конечно, такая процедура не эффективна. Алгоритм симплекс-метода находит оптимальное реше­ние, рассматривая ограниченное количество допустимых базисных решений. В разделе 3.3.1 мы покажем итерационную природу симплекс-метода, а в разде­ле 3.3.2 — вычислительные детали его алгоритма.

3.3.1. Итерационная природа симплекс-метода

На рис. 3.3 показано пространство решений задачи ЛП из примера 3.2.1. Обыч­но алгоритм симплекс-метода начинается с исходной точки, где х_х = х₂ = 0 (точка А). В этой начальной точке значение целевой функции г равно нулю. Возни­кает естественный вопрос: если одна или обе небазисные переменные х_х и х₂ примут положительные значения, то приведет ли это к улучшению (возрастанию) значений целевой функции? Для ответа на этот вопрос рассмотрим целевую функцию

максимизировать г = 2х_х + Зх₂.

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

1. Если увеличивать значение переменной x_v то (см. рис. 3.3) ее значение должно возрасти таким образом, чтобы соответствовать угловой точке В (повторим, что внутренние точки отрезка от точки А до точки В неприемле­мы, поскольку кандидатом на оптимальное решение может быть только уг­ловая точка). В точке В симплекс-метод должен увеличить значение пере­менной х₂, перемещаясь при этом в угловую точку С. Так как точка С соответствует оптимальному решению, то на этом процесс вычислений за­канчивается. Таким образом, алгоритм симплекс-метода создает путь А—> В —» С.

2. Если сначала увеличивать значение переменной х₂, то следующей угловой точкой будет точка D, из которой процесс решения переходит в оптимальную точку С. Здесь алгоритм симплекс-метода создает путь А —> Z) —»С.

Отметим, что оба пути, A^>B—>CnA—>D—>C, расположены вдоль границы про­странства решений. Это означает, что симплекс-метод не может сразу перескочить из точки А в точку С.

Может возникнуть правомерный вопрос: существует ли правило, в соответствии с которым можно было бы определить, какую небазисную переменную сделать по­ложительной в данной угловой точке? Например, в точкеА как переменная x_v так и переменная х₂ могут увеличить значение целевой функции. Симплекс-метод предлагает простое правило выбора переменных, которое в основном применяется в его программных реализациях. Поскольку здесь мы рассматриваем задачу мак­симизации, то следует выбирать такую небазисную переменную, которая имеет наибольший положительный коэффициент в выражении целевой функции. Если таких переменных несколько, то выбор произвольный. Необходимо понимать, что это эмпирическое правило, сформулированное на основе многочисленных компью­терных вычислений симплекс-метода — в большинстве случаев (но не обязательно всегда) применение этого правила ведет к наименьшему числу итераций, затрачи­ваемых на поиск оптимального решения.

3.3. Алгоритм симплекс-метода

0 1 2 3 4 5 *i

Рис. 3.3. Итерацион