- •Киевский университет имени Тараса Шевченко
- •Общие рекомендации к использованию программного обеспечения
- •Элементарные преобразования матриц. Метод гаусса
- •Задача линейного программирования. Симплекс-метод Постановка задачи линейного программирования в стандартной форме (сзлп).
- •Задача линейного программирования. Модифицирован симплекс-метод.
- •Задача линейного программирования. Двойственный симплекс-метод
- •Транспортная задача. Метод потенциалов
- •Транспортная задача с ограниченными пропускными
- •Способностями. Метод потенциалов
- •Постановка транспортной задачи с ограниченными
- •Пропускными способностями (тзо).
- •Задача о кратчайшем пути на сети. Метод минти
- •Задача о максимальном потоке на сети. Метод форда-фалкерсона
- •Задача целочисленного линейного программирования. Метод гомори-1
- •Задача частично целочисленного линейного программирования. Метод гомори-2 Постановка частично целочисленной задачи линейного программирования (чцзлп).
- •Задача целочисленного линейного програмування. Метод гомори-3
- •Задача частично дискретного линейного программирования. Метод дальтона-ллевелина Постановка частично дискретной задачи линейного программирования (чдзлп).
- •Задача целочисленного линейного программирования. Метод ветвей и границ.
- •Лабораторная работа 14. Задача о назначении. Венгерский метод
- •Лабораторная работа 15. Задача о назначении. Метод мака Постановка задачи такая же самая, как и в предыдущем разделе (14.1–14.4).
- •6. Если каждый столбец матрицы расходов имеет элемент с отметкой *, тогда задача об оптимальных назначениях решена. Иначе переходим к следующему пункту.
- •Матричные игры. Связь с задачей линейного программирования. Метод брауна-робiнсон
- •Лабораторная работа 17. Методы одномерной оптимiзации
- •Лабораторная работа 18. Задача выпуклого квадратичного программирования. Квадратичный симплекс-метод
- •Задача безусловной оптимизации. Метод самого быстрого спуску
- •Лiтература
Задача безусловной оптимизации. Метод самого быстрого спуску
Постановка задачи безусловной оптимизации.
Найти вектор x=(x1...,xn), что минимизирует (максимизирует) функцию
F(x)=F(x1...,xn).
Градиентные методы безусловной оптимизации.
Для задачи безусловной минимизации метод заключается в вычислении последовательности приближений x[s] по правилу
x[s+1]= x[s] – [s] F(x[s])
где F(.) — градиент функции F(.), который задается соотношением
[s]>0 — шаг, величина которого определяется конкретным градиентным методом. Начальное решение x[0] выбирается произвольно. Итерации прекращают, если на некотором шаге s выполняется неравенство
||F(x[s])|| < ,
где норма градиента определяется формулой
а >0 — некоторая заранее заданная величина, что определяет точность решения.
Метод самого быстрого спуска.
Метод самого быстрого спуска представляет собой градиентный метод, в котором величина шага [s] выбирается по правилу
F(x[s]– [s]F(x[s])) = min(F(x[s]–F(x[s])))
где минимум берется по всем >0.
При некоторых условиях x[s] следует к стационарной точке функции F(x), если s следует к бесконечности.
Программное обеспечение.
Обучающий модуль, с помощью которого задача безусловной оптимизации решается в диалоге с пользователем методом самого быстрого спуска, вызывается из раздела «НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета.
Задание.
Решить методом самого быстрого спуска задачи безусловной оптимизации, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9).
Лiтература
1. Ю.М.Ермольев, И.И.Ляшко, В.С.Михалевич, В.И.Тюптя. Математические методы исследования операций. Киев, «Высшая школа», 1979.
2. Ю.Д.Попов. Линейное и нелинейное программирование. Киев, УМК ВО, 1988.
3. Ф.П.Васильев. Численные методы решения экстремальных задач. Москва, «Наука», 1980.
4. И.Л.Калихман. Сборник задач по математическому программированию. Москва, «Высшая школа», 1975.
5. В.Ф.Капустин. Практические занятия по курсу математического программирования. Издательство Ленинградского университета, 1976.
6. Ю.П.Зайченко, С.А.Шумилова. Исследование операций, сборник задач. Киев, «Высшая школа», 1990.
7. В.Э.Фигурнов. IBM PC для пользователя. Москва, «Финансы и статистика», 1992.