Введение в линейное программирование. Палий И.А. - 30 стр.

UptoLike

ВУЗ: 

СибАДИ | Омск

Составители: 

Рубрика: 

Если
i
b − правая часть i-го ограничения задачи (1), то
i
b
−
коэффициент при
i
y
в целевой функции задачи (2), mi ,,1 L= .
Если
j
c − коэффициент при
i
x
в целевой функции задачи (1), то
j
c − правая часть j-го ограничения задачи (2), n
j
,,1 L
=
.
4.
Каждому ограничению-неравенству задачи (1) соответствует
условие неотрицательности ассоциированной с этим ограничением
переменной задачи (2). Каждому ограничению-равенству задачи (1)
соответствует переменная задачи (2) без ограничений на знак.
Наоборот, каждому ограничению-неравенству задачи (2)
соответствует неотрицательная переменная задачи (1), каждому
ограничению-равенству задачи (2) соответствует переменная
задачи (1) произвольного знака.
Задача (1) называется
двойственной задаче (2); задача (2) называется
двойственной задаче (1).
Из определения двойственной пары следует, что отношение
двойственности взаимное, задача, двойственная двойственной, совпадает с
исходной задачей.
Пример 1. Построить задачу, двойственную следующей ЗЛП
max2
54321
→
+
−+−= xxxxxZ ;
6232
54321
=
−
++− xxxxx ; (y
1
)
432
54321
≤
+
+−+ xxxxx ; (y
2
)
52
421
−
≤
+− xxx ; (y
3
)
0,,
521
≥xxx .
Двойственная задача:
min546
321
→−+= yyyW ;
12
321
≥+
+
yyy (x
1
)
2232
321
−
≥−
+
− yyy ; (x
2
)
1
21
=
−
yy ; (x
3
)
13
321
−
=
++ yyy
(x
4
)
12
21
≥+− yy
; (x
5
)
y
2
, y
3
≥ 0.
Пример 2. Любую ЗЛП можно привести к каноническому виду.
Доказывать теоремы двойственности удобно, когда одна из пары
двойственных задач записана в канонической форме. Построим
двойственную ей задачу.

Страницы