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