Условия единственности оптимального решения задачи интервального программирования.

Алгоритм проверки условия единственности. Графическая иллюстрация.

Предположим, что нулевой вектор не принадлежит интервалу:

Множество возможных реализаций коэффициентов целевой функции задает в -мерном евклидовом пространстве гиперпараллелепипед .

Пример.

С учетом условия (3) на можно потянуть выпуклую коническую оболочку с вершиной в т. 0

Обозначим - наименьший выпуклый конус, содержащий - конус возможных вариаций градиента целевой функции.

Возьмем вектор и рассмотрим задачу

(*)

- одна из возможных постановок задачи интервального программирования.

Согласно теореме Куна –Таккера, если , - решение задачи и - множество индексов активных в точке основных ограничений, - множество индексов активных в точке прямых ограничений, то

- нормали; коэффициенты.

Т.е. градиент целевой функции можно представить в виде линейной комбинации с неотрицательными коэффициентами нормалей к активным ограничениям в точке . Значит, градиент , где - конус, натянутый на нормали к активным в точке ограничениям.

Утверждение 2. Пусть (- вектор коэффициентов целевой функции) и пусть - решение задачи . Тогда если S - множество всех решений задачи (1)-(2), то .

Доказательство. Для доказательства надо показать, что.

Заметим, во-первых, что

Покажем теперь, что , где . Так как то по определению выпуклой конической оболочки верно, что существует : , - крайние векторы для конуса , , где .

Так как выпукло и , то , то , . Получили , . По условию утверждения . Отсюда следует . Утверждение доказано.

Для определения единственности решения задачи (1) рассмотрим конусы и - конус, крайними векторами которого являются векторы нормалей ограничений в точке .(см.РИС)

Из условий (2) и свойств задач линейного программирования следует, что и сформировались в . Оба конуса не зависят от , и поэтому их вершины можно приложить в общую точку.

Пример. Определение активных ограничений через коэффициенты. Вставить.

Утверждение 3. Если , то любой вектор является линейной комбинацией с положительными коэффициентами нормалей к активным ограничениям в точке : , - нормали к активным ограничениям в точке .

Доказательство. Следует из определения конусной оболочки, натянутой на векторы нормали.

Теорема. Решение задачи (1)-(2) является единственным, если конус возможных вариаций градиента целевой функции содержится в конусе, натянутом на нормали к активным ограничениям в точке . Т.е. если выполняется следующее включение:

- единственно , .