Понятие выпуклого прогр-я, геом. прогр-я, сепарабильного прогр-я

для решения задач инженерного характера, когда ц.ф. и ограничени япредставлены в в иде положит. полиномов:

(x) = (

min (x)

(x)<=1, k=

aj – веществен. число

cj>0 положит. Число

Метод сепарабильного прогр-я

ф-ция f() явл. пепарабильной, если ее можно представить в виде:

 

f() =

если ц.ф. ограничена сепарабильно, то эта задача сепарабильного программирования.

 

>=

метод выпуклого программирования

функция f() наз-ся выпуклой в некоторой области, если для любых 2 точек и этой области вып-ся условие:

 

f(θ + (1-θ ) θ f()+ (1-θ) f()

 

0≤θ≤1 - сепарабильная величина

в общем случае выпуклость опр-ся след образом:

1 – выпукл

2-вогнут

множество точек наз-ся выпуклым, если отрезок линии, соединяющий 2 произвольные точки множества, целиком лежит в этом множестве.

max (min) f() (1)

, j= (2)

 

– выпукл. ф-ция, f() - вып. или вогнут. ф-ция

тогда задача 1,2 наз-ся задачей выпукл. програм-я

локальный экстремум ЗЛП явл. глобальн. экстремум, т.е. если вы нашли локальн. экстремум, то не надо дальше искать.

 

 

Решение ЗЛП. Симплек метод реш ЗЛП

Ограничения ЗЛП образуют некоторую общую часть N- мерного пространства, кот наз-ся многогранником решений. Если линейн ф-ция f(x) достиг своей мин значения, то она достигается в угловой точки многогранника решений.

Любое решение , - наз-ся допуст решением. Допустимое решение r m, наз-ся базисным решением. Баз. решение кот достигает min целев. ф-ии f(x) наз-ся оптимальн решением, кот требуется найти. для решения прим-ся граф. и симплексный метод. n=2, m=3 n-m=1

Симплек метод реш ЗЛП

Универсальным методом реш ЗЛП явл=ся симплекс метод, кот непосредственно примен-ся. Баз решение опред. координаты вершин многогранника реш=ий и из них необход найти ту вершину, кот доставляет min целев ф-ии f(x).

При больших числах ограничения n и числа неизвестных m найти оптимальное решение трудно. Max яисло переборов будет , поэтому необходимо иметь схему, позволяющую исходя из известного баз реш-я найти оптимальное решение. Такой схемой яв-ся симплек метод.

2 этапа:

1. нахождение первоначальн баз реш

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

Переменные:

-базисные r

- небазисные, применяются равными 0.

Каждый шаг приближает к min

Обычно ЗЛП решается в ручную с помощью симплекс таб.

Иногда вместо исходной ЗЛП выгоднее решать другую задачу, называемую двойственной, когда число ограничений гораздо больше число значений.