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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

6. Основы теории двойственности
6.1. Определение пары двойственных задач
Рассмотрим пару задач линейного программирования, связанных
между собой симметричными зависимостями. В частности, целевая
функция одной задачи максимизируется, другой − минимизируется.
Задачу, для которой требуется найти максимум целевой функции, назовем
задачей (1), симметричную ей задачу назовем задачей (2). Условимся все
ограничения-неравенства задачи (1) записывать в виде ≤, все ограничения-
неравенства-задачи (2) записывать в виде
≥. Целевую функцию задачи (1)
обозначим буквой Z, целевую функцию задачи (2) − буквой W.
Задачи (1) и (2) называют
парой двойственных задач линейного
программирования (или просто
двойственной парой), если выполнены
следующие соотношения:
1.
В задаче (1) n неизвестных и m ограничений (без учета условий
неотрицательности), В задаче (2) m неизвестных и n ограничений
(без учета условий неотрицательности).
Ограничения задачи (1) находятся во взаимнооднозначном
соответствии с переменными задачи (2). Переменные задачи (1)
находятся во взаимнооднозначном соответствии с ограничениями
задачи (2).
Переменные задачи (1) обозначим через
n
xxx ,,,
21
L ;
Переменные задачи (2) − через
m
yyy ,,,
21
L .
2.
Матрицы ограничений задач (1) и (2) взаимно
транспонированы. Строка коэффициентов системы ограничений
задачи (1) − это столбец коэффициентов системы ограничений
задачи (2) и наоборот.
Если
ij
a − это коэффициенты при переменной
i
x в i-м
ограничения задачи (1), mi ,,1
L
=
; n
j
,,1 L
=
, то в задаче (2)
коэффициент
ij
a стоит при переменной
i
y в j-м ограничении.
3.
Правые части системы ограничений задачи (1) − это
коэффициенты целевой функции задачи (2); коэффициенты целевой
функции задачи (1) − это правые части системы ограничений задачи
(2).

Страницы