Лекция 7. Экономико-математический анализ решения задач линейного программирования

План

1. Интервалы устойчивости ресурсов.

2. Интервалы устойчивости цен на продукцию.

3. Анализ целесообразности производства.

1. Двойственные оценки являются показателем влияния ограничений на значение целевой функции.

Поэтому представляет практический интерес вычислить предельные зна-

чения правых частей системы ограничений bi

(нижней и верхней границы запа-

JG*

сов ресурсов), при которых оптимальный план X

останется неизменным.

Пример 1. Для исходной задачи ЛП из примера табл. 1 найти интервалы устойчивости ресурсов.

Табл. 1. Симметричная пара для примера о строительных смесях

Исходная задача	Двойственная задача
Z = 4 x 1 + 5 x 2 → max; ⎧0,25 x 1 + 0,6 x 2 ≤15, ⎪ ⎨0,25 x 1 + 0,2 x 2 ≤ 7, ⎪0,5 x 1 + 0,2 x 2 ≤12; x 1 ≥ 0 ,x 2 ≥ 0.	F =15 y 1 + 7 y 2 +12 y 3 → min; ⎧0,25 y 1 + 0,25 y 2 + 0,5 y 3 ≥ 4, ⎨ ⎩0,6 y 1 + 0,2 y 2 + 0,2 y 3 ≥ 5; y ≥ 0 ,y ≥ 0 ,y ≥ 0.
JJG* X = (12; 20), Z max =148.	JG* Y = (4,5;11,5; 0), F min =148.

y

y

y

⎩ 1 2 3

Решение. Оптимальное решение двойственной задачи имеет вид:

y

y

* = 4,5;

* =11,5;

* = 0. Т.к.

* > 0,

* > 0 и

* = 0, то согласно второй

теореме двойственности первые два ограничения исходной задачи при подста-

y

JJG*

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

X = (12; 20)

обратятся в равенства, а третье ог-

раничение останется неравенством.

Имеем систему:

⎧0,25 x 1 + 0,6 x 2 =15;

⎪

⎩

⎨0,25 x 1 + 0,2 x 2 = 7;

⎪0,5 x 1 + 0,2 x 2 ≤12.

Правая часть первого ограничения исходной задачи (число 15) – это величина

запаса первого ресурса. Заменим число 15 на неизвестный параметр b 1:

⎧0,25 x 1 + 0,6 x 2 = b 1;

⎪

⎩ 1 2

⎨0,25 x 1 + 0,2 x 2 = 7;

⎪0,5 x + 0,2 x ≤12.

Из первых двух равенств выразим неизвестные

ченные выражения в третье неравенство системы:

⎧

⎪ x 1 = −2 b 1 + 42;

⎪

x 1,

x 2 и подставим полу-

⎪ x = 5 b

− 35;

⎨ 2 1

⎪ 2

⎪− 1 b

+ 35 ≤12.

2 1 2

Для первых двух равенств учтём тот факт, что

приобретёт вид:

x 1 ≥ 0 и

x 2 ≥ 0. Система

⎧

⎪−2 b 1 + 42 ≥ 0;

⎪

⎪5 b

− 35 ≥ 0;

⎨ 1

⎪

⎪− 1 b

+ 35 ≤12.

Решим её относительно b 1:

2 1 2

⎧ b 1 ≤ 21;

⎪

⎩ 1

⎨ b 1 ≥ 7;

⎪ b ≥11.

Интервал устойчивости 1-го ресурса b 1 ∈[11; 21],

Аналогичными действиями определим интервал устойчивости величины

запаса b 2

2-го ресурса:

⎧0, 25 x 1 + 0, 6 x 2 = 15;

⎪

⎩ 1 2

⎨0,25 x 1 + 0,2 x 2 = b 2;

⎪0,5 x + 0,2 x ≤12.

Указание. Студентам выполнить самостоятельно и получить b 2 ∈[5; 7,8].

Краткое решение:

⎧

⎪ x 1 = 6 b 2 − 30;

⎪

⎧

⎪6 b 2 − 30 ≥ 0;

⎪

⎧ b 2 ≥ 5;

⎪ x 5 b

75;

⎪ 5 75 ⎪

=− +

⎨− b

+ ≥ 0;

b ≤15;

b ∈[5; 7,8].

⎨ 2 2 2 2

2 2 2

⎨ 2 2

⎪ ⎪ ⎪ b

≤ 7,8.

⎪ 5 b

− 15 ≤12.

⎪ 5 b

− 15 ≤12. ⎩ 2

2 2 2

2 2 2

Определим интервал устойчивости для 3-го ресурса. Для этого правую часть третьего ограничения (число 12) заменим на неизвестный параметр b 3:

⎧0,25 x 1 + 0,6 x 2 =15;

⎪

⎩ 1 2 3

⎨0,25 x 1 + 0,2 x 2 = 7;

⎪0,5 x + 0,2 x ≤ b.

Найдём из первых двух уравнений неизвестные

неравенство системы. Получим:

x 1,

x 2 и подставим их в третье

⎧ x 1 =12;

⎪

⎩ 3

⎨ x 2 = 20;

⎪10≤ b.

Интервал устойчивости 3-го ресурса: b 3 ∈[10; +∞).

Заметим, что вычисленные значения неизвестных

JG*

x 1,

x 2 совпадают с оп-

тимальным решением исходной задачи ЛП

X = (12; 20). Поэтому можно было

сразу подставить значения решить его.

x 1 =12 и

x 2 = 20

в последнее неравенство, а затем

Ответ: Интервал устойчивости 1-го ресурса:

b 1 ∈[11; 21]. Интервал устой-

чивости 2-го ресурса:

b 3 ∈[10; +∞).

b 2 ∈[5; 7,8]. Интервал устойчивости 3-го ресурса:

2. Благодаря теории двойственности можно проводить и другие виды анализа.

Интервалом устойчивости цены за единицу j -й продукции (j =1, n)

; c

c j j

называется отрезок

[ min

max ]

со следующими свойствами. Если цена

c ∈[ c

min; c

max ], а цены на остальные виды продукции зафиксированы, то оп-

j j j

тимальный план выпуска продукции

JG*

X

останется неизменным.

Пример 2. Для исходной задачи ЛП из табл. 1 найти интервалы устойчи-

вости цен на продукцию.

Решение. Оптимальное решение исходной задачи содержит положитель-

ные числа:

x * =12;

x * = 20. Согласно второй теореме двойственности, два ог-

раничения двойственной задачи

0,25 y 1 + 0,25 y 2 + 0,5 y 3 ≥ 4,

0, 6 y 1 + 0, 2 y 2 + 0, 2 y 3 ≥ 5

должны обратиться в точные равенства.

Кроме того,

y * = 0. Поэтому получим систему:

⎧0,25 y 1 + 0,25 y 2 + 0,5 y 3 = 4;

⎨

⎧0,25 y 1 + 0,25 y 2 = 4;

⎪

⎨0,6 y 1 + 0,2 y 2 = 5;

⎩0, 6 y 1 + 0, 2 y 2 + 0, 2 y 3 = 5.

⎪ y = 0.

⎩ 3

Правая часть первого ограничения двойственной задачи (число 4) – это

цена единицы первой продукции. Заменим число 4 на неизвестный параметр

⎧0,25 y 1 + 0,25 y 2 = c 1;

⎨

⎩0,6 y 1 + 0,2 y 2 = 5.

c 1:

Для определения интервала устойчивости находим из системы неизвест-

ные

y 1 и

y 2:

⎧ y = 25 − 4 c 1;

⎪ 1 2

⎨

y

⎪

⎩⎪ 2

= 12 c 1 − 25.

2

Т.к.

y 1 ≥ 0 и

y 2 ≥ 0, то имеем систему неравенств, которую решаем относи-

тельно

c 1:

⎧25 − 4 c 1 ≥ 0;

⎪ 2

⎨

Получено решение:

⎪12 c 1 − 25 ≥ 0.

⎪⎩ 2

⎧ c 1 ≤ 6,25;

⎪

⎪

⎨ c ≥ 2 1.

⎩ 1 12

Т.о. интервал устойчивости цены c 1

⎡2 1; 6, 25⎤.

на первую продукцию составляет:

12 ⎥⎦

Указание. Студентам самостоятельно определить интервал устойчивости

цены c 2

на вторую продукцию и получить [3,2;9,6].

Краткое решение:

⎧ y = 5 c 2 −16;

⎧5 c 2 −16 ≥ 0;

⎧0,25 y 1 + 0,25 y 2 = 4; ⎪ 1 2 ⎪ 2

⎨ ⎨ ⎨

⎧ c 2 ≤ 9,6;

⎨

y

⎩0,6 y 1 + 0,2 y 2 = c 2.

Пример 2 выполнен.

⎪

⎩⎪ 2

= 48 − 5 c 2.

⎪48 − 5 c 2

⎪⎩ 2

≥ 0.

⎩ c 2 ≥ 3,2.

3. Двойственные оценки являются показателем целесообразности производ-

ства новых видов продукции.

Допустим, имеется возможность начать выпуск продукции

Pn +1. Нормы

расхода ресурсов на производство одной единицы продукции составляют соот-

ветственно

a 1, n +1;

a 2, n +1;…;

am, n +1. Цена единицы продукции

cn +1.

Целесообразность производства определяется прибылью от одной едини-

цы продукции:

n +1

n +1

m

∑ i, n +1 i

∆ = c

− a

i =1

⋅ y *.

Если

∆ n +1 > 0, то производство прибыльное,

∆ n +1 = 0

– безубыточное,

∆ n +1< 0

– убыточное.

Пример 3. Пусть для исходной задачи ЛП из табл. 1 известно, что имеет-

ся возможность начать выпуск продукции

P 3. Нормы расхода ресурсов на про-

изводство одной единицы продукции составляют соответственно

a 13 = 0,3;

a 23 = 0,3;

a 33 = 0,4. Цена единицы продукции

c 3 = 4,7

тыс. грн.

P 3.

Требуется сделать выводы о целесообразности производства продукции

Решение. Целесообразность производства определяется размером при-

были от одной единицы продукции:

*

3

∆3 = c 3

− ∑

i =1

ai 3

⋅ yi = 4,7 − (0,3⋅ 4,5 + 0,3⋅11,5 + 0,4⋅ 0) = 4,7 − 4,8 = −0,1(тыс. грн).

Т.к.

∆3 < 0, то производство убыточное. Производить продукцию

P 3 не

целесообразно. Пример 3 выполнен.

Двойственные оценки также используют как инструмент сопоставления условных затрат и результатов.

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

ся, как

(∆ Z

) = ∆ b

⋅ y *. Если

(∆ Z

) > 0, то доход увеличится на

(∆ Z)

max

i i i

max i

max i

денежных единиц, в противном случае – уменьшится.

Суммарное влияние изменений количества всех ресурсов вычисляется

так:

JGJG*

∆ Z max = ∆ B ⋅ Y

m

= ∑ (∆ Z max) i.

i =1

Рассмотрим возможность дополнительной закупки i -го ресурса в объёме

+ +

∆ bi

по цене

pi за единицу ресурса. Затраты на приобретение составят

∆ bi

⋅ pi.

i i

Приращение дохода составит

∆ b + ⋅ y *.

Если приращение дохода превысит затраты на приобретение, т.е.

i i i i

∆ b + ⋅ y * − ∆ b + ⋅ p

> 0, то закупка целесообразна. В противном случае – нет.

По-другому,

∆ b + ⋅ y * − ∆ b + ⋅ p

= ∆ b + (y * − p).

i i i i i i i

i i

Знак данного выражения зависит от знака разности

(y * − p). Следовательно,

y

i

если теневая цена

* превышает цену

pi, то закупка целесообразна.

Дата добавления: 2014-01-07