Двойственность в линейном программировании

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

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

«Рязанский государственный университет имени С.А. Есенина»

 

Факультет  экономики

Кафедра учета и аудита

 

 

 

 

                                    Дисциплина «Теория игр»

 

 

 

Контрольная работа

Вариант № 9

 

 

 

 

 

                                                        Выполнил(а): студентка                    

2 курса на базе С/П гр. 23                                          

Направление «Экономика»

Профиль «Бухгалтерский учет,

анализ и аудит»

Игнатова К.В.

 

                                                           Проверил: ___________________                                             

 

                                                                             Дата «____» ___________ 2014г.

 

 

 

 

Рязань 2014

 

 

 

 

 

 

                                               Содержание

Введение…………………………………………………………………………...3

1. Двойственность в линейном  программировании…………………………….4

2. Виды двойственных задач……………………………………………………..6

3. Теоремы двойственности………………………………………………………9

4. Двойственный симплексный  метод………………………………………….15

Заключение……………………………………………………………………….17

Список использованных источников…………………………………………...18

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

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

Цель - проанализировать теоремы двойственности.

В соответствии с поставленной целью были выделены следующие задачи:

• рассмотреть двойственность в линейном программировании;
• описать виды двойственных задач;
• изучить теоремы двойственности;
• охарактеризовать двойственный симплекс метод.

 

 

1. Двойственность  в линейном программировании

 

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

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

Связующим фактом этих двух задач являются коэффициенты C j   функции исходной задачи. Данные коэффициенты называются свободными членами системы ограничений двойственной задачи. Коэффициенты B i системы ограничений исходной задачи называются коэффициентами двойственной задачи. Транспонированная матрица коэффициентов системы ограничений исходной задачи является матрицей коэффициентов системы ограничений двойственной задачи [4, с. 86].

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

У предприятия есть т видов ресурсов в количестве b i ( i = 1, 2, ..., m ) единиц, из которых выпускается n видов продукции. На изготовление1 ед. i -й продукции тратится a ij ед. t-гo ресурса, ее стоимость составляет C j ед. Необходимо определить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Примем за x j (j =1,2, ..., n) количество ед. j -й продукций.

Сформулируем исходную задачу. Определить вектор Х =( x 1 , x 2 , …, x n ), который удовлетворяет ограничениям.

Определим ресурсы, которые потребуются для изготовления товара. Обозначим за единицу стоимости ресурсов единицу стоимости выпускаемого товара. А через у i (j =1,2, ..., m) стоимость единицы i -го ресурса. То есть стоимость всех затраченных ресурсов, которые используются для изобретения единицы j -й продукции, составляет. Цена израсходованных ресурсов не должна превышать цены окончательного товара. Таким образом должно выполняться неравенство і C j , j =1,2, ..., n. Цена имеющихся ресурсов составляет.

Сформулируем   двойственную задачу.

Необходимо определить вектор Y = (y 1 , y 2 , …, y n), удовлетворяющий ограничениям.

Переменные у i называются оценками или учетными, неявными ценами.

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

А исходную задачу определим следующим образом: сколько и какой продукции x j   (j =1,2, ..., n) необходимо произвести, чтобы при заданных стоимостях C j   (j =1,2, ..., n) единицы продукции и размерах имеющихся ресурсов b i   (i =1,2, ..., n) максимизировать выпуск продукции в стоимостном выражении.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Виды двойственных задач

 

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

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

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

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

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

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

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

 

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

Для решения двойственной задачи необходимо ввести три дополнительные переменные. Система ограничений не требует предварительных преобразований, ее первая симплексная таблица содержит четыре строки и восемь столбцов [1, с. 59]. Двойственную задачу решаем симплексным методом (таблица 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

i	Базис	С базиса	An	2		3		6			3			0			0			0
				A1		A2		A3			A4			A5			A6			A7
1 2 3	А5 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		21/2	10		0	0		9/2			3/2			9/2			0

 

 

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

Исходная задача. Найти матрицу-столбец 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 для канонической задачи произвольны по знаку [1, с. 62].

 

3. Теоремы двойственности

 

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

Первая основная теорема двойственности - если одна из двойственных задач имеет оптимальное решение, то двойственная ей задача также имеет оптимальное решение, причем экстремумы целевых функций равны, то есть  [7, с. 59].

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

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