§ 9.4. доказательство основной теоремы двойственности. метод одновременного решения пары двойственных задач
§ 9.4. доказательство основной теоремы двойственности. метод одновременного решения пары двойственных задач
Рассмотрим снова взаимно двойственные задачи I и Г. Между их решениями существует, как мы знаем, связь, выражаемая равенством max/ = min ф.
В действительности эта связь намного глубже. Оказывается, что симплекс-метод, примененный к одной из задач, автоматически
решает и другую.
Для сокращения записей снова будем считать, что задача I имеет размеры 2 х 3, а задача Г размеры 3x2. Произведем ряд уточнений.
1. Представим обе задачи как задачи на нахождение минимума, для чего перейдем в задаче I от функции/к функции F-/. Наконец (смысл этого станет ясен позднее), введем в выражения для / и ф некоторый свободный член d. Тогда в выражении для F появится свободный член -d.
208
14—3700
Если в системе (9.29) числа Ъ и Ь2 неотрицательны, то переменные х4 и х5 образуют в этой системе допустимый базис. Аналогично если -С| > О, -с2 ^ 0, -с2 S 0, то переменные у3, у4, у5 образуют допустимый базис в (9.29'). Чтобы не связывать себя условием неотрицательности свободных членов, расширим на некоторое время понятие допустимого базиса, сняв условие неотрицательности свободных членов. Тогда можно считать, что переменные х4, х5 — независимо от того, какие знаки имеют числа b, b2, -С[, -с2, -сз — являются базисными для задачи I, а переменные у3, у4, у5 — базисными для задачи Г.
3. Между переменными обеих задач можно установить естественное соответствие. Рассмотрим, например, переменную х4, являющуюся базисной в (9.29). В выражении х4 = b а{ |jcj а|2*2 ~ аізх3
КОЭффИЦИеНТЫ При СВОбоДНЫХ Переменных, Т. Є. ЧИСЛа -Яц, -Я|2.
-а|3, лишь знаками отличаются от коэффициентов <3|(, аХ2, а)3 при У) в (9.29'). В соответствии с этим будем считать, что переменной 210 х4 соответствует і>|. Аналогичным образом, если взять, например, переменную у у являющуюся базисной в (9.29'), то можно видеть, что в ее выражении через свободные переменные коэффициенты при последних лишь знаками отличаются от коэффициентов при х( в (9.29). Поэтому считаем, что переменнойу^ соответствует*!. В итоге устанавливаем следующее соответствие:
х4 -> У, х5 -> у2, у3 -» х,, у4 х2, у5 хг,
при котором базисным переменным одной задачи отвечают свободные переменные другой задачи.
Будем считать соответствие взаимным и писать:
x, х2 *3 х4 xs
X X X X X (9.30)
Уъ У а У 5 У У гУстановленное соответствие между переменными позволяет следующим образом охарактеризовать связь между задачами I и Г:
Пусть xi — базисная, a Xj — свободная переменная в задаче I; им отвечают (соответственно) переменные ук и уе в задаче Г:
х, (базисная) ■*/ (свободная)
X X
У к (свободная) Уе (базисная).
Тогда коэффициент, с которым Xj входит в выражение для xjt лишь знаком отличается от коэффициента, с которым ук входит в выражение для уе:
х, = ... + a xj + уе = ... а ук + ... .
Свободные члены в выражениях для базисных переменных одной из задач равны коэффициентам при соответствующих свободных переменных в целевой функции другой задачи.
Свободный член в выражении для F через свободные переменные лишь знаком отличается от свободного члена в выражении для ф.
Справедливо следующее предложение.
Указанная выше связь (см. I, 2, 3) между записями задач I и V сохраняется при согласованных заменах базисов в этих задачах.
Поясним сказанное. Пусть в задаче I производится, например, следующая замена базиса:
х +-» *ф
т. е. переменная х{ из свободных переводится в базисные, а переменная х4, наоборот, из базисных переводится в свободные. Разумеется, для осуществления такой замены необходимо, чтобы было аи#0. В этом случае возможна и замена
Уг «■» УВыделенное курсивом предложение означает, что после осуществления таких согласованных замен связь между записями задач I и Г, указанная в положениях I, 2, 3, сохраняется.
Предоставляем читателю убедиться в справедливости этого предложения, выполнив соответствующие преобразования над записями задач I и Г.
Предположим, что в одной из систем (9.29), (9.29' ) свободные члены в правых частях неотрицательны (именно так и обстояло дело в производственной задаче из § 9.1, где было Ь, > 0 и Ь2 > 0). Пусть, например, Ь > 0, Ь2> 0. Тогда к задаче I можно непосредственно
Однако следует иметь в виду, что таблица Г не обязательно является симплекс-таблицей в полном смысле, поскольку числа -с|, -с2 -Су не обязательно больше или равны 0.
Итак, будем решать симплекс-методом задачу I. После ряда шагов придем к оптимальному решению. В заключительной симплекс-таблице все числа столбца свободных членов (кроме, может быть, последнего числа) и все числа строки F (кроме, быть может, первого числа) неотрицательны. Но тогда на основании правил 1, 2, 3 можем заключить, что в соответствующей таблице для задачи Г также не будет отрицательных чисел — ни в столбце свободных членов, ни в строке для (р (за указанными исключениями). Это означает, что в задаче I' также достигнуто оптимальное решение. При этом, поскольку числа, стоящие на пересечении столбца свободных членов и строки для целевой функции, в обеих таблицах отличаются лишь знаком, приходим к заключению, что min F = -min q> или, что то же самое, max/ = min ф, что и доказывает основную теорему двойственности.
Попутно мы получили следующий метод одновременного решения пары взаимно двойственных задач I и Г. Приводим обе задачи к каноническому виду и устанавливаем соответствие между переменными обеих задач. Далее решаем с помощью симплекс-метода ту из двух задач, где свободные члены в выражениях для базисных неизвестных неотрицательны (предполагается, что одна из задач таким свойством обладает). Из последней симплекс-таблицы выделяем строку для целевой функции. Если числа, стоящие в ней, начиная со второго, взять с противоположными знаками, а затем воспользоваться соответствием между переменными обеих задач, то получим оптимальное решение двойственной задачи. Первое же число в указанной строке дает искомый оптимум целевой функции.
Пример. Пусть в результате решения задачи I получена следующая симплекс-таблица Т:
Предположим также, что соответствие между переменными обеих задач имеет вид (9.30). На основании этих данных запишем решение задачи Г.
Для этого нам достаточно знать лишь фрагмент таблицы Т:
*1 | хг | хъ | *4 | *5 | ||
F | 150 | 0 | -2 | -3 | 0 | -1 |
Учитывая соответствие (9.30), получаем, что оптимальное решение задачи Г будет
Уз = 0,^4 = 2, ^5 = 3,/, = 0,y2=U
причем
min ф = -min f = -150. § 9.5. Несимметричные двойственные задачи
От соответствующих задач I и Г § 9.1 (матричная форма записи
задач) они отличаются тем, что:
а) все ограничения в задаче L имеют вид уравнений, в то время
как в задаче I это неравенства;
б) в задаче L' отсутствует условие неотрицательности неизвестных; таким образом, неизвестные в этой задаче могут быть
любого знака.
Для упрощения записей будем считать, как и в § 9.1, что задача L имеет размеры 2x3. Итак:
Задача L | Задача L' | |
аи х{ +аа*2 + дізх3 = V (9 31) }а2|Х|+а22х2+а23 Х3=Ь2' х,>0,*2>0,х,£0, (9.32) /= с,х, + с^г + с3х3 -► max. (9.33) | ■ і | аиУ +a2i^22cl' °гУ +аг2Уг*с2' (9-31') anyt +а2з>'2-с3' р = Ьіу{+Ь1у2-+тт(9.33') |
I о.Х + а2х2 + аз*з ^ 1 -д)*, «2*2 03*3 ^ -6.
Проделав такую замену с каждым из уравнений (9.31), запишем задачу L в следующем виде: «"'ищем
Задача I | |
а\Х]+аих2 + а]3хійЬ], | |
-ацХ1-апх2-а]3х}і-Ь1, | |
°21 х +a22x2 + a23xj^b2, | |
-агх-^22х2-^1ъхъ<-ьъ | |
X] >0, х2г:0, х3 > 0, | |
f-clxl+c2x2 + сг х3 ->■ max. |
Двойственная задача в смысле § 9.1 будет иметь размеры 3 х 4 Обозначим неизвестные в этой задаче n,,v„«2,v2. Итак:
Задача I' | |
ali и~а\ v[+a2i и2-а2] v2>cv | |
< | a2u-a2vl+ °22 и2 ~ а22 V2 CV |
аіз"і -Ч|з "і +a23 и2-а2ъ v2>c3, | |
"і >0, v, > 0, u2>Q, v2>0, | |
Ф | = bx (u,-v,) + b2 (uj-vd min. |
Если существует решение задачи I, то в силу теоремы двойственности существует и решение задачи Г, причем max/ = тіпФ.
Сравнивая задачи L' и Г, замечаем, что они, в сущности, эквивалентны. В самом деле, если У,у2 — какое-либо решение задачи L', то, взяв любые четыре неотрицательных числа u,, vi,u2, v2, удовлетворяющих условиям
"I -v| =У, и2-2 = у2 (9.34)
(что, очевидно, возможно), получим решение задачи Г. Наоборот, если V,u2, v2, есть решение задачи Г, то числа ух,у2, найденные по формулам (9.34), дают решение задачи L'. Таким образом мы приходим к следующей теореме, которая является, по существу, одним из вариантов теоремы двойственности.
Теорема. Если задача L имеет решение, то задача V также имеет решение; при этом max / = min ср.
В заключение укажем общую постановку взаимно двойственных задач, когда система ограничений включает как уравнения, так и неравенства.
Задача I | Задача Г | ||
а х<в, | (9.35) | aty>c, | (9.35') |
*,><>, | (9.36) | У, > 0, | (9.36') |
/= CrJT-» max. | Ф = вт У-> min. |
Здесь предполагается, что:
В системе (9.35) некоторые ограничения являются неравенствами (типа <), а некоторые — уравнениями. Вектор Yx является частью вектора Y; неизвестное yt входит в Yx, тогда и только
тогда, когда i-e ограничение в системе (9.35) является неравенством.
Система (9.35') также состоит из неравенств (типа >) и уравнений. Вектор Х{ является частью X; неизвестное х^ входит в Х{ тогда и только тогда, когда j-e ограничение в системе (9.35') является неравенством.
Теоремадвойственности (общая ) утверждает, что если разрешима задача I, то разрешима и задача Г, причем max/= min (p.
Пример. Если в качестве исходной задачи взять
2Х| 3*2 + 4jc3х4 + х5<-1, • Х| + 2х2 Зх3 + 4х45х5 < 3, х2 + 5х3 6х5 = 2,
х1>0,х2>0, х3>0,
/= 7х| + х2 х4 + 2х5 -> max,
то двойственная задача будет
*У + Уг 2 7,
-Ь +ІУ2+ Уз^1> ■ 4^,-3^2 + 5^ > О, ->,|+4у2 =-Ц, у{-5у2-6уг = 2,
у{>0,у2>0,
ф = -у + Ъу2 + 2у3 -> min.
Обсуждение Математика в экономике
Комментарии, рецензии и отзывы