Модели и методы интервального программирования

Август 12, 2022

Главная
Математика
Модели и методы интервального программирования

Содержание

2. Следует повторить определение выпуклого множества, конуса, выпуклого конуса, необходимое и достаточное условие выпуклости конуса, определение крайнего
3. Входной контроль Построить коридор возможных значений интервально заданной функции f(x)]=[-1,1]+[0.5,1]x
4. Входной контроль Построить коридор возможных значений интервально заданной функции f(x)]=[-1,1]+[0.5,1]x f(x)]=[-1,1]+[0.5,1]x; f--(x)=min{[-1,1]+[0.5,1]x}, f+(x)=max{[-1,1]+[0.5,1]x}.
5. План лекции Элементы интервальной математики Задача интервального линейного программирования (ЗИЛП) Постановки и детерминированные эквиваленты ЦФ и
6. Элементы интервальной математики Интервальное число [b] = [b⁻, b⁺] [A]=([aij]) – интервальная матрица Интервально заданная функция
7. Задачи интервального программирования с линейными ограничениями
8. ЗИЛП Интервально заданная функция [f(x)]=[c`x] → max(min) Ограничения с интервальными коэффициентами [A]x ≤ [b] Х >=0
9. Постановки ЗИЛП Модели ограничений 1. x₁ = { x ≥ 0 | при ∀ A ∈
10. Детерминированные эквиваленты ограничений 1. х₁ = { x ≥ 0: A⁺x ≤ b⁻ } 2. х₂
11. Пример
12. Утверждение 1. При любом выборе f(x) согласно условию (*) вариация экстремального значения критерия ограничена пределами где
13. Постановки и детерминированные эквиваленты ЦФ 1. Минимаксная: минимальная реализация функции на max. min [c]`x → max,
14. Постановки и детерминированные эквиваленты ЦФ
15. Основы выпуклого анализа Выпуклым конусом, порожденным конечной системой элементов пространства называется множество элементов , определяемых формулой
16. Опр. Выпуклый конус называется многогранным, если для заданного конечного множества векторов любая точка является их неотрицательной
17. Единственность решения задачи линейного программирования с интервальной ЦФ [c]`x → max; Ax ≤ b; x ≥
18. 5. Единственность решения задачи линейного программирования с интервальной ЦФ Выберем какую-либо реализацию целевой функции и пусть
19. Аx = b ☜ активные ограничения Ax -------- градиенты(нормали) функции c⁻`x = f⁻(x) и c⁺`x =f⁺(x).
20. 6. Алгоритм определения единственности решения
21. 6. Алгоритм определения единственности решения
22. Пример №1 Решить задачу интервального программирования Где - интервальный вектор коэффициентов целевой функции, проверить единственность ее
23. Постановка задачи Решение задачи 1.Детерминированный эквивалент (максиминная модель ).
24. 2. Решение задачи: 3. Проверка единственности решения. 3.1 Сформируем матрицу из векторов
25. 3.2 Формируем ЗЛП с коэффициентами из первого столбца
26. Вектору соответствует оптимальный план: Активными в точке являются ограничения (1), (2), (3).
27. 3.3. Для решения формируем матрицу Строки которой – векторы нормали активных ограничений в точке
28. 3.4. Решаем матричное уравнение . 3.5. Т.к. Все , то - единственное решение задачи!
30. Скачать презентацию

Слайд 2

Следует повторить
определение выпуклого множества, конуса, выпуклого конуса,
необходимое и достаточное условие

выпуклости конуса, определение крайнего вектора для выпуклого конуса, конической оболочки, многогранного конуса.
основные ограничения, прямые ограничения
Нормаль
Активные, пассивные ограничения
Теорема Куна-Таккера
выпуклое множество

Слайд 3

Входной контроль
Построить коридор возможных значений интервально заданной функции
f(x)]=[-1,1]+[0.5,1]x

Слайд 4

Входной контроль
Построить коридор возможных значений интервально заданной функции
f(x)]=[-1,1]+[0.5,1]x
f(x)]=[-1,1]+[0.5,1]x;
f--(x)=min{[-1,1]+[0.5,1]x},
f+(x)=max{[-1,1]+[0.5,1]x}.

Слайд 5

План лекции
Элементы интервальной математики
Задача интервального линейного программирования (ЗИЛП)
Постановки и детерминированные эквиваленты

ЦФ и ограничений
Единственность решения задачи линейного программирования с интервальной ЦФ
Алгоритм определения единственности решения ЗЛП с интервальной ЦФ

Слайд 6

Элементы интервальной математики
Интервальное число [b] = [b⁻, b⁺]
[A]=([aij]) – интервальная

матрица
Интервально заданная функция
[f(x)] ={f⁻(х) ≤ f(x) ≤ f⁺(x)}

Пример:
f(x)]=[-1,1]+[0.5,1]x;
f--(x)=min{[-1,1]+[0.5,1]x},
f+(x)=max{[-1,1]+[0.5,1]x}.

Замечание.
При умножении интервала на -1 меняется знак границ интервала и сами границы меняются местами:

Интервально заданная матрица и интервально заданный вектор

Слайд 7

Задачи интервального программирования с линейными ограничениями

Слайд 8

ЗИЛП
Интервально заданная функция
[f(x)]=[c`x] → max(min)
Ограничения с интервальными коэффициентами [A]x ≤

[b]
Х >=0 – детерминированный → [c`x] = [c]`x

Слайд 9

Постановки ЗИЛП
Модели ограничений
1. x₁ = { x ≥ 0 | при

∀ A ∈ [A],
∀ b ∈ [b] верно Ax ≤ b } (жёсткое ограничение)
2. х₂ = { x ≥ 0; ∀ A ∈ [A], ∃ b ∈ [b]: Ax ≤ b }
3. х₃ = { x ≥ 0: ∃ A ∈ [A], ∀ b ∈ [b]: Ax ≤ b }
4. х₄ = { x ≥ 0: ∃ A ∈ [A], ∃ b ∈ [b]: Ax ≤ b } (мягкое ограничение)
5. х₅ = { x ≥ 0: } где

Слайд 10

Детерминированные эквиваленты ограничений
1. х₁ = { x ≥ 0: A⁺x ≤

b⁻ }
2. х₂ = { x ≥ 0: A⁺x ≤ b⁺ }
3. х₃ = { x ≥ 0: A⁻x ≤ b⁻ }
4. х₄ = { x ≥ 0: A⁻x ≤ b⁺ }
5. х₅ = { x ≥ 0: }
Соотношение между множествами x₁ - х₅:
x₁ ⊂ х₅ ⊂ х₄

Слайд 11

Пример

Слайд 12

Утверждение 1. При любом выборе f(x) согласно условию
(*)
вариация экстремального

значения критерия ограничена пределами

где

Доказательство. Для выполнено (*). Покажем, что
От противного. Пусть выполнено обратное:
Тогда
Возьмем , что противоречит (*). Значит, (1*) верно. Аналогично доказывается f(x0-)<= f(x0).

(1*)

Слайд 13

Постановки и детерминированные эквиваленты ЦФ
1. Минимаксная: минимальная реализация функции на max.
min

[c]`x → max, c ⁻ x → max
Максиминная: максимальная реализация функции на min.
max [c]`x → min, c⁺x → min
Принцип пессимистический. Применяется, когда необходимо обеспечить гарантированный результат. Эта постановка ориентирована на наихудший случай, особенно в случае допустимой области X1
2. Миниминная:
min [c]`x → min, c ⁻ x → min
Максимаксная:
max [c]`x → max, c⁺x → max
Принцип оптимистический. Если использовать область X4, то буде получено минимально (максимально) возможное значение критерия
3. В среднем
[ ]`x → max: ((c⁻+c⁺)/2)*x → max
Наиболее естественно использовать Х5.
4. Многокритериальная
f₁(x) → max
…………….
fm(x) → max
fi(x) ∈ [f⁻(x), f ⁺(x)]

Слайд 14

Постановки и детерминированные эквиваленты ЦФ

Слайд 15

Основы выпуклого анализа
Выпуклым конусом, порожденным конечной системой элементов
пространства называется множество

элементов , определяемых формулой
При этом элементы называются образующими элементами конуса.
Опр. Пусть Х – произвольное множество из . Конической оболочкой множества Х называется множество всех неотрицательных линейных комбинаций
точек .
Коническая оболочка является наименьшим выпуклым конусом, содержащим множество Х.

Слайд 16

Опр. Выпуклый конус называется многогранным, если для заданного конечного множества векторов

любая точка является их неотрицательной линейной комбинацией
Столбцы матрицы А будут крайними векторами.

Пример: Определить, принадлежит ли вектор х=(1,1,1) конусу с крайними векторами
Составим матрицу и решим систему
Решение . Так как , то да, принадлежит.

Слайд 17

Единственность решения задачи линейного программирования с интервальной ЦФ
[c]`x → max; Ax

≤ b; x ≥ 0;
Интервально заданная ЦФ определяет в пространстве Rn выпуклый конус Кс, образующими которого являются градиенты (нормали) функции
c⁻`x = f⁻(x) и c⁺`x =f⁺(x).
Любой реализации целевой функции соответствует градиент внутри этого конуса (Kc)

Слайд 18

5. Единственность решения задачи линейного программирования с интервальной ЦФ
Выберем какую-либо реализацию

целевой функции и пусть х* - решение полученного детерминируемого эквивалента
Обозначим Ka – конус, натянутый на нормали к активным в точке х* ограничениям
Если конус Kc лежит внутри конуса Ka, то решение интервальной задачи – единственно!
В противном случае решение не единственно, но можно выделить недоминируемые решения.

Слайд 19

Аx = b ☜ активные ограничения Ax < b ☜ пассивные ограничения
--------

градиенты(нормали) функции c⁻`x = f⁻(x) и c⁺`x =f⁺(x).

Слайд 20

6. Алгоритм определения единственности решения

Слайд 21

6. Алгоритм определения единственности решения

Слайд 22

Пример №1
Решить задачу интервального программирования
Где - интервальный вектор коэффициентов целевой

функции, проверить единственность ее решения.

Слайд 23

Постановка задачи
Решение задачи
1.Детерминированный эквивалент (максиминная модель ).

Слайд 24

2. Решение задачи:
3. Проверка единственности решения.
3.1 Сформируем матрицу
из

векторов

Слайд 25

3.2 Формируем ЗЛП с коэффициентами из первого столбца

Слайд 26

Вектору соответствует оптимальный план:

Активными в точке являются ограничения

(1), (2), (3).

Слайд 27

3.3. Для решения формируем матрицу
Строки которой – векторы нормали активных
ограничений

в точке

Слайд 28

3.4. Решаем матричное уравнение

.
3.5. Т.к. Все , то -

единственное
решение задачи!

Модели и методы интервального программирования

Содержание

Следует повторитьопределение выпуклого множества, конуса, выпуклого конуса, необходимое и достаточное условие

Входной контрольПостроить коридор возможных значений интервально заданной функцииf(x)]=[-1,1]+[0.5,1]x

Входной контрольПостроить коридор возможных значений интервально заданной функцииf(x)]=[-1,1]+[0.5,1]xf(x)]=[-1,1]+[0.5,1]x; f--(x)=min{[-1,1]+[0.5,1]x}, f+(x)=max{[-1,1]+[0.5,1]x}.

План лекцииЭлементы интервальной математикиЗадача интервального линейного программирования (ЗИЛП)Постановки и детерминированные эквиваленты

Элементы интервальной математикиИнтервальное число [b] = [b⁻, b⁺] [A]=([aij]) – интервальная

Задачи интервального программирования с линейными ограничениями

ЗИЛПИнтервально заданная функция [f(x)]=[c`x] → max(min)Ограничения с интервальными коэффициентами [A]x ≤

Постановки ЗИЛП Модели ограничений1. x₁ = { x ≥ 0 | при

Детерминированные эквиваленты ограничений1. х₁ = { x ≥ 0: A⁺x ≤

Пример

Утверждение 1. При любом выборе f(x) согласно условию (*) вариация экстремального

Постановки и детерминированные эквиваленты ЦФ1. Минимаксная: минимальная реализация функции на max. min

Постановки и детерминированные эквиваленты ЦФ

Основы выпуклого анализаВыпуклым конусом, порожденным конечной системой элементов пространства называется множество

Опр. Выпуклый конус называется многогранным, если для заданного конечного множества векторов

Единственность решения задачи линейного программирования с интервальной ЦФ [c]`x → max; Ax

5. Единственность решения задачи линейного программирования с интервальной ЦФ Выберем какую-либо реализацию

Аx = b ☜ активные ограничения Ax < b ☜ пассивные ограничения--------

6. Алгоритм определения единственности решения

6. Алгоритм определения единственности решения

Пример №1Решить задачу интервального программирования Где - интервальный вектор коэффициентов целевой

Постановка задачиРешение задачи1.Детерминированный эквивалент (максиминная модель ).

2. Решение задачи: 3. Проверка единственности решения.3.1 Сформируем матрицу из

3.2 Формируем ЗЛП с коэффициентами из первого столбца

Вектору соответствует оптимальный план: Активными в точке являются ограничения

3.3. Для решения формируем матрицуСтроки которой – векторы нормали активных ограничений

3.4. Решаем матричное уравнение .3.5. Т.к. Все , то -

Похожие презентации

Следует повторить
определение выпуклого множества, конуса, выпуклого конуса,
необходимое и достаточное условие

Входной контроль
Построить коридор возможных значений интервально заданной функции
f(x)]=[-1,1]+[0.5,1]x

Входной контроль
Построить коридор возможных значений интервально заданной функции
f(x)]=[-1,1]+[0.5,1]x
f(x)]=[-1,1]+[0.5,1]x;
f--(x)=min{[-1,1]+[0.5,1]x},
f+(x)=max{[-1,1]+[0.5,1]x}.

План лекции
Элементы интервальной математики
Задача интервального линейного программирования (ЗИЛП)
Постановки и детерминированные эквиваленты

Элементы интервальной математики
Интервальное число [b] = [b⁻, b⁺]
[A]=([aij]) – интервальная

ЗИЛП
Интервально заданная функция
[f(x)]=[c`x] → max(min)
Ограничения с интервальными коэффициентами [A]x ≤

Постановки ЗИЛП
Модели ограничений
1. x₁ = { x ≥ 0 | при

Детерминированные эквиваленты ограничений
1. х₁ = { x ≥ 0: A⁺x ≤

Утверждение 1. При любом выборе f(x) согласно условию
(*)
вариация экстремального

Постановки и детерминированные эквиваленты ЦФ
1. Минимаксная: минимальная реализация функции на max.
min

Основы выпуклого анализа
Выпуклым конусом, порожденным конечной системой элементов
пространства называется множество

Единственность решения задачи линейного программирования с интервальной ЦФ
[c]`x → max; Ax

5. Единственность решения задачи линейного программирования с интервальной ЦФ
Выберем какую-либо реализацию

Аx = b ☜ активные ограничения Ax < b ☜ пассивные ограничения
--------

Пример №1
Решить задачу интервального программирования
Где - интервальный вектор коэффициентов целевой

Постановка задачи
Решение задачи
1.Детерминированный эквивалент (максиминная модель ).

2. Решение задачи:
3. Проверка единственности решения.
3.1 Сформируем матрицу
из

Вектору соответствует оптимальный план:

Активными в точке являются ограничения

3.3. Для решения формируем матрицу
Строки которой – векторы нормали активных
ограничений

3.4. Решаем матричное уравнение

.
3.5. Т.к. Все , то -