ВУЗ:
Составители:
124
IV Если
0<
s
c , то
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
−
s
s
s
s
c
p
B
c
p
1
.
V.
Предполагается, что
T
2
1
)...,,,(
ms
s
s
s
aaap =
. Если все
0≤
is
a
то
решение является неограниченным.
VI В противном случае определяется
θ=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
is
i
rs
r
a
b
a
b
min
.
VII После этого с помощью р-операции относительно элемента
rs
a
опре-
деляется
s
s
c
pB
#
"#
#
1−
.
Первые (m+1) столбцов содержат обратную матрицу нового базиса.
Новое базисное решение имеет вид
()
θ=≠θ−=
rB
is
iB
i
B
xriaxx )
~
(;где,)(
~
.
Основное отличие модифицированного симплекс-метода от обычного
заключается в том, что на каждой итерации необходимо преобразовывать
лишь элементы обратной матрицы (шаг VII).
Дальнейшие разработки метода ЛП: метод искусственных переменных,
двойственный симплекс-метод, целочисленное программирование и т.д.
7.7.5. Критерии оптимальности в задачах с ограничениями
Имеем задачу с ограничениями в виде равенств:
Минимизировать f(x
1
, x
2
, …, x
N
)
при ограничениях h
k
(x
1
, x
2
, …, x
N
)=0 k=1,…,K.
Задача может быть решена методом безусловной оптимизации путем
исключения из целевой функции К независимых переменных с помощью за-
данных равенств. Это уменьшает размерность исходной задачи с N до N-K.
ПРИМЕР 7.18. Минимизировать f(x)=x
1
x
2
x
3
при ограничениях: h
1
=x
1
+x
2
+ x
3
=1.
Исключаем переменную x
3
: x
3
=1-x
1
-x
2
, тогда
min f(x
1
, x
2
)= x
1
x
2
(1-x
1
-x
2
).
Этот метод применим лишь в тех случаях, когда уравнения ограничений
можно разрешить относительно некоторого набора переменных. При нали-
чии большого числа ограничений в виде равенств процесс исключения пере-
менных становится весьма сложным. Кроме того, возможен случай, когда
Страницы
- « первая
- ‹ предыдущая
- …
- 122
- 123
- 124
- 125
- 126
- …
- следующая ›
- последняя »
