Имя материала: Справочник по математике для экономистов

Автор: В.И. Ермаков

9.10. теоремы двойственности в линейном программировании

Основные утверждения о взаимно двойственных задачах содержатся в двух следующих теоремах.

Первая теорема двойственности. Для взаимно двойственных задач (9.25)—(9.28) и (9.29)—(9.32) имеет место один из четырех взаимоисключающих случаев:

Обе задачи (прямая и двойственная) имеют оптимальные решения, причем значения целевых функций на оптимальных решениях совпадают.

В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена сверху. При этом у двойственной задачи будет пустое допустимое множество.

В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи пустое допустимое множество.

Обе задачи (прямая и двойственная) имеют пустые допустимые множества.

Вторая теорема двойственности. Пусть сс° = (х°, х\%,х?,x°) —

допустимое решение прямой задачи (9.25)—(9.28), а Р° = (у®, у\%, у9,     yfy — допустимое решение двойственной задачи (9.29)— (9.32). Для того чтобы а0 и Р° были оптимальными решениями соответственно задач (9.25)—(9.28) и (9.29)—(9.32), необходимо и достаточно, чтобы выполнялись следующие соотношения:

( т

Х°

= 0, / = 1,2,..., и, (9.33)

i=l J

Л

= 0,    / = 1,2,..., т. (9.34)

 

Условия (9.33), (9.34) позволяют, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное решение другой задачи. Поэтому для решения некоторой задачи линейного программирования можно вначале решить двойственную ей задачу, а затем определить оптимальное решение исходной задачи.

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

 

240

На основании второй теоремы двойственности можно сформулировать критерий оптимальности для допустимого решения задачи линейного программирования.

Критерий оптимальности. Пусть а0 = (х,, х2, ...,х^, х°п) — допустимое решение задачи (9.25)—(9.28). Вектор а0 является оптимальным решением этой задачи тогда и только тогда, когда среди решений системы уравнений

т

2>^,-уу. = 0    прих°*0, (9.35)

г=1

у,=0   приХаЛ0<й,. (9.36)

У=1

содержится хотя бы одно допустимое решение задачи (9.29)—(9.32), двойственной к задаче (9.25)—(9.28).

О Пример. Вектор а = (3; 0; 1; 3) является допустимым решением задачи

/= -2ху - х2 + х3 + х4(тах),

Х-^      Х^ Н~ 2^С^       ^4 =

Зх2 - 7х3 + Зх4 = 2,

х^ И- 2-Х^        = 2Э

Xj>0, j= 1,2, 3,4.

В данном случае соотношения вида (9.36) отсутствуют, а из условий (9.35) имеем

У       = -2,

' 2уу - 1у2 + 2^з = 1,

ГУ + ЪУ2        = L Отсюда ух - -2, у2 - -1/3, у3 - 4/3. Нетрудно проверить, что Р - (-2; -1/3; 4/3) — решение системы ограничений двойственной задачи

' У!     > -2,

-Уі + 3j>2 + Уз> -1> 2-Уі ~ 7у2 + 2Уз ^ -^+3у2 >1.

 

241

Следовательно, а = (3; 0; 1; 3) — оптимальное решение нашей задачи (из второй теоремы двойственности сразу следует, что Р = (-2; -1/3; 4/3) — оптимальное решение задачи, двойственной к данной). •

Страница: | 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 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 | 151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 | 176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 |