Читайте также:
|
|
Из первой части теоремы следует, что равенство (3.25) является не только достаточным признаком оптимальности решений, но и необходимым условием оптимальности решений взаимно двойственных задач.
Рассмотрим примеры, подтверждающие справедливость первой теоремы двойственности.
Пример 3.11. Даны две взаимно двойственные задачи:
1) Ф = 2×x1 + 3×x2 ® max 2) F = 18×y1 + 16×y2 + 5×y3 + 21×y4 ® min
при ограничениях при ограничениях
x1 + 3×x2 £ 18, y1 + 2y2 + 3y4 ³ 2,
2x1 + x2 £ 16, 3×y1 + y2 + y3 ³ 3.
x2 £ 5,
3x1 £ 21.
x1 ³ 0, x2 ³ 0 yi ³ 0, i = 1,4
Решив эти задачи (например, первую графическим, вторую – симплексным методами), можно получить экстремумы целевых функций Фmax = 24, Fmin = 24, что подтверждает справедливость первой части первойтеоремыдвойственности.
Пример 3.12. Даны две взаимно двойственные задачи:
1) Ф = 3×x1 + 5×x2 ® max 2) F = 5×y1 - 7×y2 ® min
при ограничениях при ограничениях
3 ×x1 - 4×x2 £ 5, 3×y1 - 2 ×y2 ³ 3,
-2× x1 ³ -7, - 4×y1 ³ 5
x1 ³ 0, x2 ³ 0 y1 ³ 0, y2 ³ 0
Решив эти задачи (например, графическим методом), можно убедиться, что в исходной задаче (задача 1) целевая функция не ограничена Фmax = + ¥, в
ОДР не Система
ограни- ограничений
чена не совместна
двойственной задаче (задача 2) условия противоречивы, то есть, система ограничений несовместна, что подтверждает справедливость второй части теоремы.
Однако, утверждение, обратное по отношению ко второй части первой теоремы двойственности, в общем случае неверно, то есть, из противоречивости условий исходной задачи, не следует, что линейная функция двойственной задачи не ограничена.
Пример 3.13. Даны две взаимно двойственные задачи:
1) Ф = -8×х1 + 2×х2 ® min 2) F = y1 - y2 ® max
при ограничениях при ограничениях
-х1 + 2×х2 ³ 1, y1 +2×y2 ³ 8,
-2× х1 + х2 ³ -1, 2×y1 + y2 £ 2.
х1 ³ 0, х2 ³ 0 y1 ³ 0, y2 ³ 0
Решив эти задачи (например, графическим методом), можно убедиться, что в каждой из задач отсутствуют допустимые решения, то есть, условия обеих задач противоречивы.
х2 Системы y2
ограничений
не совместны
х1 8 y1
Тесная связь между двумя взаимно двойственными задачами проявляется не только в равенстве оптимальных значений их линейных функций, о чем утверждалось в первой теореме двойственности, но и в наличии связи между оптимальными решениями пары двойственных задач.
Рассмотрим две взаимно двойственные задачи:
1) исходная задача 2) двойственная задача
Ф = cj ×xj ® max F = bi×yi ® min
при ограничениях при ограничениях
aij× xj £ bi (i = 1,m) (3.26) aji× yi ³ cj (j = 1,n) (3.27)
xj ³ 0 (j = 1,n) yi ³ 0 (i = 1,m)
Чтобы каждую из этих задач решить симплексным методом, необходимо привести их к каноническому виду, для чего в систему ограничений исходной задачи (3.26) следует ввести m неотрицательных переменных x n+1, x n+2,..., x n+i,..., x n+m, а в систему ограничений двойственной задачи (3.27) -n неотрицательных переменных ym+1, ym+2,..., ym+j,..., ym+n, где i(j) - номер неравенства, в которое введена дополнительная переменная x n+i ³ 0 (y m+j ³ 0).
Системы ограничений каждой из задач примут вид: aij× xj + x n+i = bi, (i = 1,m) (3.28)
aji× yi - y m+j = сj, (j = 1,n) (3.29)
Между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи существует следующая взаимосвязь:
Переменные исходной задачи 1 | |
Первоначальные | Дополнительные |
x1, x2,..., xj,..., xn | x n+1, x n+2,..., x n+i,..., x n+m |
↕ ↕ ↕ ↕ | ↕ ↕ ↕ ↕ |
ym+1, ym+2,..., ym+j,..., ym+n | y1, y2,..., yi, ..., ym |
Дополнительные | Первоначальные |
Переменные двойственной задачи 2 |
Эту взаимосвязь можно сформулировать в виде следующей теоремы.
Теорема о взаимосвязях переменных. Положительным (ненулевым) компонентам оптимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, то есть, для любых i = 1, m и j = 1, n:
если x*j > 0, то y*m+j = 0; если x*n+i > 0, то y*i = 0,
Дата добавления: 2014-12-20; просмотров: 100 | Поможем написать вашу работу | Нарушение авторских прав |