Линейная алгебра. Линейное программирование. Тарбокова Т.В. - 108 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

108
2.11. Двойственность в линейном программировании
Предположим, что задача линейного программирования задана в сле-
дующем виде:
→
+
+
+
=
n
n
xcxcxcXL ...)(
2
2
1
1
max (
или
min)
mmmnmnmm
nn
nn
y
y
y
b
b
b
bxaxaxa
bxaxaxa
bxaxaxa
...
)(
)(
)(
....
...........................................
,...
,...
2
1
2
1
2211
22222121
11212111
≥
≥
≥
≤+++
≤+++
≤+++
0...,,0,0
2
1
≥
≥
≥
n
xxx
Составим
другую
задачу
линейного
программирования
,
число
пере
-
менных
которой
равно
числу
ограничений
данной
задачи
,
т
.
е
.
m
.
Обозна
-
чим
их
вектором
)...,,,(
2
1
m
yyyY
=
.
Эта
задача
имеет
вид
:
→
+
+
+
=
m
m
ybybybYF
...)(
2
2
1
1
min (
или
max)
)(
)(
)(
....
...........................................
,...
,...
2
1
2211
22222112
11221111
mmmnmnn
mm
mm
c
c
c
cyayaya
cyayaya
cyayaya
≤
≤
≤
≥+++
≥+++
≥+++
0...,,0,0
2
1
≥
≥
≥
m
yyy
Вторая
задача
называется
двойственной
,
или
сопряженной
для
пер
-
вой
,
а
первая
–
прямой
,
или
основной
.
Если
для
второй
задачи
составить
двойственную
задачу
,
то
получим
первую
.
Таким
образом
,
сформулированные
задачи
составляют
пару
вза
-
имно
двойственных
,
или
взаимно
сопряженных
задач
линейного
програм
-
мирования
.

Страницы