Составители:
Рубрика:
31
и значением целевой функции x
0max
= 61/16. Переменная x
2
является
целочисленной. Ближайшими к оптимальному x
1
= 33/16 являются це-
лочисленные значения x
1
= 1 и x
2
= 2. Поэтому задача (51) решается с
учетом сначала x
1
< = 2, а потом x
1
> = 3. Симплекс S
21
разбивается при
этом на S
211
и S
212
(рис. 9). В первом оптимальной вершиной является F,
а во втором – вершина E с координатами соответственно (2, 2) и (3, 1) и
одинаковым значением x
0max
, равным 4. Поскольку полученное значе-
ние x
0max
для целочисленных переменных x
1
и x
2
больше, чем оценки
x
0max
в нерассмотренных симплексах, то оно тем более больше самих
значений x
0max
в этих симплексах. Это означает, что последнее значение
x
0max
является наибольшим для всего симплекса S и, следовательно, яв-
ляется окончательным решением задачи. На рис. 10 приведено тради-
ционное изображение графа решения методом ветвей и границ рассмот-
ренной задачи, в котором наглядно видно, что последнее значение x
0max
больше, чем оценка x
0max
для любой не-
развернутой вершины графа. Если бы
нашлась такая, у которой оценка x
0max
больше, чем найденное значение x
0max
,
то пришлось бы вернуться к соответ-
ствующему симплексу и искать в нем
решение задачи.
В реальных задачах такие возвраты
приходится выполнять довольно часто,
поэтому решение задачи затягивается.
В большинстве крупных машинных
программ, реализующих частично цело-
численные алгоритмы, используется
Рис. 8. Разбиение cимплекса S
2
Рис. 9. Разбиение симплекса S
21
2
D
x
2
x
2
x
1
x
1
1
2
1
0
0
4
4
5
5
E
F
S
21
S
212
S
211
Рис. 10. Граф решения задачи
методом ветвей и границ
S, A
29 / 6
S
1
, C
10 / 3
S
2
, B
41 / 9
S
21
, D
61 / 14
S
22
, –
–
S
211
, E
4
S
212
, F
4
Страницы
- « первая
- ‹ предыдущая
- …
- 29
- 30
- 31
- 32
- 33
- …
- следующая ›
- последняя »
