Имя материала: Математика в экономике

Автор: Солодовников А.С.

§ 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 можно непосредственно

применить симплекс-метод. Исходная симплекс-таблица будет иметь вид

Заметим, что соответствующая таблица для задачи Г может быть составлена исходя из таблицы I автоматически на основании соответствия (9.30) и правил 1, 2, 3. Она запишется как таблица Г.

Однако следует иметь в виду, что таблица Г не обязательно является симплекс-таблицей в полном смысле, поскольку числа -с|, -с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')

 

Ясно, что любое линейное уравнение Д|Х( + а2х2 + азхг = 0 может быть заменено эквивалентной ему системой из двух неравенств а(Х| + а2лс2 + аз*з - 0 и ах + alxl+ аз-*з - т- е. системой вида

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х4- 5х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.

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 |