Методы оптимизации. Рейзлин В.И. - 38 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

Задачи (4.1) – (4.3) и (4.4) – (4.6) образуют пару задач, называемую в
линейном программировании двойственной парой.
Из сравнения двух сформулированных задач видно, что двойственная
задача по отношению к исходной составляется согласно следующим правилам:
1.Целевая функция имеет противоположный тип экстремума.
2.Матрица коэффициентов двойственной задачи получается в результате
транспонирования матрицы коэффициентов исходной задачи.
3.Число переменных в двойственной задаче (4.4) – (4.6) равно числу
соотношений в системе (4.2) исходной задачи, а число ограничений в системе
(4.5) – числу переменных в исходной задаче.
4.Коэффициентами при неизвестных в целевой функции (4.4) двойственной
задачи являются свободные члены в системе (4.2), а правыми частями в системе
(4.5) двойственной задачи – коэффициенты при неизвестных в целевой функции
(4.1).
Многие задачи линейного программирования первоначально составляются
в виде исходных или двойственных задач, поэтому имеет смысл говорить о паре
двойственных задач линейного программирования.
Между оптимальными планами пары двойственных задач существует связь,
которую устанавливает теорема двойственности [5]:
Если из пары двойственных задач одна обладает оптимальным планом, то
и другая имеет решение, причем для экстремальных значений линейных функций
выполняется соотношение
'
maxmin ZZ .
Если линейная функция одной из задач не ограничена, то другая не имеет
решения.
4.2 Модели двойственных задач
Различают несимметричные и симметричные двойственные задачи. В несимметричных двойственных задачах система
ограничений исходной задачи задается в виде равенств, а двойственной – в виде неравенств, причем в последней переменные могут быть и
отрицательными. В симметричных задачах система ограничений как исходной так и двойственной задач задается неравенствами, причем на
двойственные переменные налагается условие неотрицательности.
Математические модели пары двойственных задач могут иметь один из
следующих видов.
Несимметричные задачи
Исходная задача Двойственная задача
1. CXZ
min
; YBZ
max
;
B
AX
;
CYA
.
0
X
.

Страницы