22.Основное неравенство теории двойственности и его экон. Содерж.

Рассмотрим пару симметричных двойственных задач

maxF=∑c_jx_j

∑a_ijx_j≤b_i,i=1,m; i=1,m (1)

x_j≥0,j=1,n

minϕ=∑b_iy_i, i=1,m

∑a_ijy_j≥c_j, j=1,n; (2)

y_i≥0, i=1,m

Теорема. Для любых допустимых планов Х=(х₁,х₂,…,х_n) и Y=(y₁,y₂,…,y_m) прямой и дв-ной задач ЛП справедливо неравенство

F(X)≤ϕ(Y), т.е.

∑c_jx_j≤∑b_iy_i (3)

Доказательство:учитывая неравенства 1 и 2, получаем:

F(X)=∑c_jx_j(j=1,n)≤∑(j=1,n)(∑a_ijy_i(i=1,m))x_j=∑(i=1,m)y_i∑(j=1,n)a_ijx_j≤∑(i=1,m)b_iy_i=ϕ(Y)

Эк-ое содержание теоремы: для любого допустимого плана производства Х и любого допустимого вектора оценок ресурсов У общая созданная стоимость не превосходит суммарной оценки ресурсов.

23.Критерий оптимальности Канторовича

Теорема. Если для некоторых допустимых планов Х^* и У^* пары дв-ных задач выполняется равенство F(X^*)=ϕ(Y^*),то Х^* и У*- оптимальные планы соответственно.

Доказательство: согласно осн-му неравенству теорем дв-ти для любого допустимого плана Х прямой задачи и любого допустимого плана У* дв-ной задачи выполняется неравенство F(X)≤ϕ(Y*). Но по условию теоремы F(X^*)=ϕ(Y^*). Отсюда в силу транзитивности отношений «≤» и (=) имеем F(X)≤F(X*),но т.к. Х-произвольный допустимый план, то тогда F(X*)=maxF.Значит, Х*-оптим. план прямой задачи ЛП. Аналогично доказывается, что У* явл-ся оптимальным для дв-ной задачи.

Эк. содержание: план производства Х* и вектор оценок ресурсов У* явл-ся оптимальными, если цена всей произведенной продукции и суммарная оценка ресурсов совпадает.

25. теор о доп-ей нежесткости и ее эк сод-ие. Теорема: для того, чтобы планы Х*, У* пары двойст-х задач были оптим-ми необх и достат вып-ие след-х усл-ий: х_j*(∑а_ijy_i*- с_j)=0, j=1,n (1),y_i*(∑а_ijx_i*- b_i)=0, i=1,m(2). Док-во: необход-ть махF =∑c_jx_j, ∑а_ijx_i*= b_i, i=1,m, x_j≥0, j=1,n.(3) minφ= ∑b_iy_i∑а_ijy_i* ≥с_j, j=1,n y_i≥0, i=1,m. F (X*)=φ(Y*)т.е∑c_jx_j,*= ∑b_iy_i*(4). Подставим в 4 b_iиз 3: ∑c_jx_j,*=(∑а_ijx_i*) y_i*= ∑х_j*∑а_ijy_i*→ ∑х_j*(∑а_ijy_i*- с_j)=0 (5). Т.к х_j*≥0, и ∑а_ijy_i*- с_j ≥0, j=1,n. След-но из рав-ва 5 след-т условие 1, усл 2 док-ся аналогично. Достат-ть: ∑х_j*(∑а_ijy_i*- с_j)= ∑х_j*∑а_ijy_i*-∑c_jx_j,*= ∑y_i*∑а_ijx_i* - ∑c_jx_j,*= ∑b_iy_i*- ∑c_jx_j,*→ F (X*)=φ(Y*). Эк содерж: Двойствоценки могут служ мерой дефицитности ресурсов (ДР).ДР, т.е ресурс по опт-му плану пр-ва исп-ся полностью имеет полож-ю оценку, а избыт-й имеет нулевую оценку.

26.Теорема об оценках.Теорема: двойств-е оценки показ-ют приращение ЦФ, вызванное измен-ем св. члена соотв. ограни. ∂F(X*)/∂b_i=y*, i=1,m. (1). Док-во: Рассм. задачу вида:maxF=f(X)(2), ϕi=bi,(i=1,m)(3).перейдём от задачи на условн. экстремум к зад. на безусл. экстрем. Для этого построим вспом. функц. Лагранжа(фЛ): L(X,Y)=f(X)+∑(m,i=1)yi(bi-ϕi(X))(4), где yi непред. множит. лагранжа. запишем необходимые условия экстремума фЛ для этого ищем часные производные фЛ по xiиyi, приравнив. к 0: покажем что всякое экстр. значение задачи(2,3) удовл. услов. (5,6) Пусть Х*-допустим. план, доставляющий ЦФ экстр. значение, то , i=1,m, и услов. 6 выполняются, след-но из фЛ следует: L(X*,Y*)=f(F*), откуда ,выполн. условие 5.Каждая доп. точка Х* д\б решением системы,это необход. условие для отыск. экстр.Пусть своб члены сист. огран.(3) измен. в некот. пределах, следов-но будет меняться и ЦФ. обозначим коорд. крайних точек через:x1(B)=x1(b1,b2,…,bm), x2(B)=x2(b1,b2,…,bm),…, xn(B)=xn(b1,b2,…,bm). рассм. фЛ, как функц. завис-щую от В: L(B)=f(X(b))+∑(m,i=1)yi(bi-ϕi(X(B))) (7).дифференцируя фЛ по biполучим: (8) учитывая (5 и 6) из равенства (8) Но для ОП L(X*,Y*)=f(X*),следовательно Эк. содерж-е: для этого в выраж-ии (1) дифференциалы заменим приращениями, т.е. ∂b_i≈∆b_i, ∂z(x*)≈∆z(x*). Получим ∆z(x*)=у_i*∆b_i; при ∆b_i=1 имеем ∆z(x*)≈y_i*. Отсюда двойств оценка числ-но равна измен-ю ЦФ при измен-ии соотв. своб. члена ограничений на ед.