17 Классификация чм.

ЧМ условно разбиваются на: 1)методы нулевого уровня(не требуют производных функций участвующих задач);

2)методы первого уровня (требуют использования производных функций 1-го порядка);

3)методы 2-го уровня (требуют использования производных функций 2-го и более высоких уровней).

М.б. также разбиты на классы,соответствующие определенным разделам математики.

15. 3-я теорема двойственности. Экономическая интерпретация двойственных оценок

3-я теорема двойственности

Пусть f٭=f(x٭)- оптим-ое значение целевой ф-ии прямой ЗЛП, тогда двойственные оценки удовлетворяют соотношению y*i=df٭/db_i, i=1,m, где b_i – компоненты вектора В в правой части огр-ий прямой задачи Ax ≤ b.

Замечание: двойственные оценки играют в линейном прогр-ии ту же роль, что и мн-ли Лагранжа в нелинейном прогр-ии.

Экономическая интерпретация двойственных оценок.

Согласно 1-й теореме двойственности значения целевой ф-ции задач двойств. пары равны на оптимальных планах равны между собой:

Σj₌₁ⁿcjx*j = c^тx= f(x*) = g(y*) = b^ту* =Σi₌₁^mb_iy*i

Пусть целевая ф-ция f(x) в прямой ЗЛП выражает прибыль ($), а величины b_i,стоящие в правой части орг-ий Ax ≤ b прямой задачи опр-ют кол-во ресурса i-го вида в у.е.. Тогда y* должны содержать компоненты, выраженные в $ на единицу ресурса, т.е. двойственные оценки y*_I играют роль цены и наз-ся теневыми ценами.

16. Понятие алгоритма в численных методах математического программирования. Понятия к-го приближения, итерации, сходимости, критерия останова

ЧМ наз. методы решения задач прикладной мат-ки с пом ЭВМ.

Алгоритмом метода наз.произвольная процедура, порождающая послед-ть точек х^→(0),х^→(1),…,х^→(к) ,… (приближения к истинному решению х^→*) в соотв.с приписанным набором правил.

Преобразования к-го приближения х^→(к) в х^→(к+1) представ. собой к-тую итерацию алгоритма. Итерация на каждом шаге реализ-ся заранее заданным порядком действий.

Алгоритм наз.сходящимся на мн-ве S ,если при произвольном начальном приближении х^→(0) из предел посл-ти приближений, порождаемых алгоритмом = истинному решению. lim_к→∞ х^→(к)=х^→*.

Остановка алгоритма происходит, как только выполняется критерий Останова,задаваемый перед началом запуска алгоритма. Критерии Останова различаются в зависимости от исходных задач. Самым главным фактором, определяющим этот критерий явл.степень близости текущего приближения к истинному решению задачи.

18 Метод наискорейшего спуска (подъема).

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

Шаг 0:выбир-ся точка начального приближения х^→(0), длина шага λ(λ>0 – max, λ<0 – min), точность решения ε>0. Выбирается целое число к>1 – параметр дробления шага.

Шаг к: (а) делается пересчет очередного приближения по формуле: х^→(к)={х^→(к-1)-λ*▼f(х^→(к-1)),если имеется min,

{ х^→(к-1)+λ*▼f(х^→(к-1)), если имеется max

(б) проверяется, прошел ли переход черезточку экстремума:

F(х^→(к))>(<) f(x^→(k-1)), при поиске min(max)

Если эти условия выполнились, то длина шага уменьшается в к раз: λ:= λ/к

(в) Если зафиксирован хотя бы один переход ч/з экстремум, проверяется критерий Останова: |х^→(к)-х^→(к-1)|<ε. Если кр.вып-ся, то алгоритм заканчивает свою работу и в кач-ве решения берется последнее приближение х^→(к)