Решить две задачи под Вариантом № 4

Переходим к шагу 5.

50. Проверим условие k ≥ M: k= 0 <10 = M, переходим к шагу 6.

60. Следующая точка находится по формуле

.

Подставим полученные выражения, для координат в f (x):. Найдем минимум функции по t0 с помощью необходимых условий безусловного экстремума:

. Отсюда. Поскольку, найденное значение шага обеспечивает минимум функции по t0.

70. Найдем

80. Вычислим. Вычислим. Вывод: полагаем k = 1 и переходим к шагу 3.

31. Вычислим .

41. Вычислим. Переходим к шагу 5.

51. Проверим условие k ≥ M: k =1 <10 = M, затем переходим к шагу 6.

61. (см. п. 60).

71. Найдем

81. Вычислим. Вычислим. Полагаем k=2 и переходим к шагу 3.

33. Вычислим .

43. Вычислим. Переходим к шагу 5.

53. Проверим условие k ≥ M: k = 2 < 10 = M, переходим к шагу 6.

63. (см. п. 60).

73. Найдем

83. Вычислим. Вычислим. Полагаем k=3 и переходим к шагу 3.

33. Вычислим .

43. Вычислим. Расчет окончен. Найдена точка, f (x3)= 0,127

На рис. 3.1 полученные точки выделены и соединены сплошной линией.

Рис. 3.1

3.

1.2. Метод покоординатного спуска Пусть дана функция f (x), ограниченная снизу на множестве Rn и имеющая непрерывные частные производные во всех его точках.

Требуется найти локальный минимум функции f (x) на множестве допустимых решений X = Rn, т. е. найти такую точку x0 Rn, что

Стратегия поиска Стратегия решения задачи состоит в построении последовательности точек {xk}, k = 0,1,…, таких что f (xk+1) < f (xk), k= 0,1,…. Точки последовательности {xk} вычисляются по циклам в соответствии с правилом

xk+1 = xk — tkf (xk), (3.3)

где j — номер цикла вычислений; j = 0,1,2,…; k — номер итерации внутри цикла, k = 0,1,…, n-1; ek+1, (k = 0,1,…, n-1) — единичный вектор, (k+1)-я проекция которого равна 1; точка x00 задается пользователем, величина шага tk выбирается из условия

или .

Если выбранное условие при текущем tk не выполняется, шаг уменьшается вдвое и точка вычисляется заново. Легко видеть, что при фиксированном j за одну итерацию с номером k изменяется только одна проекция точки xjk, имеющая номер k+1, а в течение всего цикла с номером j, т. е. начиная с k = 0 и кончая k = n-1, изменяются все n проекций точки xj0. После этого точке xjn присваивается номер xj+1,0 и она берется за начальную точку для вычислений в j+1 цикле. Расчет заканчивается в точке xjk при выполнении, по крайней мере, одного из трех критериев окончания счета:, или j

3.

1.3. Метод конфигураций Хука и Дживса Требуется найти безусловный минимум функции f (x) многих переменных, т. е. найти такую точку, что .

Стратегия поиска Метод конфигураций представляет собой комбинацию исследующего поиска с циклическим изменением переменных и ускоряющего поиска по образцу. Исследующий поиск ориентирован на выявление локального поведения целевой функции и определение направления ее убывания вдоль «оврагов». Полученная информация используется при поиске по образцу при движении вдоль «оврагов».

Исследующий поиск начинается в некоторой начальной точке x*, называемой старым базисом. В качестве множества направлений поиска выбирается множество координатных направлений. Задается величина шага, которая может быть различной для разных координатных направлений и переменной в процессе поиска. Фиксируется первое координатное направление и делается шаг в сторону увеличения соответствующей переменной.

Если значение функции в пробной точке меньше значения функции в исходной точке, шаг считается удачным. В противном случае необходимо вернуться в предыдущую точку и сделать шаг в противоположном направлении с последующей проверкой поведения функции. После перебора всех координат исследующий поиск завершается. Полученная точка называется новым базисом. Если исследующий поиск с данной величиной шага неудачен, то она уменьшается, и процедура продолжается. Поиск заканчивается, когда текущая величина шага станет меньше некоторой величины.

Поиск по образцу заключается в движении по направлению от старого базиса к новому (от точки х0 через точку х1, из точки х1 через точку х2, из точки х2 через х3 на рис. 3.4). Величина ускоряющего шага задается ускоряющим множителем λ. Успех поиска по образцу определяется с помощью исследующего поиска из полученной точки. Если при этом значение в наилучшей точке меньше, чем в точке предыдущего базиса, то поиск по образцу удачен (точки 6, 11 — результат удачного поиска по образцу, а точка 15 — неудачного). Если поиск по образцу неудачен, происходит возврат в новый базис, где продолжается исследующий поиск с уменьшенным шагом.

3.

1.4. Метод Розенброка Требуется найти безусловный минимум функции f (x) многих переменных, т. е. найти такую точку, что .

Стратегия поиска Задается начальная точка. Из нее осуществляется итеративный поиск направления убывания функции с помощью изменяемых дискретных шагов вдоль n линейно независимых и ортогональных направлений. В случае удачного шага в исследуемом направлении его значение на следующей итерации увеличивается с помощью коэффициента растяжения, а в случае неудачи уменьшается за счет умножения на коэффициент сжатия (при этом направление поиска изменяется на противоположное). Поиск в системе текущих направлений проводится до тех пор, пока все возможности уменьшения функции не будут исчерпаны. Если по каждому направлению поиска имеет место неудача, строится новое множество линейно независимых и ортогональных направлений и циклический поиск по отдельным направлениям продолжается. Новые направления поворачиваются по отношению к предыдущим так, что они оказываются вытянутыми вдоль оврага

3.

2. Условная оптимизация

3.

2.1. Методы штрафных функций

3.

2.1.

1. Метод барьерных поверхностей Рассмотрим метод барьеров применительно к задаче вида

n (3.1)

.

Этот метод (МБП) относится к группе методов внутренней точки и основан на использовании барьерной функции вида

(3.2)

где r > 0 — параметр, значения которого убывают с каждым циклом;

(i (0 — весовые коэффициенты;

— функционал: при ,

т.е. при (точка x должна быть внутренней).

При этом барьерная функция Р (x, r) неограниченно возрастает при .

Примерами функций барьера являются:

а) обратная функция

(3.3)

б) логарифмическая функция

.

При приближении к границе изнутри области, как только gi (x) (0, штраф становится очень большим. Таким образом, вдоль границ допустимой области образуются сильные барьеры. Построив барьерную функцию и определив начальную внутренюю точку x (1) и, приступаем к процедуре минимизации Р (x, r) при заданном начальном значении параметра r0. Тогда конечная точка х (2) первой итерации процедуры становится исходной точкой следующего шага для минимизации Р при уменьшенном значении r и т. д. Завершающий этап минимизации реализуется при очень малом значении r, так что результирующая точка x с точностью до установленного допуска может оказаться либо на одной, либо одновременно на нескольких поверхностях, заданных ограничениями задачи.

Если через обозначить точку минимума вспомогательной функции Р (x, r), то последовательность {x ®} сходится к решению исходной задачи при r (0.

Минимизация барьерной функции может быть выполнена любым методом безусловной минимизации, которые были рассмотрены выше. Один из существенных недостатков методов барьерных функций связан с тем, что эти функции определены в допустимой области, которая должна иметь непустую внутреннюю область, т. е. множество

{X: gi (x) >0, i = (1,…, m) } должно быть непустым.

Алгоритм метода барьерных поверхностей Пусть имеется исходная задача вида:

минимизировать f (x)

при условиях gi (x) (0, i = (1,…, т).

Начальный этап. Выбрать (> 0 в качестве константы остановки и начальную допустимую точку x0 (R, для которой gi (x0) > 0, i = (1,m), скаляр r0, 0 < β < 1. Положить k = 1 и перейти к основному этапу.

Основной этап Шаг 1. При начальной точке xk решить следующую задачу безусловной оптимизации:

минимизировать ,

где R (gi (xk)) описывается одним из выражений (3.3) .

Положить xk+1 равным оптимальному решению xk◦ задачи (3.2) и перейти к шагу 3.

Шаг 3. Если штрафная составляющая барьерной функции (3.2), то нужно остановиться. В противном случае положить rk+1 = β rk, заменить k на (k+1) и перейти к шагу 1.

3.

2.1.

3. Метод штрафных функций Ранее рассмотренные методы барьерных поверхностей относятся к группе методов внутренней точки (т.е. они начинают работать с допустимой точки x○ и генерируют последовательность оптимальных допустимых решений x1○, x2○,…, xk○). В отличие от них методы внешней точки начинают работать с недопустимой точки и генерируют последовательность недопустимых решений, которая приближается к оптимальному решению извне допустимой области.

Пусть имеется задача НП. Метод штрафных функций основан на преобразовании исходной задачи с ограничениями в одну или последовательность задач безусловной оптимизации. С помощью функций, задающих ограничения, строится так называемая штрафная функция, которая добавляется к целевой функции исходной задачи так, чтобы нарушение какого-либо из ограничений исходной задачи становилось невыгодным (с точки зрения получаемой задачи безусловной оптимизации). В частности, для ограничений целесообразна штрафная функция следующего вида:

(3.4)

где R1 и R2— непрерывные функции, удовлетворяющие условиям:

а) R1(y) = 0, если у ≥ 0, и R1(у) > 0, если у < 0;

б) R2(у) = 0, если у = 0, и R2(у) > 0, если у ≠ 0.

Типичными являются следующие формы функций R1 и R2 :

R1(у) = [mах {0; -у} ]p, R2(у) = -y-p, где р (0 — целое число. Таким образом, штрафная функция ((x) обычно имеет вид

. (3.5)

И далее от задачи НП переходим к задаче безусловной оптимизации вспомогательной функции:

минимизировать f (x) + rа (x), (3.6)

где r> 0— коэффициент штрафа.

Пусть (— непрерывная функция вида (3.5). Обозначим

. (3.7)

Подход, связанный со штрафной функцией, состоит в решении следующей задачи:

максимизировать (® при условии r > 0.

Алгоритм метода штрафных функций В связи с трудностями, связанными с использованием большого параметра штрафа r, в большинстве алгоритмов штрафных функций применяют последовательность возрастающих параметров для каждого нового значения параметра штрафа. Используется алгоритм оптимизации, начинающийся из оптимального решения, соответствующего предыдущему значению параметра r .

Пусть имеется задача минимизации f (x) при условиях gi (x) (0, hi (x) = 0, где функции fi (x), gi (x) и hi (x) непрерывны на множестве Rn.

Начальный этап. Выбрать (> 0. Выбрать начальную точку x1, параметр штрафа r1 и число (> 1. Положить k = 1 и перейти к основному этапу.

Основной этап

Шаг 1. При начальной точке xk решить следующую задачу:

минимизировать f (x) + rk ((x) =

где р > 0, р — целое и x (X.

Положить xk+1 равным оптимальному решению этой задачи и перейти к следующему шагу.

Шаг 3. Если rk ((xk+1) < (, то следует остановиться, в противном случае положить rk+1=(rk. Заменить k на (k+1) и перейти к шагу 1.

Список литературы

Введение

в математическую экономику. — М.: Наука, 1984. — 296 с.

Ашманов С. А. Линейное программирование. — М.: Наука, 1981. — 340 с.

Данциг Дж. Линейное программирование. Его применения и обобщения. — М.: Прогресс, 1966. — 280 с.

Замков О.О., Толстопятенко А. В., Черемных М. Математические методы в экономике. — М.: Наука, 1998. — 180 с.

Иванилов Ю.П., Лотов А. В. Математические модели в экономике. — М.: Наука, 1979. — 250 с.

Интрилигатор М. Математические методы оптимизации и экономическая теория. — М.: Прогресс, 1975. — 380 с.

Канторович Л.В., Горстко А. Б. Оптимальные решения в экономике. — М.: Наука, 1972. — 250 с.

Колесников А. Н. Краткий курс математики для экономистов. — М.: Прогресс, 1997. — 208 с.

Петров А.А., Поспелов И. Г., Шананин А. А. Опыт математического моделирования экономики. — М.: Энергоиздат, 1996. — 544с.

Федосеев и др. Экономико-математические методы и прикладные модели. — М.: Наука, 2000. — 220 с.

Юдин Д.Б., Гольштейн Е. Г. Линейное программирование. Теория, методы и приложения. — М.: Наука, 1969. — 320 с.