Аудит / Институциональная экономика / Информационные технологии в экономике / История экономики / Логистика / Макроэкономика / Международная экономика / Микроэкономика / Мировая экономика / Операционный анализ / Оптимизация / Страхование / Управленческий учет / Экономика / Экономика и управление народным хозяйством (по отраслям) / Экономическая теория / Экономический анализ Главная Экономика Оптимизация
Харчистов Б.Ф.. Методы оптимизации, 2004

Метод дихотомии (половинного деления)


В данном случае общее количество вычислений f(x) четное, т.е. N = 2/, l = 1,2,", на j-м шаге (j-й итерации) производится пара вычислений xjj) и x^j), отстоящих на расстоянии е /2 по обе стороны от середины текущего отрезка локализации [a(j-1), b(j-1)]. Если fj(j) < f2(j), то отбрасывается часть отрезка, расположенная справа от x^j); если f1(j) > f2(j), то отбрасывается
часть отрезка, расположенная слева от x1( j) .
Используются два условия окончания вычислений:
а) выполнение заданного количества вычислений N;
б) достижение заданной величины 5 уменьшения отрезка локализации.
Итак, алгоритм поиска минимума унимодальной функции методом дихотомии заключается в следующем.
Задаются N (либо 5) и е, полагается j=1.
На j-й итерации вычисляются
x1 j) =1 (a(j-1) + b( j-1))--, x2 j) =1 (a(j-1) + b (j-1)) + -, 1 2 2 2 2 2
f( j) = f (x1j)), f2( j) = f (x2j)).
Если f( j) < f2( j), то a(j) = a(j-1), b( j) = x^).
Если f(j) > f2(j), то a(j) = xПроверяется условие окончания вычислений:
L2 j
а) j=N/2 либо б) <5.
L0
Если оно выполняется, то определяются итоговый отрезок
локализации, оценки точки минимума x* и величины минимума
* *
f = f (x ), и вычисления завершаются.
Если условие не выполняется, то полагается j = j +1 и
осуществляется переход к п.2.
Отметим, что для определения оценки точки минимума надо рассмотреть все исследованные точки итогового отрезка локализации и выбрать ту из них, для которой значение функции минимально.
Пример. Определить методом дихотомии минимум функции f (х) = х4 -6х2 +10, заданной на отрезке А=[ 1,3], при N=8, ?=0,1.
Решение.
В данном случае будут выполнены N/2=4 итерации.
Результаты вычислений заносим в табл. 4.3.
Таблица 4.3 Номер итерации х{ J) х (J) 2 f1( J) < > f(J) a(J) b( J ) 0 1 1,95 2,05 1,644 < 2,446 1 1 3
2,05 2 1 ,475 1,575 1,680 > 1,270 1 ,475 2,05 3 1,713 1,813 1,004 < 1,082 1 ,475 1,813 4 1,594 1,694 1,211 > 1,017 1,594 1,813 Поскольку j=N/2=4, то вычисления завершаются. Точка минимума локализована на отрезке А8 = [1,594; 1,813]. На данном отрезке исследованы 4 точки: (4)
a
1,594 ^ f (a(4)) = 1,211; (4)
,(3)
1,713, f * = f (х13)) = 1,004.
> х = х
b(4) = 1,813 ^ f (bw) = 1,082;
(4)
= 1,694 ^ f (х24)) = 1,017; (3Ъ
X(3) = 1,713 ^ f (х(3)) = 1,004; Ответ: А8 = [1,594; 1,813], х = 1,713, f = 1,004.
<< Предыдушая Следующая >>
= К содержанию =
Похожие документы: "Метод дихотомии (половинного деления)"
  1. СОЦИАЛЬНАЯ ПОЛИТИКА ГОСУДАРСТВА
    методов регулирования социальной сферы перед методами прямого государственного вмешательства. Она характеризуется разгосударствлением социальной сферы, сведе нием до минимума государственных субсидий и дотаций и расши рением рыночных инструментариев в функционировании. В нашей стране при стратегической ориентации на социаль ное рыночное хозяйство в настоящее время доминирует рыночная социальная
  2. ГОСУДАРСТВЕННОЕ РЕГУЛИРОВАНИЕ ВНЕШНЕЭКОНОМИЧЕСКИХ СВЯЗЕЙ
    методов государственного воздей-ствия на сферу внешней торговли; Х равенство участников внешнеторговой деятельности, их не-дискриминация; Х исключение неоправданного вмешательства государственных органов во внешнеторговую деятельность; Х защита государством законных интересов и прав участников внешнеторговой деятельности и др. Каждый принцип имеет конкретное содержание, проявляю щееся в
  3. 6.5 Государственная поддержка и проблемы малого предпринимательства
    методы государственного ре гулирования и стимулирования субъектов малого предприниматель ства, разграничены полномочия между Российской Федерацией и ее субъектами. В Законе названы важнейшие направления государст венной поддержки малого предпринимательства: ж формирование инфраструктуры поддержки и развития малого п редпри н и м ател ьства; ж создание льготных условий использования субъектами
  4. 11.1. ИЗ ИСТОРИИ РАЗВИТИЯ НАУЧНОЙ ОРГАНИЗАЦИИ ТРУДА В РОССИИ
    методов решения конкрет ных производственных задач. Подход к обоим аспектам в разные периоды истории нашего государства был неодинаков. Говоря об историческом развитии НОТ, следует отметить, что были годы расцвета науки об организации труда, но были и перио ды ее полного забвения. Наука об организации труда как система сформулированных научных положений, относящихся к этой области знаний,
  5. 1.4. Становление глобального хозяйства
    методов менеджмента, маркетинга, передаче новых технологий и тем самым спо собствует глобализации мировой экономики. В основе экономической мощи транснационального капитала лежит международная олигополия, когда согласованная, скоординированная политика ведущих производителей разных стран не исключает конкурен ции между ними. Сеть международного производства привела к образованию эконо мического
  6. 13.2. Особенности международного маркетинга
    методов и приемов работы. Как и на отечественном рынке, маркетинг на зарубежных рынках состоит из ряда аналогичных последовательных шагов; постановка цели, разработка программы мероприятий и планирование деятельности, ана лиз и прогноз рыночной конъюнктуры, внутренней и внешней среды, сег ментирование рынка, разработка товарной стратегии и ценообразования, формирование каналов товародвижения,
  7. 30.1. Тенденции развития мирового рынка телекоммуникационных услуг
    методам регулирова ния (государственная собственность, государственные инвестиции и суб сидии) приходят косвенные (денежно-кредитная и налоговая политика), уже активно идут в ведущих странах на мировом телекоммуникационном рынке услуг и постепенно перемещаются в страны с менее развитыми рынками. Страны Центральной и Восточной Европы пока еще в меньшейстепени охвачены процессами либерализации,
  8. 30.2. Особенности ценообразования на телекоммуникационные услуги на мировом рынке
    метода является широкий диапазон возможных колебаний нормы прибыли компании-оператора в зависимости от текущей конъюнктуры рынка. В самом общем случае процесс ценообразования на телекоммуника ционные услуги определяется следующими факторами: общим уровнем развития научно-технического прогресса, процессами углубления между народного разделения труда, техническим уровнем развития телекомму
  9. Преемственность рабочей силы
    методы веде ния бизнеса, принятые в компании. Тем не менее упор де-лается на ограничении бюрократических формальностей, и традиция непосредственной передачи опыта среди со-трудников компании продолжает
  10. 5.2.3. Акционерное общество. Отделение собственности от контроля
    методов поглощения. Покупка акций на фондовом рынке. Аутсайдеры могут про сто покупать акции на фондовом рынке до тех пор, пока не при обретут то их количество, которое необходимо для контроля над компанией. Однако этот метод не может быть использован из-за существующих в большинстве стран законодательных ограниче ний. Почти во всех странах действуют законы, которые обязыва ют покупателя,