資源描述：
《對偶問題及對偶單純形法完整》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、DualityTheory線性規(guī)劃的對偶問題對偶問題的經(jīng)濟(jì)解釋——影子價格對偶單純形法第四章線性規(guī)劃的對偶理論靈敏度分析對偶問題的基本性質(zhì)線性規(guī)劃的對偶問題DualityTheory對偶問題的經(jīng)濟(jì)解釋——影子價格對偶單純形法靈敏度分析對偶問題的基本性質(zhì)第四章線性規(guī)劃的對偶理論例如：平面中矩形的面積與周長的關(guān)系周長一定面積最大的矩形是正方形:面積一定周長最短的矩形是正方形一、對偶問題的提出對同一問題從不同角度考慮，有兩種對立的描述。例1、應(yīng)如何安排生產(chǎn)計(jì)劃，使一天的總利潤最大？某企業(yè)生產(chǎn)甲、乙兩種產(chǎn)品，要用A、B、C三種不同的原料。每生產(chǎn)1噸甲產(chǎn)品，需耗用三種原料分
2、別為1，1，0單位；生產(chǎn)1噸乙產(chǎn)品，需耗用三種原料分別為1，2，1單位。每天原料供應(yīng)的能力分別為6，8，3單位。又知道每生產(chǎn)1噸甲產(chǎn)品企業(yè)利潤為300元，每生產(chǎn)1噸乙產(chǎn)品企業(yè)利潤為400元。例1、應(yīng)如何安排生產(chǎn)計(jì)劃，使一天的總利潤最大？maxx1≥0,x2≥0s.t.x1+x2≤6z=3x1+4x2x1+2x2≤8x2≤3設(shè)xj表示第j種產(chǎn)品每天的產(chǎn)量假設(shè)該企業(yè)決策者決定不生產(chǎn)甲、乙產(chǎn)品，而是將廠里的現(xiàn)有資源外售。決策者應(yīng)怎樣制定每種資源的收費(fèi)標(biāo)準(zhǔn)才合理？例1、應(yīng)怎樣制定收費(fèi)標(biāo)準(zhǔn)才合理？設(shè)yj表示第j種原料的收費(fèi)單價分析問題：1、出讓每種資源的收入不能低于自己生產(chǎn)
3、時的可獲利潤；2、定價不能太高，要使對方能夠接受。把生產(chǎn)一噸甲產(chǎn)品所用的原料出讓，所得凈收入應(yīng)不低于生產(chǎn)一噸甲產(chǎn)品的利潤：乙產(chǎn)品同理：把企業(yè)所有原料出讓的總收入：只能在滿足≥所有產(chǎn)品的利潤的條件下,其總收入盡可能少,才能成交.s.t.一、對偶問題的提出任何一個求極大的線性規(guī)劃問題都有一個求極小的線性規(guī)劃問題與之對應(yīng)，反之亦然.把其中一個叫原問題，則另一個就叫做它的對偶問題，這一對互相聯(lián)系的兩個問題就稱為一對對偶問題。s.t.LP1s.t.LP2原問題（P）對偶問題（D）二、原問題與對偶問題的對應(yīng)關(guān)系s.t.Ps.t.Dyj表示對第j種資源的估價矩陣形式：s.t.s
4、.t.maxz=CXs.t.AX≤bX≥0minw=bTYs.t.ATY≥CTY≥0(一)對稱型對偶問題其中yi≥0（i=1,2,…,m）稱為對偶變量。變量均具有非負(fù)約束，且約束條件：當(dāng)目標(biāo)函數(shù)求極大時均取“≤”號，當(dāng)目標(biāo)函數(shù)求極小時均取“≥”號。maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2(P)……am1x1+am2x2+…+amnxn≤bmxj≥0（j=1,2,…,n）minw=b1y1+b2y2+…+bmyms.t.a11y1+a21y2+…+am1ym≥c1a12
5、y1+a22y2+…+am2ym≥c2(D)……a1ny1+a2ny2+…+amnym≥cnyi≥0（i=1,2,…,m）maxz=CXs.t.AX≤bX≥0minw=bTYs.t.ATY≥CTY≥0(二)非對稱型對偶問題分析：化為對稱形式。maxx1≥0,x2≤0,x3無約束s.t.a11x1+a12x2+a13x3≤b1z=c1x1+c2x2+c3x3a31x1+a32x2+a33x3≥b3a21x1+a22x2+a23x3=b2令maxs.t.(二)非對稱型對偶問題maxs.t.對偶變量mins.t.對偶問題：(二)非對稱型對偶問題mins.t.令mins.
6、t.mins.t.3個≥≤=約束條件變量(二)非對稱型對偶問題mins.t.原問題對偶問題目標(biāo)函數(shù)max目標(biāo)函數(shù)min目標(biāo)函數(shù)的系數(shù)約束條件右端常數(shù)約束條件右端常數(shù)目標(biāo)函數(shù)的系數(shù)3個≤≥=3個≥0≤0無符號限制約束條件變量3個≥0≤0無符號限制原問題（對偶問題）對偶問題（原問題）3個≥≤=約束條件變量(一)對稱型對偶問題原問題（對偶問題）對偶問題（原問題）目標(biāo)函數(shù)max目標(biāo)函數(shù)min目標(biāo)函數(shù)的系數(shù)約束條件右端常數(shù)約束條件右端常數(shù)目標(biāo)函數(shù)的系數(shù)3個≤≥=3個≥0≤0無符號限制約束條件變量3個≥0≤0無符號限制s.t.s.t.2個2個二、原問題與對偶問題的對應(yīng)關(guān)系例2
7、、寫出下述線性規(guī)劃問題的對偶問題解：設(shè)對偶變量為maxs.t.mins.t.則對偶問題為例3、寫出下述線性規(guī)劃問題的對偶問題解：設(shè)對偶變量為mins.t.maxs.t.則對偶問題為練習(xí)、寫出下述線性規(guī)劃問題的對偶問題maxs.t.mins.t.對偶問題的基本性質(zhì)DualityTheory線性規(guī)劃的對偶問題對偶問題的經(jīng)濟(jì)解釋——影子價格對偶單純形法靈敏度分析第二章線性規(guī)劃的對偶理論對偶問題的基本性質(zhì)對稱性弱對偶性無界性最優(yōu)性原問題與對偶問題單純形表間的性質(zhì)互補(bǔ)松弛性強(qiáng)對偶性對偶問題的基本性質(zhì)maxz=CXs.t.AX≤bX≥0minw=bTYs.t.ATY≥CTY≥
8、0s.t.
