4第四章 對(duì)偶單純形法和對(duì)偶問(wèn)題課件

第四章對(duì)偶問(wèn)題及對(duì)偶單純形法§4.1對(duì)偶問(wèn)題的提出4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題一、問(wèn)題的提出ABC擁有量工時(shí)1113材料1479單件利潤(rùn)233例1現(xiàn)有工廠生產(chǎn)A、B、C三種產(chǎn)品，單位產(chǎn)品所需要消耗的工時(shí)、材料及擁有量如下表，已知每單位A、B、C產(chǎn)品的利潤(rùn)分別為2、3、3，如何分配資源可以使得利潤(rùn)最大4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題建立模型如下4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題ABC擁有量工時(shí)1113材料1479單件利潤(rùn)233

假設(shè)有客戶(hù)提出要求，購(gòu)買(mǎi)工廠所擁有的工時(shí)和材料，為客戶(hù)加工別的產(chǎn)品，由客戶(hù)支付工時(shí)費(fèi)和材料費(fèi)。那么工廠給每單位工時(shí)和材料制訂的最低價(jià)格應(yīng)是多少，才值得出賣(mài)工時(shí)和材料?

同樣是這個(gè)問(wèn)題，現(xiàn)在我們來(lái)?yè)Q一個(gè)角度思考4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題ABC擁有量工時(shí)1113材料1479單件利潤(rùn)233在考慮這個(gè)問(wèn)題時(shí)我們應(yīng)做到：1、價(jià)格應(yīng)該盡量低，這樣，才能有競(jìng)爭(zhēng)力;2、出賣(mài)資源獲利應(yīng)不少于生產(chǎn)產(chǎn)品的獲利;3、價(jià)格應(yīng)該是非負(fù)的目標(biāo)約束條件非負(fù)約束4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題ABC擁有量工時(shí)1113材料1479單件利潤(rùn)233

現(xiàn)在我們用數(shù)學(xué)語(yǔ)言描述，設(shè)y1和y2分別表示單位工時(shí)和材料的出售價(jià)格總價(jià)格最小minW=3y1+9y2保證獲利大于A產(chǎn)品利潤(rùn)y1+y2≥2保證獲利大于B產(chǎn)品利潤(rùn)y1+4y2≥3保證獲利大于C產(chǎn)品利潤(rùn)y1+7y2≥3售價(jià)非負(fù)y1≥0y2≥04第四章對(duì)偶單純形法和對(duì)偶問(wèn)題ABC擁有量工時(shí)1113材料1479單件利潤(rùn)2334第四章對(duì)偶單純形法和對(duì)偶問(wèn)題二、對(duì)偶問(wèn)題概念

任何一個(gè)線(xiàn)性規(guī)劃問(wèn)題都有一個(gè)與之相對(duì)應(yīng)的線(xiàn)性規(guī)劃問(wèn)題，如果前者稱(chēng)為原始問(wèn)題，后者就稱(chēng)為“對(duì)偶”問(wèn)題。對(duì)偶問(wèn)題是對(duì)原問(wèn)題從另一角度進(jìn)行的描述.其最優(yōu)解與原問(wèn)題的最優(yōu)解有著密切的聯(lián)系，在求得一個(gè)線(xiàn)性規(guī)劃最優(yōu)解的同時(shí)也就得到對(duì)偶線(xiàn)性規(guī)劃的最優(yōu)解，反之亦然。對(duì)偶理論就是研究線(xiàn)性規(guī)劃及其對(duì)偶問(wèn)題的理論，是線(xiàn)性規(guī)劃理論的重要內(nèi)容之一。

4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題第四章對(duì)偶問(wèn)題及對(duì)偶單純形法§4.2建立對(duì)偶問(wèn)題的規(guī)則4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題一、建立對(duì)偶問(wèn)題的規(guī)則可以用如下形式表示原問(wèn)題與對(duì)偶問(wèn)題之間的關(guān)系原問(wèn)題maxz=CXAX≤bX≥0對(duì)偶問(wèn)題minw=bTY ATY≥CT Y≥0其中Y=（y1,y2,……ym）4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題二、對(duì)偶問(wèn)題的特點(diǎn)（1）目標(biāo)函數(shù)在一個(gè)問(wèn)題中是求最大值在另一問(wèn)題中則為求最小值（2）一個(gè)問(wèn)題中目標(biāo)函數(shù)的系數(shù)是另一個(gè)問(wèn)題中約束條件的右端項(xiàng)（3）一個(gè)問(wèn)題中的約束條件個(gè)數(shù)等于另一個(gè)問(wèn)題中的變量數(shù)（4）原問(wèn)題的約束系數(shù)矩陣與對(duì)偶問(wèn)題的約束系數(shù)矩陣互為轉(zhuǎn)置矩陣4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題對(duì)偶問(wèn)題對(duì)應(yīng)表原問(wèn)題（對(duì)偶問(wèn)題）對(duì)偶問(wèn)題（原問(wèn)題）目標(biāo)函數(shù)max目標(biāo)函數(shù)min變量數(shù)：n個(gè)第j個(gè)變量≥0第j個(gè)變量≤0第j個(gè)變量是自由變量

目標(biāo)函數(shù)中變量的系數(shù)約束條件：n個(gè)第j個(gè)約束類(lèi)型為“≥”第j個(gè)約束類(lèi)型為“≤”第j個(gè)約束類(lèi)型為“＝”約束條件右端項(xiàng)約束條件：m個(gè)第i個(gè)約束類(lèi)型為“≤”第i個(gè)約束類(lèi)型為“≥”第i個(gè)約束類(lèi)型為“＝”約束條件右端項(xiàng)變量數(shù)：m個(gè)第i個(gè)變量≥0第i個(gè)變量≤0第i個(gè)變量是自由變量

目標(biāo)函數(shù)中變量的系數(shù)4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題三、例題原問(wèn)題：對(duì)偶問(wèn)題：maxZ=70X1+120X2minω=360y1+200y2+300y3

9X1+4X2≤3609y1+4y2+3y3≥704X1+5X2≤2004y1+5y2+10y3≥1203X1+10X2≤300y1≥0,

y2≥0,

y3≥0X1≥0X2≥0習(xí)題：課本P51例24第四章對(duì)偶單純形法和對(duì)偶問(wèn)題練習(xí)寫(xiě)出如下LP問(wèn)題的對(duì)偶問(wèn)題4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題第四章對(duì)偶問(wèn)題及對(duì)偶單純形法§4.3對(duì)偶問(wèn)題的基本性質(zhì)(選學(xué))4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題一、對(duì)稱(chēng)性定理1、對(duì)偶問(wèn)題的對(duì)偶就是原始問(wèn)題定理2（可行解的目標(biāo)函數(shù)值之間的關(guān)系）設(shè)X、Y分別是原始問(wèn)題和對(duì)偶問(wèn)題的可行解，則

CX≤YTb二、弱對(duì)偶性4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題1.如果原問(wèn)題（對(duì)偶問(wèn)題）具有無(wú)界解，則其對(duì)偶問(wèn)題（原問(wèn)題）無(wú)可行解。2.若原問(wèn)題可行,而對(duì)偶問(wèn)題不可行,則原問(wèn)題的目標(biāo)函數(shù)值無(wú)界3.若對(duì)偶問(wèn)題可行,而原問(wèn)題不可行,則對(duì)偶問(wèn)題的目標(biāo)函數(shù)值無(wú)界推論:4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題例如試用對(duì)偶理論證明原問(wèn)題無(wú)界。

解：=（0.0.0）是原問(wèn)題的一個(gè)可行解，而對(duì)偶的第一個(gè)約束條件不能成立（因?yàn)閥1,

y2≥0)。因此，原問(wèn)題無(wú)界。習(xí)題P603.4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題定理3三、可行解是最優(yōu)解的性質(zhì)4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題四、對(duì)偶定理

定理4如果原問(wèn)題有最優(yōu)解，則其對(duì)偶問(wèn)題也一定有最優(yōu)解，且兩者的目標(biāo)函數(shù)值相等

定理5若X為原問(wèn)題的滿(mǎn)足最優(yōu)檢驗(yàn)的基本解。則Y=CBb-1為對(duì)偶問(wèn)題的可行解

(原問(wèn)題在得到基本可行解的同時(shí)，其檢驗(yàn)數(shù)的相反數(shù)就構(gòu)成對(duì)偶問(wèn)題的一個(gè)基本解，且各自目標(biāo)函數(shù)值恒相等。)補(bǔ)充：對(duì)比原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)單純形表P54表4－2，4－34第四章對(duì)偶單純形法和對(duì)偶問(wèn)題Cj→-6-3-2000θjCBXBb

X1

X2

X3

X4

X5

X6-20-3X3X6X216104001-240-100-1011101-40σj=cj-zj-300-1-40Cj→20610000θjCBYBb

Y1

Y2

Y3

Y4

Y5

Y60620Y4Y2Y134100111-1001004-41010-12σj=cj-zj00-100-4-16原問(wèn)題對(duì)偶問(wèn)題4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題第四章對(duì)偶問(wèn)題及對(duì)偶單純形法§4.4對(duì)偶單純形法4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題

當(dāng)一個(gè)線(xiàn)性規(guī)劃問(wèn)題是求目標(biāo)函數(shù)值最小，約束方程是≥時(shí)，求解時(shí)用大M法或兩階段法比較麻煩，此時(shí)較有效的算法是將要介紹的對(duì)偶單純形法對(duì)偶單純形法并不是求解對(duì)偶問(wèn)題解的方法，而是利用對(duì)偶理論求解原問(wèn)題的解的方法。一、原理4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題第一步找出一個(gè)初始正則解B0，要求對(duì)應(yīng)的單純形表中的全部檢驗(yàn)數(shù)≤0，但右邊項(xiàng)中允許有負(fù)數(shù)第二步若右邊項(xiàng)中各數(shù)均非負(fù)，則B0已是最優(yōu)基，即已求得最優(yōu)解，計(jì)算終止；否則轉(zhuǎn)為下一步第三步取右邊項(xiàng)中取值最?。簇?fù)的最多）的數(shù)所對(duì)應(yīng)的變量為換出變量。二、對(duì)偶單純形法的計(jì)算步驟4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題第四步按公式

其中σj＝cj–zj計(jì)算最小比值θ,則該列所對(duì)應(yīng)的變量即為換入變量第五步以換出變量的行和換入變量列交點(diǎn)處的元素為主元進(jìn)行單純形迭代，再轉(zhuǎn)入第二步。<4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題

用對(duì)偶單純形法求解線(xiàn)性規(guī)劃問(wèn)題：

minw=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1yj≥0，對(duì)一切j解：先將問(wèn)題改寫(xiě)為

maxw’=-15y1-24y2-5y3maxw’=-15y1-24y2-5y36y2+y3-y4=2-6y2-y3+y4=-25y1+2y2+y3-y5=1-5y1-2y2-y3+y5=-1yj≥0，對(duì)一切jyj≥0，對(duì)一切j三、例題4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題第一步建立一個(gè)初始單純形表，使表中檢驗(yàn)行的值全部≤0

即對(duì)其對(duì)偶問(wèn)題而言是一基本可行解。Cj→-15-24-500CBYBbY1Y2Y3Y4Y500Y4Y5-2-10-6-110-5-2-101σj=cj-zj-15-24-5004第四章對(duì)偶單純形法和對(duì)偶問(wèn)題第二步檢驗(yàn)當(dāng)前可行解是否可行，若可行，已得最優(yōu)解，否則轉(zhuǎn)入下一步Cj→-15-24-500CBYBbY1Y2Y3Y4Y500Y4Y5-2-10-6-110-5-2-101σj=cj-zj-15-24-500檢驗(yàn)數(shù)均為非正數(shù)，但右邊項(xiàng)仍有負(fù)數(shù)，并非最優(yōu)解，繼續(xù)迭代4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題第三步選擇b列中取值最小（即負(fù)的最多）的數(shù)所對(duì)應(yīng)的變量為出基變量。Cj→-15-24-500CBYBbY1Y2Y3Y4Y500Y4Y5-2-10-6-110-5-2-101σj=cj-zj-15-24-5004第四章對(duì)偶單純形法和對(duì)偶問(wèn)題第四步按公式

計(jì)算最小比值θ,則該列所對(duì)應(yīng)的變量即為入基變量。（其中σj＝cj–zj

）<Cj→-15-24-500CBYBbY1Y2

Y3Y4Y500Y4Y5-2-10[-6]-110-5-2-101σj=cj-zj-15-24-500θ/45//4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題第五步用換入變量替換對(duì)偶問(wèn)題中的換出變量得到一個(gè)新的單純形表。表中數(shù)字計(jì)算同用單純形法時(shí)完全一樣。新表中對(duì)偶問(wèn)題仍保持基本可行解

Cj→-15-24-500CBYBbY1Y2Y3

Y4Y5-240Y2Y51/3-1/3011/6-1/60-50[-2/3]-1/31σj=cj-zj-150-1-40θ3/3/212/4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題第六步：重復(fù)第二～四步，一直到找出最優(yōu)解為止。Cj→-15-24-500CBYBbY1Y2Y3Y4Y5-24-5Y2Y31/41/2-5/410-1/41/415/2011/2-3/2σj=cj-zj-15/200-7/2-3/2θ

此時(shí)右邊項(xiàng)全為非負(fù)值，達(dá)到最優(yōu)，Y1=0，Y2=1/4,Y3=1/2,W最優(yōu)為17/2

4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題四、練習(xí)課本60頁(yè)24第四章對(duì)偶單純形法和對(duì)偶問(wèn)題第四章對(duì)偶問(wèn)題及對(duì)偶單純形法§4.5對(duì)偶問(wèn)題的經(jīng)濟(jì)意義——影子價(jià)格4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題定義：約束條件方程右端的bi增加一單位時(shí)，最優(yōu)目標(biāo)函數(shù)z的變化量稱(chēng)為資源i的影子價(jià)格.影子價(jià)格越大，說(shuō)明這種資源越是相對(duì)緊缺影子價(jià)格越小，說(shuō)明這種資源相對(duì)不緊缺如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0q’i4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題第四章對(duì)偶問(wèn)題及對(duì)偶單純形法§4.6對(duì)偶單純形法的一個(gè)應(yīng)用（增加約束條件）4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題

在求出線(xiàn)性規(guī)劃問(wèn)題的最優(yōu)解后，又增加一個(gè)約束條件，此時(shí)可以利用對(duì)偶單純形法求解，不必對(duì)原問(wèn)題從頭做起。其步驟如下：1、將最優(yōu)解代入新的約束條件，若滿(mǎn)足，則最優(yōu)解不變2、若不滿(mǎn)足，則當(dāng)前最優(yōu)解要發(fā)生變化；將新增約束條件加入松弛變量或剩余變量后加入到原來(lái)的最優(yōu)單純形表，令原來(lái)的基變量和新增加的變量組成新的基，進(jìn)行初等變換將基變量對(duì)應(yīng)的系數(shù)矩陣變?yōu)閱挝痪仃嚒?、利用對(duì)偶單純形法繼續(xù)迭代一、原理及步驟4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題二、例題2x1+3x2+x3+2x4+x5=8005x1+4x2+3x3+4x4+x6=12003x1+4x2+5x3+3x4+x7=1000xj≥0轉(zhuǎn)化為標(biāo)準(zhǔn)型：4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題Cj→1534000CBXBbX1X2X3X4X5X6X7045X5X4X21002001001/40-13/4011/4-120-2101-1-3/4111/400-3/41σj=cj-zj-13/40-11/400-1/4-1以達(dá)到最優(yōu)，此時(shí)X1=0，X2=100，X3=0，X4=200，X5=100，X6=0，X7=0,Z=1300若此時(shí)增加約束條件X1+2X2+3X3+3X4≤650，代入當(dāng)前的最優(yōu)解檢驗(yàn)不符合條件，應(yīng)繼續(xù)迭代加入新條件，將原問(wèn)題變?yōu)椋豪脝渭冃畏ǖ蟮茫?第四章對(duì)偶單純形法和對(duì)偶問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)型：2x1+3x2+x3+2x4+x5=8005x1+4x2+3x3+4x4+x6=12003x1+4x2+5x3+3x4+x7=1000x1+2x2+3x3+3x4+x8=650xj≥0，對(duì)一切j4第四章對(duì)偶單純形法和對(duì)偶問(wèn)題Cj→15340000CBXBbX1X2X3X4X5X6X7X80450X5X4X2X81002001006501/40-13/4011/4-1020-2101-10-3/4111/400-3/41012330001Cj→15340000CBXBbX1X2X3X4X5X6X7X80450X5X4X2X81002001004501/40-13/4011/4-1020-2101-10-3/4111/400-3/4105/20-5/2303/2-21Cj→15340000CBXBbX1X2X3X4X5X6X7X80450X5X4X2X8100200100-1501/40-13/4011/4-1020-2101-10-3/4111/400-3/410-7/207/200-3/2114第四章對(duì)偶單純形法和對(duì)偶問(wèn)題Cj→15340000CBXBbX1X2X3X4X5

X6X7X80450X5X4X2X8100200100-1501/40-13/4011/4-1020-2101-10-3/4111/4