ВУЗ:
Составители:
Рубрика:
80
Анализ устойчивости решения к варьированию коэффициентов
целевой функции задачи (1)
. Пусть uU
∈
. Для любого
j
,
принадлежащего множеству неактивных ограничений множества
U , при
достаточно малых изменениях величины
j
c решение u будет оставаться
оптимальным для задачи (2). Точнее оно будет оставаться оптимальным
при замене величины
j
c на величину
jj
c
−
Δ , если ().
jj
gu
Δ
≤ Тогда
любое решение
x
X∈ также будет остаться оптимальным решением
задачи (1).
Если же
j
принадлежит множеству активных ограничений задачи (2),
то при сколь угодно малом уменьшении величины
j
c вектор u престает
быть оптимальным и даже допустимым решением задачи (2).
Но отсюда не следует, что вектор
x
X
∈
перестает быть оптимальным
решением задачи (1). Если
uriU∈
/
, то для его номеров активных
ограничений
j
любое решение
x
X
∈
при некотором уменьшении
величины
j
c будет оставаться оптимальным для задачи (1).
Когда
uriU∈
и, поэтому, известен набор неактивных ограничений
множества оптимальных решений задачи (2) (а он для всех таких решений
будет одним и тем же), можно точно определить какие коэффициенты
j
c
можно варьировать без изменения множества оптимальных решений
задачи (1), а какие нельзя. Эту же информацию получим, имея решение
x
riX∈
, что следует из достижимости для оптимальных решений задач (1),
(2) условия дополняющей нежесткости в строгой форме.
С определенной условностью можно говорить, что решение
uriU∈
устойчивее, чем оптимальное решение задачи (2), не принадлежащее
riU ,
поскольку это решение
u будет иметь меньший по сравнению с любым
решением из
U
набор активных ограничений. В частности, для решения
uriU∈
будет наибольшим набор коэффициентов
j
c , допускающих
варьирование без изменения оптимальности данного решения.
Описание множеств оптимальных решений взаимно
двойственных задач линейного программирования
. Относительно
внутренние точки могут эффективно использоваться для описания
множеств оптимальных решений. Введем специальные обозначения для
множеств номеров активных и неактивных ограничений неравенств на
знак переменных. Для
n
x
R
+
∈ положим
}0:{)(
0
==
j
xjxJ , }0:{)( >=
j
xjxJ .
Если известно, что
Xri
x
∈ ,то получаем следующее представление
множеств оптимальных решений:
Анализ устойчивости решения к варьированию коэффициентов целевой функции задачи (1). Пусть u ∈U . Для любого j , принадлежащего множеству неактивных ограничений множества U , при достаточно малых изменениях величины c j решение u будет оставаться оптимальным для задачи (2). Точнее оно будет оставаться оптимальным при замене величины c j на величину c j − Δ j , если Δ j ≤ g j (u ). Тогда любое решение x ∈ X также будет остаться оптимальным решением задачи (1). Если же j принадлежит множеству активных ограничений задачи (2), то при сколь угодно малом уменьшении величины c j вектор u престает быть оптимальным и даже допустимым решением задачи (2). Но отсюда не следует, что вектор x ∈ X перестает быть оптимальным решением задачи (1). Если u ∈ / riU , то для его номеров активных ограничений j любое решение x ∈ X при некотором уменьшении величины c j будет оставаться оптимальным для задачи (1). Когда u ∈ riU и, поэтому, известен набор неактивных ограничений множества оптимальных решений задачи (2) (а он для всех таких решений будет одним и тем же), можно точно определить какие коэффициенты c j можно варьировать без изменения множества оптимальных решений задачи (1), а какие нельзя. Эту же информацию получим, имея решение x ∈ riX , что следует из достижимости для оптимальных решений задач (1), (2) условия дополняющей нежесткости в строгой форме. С определенной условностью можно говорить, что решение u ∈ riU устойчивее, чем оптимальное решение задачи (2), не принадлежащее riU , поскольку это решение u будет иметь меньший по сравнению с любым решением из U набор активных ограничений. В частности, для решения u ∈ riU будет наибольшим набор коэффициентов c j , допускающих варьирование без изменения оптимальности данного решения. Описание множеств оптимальных решений взаимно двойственных задач линейного программирования. Относительно внутренние точки могут эффективно использоваться для описания множеств оптимальных решений. Введем специальные обозначения для множеств номеров активных и неактивных ограничений неравенств на знак переменных. Для x ∈ R+n положим J 0 ( x) = { j : x j = 0} , J ( x) = { j : x j > 0} . Если известно, что x ∈ ri X ,то получаем следующее представление множеств оптимальных решений: 80
Страницы
- « первая
- ‹ предыдущая
- …
- 78
- 79
- 80
- 81
- 82
- …
- следующая ›
- последняя »