АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Градиентные методы. Используя градиентные методы, можно найти, решение любой задачи нелинейного программирования

Читайте также:
  1. II. Методы непрямого остеосинтеза.
  2. II. Рыночные методы.
  3. III. Методы искусственной физико-химической детоксикации.
  4. III. Параметрические методы.
  5. IV. Современные методы синтеза неорганических материалов с заданной структурой
  6. А. Механические методы
  7. Автоматизированные методы
  8. Автоматизированные методы анализа устной речи
  9. Адаптивные методы прогнозирования
  10. Административно-правовые методы государственного управления
  11. Административно-правовые методы государственного управления
  12. АДМИНИСТРАТИВНО-ПРАВОВЫЕ МЕТОДЫ УПРАВЛЕНИЯ

 

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

К первой группе относятся методы, при использовании которых иссле­дуемые точки не выходят за пределы области допустимых решений задачи. В данном случае наиболее распространенным является метод Франка - Вульфа. Ко второй - методы, при использовании которых исследуемые точки могут как принадлежать, так и не принадлежать области допустимых решений. Од­нако в результате реализации итерационного процесса находится точка об­ласти допустимых решений, определяющая приемлемое решение. Наиболее часто используются метод штрафных функций и метод Эрроу - Гурвица. При нахождении решения задачи градиентными методами ите­рационный процесс продолжается до тех пор, пока градиент функции в очередной точке не станет равным нулю или же пока не выполнится неравенство

, где (точность полученного решения).

Метод Франка - Вульфа. Пусть требуется найти максимальное значе­ние вогнутой функции

(9)

при условиях

(10)

(11)

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

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

,

строят линейную функцию

. (12)

Находят максимум функции (12) при ограничениях (10) и (11). Пусть решение данной задачи определяется точкой . За новое допустимое решение исходной задачи принимают координаты точки , которые находят по формулам

,

где - некоторое число, называемое шагом вычислений . За принимают наименьший корень уравнения или выбирают произвольно, если он не принадлежит интервалу (0; 1).

Метод штрафных функций. Рассмотрим задачу нелинейного программирования (6) -(8), где - выпуклые функции.

Вместо того, чтобы решать эту задачу, находят максимум функции

,

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

,

где

а - некоторые постоянные числа, представляющие собой весовые ко­эффициенты.

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

,

где - шаг вычислений .

Итерационный процесс обычно начинают при сравнительно малых зна­чениях и, продолжая его, эти значения постепенно увеличивают.

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

В качестве начальных значений берут произвольные неотрицательные числа.

 

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)