 |
 |
 |
 |
|
 |
 |
30
1.6. ТЕОРИЯ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ
1.6.1. Понятие двойственной задачи ЛП. Пусть задана КЗЛП (1.7). Если целевая функция f(x) = cx
достигает максимального значения на множестве
D, то обоснованным представляется вопрос о том,
каким образом можно построить верхнюю оценку для нее. Очевидно, что если через и обозначить
некоторый m-мерный вектор, то
Предположим, что и можно выбрать таким образом, чтобы иА
?
с. Тогда при любых х
? 0
справедливо неравенство
Стремясь получить наилучшую оценку (1.47), мы приходим к формулировке некоторой новой
кстремальной задачи, которая в некотором смысле логически сопряжена с задачей (1.7) называется
двойственной. Оговоримся, что приведенные рассуждения не носят строгого характера и
предназначены только для того, чтобы подготовить читателя к приводимому ниже формальному
определению двойственной задачи линейного прoграммирования.
Если задана каноническая задача ЛП
то задача ЛП
называется двойственной по отношению к ней. Соответственно, задача (D, f) no отношению к
(D*,f*) называется прямой (или исходной).
1.6.2. Общая схема построения двойственной задачи.
Приведенное выше определение задачи,
двойственной по отношению к канонической ЗЛП, может быть распространено на случай общей задачи
линейного программирования.
Если задана общая задача ЛП
f(x) = c1x1 + ... + с
j
х
j
+
с
j+1
х
j+1
+ ... + с
n
x
n
>
max, x
D, (1.50)
где D определяется системой уравнений и неравенств: