Необходимое и достаточное условие выпуклости
По матрице гесса H(x) >0 <0
Особенности ЗВП
Алгоритм:
1) рисуем
2) проверяем на вып/вогнутость
3) нах стац точки
4) входит точка в область, если до, то она мин/мах в зависимости от типа функции (по дано че искали)
ДЗ
Для проведения косвенного пост-оптимизационного анализа
Решение ДЗ показывает, каким образом наиболее выгодно изменить знач переменных, которые были известны при решении ИЗ.
Свойства ДЗ:
1. Число переменных ИЗ = числу огр ДЗ.
2. Число огрИЗ = числу переменных ДЗ
3. Если в ИЗ находится maxF, то в ДЗ minF, и наоборот
4. Если в ИЗ ограничения типа <, то в д ДЗ >
5. Коэффициенты при переменных в F ИЗ явл константами в правой части огр ДЗ.
6. Коэффициенты огр исходной являются константами в правой части ДЗ
7. В ИЗ в качестве переменных используется матрица А, в двойственной - Ат
8. Задачи являются взаимодвойственными
Связь между решениями ИЗ и ДЗ
Теорема 1. Основное нерав-во теории двойств. Для любых допустимых решений х и у справедливо: F(x) <=G(y)
Теорема 2. Если F(x*) =G(y*), то x* - оптимальнн реш ИЗ ; y* оптимальнн реш ДЗ.
Теорема 3. Основное равенство ТД. Если одна из двойственных задач имеет оптимальное реш, то
F(x*) =G(y*) его имеет и другая.
Св-во 4. Соответствие между переменными.
Теорема 5. Значение БП в оптимальном решении ДЗ = абсолютн знач коэф при перемен F опт реш ИЗ
Целевая функция(двойственная задача)-это доход, который получит производитель, если продаст по теневой цене всё сырье.
Теневые цены характеризуют ценность сырья для производителя. Чем теневая цена больше, тем дефицитней ресурс. Теневая цена показывает насколько увеличится пропущено при увеличении запаса i-го сырья на 1 ед. Выгоднее в первую очередь увеличивать запас ресурса у которого теневая цена больше.
F в двойственной задаче - доход, который получит производитель, если продаст по теневым ценам все имеющееся сырье. С другой стороны, F можно рассматривать как издержки покупателя сырья, которые надо min, принимая во внимание интересы производителя сырья.
Решение ДЗ позволяет продавцу определить нижние границы цен на сырье, которые он может назначить, чтобы прибыль от их продажи была не меньше, чем от производства товаров из этого сырья.
Теневая цена – переменные ДЗ yi цены, которые устанавливает продавец сырья на i-ый ресурс.
Исследование операций - наука об исследовании наиболее рациональных решений при проведении целенаправленных действий.
Операция - любое управляемое мероприятие, направленное на достижение цели. Результат проведения операции всегда зависит от способа ее проведения (от выбора параметров). Решение задач - определенный набор параметров.
Оптимальное решение - то решение, которое по тем или иным соображениям предпочтительней другим. Основная задача - предварительное количественное обоснование оптимальных решений.
КЗМП (классическая задача)
Мах(мин)F(х) в условных огр: g(x)=bi огр< перемен
n-m это число степеней свободы решаемой задачи.
Особенности КЗП
1. все орг =
2. нет условия неотриц перемен
3. переменные, функции и огр – непрерывные.
4. Функции F(x) и Gi (x) непрерывны и имеют частные производные по крайней мере второго порядка.
Методика решения КЗП
м=0 тогда безусловная оптимизация
m>0 задача условной оптимизации
Метод "ветвей и границ"
Основная идея - множество допустимых решений некоторым способом разбивается на подмножества, каждый из которого оценивается с точки зрения перспективности получения оптимального решения. Наиболее перспективное подмножество далее в свою очередь разбивается до получения оптимального решения.
Многокретериальные задачи
R- мн-во всех реш задачи. ri векторная функция, с помощью кот можно оцуенить каждый вариант реш.
Требуется найти наилучший вариант r* учитывая все критерию
Свертка критерия – попытка с помощью опр алгоритма свести мн-во критериев к одному – привести задачу к однокритериальной задачи.
Метод свертки критерия плохо работает при различной размерности критериев. Поэтому используют метод смещенного идеала.
1. по каждому притерию выбираем наилучший и худший
2. относительное расстояние до лучшего (идеального) dji = (f+ - fi )/ (f+ - f-)
3. находим относительное расстояние до наихудшего : 1-d
4. вводится понятие значимости (веса wi)
5. интегральное расстояние до наихудшего Li^p=p√∑(w(1-d))^p
p- параметр, опр правильность вычисл расстояния, р=1, р=2, (степень концентрации)
НЛП
Особенности ЗНЛП:
1. Функции F(x1 ...xn) и Gi (x1 ...xn) в общем случае нелинейны
2. m и n не связаны никакими ограничениями
3. все ограничения в виде неравенств. Если в системе ограничений есть ограничения типа равенство,тоего переводят в неравенство.
4. нет обязательного условия неотрицательности переменных
5. КЗМП может рассматриваться как частный случай ЗНЛП
Простейший алгоритм решенияЗНЛП
Экстремум сожжет быть внутри области и на ее границах
Алгоритм:
1) нах стац точки без условия огр: dF/dxi = 0 проверяем, входят ди эти точки в область, если да, то F/M1
2) нах стац точки в области: g(x)=bi или выражаем переменную через др, или методом лагранжа.
Проверяем удовлетв система огр
Если попадает в область или на границу выычиляем F/M2
3) нах стац точки на пересеч границ : (5;0) (0;5)
4) выбираем F/M – наиб и F/M - наим
Оптимальное решение - то решение, которое по тем или иным соображениям предпочтительней другим. Основная задача - предварительное количественное обоснование оптимальных решений.
Свободные и базисные переменные.
любые m переменных системы m уравнений с n переменными (m<n) называются основными (базисными, если опредедитель матрицы уоэффициентов при них отличен от нуля. Тогда отальные n-m переменных называются неосновными (свободными).
Свойства решений ЗЛП.
1. Допустимое множество решений задач ЛП представляет собою выпуклое множество
(мн-во выпуклое, если оно с двумя своими точками содержит весь отрезок, соединяющий эти точки).
2.Каждое огр можно поставить в соответствие переменную, которая на этом огр обращается в 0.
3. Пусть задача ЛП задана в канонической форме (равенства), имеет n переменных на m ограничений. Тогда если с помощью эквивалентных преобразований выделить m переменных и оставить их в левой части равенств, а остальные n-m переменных перенесем в правую часть, то получим выражение: xi = βi-∑ о€S αij*xj , где xi - базисные, xj - свободные, β-множество индекси базесных переменных
множество индексов базисных переменных, S - множество индексов свободных переменных.
Если xJ=0, тогда xi=βi и βi≥0, i € B, i € S , тогда решение называется базисным.
4. Основное свойство базисного решения - оно представляет собою вершину допустимого множества M.
5. Оптимальное решение находится в вершине многогранной области допустимых значений. Иногда множество оптимальных решений может находится на i-ой плоскости.
6. Если перебрав все комбинации свободных переменных не удалось найти базисное решение, значит, система ограничений несовместна.
Путь к решению любой задачи ЛП - набор конечного числа допустимых базисных решений и выбор среди них того, на котором F принимает свое max или min значение.
Симплекс-метод:
Осн идея: перебор БР производится с учетом изменения знач F(х).
Целенаправленный пербор вершин многогранной выпуклой области, при кот знач F(х) монотонно стремится к своему экстремуму (мах/мин).
Схема решения симплекс-метода.
Необходим канонический (=) вид! Решаем задачу на мин!
1. Построение первоначального базисного решения
2. Переход к лучшему или хотя бы не худшему решению
3. Проверка оптимальности найденного решения
ТЗ
Пусть имеется А1_ An поставщиков однородной продукции. Известны запасы на складах у этих поставщиков (а1.. .am ед.). Имеется B1.Bn потребителей этой продукции. Известен спрос каждого потебителя (b1.bn). Известна стоимость (или время перевозки в некоторых задачах) одной ед. продукции от i-го поставщика к j-му потребителю (cij). Необходимо найти такой план переменных, чтобы их суммарная стоимость (время) была min.
Закрытая и открытая ТЗ.
Условием разрешения ТЗ является равенство общего количества продукции у поставщиков и общего спроса у потребителя.
Если равенство выполнено, то такая ТЗ-называется закрытой.
Если не равно, то открытой. Для существования задачи необходимо и достаточно, чтобы ТЗ была закрытой.
Методы решения ТЗ
1. Точные методы - гарантируют оптимальное решение, но требуют больших временных затрат.
а. Венгерский метод
б. Метод потенциалов
2. Методы построения допустимого решения - находят на оптимальное решение, но быстро.
а. Метод "северо-западного угла" - не учитывает стоимость перевозки, поэтому решение не оптимально.
б. Метод "минимального элемента" - учитывает стоимость перевозок только на текущем шаге, поэтому в общем случае полученное решение лучше решения "С-З угла", но все равно не оптимально.
Условная оптимизация
Нахождение экстремума при наличии огр
1 способ. Если можно однозначно выразить переменную через другие.
1) выражаем переменную
2) подставляем в функцию
3) ищем производную по функции 1ой переменной и приравниваем произвдную =0
Находим точку и - стационарная точка
Проверяем на плоскости по 2ой производной в этой точки, подставляя в функцию
5) Fmaх= ; х*( ; )