- •Киевский университет имени Тараса Шевченко
- •Общие рекомендации к использованию программного обеспечения
- •Элементарные преобразования матриц. Метод гаусса
- •Задача линейного программирования. Симплекс-метод Постановка задачи линейного программирования в стандартной форме (сзлп).
- •Задача линейного программирования. Модифицирован симплекс-метод.
- •Задача линейного программирования. Двойственный симплекс-метод
- •Транспортная задача. Метод потенциалов
- •Транспортная задача с ограниченными пропускными
- •Способностями. Метод потенциалов
- •Постановка транспортной задачи с ограниченными
- •Пропускными способностями (тзо).
- •Задача о кратчайшем пути на сети. Метод минти
- •Задача о максимальном потоке на сети. Метод форда-фалкерсона
- •Задача целочисленного линейного программирования. Метод гомори-1
- •Задача частично целочисленного линейного программирования. Метод гомори-2 Постановка частично целочисленной задачи линейного программирования (чцзлп).
- •Задача целочисленного линейного програмування. Метод гомори-3
- •Задача частично дискретного линейного программирования. Метод дальтона-ллевелина Постановка частично дискретной задачи линейного программирования (чдзлп).
- •Задача целочисленного линейного программирования. Метод ветвей и границ.
- •Лабораторная работа 14. Задача о назначении. Венгерский метод
- •Лабораторная работа 15. Задача о назначении. Метод мака Постановка задачи такая же самая, как и в предыдущем разделе (14.1–14.4).
- •6. Если каждый столбец матрицы расходов имеет элемент с отметкой *, тогда задача об оптимальных назначениях решена. Иначе переходим к следующему пункту.
- •Матричные игры. Связь с задачей линейного программирования. Метод брауна-робiнсон
- •Лабораторная работа 17. Методы одномерной оптимiзации
- •Лабораторная работа 18. Задача выпуклого квадратичного программирования. Квадратичный симплекс-метод
- •Задача безусловной оптимизации. Метод самого быстрого спуску
- •Лiтература
Лабораторная работа 17. Методы одномерной оптимiзации
Метод золотого сечения.
Метод золотого сечения (МЗС) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B]. Алгоритм метода реализуется в виде последовательности шагов, на каждом из которых осуществляется сужение интервала, что содержит точку минимума.
В начале вычислений возлагают А{0}= А, B{0}= B.
На s-у шаге определяют величины
L{s}= B{s} – G(B{s} – А{s})
R{s}= А{s}+ G(B{s} – А{s})
где константа G = (5 –1)/2 0.618. Подставим
А{s+1}= А{s}, B{s+1}= R{s}, если F(L{s}) F(R{s})
А{s+1}= L{s}, B{s+1}= B{s}, если F(L{s})> F(R{s}).
Итерации продолжают до тех пор, пока не будет выполняться неравенство
B{s} – А{s} ,
где > 0 — заданное число, которое определяет погрешность решения задачи.
На каждом шагу МЗП, начиная с 1-го, вычисляется лишь одно значение функции F(x), потому что одна из точек золотого перерезу на предыдущем шаге осуществляет золотой перерез промежутка на следующем шаге.
За приближенное решение задачи принимают
x* = (А{s}+ B{s})2, y* = F(x*).
При решении задачи максимизации функции F(x) необходимо заменить ее на функцию – F(x).
Метод случайного поиска.
Метод случайного поиска применяется для нахождения минимума (максимума) произвольной функции y=F(x), что задана в любой допустимой области D.
В программе рассматривается реализация данного метода для функции одной переменной.
Произвольная функция F(x) задана на промежутке [A,B]. С помощью датчика случайных чисел, равномерно распределенных на промежутке [0,1], строится последовательность случайных чисел x{k}, k=1...,N, равномерно распределенных на промежутке [A,B]. Вычисляются и сравниваются между собой значения функции F(x) в точках x{k}. Минимальное из них принимается за оценку минимума функции F(x) на промежутке [A,B].
Если N стремится к бесконечности, полученная оценка за вероятностью совпадает к глобальному минимуму функции, что рассматривается.
При решении задачи максимизации функции F(x) необходимо заменить ее на функцию – F(x).
Метод Фибоначчи.
Метод Фибоначчи (МФ) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B].
Алгоритм метода реализуется в виде последовательности шагов, на каждом из которых осуществляется сужение интервала, что содержит точку минимума.
В начале вычислений возлагают А{0}= А, B{0}= B.
На s-у шаге определяют величины
L{s}= B{s} – G{s}(B{s} – А{s})
R{s}= А{s}+ G{s}(B{s} – А{s})
где G{s}=Fi(N–s–1)Fi(N–s), s=0...,N–3, G{N–2}=(1+)2 или (1–)2, N — заданное число итераций >0, Fi(j) — числа Фибоначчи, что задаются рекуррентным соотношением
Fi(j)= Fi(j–1) + Fi(j–2), j 2, Fi(0)= Fi(1)= 1.
Возлагают
А{s+1}= А{s}, B{s+1}= R{s}, если F(L{s}) F(R{s})
А{s+1}= L{s}, B{s+1}= B{s}, если F(L{s})> F(R{s}).
За приближенное решение задачи принимают
x* = (А{N}+ B{N})2, y* = F(x*).
Для МФ в случае предварительно фиксированного числа итераций длина конечного интервала поиска минимальная.
При решении задачи максимизации функции F(x) необходимо заменить ее на функцию – F(x).
Метод дихотомии (половинного деления).
Метод дихотомии (МД) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B].
Алгоритм метода реализуется в виде последовательности шагов, на каждом из которых осуществляется сужение интервала, что содержит точку минимума.
В начале вычислений возлагают А{0}= А, B{0}= B.
На s-у шаге определяют величины
L{s} = (А{s}+ B{s} – )2
R{s}= (А{s}+ B{s}+ )2
где > 0 — достаточно малое число. Возлагают
А{s+1}= А{s}, B{s+1}= R{s}, если F(L{s}) F(R{s})
А{s+1}= L{s}, B{s+1}= B{s}, если F(L{s})> F(R{s}).
Итерации продолжают до тех пор, пока не будет выполняться неравенство
B{s} – А{s} ,
где >0 — заданное число, которое определяет погрешность решения задачи.
За приближенное решение задачи принимают
x* = (А{s}+ B{s})2, y* = F(x*).
При решении задачи максимизации функции F(x) необходимо заменить ее на функцию – F(x).
Программное обеспечение.
Обучающий модуль, с помощью которого задачи одномерной оптимизации Решаются в диалоге с пользователем за выложенными алгоритмами, вызывается из раздела «НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.
Задание.
Решить методами золотого пересечения, случайного поиска, Фибоначчи и дихотомии задачи одномерной оптимизации, условия которых задаются модулем с помощью команды «Данные» главного меню, а также найти наибольшее и наименьшее значение следующих функций на указанных промежутках:
1) F(x)= |||x2–1|–1|–1| x [–2, 2];
2) F(x)= 2x3–3x2–12x+1++ x [–2, 2];
3) F(x)= (x+1)2 ln(x+1)+x exp(–x) x [0, e];
4) F(x)= sin(x) sin(2x)+ arccos(x2) x [–0.75, 0.75];
5) F(x)= arctg(x) – ln(x) /2 x [0.65, 1.75];
6) F(x)= x+ + ехp(x) x2 x [0, 4];
7) F(x)= 4 x(x2 + 4)–[x2 (x – 2)](2/5) x [–2, 2].