Клюшин В.Л. Высшая математика для экономистов

Подождите немного. Документ загружается.

121

В более компактном виде целевая функция и система ограни-

чений обычно записываются так:

f c x

j j

= →

∑

max,

a x b i m

ij j

∑

≤ =

1 2, , , , ,…

x j n

≥ =0 1 2, , , , .…

Предположим, что имеется покупатель, желающий перекупить

частично или полностью ресурсы, запасенные для выполнения

рассматриваемой задачи. В рыночной экономике, как правило,

категорических отказов не бывает, обычно все определяется це-

ной и условиями продажи.

Рассмотрим двойственную задачу, решение которой позволит

определить условия продажи ресурсов. Обозначим оценку (це-

ну) i-го ресурса через y

, тогда вектор этих оценок будет иметь

вид Y = (y

, y

, …, y

)′.

Затраты на приобретение i-го вида сырья в количестве b

рав-

ны, очевидно, b

. Покупатель, естественно, желает заплатить

поменьше, поэтому для него целевая функция имеет вид

ϕ = b

+ b

+ … + b

→ min. (10.5)

Однако производителю, выступающему продавцом, выгодно

так оценить свои ресурсы, чтобы суммарная их стоимость, расхо-

дуемая на каждое изделие j-й продукции, была не меньше прибы-

ли c

, которую он получил бы при реализации этого изделия, т.е.

+ a

+ … + a

≥ c

Следовательно, система ограничений задачи имеет вид

a y a y a y c

a y a y a y

m m

11 1 21 2 1 1

12 1 22 2 2

+ + + ≥

…

a y a y a y c

n n mn m n

1 1 2 2



…+ + + ≥













(10.6)

Кроме того, очевидно, оценки всех видов ресурсов неотрица-

тельны:

≥ 0, i = 1, 2, …, m. (10.7)

122

Итак, условия (10.5)–(10.7) определяют новую задачу линей-

ного программирования. Она называется двойственной к исход-

ной задаче (10.2)–(10.4).

Рассмотрим подробнее связь исходной и двойственной задач:

коэффициенты c

целевой функции исходной задачи являются

свободными членами системы ограничений (10.6) двойствен-

ной задачи;

свободные члены b

системы ограничений (10.3) исходной за-

дачи являются коэффициентами целевой функции двойствен-

ной задачи;

матрица коэффициентов системы ограничений двойственной

задачи является транспонированной матрицей коэффициен-

тов системы ограничений исходной задачи.

Далее мы узнаем, что если одна из двойственных задач имеет

оптимальное решение, то и другая также имеет оптимальное ре-

шение (см. теорему 10.4).

Рассмотренная пара задач относится к так называемым сим-

метричным парам двойственных задач. В теории двойственности

рассматриваются две симметричные пары двойственных задач.

Приведем их в матрично-векторной форме (с л е в а – исходная

задача, с п р а в а – двойственная ей):

1. f = CX → max,

ϕ = YB → min,

AX ≤ B,

YA ≥ C, (10.8)

X ≥ 0;

Y ≥ 0.

2. f = CX → min,

ϕ = YB → max,

AX ≥ B,

YA ≤ C, (10.9)

X ≥ 0;

Y ≥ 0.

Напомним, что здесь

C = (c

, c

, …, c

), Y = (y

, y

, …, y

a a a

m m mn









11 12 1

21 22 2

1 2



   



















=, ,B

 













Заметим, что в теории двойственности используются и несим-

метричные пары двойственных задач (их также две), но мы их

рассматривать не будем.

12

Сформулируем теперь более четко правила составления

двойственной задачи:

Целевая функция ϕ двойственной задачи должна оптимизиро-

ваться противоположным по сравнению с f образом, т.е. если

f → max, то ϕ → min, и наоборот.

В правых частях ограничений исходной задачи стоят коэффици-

енты при неизвестных целевой функции двойственной задачи.

Матрицы из коэффициентов при неизвестных в левых частях

ограничений обеих задач (исходной и двойственной) являют-

ся взаимно транспонированными. При этом если исходная

задача имеет размер m × n (m ограничений с n неизвестными),

то двойственная – размер n × m.

П р и м е р 10.2. Составить задачу, двойственную к данной:

f = x

+ 4x

+ x

→ max,

− + + ≤

− − − ≤ −

+ + ≤





x x x

1 2 3

2 4

2 3 6

3 2 9







≥ 0, j = 1, 2, 3.

Р е ш е н и е. Умножим правые части ограничений на соот-

ветствующие переменные двойственной задачи и составим целе-

вую функцию (которая должна минимизироваться, так как целе-

вая функция исходной задачи максимизируется):

- 6y

+ 9y

→ min.

Далее транспонируем матрицу коэффициентов при неизвест-

ных в левых частях ограничений исходной задачи, меняем все нера-

венства на противоположные, а в правых частях записываем соот-

ветствующие коэффициенты целевой функции исходной задачи:

− − + ≥

− + ≥









y y y

1 2 3

2 3 1

2 3 4

2 1



Окончательно получаем двойственную задачу в виде

ϕ = 4y

- 6y

+ 9y

→ min,

− − + ≥

− + ≥









y y y

1 2 3

2 3 1

2 3 4

2 1



≥ 0, i = 1, 2, 3.

12

П р и м е р 10.3. Составить задачу, двойственную к данной:

f = 2x

+ 3x

+ 2x

→ min,

x x x x

1 2 3 4

2 3 9

2 2 8

− + + ≥

− − + + ≤ −











≥ 0,

j = 1, .4

Р е ш е н и е. Так как целевая функция минимизируется, то

все ограничения-неравенства должны иметь вид «≥». Поэтому

преобразуем исходную задачу, умножив второе ограничение-

неравенство на -1:

f = 2x

+ 3x

+ 2x

→ min,

x x x x

1 2 3 4

2 3 9

2 2 8

− + + ≥

+ − − ≥











≥ 0,

j = 1, .4

Составим теперь двойственную задачу подобно тому, как это

делалось в предыдущем примере:

ϕ = 9y

+ 8y

→ max,

y y

1 2

2 0

2 3

3 2 2

+ ≤

− + ≤

− ≤













≥ 0, i = 1, 2.

Теоремы двойственности устанавливают связь между оптималь-

ными решениями пары двойственных задач.

Рассмотрим симметричную пару двойственных задач (10.8):

I. f = CX → max,

II. ϕ = YB → min,

AX ≤ B,

YA ≥ C,

X ≥ 0.

Y ≥ 0.

(Напомним, что если задача I имеет размер m × n, то задача II –

размер n × m.)

Отметим основное неравенство теории двойственности.

Т е о р е м а 10.3. Пусть X – любое допустимое решение ис-

ходной задачи I, а Y – любое допустимое решение двойственной

задачи II. Тогда имеет место неравенство

f(X) ≤ ϕ(Y).

(10.10)

12

Д о к а з а т е л ь с т в о. Так как все переменные в обеих зада-

чах неотрицательные, получаем (с учетом YA ≥ C):

f(X) = CX ≤ (YA)X.

()

В силу ассоциативности умножения матрицы и с учетом AX ≤ B

(YA)X = Y(AX) ≤ YB = ϕ(Y ).

()

Соединяя () и (), получаем

f(X) ≤ ϕ(Y ),

что и требовалось доказать.

Заметим, в частности, что применительно к задаче, рассмот-

ренной в примере 10.3, неравенство (10.10) означает

+ 3x

+ 2x

≤ 9y

+ 8y

С л е д с т в и е из основного неравенства: если допустимое

множество одной из задач I, II не пусто, то целевая функция дру-

гой задачи ограничена в направлении экстремума на своем допус-

тимом множестве.

Действительно, пусть, например, множество D исходной зада-

чи I не пусто, т.е. существует хотя бы одна точка X

∈ D. Тогда,

согласно неравенству (10.10), для любой точки Y из допустимого

множества задачи II выполняется неравенство ϕ(Y) ≥ f (X

т.е. все значения функции ϕ ограничены снизу одним и тем же

числом f(X

Т е о р е м а 10.4 (основная теорема двойственности). Если од-

на из двойственных задач I или II имеет оптимальное решение, то

и другая задача имеет оптимальное решение, причем экстремаль-

ные значения целевых функций равны:

max f = min ϕ.

(10.11)

(Примем эту теорему без доказательства.)

Одним

из важных следствий основной теоремы двойственно-

сти является критерий оптимальности допустимых решений. Рас-

смотрим его. Пусть X

и Y

– допустимые решения исходной и

двойственной задач I и II. Для того чтобы эти решения были опти-

мальными, необходимо и достаточно выполнение равенства

f(X

) = ϕ(Y

). (10.12)

Д о к а з а т е л ь с т в о. 1. Необходимость. Пусть X

и Y

– оп-

тимальные решения. Тогда f(X

) = max f, ϕ(Y

) = min ϕ и равен-

ство (10.12) следует из основной теоремы двойственности.

12

2. Достаточность. Пусть выполняется равенство (10.12) и

пусть X – произвольная точка, принадлежащая допустимому мно-

жеству исходной задачи. Тогда, в силу основного неравенства

(10.10), имеем f(X) ≤ ϕ(Y

) = f(X

). Следовательно, f(X

) = max f,

т.е. X

– точка максимума. Аналогично доказывается, что точка Y

для которой выполняется равенство (10.12), есть точка минимума.

Т е о р е м а 10.5 (вторая теорема двойственности). Для того что-

бы допустимые решения X = (x

, x

, …, x

)′ и Y = (y

, y

, …, y

) явля-

лись оптимальными решениями пары двойственных задач I и II,

необходимо и достаточно, чтобы выполнялись следующие ра-

венства:

x a y c j n

j ij i j

−













= =

∑

0 1, , ;2, ,…

(10.13)

y a x b i m

i ij j i

−













= =

∑

0 1, , .2, ,…

(10.14)

(Эту теорему примем без доказательства.)

Выясним смысл равенств (10.13) и (10.14). Например, второе

из них означает, что если при подстановке оптимального решения

в систему ограничений (10.3) i-е ограничение исходной задачи

выполняется как строгое н е р а в е н с т в о, то i-я координата оп-

тимального решения двойственной задачи равна нулю. Напротив,

если i-я координата оптимального решения двойственной задачи

отлична от нуля, то i-е ограничение исходной задачи при подста-

новке оптимального решения обращается в р а в е н с т в о.

Условия (10.13) и (10.14) устанавливают в некотором смысле

равновесие между задачами I и II. Поэтому теорему 10.5 называют

также теоремой равновесия.

П р и м е р 10.4. Решить задачу

+ 3x

- 30x

→ min,

x x

1 3

2 3

6 1

5 2

− ≥











, x

≥ 0.

Р е ш е н и е. В данной задаче три переменных. Решить ее гра-

фически, подобно тому, как это сделано в примере 10.1, нельзя.

Составим для этой задачи двойственную, решим ее графическим

12

методом, а затем, применяя вторую теорему двойственности, ре-

шим исходную задачу.

Итак, составляем двойственную задачу:

+ 2y

→ max,

y y

1 2

4 1

3 2

6 5 30 3

≤

− − ≤ −











, ( )

, y

≥ 0.

Решим ее графическим методом. На рис. 10.2 изображены область

допустимых решений, нормаль

= (1, 2) и оптимальное реше-

ние – точка (4, 3).

(1)

(2)

(3)

5 10

рис. 10.2

Теперь находим решение исходной задачи с помощью второй

теоремы двойственности. Так как третье ограничение двойствен-

ной задачи есть строгое неравенство при y

= 4, y

= 3, то x

= 0.

Далее, так как y

> 0, y

> 0, то x

- 6x

= 1, x

- 5x

= 2, откуда x

= 1,

= 2. Следовательно, оптимальное решение исходной задачи есть

точка (1, 2, 0).

П р и м е р 10.5. С помощью второй теоремы двойственности

решить задачу

+ 6x

+ 3x

→ min,

3 3 0

2 2

1 2

1 2 3

+ − ≤

− + ≥











x x

x x x

, x

≥ 0.

12

Р е ш е н и е. Составим для этой задачи двойственную. Снача-

ла приведем все неравенства к виду «≥», так как целевая функция

минимизируется:

+ 6x

+ 3x

→ min,

− + ≥











x x

x x x

1 2

1 2 3

3 3

2 2

, x

≥ 0.

Напишем теперь двойственную задачу:

+ 2y

→ max,

− + ≤

− ≤

≤











y y

1 2

3 2 6

, y

≥ 0.

Эта задача совпадает с задачей, рассмотренной в примере 10.1

(только там переменные x

, x

, а здесь y

, y

). Воспользуемся ее

решением: y

= 4, y

= 3.

Так как первое ограничение двойственной задачи выполняется

как строгое неравенство, то x

= 0. Так как y

> 0, y

> 0, то

− + =











x x

x x x

1 2

1 2 3

3 3

2 2

откуда x

= 1, x

= 4.

Итак, оптимальное решение исходной задачи есть (0, 1, 4).

Рассмотрим теперь задачу с четырьмя переменными, кото-

рую также можно свести к двойственной задаче, решаемой гра-

фически.

П р и м е р 10.6. Для

данной задачи составить двойственную,

решить ее и с помощью второй теоремы двойственности найти

решение ее исходной задачи:

+ x

- 3x

+ x

→ max,

x x x

x x x x

1 2 4

1 2 3 4

2 4

3 1

+ − ≤

− + + ≤











, x

≥ 0.

12

Р е ш е н и е. Составим двойственную задачу:

+ y

→ min,

y y

1 2

2 1

3 1

+ ≥

− ≥

≥ −

− + ≥











, y

≥ 0.

Решив ее графическим методом (проделайте это самостоятельно),

находим точку (1, 1).

Теперь применим вторую теорему двойственности для на-

хождения решения исходной задачи. Мы видим, что третье и

четвертое ограничения двойственной задачи выполняются как

строгие неравенства. Следовательно, x

= 0, x

= 0. Кроме того,

так как y

> 0, y

> 0, то

x x x

x x x x

1 2 4

1 2 3 4

2 4

3 1

+ − =

− + + =











откуда (с учетом x

= x

= 0) получаем x

= 2, x

= 1. Следовательно,

оптимальное решение исходной задачи есть точка (2, 1, 0, 0). При

этом, очевидно,

f(X)

max

= ϕ(Y )

min

= 5.

вопросы

Что такое технологическая матрица?

Что называется задачей оптимизации? Как она записывается?

Что называется допустимым решением задачи оптимизации?

Какое решение называется оптимальным?

Как формулируется общая задача линейного программирова-

ния?

Как связаны между собой исходная и двойственная задачи

линейного программирования?

Пусть исходная задача линейного программирования имеет

размер m × n. Каков размер двойственной задачи?

В чем заключается основное неравенство теории двойствен-

ности?

Как формулируется основная теорема двойственности?

Может ли задача линейного программирования с двумя пе-

ременными быть двойственной к задаче с пятью перемен-

ными?