- •И.Н. Слинкина
- •Оглавление
- •Вопросы к блокам по курсу «Исследование операций» Блок 1
- •Блок 1.
- •1.1. Предмет и задачи исследования операций
- •1.2. Основные понятия и принципы исследования операций
- •1.3. Математические модели операций
- •1.4. Понятие линейного программирования
- •1.5. Примеры экономических задач линейного программирования. Задача о наилучшем использовании ресурсов
- •1.6. Примеры экономических задач линейного программирования. Задача о выборе оптимальных технологий
- •1.7. Примеры экономических задач линейного программирования. Задача о смесях
- •1.8. Примеры экономических задач линейного программирования. Транспортная задача
- •1.9. Основные виды записи задач линейного программирования
- •1.10. Способы преобразования
- •1.11. Переход к канонической форме
- •1.12. Переход к симметричной форме записи
- •Блок 2.
- •2.1. Геометрическая интерпретация задачи линейного программирования
- •2.2. Решение задач линейного программирования графическим методом
- •2.3. Свойства решений задачи линейного программирования
- •2.4. Общая идея симплексного метода
- •2.5. Построение начального опорного плана при решении задач линейного программирования симплексным методом
- •2.6. Признак оптимальности опорного плана. Симплексные таблицы
- •2.7. Переход к нехудшему опорному плану.
- •2.8. Симплексные преобразования
- •2.9. Альтернативный оптимум (признак бесконечности множества опорных планов)
- •2.10. Признак неограниченности целевой функции
- •2.11. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание
- •2.12. Понятие двойственности для симметричных задач линейного программирования
- •3.1. Несимметричные двойственные задачи
- •3.2. Открытая и закрытая модели транспортной задачи
- •3.3. Построение начального опорного плана. Правило "Северо-западного угла"
- •3.4. Построение начального опорного плана. Правило минимального элемент
- •3.5. Построение начального опорного плана. Метод Фогеля
- •3.6. Метод потенциалов
- •3.7. Решение транспортных задач с ограничениями по пропускной способности
- •3.8. Примеры задач дискретного программирования. Задача о контейнерных перевозках. Задача о назначении
- •3.9. Сущность методов дискретной оптимизации
- •3.10. Задача выпуклого программирования
- •3.11. Метод множителей Лагранжа
- •3.12. Градиентные методы
- •4.1. Методы штрафных и барьерных функций
- •4.2. Динамическое программирование. Основные понятия. Сущность методов решения
- •4.3. Стохастическое программирование. Основные понятия
- •4.4. Матричные игры с нулевой суммой
- •4.5. Чистые и смешанные стратегии и их свойства
- •4.6. Свойства чистых и смешанных стратегий
- •4.7. Приведение матричной игры к злп
- •4.8. Задачи теории массового обслуживания. Классификация систем массового обслуживания
- •4.9. Потоки событий
- •4.10. Схема гибели и размножения
- •4.11. Формула Литтла
- •4.12. Простейшие системы массового обслуживания
- •2. Одноканальная система массового обслуживания с неограниченной очередью.
- •Список рекомендуемой литературы
3.10. Задача выпуклого программирования
Определение 1: Функция f(x), определенная на выпуклом множестве Х, называется выпуклой, если для любых точек ииз этого множества и любогосправедливо неравенство:
.
Если в этом соотношении при и любыхиХ (≠) имеет место строгое неравенство, тоf(x) называется строго выпуклой.
Определение 2: Функция f(x), определенная на выпуклом множестве Х, называется вогнутой, если для любых точек ииз этого множества и любогосправедливо неравенство:
.
Если в этом соотношении при и любыхиХ (≠) имеет место строгое неравенство, тоf(x) называется строго вогнутой.
Определение 3: Задача математического программирования
при ограничениях
(),
().
в которой либо целевая функция, либо ограничения, либо то и другое нелинейны, называется нелинейной.
Класс задач нелинейного математического программирования очень велик. Общих универсальных методов нет. Однако, есть задачи нелинейного программирования, для которых есть методы решения. Один из таких типов задач являются задачи выпуклого программирования.
В теории выпуклого программирования в качестве основной обычно рассматривается задача минимизации выпуклой функции n переменных при ограничениях(), (), где функции предполагаются выпуклыми.
Если иявляются вогнутыми, то имеем задачу максимизациипри ограничениях(), ().
3.11. Метод множителей Лагранжа
Метод множителей Лагранжа является классическим методом решения задач математического программирования (в частности выпуклого).
Рассмотрим классическую задачу оптимизации
при ограничениях
().
От основной задачи выпуклого программирования в данной постановке задача отличается тем, что в системе ограничений нет неравенств и нет ограничения неотрицательности для переменных.
Классический подход к решению данной задачи дает систему уравнений (необходимые условия), которым должна удовлетворять точка , доставляющая функциилокальный экстремум на множестве точек, удовлетворяющих системе ограничений (для задачи выпуклого программирования найденная точка будет и глобальным экстремум).
Предположим, что в точке функцияимеет локальный условный экстремум и ранг матрицы
равен m. Тогда необходимые условия запишутся в виде:
(),
(),
где
есть функция Лагранжа, – множители Лагранжа.
Алгоритм решения задачи методом множителей Лагранжа:
Составить функцию Лагранжа.
Найти частные производные функции Лагранжа по всем переменным и приравнять их к нулю. Получим систему изn+m уравнений с n+m неизвестными. Решив полученную систему, вычислим стационарные токи функции Лагранжа.
Из стационарных точек, взятых без , выбрать точки, в которых функция имеет условный локальный экстремумы при наличии ограничений.
Пример: Решить задачу математического программирования, используя метод множителей Лагранжа.
при
,
Решение:
Будем решать задачу без учета неотрицательности переменных.
1. Составим функцию Лагранжа.
2. Найдем ее частные производные по .
Приравняв производные к нулю, получим систему:
Решим ее:
Получена стационарная точка (91, 89). С помощью вторых производных легко доказать, что в полученной точке функция достигает условный локальный экстремум. Данная точка является точкой минимума функции.
Ответ: Z=17278.