Системы линейных неравенств. Зоркальцев В.И - 81 стр.

UptoLike

81
0
{: ,0,0,()}
n
j
XxRAxbx x jJx=∈ = =
,
{ : () 0, () 0, ()}
n
j
UuRgu gu jJx=∈ = .
На основе таких описаний множеств оптимальных решений легко можно
определить единственность или неединственность оптимальных решений
задач (1), (2). Выяснение вопроса о единственности оптимального решения
задачи (1) сводится к установлению линейной зависимости или
независимости столбцов матрицы
A
с номерами из
()Jx
. Если эти
столбцы линейно независимы, то полученное решение является
единственным оптимальным решением задачи. Если же они линейно
зависимы, то существуют другие оптимальные решения.
Лексикографические задачи линейной оптимизации. Если
известно, что используются алгоритмы решения задач линейного
программирования, всегда вырабатывающие относительно внутренние
точки множества оптимальных решений, то сильно упрощается решение
многокритериальных задач последовательной линейной оптимизации. Под
задачей последовательной линейной оптимизации на некоторой области
{
}
:,0
n
XxRAxbx=∈ = с целевыми функциями
12
,,,,1,,
TT T
k
cx cx cxk K=KK
будем понимать такую последовательность
задач линейного программирования: найти величины ,1,,
k
Fk K= K и
вектор
x
X из условий
{
}
{}
{}
1
1
21
21
1
1
min : ,
min : , ,
min : , , 1, , .
T
TT
KT Tk
kk
FcxxX
FcxxXcxF
FcxxXcxFkK
=∈
=∈=
=∈==
KKKKKKKK
K
Такие задачи последовательной оптимизации возникают при наличии
нескольких критериев, между которыми задан жесткий приоритет
улучшение по менее важному критерию может быть достигнуто только в
том случае, если более важные при этом не ухудшаются.
Например, множество
X можно интерпретировать как область
допустимых по технологическим ограничениям вариантов удовлетворения
потребности категорий потребителей с индексами 1, ,kK
=
K . Потребители
проранжированы в порядке их важности. Удовлетворение потребности
1k ой−− категории имеет большее значение, чем k ой
. Функции
T
k
с
характеризуют степень удовлетворения потребности k ой категории
потребителей.
Так, при рассмотрении первого, самого важного критерия на
допустимом множестве X имеем следующую задачу:
               X = {x ∈ R n : Ax = b, x ≥ 0, x j = 0, j ∈ J 0 ( x)} ,
              U = {u ∈ R n : g (u ) ≥ 0,         g j (u ) = 0, j ∈ J ( x)} .
На основе таких описаний множеств оптимальных решений легко можно
определить единственность или неединственность оптимальных решений
задач (1), (2). Выяснение вопроса о единственности оптимального решения
задачи (1) сводится к установлению линейной зависимости или
независимости столбцов матрицы A с номерами из J ( x) . Если эти
столбцы линейно независимы, то полученное решение является
единственным оптимальным решением задачи. Если же они линейно
зависимы, то существуют другие оптимальные решения.
    Лексикографические задачи линейной оптимизации. Если
известно, что используются алгоритмы решения задач линейного
программирования, всегда вырабатывающие относительно внутренние
точки множества оптимальных решений, то сильно упрощается решение
многокритериальных задач последовательной линейной оптимизации. Под
задачей последовательной линейной оптимизации на некоторой области
    {
X = x ∈ R n : Ax = b, x ≥ 0 }               с              целевыми            функциями
c1T x, c2T x,K, ckT x, k = 1, K, K будем понимать такую последовательность
задач линейного программирования: найти величины F k , k = 1,K, K и
вектор x ∈ X из условий
                              {
                  F 1 = min c1T x : x ∈ X ,          }
                    F2   = min {c   T
                                    2 x:                       }
                                           x ∈ X , c1T x = F 1 ,
                    KKKKKKKK

                                {
                    F K = min ckT x : x ∈ X , ckT−1x = F k −1, k = 1, K, K .   }
      Такие задачи последовательной оптимизации возникают при наличии
нескольких критериев, между которыми задан жесткий приоритет –
улучшение по менее важному критерию может быть достигнуто только в
том случае, если более важные при этом не ухудшаются.
      Например, множество X можно интерпретировать как область
допустимых по технологическим ограничениям вариантов удовлетворения
потребности категорий потребителей с индексами k = 1,K, K . Потребители
проранжированы в порядке их важности. Удовлетворение потребности
k − 1 − ой категории имеет большее значение, чем k − ой . Функции сkT
характеризуют степень удовлетворения потребности k − ой категории
потребителей.
      Так, при рассмотрении первого, самого важного критерия на
допустимом множестве X имеем следующую задачу:

                                                81