Метод множ Ланг-жа реш задач НП.Эк смысл множ Ланг-жа

Рассм частный случай общ.з-чи

max(min)F=f (x_1, x_2,…, x_n)

φ_i (x_1, x_2,…, x_n)=b_{i, i=1,m}

для того,ч.найти ее реш-е сост-ем ф-цию Ланг-жа,безусловный экстр-м кот.совпад. с условным экстр-ом

L(x_1, x_2,…, x_n,λ_1, λ_2,…, λ_n )= f (x_1, x_2,…, x_n)+ (b_i- φ_i (x_1, x_2,…, x_n))

Для эт.ф-ции запи-ем необх-е усл-е экстр-ма

Решив посл-юю сист.,мы найдем все критич.точки,в кот.ф-ция может иметь экстремум знач-я. Затем с пом.достат.усл-й определяем точки экстремума ф-ции.

Алгоритм:1)сост-ем ф-цию Ланг-жа,2)нах-им част-е произв-е ф-ции Л-жа по всем перем-м и при=ваем их к0,3)реш-в сист.ур-ний,найдем стационар-е точки,т.е.точки,в кот.ЦФ мож.иметь экстр-м,4)среди стацион-х точек с примен-ем достат.усл-й нах-им те,в кот.ф-ция имеет экстср-мы

Экон.сод-ние множ-лей Л-жа λ_i:рассм-м прост-шую з-чу оптим-ции

max(min)F=f (x_1, x₂)

φ_i (x_1, x₂)=b.Предпол-м,что экстр-м достиг-ся в как.-то точке Х^*=(x₁^*_, x₂^*), F^*=f(x₁^*_, x₂^*).пусть координаты x₁^*_и x₂^*,а значит и F^*от знач-й прав.части b

x₁^*₌x₁^*(b), x₂^*₌x₂^*(b), F^*=f(x₁^*(b)_, x₂^*(b)).Найдем част.произв-еЦФ по x₁ и x₂ в завис-ти от b

(1)из осн-х огран-й след-т,что част.произв-я ф-ции φ

=1(2)в экстр-й точке вып-ся необх.усл-е экстр-ма и (3).Подставим в 1-ую 3,испол-я2 .для з-ч,у кот.кол-во огран-й=m,т.будет спрвед-ва ф-ла ,i=1,m

14. Общая идея симп.метода решения зад ЛППри графическом методе решения задач ЛП мы фактически из множества вершин, принадлежащих границе множества решений системы неравенств, выбрали такую вершину, в которой значение целевой функции достигало максимума (минимума). В случае двух переменных этот метод совершенно нагляден и позволяет быстро находить решение задачи.

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

По определенному правилу находится первоначальный опорный план (некоторая вершина области ограничений). Проверяется, является ли план оптимальным. Если да, то задача решена. Если нет, то переходим к другому улучшенному плану - к другой вершине. значение целевой функции на этом плане (в этой вершине) заведомо лучше, чем в предыдущей. Алгоритм перехода осуществляется с помощью некоторого вычислительного шага, который удобно записывать в виде таблиц, называемых симплекс-таблицами. Так как вершин конечное число, то за конечное число шагов мы приходим к оптимальному решению.

48.Задача замены оборудования.

Пусть в нач. планового периода продолж. Тлет имеется оборудование возраста t.Произв-ся продукция стоим-тью(t),u(t)-эксплуат-ые затр-ы,s(t)-остат.ст-ть в любое время оборуд.Можно купить,сохр-ть или продать новое по ценеP. (t)-макс. Прибыль за kлет. Необх. рассм-ть процесс оптимизац. с конца планового периода в этой задаче.Сис-му составл. оборуд. Вектор управления-это решен. В момент t=0,1,2….T,о сохр. Или замене оборуд. Необходимо проан-ть процесс от конца к нач. Пусть k=1,t-возраст оборуд.

Имеем 2 возм-ти:1)сохр-ть оборуд.,тогда прибыль за посл. Год=r(t)-u(t).2)Продать оборуд.:прибыль=s(t)-p+r(0)-u(0).Решение о замене оборуд.возраста t следует принять,когда прибыль от нового оборуд. На посл. Периоде больше,чем от старого,т.е: s(t)-p+r(0)-u(0)>r(t)-u(t),то замена. Если s(t)-p+r(0)-u(0)<=r(t)-u(t),то сохр. Старое.

Общее функцион. Ур-ие:

(t)=max(t)-u(t)+ (t+1),сохр-е

s(t)-p+r(0)-u(0)+ (1),замена.