МУ ЭММ часть 1

31

Иными словами, каждой первоначальной переменной исходной задачи xj (1 j n) ставится в соответствие добавочная переменная уm+j, введенная в j-е неравенство двойственной задачи, а каждой добавочной переменной xn+i исходной задачи (1 i m), введенной в i-е неравенство исходной задачи, ставится в соответствие первоначальная переменная yi двойственной задачи.

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

Из вышеприведенных теорем следует вывод, что, решив одну из взаимно двойственных задач, т. е., найдя ее оптимальное решение и оптимум линейной формы, мы можем записать оптимальное решение и оптимум линейной формы другой задачи.

Рассмотрим еще одну теорему, выводы которой будут использованы в дальнейшем.

Теорема об оценках. Значения переменных уi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi системы ограничений-неравенств прямой задачи на величину Fmax , т. е.

yi Fmax .

bi

Эта теорема показывает еще одну связь между переменными прямой и двойственной задач. Поясним это подробнее.

Пусть (х1, х2, …, хj, …, xn) оптимальное решение прямой задачи, а (у1, у2, …, уi, …, уm) оптимальное решение двойственной задачи. Оптимальные значения целевых функций F и Z достигаются при подстановке компонент оптимального решения в их первоначальные выражения, т. е.

Fmax = c1x1 + … + cjxj + … + cnxn,

Zmin = b1y1 + … + biyi + … + bmym.

На основании первой теоремы двойственности (Fmax = Zmin) можно записать

c1x1 + … + cjxj + … + cnxn = b1y1 + … + biyi + … + bmym.

Отсюда следует, что

Fmax = b1y1 + … + biyi + … + bmym.

Поставим вопрос, как изменится величина Fmax, если в исходной задаче увеличить свободный член bi, в i-м ограничении-неравенстве на величину bi (1 i m). Величина Fmax, рассматриваемая теперь как

32

функция переменных b1, …, bi, …, bm, получит приращение Fmax. Частные производные этой функции по любому из этих аргументов имеют вид

Fmax yi .

bi

Учитывая, что функция Fmax линейная, получим Fmax = yi bi.

Пример. Рассмотрим экономическую интерпретацию двойственной задачи на примере (см. лабораторную работу №1) выше.

F = 15x1 + 10x2 max,

3x1 7x2 29,3x1 x2 18,

x1 6x2 23, x1, x2 0.

Пусть некая организация решила закупить все ресурсы рассматриваемого предприятия. При этом необходимо установить оптимальную цену на приобретаемые ресурсы у1, у2, у3, исходя из следующих объективных условий:

1)покупающая организация старается минимизировать общую стоимость ресурсов;

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

Согласно первому условию общая стоимость сырья выразится

величиной Z = 29у1 + 18у2 + 23у3 min.

Согласно второму требованию вводятся ограничения: на единицу продукции А расходуются три единицы первого ресурса (Электроэнергия) ценой у1, три единицы второго ресурса (Сырье) ценой у2, одна единица третьего ресурса (Оборудование) ценой у3. Стоимость всех ресурсов, расходуемых на производство единицы первого вида продукции, равна 3у1 + 3у2 + у3 и должна составлять не менее 15 единиц, т. е.

3у1 + 3у2 + у3 15.

В результате аналогичных рассуждений относительно производства продукции В получаем неравенство:

7у1 + у2 + 6у3 10.

По экономическому смыслу цены неотрицательные: y1, y2, y3 0. Получили симметричную пару взаимодвойственных задач.

33

F = 15x1				+ 10x2 max,				Z = 29у1 + 18у2 + 23у3 min,
3x			7x				29,	3y		3y			y		15,
	1					2	18,		1	y		2		3	10,
	3x x				2			7y			2	6y
x		1							1					3
			6x				23,	y1, y2, y3 0.
	1			2
	x1, x2				0;

Так как прямая задача решена симплекс-методом, опираясь на теоремы запишем решение двойственной задачи.

Задача линейного программирования имеет конечный оптимум, тогда двойственная к ней также имеет конечный оптимум. При этом

Fmax = 99,17, тогда Zmin = 99,17.

Установим соответствие между переменными исходной и двойственной задачи:

x1	x2	x3	x4	x5
y4	y5	y1	y2	y3

В результате решения данной задачи симплексным методом получено следующее решение (0,83; 4,17; 0; 0; 0), которое записываем из строки F таблицы оптимального решения..

Компоненты у1, у2, у3 оптимального решения двойственной задачи оценивают добавочные переменные х3, х4, х5 прямой задачи.

Равенство нулю переменной у3, в оптимальном решении свидетельствует о том, что переменная х5 положительна в оптимальном решении прямой задачи, или что подстановка компонент оптимального решения в первое неравенство системы ограничений прямой задачи не обращает его в строгое равенство. Переменные у1, у2 положительны, а соответствующие им переменные прямой задачи х3, х4 равны нулю в оптимальном решении прямой задачи. Подстановка компонент оптимального решения в первое и второе неравенства прямой задачи обращает их в строгие равенства.

Экономический смысл этого обстоятельства состоит в том, что ресурса Оборудования в задаче имеется с излишком и этим ресурсом не особенно дорожат, поэтому устанавливают для него нулевую оценку. А ресурсы Электроэнергия и Сырье являются дефицитным (целиком расходуются), поэтому эти виды оценивают некоторыми положительными оценками (у1 = 0,83, у2 = 4,17).

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

34

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

Электроэнергии или Сырья.

Согласно выводу из теоремы об оценках Fmax = yi bi.

В этой формуле уi компонента оптимального решения двойственной задачи, которые выступают как условные цены единицы i-го вида ресурса. Поэтому переменные двойственной задачи часто называют объективно обусловленными оценками.

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

Fmax = y3 b3 = 0 1 = 0,

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

Увеличим на 1 единицу запас Электроэнергии. Тогда

Fmax = y1 b1 = 0,83 1 = 0,83.

Увеличив на одну единицу запас ресурса Сырье, получим

Fmax = y2 b2 = 4,17 1 = 4,17.

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

				Таблица 12
	Объективно	Затраты ресурсов на единицу
Ресурс	обусловленные оценки		продукции
	ресурсов	Продукт С		Продукт D
Электроэнергия	0,83	6		4
Сырье	4,17	3		2
Оборудование	0	3		4
Цена единицу продукции		15		14

Решим эту задачу на основании свойства двойственных оценок: в оптимальный план задачи на получение максимума дохода может быть

m

включен лишь тот вариант, для которого величина aij yi ,

i 1

покрывается установленной ценой сj. Таким образом, характеристикой того или иного варианта служит разность

35

m

j aij yi cj , i 1

при этом если, j 0, то вариант выгоден; если. j > 0, то невыгоден. Для продукта С:

С = 0,83 ∙ 6 + 4,17 ∙ 3 + 0 ∙ 3 – 15 = 17,49 – 15 = 2,49

Поскольку С = 2,49 > 0, то делаем вывод, что продукт С невыгодно включать в план, так как затраты на его изготовление не покрываются получаемой прибылью.

Аналогично оценим прибыль продукта D:

D = 0,83 ∙ 4 + 4.17 ∙ 2 + 0 ∙ 4 – 14 = 11,66 – 14 = 2,34.

Поскольку D = 2,34 > 0, то делаем вывод, что продукт D невыгодно включать в план, так как затраты на его изготовление покрываются получаемой прибылью.

Решение задачи линейного программирования в Microsoft Excel

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

1. Осуществляем ввод данных в таблицу Excel согласно схеме, представленной на рис. 8.

Рис. 6. Заполнение схемы для решения задачи

Для переменных задачи x1 и x2 отведены ячейки B3 и C3. Эти ячейки называются рабочими или изменяемыми ячейками. В изменяемые ячейки значения не заносятся, в результате решения задачи в этих ячейках будет отражено оптимальное значение переменной.

В ячейку D4 необходимо ввести формулу для вычисления целевой функции задачи (дохода) F = 15x1 + 10x2. Формула в алфавите языка

Excel имеет вид: =B4*B3+C4*C3.

Израсходованное количество ресурса Электроэнергия составляет 3x1 + 7x2. В ячейку D7 (расход электроэнергии) вводится формула

=B7*$B$3+C7*$C$3.

Аналогично вводятся формулы расхода остальных ресурсов, а именно Сырья и Оборудования. В ячейку D8 (расход сырья) вводится

36

формула =B8*$B$3+C8*$C$3. В ячейку D9 (расход оборудования) вводится

формула =B9*$B$3+C9*$C$3.

В результате страница примет вид:

Рис. 7. Вид страницы с добавленными формулами

2. На вкладке Данные выбираем команду Поиск решения (если команда отсутствует в окне параметров Excel выберете Надстройки Перейти и установите Поиск решения) (рис. 8).

Рис. 8. Окно средства Поиск решения

В появившемся окне нужно оптимизировать целевую функцию в ячейке D4 до Максимум, изменяя ячейки переменных B3:C3. Выберите

метод решения: Поиск решения линейных задач симплекс-методом.

3. Чтобы ввести ограничения задачи, нажать кнопку Добавить. В появившемся диалоговом окне слева ввести адрес D7 (израсходованное количество Электроэнергии), затем выбрать знак ≤ и в правой части количество этого ресурса, равное 29 (или адрес ячейки E7). После ввода нажать кнопку Добавить и аналогично ввести второе и третье ограничения, а также условие положительности изменяемых ячеек.

37

Рис. 9. Добавление ограничения

4. После ввода ограничений получим заполненное окно Поиск решения

(рис. 10).

Рис. 10. Результат добавления ограничений

5. Для решения задачи в окне Поиск решения нажать кнопку Найти решение. Если решение найдено, появляется окно (рис. 11).

Рис. 11. Результаты Поиска решения

7. Для просмотра результатов выбираем тип отчета Результаты и нажимаем кнопку ОК. В рабочей книге появится лист Отчет по

38

результатам, который состоит из трех таблиц (рис. 12): в таблице 1 приводятся сведения о целевой функции, в таблице 2 приводятся значения переменных задачи, а в таблице 3 показаны результаты поиска для ограничений задачи.

Рис. 12. Отчет по результатам решения задачи

Из этих таблиц видно, что в оптимальном решении:

максимальный доход ($D$4) равен 99,17;

объем выпуска продукта А ($B$3) равен 5,39;

объем выпуска продукта В ($С$3) равен 1,83;

расход ресурса Электроэнергия ($D$7) равен 29, статус ресурса

связанный, разница (остаток ресурса) 0;

расход ресурса Сырье ($D$8) равен 18, статус ресурса связанный, разница (остаток ресурса) 0;

расход ресурса Оборудование ($D$9) равен 16,39, статус ресурса

не связанный, разница (остаток ресурса) 6,611.

Первоначальная таблица рабочей книги заполняется результатами, полученными при решении (рис. 13).

Рис. 13. Результат поиска решения

39

8. Если в окне для просмотра результатов выбрать тип отчета Устойчивость, нажимаем кнопку ОК. В рабочей книге появится лист Отчет по устойчивости, который позволяет проанализировать изменение параметров задачи (рис. 14).

Рис. 14. Отчет по устойчивости решения задачи

Отчет состоит из двух таблиц: в таблице 1 приводятся сведения о чувствительности решения к изменению коэффициентов целевой функции (cj), в таблице 2 приводятся сведения о чувствительности решения задачи к изменению запасов сырья (bi).

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

коэффициенту cj, допустимое увеличение ( c(j ) ) – максимально возможное увеличение коэффициента cj, а допустимое уменьшение

( c(j ) ) максимально возможное уменьшение коэффициента cj.

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

с1 = c1 c1( );c1 c1( ) 15 10,71;15 15 4,29;30 .

Для второго коэффициента целевой функции с2:

с2 = c2 c2( );c2 c2( ) 10 5;10 25 5;35 .

Таким образом, найденный оптимальный план выпуска продукции не будет меняться при изменении цены на единицу продукции А в диапазоне от 4,29 до 30 денежных единиц и цены на единицу продукции В в диапазоне от 5 до 35 денежных единиц.

ограничение правая часть

40

Чувствительности решения задачи к изменению запасов ресурсов

целесообразно проводить для связанных ресурсов (для примера Электроэнергия и Сырье). Отчет по устойчивости определяет интервалы изменения каждого из свободных членов системы ограничений (bi) исходной задачи линейного программирования, в которых оптимальный план двойственной задачи не меняется.

Свойство двойственных оценок утверждает, что изменение значений величины bi приводит к увеличению или уменьшению Fmax и это изменение определяется величиной yi.

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

отражает значение свободных членов системы ограничений bi,

допустимое увеличение ( bi( ) ) – максимально возможное увеличение

коэффициента bi, а допустимое уменьшение ( bi( ) ) максимально

возможное уменьшение коэффициента bi.

Для ресурса Электроэнергия получен следующий диапазон изменения b1:

b1 = b1 b1( );b1 b1( ) 29 11;29 7 18;36 .

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

F( ) = b1( ) yi = 11 0,833 = 9,163 денежных единиц;F( ) = b1( ) yi = 7 0,833 = 5,831 денежных единиц.

При изменении запасов ресурса Электроэнергия в пределах от 18 до 36 единиц значение целевой функции принимает значения от

90,01 (99,17 – 9,16) до 105 (99,17 + 5,83) денежных единиц.

Для ресурса Сырье получен следующий диапазон изменения b2: b2 = b2 b2( );b2 b2( ) 18 10,82;18 11 7,18;29 .

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

F( ) = b1( ) yi = 10,82 4,17 = 45,12 денежных единиц;

F( ) = b1( ) yi = 11 4,17 = 45,87 денежных единиц.

При изменении запасов ресурса Сырье в пределах от 7,18 до 29 единиц значение целевой функции принимает значения от

54,05 (99,17 – 45,12) до 145,04 (99,17 + 45,87) денежных единиц.