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

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

9.17. метод отсечения для целочисленных задач линейного программирования

Дана полностью целочисленная задача линейного програм-vuipOBaiuM:

л

/= Е УМ (max),

(9.47)

ft

£ aiJXj=bi, i = l, 2, m,

(9.48)

j-1

 

x^<iJ-, 2, л, x} — целое, j'= 1, 2,и.

(9.49) (9.50)

Методы отсечений опираются на следующее утверждение; если ослабление задачи (9.47)—(9.50) имеет нецелочисленное оптимальное опорное решение а0, то существует неравенство вида

t (9-51>

которому а0 не удовлетворяет, а любое допустимое решение исходной целочисленной задачи — удовлетворяет.

Неравенство (9.51), обладающее указанными свойствами, называют правильным отсечением. Правильное отсечение, например, можно построить следующим образом.

Симплекс-таблицу для ослабления задачи (9.47)—(9.50) приведем к базису а0, все оценки которого не положительны. Ц полученной таблице выбираем строку с дробным свободным членом dp:

 

 

 

х1

 

 

 

 

 

 

 

 

 

 

 

*<

 

 

*0

Обозначим через [а„] целую часть числа ак {q — , 2, л) т. е. ближайшее целое число, не превосходящее aw, а через [dp] — целую часть числа dr. Правильное отсечение в этом случае имеет вид

 

... +(ap„-[apn]) x^dp-[dpJ. О Рассмотрим симплекс-таблицу

 

*|

ч

Х4

 

1/2

-5/2

1

0

3/2

-7/2

5/3

0

1

7/3

-2

-1

0

0

5

Так как [1/2] = 0, [-5/2]=-3, [1] = 1, [0] = 0, [3/2]= 1, то по первой строке можно построить правильное отсечение (1/2) xt +(1/2) дг2> 1/2. Аналогично, по второй строке строится правильное отсечение (1/2) Х + (2/3) х{21/3. 0

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

Для решения целочисленной задачи линейного программирования (9.47)—(9.50) методом отсечений необходимо выполнить ряд последовательных шагов. На каждом шаге решается задача линейного программирования; если эта задача оказывается нера^ зрешимой, то и исходная целочисленная задача является неразрешимой.

Первый шаг. Находим оптимальное опорное решение

/?1 = (хг.   хг'          xi1*)   ослабления   целочисленной задачи

(9.47)~(9.50). Если р окажется целочисленным, то оно — искомое. В противном случае строим правильное отсечение, записываем его в виде

ZWx;-xn+l=zAw,x„^0, j-v

и добавляем к системе ограничений исходной задачи.

лг-й шаг (к^2). Находим оптимальное опорное решение fik=(xk х* ...; х(~ xfiu ...; х**і*_і) ослабления задачи, построенной на предыдущем шаге. Если fik целочисленно, то ик={хк),

xfh ...; х[к)) — оптимальное решение исходной задачи (9,47)— (9.50).  В  противном  случае  строим  правильное отсечение

£ Xf* Xj—х„+к= Д , x„+Jt> 0 и добавляем его к системе ограни-j-i

чений задачи, полученной на (к — 1)-м шаге. После этого выполняем (к+ 1)-й шаг.

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

 

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