Н И Самойленко - Установка границ интервала неопределенности в задачах одномерной оптимизации - страница 1

Страницы:
1  2 

том. - М.: Транспорт, 1987. - 287 с.

2.Перевозка экспортно-импортных грузов. Организация логистических систем. -2-е изд. / Под ред. А.В.Кириченко. - СПб.: Питер, 2004. - 506 с.

З.Воркут А.И. и др. Транспортное обслуживание торгово-оптовых баз. - К.: Техні­ка, 1985. - 112 с.

Получено 03.02.2008

 

УДК 656.02

Н.И.САМОЙЛЕНКО, д-р техн. наук,

Харьковская национальная академия городского хозяйства

УСТАНОВКА ГРАНИЦ ИНТЕРВАЛА НЕОПРЕДЕЛЕННОСТИ В ЗАДАЧАХ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

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

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

Прямые методы одномерной оптимизации представляют собой двойной интерес: непосредственный - как методы поиска экстремума функций одной переменной и косвенный - в качестве встроенного этапа в ряде методов многомерной оптимизации.

Наиболее известными прямыми методами одномерной оптимиза­ции (безусловной и условной) являются: метод дихотомии (МД), метод золотого сечения (МЗС) и метод Фибоначчи (МФ) [1, 2]. Все перечис­ленные методы предполагают, что оптимизируемая функция является унимодальной.

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

Безусловная одномерная оптимизация состоит из двух этапов:

-  определения отрезка \^ x+, x++ J є R1 , содержащего оптималь­ное решение х и называемого интервалом неопределённости [1, c.49];

*                   Г + ++1

-    локализации   х  на отрезке I x , x    I с точностью до Є

(є<<1).

*

На втором этапе для определения точки х используются упомя­нутые ранее методы: МД, МЗС, МФ. Однако не один из методов не

ориентирован на определение отрезка [x +, x++] . Настоящая работа предназначена для устранения этого недостатка.

В случае безусловной минимизации функции цели алгоритм оп­ределения отрезка ^ x+, x++ J , гарантированно содержащего точку х*,

предполагает следующие действия :

1)      a : = -1;   b : = 1;   c : = 10

2)      if F(a) = F(b)  => [ x+ : = a;   x++ : = b; stop ]

3)      if F(a) > F(b)  => [ a := 1; b : = -1 ]

4)      if F(c) > F(a)  => [ x+ : = c;   x++ : = b; stop ]

5)      b : = a ;   a : = c ;   c : = 10 * c ; goto 4.

На рисунке схематично показан процесс оптимизации по приве­денному алгоритму. Ось абсцисс условно представлена в логарифми­ческой шкале.

<=| F(a) < F(bT\\ c

К


 

Начальный

1

1

2

3

4

отрезок

1

шаг

шаг

шаг

шаг


4

3

2

1

шаг

шаг

шаг

шаг

Схема работы алгоритма

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

Ax(*) = x++(k) x+(k) на kшаге и ставить её в зависимость от вида минимизируемой функции. Примером модифицированного алгоритма может служить следующая процедура:

1)   a : = -Є;   b : = Є;   c : = 1 ;   d : = c

2)       if F(a) = F(b)  => [ x : = 0 ; stop]

3)       if F(a) > F(b)  => [ a := Є ; b : = ]

4)       if F(c) > F(a)  =>  [ x+: = c;   x++ : = b; stop ]

5)       b : = a ;   a : = c ;   c : = d * c ; goto 4.

Данная модификация алгоритма при выполнении условия F(a) = F(b) в п.2 позволяет процесс оптимизации свести к одному эта­пу - первому.

Начальные значения величин с и d в п.1 позволяют регулировать приращение границ отрезка на каждом шаге алгоритма. Возможными значениями могут быть, например:

d = -,—1;  d = —-.1^—;  c = 1 и др.

'dF)    '            (dF)    ' Р

dx )х=а             V dx )х=а

Разработка алгоритма для установки границ интервала неопреде­лённости позволяет усовершенствовать методы МД, МФ и МЗС, как и любой другой метод, требующий задания интервала неопределённо­сти. Так, алгоритм усовершенствованного метода МД с учетом моди­фицированного алгоритма захвата оптимального решения при поиске минимума соответствует следующей процедуре:

1.      a : = -Є;   b : = Є;   c : = 1/Є ;   d : = c

2.      if F(a) = F(b)  => [ x* : = 0 ; F*=F(x*) stop ]

3.      if F(a) > F(b)  => [ a := Є ; b : = ]

4.      if F(c) > F(a)  => [ x+ : = c;   x++ : = b; goto 6 ]

5.      b : = a ;   a : = c ;   c : = d * c ; goto 4

'3

6.    x+(0) := a;   x++(0) := b; Є = Є3;   к: = 0

x+(k) + x++(k)                          Є Є

7.   xs   ~        2        '        1   — s     2' 2

8.      if (F^x(sk) _ Є)j = F^x(sk) + Є^) => [ x* : = xs(k) ; F*=F(x*); stop]

9.      if (F^x(k)< F Vxf jj) => [ x+(k+1) : = x+(k) ; x++(k+1) :=xs(k) ]

else   [x+(k+1) : = xs(k);   x++(k+1) : = x++(k) ]

10.     if ( x^(k+1) - x+(k+1) > Є) =>  [ k: = k+1 ;   goto 7]

x+(k +1) + x++(k +1)

11.     x* : =          2            ;  F*=F(x*) ; stop.
Здесь F(.) - минимизируемая функция.

Алгоритм усовершенствованного метода МЗС соответствует сле­дующей процедуре:

1.   a : = -Є;   b : = Є;   c : = 1ІЄ ;   d: = c

2.   if F(a) = F(b)  => [ x*: = 0 ; F*=F(x*) stop ]

3.   if F(a) > F(b)  => [ a := Є ; b : = ]

4.   if F(c) > F(a)  => [ x+: = c;   x++ : = b; goto 6 ]

5.   b : = a ;   a : = c ;   c : = d * c ; goto 4

6.   x+(0) := х+;   x++(0) := х++;   Є = Є3;   k: = 0]

7.   xi(k) = x+(k) + 0,382(x++(k) - x+(k)); x^k) = x+(k) + 0,618(x++(k) - x+(k))

8.   if (F(xi(k)) < F(x2(k)))  => [ x+(k+1) : = x+(k) ;   x++(k+1) : =x2(k) ;

Страницы:
1  2 


Похожие статьи

Н И Самойленко - Программа по теории вероятностей (для студентов заочной формы обучения)

Н И Самойленко - Методы решения задачи коммивояжера больших размерностей

Н И Самойленко - Установка границ интервала неопределенности в задачах одномерной оптимизации

Н И Самойленко - Расчет надежности трубопроводных систем с мостовыми соединениями элементов

Н И Самойленко - Исследование операций