Математическое программирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
?аков коэффициентов на противоположные;
)если переменное xj не ограничено знаком, его можно представить в виде разности двух неотрицательных переменных.
Пример. Составить двойственную задачу к исходной.
.
Решение. 1) Стандартный вид прямой задачи.
) Двойственная задача:
Задачу можно записать в виде, соответствующем исходной прямой задаче, если заменить: а) - не ограничена знаком,
б) два последних ограничения соответствуют равенству.
.
3. Основные теоремы двойственности и их экономическое содержание
Теорема 1. Двойственная задача к двойственной есть прямая задача.
Доказательство: Пусть имеем пару двойственных задач в матричном виде.
Ах АТy C
F = CTx Z =
x 0 y 0
Построим к двойственной задаче двойственную:
) запишем в стандартном виде -АТy -C
Z = -
2) -Ах Ах
F = - CTx F = CTx
Что и требовалось доказать.
Теорема 2. Значение функции F, соответствующее любому допустимому решению прямой задачи, не больше значения функции Z, соответствующего любому допустимому решению двойственной задачи.
Доказательство: Пусть X и Y соответственно произвольные допустимые решения прямой и двойственной задач. Следовательно,
1) Ах и Y YТ , YTAX YTb = bTY = Z.
) ATY C и X 0 XТ , XTATY XTC = CTX = F.
) выражение XTATY - скалярная величина (число) она равна своей
транспозиции, т.е. XTATY = YTAX. Итак, имеем,
F XTATY = YTAX Z F Z. Что и требовалось доказать.
Следствия: 1) если в прямой задаче допустимая область не пуста, а целевая функция не ограничена сверху, то у двойственной задачи допустимая область пуста;
) если в двойственной задаче допустимая область не пуста, а целевая функция не ограничена снизу, то у прямой задачи допустимая область пуста.
Теорема 3. Если прямая задача имеет конечное оптимальное решение F = Fmax, то двойственная задача имеет конечное оптимальное решение Z = Zmin. При этом Fmax = Zmin, а симплекс-множители оптимального решения прямой задачи являются значениями переменных в оптимальном решении двойственной задачи.
Доказательство: Запишем прямую задачу
Ах , x 0 , b , F = CTx .
Запишем задачу в стандартном виде Ах + хР = b, где хР = (х1,…,хn+m)- дополнительные, уравновешивающие переменные, Т- симплекс-множители оптимального решения. Известно, что прямая задача разрешима, следовательно, можно определить значения симплекс-множителей оптимального решения. Получим оптимальное выражение целевой функции, то есть
+
(-СT+)x+= F + bT. (*)
Так как это оптимальный вид целевой функции, то все коэффициенты
неотрицательны.
или .
Т.о., если y = , то ограничения двойственной задачи выполняются.
Так как (*) - оптимальный вид целевой функции, то коэффициенты перед базисными переменными равны нулю, а свободные переменные сами равны нулю Fmin = -bT или Fmax = bT. Если y = , то это и есть целевая функция двойственной задачи, то есть Z = Fmax = Zmin. Что и требовалось доказать.
Теорема 4. Если двойственная задача имеет конечное оптимальное решение Z = Zmin, то прямая задача имеет конечное оптимальное решение F = Fmax. При этом Zmin = Fmax , а значения симплекс-множителей оптимального решения двойственной задачи являются значениями переменных в оптимальном решении прямой задачи с противоположными знаками (если обе задачи решаются прямым симплекс-методом).
Доказательство: В матричной форме двойственная задача имеет вид.
АТy C , y 0, С 0, Z =
1) Запишем в стандартном виде ATy - yS = C, где yS= (ym+1,…,ym+n)T 0 - дополнительные, уравновешивающие переменные, - симплекс-множители оптимального решения двойственной задачи. Для двойственной задачи имеют то же значение, то есть
+
(bT + = Z + . (**)
Так как это оптимальный вид целевой функции Z, то все коэффициенты неотрицательны.
или .
Таким образом, если , то ограничения прямой задачи удовлетворяются, значит это решение.
) Так как (**) - оптимальное решение для целевой функции, то коэффициенты перед базисными переменными равны нулю, а свободные переменные сами равны нулю. Следовательно, min = -, а это есть целевая функция прямой задачи, если . Что и требовалось доказать.
Экономическое содержание теорем состоит в следующем: если задача оптимизации плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения оценок ресурсов. План производства и оценки ресурсов являются оптимальными тогда и только тогда, когда цена произведенной продукции и суммарная оценка ресурсов совпадают. Оценки выступают как инструмент балансирования затрат и результатов. Так как F Z, Z - F = - издержки производства, которые равны нулю когда F* = Z*.
Двойственные оценки обладают тем свойством, что они гарантируют рентабельность оптимального плана, то есть равенство общей оценки продукции и ресурсов, и обуславливают убыточность всякого другого плана, отличного от оптимального.
Кроме того, если yi > 0, то при оптимальной производственной программе этот ресурс используется полностью; если yi = 0, то ресурс используется не полностью.
Лекция 7, 8
Элементы теории игр и принятия решений
Вопросы:
1. Основные понятия.
. Теоремы теории игр.
. Способы решения задач теории игр.
. Методы принятия решений: в условиях