Езу9у. Учебное пособие Рекомендовано методическим советом Уральского федерального университета в качестве учебного пособия для студентов вуза, обучающихся по направлениям подготовки
 Скачать 5.85 Mb.
|
|
5.2. Правила перехода от прямой задачи к двойственной Каждая из задач двойственной пары фактически является самостоятельной задачей линейного программирования и может быть рассмотрена и решена не- зависимо от другой задачи. С этой целью целесообразно рассмотреть правила составления двойственной задачи, т. е. распространить данное выше опреде- ление двойственной задачи для стандартной формы на случай общей задачи линейного программирования. Стоит отметить, что часто рассматривают формулировки двойственной задачи в зависимости от различных видов прямой задачи, которые определя- ются типами ограничений, знаками переменных и типом оптимизации, но это не всегда оправдано. В табл. 5.1 приведены правила перехода от прямой задачи линейного прог- раммирования L к двойственной L * Стоит отметить, что построение двойственной задачи зависит от того, какой оптимум в прямой задаче: если максимум, то необходимо пользоваться первыми двумя столбцами перехода, если минимум, то последними двумя. 137 Таблица 5.1 L L * L L * max min min max A — матрица коэффициентов при неизвестных в системе ограни- чений A T — матрица коэффициентов при неизвестных в системе ограни- чений A — матрица ко- эффициентов при неизвестных в сис- теме ограничений A T — матрица коэффициентов при неизвестных в системе ограни- чений m ограничений m переменных m ограничений m переменных n переменных n ограничений n переменных n ограничений x — переменная y — переменная x — переменная y — переменная Коэффициенты целевой функции Правые части огра- ничений Коэффициенты целевой функции Правые части огра- ничений Правые части ограничений Коэффициенты целевой функции Правые части огра- ничений Коэффициенты целевой функции Ограничения Переменная Ограничения Переменная Ограничения типа «≤» y ≥ 0 Ограничения типа «≤» y ≤ 0 Ограничения типа «≥» y ≤ 0 Ограничения типа «≥» y ≥ 0 Ограничения типа «=» y свободная Ограничения типа «=» y свободная x ≥ 0 Ограничения типа « ≥ » x ≥ 0 Ограничения типа «≤» x ≤ 0 Ограничения типа « ≤ » x ≤ 0 Ограничения типа «≥» x свободная Ограничения типа « = » x свободная Ограничения типа «=» Также необходимо четко понять, что в двойственной задаче знаки функцио- нальных ограничений определяются по знакам переменных прямой задачи, а знаки переменных двойственной задачи определяются по знакам функцио- нальных ограничений прямой задачи. Пример 5.1. Составить двойственную задачу следующей задачи линейного программирования: 1 2 3 ( ) max, Z X x x x = + + → 1 3 1 2 1 3 4 1, : 2 3, 0, 0. x x L x x x x − + ≥ + = ≥ ≥ 138 Решение. Сразу заметим, что в прямой задаче целевая функция максими- зируется, значит, при построении двойственной будем пользоваться первыми двумя столбцами табл. 5.1, и целевая функция будет уже минимизироваться. Двойственную задачу обозначим L * . Переменных в ней будет столько, сколь- ко функциональных ограничений в прямой задаче, т. е. две; сами переменные обозначим y 1 и y 2 . Для удобства припишем их справа у ограничений прямой задачи следующим образом: 1 3 1 2 1 2 4 1 , 2 3 x x y y x x − + ≥ + = (5.3) Такая запись позволяет четко определить, что переменной y 1 соответствует первое ограничение прямой задачи, y 2 — второе. Далее, согласно правилам перехода, числа, стоящие в правых частях огра- ничений, образуют коэффициенты целевой функции, т. е. получается: 1 2 3 . y y + Затем транспонированная матрица коэффициентов функциональных ог- раничений прямой задачи будет образовывать матрицу функциональных ог- раничений двойственной задачи. Стоит заметить, что можно не выписывать эти матрицы, а транспонировать и записывать левые части ограничений двой- ственной задачи, исходя из (4.3). Записываем коэффициент при x 1 из первого ограничения и умножаем его на y 1 , затем аналогично выписываем коэффици- ент при x 1 из второго ограничения и умножаем его на y 2 , подобным образом поступаем с коэффициентами при x 2 и x 3 , получаем левые части ограничений двойственной задачи: 1 2 2 1 2 , , 4 . y y y y − + В правой части ограничений будут располагаться коэффициенты из целевой функции. Таким образом, имеем: 1 2 2 1 2 , , 4 . y y y y − + (5.4) Теперь определяем знаки между левой и правой частями функциональных ограничений, исходя из знаков переменных прямой задачи. Согласно правилам 139 перехода, знак функционального ограничения будет такой же, как и у соответ- ствующей ему переменной, за исключением свободных переменных. Перемен- ная x 1 неотрицательная, значит, в первом ограничении двойственной задачи имеет место знак « ≥ », x 2 не зависит от знака (может быть как положительной, так и отрицательной, и равной нулю), т. е. свободная, следовательно, знак вто- рого ограничения двойственной задачи « = », x 3 неположительная, значит, знак третьего ограничения « ≤ ». Далее знаки переменных двойственной задачи определяем по знакам функ- циональных ограничений прямой задачи. Первое ограничение прямой задачи имеет знак « ≥ », значит, y 1 ≤ 0, второе ограничение имеет знак « = », значит, y 2 — свободная. Указанные знаки записываем в (5.4). Все эти рассуждения про определение знаков ограничений и переменных мы провели, опираясь на первые два столбца табл. 5.1. Таким образом, получаем двойственную задачу к исходной: 1 2 ( ) 3 min, Z Y y y ∗ = + → 1 2 2 1 1 2 1, 1, : 4 1, 0. y y y L y y ∗ − + ≥ = ≤ ≤ Обратите внимание, что целевую функцию двойственной задачи принято обозначать Z * Пример 5.2.Составить двойственную задачу следующей задачи линейного программирования: 1 2 3 ( ) 2 2 min, Z X x x x = + + → 1 2 3 1 2 3 1 2 3 1 3 1, 2 3 6, : 3, 0, 0. x x x x x x L x x x x x − + + ≥ − − − = − + − ≤ ≥ ≤ Решение. Сразу заметим, что в прямой задаче целевая функция минимизи- руется, значит, при построении двойственной будем пользоваться последними двумя столбцами табл. 5.1, и целевая функция будет уже максимизироваться. Двойственную задачу обозначим L * . Переменных в ней будет столько, сколь- ко функциональных ограничений в прямой задаче, т. е. три; сами переменные 140 обозначим y 1 , y 2 и y 3 . Для удобства припишем их справа у ограничений прямой задачи следующим образом: 1 2 3 1 1 2 3 2 3 1 2 3 1 , 2 3 6 , 3 x x x y x x x y y x x x − + + ≥ − − − = − + − ≤ (5.5) Такая запись позволяет четко определить, что переменной y 1 соответствует первое ограничение прямой задачи, y 2 — второе, y 3 — третье. Далее, согласно правилам перехода, числа, стоящие в правых частях ограни- чений, образуют коэффициенты целевой функции, т. е. получается: y 1 − 6y 2 + 3y 3 Затем транспонированная матрица коэффициентов функциональных ог- раничений прямой задачи будет образовывать матрицу функциональных ог- раничений двойственной задачи. Аналогично предыдущему примеру не будем выписывать эти матрицы, а будем транспонировать и записывать левые части ограничений двойственной задачи, исходя из (5.5). Записываем коэффициент при x 1 из первого ограничения и умножаем его на y 1 , затем аналогично выписы- ваем коэффициент при x 1 из второго ограничения и умножаем его на y 2 , также коэффициент при x 1 из третьего ограничения умножаем на y 3. Аналогично поступаем с коэффициентами при x 2 и x 3 , получаем левые части ограничений двойственной задачи: 1 2 3 1 2 3 1 2 3 2 , 3 , y y y y y y y y y − − + − + − − В правой части ограничений будут располагаться коэффициенты из целевой функции. Между левой и правой частями пока оставим пропуск, в который в дальнейшем поместим знаки ограничений. Таким образом, имеем: 1 2 3 1 2 3 1 2 3 2 1, 3 2, 2. y y y y y y y y y − − + − + − − (5.6) Теперь определяем знаки между левой и правой частями функциональных ограничений исходя из знаков переменных прямой задачи. Согласно правилам перехода, знак функционального ограничения двойственной задачи будет со- ответствовать противоположному знаку переменной прямой задачи. В этом заключается одно из отличий от предыдущего примера, так как здесь целевая функция минимизируется. Переменная x 1 неотрицательная, значит, в первом 141 ограничении двойственной задачи имеет место знак « ≤ », x 2 не зависит от знака, т. е. свободная, следовательно, во втором ограничении имеет место знак « = », x 3 неположительная, значит, знак третьего ограничения « ≥ ». Далее знаки переменных двойственной задачи определяем по знакам функ- циональных ограничений прямой задачи. Первое ограничение прямой задачи имеет знак « ≥ », значит, y 1 ≥ 0, второе ограничение имеет знак « = », значит, y 2 — свободная. Первое ограничение прямой задачи имеет знак « ≤ », значит, y 3 ≤ 0. Указанные знаки подписываем в (5.6). Все эти рассуждения про определение знаков ограничений и переменных мы провели, опираясь на табл. 5.1. Таким образом, получаем двойственную задачу к исходной: 1 2 3 ( ) 6 3 max, Z Y y y y ∗ = − + → 1 2 3 1 2 3 1 2 3 1 3 2 1, 3 2, : 2, 0, 0. y y y y y y L y y y y y ∗ − − + ≤ − + = − − ≥ ≥ ≤ 5.3. Теоремы двойственности и их экономический смысл Вначале мы ввели понятие двойственной задачи исходя из ее экономиче- ского смысла, затем поняли, что эта задача может быть рассмотрена как са- мостоятельная задача, и для этого изучили правила ее построения. Сейчас же рассмотрим, что общего между прямой и двойственной задачами линейного программирования. Оказывается, что эти задачи тесно связаны друг с другом, и установить это удается благодаря так называемым теоремам двойственности. Для простоты сформулируем эти теоремы для следующих взаимно двой- ственных задач линейного программирования: 1 1 2 2 ( ) max, n n Z X c x c x c x = + + + → 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 , , : , 0, 1, n n n n m m mn n m j a x a x a x b a x a x a x b L a x a x a x b x j n + + + ≤ + + + ≤ + + + ≤ ≥ = 142 и 1 1 2 2 min ) , ( m m Z Y b y b y b y ∗ → = + +…+ 11 1 21 2 1 1 12 1 22 2 2 2 1 1 2 2 , , : , 0, 1,.. ., . m n i m m m n n mn m a y a y a y c a y a y a y c L a y i y a y a m y c ∗ ≥ = + +…+ ≥ + +…+ ≥ … + +…+ ≥ Теорема 5.1 (cлабая теорема двойственности). Если X = (x 1 , …, x j , …, x n ) и Y = (y 1 , …, y i , …, y m ) — допустимые решения задач L и L * соответственно, то справедливо следующее неравенство: 1 1 2 2 1 1 2 2 , n n m m c x c x c x b y b y b y + +…+ ≤ + +…+ (или так: Z(X) ≤ Z * (Y)). Доказательство. Умножим каждое функциональное ограничение прямой задачи L соответственно на переменные y 1 , y 2 , …, y m , получим: ( ) ( ) ( ) 11 1 12 2 1 1 1 1 21 1 22 2 2 2 2 2 1 1 2 2 , , n n n n m m mn n m m m a x a x a x y b y a x a x a x y b y a x a x a x y b y + + + ≤ + + + ≤ + + + ≤ Сложив левые и правые части этих неравенств, получим: 11 1 1 21 1 2 1 1 12 2 1 22 2 2 2 2 1 1 2 2 1 1 2 2 m m m m n n n n mn n m m m a x y a x y a x y a x y a x y a x y a x y a x y a x y b y b y b y + +…+ + + +…+ +…+ + + + + +…+ ≤ + +…+ (5.7) Аналогично преобразовав систему функциональных ограничений двойст- венной задачи L * путем умножения обеих частей ее неравенства на переменные x 1 , x 2 , …, x n и последующего их сложения, получим: 11 1 1 12 1 2 1 1 21 2 1 22 2 2 2 2 1 1 2 2 1 1 2 2 n n n n m m m m mn m n n n a y x a y x a y x a y x a y x a y x a y x a y x a y x c x c x c x + +…+ + + +…+ +…+ + + + +…+ ≥ + +…+ (5.8) Очевидно, что левые части (5.7) и (5.8) совпадают, таким образом, имеем: 1 1 2 2 11 1 1 21 1 2 1 1 12 2 1 22 2 2 2 2 1 1 2 2 1 1 2 2 n n m m m m n n n n mn n m m m c x c x c x a x y a x y a x y a x y a x y a x y a x y a x y a x y b y b y b y + +…+ ≤ + +…+ + + +…+ + +…+ + + + +…+ ≤ + +…+ 143 Следовательно, 1 1 2 2 1 1 2 2 , n n m m c x c x c x b y b y b y + +…+ ≤ + +…+ что и требо- валось доказать. Следствие (достаточный признак оптимальности). Если X и Y — до- пустимые решения взаимно двойственных задач, для которых выполняет- ся равенство ( ( , ) ) Z Z X Y ∗ = то X — оптимальное решение прямой задачи, а Y —двойственной задачи. На основе приведенного следствия из слабой теоремы двойственности можно составить а л г о р и т м, позволяющий проверить, являются ли X и Y оптимальными в прямой и двойственной задачах соответственно. 1. Проверить, принадлежит ли X множеству допустимых решений прямой задачи; если нет, то данные X и Y неоптимальные. 2. Вычислить значение целевой функции прямой задачи в точке X 3. Составить двойственную задачу и проверить, принадлежит ли Y мно- жеству ее допустимых решений; если нет, то данные X и Y неоптимальные. 4. Вычислить значение целевой функции двойственной задачи в точке Y 5. Сравнить значения целевых функций прямой и двойственной задач, если совпадают, то данные X и Y оптимальны, иначе — неоптимальные. Пример 5.3.Определить, являются ли (1, 0, 2) X = и (1; 0) Y = оптималь- ными в прямой задаче L и двойственной к ней L * соответственно, если прямая задача имеет следующий вид: 1 2 3 ( ) 4 max, Z X x x x = + + → 1 2 3 1 2 3 1 2 3 5 12 2 9, : 3 10 4 11, 0; 0; 0. x x x L x x x x x x + + = + + = ≥ ≥ ≥ Решение. Действуем по вышеописанному алгоритму. 1. Подставим X в ограничения прямой задачи L: 5 + 4 = 9; 3 + 8 = 11; 1 ≥ 0; 0 ≥ 0; 2 ≥ 0. Все ограничения выполняются, следовательно, переходим к следу- ющему пункту. 2. Вычисляем значение целевой функции прямой задачи в точке : X ( ) Z X |