實驗三--對偶理論

1、實驗三對偶理論、實驗?zāi)康恼莆誛inQSB軟件求解對偶規(guī)劃，進行靈敏度分析和參數(shù)分析。、實驗平臺和環(huán)境Windows9X/ME/NT/2000/XP 平臺下，WinQSB V1.0 版本已經(jīng)安裝在 C:WinQSB 中。三、實驗內(nèi)容和要求熟悉WinQSB軟件子菜單能用WinQSB軟件求解運籌學中常見的數(shù)學模型。用WinQSB軟件完成以下問題例 3.1 max Z=4x 1 +2x 2 +3x 3利潤f 2 x1+2 x2+4 x3100 材料 1 約束3 x1 + x2+6 x3 100材料 2 約束3 X1 + X2+2 X3 120材料 3 約束Lx 1， x 2 ， x 301寫出對偶線性

2、規(guī)劃，變量用y表示。2. 求原問題及對偶問題的最優(yōu)解。j及右端常數(shù)的最大允許變化范圍。4. 目標函數(shù)系數(shù)改為 C = (5, 3, 6)，常數(shù)改為b= (120, 140, 100)，求最優(yōu)解。1 +5x 2 +x 3 200 和一個變量 X4，系數(shù)為(C4 , a14 , a24 , 834 ,玄44)=(7, 5, 4, 1, 2), 求最優(yōu)解。6. 在第5問的模型中刪除材料 2的約束，求最優(yōu)解。7. 原模型的資源限量改為b= (100+ , 100+3 , 120 )T，分析參數(shù)的變化區(qū)間及對應(yīng)解的關(guān)系，繪制參數(shù)與目標值的關(guān)系圖。四、實驗操作步驟1 問題命名條件，條件設(shè)定并保存1啟動線性

3、規(guī)劃與整數(shù)規(guī)劃程序；(Linear and Integer Programming)，建立新問題例3.1，根據(jù)題意知道變量Number of Variables丨和約束條件(Number of Constraints)各有三個，設(shè)置如以下列圖。圖3-12其余選擇默認即可。點0K得到下表，根據(jù)實驗條件輸入數(shù)據(jù)并存盤。陽 Untsr and Integer Progranwnng-T X.Fie 5dt Ftrhna:刃低 3七山遜址 it.-.L. Ltlltes 齷如 Wn匚那 Hep圖3-22得到對偶問題極其模型1點擊Format Switch to Dual Form，得到對偶問題的數(shù)據(jù)表

4、如下:圖3-32點擊 Format Switch to Normal Model Form，得到對偶模型。圖3-43點擊 Edit圖3-54點上圖中的“ ok，得到以y為變量的對偶模型圖3-65 返回原問題求出最優(yōu)解及最優(yōu)值再求一次對偶返回到原問題，求解模型顯示最優(yōu)解為X=(25,25,0)，最優(yōu)值為 Z=150。查看最優(yōu)表中影子價格(Shadow Price)對應(yīng)列的數(shù)據(jù)就是對偶問題的最優(yōu)解為丫=(0.5,1.0 ,0)見表5,還可以根據(jù)性質(zhì)求出，顯示最終單純形表。松弛變量檢驗數(shù)的相反數(shù)就是對偶問 題的最優(yōu)解。寶 Fncl fesLk 也ttfpQl|1訕A|n=|q?JI onlMned

5、Import For I1t5k452D0t4101S:5kUKDecnion VaiableVdueUnit Ccsl nMcfl)T備1CMhibutjonReduced CostBd$if StahiiAb皿 血珊ARVHdlB 血珊TXI曲lOOOO4.0000waoooo0bdticimB.00002X225.0000500000Dbdtic1J333400003X30 20005 0000制 iKWdsownObfectivEFunctionHath15MDOOConstrainlLdtHandSideDiecticnHi只H聞dEideSlack o EuphisShadow P

6、riceAllow aH? Min. RH$Allowable Mai. RH5Tk11O0.NKN)<-100.00000uoinUG567200.00002總10D.M0t<-lOOlOOOO0uotn51 血 00PDLOOOO3h3lOD.MOO<=iaoMi20 OOM01 M.OD00M圖3-73. 求價值系數(shù)Cj及右端常數(shù)的最大允許變化范圍在綜合分析報告表中查找Allowable min(max)對應(yīng)列，寫出價值系數(shù)及右端常數(shù)的允許變化范圍。由表最后兩列價值系數(shù)Cj (j=1,2,3)取最大允許范圍分別是2 , 6 1.3333,4-,8右端常數(shù)bi(9=1,2

7、,3)的最大允許變化范圍分別是66.6667,20050,120100, + g 4修改目標函數(shù)系數(shù)，常數(shù)向量并求最優(yōu)解1修改系數(shù)和常數(shù)向量，把原條件的C=4, 2, 3變?yōu)?, 3, 6常數(shù)由100,100, 120丨變?yōu)?20, 140, 100。修改后如下：圖3-82按下(solve and analyze)得到下表:hi£ ar and Integer Prograirmirig由表中可以得到修改模型的最優(yōu)解為圖3-9X=(20,20,10 )。最優(yōu)值為 Z=220.慶 F;nn Rcsuj yitts 理Mew Heb1S3Cofiibrwd Report for 115:

8、57:37200C411印:戈下甲 2W6411 15c57:36T 2006+11 1i57:3G-| 2D0M1115:57:36 TT7Decttion Vaiia bitSvkibofi VatasUn* CottQr PMitcOTotal l 前 itnjliondeducedSail StAusAl Mabie Mil即Mat 琲XIZlOOMl5.WN1mooM0b«KiflMid9 OOM2X2加 OOOO300 DO曲.MOD0banc1 wa.oom3X310.0000EO0HBO.MOD0banctoooo10.NNObfecliYeFificbari(Tau

9、noo(Niie.MemateSolutionConsbainiLeft Hand Side：DiedionRiRt Had Side弘let h Suriplushadofl PncEAlDHdbfc Min. R船Ala.婭Uu. RMSTn13DOOOO120.DOB01.000093333320Q.0D002D14D.0NK1<-1O.KUQ0018MN03ca100.0000<=mono01.D0D0NLOOOO14U0M5. 改變約束條件和系數(shù)求解1插入約束條件點擊EditInsert a Contraint選擇在結(jié)尾處插入變量The end再按下"ok圖 3

10、-10插人一個約束 6x1 +5x 2 +X 3200,圖 3-112修改相應(yīng)系數(shù)如1中一樣操作，點擊EditInsert a Variable插入一個變量，選擇在末尾添加。改變系數(shù)：C4，a14，a24，a34，a44=7, 5，4，1，2，圖 3-12按下solve and analyze得到以下結(jié)果:涓 ILiwarrd Integer Proqtairmi 珂FH f FsuU tites kroew Hri:a®*-ip：2MflQunnbined Report fev 11S 04:14aiUfr+ll20M+11 IfchzIl'MF l0fr4-11 堆MM下

11、午OKitiofilSold 湖 VIKUnit Coit aMcOTdUIEMibutiwiR* 臥<1 CodD«nSlhflA«ow 恥 Min clMn efil1XI14.29574.D0IM57.U3B0hanc4朋2X2D2D0D0D41.185?a4 bai»d22fi£?2X3Dloom0<NMHal baundMODOM4X4H 285?zoomWKIOO9IhkG咖I0Q000UbiediYB卜Uhdli聞出辺=15T.uaCMihwtLelt Hand SidhHighl HandSlKlk cir SiipkjtSh

12、iddoH PricefArttMeMih RHSAlmbleU«h. RFIS7Cl1DODDOO<=imnDOD0L7143125 00002G190 9000ltnwua0臨1»DUMIZ3 03圮1<120. VUDOaxn0Ml僭M4iu.a&/<=2UU-UUMIlfi/143(11H2V5JM圖 3-13由H表中可以查得：最優(yōu)解為：X=(14.2857,0,0,14.2857),最優(yōu)值為Z=157.1429.6. 刪除約束條件操作Delete a Contraint，選擇要刪除的約束C2點其操作類似于添加約束條件：點擊Edit“ok

13、再求解即可。得到如下結(jié)果：囿 Iand Wefer fruyMTwihgRlt FcffMt蟲fb林過曲m 妙直闔可ghfil封計啊凰川RIG 刑M Dfritinal) Report For I1&1B542DOW-111G-1E:5*T-|2M1&4-11 丫:懷創(chuàng)匚二2006-4-11D*ciuon 也話出Sduiion換Unit Cmi « hoft 4)laidCoMriuthnFUdutwi CoriBaahSl4hnAllctwbfeMincfilAllMtabicMdLCflTXI3(176324.0M012JI7E30buk：2.BODO21 ONO

14、2X202m01,7692al bMmi倔23X30IttOO0咖5al bond5.4C1543U7 £9(2?7 0IN051M»OburIDOINIOObjectneFunction|Mk| =ConsuamlLeft Hand SidettirEKlionRigMH*SiteDfSupIlBShdwPiceAllombteHm RH5Allmbie RHS7_ci100.CUN141DQMD0O1.M77皈刪5N OOCO2a1001( DO=VAD0003100000iou«nMac+2D0.HMM<=290. DODO0(L23DB4DJONO2

15、40 0000圖 3-14由表中可以查得：最優(yōu)解為X=(30.7692,0,0,7.6923),最優(yōu)值為 Z=176.9231.7. 改變資源限量并分析繪圖u的系數(shù)1返回到原問題數(shù)據(jù)表，先求解。目標函數(shù)系數(shù)由兩局部構(gòu)成，記住參數(shù)1，3，-1對原問題求解后，點擊Results Perform Parametric Analysis，在參數(shù)分析對話框中選擇目標函數(shù)ObjectiveFunction圖 3-152輸入?yún)?shù)u的系數(shù)(1，3，-1)，hjerl-ive Fi inrtinvi Prturbritinn Virhnii1OKCone clHelp圖 3-163確定后顯示下表。表中沒有顯示參

16、數(shù)在區(qū)間內(nèi)的最優(yōu)解，這是因為最優(yōu)解是參數(shù)u的函數(shù)，只有給定了具體參數(shù)值才能得到具體的最優(yōu)解,圖 3-174由上表知，將參數(shù) u奉承5個區(qū)間討論，在不同區(qū)間顯示了目標函數(shù)值的變化區(qū)間及其變化率 slope,出基變量和進基變量Leaving Variable Entering V ariable丨點擊ResultsGraphic Parametric analysis打印參數(shù)與目標值的關(guān)系圖。顯示以下列圖圖 3-18五、數(shù)據(jù)處理和分析1 題目中對數(shù)據(jù)進行插入約束變量插入的時候要首先把變量個數(shù)由原來的3個替換為4個然后才可以添加，否那么由于個數(shù)為做改變新變量會覆蓋舊變量。2 .7個問題是獨立求解和分

17、析，每個問題都是針對原線性規(guī)劃分析和求解，每一步都必須回到原模型。技巧：做完一個問題后退出所有活動窗口，翻開剛剛保存的原向題文件。這樣不必修改數(shù)據(jù)六、分析討論題1. 某人根據(jù)醫(yī)囑，每天需補充 A、B、C三種營養(yǎng)，A不少于80單位，B不少于150 單位，C不少于180單位。此人準備每天從6種食物中攝取這三種營養(yǎng)成分。 6種食物 每百克的營養(yǎng)成分含量及食物價格如表所示1試建立此人在滿足健康所需要的根底上花費最少的數(shù)學模型2假定有一個廠商方案生產(chǎn)一種藥丸，售給此人服用，藥丸中含有A，B，C三種營養(yǎng)成分試為廠商制定一個藥丸的合理價格，既要此人愿意購置， 又使廠商能獲利最大， 建立數(shù)學模型。表3-1食物

18、含量需營養(yǎng)123456要分量A1251440811>=830B2930251215>=1450C172134100>=1880食物單價元 /100g根據(jù)題目意思得到以下數(shù)學模型：其中變量X為6中食物前面的系數(shù)為其含量，由A，B，C得到3個約束條件M 1+0. 4x 2+0.8 X34+0. 3x 5+0.2 X6花費廠 13x1 +25x 2 +14 X3+40x4+8x5+11 X6=80A 營養(yǎng)約束24x 1 +9x 2 +30 x3+25x4+12x5+15 X6=150B 營養(yǎng)約束18x1 +7x 2 +21 x 3+34x4+10x5 =180C 營養(yǎng)約束V x 1

19、， x2，x 3，X4，X5， X6 02從廠商來看當然是1 +0. 4x 2 +0.8 X34+0. 3x5+0.2 X6越大越好，但從此人來看他的支付越少越好。廠商只有在先滿足此人能接受的情況下制定一個藥丸的合理價格，為此得到如下的數(shù)學模型：M 1 +0. 4x 2 +0.8 X34+0. 3X5+0.2 X6花費廠 13x 1 +25x 2 +14 X3+40X4+8X5+11 X6 >=80A 營養(yǎng)約束24x 1 +9x 2 +30 X3+25X4+12X5+15 X6 >=150B 營養(yǎng)約束C營養(yǎng)約束18x 1 +7x 2 +21 X3+34X4+10X5 >=18

20、0X 1 , X 2 , x3 , X4, X5, X602. 現(xiàn)有線形規(guī)劃問題max Z=5x 1 +5x 2 +13x 3廠一x 1 + X 2 +3 X 320s 12 x 1 + 4x 2 +10 x 390先用單純形法求出最優(yōu)解，然后分析在各種情況下，最優(yōu)解分別有什么變化?(1) 約束條件的右端常數(shù)由20變?yōu)?0；(2) 約束條件的右端常數(shù)由90變?yōu)?0；(3) 目標函數(shù)中x3的系數(shù)由13變?yōu)?；(4) x1的系數(shù)列向量由一1, 12丨變?yōu)?, 5(5) 增加一個約束條件 2 x1 + 3x2 +5 x3 50 ;(6) 將原約束條件 改變?yōu)?0 x1+ 5x 2+10 x 3100 ；解答：(1)按步驟求解得到如下表格：fieRraJls 歩 BJe上沖Si coHixned Kemt fw 1匕0目目目血置MeLnev -and lrfteer Pe ogranwrii-ig15:12:41200G