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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

109
Отметим особенности пары взаимно двойственных задач.
1) Если основная задача – задача на максимум (минимум), то
система ограничений должна состоять из неравенств вида
≤
(
≥
), и в таком
случае двойственная задача должна быть задачей на минимум (макси-
мум), а ее система ограничений должна состоять из неравенств вида
≥
(
≤
),
т.е. неравенств противоположного смысла.
2) В основной задаче все переменные должны быть неотрица-
тельными.
3) Коэффициентами целевой функции
)
(
Y
F
двойственной
зада
-
чи
являются
свободные члены
системы
ограничений
основной
задачи
,
и
их
число
равно
m
.
4)
Основная
матрица
системы
ограничений
двойственной
задачи
получается
транспонированием
матрицы
системы
ограничений
основной
задачи
.
5)
Свободными членами
системы
ограничений
двойственной
задачи
являются
коэффициенты
целевой
функции
)
(
X
L
основной
задачи
.
6)
Все
переменные
двойственной
задачи
неотрицательные
.
Предположим
теперь
,
что
основная
задача
задана
в
ослабленной
форме
,
т
.
е
.
среди
ее
переменных
имеются
переменные
произвольного
зна
-
ка
(
на
них
не
наложено
требование
неотрицательности
),
а
система
ограни
-
чений
содержит
неравенства
противоположных
направлений
и
,
возможно
,
равенства
.
Построение
двойственной
задачи
в
таком
случае
основано
на
следующих
правилах
.
1)
Все
неравенства
системы
ограничений
основной
задачи
следу
-
ет
привести
к одному направлению
:
≥
в
задаче
на
минимум
или
≤
в
за
-
даче
на
максимум
.
2)
Если
в
системе
ограничений
основной
задачи
имеется
равен-
ство (уравнение)
,
то
та
переменная
i
y
,
которая
соответствует
этому
-
му
ограничению
-
равенству
,
может
быть
произвольного
знака
..
Запишем
это
соответствие
так
:
Rybxaxaxa
i
i
n
in
i
i
∈
→
=
+
+
+
...
2
2
1
1
.
3)
Если
на
некоторую
переменную
j
x
основной
задачи
не наложено
условие неотрицательности
,
то
соответствующее
ей
ограничение
двойст
-
венной
задачи
является
равенством

Страницы