ВУЗ:
Составители:
82
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
≤+++
≤+++
≤+++
...
...............................
;...
;...
2211
22222121
11212111
соответствует некоторый выпуклый гипермногогранник (в частности, это множество может
быть пустым или бесконечным).
4) Неотрицательность
0,...,0,0
21
≥≥≥
n
xxx означает, что гипермногогранник ограничений
лежит в первом гипероктанте осей x
1
, x
2
,…, x
n
.
5) Целевой функции Z=c
1
x
1
+c
2
x
2
+…+c
n
x
n
соответствует параллельно перемещающаяся
гиперплоскость c
1
x
1
+c
2
x
2
+…+c
n
x
n
=const (поверхность уровня целевой функции).
6) Максимум (минимум) целевой функции всегда достигается в какой-то вершине
гипермногогранника ограничений (но он может стать бесконечным, если область ограничений
бесконечна).
4.6.2.5. Алгебраическая характеристика вершины многогранника ограничений
Чтобы получить такую характеристику, обратимся снова к двумерной картинке. В этом
случае вершина соответствующего многоугольника есть точка пересечения каких-то его двух
сторон (l
r
) и (l
s
), которые изображают границу r-го и s–го ограничений, т.е. имеют своими
уравнениями прямые
(l
r
): a
r1
x
1
+a
r2
x
2
=b
r
;
(l
s
): a
s1
x
1
+a
s2
x
2
=b
s
.
В трехмерном случае (т.к. точка трехмерного пространства определяется пересечением
трех плоскостей) вершину многогранника ограничений можно охарактеризовать уравнениями тех
трех граней (П
r
), (П
s
) и (П
t
), пересечением которых она является:
(П
r
): a
r1
x
1
+a
r2
x
2
+a
r3
x
3
=b
r
;
(П
s
): a
s1
x
1
+a
s2
x
2
+a
s3
x
3
=b
s
;
(П
t
): a
t1
x
1
+a
t2
x
2
+a
t3
x
3
=b
t
.
Заметим, что некоторые вершины могут попасть на одну из координатных плоскостей или
на одну из координатных осей, как, например, в задаче 5 раздела 4.6.2.3. Для такой вершины будет
выполняться одно или два из уравнений x
1
=0, x
2
=0, x
3
=0 (и если, в частности, начало координат
является вершиной, то выполняются все три уравнения).
Наконец, в случае n-мерной задачи надо считать, что вершина характеризуется как
пересечение соответствующих n гиперплоскостей (в том числе, возможно, и координатных
гиперплоскостей).
Для дальнейшего будет удобно каждое ограничение
a
i1
x
1
+a
i2
x
2
+…+a
in
x
n
≤
b
i
(i=1,2,…,m)
записывать в виде
b
i
- a
i1
x
1
-a
i2
x
2
-…-a
in
x
n ≥
0
или, что то же самое, в виде
a
i1
(-x
1
)+a
i2
(-x
2
)+…+a
in
(-x
n
)+b
i
≥ 0 (i=1, 2,…, m).
Будем рассматривать левую часть ограничения как новую переменную y
i
, т.е. положим
y
i
= a
i1
(-x
1
)+a
i2
(-x
2
)+…+a
in
(-x
n
)+b
i
(i=1, 2,…, m),
так что совокупность ограничений теперь запишется в виде
,0,...,0,0
21
≥≥≥
m
yyy
а вместе с требованием неотрицательности получим единообразную запись для всех ограничений:
.0,...,0,0,0,...,0,0
2121
≥≥≥≥≥≥
mn
yyyxxx
Заметим, что дополнительные переменные имеют простой экономический смысл. Так как
y
i
=b
i
-(a
i1
x
1
+a
i2
x
2
+…+a
in
x
n
),
то y
i
представляет собой остаток i-го производственного ресурса (из его запаса b
i
) после того, как
при реализации плана x
1
, x
2
,…, x
n
он затрачен в количестве
a
i1
x
1
+a
i2
x
2
+…+a
in
x
n
.
82
a11 x1 + a12 x 2 + ... + a1n xn ≤ b1 ;
a 21 x1 + a 22 x 2 + ... + a2 n xn ≤ b2 ;
...............................
a m1 x1 + a m 2 x2 + ... + a mn x n ≤ bm
соответствует некоторый выпуклый гипермногогранник (в частности, это множество может
быть пустым или бесконечным).
4) Неотрицательность x1 ≥ 0, x2 ≥ 0,..., xn ≥ 0 означает, что гипермногогранник ограничений
лежит в первом гипероктанте осей x1, x2,…, xn.
5) Целевой функции Z=c1x1+c2x2+…+cnxn соответствует параллельно перемещающаяся
гиперплоскость c1x1+c2x2+…+cnxn=const (поверхность уровня целевой функции).
6) Максимум (минимум) целевой функции всегда достигается в какой-то вершине
гипермногогранника ограничений (но он может стать бесконечным, если область ограничений
бесконечна).
4.6.2.5. Алгебраическая характеристика вершины многогранника ограничений
Чтобы получить такую характеристику, обратимся снова к двумерной картинке. В этом
случае вершина соответствующего многоугольника есть точка пересечения каких-то его двух
сторон (lr) и (ls), которые изображают границу r-го и s–го ограничений, т.е. имеют своими
уравнениями прямые
(lr): ar1x1+ar2x2=br;
(ls): as1x1+as2x2=bs.
В трехмерном случае (т.к. точка трехмерного пространства определяется пересечением
трех плоскостей) вершину многогранника ограничений можно охарактеризовать уравнениями тех
трех граней (Пr), (Пs) и (Пt), пересечением которых она является:
(Пr): ar1x1+ar2x2+ar3x3=br;
(Пs): as1x1+as2x2+as3x3=bs;
(Пt): at1x1+at2x2+at3x3=bt.
Заметим, что некоторые вершины могут попасть на одну из координатных плоскостей или
на одну из координатных осей, как, например, в задаче 5 раздела 4.6.2.3. Для такой вершины будет
выполняться одно или два из уравнений x1=0, x2=0, x3=0 (и если, в частности, начало координат
является вершиной, то выполняются все три уравнения).
Наконец, в случае n-мерной задачи надо считать, что вершина характеризуется как
пересечение соответствующих n гиперплоскостей (в том числе, возможно, и координатных
гиперплоскостей).
Для дальнейшего будет удобно каждое ограничение
ai1x1+ai2x2+…+ainxn ≤ bi (i=1,2,…,m)
записывать в виде
bi- ai1x1-ai2x2-…-ainxn ≥ 0
или, что то же самое, в виде
ai1(-x1)+ai2(-x2)+…+ain(-xn)+bi ≥ 0 (i=1, 2,…, m).
Будем рассматривать левую часть ограничения как новую переменную yi, т.е. положим
yi= ai1(-x1)+ai2(-x2)+…+ain(-xn)+bi (i=1, 2,…, m),
так что совокупность ограничений теперь запишется в виде
y1 ≥ 0, y 2 ≥ 0,..., y m ≥ 0,
а вместе с требованием неотрицательности получим единообразную запись для всех ограничений:
x1 ≥ 0, x2 ≥ 0,..., x n ≥ 0, y1 ≥ 0, y 2 ≥ 0,..., y m ≥ 0.
Заметим, что дополнительные переменные имеют простой экономический смысл. Так как
yi=bi-(ai1x1+ai2x2+…+ainxn),
то yi представляет собой остаток i-го производственного ресурса (из его запаса bi) после того, как
при реализации плана x1, x2,…, xn он затрачен в количестве
ai1x1+ai2x2+…+ainxn.
Страницы
- « первая
- ‹ предыдущая
- …
- 80
- 81
- 82
- 83
- 84
- …
- следующая ›
- последняя »
