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

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

9.5. опорные решения задачи линейного программирования в канонической форме

Допустимое решение а задачи (9.7)—(9.9) в канонической форме называется опорным решением этой задачи, если векторы условий Аі^,АІ2,...,Аік, где iviv ik — номера всех ненулевых координат а, образуют линейно независимую систему векторов.

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

/= 3xj + 4х2 - х3 + x4(min),

Х^ ~Ь   Х^ "І" Х1^ ~~ х^ = 35 xj >0,  у = 1,2,3,4.

 

228

Векторы условий А3 =

образуют, очевидно,

 

 

 

 

 

,2,

,АЪ =

-1,

,А^ —

 

ли

линейно независимую систему. Значит, а, является опорным решением данной задачи. Векторы Ау -

нейно зависимы. Поэтому сс2 не является опорным решением. • Свойства опорных решений:

Г. Если допустимое множество задачи (9.7)—(9.9) в канонической форме не пусто, то эта задача имеет опорное решение.

2°. Опорные решения задачи (9.7)—(9.9) являются крайними точками допустимого множества этой задачи. (Допустимое множество всегда выпукло.)

3°. Задача (9.7)—(9.9) в канонической форме имеет лишь конечное число различных опорных решений (либо не имеет их вовсе).

Чтобы найти некоторое опорное решение задачи (9.7)—(9.9), достаточно выбрать базис системы векторов условий Ау,А2, —,Ап этой задачи так, чтобы вектор ограничений В раскладывался по нему с неотрицательными коэффициентами.

Если Af^Af^Ajr — такой базис и В = A^d^ + 4242 + — + W' dt >0,то

dh^0,di2>0,

0,^,0,...,0,^,0,...,0)

а = (0, ...,0,4:,О,

является опорным решением задачи (9.7)—(9.9).

Базис Аіі,АІ2,...,Аіг системы векторов условий АрА2,...,Ап задачи (9.7)—(9.9) называется базисом опорного решения a = (dvd2,..., dn) этой задачи, если d. - 0 при / Ф iv i2,іҐ

О Пример. Рассмотрим опорное решение а = (1; 0; 0; 1) задачи /= Ху + х2 - х3 + x4(min), Iх-^ — х^ ~ь     И- Х4 = 2,

Х-^ ~г"        ^4 =

229

 

Так как вторая и третья координаты вектора а равны 0, то Ах, А4 является базисом опорного решения а. С другой стороны, четвертая координата а отлична от нуля. Следовательно, Av А2 не будет базисом а. •

У любого опорного решения задачи (9.7)—(9.9) не может быть более чем г ненулевых (положительных) координат, где г = r(Av А2, Ап), т.е. г равно рангу системы векторов условий. Опорное решение называется невырожденным, если число его ненулевых координат точно равно г, и вырожденным — в противном случае.

Любое опорное решение имеет базис. При этом у невырожденного опорного решения базис только о д и н, а вырожденное опорное решение может иметь несколько различных базисов.

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

9.6. Признак оптимальности опорного решения задачи линейного программирования в канонической форме. Условие неограниченности целевой функции

По задаче линейного программирования в канонической форме (9.7)—(9.9) всегда можно составить симплекс-таблицу (табл. 9.2).

Предположим, что а = (dx, d2, dn) — некоторое опорное решение задачи (9.7)—(9.9), а векторы Аіі,АІ2,Aj образуют его базис. Тогда табл. 9.2 можно преобразовать методом Гаусса (см. п. 2.4) в табл. 9.3.

230

Прибавим к последней строке табл. 9.3 первую строку, умноженную на у^, вторую строку, умноженную на уІ2, r-ю строку, умноженную на у, . В результате получим новую таблицу (табл. 9.4), где dti,di2, dt — координаты опорного решения, соответствующие векторам базиса А^,А^,...,А.

Здесь 8^ = 8^ = ... = 8ir = 0 a 80 = /(а) (значение целевой функции на опорном решении а).

Таблица 9.4, полученная указанным способом, называется симплекс-таблицей, приведенной к базису Ati,Aii,...,Air опорного решения а, а числа bv 8^, §І2,5f,8S, 8й — оценками этого базиса.

Для задачи минимизации имеют место следующие утверждения:

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

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

231

3. Предположим, что симплекс-таблица для задачи линейного программирования в канонической форме приведена к базису некоторого опорного решения. Если среди оценок этого базиса имеется положительная оценка 6^, а все остальные элементы s-ro столбца таблицы не положительны, то целевая функция не ограничена снизу на допустимом множестве (условие неограниченности целевой функции).

О Пример. Рассмотрим опорное решение а = (1; 0; 0; 0) задачи / = -1(Ц + х2 - 9х3 + 6x4(min),

{

Ху + х2 + Зх3        = 1,

х-^   х^     х^ ~~     — 13 х.>0, ; = 1,2, 3,4.

Приведем симплекс-таблицу для этой задачи к базису Av А2 опорного решения ос:

 

х1

х2

*4

 

 

х1

х2

*4

 

 

1

1

3

0

1

 

1

1

3

0

1

 

1

-1

-1

2

1

->

0

-2

-4

2

0

->

10

-1

9

-6

0

 

10

-1

9

-6

0

 

 

х1

Х2

*4

 

 

*1

 

*4

 

 

1

0

1

1

1

 

1

0

1

1

1

 

0

1

2

-1

0

 

0

1

2

-1

0

 

10

-1

9

-6

0

 

0

0

1

-17

-10

Среди оценок базиса Av А2 есть положительная оценка 53 = 1. Значит, утверждать на этом этапе, что а — оптимальное решение, мы не можем.

232

С другой стороны, возьмем базис Av Аг того же опорного решения а. Приведя симплекс-таблицу к этому базису, получим

Страница: | 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 |