Министерство образования и науки Российской
Федерации
Федеральное государственное бюджетное
образовательное учреждение
Высшего профессионального образования
«Рязанский государственный университет
имени С.А. Есенина»
Факультет экономики
Кафедра учета и аудита
Дисциплина «Теория игр»
Контрольная работа
Вариант № 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) - матрица
коэффициентов системы ограничений.
Для составления несимметричной
двойственной задачи используются те
же правила, что и для составления симметричной
двойственной задачи, но с учетом особенностей:
Если задача имеет канонический
вид, то ограничения двойственной задачи
будут неравенства. Если в целевой функции
исходной задачи требуется найти минимум,
то знак неравенства - ≥, а если требуется
найти максимум, то знак неравенства -
≤.
Переменные уi для канонической задачи произвольны по знаку [1, с. 62].
3. Теоремы двойственности
Каждой задаче
линейного программирования можно поставить в соответствие
другую задачу линейного программирования,
которую называют двойственной к данной.
Исходная и двойственная к ней задача
образуют пару двойственных задач.
Первая основная теорема двойственности
- если одна из двойственных задач имеет оптимальное
решение, то двойственная ей задача
также имеет оптимальное решение, причем
экстремумы целевых
функций равны, то есть
[7, с. 59].
Если одна из двойственных задач
не имеет оптимального решения, то другая
задача также не имеет оптимального решения,
причем если одна из задач не имеет оптимального
решения из-за неограниченности целевой
функции, то другая из-за несовместности
системы ограничений.
Вторая теорема двойственности
для несимметричных двойственных задач
формулируется так: для того, чтобы допустимые
решения
и
несимметричной пары двойственных
задач были соответственно оптимальными
решениями, необходимо и достаточно, чтобы
для любого j выполнялось равенство: