Задачи нелинейного программирования. Графический метод решения ЗНП

Рассмотрим ЗНП и способы её решения. Математическая модель ЗНП в общем виде формулируется следующим образом:

f =(x₁,x_2, …,х_n) → min (max). При этом переменные должны удовлетворять ограничениям:

g₁(x₁,x_2, …,х_n) ≤b₁,

…………………………

g_m(x₁,x_2, …,х_n) ≤b_m,

g_m+1(x₁,x_2, …,х_n) ≥b_m+1,

…………………………

g_k(x₁,x_2, …,х_n) ≥b_k,

g_k+1(x₁,x_2, …,х_n)=b_k+1,

………………………

g_p(x1,x_2, …,х_n)=b_p.

x₁,x_2,…,х_n ≥0, где хотя бы одна из функций f, g_i нелинейная.

Для ЗЛП нет единого метода решения. В зависимости от вида целевой функции и системы ограничений разработаны специальные методы решения, к которым относятся метод множителей Лагранжа, градиентные методы, приближённые методы решения, графический метод.Рассмотрим основные идеи графического метода. Максимум и минимум достигается в точках касания линии уровня с областью допустимых решений (ОДР), которая задается системой ограничений. Например, если линии уровня - прямые, то точки касания можно определить, используя геометрический смысл производной.

29.Динамическое программирование. При решении, задачи разделяются на этапы:1) Необходимо описать процесс перехода производной эк-й системы из одного состояния в другое, при этом пред-т., что процесс должен быть Марковским. Этот процесс без посл-й т.е дальнейшее развитие процесса, если система находится в состоянии Sn, зависит только от данного состояния и не зависит от того, как система пришла в это состояние.Процесс длится опред-е число шагов N и на кажд шаге осущ-ся выбор одного управления Un, под воздействием к-го система перех-т с одного в др состояние.Sn , Un=U(n)*S(n) Каждый шаг т.е выбор очер-го решения связан с опред-м эф-м , к-й зависит от тек-го состояния. .Общий эффект за n шагов сумм-тся из эф-в на отд-х шагах т.е критерий оптим-ии должен быть адетивным. Основная идея- требуется для кажд шага найти Un, чтобы посл-ть U1,U2…UN приводила к max эффекту.Стратегия управления-любая допуст-я послед-ть решений. Основоположник Бэлман. Посл. Решения должны составлять оптим-ю стратегию, привяз-ся к этому состоянию : , Sn SN, где все допустимые напрвавления находившиеся в Sn, - эффект от принятия решения Un состояния.

4 Общая запись оптимизационной ЭММ. Оптим-е модели в эк-ке возникают при практической реализации принципа оптимальности в управлении. Суть принципа оптимальности состоит в стремлении выбрать такое управленческое решение. К-е состоит из Х=(Х1,Х2…Хn) к-е учитывало бы внутр возможности и внешние производ-й деят-ти объекта F(x) max (min) F-целевая ф-я(критерий оптимальности). В более развернутом виде задача усл-й оптимизации можно записать F(x)=F(x1,x2,…xn) max(min). План, к-й достовляет max(min) наз-тся оптимальным решением. ЭММ делится на:1) Макроэк-е,2)Микроэк-е,3)Аналитические,4)Нормативные. Этапы рения задач:1) постановка задачи:описание,суть;2)разработка мат-й модели;3) получение решения по модели: решение задачи.; 4)интерпритация результата и внедрение полученного решения. Основные принципы разработки ЭММ: 1)принцип адекватности, 2)принцип системности. Адэкватность модели – требование сглаж-го приблежения теорит-й модели к устойчивым сущ-м характеристикам и закономерностям исслед-го реального процесса или явления.

Системность предполагает интерпритацию объект, как большой системы и соот-о применения системного подхода к его исследованию.

Составление математической модели.

1) Цель – минимизация себестоимости раскроя.2) Параметры:п – число различных видов материала, поступающего на раскрой;d_j – количество материала j-го вида, m – число различных видов изделий, которые надо изготовить. b_j – число изделий i-го вида, l – число различных способов раскроя;a_ijk – число изделий i-го вида, которое можно получить из единицы материала j-го вида при k-м способе раскроя ;

c_jk – себестоимость раскроя единицы материала j-го вида k-м способом;3) Управляющие переменные x_jk – количество единиц материала j-го вида, раскраиваемых k-м способом;4) Область допустимых решений определяется ограничениями по количеству исходного материала (3.13), ограничениями по выпуску (3.14) и условиями неотрицательности управляющих переменных.