Экономическая интерпретация двойственной задачи. Третья теорема двойственности (об оценках). Пример использования объективно обусловлен

Министерство образования и науки Российской Федерации

Филиал ФГБОУ ВПО «Уральский государственный экономический университет» в г. Нижнем Тагиле

Институт непрерывного образования

 

 

 

 

 

 

КОНТРОЛЬНАЯ РАБОТА

по дисциплине:

Методы оптимальных решений

 

на тему:

Экономическая интерпретация двойственной задачи. Третья теорема двойственности (об оценках). Пример использования объективно обусловленных оценок для принятия оптимальных решений.

 

 

 

Факультет	Исполнитель: Лысов И.Л.
Специальность	Группа: 1Ф1
Кафедра	Научный руководитель:   канд. мат. наук, доцент Лубарев В.В.
Дата защиты
Оценка

Нижний Тагил

   2014

СОДЕРЖАНИЕ

 

 

 

Введение            3

1 Экономическая интерпретация  двойственной задачи    4

2 Третья теорема двойственности  об оценках      9

3 Пример использования объективно обусловленных оценок для принятия оптимальных решений                 12

Заключение                  16

Список использованной литературы              17

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

 

 

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

Если задача в математическом и линейном программировании – результат моделирования конкретной экономической (производственной) ситуации, то двойственность и та информация, которую двойственность порождает, позволяют провести глубокий анализ моделируемой ситуации (моделируемого объекта), выявить узкие места, тенденции динамики объекта, выразив эти факторы в количественной форме.

За такого рода анализом закрепился термин – «экономико-математический анализ». Профессионально сделанные пакеты прикладных программ, решающие задачи математического или линейного программирования, обычно выдают в форме удобных распечаток всю совокупность информации, необходимую для экономико-математического анализа.

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

 

 

1 ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ  ДВОЙСТВЕННОЙ ЗАДАЧИ

 

Двойственность – это принцип, заключающийся в том, что для каждой задачи линейного программирования можно сформулировать двойственную задачу [1, с. 87].

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

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

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

Традиционная экономическая интерпретация двойственной задачи базируется на модели простейшей задачи производственного планирования. Для экономической интерпретации двойственной задачи будем полагать, например, что прямая задача – задача распределения ресурсов. Предположим, что в производстве используется k различных видов ресурсов, объем которых ограничен величинами bi. Может производиться n видов продукции, величина выпуска которых характеризуется переменными хi. Известны нормы затрат каждого ресурса на единицу каждого вида продукции – аij, а также стоимостная оценка единицы продукции – сj [2, с. 68].

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

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

Следующая теорема устанавливает связь между решениями двух задач.

Пусть xi*,...,хn* и у1*,...,yk* - оптимальные планы двойственных задач. Тогда

1. Если ai1,xi* +...+аinхn* < bi (i ), то уi* = 0.

2. Если уi* >0 (i ),то ai1x1* +...+аinхn* =bi

Экономическое содержание: двойственные оценки не полностью используемых ресурсов всегда равны нулю; положительную двойственную оценку могут иметь лишь ресурсы, полностью используемые в оптимальном плане.

3. Если а1jy1* +...+akjyk* >сj (j ),то хj*=0.

4. Если хj* > 0 (j ),то а1jу1* +...+ akjyk* =сj.

Экономическое содержание: если по двойственным оценкам производство данной продукции убыточно, то выпускать ее нерационально, и она не вошла в оптимальный план; если данный вид продукции вошел в оптимальный план, то двойственная оценка затрачиваемых ресурсов равна ее цене и производство продукции по оценкам оправдано [2, с. 71].

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

Исходная задача. Найти матрицу Х = (x1, x2, …, xn), которая удовлетворяет системе ограничений AX>An, X>0 и минимизирует линейную функцию Z = CX.

Двойственная задача. Найти матрицу Y = (y1, y2, …, yn), которая удовлетворяет системе ограничений YA £ C, Y ³ 0 и максимизирует функцию F = YAm.

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

Исходная задача: Z = x1 + 2x2 + 3x3 →min при ограничениях:

 

          (1)

 

Очевидно, для того чтобы записать двойственную задачу, сначала необходимо систему ограничений исходной задачи привести к виду AX>An. Для этого второе неравенство следует умножить на -1.

Двойственная задача. Найти максимум функции f = 2y1+ 3y2 + 6y3 + 3y4 при ограничениях

 

         (2)

 

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

Для решения двойственной задачи необходимо ввести три дополнительные переменные. Система ограничений не требует предварительных преобразований, ее первая симплексная таблица содержит четыре строки и восемь столбцов. Двойственную задачу решаем симплексным методом (таблица 1). Оптимальный план двойственной задачи Y* = (0; 1/2; 3/2; 0), fmax = 21/2. Оптимальный план исходной задачи находим, используя оценки (m + 1)-й строки последней итерации, стоящие в столбцах A5, A6, A7: x1 = 3/2 + 0 = 3/2; x2 = 9/2 + 0 = 9/2; x3 = 0 + 0 = 0. При оптимальном плане исходной задачи X* = (3/2; 9/2; 0) линейная функция достигает наименьшего значения: Zmin =21/2.

 

Таблица 1 – Симплексный метод решения двойственной задачи [3, с. 102].

i	Базис	С базиса	An	2		3		6			3			0	0	0
				A1		A2		A3			A4			A5	A6	A7
1 2 3	A5 A6 A7	0 0 0	1 2 3	2 2 -1		-1 1 4		1 1 -2			2 -1 -2			1 0 0	0 1 0	0 0 1
m + 1	Zi - Cj		0	-2		-3		-6			-3			0	0	0
1 2   3	A3 A6 A7	6 0 0	1  1  5	2 0 3		-1    2 6		1 0 0			2 -1  2			1 -1  2	0 1  0	0 0 1
m + 1	Zi - Cj		6	10	-9		0			9			6		0	0
1 2 3	A3   A2 A7	6 3 0	3/2 ½ 2	2 0 3		0 1 0	1 0 0		3/2 -1/2 4			½ -1/2 5			½ ½ 3	0 0 1
m + 1	Zi - Cj		1/2	0		0	0		9/2			3/2			9/2	0

 

Далее рассмотрим несимметричные двойственные задачи.

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

Исходная задача. Найти матрицу-столбец X = (x1, x2, …, xn), которая удовлетворяет ограничениям AX = A0, Х ³ 0 и минимизирует линейную функцию Z = СХ.

Двойственная задача. Найти матрицу-строку Y = (y1, y2, …, ym), которая удовлетворяет ограничениям YA £ С и максимизирует линейную функцию f = YA0.

В обеих задачах C = (c1, c2, …, cn) – матрица-строка, An = (b1, b2, …, bm) – матрица-столбец, А = (aij) – матрица коэффициентов системы ограничений.

Для составления несимметричной двойственной задачи используются те же правила, что и для составления симметричной двойственной задачи, но с учетом особенностей:

1. Если задача имеет канонический вид, то ограничения двойственной задачи будут неравенства. Если в целевой функции исходной задачи требуется найти минимум, то знак неравенства – ≥, а если требуется найти максимум, то знак неравенства – ≤.
2. Переменные уi для канонической задачи произвольны по знаку.

 

 

 

 

 

 

 

 

 

 

2 ТРЕТЬЯ ТЕОРЕМА ДВОЙСТВЕННОСТИ ОБ ОЦЕНКАХ

 

 

Третья теорема двойственности звучит следующим образом: двойственные оценки показывают приращение целевой функции, вызванные малыми изменениями свободного члена соответствующего ограничения задачи линейного программирования [4, с. 121], то есть:

 

     (3)

 

Выясним экономическое содержание третьей теоремы двойственности. Для этого в выражении, указанном в формулировке теоремы, дифференциалы заменим приращениями, то есть:

 

       (4)

 

Получим       (5)

при имеем      (6)

 

Двойственная оценка численно равна изменению целевой функции при изменении соответствующего ресурса на единицу. Их часто называют «скрытыми», «теневыми» или «маргинальными» оценками ресурсов.

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

Из последней таблицы получено решение двойственной задачи:

 

   (7)