ТЕМА 2. Статическая оптимизация 2.1. Общая постановка задачи математического программирования 2.2. Задача линейного программирования и методы ее решения. - презентация

1 ТЕМА 2. Статическая оптимизация 2.1. Общая постановка задачи математического программирования 2.2. Задача линейного программирования и методы ее решения 2.3. Задача нелинейного программирования и методы ее решения 2.1. Общая постановка задачи математического программирования 2.2. Задача линейного программирования и методы ее решения 2.3. Задача нелинейного программирования и методы ее решения

2 2.1. Общая постановка задачи математического программирования

3 Математическое программирование Математическое программирование – раздел математики, занимающийся изучением свойств оптимизационных задач и алгоритмов их решения.

4 Задача математического программирования Основные элементы задачи: - Управляемые переменные - Допустимое множество - Ограничения - Целевая функция Основные элементы задачи: - Управляемые переменные - Допустимое множество - Ограничения - Целевая функция

5 Управляемые переменные Управляемые (инструментальные) переменные – искомые переменные задачи. Если вектор инструментальных переменных удовлетворяет условиям задачи, то он называется допустимым. Управляемые (инструментальные) переменные – искомые переменные задачи. Если вектор инструментальных переменных удовлетворяет условиям задачи, то он называется допустимым.

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

7 Целевая функция Целевая функция – краткое математическое изложение цели задачи. Целевая функция состоит из трех элементов: управляемых переменных; параметров, которые не поддаются управлению; формы зависимости между ними. Целевая функция – краткое математическое изложение цели задачи. Целевая функция состоит из трех элементов: управляемых переменных; параметров, которые не поддаются управлению; формы зависимости между ними.

8 Задача математического программирования Общая задача математического программирования состоит в выборе вектора инструментальных переменных x из допустимого множества X, максимизирующего либо минимизирующего значение целевой функции: или. Общая задача математического программирования состоит в выборе вектора инструментальных переменных x из допустимого множества X, максимизирующего либо минимизирующего значение целевой функции: или.

9 Классификация задач 1. По характеру взаимосвязи между переменными а)линейные, б)нелинейные. 2. По характеру изменения переменных а)непрерывные, б)дискретные. 3. По учету фактора времени а)статические, б)динамические. 1. По характеру взаимосвязи между переменными а)линейные, б)нелинейные. 2. По характеру изменения переменных а)непрерывные, б)дискретные. 3. По учету фактора времени а)статические, б)динамические.

10 Классификация задач 4. По наличию информации о переменных а)задачи в условиях полной определенности (детерминированные), б)задачи в условиях неполной информации, в)задачи в условиях неопределенности. 5. По числу критериев оценки альтернатив а)однокритериальные задачи, б)многокритериальные задачи. 4. По наличию информации о переменных а)задачи в условиях полной определенности (детерминированные), б)задачи в условиях неполной информации, в)задачи в условиях неопределенности. 5. По числу критериев оценки альтернатив а)однокритериальные задачи, б)многокритериальные задачи.

11 2.2. Задача линейного программирования и методы ее решения Общая формулировка Графическое решение Симплекс-метод Метод искусственного базиса Теория двойственности

12 Общая формулировка задачи линейного программирования

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

14 Запись задачи линейного программирования Целевая функция: Ограничения: и Целевая функция: Ограничения: и

15 Запись задачи линейного программирования (краткая форма) Данная задача называется канонической. Если хотя бы одно ограничение представлено неравенством, то задача является неканонической. Данная задача называется канонической. Если хотя бы одно ограничение представлено неравенством, то задача является неканонической.

16 Алгоритм математической записи задачи ЛП Для составления математической записи задачи необходимо: обозначить управляемые переменные; составить целевую функцию исходя из цели задачи; записать систему ограничений, учитывая имеющиеся в условии задачи количественные закономерности. Для составления математической записи задачи необходимо: обозначить управляемые переменные; составить целевую функцию исходя из цели задачи; записать систему ограничений, учитывая имеющиеся в условии задачи количественные закономерности.

17 Пример задачи ЛП: условие Спрос на сливочное мороженое превышает спрос на шоколадное не более чем на 100 кг. в сутки. Спрос на шоколадное мороженое не превышает 350 кг в сутки. Цена 1 кг сливочного мороженого 16 ден.ед., шоколадного 14 ден ед. Исходный продукт Расход исходного продукта на 1 кг. мороженого Запас Сливочное Шоколадное Молоко 0,80,5400 Наполнители 0,40,8365

18 Пример задачи ЛП: математическая запись Управляемые переменные: x 1 и x 2 - суточный объем выпуска каждого вида мороженого Целевая функция: Ограничения задачи:. Управляемые переменные: x 1 и x 2 - суточный объем выпуска каждого вида мороженого Целевая функция: Ограничения задачи:.

19 Графическое решение задачи линейного программирования

20 Геометрическая интерпретация системы ограничений Если ограничение задано равенством, то геометрически оно может быть представлено прямой на плоскости в системе координат, где по осям отложены управляемые переменные. Если ограничение задано неравенством, то геометрически оно может быть представлено полуплоскостью. Множество точек на плоскости, удовлетворяющих системе ограничений, составляет выпуклую многоугольную область. Если ограничение задано равенством, то геометрически оно может быть представлено прямой на плоскости в системе координат, где по осям отложены управляемые переменные. Если ограничение задано неравенством, то геометрически оно может быть представлено полуплоскостью. Множество точек на плоскости, удовлетворяющих системе ограничений, составляет выпуклую многоугольную область.

21 Варианты области допустимых решений (ОДР) 1. ОДР имеет вид ограниченного выпуклого многоугольника. x 1 0 x 2 1. ОДР имеет вид ограниченного выпуклого многоугольника. x 1 0 x 2

22 Варианты области допустимых решений (ОДР) 2. ОДР имеет вид неограниченного выпуклого многоугольника. x 1 0 x 2 2. ОДР имеет вид неограниченного выпуклого многоугольника. x 1 0 x 2

23 Варианты области допустимых решений (ОДР) 3. Неравенства противоречат друг другу, и допустимая область пуста, задача решений не имеет.

24 Графическая интерпретация целевой функции Графическим отображением целевой функции являются ее линии уровня. Для построения линий уровня целевой функции используют вектор-градиент, который показывает направление наискорейшего изменения целевой функции. Координатами этого вектора являются коэффициенты целевой функции (с 1 ; с 2 ). Графическим отображением целевой функции являются ее линии уровня. Для построения линий уровня целевой функции используют вектор-градиент, который показывает направление наискорейшего изменения целевой функции. Координатами этого вектора являются коэффициенты целевой функции (с 1 ; с 2 ).

25 Графическая интерпретация решения С геометрической точки зрения в задаче линейного программирования ищется такая угловая точка или набор точек из допустимого множества решений, на которой достигается самая верхняя (нижняя) линия уровня целевой функции.

26 Алгоритм графического решения 1. Построить область допустимых решений. 2. Построить вектор-градиент С = (c 1, c 2 ). 3. Провести одну из линий уровня, перпендикулярную С и имеющую общие точки с областью допустимых решений. 4. Линию уровня переместить в направлении вектора- градиента в задаче на максимум (в противоположном направлении в задаче на минимум) до тех пор, пока у нее окажется только одна общая точка с областью допустимых решений (ОДР). 5. Найти координаты точки экстремума (совместно решить уравнения прямых) и значение целевой функции в ней. 1. Построить область допустимых решений. 2. Построить вектор-градиент С = (c 1, c 2 ). 3. Провести одну из линий уровня, перпендикулярную С и имеющую общие точки с областью допустимых решений. 4. Линию уровня переместить в направлении вектора- градиента в задаче на максимум (в противоположном направлении в задаче на минимум) до тех пор, пока у нее окажется только одна общая точка с областью допустимых решений (ОДР). 5. Найти координаты точки экстремума (совместно решить уравнения прямых) и значение целевой функции в ней.

27 Варианты решения 1. Решение единственно. x 1 0 x 2 1. Решение единственно. x 1 0 x 2

28 Варианты решения 2. Задача имеет бесчисленное множество решений. x 1 0 x 2 2. Задача имеет бесчисленное множество решений. x 1 0 x 2

29 Варианты решения 3. Задача не имеет решения по причине неограниченности целевой функции x 1 0 x 2 4. Если ограничения задачи противоречивы, задача является неразрешимой. 3. Задача не имеет решения по причине неограниченности целевой функции x 1 0 x 2 4. Если ограничения задачи противоречивы, задача является неразрешимой.