Классификация задач и методов математического программирования.

I. задачи могут отличаться по виду целевой функции:

- линейная (все переменные в 1ой степени);

- квадратичная

- мультипликативная: F=a0 * x1^α * x2^β (куба-дугласа)

-селарабельная (целевая функция: сумма различных функций): F=∑fi(xi), i=1,n

II. по виду целевой функции и одновременно по виду функций, входящих в систему, ограничений.

- ЗЛП: F(x) и gi(x) j=1,m g-система ограничений;

- ЗНЛП: хотя бы одна из функций F(x) лии gi(x) – нелинейная;

- задачи целочисленного программирования: xi, i=1,n должна принимать ток целые значения;

- классич задачи мат программирования: F(x) и gi(x) j=1,m - непрерывно дифференцируемые функции.

Математическое программирование- это область математики, разрабатывающая теорию и численные методы решения многомерных и экстимальных задач с ограничениями. Нахождение max и min ф-ции многих переменных с ограничениями на области изменения этих переменных.

Целевая функция – это множество точек, для которых значение целевой функции F(x)=const,задавая различные значения const, получим различные линии уровня.

Алгоритм Гомори (целочисл)

1. Решаем задачу симплекс-методом без условия целочисленности

2. Если среди xj , где jeS есть не целые числа, то выбирают переменную xj с наибольшей целой частью и строят дополнительное ограничение:

βi - ∑[αij]xj ≥0 jeS

3. Полученное неравенство приводится к виду равенства путем введения дополнительных неотрицательных переменных — βi - ∑αIJXJ— xn+1 = 0 jeS Xn+1=-βi-∑αijxj jeS

Полученная задача с новой системой ограничений решается симплекс-методом.

Если задача разрешима в целых числах, то оптимальное решение находится после конечного числа шагов. Если в процессе решения на 3) шаге появляется уравнение с нецелым свободным членом β1 и целым остаточным коэффициентом αij, то данная задача не имеет решения в целых числах

Алгоритм Лэнд и Дойг.

[1]Решается задача ЛП без учета целочисленности (З0). Пусть решение З0: x , F( x )

2. Если x целочислено, то задача решена. Иначе, пусть x*i - нецелочисленна, тогда x*e = [x*e ]+ xe Образуем 2 новые задачи (З11, З12).

З11: к ограничениям З0 добавляется ограничение xl < [x*e]

З12: к ограничениям З0 добавляется ограничение xl > [x*e] +1

3. Решаем задачи З11 и З12 без учета целочисленности . Если решение целочислено, то выбираем решение с наилучшим значением целевой функции.

Если решение нецелочисленно, то выбираем задачу с наилучшим значением целевой функции и образуем 2 новые задачи т.д.

Базисное решение.

Решение системы ограничений при нулевых значениях свободных переменных называется базисным.

1. xi = βi-∑ о€S αij*xj , где xi - базисные, xj - свободные, β-множество индекси базесных переменных множество индексов базисных переменных, S - множество индексов свободных переменных.

Если xJ=0, тогда xii и βi≥0, i € B, i € S , тогда решение называется базисным.

Свойства:

1. В пространстве базисному решению соответствует вершина допустимой области.

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

3. В базисном решении свободные переменные равны нулю.

4. Неположительность всех коэффициентов при свободных переменных является признаком оптимального базисного решения.

Безусловная оптимизация

Нахождение экстремума при отсутствии огр

n=1необходимое условие сущ экстремума: первая производная =0 или не сущ

вторая произв >0 тогда мин, <0 мах

n>1необходимое условие сущ экстремума : dF/dxi = 0 в т. х*

достаточное условие сущ экстремума: H(х) >0 х*-мин H(х) <0 х*-мах

критерий Сильвестра

Вектор-градиент - вектор, в направлении которого функция возрастает с наибольшей скоростью

Геометрический метод

Условие:

количество переменных равно 2

1. Строим область допустимых значений варьируемых переменных

2. Строим линии уровня (типа градиенты) для целевой функции

3. Определяем в какую сторону F возрастает (убывает)

4. Точка (прямая), в которой линия уровня выходит из допустимой

Линия уровня - множество точек, для которых F(x)=const. Задавая различные const получаем различные линии уровня.

Выпуклое программиров (ВП) - частный случай ЗНП. Выделение ЗВП в отдельный класс связано с тем, что если F является строго выпуклой (вогнутой), и допустимое множество решений не являетя пустым и ограничена, то ЗВП всегда имеет единственное решение: min выпуклой функции достигается либо внутри области решения, если там имеется стационарная точка или на границе, или стационарной точки нет.

Мн-во выпукло, если для любых 2х точек x1 x2 принадлежащ этому множество справедливо:

x= λ x1 + (1-λ)x2 и это тоже принадлежит мн-ву. 0<=λ<=1

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

F(x) выпукло на выпуклом мн-ве, если для любых 2х точек х1 х2 справедливо:

F( λ x1 + (1-λ)x2 )<= λ F(x1) + (1-λ)F(x2) 0<=λ<=1

F строго выпукла, Если неравенство строгое

Наши рекомендации