- •Планирование и управление в условиях неопределенности и риска. Модели и методы интервального программирования
- •Элементы интервальной математики
- •Задачи интервального программирования с линейными ограничениями.
- •Модели ограничений.
- •Модели критерия.
- •Основы выпуклого анализа
- •Алгоритм проверки условия единственности оптимального решения задачи интервального программирования с интервальной целевой функцией.
- •Графическая иллюстрация.
- •Решение задач интервального программирования средствами Excel, Mathematica, MathCad
Основы выпуклого анализа
Определение. [С.Н.Черников. Линейные неравенства. Стр.153]
Выпуклым конусом, порожденным конечной системой элементов
пространства называется множество элементов , определяемых формулой
.
При этом элементы называются образующими элементами конуса.
Опр. Пусть Х – произвольное множество из . Конической оболочкой множества называется множество всех неотрицательных линейных комбинаций
точек .
Коническая оболочка является наименьшим выпуклым конусом, содержащим множество Х.
Опр. Выпуклый конус К называется многогранным, если он представляет собой коническую оболочку конечного числа своих точек.
Т.о. конус выпуклый, если конечное число крайних векторов таких что для и только для них справедливо, что .
Еще одно определение многогранного конуса.
Опр. Выпуклый конус называется многогранным, если для заданного конечного множества векторов , любая точка является их неотрицательной линейной комбинацией
Столбцы матрицы будут крайними векторами.
Пример: Определить, принадлежит ли вектор конусу с крайними векторами
Составим матрицу и решим систему
: . Решение относительно : . Так как , то . Да, принадлежит.
Еще одно определение конуса.
Множество называется конусом с вершиной в т. , если из того, что , следует, что множеству К принадлежит и весь луч, выходящий из точки и проходящей через т. .
Т.е. , . (1)
Точка может принадлежать или не принадлежать множеству (1)
Утв. К – выпуклый конус с вершиной в точке тогда и только тогда, когда из условия , будет следовать, что
, (2)
а также
, , . (3)
Док-во. Необх. К – выпуклый конус. Из его определения следует, что если , то . Возьмем и положим , . Получим , . Т.к. конус выпуклый, то отрезок .
Дост. Пусть выполнено (2) и (3). Из (3) и (1) следует, что К-конус. Докажем, что он выпуклый. Т.е. если , то
, . (4)
При и это очевидно. Докажем для . Рассмотрим точки , . Тогда , что совпадает с (4). Утверждение доказано.
Опр. Вектор называется крайним для выпуклого конуса , если из того, что следует .
Условия единственности оптимального решения задачи интервального программирования.
Алгоритм проверки условия единственности. Графическая иллюстрация.
Предположим, что нулевой вектор не принадлежит интервалу:
Множество возможных реализаций коэффициентов целевой функции задает в -мерном евклидовом пространстве гиперпараллелепипед .
Пример.
С учетом условия (3) на можно потянуть выпуклую коническую оболочку с вершиной в т. 0
Обозначим - наименьший выпуклый конус, содержащий - конус возможных вариаций градиента целевой функции.
Возьмем вектор и рассмотрим задачу
(*)
- одна из возможных постановок задачи интервального программирования.
Согласно теореме Куна –Таккера, если , - решение задачи и - множество индексов активных в точке основных ограничений, - множество индексов активных в точке прямых ограничений, то
- нормали; коэффициенты.
Т.е. градиент целевой функции можно представить в виде линейной комбинации с неотрицательными коэффициентами нормалей к активным ограничениям в точке . Значит, градиент , где - конус, натянутый на нормали к активным в точке ограничениям.
Утверждение 2. Пусть ( - вектор коэффициентов целевой функции) и пусть - решение задачи . Тогда если S - множество всех решений задачи (1)-(2), то .
Доказательство. Для доказательства надо показать, что .
Заметим, во-первых, что
Покажем теперь, что , где . Так как то по определению выпуклой конической оболочки верно, что существует : , - крайние векторы для конуса , , где .
Так как выпукло и , то , то , . Получили , . По условию утверждения . Отсюда следует . Утверждение доказано.
Д ля определения единственности решения задачи (1) рассмотрим конусы и - конус, крайними векторами которого являются векторы нормалей ограничений в точке .(см.РИС)
Из условий (2) и свойств задач линейного программирования следует, что и сформировались в . Оба конуса не зависят от , и поэтому их вершины можно приложить в общую точку.
Пример. Определение активных ограничений через коэффициенты. Вставить.
Утверждение 3. Если , то любой вектор является линейной комбинацией с положительными коэффициентами нормалей к активным ограничениям в точке : , - нормали к активным ограничениям в точке .
Доказательство. Следует из определения конусной оболочки, натянутой на векторы нормали.
Теорема. Решение задачи (1)-(2) является единственным, если конус возможных вариаций градиента целевой функции содержится в конусе, натянутом на нормали к активным ограничениям в точке . Т.е. если выполняется следующее включение:
- единственно , .