Первая теорема двойственности.

а) Если одна из пары двойственной задачи разрешима, то разрешима и другая, причем Z_max = F_min.

б) если одна из пары двойственной задачи неограниченна сверху (Z_max = + ∞), то другая задача неразрешима, по причине несовместимости системы ограничений в области допустимых решений.

Экономический смысл теоремы: план производства Х и набор цен ресурсов У оказывается оптимальным тогда и только тогда, когда прибыль от продукции, найденная при внешних ценах с_j равна затратам на ресурсы по внутренним ценам у_i.

Вторая теорема двойственности. Для того, чтобы планы Х и У пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:

. (12)

Отсюда следует, что положительными (ненулевыми) компонентами оптимального решения одной из возможных двойственных задач соответствует нулевые компоненты оптимального решения другой задачи, т.е. для любого i и j при х*_j>0 → у*_m+j = 0 и, наоборот, при у*_j>0 → х*_n+i = 0.

Экономический смысл: если по некоторому оптимальному плану Х производство расходов i-го ресурса строго меньше его запаса b_i то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его i-я компонента строго больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда вывод: дефицитный ресурс имеет положительную оценку, а ресурс избыточный нулевую оценку.

Третья теорема двойственности (об оценках):

Двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена соответствующего ограничения: (13)

или ΔF = Δb_i*y_i.

Свойство 1. Оценка является мерой дефицитности ресурсов. Чем выше величина оценки y_i, тем выше дефицитность i -го ресурса.

Свойство 2. Оценка есть мера влияния ограничений на значение целевой функции. Величина двойственной оценки какого-либо ресурса показывает, насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на единицу.

Свойство 3. Оценки есть мера относительной взаимозаменяемости ресурсов. Например, отношение y_i/y_k показывает, сколько единиц k -го ресурса может быть высвобождено при увеличении объема i- го ресурса на единицу, для того чтобы максимум целевой функции остался на прежнем уровне.

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

, (14)

вариант производства является выгодным, если Δ_j > 0 – вариант невыгоден, где a_ij число единиц нового ресурса.

1.5.3. Объективно обусловленные оценки и их смысл

Пример 25. Для изготовления двух видов продукции Р₁ и Р₂ используются четыре вида ресурсов. Запасы ресурсов, нормы затрат на 1ед. продукции данного вида и цена на 1ед. продукцию каждого вида приведены в табл. 16:

Таблица 16

Вид ресурса	Число единиц ресурсов на 1 ед. прод.	Запас
Р1	Р2
S1
S2
S3	-
S4		-
Цена 1ед. прод.

Решение. 1. Составим исходную и двойственную модель.

F = 2х₁ + 3х₂à max Z = 18y₁ + 16y₂ + 5y₃ + 21y₄ à min

x₁ + 3x₂ ≤ 18 y₁ + 2y₂ + 3y₄ ≥ 2

2x₁ + x₂ ≤ 16 3y₁ + y₂ + y₃ ≥ 3

x₂ ≤ 5 любое y_i ≥ 0

3x₁ ≤ 21

х₁ ≥ 0, х₂ ≥ 0.

Экранная форма для ввода условий задачи вместе с введенными в нее исходными данными представлена на рис. 17. В ячейку D4, в которой будет отображаться значение ЦФ, необходимо ввести формулуСУММПРОИЗВ($B$2:$C$2;B3:C3),по которой это значение будет рассчитано. В ячейку D7 вводим формулуСУММПРОИЗВ($B$2:$C$2;B7:C7) и растягиваем вниз в ячейки D8; D9; D10. Дальнейшие действия производим в окне «Поиск решения»
( рис. 18).

Рис. 17. Экранная форма после ввода всех необходимых формул

Рис. 18. Окно "Поиск решения" после ввода всех данных

Запускаем решение задачи путем нажатия кнопки «Выполнить», выбирая два отчета.

После этого в экранной форме появляется оптимальное решение задачи (рис. 19).

Рис. 19. Экранная форма оптимального решения

Таким образом, оптимальное решение Х = (6; 4); F_max = 24 рублей. Отчет по устойчивости (рис. 20) дает значение теневой цены
У_опт = (0,8;0,6;0;0).

Рис. 20. Отчет по устойчивости

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

Предельное изменение стоимости (рис. 20):

с₁ = 2 → → .

с₂ = 3→ → .

Предельное изменение по ресурсам (рис. 20):

b₁ = 18 → ; ;

b ₂ = 16 → ; 11 ≤ b₂ ≤ ;

b ₃ = 5→ ; ;

b ₄ = 21→ ; .

2. Дадим экономическую интерпретацию двойственных задач.

2.1. Дефицитность продукции и ресурсов

Так как х₁ = 6 и х₂ = 4 > 0, то выпускать продукцию Р₁ и Р₂ рентабельно (если бы основная переменная х_i равнялась нулю, то продукцию Р_i выпускать было бы не целесообразно). На рис. 21 статус «связан» означает, что данный ресурс является дефицитным. Следовательно, ресурсы S₁ и S₂ являются дефицитными, а ресурсы S₃ и S₄ являются недефицитными

Рис. 21. Отчет по результатам

Основные переменные у₁, у₂ положительны, следовательно ресурсы S₁ и S₂ являются дефицитными, основные переменные у_3, у₄ равны нулю, тогда ресурсы S₃ и S₄ являются недефицитными. Так как у₁ > у₂, то по третьей теореме двойственности (свойство 1) ресурс S₁ более дефицитен, чем S₂. Следовательно, наиболее выгодно увеличение объемов ресурса S₁.

2.2. Прирост прибыли при изменении ресурсов.

Увеличение S₁ на одну единицу () увеличит прибыль по третьей теореме двойственности на
ΔF₁ = 4/5*1 = 4/5 руб., т.е. общая стоимость F = 24 + 0,8 = 24,8 руб.

Увеличение S₂ на одну единицу () увеличит прибыль на ΔF₂ = 3/5*1 = 3/5 руб., т.е. F = 24 + 0,6 =
= 24,6 руб.

Увеличение S₃ и S₄ не изменит прибыль, так как
ΔF₃ = 0*1=0; ΔF₄ = 0*1 = 0.

Увеличение одновременно первого и второго ресурса на 5 единицы приведет к увеличению прибыли на ΔF = 4/5*5+3/5*5 =
= 7 руб., т.е. общая стоимость F = 24 + 7 = 31 руб.

2.3. Взаимозаменяемость ресурсов. Если бы S₁ уменьшилось на 1 единицу, то падение выручки можно компенсировать увеличением S₂ (свойство 3) на Δв₂ = у₁/у₂ * Δв₁ = = 4/3. Тогда новые запасы ресурсов составят: ;

2.4. Выпуск дополнительной продукции.

Пусть имеется возможность выпуска третьей продукции, причем а₁₃ = 3, а₂₃ = 2, а₃₃ = 4, а₄₃ = 1, с₃ = 3. Ответим на вопросы: дает ли это прибыль? Какой должна быть цена на Р₃, чтобы производство оставалось рентабельным?

По свойству 4 Δ = а₁₂у₁ + а₂₃у₂ + а₃₃у₃ + а₄₃у₄ – 3 =
= 3*4/4 + 2*3/5 + 4*0 + 1*0 – 3 = 0,6 > 0, следовательно, производство дополнительной продукции невыгодно. Цена должна быть: 3*4/4 + 2*3/5 + 4*0 + 1*0 – с < 0, не менее 3,6 руб.

2.5. Прирост прибыли при изменении стоимости продукции.

Пусть стоимость первой продукции увеличиться 3 рубля, тогда прибыль изменится на Δ F_max = Δс₁х₁ = 6*5 = 30 руб.

Пусть стоимость второй продукции увеличиться 2 рубля, тогда прибыль изменится на Δ F_max = Δс₂х₂ = 4*2 = 8 руб.

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

1. Для изготовления четырех видов продукции используются три вида ресурсов. Запасы ресурсов; нормы затрат на 1ед. продукции данного вида и цена на 1ед. продукцию каждого вида приведены в таблице:

Вид ресурса	Число единиц ресурсов на 1 ед. прод.	Запас
Р1	Р2	Р3	Р4
S1- трудовые ресурсы
S2 - полуфабрикаты
S3 - станочное оборудование
Цена 1ед. прод.

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

b) Определить дефицитность ресурсов и рентабельность продукции.

c) Какой ресурс более дефицитен и какова его взаимозаменяемость другими ресурсами.

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

e) Как изменится прибыль, если трудовые ресурсы уменьшить на 100 единиц, а оборудование увеличить на 50 единиц. Каково при этом оптимальное решение.

f) Найти предельное изменение стоимости.

g) Как изменится прибыль, если стоимость третьей продукциии уменьшить на 10 единиц, а четвертой увеличить на 20 единиц.

h) Определить выгодность выпуска дополнительной продукции, если затраты составляют на трудовые ресурсы 5 ед., полуфабрикаты - 3 ед, оборудования – 1 ед. Стоимость продажи при этом планируется 100 руб.

i) Если выпуск дополнительной продукции невыгоден, то какова должна быть цена при реализацию чтобы выпуск был рентабелен.

j) Если выпускать нерентабельную продукции в объеме 10 штук, то как при этом меняется прибыль.

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

Тип	Нормы расхода сырья на одно изделие	Запасы
сырья	А	Б	В	Г	сырья
I
II
III
Цена изделия

a) Определить план выпуска продукции из условия максимизации его стоимости.

b) Определите ценность каждого ресурса (двойственные оценки) и его приоритет при решении задачи увеличения запаса ресурсов.

c) Определите суммарную стоимостную оценку ресурсов, используемых при производстве единицы каждого изделия. Выпуск какой продукции нерентабелен?

d) Насколько уменьшится стоимость выпускаемой продукции при принудительном выпуске единицы нерентабельной продукции?

e) Определить, как изменятся общая стоимость продукции и план ее выпуска при увеличении запасов сырья I и II вида на 4 и 3 единицы соответственно и уменьшении на 3 единицы сырья III вида.

f) Определить целесообразность включения в план изделия «Д» ценой 10 ед., на изготовление, которого расходуется по две единицы каждого вида сырья.

3. При изготовлении изделий И₁ и И₂ используются сталь и цветные металлы, а также токарные и фрезерные станки. По технологическим нормам на производство единицы изделия И₁ требуется 300 и 200 станко-часов соответственно токарного и фрезерного оборудования, а также 10 и 20 кг соответственно стали и цветных металлов. Для производства единицы изделия И₂ требуется 400, 100, 70 и 50 соответствующих единиц тех же ресурсов. Цех располагает 12400 и 6800 станко-часами соответственно токарного и фрезерного оборудования и 640 и 840 кг соответственно стали и цветных металлов. Прибыль от реализации единицы изделия И₁ составляет 6 руб. и от единицы изделия И₂ – 16 руб.

a) Постройте математическую модель задачи, используя в качестве показателя эффективности прибыль и учитывая, что время работ станко-часы фрезерных станков должны быть, использовано полностью.

b) Определите ценность каждого ресурса (двойственные оценки) и его приоритет при решении задачи увеличения запаса ресурсов.

c) Определите суммарную стоимостную оценку ресурсов, используемых при производстве единицы каждого изделия. Выпуск, какой продукции нерентабелен?

d) Насколько уменьшится стоимость выпускаемой продукции при принудительном выпуске единицы нерентабельной продукции?

e) Определить, как изменятся общая стоимость продукции и план ее выпуска при уменьшении стали и цветные металлы на 200 и 300 кг соответственно и увеличении на 500 и 250 станко-часов токарных и фрезерных станков.

f) Определить целесообразность включения в план изделия И3 ценой 15 ед., на изготовление, которого расходуется по одной единицы каждого вида сырья.

4. Для сохранения нормальной жизнедеятельности человек должен в сутки потреблять белков не менее 120 условных единиц (усл. ед.), жиров – не менее 70 и витаминов – не менее 10 усл. ед. Содержание их в каждой единице продуктов П1 и П2 равно соответственно (0,2; 0,075; 0) и (0,1; 0,1; 0,1) усл. ед. Стоимость 1 ед. продукта П1 – 2 руб., П2 –3 руб.

a) Определить количество продукции из условия минимизации его стоимости.

b) Определите ценность питательных веществ (двойственные оценки) и их приоритет при решении задачи минимизации стоимости.

c) Какая продукция нерентабелена?

d) Определить, как изменятся общая стоимость продукции и план ее выпуска при увеличении витаминов I и II вида на 3 и 6 единицы соответственно и уменьшении на 2 единицы сырья III вида.

e) Определить целесообразность включения в план продукта «П3» ценой 9 ед., на изготовление, которого расходуется по две единицы каждого вида питательных веществ.

5. Некоторая редакция в своей деятельности ограничена финансовыми ресурсами в размере 50 000 руб., лимитами на бумагу и переплетные материалы в объеме 70 000 листов и пропускной способностью полиграфической базы, равной
60 000 оттисков. Зная удельные (на ед.объема издательских листов) расходы ресурсов и выручку от реализации ед. объема каждого из четырех видов альбомов, редакция должна так составить план выпуска альбомов, чтобы максимизировать прибыль от их реализации и уложиться при этом в лимитированные ресурсы.

Альбомы
Показатели
Удельные финансовые расходы, руб./изд. лист	1/3		1/2	1/4
Удельные расходы ресурсов бумаги, лист./изд.лист			I
Удельные затраты полиграфических мощностей, оттиск./изд.лист				I
Выручка от реализации ед. объема, руб./ изд.лист

a) Как изменится решение задачи, если туристическое агентство оформило заказ на выпуск альбомов I вида в размере 8000 экз.?

b) Проанализируйте использование ресурсов в оптимальном плане.

c) Как повлияет на прибыль редакции решение оставить сэкономленную ранее бумагу и переплетные материалы в объеме 5000 листов в ее распоряжении?

d) Выгодно ли редакции закупить (в счет будущей прибыли) 20 000 листов бумаги и переплетных материалов по цене 4 руб. за 1000 листов?