Составители:
Рубрика:
30
хних границ. Для пояснения сказанного рассмотрим систему (51).
Найти x
1
≥ 0 и x
2
≥ 0 такие, что
x
0
= x
1
+ x
2
= x
0max
;
x
1
+9/16 x
2
≤ 51/16; (51)
– 2 x
1
+ x
2
≤ 1/3;
x
1
и x
2
– целые.
Симплекс, удовлетворяющий условиям (51), приведен на рис. 6. Ре-
шения, удовлетворяющие четвертому условию, показаны точками. Без
этого условия решением задачи является точка A с координатами (3/2,
10/3), в которой достигается максимум x
0
, равный 29/6. Ближайшими
целочисленными значениями для x
1
являются 1 и 2. Рассмотрим реше-
ние задачи (51) сначала при условии x
1
<= 1, а потом при условии x
1
>= 2.
Тем самым симплекс S разбивается на два непересекающихся симплек-
са S
1
и S
2
(рис. 7). В обоих симплексах без учета целочисленности реше-
ниями задачи будут соответственно точки C и B с координатами (1, 7/3)
и (2, 23/9) и максимальными значениями x
0
, равными 10/3 и 41/9.
Значение x
0max
в симплексе S
1
с учетом целочисленности x
1
и x
2
не
может быть больше 10/3, а в симплексе S
2
– может, хотя и не превысит
значение 41/9. Поэтому дальнейший поиск x
0max
осуществляется в S
2
.
Ближайшими к оптимальному значению x
2
= 23/9 являются целочис-
ленные точки со значениями x
2
= 2 и x
2
= 3. Поэтому рассматривается
решение задачи (51) с учетом (помимо дополнительного условия x
1
>= 2)
сначала условия x
2
<= 2, а потом x
2
> = 3. Тем самым симплекс S
2
разби-
вается на симплекс S
21
и несуществующий симплекс S
22
(рис. 8). В пер-
вом оптимальной является вершина D с координатами x
1
= 33/16, x
2
= 2
Рис. 6. Постановка задачи Рис. 7. Разбиение симплекса S
x
2
A
S
x
2
2
2
1
1
5
4
0
0
x
1
x
1
4
5
С
B
S
1
S
2
Страницы
- « первая
- ‹ предыдущая
- …
- 28
- 29
- 30
- 31
- 32
- …
- следующая ›
- последняя »
