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