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

Базис	Х1	хг	хз	х4	Х5	Хб	Решение
z
хг	-1/4			1/2	-1/4
Хз	3/2				1/2
Хб				-2			-40

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

Глава 4. Двойственность и анализ чувствительности

Базис	Х\	хг	хз	Хл	Хъ	Хв	Решение
z					5/2	1/2
хг	1/4					1/4
хз	3/2				1/2
Хл	-1				-1/2	-1/2

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

УПРАЖНЕНИЯ 4.5.1

1. В модели для фабрики TOYCO 20-минутная часть фонда рабочего времени третьей операции перенесена в фонд рабочего времени второй операции. Улучшит ли это оптимальное решение?

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

	Чб0>		'500^		f300^		f450N
а)		. Ь)		, с)		. d)
	,400,		Ш)		200,		ч350,

Воспользуйтесь возможностями анализа чувствительности, чтобы найти оп­тимальное решение.

3. Вернитесь к модели предприятия Reddy Mikks из примера 2.1.1. Ее симплекс-таблица с оптимальным решением приведена в примере 3.3.1. Используя анализ чувствительности, найдите новое оптимальное решение этой задачи, предпола­гая, что ограничения на сырье Ml и М2 составляют 28 и 8 тонн соответственно.

4. Птицефабрика Ozark содержит 20 000 цыплят, которых выращивают до 8-недель-ного возраста и затем отправляют на рынок. В следующей таблице представлен недельный расход корма на одного цыпленка в зависимости от его возраста.

Неделя __ 12 3 4 56 7 8

Расход корма (фунты) 0,26 0,48 0,75 1,00 1,30 1,60 1,90 2,10

Для того чтобы цыплята к 8-й неделе могли достичь определенного веса, их ра­цион должен удовлетворять определенным требованиям к калорийности. Хотя обычно список кормов очень большой, мы ограничимся тремя основными ин­гредиентами: известняк, зерно и соевая мука крупного помола. Требования к качественному составу рациона также ограничим только тремя показателя­ми: кальций, белок и клетчатка. В следующей таблице приведены обобщенные данные по их содержанию в кормовых ингредиентах.

	Содержание веществ (фунт/фунт ингредиента)	Стоимость
Ингредиент	Кальций	Белок	Клетчатка	(долл./фунт)
Известняк	0,380	0,00	0,00	0,12
Зерно	0,001	0,09	0,02	0,45
Соевая мука	0,002	0,50	0,08	1,60

4.5. Анализ чувствительности оптимального решения

Кормовой рацион должен содержать:

а) кальция — не менее 8 и не более 12%,

б) белка — не менее 22%,

в) клетчатки — не более 5%.

Составьте оптимальный кормовой рацион для каждой недели.

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

Пример 4.5.2

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

Г430+ОЛ 460 420

Переменная D, представляет изменение фонда рабочего времени первой операции по сравнению с текущим уровнем в 430 минут. Текущее базисное решение останет­ся допустимым, если все базисные переменные останутся неотрицательными. От­сюда получаем следующую систему неравенств.

		' 1
4)				'430+ D,4
х,	=
		,-2	2 1	К	ч 420,

100 + -^

230 20 -2D,

'0} 0

Первое неравенство х, > 0 порождает D, > -200, второе неравенство х, > 0 не зависит от D,, третье х₆ > 0 дает условие D, < 10. Таким образом, текущее базисное решение останется допустимым при выполнении неравенств -200 < D, < 10. Это эквивалентно следующему интервалу допустимости для фонда рабочего времени первой операции.

430 - 200 < Фонд рабочего времени операции 1 < 430 + 10

или

230 < Фонд рабочего времени операции 1 < 440.

Изменение значения целевой функции, соответствующее изменению D,, равно D_ly_i, где у, — стоимость (в долларах) одной минуты фонда рабочего времени первой опе­рации (т.е. двойственная цена этого ресурса).

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

Глава 4. Двойственность и анализ чувствительности

Для вычисления новых значений переменных воспользуемся значением D, = 400 -- 430 = -30. Далее получим следующее.

(1 ^ 100+ -(-30) 2

'85' 230 80

_v 20-2(-30))

Для вычисления нового значения целевой функции сначала найдем значения двойст­венных цен, для чего применим метод 1 из раздела 4.2.3, т.е. используем формулу

' Вектор-строка исходных ^ коэффициентов целевой функции при базисных переменных в оптимуме прямой задачи

'Оптимальные значения⁴ двойственных

переменных На основании этой формулы получаем

Обратная матрица ⁴ в оптимуме прямой задачи

(у₁._Л._Л) = (2.5,0)

f 1 2

-2

— —- 0

о 1 = (1,2,0).

Таким образом, стоимость одной минуты фонда рабочего времени первой операции равна у, = 1 долл. Тогда изменение оптимального дохода составит D_ly_l = -30 х 1 = = -30 долл. Следует помнить, что данная стоимость минуты фонда рабочего времени первой операции, равная у, = 1 долл., справедлива только для указанного выше ин­тервала изменения D_r Любое изменение, выходящее за этот интервал, приводит к недопустимому решению. В таком случае следует использовать двойственный сим­плекс-метод для поиска нового решения, если оно существует.

Аналогичную процедуру можно использовать при определении интервалов допус­тимости для переменных D₂ и D₃, равных изменению фондов рабочего времени вто­рой и третьей сборочных операций (см. упражнение 4.5.2.1). Определение интерва­лов допустимости для Dj, D₂ и D₃, как описано выше, и их соотношения с переменными у,, у_х и у₃ двойственной задачи корректны только тогда, когда эти ресурсы рассматриваются независимо друг от друга. Далее мы рассмотрим воз­можность одновременного изменения всех трех ресурсов, в этом случае текущий вектор коэффициентов правых частей ограничений необходимо заменить на вектор с элементами 430 + D,, 460 4- D₂ и 420 + D₃ (упражнение 4.5.2.2).

УПРАЖНЕНИЯ 4.5.2

1. Пусть в задаче о фабрике игрушек TOYCO переменные D₂ и D₃ представляют изменения фондов рабочего времени второй и третьей операций.

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

b) Определите стоимость одной минуты фондов рабочего времени второй и третьей операций.

4.5. Анализ чувствительности оптимального решения

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

d) Пусть фонд рабочего времени третьей операции изменен от текущего зна­чения 420 минут до 450 минут. Найдите новое оптимальное решение и оп­ределите соответствующее изменение значения целевой функции.

e) Пусть фонд рабочего времени третьей операции изменен от текущего зна­чения 420 минут до 380 минут. Найдите новое оптимальное решение и оп­ределите соответствующее изменение значения целевой функции.

2. Пусть в задаче о фабрике игрушек TOYCO изменения D₃, D₂ и D₃ фондов ра­бочего времени всех операций производятся одновременно.

a) Сформулируйте условия для переменных D₃, D₂ и D₃, гарантирующие до­пустимость текущего оптимального решения.

b) Пусть фонды рабочего времени всех трех операций изменены до 438,500 и 410 ми­нут соответственно. На основании условия, найденного в предыдущем пунк­те, покажите, что текущее базисное решение останется допустимым. С помощью двойственных цен найдите изменение значения целевой функции.

c) Пусть фонды рабочего времени всех трех операций изменены до 460, 440 и 380 минут соответственно. На основании условия, найденного в п. а, пока­жите, что текущее базисное решение будет недопустимым. С помощью двой­ственного симплекс-метода найдите новое оптимальное решение.

3. Вернитесь к модели фабрики игрушек TOYCO.

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

b) Пусть на второй сборочной операции оператор может ежедневно работать два часа сверхурочно с оплатой 45 долл. за каждый час. Стоимость дополнитель­ного машинного времени составляет 10 долл. за час. Будет ли экономически целесообразным использовать дополнительное время для второй операции?

c) На каких условиях экономически целесообразно использовать дополни­тельное время для третьей операции?

d) Предположим, что фонд рабочего времени первой операции увеличен до 440 минут, но любое превышение текущего фонда этой операции (430 ми­нут) стоит 40 долл. за час. Найдите новое оптимальное решение, включая значение целевой функции.

e) Предположим, что фонд рабочего времени второй операции уменьшен на 15 минут. Стоимость одного часа этой операции равна 30 долл. (в течение обычной рабочей смены). Будет ли экономически целесообразным уменьшение фонда рабочего времени для второй операции?

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

Глава 4. Двойственность и анализ чувствительности

	Ресурсы, необходимые для изготовления	Ежедневный
		одного изделия		лимит
Ресурс	Бумажник	Кошелек	Рюкзак	ресурса
Кожа (кв. футы)
Прошивка (часы)
Зачистка (часы)		0,5

Отпускная цена (долл.) 24 22 45

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

a) Ежедневный лимит кожи возрос до 45 кв. футов.

b) Ежедневный лимит кожи уменьшился на 1 кв. фут.

c) Фонд рабочего времени операции прошивки изменился до 38 часов.

d) Фонд рабочего времени операции прошивки изменился до 46 часов.

e) Фонд рабочего времени операции зачистки уменьшился до 15 часов.

f) Фонд рабочего времени операции зачистки увеличился до 50 часов.

g) Следует ли рекомендовать компании набор временных рабочих на опера­цию прошивки с оплатой 15 долл. в час?

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

	Количество комплектующих на одно	Лимит
	изделие		комплектующих
Ресурс	Модель 1	Модель 2	(шт.)
Резистор г
Конденсатор
Микросхема
Доход на одно изделие (долл.)

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

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

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

2х, + Зх₂ < 1200 (ограничение на резисторы), 2х, + х₂ < 1000 (ограничение на конденсаторы), 4х₂ < 800 (ограничение на микросхемы), х„ х₂>0.

4.5. Анализ чувствительности оптимального решения

Базис	*1	х2	S1	S2	S3	Решение
z			5/4	1/4
			-1/4	3/4
S3			-2
хг			1/2	-1/2

a) Определите статус каждого ресурса (комплектующего).

b) В терминах оптимального дохода определите стоимость одного резистора, одного конденсатора и одной микросхемы.

c) Найдите интервал применимости двойственных цен для каждого ресурса.

d) Найдите новое оптимальное решение при возрастании числа доступных резисторов до 1300.

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

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

g) Новый контракт позволяет компании закупить дополнительное число рези­сторов по 40 центов за единицу, но только при условии, что закупочная пар­тия составит не менее 500 единиц. Выгоден ли компании такой контракт?

6. Компания для производства двух видов продукции имеет ежедневный фонд рабочего времени 320 часов и 350 единиц расходных материалов (сырья). При необходимости компания может позволить 10 часов сверхурочной ра­боты с оплатой 2 долл. за час. На изготовление одной единицы продукции первого вида требуется 1 час рабочего времени и 3 единицы сырья, а на из­готовление одной единицы продукции второго вида — 2 часа рабочего вре­мени и 1 единица сырья. Доход от одной единицы этих продукций составля­ет соответственно 10 и 12 долл. Обозначим через и х₂ ежедневные объемы

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

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

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

х, + 2х₂ - х₃< 320 (ограничение на фонд рабочего времени),

3Xj + х₂< 350 (ограничение на сырье),

х₃ < 10 (ограничение на сверхурочные работы),

x_v х₂, х₃>0.

Базис	X)	хг	хз	Si	S2	S3	Решение
z				26/5	8/5	16/5
хг				3/5	-1/5	3/5
Х1				-1/5	2/5	-1/5
хз

Глава 4. Двойственность и анализ чувствительности

a) Найдите оптимальное решение этой задачи.

b) Определите двойственные цены ресурсов и их интервалы допустимости.

c) Найдите двойственные цены для фонда рабочего времени и сверхурочных работ. Могут ли эти цены быть одинаковыми? Обоснуйте.

d) Компания может увеличить объем сверхурочных работ за дополнитель­ную плату 2 долл. за час. Сколько часов такой сверхурочной работы мо­жет ввести компания?

e) Компания ежедневно может получать дополнительный объем сырья в 100 единиц по цене 1,50 долл. Стоит ли компании использовать этот резерв сырья? А если стоимость дополнительного сырья будет 2 долл. за единицу?

f) Предположим, что компания вынуждена сократить складские площади для сырья и поэтому ежедневно не может использовать более 200 единиц сырья. Найдите для этой ситуации новое оптимальное решение.

g) Предположим, что компания не может ежедневно использовать более 8 часов сверхурочной работы. Найдите новое оптимальное решение.

7. Достаточное правило допустимости. Это упрощенное правило можно ис­пользовать для проверки того, что одновременные изменения Д, Д,, D_m элементов вектора правых частей неравенств ограничений сохранят допусти­мость текущего решения. Предположим, что правая часть 6 г-го ограничения была изменена на Ь_: + Д., причем независимо от изменения правых частей дру­гих ограничений, и соответствующий интервал допустимости p_t < Д < q_t рассчи­тан так, как показано в примере 4.5.2. Очевидно, что p,S0 (q_t >0), поскольку величина p_t (q) соответствует максимальному уменьшению (возрастанию) значения b_t. Положим r_i равным или отношению Д/р,, или DJq_t, в зависимо­сти от того, будет ли величина Д отрицательной или положительной. По оп­ределению 0 < r_t < 1. Достаточное правило допустимости гласит, что для дан­ных изменений Д, D₂, D_m достаточным (не необходимым) условием того, что текущее решение останется допустимым, будет выполнение неравенства ^r\ ^{+ г}г + ••• ^+rm-l- Если это условие не выполняется, то текущее решение может быть как допустимым, так и недопустимым. Сформулированное пра­вило неприменимо, если Д выходят из своих интервалов допустимости.

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

Примените данное правило к задачам & и с из упражнения 2. В задачей дос­таточное правило допустимости не может подтвердить допустимость реше­ния, а в задаче с оно не применимо. Следующее упражнение должно подтвер­дить наши утверждения относительно этого правила.

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

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

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

2*, + х₂<6, х, + 2х₂<6, х„х₂>0.

4.5. Анализ чувствительности оптимального решения

a) Покажите, что оптимальное базисное решение содержит обе переменные х_г и х_г, и что интервалы допустимости для правых частей ограничений, полу­ченные при условии их независимости, имеют вид -3 < D, < 6 и -3 <D₂ < 6.

b) Предположим, что правые части ограничений одновременно увеличива­ются на величину Д > 0. Сначала докажите, что базисное решение остается допустимым для всех Д > 0. Далее покажите, что достаточное правило до­пустимости дает правильный ответ только тогда, когда 0 < Д < 3, не дает ответа при 3 < Д < 6, и не применимо — когда Д > 6.

9. Покажите, что достаточное правило допустимости из упражнения 7 является следствием неравенства

Обратная матрица Вектор правых частей ^

^оптимального решения

ограничении исходной задачи J

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

1. Новое ограничение является избыточным. Это означает, что новое ограниче­ние выполняется при текущем оптимальном решении.

2. Новое ограничение не выполняется при текущем оптимальном решении. В этом случае необходимо применить двойственный симплекс-метод, чтобы получить (или хотя бы попытаться получить) новое оптимальное решение.

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

Пример 4.5.3

Предположим, что фабрика игрушек TOYCO изменила конструкцию выпускаемых моделей, и теперь для их производства необходима четвертая сборочная операция. Ежедневный фонд рабочего времени этой операции составляет 500 минут. Время вы­полнения этой операции при сборке одной игрушки различных видов составляет со­ответственно 3, 1 и 1 минуту. В результате получаем новое ограничение: Зд:, 4- х₂ 4-4 х₃<500. Это ограничение является избыточным, поскольку оно удовлетворяется при текущем оптимальном решении х_г — 0, х₂ = 100 и х₃ = 230. Таким образом, теку­щее оптимальное решение остается неизменным.

Теперь предположим, что в модели фабрики игрушек TOYCO время выполнения новой четвертой операции составляет соответственно 3, 3 и 1 минуту при сборке одной игрушки каждого вида. В этом случае четвертое ограничение Зх, 4- Зх₂ 4-+ х, < 500 не будет избыточным, и текущее оптимальное решение ему не удовлетво­ряет. Мы должны ввести новое ограничение в симплекс-таблицу, где представлено текущее оптимальное решение.

Базис	XI	хг	Хз	Xi,	хъ	х6	Х7	Решение
z
хг	-1/4			1/2	-1/4
хз	3/2				1/2
Хб				-2

Глава 4. Двойственность и анализ чувствительности

Поскольку переменные х₂ и х₃ являются базисными, из л:₇-строки следует исклю­чить соответствующие им коэффициенты (т.е. надо сделать их нулевыми). Для это­го необходимо выполнить следующую операцию.

Новая лустрока = старая дг.-строка - [3 х (л:₂-строка) + 1 х (х,-строка)] В результате получим новую симплекс-таблицу.

Базис	Х1	хг	хз	х4	xs	х6	Х7	Решение
z
хг	-1/4			1/2	-1/4
хз	3/2				1/2
хв				-2
х7	9/4			-3/2	1/4			-30

С помощью двойственного симплекс-метода находим новое оптимальное решение л-, = 0, х₂ = 90, х₃ = 230 и z = 1330 долл. (проверьте!).

УПРАЖНЕНИЯ 4.5.3

1. Пусть в модели фабрики игрушек TOYCO время выполнения четвертой опе­рации составляет соответственно 4, 1 и 2 минуты при сборке одной игрушки каждого вида. Найдите оптимальное решение задачи, предполагая, что фонд рабочего времени четвертой операции составляет а) 570 минут, Ь) 548 минут.

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

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

Максимизировать z = 5л:, + 6х₂ + Зх₃

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

5 л:, + 5х₂ + Зх₃ < 50, х, + х₂ - х₃ < 20, 7л:, + 6х₂ - 9*3 < 90, 5х, + Ъх₂ + 5дг₃ < 35, 12л;, + 6х₂<90, л;₂-9л;з<20,

4.5. Анализ чувствительности оптимального решения