72
min,→⋅
n
T
n
YB
,)(
mn
T
nm
CYA ≥⋅
×
.0
nn
Y ≥ (9.5)
Здесь индексы у матриц – их размерности, т.е. число строк, затем
число столбцов. Векторы
nm
YX , представлены столбцовыми
матрицами. Знак T – транспонирование.
Для двойственной задачи условия (9.2) и (9.3) определяют
область допустимых значений Y
R
n
. Целевая функция f
d
(y) задаёт
прямые уровня в пространстве R
n
. Значит, для двойственной задачи
можно применять графический метод решения. Следует помнить,
что, несмотря на формальное сходство задачи (8.1) – (8.3) и (9.1) –
(9.3), их решения находятся, вообще говоря, в разных
пространствах, т.е. x*
X
⊂
R
m
и y
*
Y
R
n
.
По аналогичной схеме можно определить двойственную
задачу для задачи линейного программирования (на
минимизацию целевой функции) (9.1) – (9.3). В этом случае
двойственная задача будет задача линейного программирования
(на максимизацию целевой функции), представленная в (8.1) –
(8.3). В этом смысле можно говорить о задаче (8.1) – (8.3) и о задаче
(9.1) – (9.3), как о паре двойственных (сопряжённых) задач
линейного программирования.
Прямая (8.1) – (8.3) и двойственная (9.1) – (9.3) задачи
линейного программирования (пара двойственных задач) имеют
общие свойства:
1°. Число неизвестных в первой задаче равно числу
ограничений во второй задаче;
2°. Матрица коэффициентов системы ограничений
получается одна из другой путём транспонирования;
3°. Неравенства в системах ограничений имеют
противоположный смысл;
4°. Свободные члены системы ограничений одной задачи
становятся коэффициентами целевой функции и наоборот.