🗊Презентация Исследование операций в логистике

Матвейчук Наталья Михайловна, к.ф.-м.н., доцент кафедры ЭИ, Матвейчук Наталья Михайловна, к.ф.-м.н., доцент кафедры ЭИ, ауд. 804-5(кафедра), 801а-5 (44)700-91-83, (29)740-11-63 matsveichuk@tut.by

ТЕМЫ: Задачи нелинейного и целочисленного линейного программирования Модели управления запасами Динамическое программирование Оптимизационные задачи на графах Марковские процессы Системы массового обслуживания Теория игр Многокритериальная оптимизация

Теория игр Теория игр Джон Нэш – 1994 (экономика) Элвин Рот и Ллойд Шепли – 2012 (экономика) Теория графов Эдсгер Дейкстра – медаль Филдса – 1972 Ричард М. Карп – медаль Филдса – 1985 СМО Агнер К. Эрланг (1878-1929) его именем названа единица интенсивности нагрузки в телекоммуникационных системах (эрланг) Динамическое программирование Ричард Беллман - Премии Норберта Винера по прикладной математике (1970), Диксона (1970), фон Неймана (1976), Медаль почёта IEEE (1979)

Классификация задач нелинейного программирования

Экстремальная задача без ограничений: случай одной переменной Постановка задачи: y = f(x)  max (min) Необходимое условие экстремума в точке x0: f’(x0) = 0 (x0 – стационарная точка) Достаточные условия экстремума в точке x0 (функция f(x) должна быть непрерывна вместе со своими производными первого и второго порядка в этой точке): - если f”(x0) > 0, то x0 – точка локального минимума, - если f”(x0) < 0, то x0 – точка локального максимума, - если f”(x0) = 0, то в точке x0 экстремума нет.

Экстремальная задача без ограничений: случай двух переменных Постановка задачи: z = f(x, y)  max (min) Необходимое условие экстремума в точке (x0, y0): ((x0 , y0) – стационарная точка)

Экстремальная задача без ограничений: случай двух переменных Достаточные условия экстремума в точке (x0, y0): обозначим частные производные второго порядка

Экстремальная задача без ограничений: общий случай Постановка задачи: Необходимое условие экстремума в точке

Экстремальная задача без ограничений: общий случай Достаточные условия экстремума в точке Х0: Если матрица вторых частных производных функции f(Х) (матрица Гессе Н) в стационарной точке Х0 положительно определена, то Х0 – точка локального минимума функции f(Х) Если матрица вторых частных производных функции f(Х) (матрица Гессе Н) в стационарной точке Х0 отрицательно определена, то Х0 – точка локального максимума функции f(Х)

Матрица Гессе:

Матрица Гессе является матрицей квадратичной формы относительно приращений x1, x2,…, xn. Матрица Гессе является матрицей квадратичной формы относительно приращений x1, x2,…, xn. Матрица положительно (отрицательно) определена (полу), если все ее собственные значения положительны (отрицательны) (могут быть равны нулю). Если отрицательно (положительно) полуопределена, то точка нестрогого экстремума (и необходимые условия). Если отрицательно (положительно) определена – точка строгого экстремума (и достаточные условия).

Критерий Сильвестра (устанавливает определенность квадратичной формы): квадратичная форма положительно определена тогда и только тогда, когда все главные миноры ее матрицы положительны, и отрицательно определена, тогда и только когда главные миноры переменных знаков, начиная с «-».

Порядок решения: найти частные производные первого порядка и приравнять к нулю; решить полученную систему, найти стационарные точки; в каждой стационарной точке определить матрицу Гессе; для каждой матрицы Гессе (для каждой стационарной точки) проверить критерий Сильвестра (установить определенность матрицы Гессе); применить достаточное условие экстремума в стационарной точке.

Пример. Квадратичная функция

Пример. Квадратичная функция

Пример: Найти экстремумы функции L(x1,x2)=x1+2x2 при ограничениях x12 + x22 ≤ 25, x1 ≥ 0, x2 ≥ 0. Максимум достигается в точке А касания окружности x12 + x22 = 25 и линии уровня x1 + 2x2 = C А(√5,2√5)

Функция f(x) является выпуклой, если для любых х1, х2 и положительных α, β, в сумме равных 1, имеет место Функция f(x) является выпуклой, если для любых х1, х2 и положительных α, β, в сумме равных 1, имеет место

ПРИЗНАК СТРОГОЙ ВЫПУКЛОСТИ Дважды дифференцируемая функция f(X) = f(x1, …, хn ) является выпуклой в том и только том случае, когда

Свойства выпуклых функций: 1) Если f(X) – выпукла, то функция - f(X) – вогнута. 2) Линии уровня выпуклой или вогнутой функции выпуклы. 3) Если функции fi(X) –выпуклы, i = 1, …, m, то при любых действительных числах i ≥ 0 функция i fi(X) также является выпуклой. 4) Если f(X) –выпукла, то для любого числа  область решений неравенства f(X) <  является либо выпуклым множеством, либо пустым. 5) Если gi(X) –выпуклые при всех неотрицательных значениях переменных, то область решений системы неравенств gi(X) ≤ bi , i = 1, ..., m, является либо выпуклым множеством либо пустым. 6) Выпуклая (вогнутая) функция, определённая на выпуклом множестве, непрерывна в каждой внутренней точке этого множества.

Теорема Вейерштрасса: Теорема Вейерштрасса: если функция f непрерывна на компакте (ограниченном и замкнутом множестве), то она достигает минимума и максимума на внутренней (стационарной) или граничной точке множества.

Решение любой задачи математического программирования (в том числе нелинейного) можно свести к решению задачи нелинейного программирования без ограничений. Решение любой задачи математического программирования (в том числе нелинейного) можно свести к решению задачи нелинейного программирования без ограничений. Для этого необходимо на основе исходной ЗМП построить функцию Лагранжа. Два случая: задача содержит только ограничения-равенства; задача содержит ограничения-неравенства.

Применим необходимое условие экстремума функции

Экономическая интерпретация множителей Лагранжа, соответствующих оптимальному решению, аналогична интерпретации двойственных оценок ограничений ЗЛП Экономическая интерпретация множителей Лагранжа, соответствующих оптимальному решению, аналогична интерпретации двойственных оценок ограничений ЗЛП Они показывают величину изменения целевой функции в расчёте на единицу изменения свободного члена ограничения, которому соответствует множитель Лагранжа, в очень малой окрестности оптимума Если ограничение можно рассматривать в качестве баланса ресурса и максимизируется прибыль, то множитель Лагранжа в точке оптимума равен оптимальной цене Если найдётся рынок, где ресурс дешевле, то его покупка увеличит прибыль Если найдётся рынок, где ресурс дороже, то для увеличения прибыли его следует продать В отличие от случая ЗЛП, множители Лагранжа (кроме частных случаев) не обладают свойством устойчивости Они меняют свои значения даже при сколь угодно малом изменении свободных членов ограничений

Применим необходимое условие экстремума функции

Условия Куна-Таккера: