- •Предисловие
- •1.1. Постановка и классификация задач
- •1.2. Основные определения
- •1.3. Классический метод определения экстремума функции
- •Контрольные вопросы и задания
- •Глава 2. Одномерная оптимизация
- •2.1. Интервал неопределенности
- •2.2. Метод дихотомии
- •2.3. Метод фибоначчи
- •2.4. Метод золотого сечения
- •2.5. Метод квадратичной интерполяции
- •Контрольные вопросы и задания
- •Глава 3. Оптимизация функций нескольких переменных
- •3.1. Методы прямого поиска
- •3.1.1. Метод покоординатного спуска
- •3.1.2. Метод поиска Хука – Дживса
- •Метод Розенброка (метод вращающихся координат)
- •Метод Нелдера-Мида (метод деформируемого многогранника)
- •Метод сопряженных направлений Пауэлла
- •3.1.6. Методы случайного поиска
- •3.2. Градиентные методы
- •3.2.1. Метод наискорейшего спуска
- •Метод сопряженных градиентов Флетчера и Ривса
- •3.3. Методы второго порядка
- •3.3.1. Метод Ньютона
- •3.3.2.Метод Дэвидона - Флетчера - Пауэлла
- •Итерационная процедура Дэвидона-Флетчер-Пауэлла может быть представлена последовательностью шагов.
- •Контрольные вопросы и задания
- •Глава 4. Условная оптимизация
- •4.1. Множители лагранжа
- •4.2. Условия куна - таккера
- •Методы решения задач условной оптимизации
- •4.3.1. Метод последовательной безусловной оптимизации
- •4.3.2.Метод скользящего допуска
- •Контрольные вопросы и задания
- •Глава 5. Линейное программирование
- •5.1. Постановка задачи лп
- •Тогда задача лп (1) - (3) запишется в виде
- •5..2. Каноническая и стандартная формы задачи лп
- •5.3. Симплекс - метод
- •Порождение начального допустимого базисного решения
- •Двойственность в линейном программировании
- •5.6. Транспортная задача
- •Контрольные вопросы и задания
- •Заключение
- •Библиографический список
- •Глава1. Безусловная оптимизация………..………4
- •Глава 2. Одномерная оптимизация………..….…….9
- •Глава 3. Оптимизация функций нескольких переменных………………………………………..….…..20
- •Глава 4. Условная оптимизация…………………..49
- •Глава 5. Линейное программирование…………..60
- •Лидия Ивановна Лыткина Методы оптимизации с программами в системе mathcad
- •660014, Красноярск, просп. Им. Газ. ”Красноярский рабочий”, 31.
Контрольные вопросы и задания
1. Определите условный экстремум следующих функций:
1.1. при;
при ;
при .
2. Как изменятся условия Куна-Таккера, если требуется максимизировать функцию?
3. Почему штрафная функция вида называется барьерной?
4. Назовите основные недостатки метода последовательной безусловной оптимизации.
5. Какой тип штрафной функции можно использовать для задачи с ограничениями типа равенства?
6. Какие точки участвуют при поиске методом скользящего допуска?
7. Какое условие является критерием остановки в методе скользящего допуска?
Глава 5. Линейное программирование
Задача линейного программирования (ЛП) состоит в оптимизации линейной функции при наличии линейных ограничений. Методы ЛП широко используются для решения различных военных, экономических, промышленных и организационных задач. Главными причинами столь широкого применения таких методов являются доступность математического обеспечения и возможность анализа решений задач ЛП.
Многие практические задачи могут быть сформулированы в виде задачи ЛП. Кроме того, эти задачи часто используются в процессе решения нелинейных оптимизационных задач.
Для задач ЛП разработан универсальный симплекс-метод, который входит в любой пакет прикладных программ.
Транспортная задача представляет собой особый случай задачи ЛП; для нее разработан метод потенциалов.
5.1. Постановка задачи лп
Приведем пример постановки задачи и построение математической модели задачи линейного программирования. Вначале рассмотрим задачу о наилучшем использовании ресурсов.
Пусть некоторая производственная единица может выпускать видов продукции. Предприятие при этом должно ограничитьсяимеющимися видами ресурсов. Известна экономическая выгода (прибыль) производства единицы продукции каждого вида. Заданы технологические коэффициенты, которые показывают: сколько единиц-го ресурса требуется для производства единицы продукции-го вида, т.е.. Составить план выпуска продукции, чтобы обеспечить максимум объема реализации при имеющихся ресурсах.
Построим математическую модель. Пусть - количество продукции-го вида, которое требуется произвести.
Учитывая тот факт, что предприятие не может потратить больше ресурсов, чем их имеется, и что каждый ресурс может быть использован для производства любого вида продукции, запишем ограничения задачи:
по смыслу задачи
, .
Целевая функция задачи – объем реализации или прибыль - имеет вид
Как видно из приведенного примера, построенная математическая модель имеет характерные особенности: и целевая функция, и функции ограничения являются линейными.
Построение математической модели задачи ЛП выполняется в определенном порядке:
вводятся переменные величины задачи, т.е. такие величины, заданием числовых значений которых однозначно определяется один из вариантов исследуемого процесса;
исходя из условий задачи записываются ограничения, которым должны удовлетворять введенные переменные;
составляется целевая функция, которая в математической форме выражает критерий выбора лучшего варианта.
Общая задача линейного программирования формулируется следующим образом:
при условиях
; .
Предполагается, что значения () известны (выявлены на стадии анализа реальной ситуации).
Введем матричные обозначения:
; ;
С=;X=.