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

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. Если среди x_j, где jeS есть не целые числа, то выбирают переменную x_j с наибольшей целой частью и строят дополнительное ограничение:

β_i - ∑[α_ij]x_j ≥0 jeS

3. Полученное неравенство приводится к виду равенства путем введения дополнительных неотрицательных переменных — β_i - ∑α_IJX_J— x_n+₁ = 0 jeS X_n+1=-β_i-∑α_ijx_j jeS

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

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

 

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

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

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

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

З₁₂: к ограничениям З₀ добавляется ограничение x_l > [x*e] +1

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

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

 

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

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

1. x_i = β_i-∑ _о€S α_ij*x_j, где x_i - базисные, xj - свободные, β-множество индекси базесных переменных множество индексов базисных переменных, S - множество индексов свободных переменных.

Если x_J=0, тогда x_i=β_i и β_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 строго выпукла, Если неравенство строгое