Задачи лин и нелин программирования

Если ЗМП целев ф-ция f(x) и все ограничения заданы линейными ф-ями, то соотв задача наз-ся ЗЛП. Если хотя бы 1 из функций нелин, то это ЗНП.

f( + = - полинома от многих переменных.

- постоянные величины

х, у- переменные

в общем случае ЗЛП м. записаться в виде:

найти max(min) =

{

от ограничения типа неравенств можно перейти к огран типа рав-ва и наоборот, введением дополнит переменных.Тогда общ задачу ЛП можно записать:

min =

,

,

иногда ЗЛП записывают стандарт форме.

З-чу нах-ия max цел. ф-ии м. свести к min ф-ции:

min[- ]

 

ограничение ЗЛП образует некотор общую часть Н-мерного простр-ва, кот наз-ся многогранником решения.

Задача дискретного программирования

Быстрое развитие эк- мат. м-дов сопровождается появлением больших кол-ва нов проблем, кот делятся на 2 группы:

1) вычислительные, вызванные дискретностью переменных, нелин-тью

2)М-дологич проблемы вызванные действием случ. факторов.

Реш- нием з-ч нахожд. оптим реш-ний при наличии оптим факторов заним-ся стохастич. программирование f(

ЗЛП записывается обычно: max(min)

при , f –целевая функция

Данная з-ча яв-ся ЗДП, еслиG- дискрет множество, - подмножества

сущ 3 осн фактора ЗДП:

1) неделимость некоторых р-рсов(здания, машины)

2) логические отношения и связи

3) з-чи не яв-ся дискретными, но сводятся к ним.

Имеется 3 основных метода реш-ия ЗДП:

1. отсечение

2. комбинаторные методы

3 приближенные методы.

Задачи матем программир-я (ОПТИМИЗАЦИИ. программ)

Задача оптим. яв-ся одним из важнейших задач экон. и управ пр-вом,процессов и т.д. Решение задачи оптимизации может разбиться на 3 этапа:

1) построение матем. модели;

2) нахождение оптим решения одним из метод матем программ.

3) практическ. использ-е результата решения.

Оптимизация - целенаправленное деят-ность запл- щийся в получение наилучщих результатов при соответст условиях. На языке матиматики целевой ф-ции наилучщие результаты нахождения max и min.

Управление – принятие решения о наиболее целесообразных действиях. Решение сложных соц- эк задач м-дами систем анализа в конечн. счете сводится к решению некоторой задачи оптимизации. В общем случае з-ча матем. прогр-ия: max(min) ( (x)) i=

ЗНП и методы его решения

имеется з-ча

max(min)

{

если хотя бы одна из ф-ий яв-ся нелин, то з-ча наз-ся ЗНП.

Для решения з-чи НП не сущ-ет станд. методов реш-ия. Выбор метода решения зависит от содержания з-чи и опыта исследователя.М-д ЗНП может быть охарактеризована как многошаговые или как методы послед-го улучшения исходного решения.

= , где к- номер шага итерации,

,это шаг. к=0,1,2,3,4

Начальное значение задается или выбирается. все сводится к нахождению . Условие остановки

задан. точность решения задачи.

При решение задачи возникает 2 трудности:

1) выбор подходящих начальных значений

2) глобальный экстремум

Эффективность методов ЗНП опред-ся след св-ми:

- точность в поисках

-надежность метода

- скорость сходимости (к)

Условные и безусловные ЗНП

Если в системе или в уравнении отсутствует ограничения, то задача наз-ся з-чей безусловной оптимизации.

Безусловная задача решается легче,чем условная з-ча, поэтому наряду с прямым методом решения услов задач часто применяется метод преобразования условных задач в бузуслов оптимизации, путем введения штрафных ф-ций.

метод – преобразования

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

сущность метода: объект исследования и анализа не сама ц.ф., а некоторая другая функция Ψ(L), образуемая в результате преображения ф. f()

если ц.ф.. f() является измеримой определенной на некотором множестве Е’ R’’ пространства и не терпящий симметричн. разрыва 1-ого рода, то является монотонно убывающей и ноль этой функции соотвествует значению max ц.ф. f()

 

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

=f + - безусловная задача оптимизации

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

В кач-ве штраф. ф-ии можно взять функцию

, и если это условие не выполняется.Поэтому если все условия выполняются, то min совпадает, а если не вып-ся, то добав шт ф-ций.

Алгоритм решения задачи min f , с использов шт ф-ций.

1) выбир нач точку ,в данной точке )>0,

2) при k=1,2,3,..., начиная с точки ) решается задача безусловной оптимизации, в результате определяется очередная точка )

) и т. д. процесс повторяется.

Если на каждом шаге алгоритма удается найти глобальн min ф-цию ) по x, то последовательность ) сойдется к глобальн min-му ф-ции f при

Обычно выбирают:

/ причем q>1- const, =[50;100]

примечание. Если решается max(min)

{ аналогич. образом строятся шт. ф-ции, причем по отдельности для условий типа равенства и неравенства.