Справочник от Автор24
Теория игр

Конспект лекции
«Численные методы оптимизации»

Справочник / Лекторий Справочник / Лекционные и методические материалы по теории игр / Численные методы оптимизации

Выбери формат для чтения

pdf

Конспект лекции по дисциплине «Численные методы оптимизации», pdf

Файл загружается

Файл загружается

Благодарим за ожидание, осталось немного.

Конспект лекции по дисциплине «Численные методы оптимизации». pdf

txt

Конспект лекции по дисциплине «Численные методы оптимизации», текстовый формат

Численные методы оптимизации М.Р.Давидсон МГУ им Ломоносова, ф-т ВМиК Кафедра Исследования Операций Лекция 1 Введение Постановка задачи оптимизации min f ( x) x∈ X целевая функция (функция цели) X - допустимое множество Вид допустимого множества: Пример 1 X = {x ∈ R n | g i ( x) ≤ 0, i = 1,..., m} Пример 2 X = {x ∈ R n | g ( x, y ) ≤ 0, y ∈ Y } f ( x) : R n → R • Математические исследования отдельных экономических проблем (20e гг. ХХ века) – Развитие экономики потребовало количественных показателей, и в 1920 годы был создан межотраслевой баланс (МОБ). Он-то и послужил толчком в деле создания и исследования математических моделей. Разработка МОБ в 1924—1925 годах в СССР повлияла на работы экономиста и статистика Василия Васильевича Леонтьева. Он разработал межотраслевую модель производства и распределения продукции: Модель продуктивна, если для всякого неотрицательного у разрешима система x = Ax + y, x ≥ 0, y ≥ 0 • Начало линейного программирования В 1938 году Леонид Витальевич Канторович в порядке научной консультации приступил к изучению практической задачи по составлению наилучшего плана загрузки лущильных станков (фанерный трест). Эта задача не поддавалась обычным методам. В 1939 году Л.В. Канторович написал работу «Математические методы организации и планирования производства», в которой сформулировал новый класс экстремальных задач с ограничениями и разработал эффективный метод их решения, таким образом были заложены основы линейного программирования. В ней был предложен расчетный метод, позволяющий находить решение технико-экономических вопросов такого рода, как наиболее рациональное распределение работ по механизмам, раскрои материала с минимальными отходами, распределение грузов по нескольким видам транспорта и т. п. Однако эта работа настолько опережала время и настолько не соответствовала догматам тогдашней политической экономии, что ее публикация оказалась возможной только в 1959 г. Изучение подобных задач привело к созданию новой научной дисциплины линейного программирования и открыло новый этап в развитии экономико-математических методов. • Применение в исследовании операций Источник: Ф.Морз, Дж.Кимбелл, Методы исследования операций, 1956 • Критерий соотношения потерь (число потопленных ПЛ/число потопленных торговых судов): • Задача оптимизации: максимизировать соотношение потерь Другие примеры задач оптимизации: Задача об оптимальном рационе Транспортная задача • Симплекс - метод Исторически общая задача линейного программирования была впервые поставлена в 1947 году Джорджем Бернардом Данцигом, Маршаллом Вудом и их сотрудниками в департаменте военно-воздушных сил США. В то время эта группа занималась исследованием возможности использования математических методов для военных задач и проблем планирования. В 1949 году Данциг разработал эффективный метод решения задач линейного программирования (ЛП)— симплекс-метод. Первое успешное решение задачи ЛП на ЭВМ SEAC было проведено в январе 1952 года • Что значит «эффективность»? – Понятие сложности задачи (битовая длина записи исходных данных задачи) – Понятие сложности алгоритма решения (количество машинных операций, как функция от размерности задачи) – Эффективный/неэффективный – полиномиальный/экспоненциальный – Пример 1: метод Гаусса решения системы линейных равенств (О(n^3)) – Пример 2: эффективный алгоритм определения простоты числа ??? • Эффективен ли симплекс-метод? – Сколько вершин у многогранника, заданного n линейными ограничениями? Пример: X = {x ∈ R n | 0 ≤ xi ≤ 1, i = 1,..., n} – Может ли симплекс-метод обойти все вершины? Klee, Victor Minty, George J. How good is the simplex algorithm? // Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, • Полиномиальный алгоритм для задачи ЛП – метод эллипсоидов (Хачиян Л.Г., 1979) – O(n^3(n + m)L) – метод внутренней точки (Кармаркар Н., 1984, O(m^{3/2}n^2L) – J. Renegar (1986) O(n^3L) – A.Немировский, Ю.Нестеров (1988), обобщение на выпуклый случай • Классификация задач оптимизации – Безусловная оптимизация • глобальный/локальный экстремум – Условная оптимизация • Линейное программирование (ЛП) • Выпуклое программирование • Общая задача нелинейного программирования (НЛП) • Полубесконечная оптимизация – Негладкая оптимизация – Дискретное программирование Лекция 2 Основные понятия • Вектор  x1     x2  n x ∈ R , x =  ,    x   n xT = ( x1 , x2 ,  , xn ) • Векторное пространство: линейное пространство, в котором, есть 0, определены сложение векторов, умножение векторов на число Свойства так определенного скалярного произведения • Неравенство Коши-Буняковского (следует непосредственно из свойств скалярного произведения) ( x, y ) ≤| x | | y |, где | u |= (u , u )1/ 2 • Неравенство треугольника | x + y |2 = ( x, x) + ( y, y ) + 2( x, y ) ≤ ( x, x) + ( y, y ) + 2 | x || y | =| x |2 + | y |2 +2 | x || y |= (| x | + | y |) 2 , откуда | x + y |≤| x | + | y | • Метрическое пространство – это пространство, в котором определена метрика: • Нормированное пространство – пространство, где для каждого вектора определена норма • Пользуясь свойствами скалярного произведения и неравенством треугольника, можем определить Евклидову метрику: d ( x, y ) =| x − y | • Евклидова длина вектора | u |= (u , u )1/ 2 является нормой • Матрицы • Умножение матрицы на вектор и на матрицу • Частный случай: произведение векторов x ∈ R n , y ∈ R n , x T y ≡ ( x, y ) • Неотрицательно/положительно определенные матрицы A ≥ 0 ⇔ ( Ax, x) = xT Ax ≥ 0 ∀x ∈ R n • Симметричная матрица имеет n вещественных собственных чисел и ортонормированный базис из собственных векторов Ah = λi h , i = 1,..., n i i i j (h , h ) = 0, i, j = 1,..., n, i ≠ j • Симметричная матрица неотрицательно определена тогда и только когда, ее собственные числа неотрицательны. λi ≥ 0, i = 1,..., n • Операторная норма матрицы • 88 x ∈ R n , || Ax ||≤|| A || || x || • По определению для всех • В Евклидовом пространстве для любого х /2 || Ax ||= ( Ax, Ax)1/ 2 = ( AT Ax, x)1/ 2 ≤ λ1max ( AT A) || x || /2 ( AT A) • Таким образом || A ||= λ1max • Если А симметрична, || A ||= max | λ ( A) | • Аналогично, || A−1 ||= max | 1 / λ ( A) |= 1 / min | λ ( A) |

Рекомендованные лекции

Смотреть все
Высшая математика

Теория оптимизации и численные методы

1 .1 : 1. 2. & . ., ."., . . . .' ( ..- ( .: .: ", 1998. ", 2000. * + 1 ' , I. * ( f (X) - X = ( x1, ...x n ) T - , , . !, " f (X) 1. f ( X ) = C cons...

Экономика труда

Оптимизация численности персонала

Тема 10: Оптимизация численности персонала Оглавление 1. Принципы и подходы к оптимизации численности персонала 1 2. Методы определения необходимой чи...

Информационные технологии

Применение ЭВМ в инженерном проектировании. Математическое моделирование

МОДЕЛИРОВАНИЕ ВВЕДЕНИЕ Слова «модель», «математическое моделирование» все более входят в жизнь современного общества. В первую очередь это связано с р...

Информационные технологии

Основные понятия и сущность сетевых методов планирования и управления (СПУ). Решение задачи по Леонарду Эйлеру

Оглавление Тема 1. Основные понятия и сущность сетевых методов планирования и управления (СПУ) 1 1. История появления и развития сетевых методов плани...

Бизнес-планирование

Понятие «планирование» и его виды.

1. Понятие «планирование» и его виды. Планирование – это процесс формирования целей, определения приоритетов, средств и методов их достижения. Планиро...

Высшая математика

Пуассоновский поток и его свойства. Простейший (пуассоновский) поток и его свойства. Получение экспоненциально распределенной случайной величины из равномерно распределенной. Уравнения в частных производных. Разностные аппроксимации гиперболических уравнений первого порядка. Параболическое уравнение в частных производных. Условно и безусловно устойчивые схемы. Метод прогонки для нахождения решения по неявной схеме. Линейная и нелинейная регрессия. Метод наименьших квадратов. Оптимизационные модели. Условная оптимизация. Метод наикратчайшего градиентного спуска для безусловной оптимизации. Метод наикратчайшего градиентного спуска. Линейная оптимизация. Симплекс-метод. Принцип оптимальности Беллмана для решения задач дискретной оптимизации.

Лекционные заметки по курсу «моделирование». §1. Общее понятие о моделировании. Моделирование как способ познания. Абстрактная логика учит, что познан...

Бизнес-планирование

Календарное планирование проекта

Лекция 5 . Календарное планирование проектов . Метод сетевого планирования. Правила построения сетевой модели Расчет параметров сетевого графика (граф...

Менеджмент организации

Календарное планирование проектов

Лекция 5 . Календарное планирование проектов . Метод сетевого планирования. Правила построения сетевой модели Расчет параметров сетевого графика (граф...

Информационные технологии

Основы исследования систем

Министерство образования и науки Российской Федерации федеральное государственное бюджетное образовательное учреждение высшего образования «САНКТ-ПЕТЕ...

Автоматика и управление

Методы и средства процессов проектирования

Дисциплина "Методы и средства процессов проектирования" (Конспект лекций) Содержание 1 Процесс проектирования 2 1.1 Структура процесса проектирования ...

Смотреть все