- •Ю.Ю. Герасимов, в.К. Хлюстов
- •Математические методы и модели в расчетах на эвм: применение в лесоуправлении и экологии
- •Часть 1. Вариационная статистика
- •Глава 1.
- •1.1. Общие положения
- •1.2. Основные понятия статистики
- •1.3. Основы теории вероятностей
- •1.3.1. Понятие случайной величины
- •1.3.2. Классическое и статистическое определения вероятности события
- •1.3.3. Основные теоремы теории вероятностей
- •1.4. Контрольные вопросы и задания
- •Глава 2.
- •2.1. Постановка задачи
- •2.2. Классификация и группировка вариант
- •2.3. Графическое представление вариационных рядов
- •2.4.1. Показатели центральной тенденции
- •2.4.2. Показатели вариации
- •2.4.3. Достоверность статистических показателей
- •2.4.4. Показатели скошенности и крутизны
- •2.5. Доверительный интервал
- •2.6. Контрольные вопросы и задания
- •Глава 3.
- •3.1. Постановка задачи
- •3.2. Нормальное распределение
- •3.3. Логнормальное распределение
- •3.4.2. Бета-распределение
- •3.5. Распределение Пуассона
- •3.6. Семейство кривых распределения Джонсона
- •3.7. Семейство кривых Пирсона
- •Контрольные вопросы и задания
- •Глава 4.
- •4.1. Постановка задачи
- •4.3. Сравнение эмпирического распределения с теоретическим (критерий "хи-квадрат")
- •4.5. Сравнение дисперсий двух эмпирических совокупностей
- •4.6. Сравнение частот взвешенных рядов по критерию
- •4.7. Использование пакетов прикладных программ
- •4.8. Контрольные вопросы и задания
- •Глава 5.
- •5.1. Постановка задачи
- •5.2. Однофакторный комплекс
- •5.3. Двухфакторный комплекс
- •5.4. Использование ms Excel для проведения дисперсионного анализа
- •5.4.1. Однофакторный дисперсионный анализ
- •5.4.2. Двухфакторный дисперсионный анализ без повторения
- •5.5. Контрольные вопросы и задания
- •Глава 6.
- •6.1. Постановка задачи
- •6.2. Коэффициент корреляции
- •6.3. Корреляционное отношение
- •6.4. Схема полного корреляционного анализа
- •6.5. Использование пакетов прикладных программ Вычисление коэффициента корреляции с использованием ms Excel
- •Контрольные вопросы и задания
- •Глава 7.
- •7.1. Постановка задачи
- •7.2. Статистический анализ одномерных моделей
- •Уравнение прямой линии
- •Уравнение гиперболы
- •Уравнение показательной кривой
- •Окончательный выбор типа уравнения регрессии
- •7.4. Множественная регрессия
- •7.5. Применение ms Excel для расчета регрессии
- •Часть 2. Исследование операций
- •Глава 8.
- •8.1. Общие положения
- •8.2. Основные понятия системного анализа
- •8.3. Основные понятия исследования операций
- •8.4. Постановка задач принятия оптимальных решений
- •8.5. Контрольные вопросы и задания
- •Глава 9.
- •9.1. Постановка задачи
- •9.2. Графическое решение задачи линейного программирования
- •9.3. Задача линейного программирования в стандартной форме
- •Преобразования неравенств
- •Преобразование неограниченных по знаку переменных
- •2.4. Основы симплекс - метода линейного программирования
- •9.5. Метод искусственных переменных
- •9.6. Анализ чувствительности в линейном программировании
- •9.7. Решение задач линейного программирования на эвм
- •9.8. Контрольные вопросы и задания
- •Глава 10.
- •10.1. Постановка задачи
- •10.2. Метод ветвей и границ
- •10.3. Рекомендации по формулировке и решению задач цп
- •10.4. Задачи оптимизации раскроя
- •XA 0, xB 0, k 0 - целые.
- •XA 0, xB 0, k 0 - целые.
- •10.5. Постановка задачи дискретного программирования
- •Решение задач целочисленного и дискретного программирования на эвм
- •10.7. Контрольные вопросы и задания
- •Глава 11.
- •11.1. Общие понятия
- •11.2. Практические рекомендации при постановке задач динамического программирования
- •11.3. Оптимальное распределение ресурсов
- •11.4. Оптимальное управление запасами
- •11.5. Оптимальная политика замены оборудования
- •11.6. Контрольные вопросы и задания
- •Глава 12.
- •12.1. Постановка задачи
- •12.2. Применение стохастического программирования
- •12.3. Метод статистического моделирования
- •12.4. Контрольные вопросы и задания
- •Глава 13.
- •13.1. Постановка задач нелинейного программирования
- •13.2. Безусловная однопараметрическая оптимизация
- •13.2.1. Методы исключения интервалов
- •13.2.2. Методы полиномиальной аппроксимации
- •13.2.3. Методы с использованием производных
- •13.2.4. Сравнение методов безусловной однопараметрической оптимизации
- •13.3. Безусловная многопараметрическая оптимизация
- •13.3.1. Постановка задачи
- •13.3.2. Методы прямого поиска
- •13.3.3. Градиентные методы
- •13.4. Нелинейная условная оптимизация
- •13.4.1. Постановка задач условной нелинейной оптимизации
- •13.4.2. Методы штрафных функций
- •13.4.3. Методы прямого поиска
- •13.4.4. Методы линеаризации
- •13.5. Решение задач нелинейной оптимизации на эвм
- •13.6. Контрольные вопросы и задания
- •Приложение 1 Значения t - распределения Стьюдента при доверительной вероятности р и числе степеней свободы k
- •Плотность вероятности нормального распределения
- •Приложение 3 Значения χ2 при доверительной вероятности р и числе степеней свободы k
- •Продолжение приложения 3
- •Значения -функции
- •Приложение 5 Значения - в распределении Джонсона
- •Продолжение приложения 5
- •Продолжение приложения 5
- •Продолжение приложения 5
- •Приложение 6
- •Продолжение приложения 6
- •Продолжение приложения 6
- •Продолжение приложения 6
- •Приложение 7
- •Продолжение приложения 7
- •Продолжение приложения 7
- •Продолжение приложения 7
13.2.1. Методы исключения интервалов
Методы поиска, которые позволяют определить оптимум функции одной переменной путем уменьшения интервала поиска, носят название методов исключения интервалов.
Все методы одномерной оптимизации основаны на предположении, что исследуемая целевая функция в допустимой области по крайней мере обладает свойством унимодальности, так как для унимодальной функции W(x) сравнение значений W(t) в двух различных точках интервала поиска позволяет определить, в каком из заданных двумя указанными точками подынтервалов точки оптимума отсутствуют.
Правило исключения интервалов. Пусть W(x) унимодальна на отрезке [a,b], а ее минимум достигается в точке x*. Рассмотрим x1 и x2, расположенные a<x1<x2<b.
Если W(x1)>W(x2), то точка минимума W(x) не лежит в интервале (a,x1), т.е. x*(x1,b).
Если W(x1)<W(x2), то точка минимума W(x) не лежит в интервале (x2,b), т.е. x*(a,x2).
Это правило позволяет реализовать процедуру поиска путем последовательного исключения частей исходного ограниченного интервала. Поиск завершается тогда, когда оставшийся подынтервал уменьшается до достаточно малых размеров.
Главное достоинство поисковых методов основано на вычислении только значений функции и, следовательно, не требуют выполнения условия дифференцируемости и записи в аналитическом виде. Последнее свойство особенно ценно при имитационном моделировании.
Процесс применения методов поиска на основе исключения интервалов включает два этапа:
этап установления границ интервала;
этап уменьшения интервала.
Этап установления границ интервала
Выбирается исходная точка, а затем на основе правила исключения строится относительно широкий интервал, содержащий точку оптимума. Обычно используется эвристический метод, например, Свенна, в котором (k+1) -пробная точка, которая определяется по рекуррентной формуле
xk+1 = xk + 2k , k=0,1,2..., (13.1)
где
xo - произвольно выбранная начальная точка;
- подбираемая величина шага.
Знак определяется путем сравнения значений W(x), W(xo + ), W(xo -):
если W(xo -) W(x) W(xo + ), то имеет положительное значение;
если W(xo -) W(x) W(xo + ), то имеет отрицательное значение;
если W(xo -) W(x) W(xo + ), то точка минимума лежит между xo - и xo + и поиск граничных точек завершен;
если W(xo -) W(x) W(xo + ), то имеем противоречие предположению об унимодальности.
Пример 13.3. Приложение метода Свенна к задаче оптимального раскроя бревна на брус.
W(l)=(l/2)(dk -(dk-do)l/lo)2 max, при lo=0,10, =0,01, dk =0,22, do =0,12.
Определим знак :
W(12)=0,06;
W(12+1)=0,05265;
W(12-1)=0,06655.
Выполняется условие W(lo-)W(x)W(lo+), следовательно, имеет отрицательное значение; l*=12.
l1=lo-20 = 11;
l2=l1-21 = 9, W(7)=0,07605 > W(l1) x*<9;
l3=l2-22 = 5, W(5)=0,07225 < W(l2) x*>5;
Искомый интервал 5<l*<9.
Этап уменьшения интервала
Метод деления пополам
Найти W(x) на отрезке [a,b].
Шаг 1. xm=(a+b)/2; L=b-a; вычислить W(xm).
Шаг 2. x1=a+L/4; x2=b-L/4; вычислить W(x1) и W(x2).
Шаг 3.
Если W(x1)<W(xm), то исключить (xm,b], т.е. b=xm, xm=x1. Перейти к шагу 5.
Если W(x1)W(xm), то перейти к шагу 4.
Шаг 4.
Если W(x2)<W(xm), то исключить [a,xm), т.е. a=xm, xm=x2. Перейти к шагу 5.
Если W(x2)W(xm), то исключить [a,x1) и (x2,b], т.е. a=x1, b=x2. Перейти к шагу 5.
Шаг 5. L=b-a. Если L<, то закончить поиск. В противном случае вернуться к шагу 2.
Как видно из алгоритма, из каждых трех значений целевой функции W, вычисленных в интервале поиска, в дальнейшем используется только два, а третье не дает дополнительной информации и в дальнейшем не используется. В методе золотого сечения целевая функция вычисляется в точках интервала, расположенных таким образом, чтобы каждое вычисленное значение целевой функции давало бы новую полезную информацию.
Метод золотого сечения
Сущность метода. Интервал поиска делится на две части так, чтобы отношение длины большого отрезка к длине всего интервала было равно отношению
. Учитывая, что z1+z2=z, имеем |
W(x) |
|
z |
|
z12=z z2 = (z1+z2)z2 = z1z2 + z22; |
|
z1 |
z2 |
|
z1z2 + z22 - z12 = 0, |
|
|
|
|
откуда . |
|
|
|
|
|
a |
|
b |
x |
Рис. 13.2. Определение коэффициента дробления |
Найти W(x) на отрезке [a,b].
Шаг 1. Вычисляем коэффициент дробления отрезка [a,b]
k=( - 1)/2.
Шаг 2. x1=a+(1-k)(b-a), вычислить W(x1).
Шаг 3. x2=a+k(b-a), вычислить W(x2).
Шаг 4.
Если x2-x1, где - заданная погрешность, то xm = (x1+x2)/2, вычислить W(xm) и закончить поиск.
Если x2-x1>, то перейти к шагу 5.
Шаг 5.
Если W(x1)>W(x2), то исключить a=x1, x1=x2 и W(x1)=W(x2). Перейти к шагу 3, затем к шагу 4.
Если W(x1)W(x2), то b=x2, x2=x1 и W(x1)=W(x2). Перейти к шагу 2 и 4.
Пример 13.4. Приложение метода золотого сечения к задаче оптимального раскроя бревна на брус.
W(l)=-(l/2)(dk -(dk-do)l/lo)2 min,
где
lo=0,10,
dk =0,22,
do =0,12
в интервале 5l9 (см. пример 6.3) при l=0,1.
Итерация 1.
Шаг 1. a=5, b=9, k=( - 1)/2.
Шаг 2. l1=5+(1-k)(9-5)= 6,528, W(l1)= -0,0781.
Шаг 3. l2=5+k(9-5)= 7,368, W(l2)= -0,0789.
Шаг 4. l2-l1 0,1.
Шаг 5. W(l1) W(l2), a=l1, l1=l2 и W(l1)=W(l2)= -0,0789.
Итерация 2.
Шаг 3. l2=6,528+k( 9-6,528)= 8,056, W(l2)= -0,0783.
Шаг 4. l2-l1 = 8,056-7,368 0,1.
Шаг 5. W(l1)= -0,0789 W(l2)= -0,0783, b=l2, l2=l1 и W(l2)=W(l1).
Итерация 3.
Шаг 2. l1=6,528+(1-k)( 8,056-6,528)= 7,112, W(l1)= -0,0788.
Шаг 4. l2-l1 = 7,368-7,112 0,1.
Шаг 5. W(l1) = -0,0788 W(l2) = -0,0789, a=l1, l1=l2 и W(l1)=W(l2)= -0,0789.
Итерация 4.
Шаг 3. l2=7,112+k(8,056-7,112)= 7,695, W(l2)= -0,0783.
Шаг 4. l2-l1 = 7,695-7,368 0,1.
Шаг 5. W(l1)= -0,0789 W(l2)= -0,0783, b=l2, l2=l1 и W(l2)=W(l1).
Итерация 5.
Шаг 2. l1=7,112+(1-k)( 7,695-7,112)= 7,335, W(l1)= -0,0789.
Шаг 4. l2-l1 = 7,368-7,335 0,1; l*= (7,368-7,335)/2 =7,352 при котором W*(7,352)= 0,0789 найдено с заданной точностью.
Таким образом, применение методов исключения интервалов накладывает единственное ограничение на исследуемую целевую функцию - унимодальность. Следовательно, рассмотренные методы можно использовать для анализа как непрерывных, так и разрывных и дискретных функций. Логическая структура поиска основана на простом сравнении значений функции в двух пробных точках.