Студопедия Главная Случайная страница Обратная связь

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

ЗНЛП – это задача вида





ƒ(x1,x2,…,xn)→opt.

g(x1,x2,…,xn)≤≥=bi; i=1,n (1)

xj≥0; j=1,n;

 

Если система ограничений содержит только уравнения и функции ƒi и gi непрерывны вместе со своими частными производными, то задача является задачей на условный экстремум и решается методом множителей Лагранжа:

1. Рассматриваем дополнительную функцию Лагранжа, вводя набор дополнительных переменных λ1, λ2, … λm

F(λi,xj)=ƒ(x1, x2, …, xn)+ λi (bi-gi (x1, x2, …, xn)).

2. Находим безусловные экстремумы функции F, которые являются решением задачи.

Приближенные методы решения ЗНЛП:

Используя градиентные методы, можно найти решение любой ЗНЛП.

 

Метод Франка-Вульфа:

 

Если ƒ(x1, x2, …, xn)→max и является вогнутой функцией на выпуклом множестве Ω, т.е

При условиях ∑aijxj≤bi ; i=1;m; xj≥0, то применяется следующий алгоритм:

1. Найти исходное допустимое решение задачи

2. Найти градиент функции ƒ

3. Построить функцию

; найти ее максимальное значение, т.е Z(k)

4. По формуле ; - произвольно, или находится как наименьшее решение уравнения

5. Проверить необходимость перехода к последующему допустимому решению, приняв в качестве критерия оценки неравенство

пункт 2, где x(0)(к). В противном случае решение задачи найдено.

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

ƒ(x1, x2, …, xn)→max ƒ вогнутая на Ω Ω: gi(x1, x2,…, xn)≤bi xj≥0, где gi - выпуклые функции.

Алгоритм метода:

1. Найти исходное допустимое решение задачи

2. Выбрать шаг вычислений

3. Найти и

4. По формуле

Определить координаты точки определяющей новое решение задачи.

Где αi(x1,x2,…,xn)=0, если bi-gi(x1,…xn)≥0 и αi(x1,x2,…,xn)=αi,если bi-gi<0 и

αi – весовые коэффициенты.

Начинают итерационный процесс при малых αi, постепенно их увеличивая.

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

В случае необходимости переходят к этапу 2, в противоположном случае решение найдено.

6. Устанавливают значение весовых коэффициентов и переходят к этапу 4

Замечание: Произвольный выбор значений αi приводит к значительным колебаниям удаленности определяемых точек от области допустимых решений. Этот недостаток устраняется при решении задачи методом Эрроу – Гурвица, согласно которому на очередном шаге числа αi выбирают по формуле:

αi (0) – произвольное положительное число.

 

 







Дата добавления: 2015-04-19; просмотров: 638. Нарушение авторских прав; Мы поможем в написании вашей работы!




Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...


Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...


Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...


Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

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

Деятельность сестер милосердия общин Красного Креста ярко проявилась в период Тритоны – интервалы, в которых содержится три тона. К тритонам относятся увеличенная кварта (ув.4) и уменьшенная квинта (ум.5). Их можно построить на ступенях натурального и гармонического мажора и минора.  ...

Понятие о синдроме нарушения бронхиальной проходимости и его клинические проявления Синдром нарушения бронхиальной проходимости (бронхообструктивный синдром) – это патологическое состояние...

Различия в философии античности, средневековья и Возрождения ♦Венцом античной философии было: Единое Благо, Мировой Ум, Мировая Душа, Космос...

Характерные черты немецкой классической философии 1. Особое понимание роли философии в истории человечества, в развитии мировой культуры. Классические немецкие философы полагали, что философия призвана быть критической совестью культуры, «душой» культуры. 2. Исследовались не только человеческая...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит...

Studopedia.info - Студопедия - 2014-2025 год . (0.012 сек.) русская версия | украинская версия