第二 對偶問題學(xué)習(xí)教案

1、會計學(xué)1第二第二 對偶對偶(du u)問題問題第一頁，共17頁。 上述兩個LP問題的數(shù)學(xué)模型是在同一企業(yè)的資源狀況和生產(chǎn)條件下產(chǎn)生的，且是同一個問題從不同角度考慮所產(chǎn)生的，因此兩者密切相關(guān)。稱這兩個LP問題是互為對偶(du u)的兩個LP問題。其中一個是另一個問題的對偶(du u)問題。 0,345432.2624min21212121yyyyyyyytsW0,26432452.34max21212121xxxxxxxxtsZ第1頁/共17頁第二頁，共17頁。 一般地對于一般地對于(duy)任何一個線性規(guī)劃問題都有一個與任何一個線性規(guī)劃問題都有一個與之相對應(yīng)的對偶問題。原問題與對偶問題的一般形

2、式為：之相對應(yīng)的對偶問題。原問題與對偶問題的一般形式為：0. .max221122222121112121112211xbxaxaxabxaxaxabxaxaxaxcxcxcjmnmnmmnnnnnnt sZ0. .min221122222112112211112211ycyayayacyayayacyayayaybybybinmmnnnmmmmmmtsW 原問題(wnt)（LP） 對偶問題(wnt)（DP）相應(yīng)(xingyng)的矩陣形式為：0XbAX.t .sCXZmax0YCYA.t .sYbWmin第2頁/共17頁第三頁，共17頁。原問題Max（對偶問題）對偶問題Min（原問題）約束條

3、件數(shù)=m 變量個數(shù)=m第i個約束條件為“”第i個約束條件為“”第i個約束條件為“=” 第i個變量0 第i個變量0 第i個變量無限制變量個數(shù)=n 約束條件個數(shù)=n第i個變量0第i個變量0第i個變量無限制 第i個約束條件為“” 第i個約束條件為“” 第i個約束條件為“=”第i個約束條件的右端項目標(biāo)函第i個變量的系數(shù) 目標(biāo)函數(shù)第i個變量的系數(shù) 第i個約束條件的右端頂 歸納對稱形式歸納對稱形式(xngsh)(xngsh)與非對稱形式與非對稱形式(xngsh)(xngsh)的對偶的對偶, ,原問題與對偶問題之間的關(guān)系如下表所示：原問題與對偶問題之間的關(guān)系如下表所示：第3頁/共17頁第四頁，共17頁。無約

4、束xxxxxxxxxxxxxxxtsZ321321321321321,0,5348321043.422min 例例1 1、寫出下列、寫出下列(xili)(xili)線性規(guī)劃問題的對偶問題線性規(guī)劃問題的對偶問題第4頁/共17頁第五頁，共17頁。例例2 2 求解求解(qi ji)(qi ji)下列線性規(guī)劃問題：下列線性規(guī)劃問題：)4, 3 ,2, 1( ,01 25246 .52415min32132321itsZyyyyyyyyyi2. 2. 對偶對偶(du u)(du u)單純形法單純形法)4 , 3 , 2 , 1( , 01 25246 . .52415ax5321432321/itsZm

5、yyyyyyyyyyyi)4 , 3 , 2 , 1( , 01 25-246- . .52415ax5321432321/itsZmyyyyyyyyyyyi第5頁/共17頁第六頁，共17頁。第6頁/共17頁第七頁，共17頁。第7頁/共17頁第八頁，共17頁。迭代終止條件(tiojin)：所有的Bi非負(fù)。第8頁/共17頁第九頁，共17頁。第9頁/共17頁第十頁，共17頁。3.1 3.1 分析價值分析價值(jizh)(jizh)系數(shù)的變化系數(shù)的變化3 靈敏度分析(fnx) 在單純形表中，價值系數(shù)的變化僅僅(jnjn)影響到檢驗數(shù)的變化，只需要對檢驗數(shù)進(jìn)行最優(yōu)性檢驗，判斷是否需要繼續(xù)迭代即可。第1

6、0頁/共17頁第十一頁，共17頁。 CCBCNCSbXBXNXSCBB-1bIB-1NB-1ZC BB-1b0C BB-1N-CNCB B-1 CCBCNCSbXBXNXSCsbBNIZCBCN03.2 3.2 分析資源系數(shù)分析資源系數(shù)(xsh)(xsh)的變化的變化資源系數(shù)(xsh)的變化對最優(yōu)單純形標(biāo)的b列有影響。第11頁/共17頁第十二頁，共17頁。1 1/4- 01/2- 1/4 0 15/2- 5/4 1B Ixxx1543，則對應(yīng)，在初始單純形表中，第12頁/共17頁第十三頁，共17頁。例題(lt) P652/12/112/35532151 1/4- 01/2- 1/4 0 15/

7、2- 5/4 1bBb 1/第13頁/共17頁第十四頁，共17頁。 CCBCNCSbXBXNXSCBB-1bIB-1NB-1ZC BB-1b0C BB-1N-CNCB B-1 CCBCNCSbXBXNXSCsbBNIZCBCN03.3 3.3 增加增加(zngji)(zngji)變量的變化變量的變化1計算該列技術(shù)(jsh)系數(shù)。2技術(shù)(jsh)該列檢驗數(shù)。第14頁/共17頁第十五頁，共17頁。207-2431 1/4- 01/2- 1/4 0 15/2- 5/4 1PBP 61/6 例題：投產(chǎn)新產(chǎn)品(chnpn)，所需原料和設(shè)備分別為3、4、2單位，利潤為3單位，問最優(yōu)生產(chǎn)計劃如何變化？1120207-3 6207- 第15頁/共17頁第十六頁，共17頁。3.4 技術(shù)系數(shù)(xsh)aij的變化 例題：如果乙