試驗(yàn)04講評(píng)、參考答案_數(shù)學(xué)規(guī)劃模型一2學(xué)時(shí)

1、實(shí)驗(yàn)04講評(píng)、參考答案未按時(shí)交的同學(xué)數(shù)學(xué)：01邊清水，27魯瑞，50鐘鑫信科：13林其博批改情況：批改了偶數(shù)學(xué)號(hào)的實(shí)驗(yàn)報(bào)告。附參考答案:海南大學(xué)信息科學(xué)技術(shù)學(xué)院實(shí)驗(yàn)報(bào)告成績(jī)實(shí)驗(yàn)課程:數(shù)學(xué)建模實(shí)驗(yàn)指導(dǎo)教師王平學(xué)號(hào)：姓名：班級(jí)：同組成員：完成日期：20 年 月 S實(shí)驗(yàn)04數(shù)學(xué)規(guī)劃模型（2學(xué)時(shí)）（第4章數(shù)學(xué)規(guī)劃模型）1.（演示）加工奶制品的生產(chǎn)計(jì)劃（線性規(guī)劃LP） p8691問(wèn)題的基本模型p86 （線性規(guī)劃模型）：max z = 72x1 + 64x2s.t. x1 + x2 5012x1 + 8x2 4803x1 0, x2 0求解以上線性規(guī)劃問(wèn)題。要求：按如下步驟操作：打開(kāi)LINGO11s LI

2、NGO 11.0 - UNGO Model UNGO1- XEle Edit LINGO Window Help0 |s a| m國(guó)| d引國(guó) 道|啜R/wdy|而 M|LnTTl , 修改 選項(xiàng)”（Options）S UNGO 110 - LINGO Model - HNGO1- X口|國(guó)&園 LINGCSohreCtrl+USolution.Ctrl-I-WRang 營(yíng)Ctrl+ROptions-Ctrl +1GeneratePictureCtrl+KDebugCtrl+DModd StatisticsCtrl+ELook.,Ctrl 4-Lfile Edit LINGO Window H

3、elpCustomize optienal system settings選擇 LINGO/Options在出現(xiàn)的選項(xiàng)Ig架中，修改2個(gè)參數(shù)：選擇General Solver（通用求解器）選項(xiàng)卡，Dual Computations（對(duì)偶計(jì)算）設(shè)置為：Prices and Ranges（計(jì)算對(duì)偶價(jià)格并分析敏感性）選擇Model Generator （模型生成器）選項(xiàng)卡， Model Regeneration （模型 的重新生成）設(shè)置為：Always （每當(dāng)有需要時(shí)）點(diǎn)擊OK退出。LINGO OptionsInteger Pre-Solver Irrte-ger Sohrar 61 口舊上I ?？?/p>

4、Iwr Model GeneratarIriteiFaceGenerali SolwrLinear Sclw#rNonlin-d r SolverLINtjO Options,?Interface | Generali Scdwer | Ibinear .Iver | INanlmer SolverIriiLer Pre-Sobermwger SnMi1 I Global Solver Modffl Generatoi,SOlVt Ttme Gmit:-Dual Computation!IRumtimc UHtf ；Ite-raEionsTime (ee):|忖口廿三Timie (sec):

5、Kill scripts on limit* Variables assumed uan-negiatrviBI Use- formal: names fer IMPS I/OGenerator Memory Limit MB):Unary Minus Pniorilr Low 用 HbghRxed Var Reduction:Line-ar rows anlylirfBrijartion：Qf greetRig M:De ha：Solwr DMKides ,HOODOO11D06F Allow ynrfrrtnrted ux 唱f primitive set member narrF Ais

6、ume m&dd ir& Jineai一 Check for duplicate names id data and mocfiMinimi工e mpmor u-5.ag選Interface選卡，撤消Errors in Dial復(fù)選項(xiàng)，使出錯(cuò)時(shí)指出位置;單選項(xiàng)被選中，使LINGO為默認(rèn)狀態(tài)（ltx為L(zhǎng)INDO ）確認(rèn)lg4LINGO OpdonsInteger Pre-Sohfer Intege-r SdHf | Glakial Salw-r | Model GeneratcrInterface | Generdll Solver | Linear Solver | NonliiieAr So

7、lvff家：_ Err0rsi in Dialogs： rc ie nAll Out Ranges 口nd TablesF Splash Screen斤 Status Bar萬(wàn) Status WrfidewP ToolbarOutput level: Solution印臺(tái)F白同配t* lg& HMende由hg (teirt only)C 也UNDOSyntax ColoringLine Limit|1DOO7 Paren MatchCommand Window:出題irHum： 000趣!imum;應(yīng)Pag?號(hào)Limrts:Lfirigth- 1 .me 可OK Send Riparte t

8、e Ca-nhwiAnd Windav 廠Etho Input 在模型窗口輸入模型p88LINGO 11.0 - LINGO Model - LINGO1口 |謝日牌|,囪 二|二|心股|e| 回回兇|周引主|曾隨|NUMMODLn 8r CFile Edit LINGO Window HelpLINGO語(yǔ)法：基本語(yǔ)法見(jiàn)提示。將文件存儲(chǔ)并命名為p85_lg.lg4操作菜單欄：File/Save As（記住所在文件夾）求解模型運(yùn)行菜單LINGO/Solve。1囪 LINGO iro-LINGO Model -P5JgFile Edit LINGO Window HelpDHSolveCtrl +

9、 Ur-* LINGCSolution.RangeCtrl+WCtrl+Rmodel:IITLE文件名OptionslrkCtrlH-ln;ax=72GenerateniilktimePictureCtrl + Kcpct end|DebugCtrl + DModel StatisticCtrl+ESo Ives th e rLooLn.Ctrl + L“倒|回回后|畫蹩解|選擇 LINGO/Solve點(diǎn)擊“Clos然閉求解器狀態(tài)框H LING011,0 - Solution Report = p85_lg X印甘 dit LINGO JSindow Help口|闔。牌I |固向二號(hào)|電周e|

10、 91gli區(qū)|園引國(guó) 已闡|只“山一廠 NUM | |Ln, 口力求解結(jié)果的報(bào)告窗口檢查輸出結(jié)果與教材p89的標(biāo)準(zhǔn)答案是否相同。靈敏性分析點(diǎn)擊模型窗口，使該窗口為當(dāng)前窗口。LINGO 11.0 - UNGO Model - p85_lgFile Edit LINGO Window Help口|詡s圜 | |e| *|匐舒心|孰國(guó)也|岡|冉屈|曾懶|ReadyNUM選擇 LINGO/Ranges網(wǎng) LINGO 11.0 - Range Report - p85_lgFil# Edit LINGO Window Htlp口I宜la爭(zhēng)Imadel!畫 Range Report - p85jgRan

11、g已H m which the basis isunchanged:TITL. !文再1 0s 1mil tire. ：,cpcendObjecciveCurrent Coefficient72.0000064.00000Costficrent RangemAllawableIncrease24.000008.000000AllowableDecrease8.00000016.000GDRewMILK TIME CP CTCurrtnt RHSSO.OOODO 480.DODO 100.DODORighthand Side RangesAllowableIncrease10.00000S3.3

12、3333iNFIEfiTYAllowable Dtcrease .667 aO.OODOD 4D.D0D0DFor Help, press FlNUMIn 1, Col 151 5g pin模型的靈敏性分析報(bào)告（此處若出錯(cuò)，請(qǐng)檢查步驟（2）修改 選項(xiàng)（Options-。） 檢查輸出結(jié)果與教材p90的標(biāo)準(zhǔn)答案是否相同。結(jié)果分析可參閱教材p89-91。2.（驗(yàn)證）奶制品的生產(chǎn)銷售計(jì)劃（LP） p9195問(wèn)題的基本模型p92 （線性規(guī)劃模型）：max z = 24xi + 16x2 + 44x3 + 32x4 - 3x5 - 3x6s.t. 4ci + 3x2 + 4x5 + 3x6 6004xi

13、+ 2x2 + 6x5 + 4x6 480Xi + x5 0用LINGO求解以上線性規(guī)劃問(wèn)題。要求：按以下步驟操作：（如果不需要保留，最好關(guān)閉之前模型的所有窗口）打開(kāi)菜單“File ”/ “Ne新建模型文件。在模型編輯窗口輸入模型：LINGO IkO - LINGO Io del - p92Pile Edit Lira Window Help將文件存儲(chǔ)并命名為p92.lg4 （記住所在文件夾）求解模型。靈敏性分析。檢查輸出結(jié)果與教材p92-93的標(biāo)準(zhǔn)答案是否相同。結(jié)果分析可參閱教材p940求解報(bào)告（比較921）:工，SoLutinn RerrTrt -通 201回1Global cptJut

14、ion f onndiObjective valuE： Illo 11 i 11 es;Total solder i匕仁工at1口口m;3460.800O XOJOOC2hocej. Tide:媯制Ri的生產(chǎn)祜售計(jì)劃VaiiaJle XL X2 X3 H4 SF 6Value (.OOOODC 168.X DO 19. ZOOM 0 0000 DO 24. onooo L?？?00 )1deduced Cost 0000 0.000000 0.00000(1 O.OOOODO O.nODODO l.DUODORow1 MILK TINE CPCTE Eor Surplus J4tiO.aUU0

15、.0000 DO c.ocooao7a. OOooc 0.0000 DO0.00DOQ0Du式 Ptic& .UlUUUD X1COODO 3,26000(1 o.oOOOOO44.0000032. OOODO靈敏性分析報(bào)告（比較93）:寫工auge RepuiLt.-13目岡Fanoes in wtiictithe basisis unchanged：Oto j ective Coefticient BangesCuEren.till larrao leJlI LoTarat leVeuz Z.CL3 leC o ef f ic i exitIncr eDecnesseXI24.QiOOOO

16、1.68OD0OIMfIJJiT?X216.00000e lEozioo2.100COOZJ修子19.TSJOD3 . 1,5 6 6 6 7工且a2 .oocoo2.O2 66 67IM FI UTT1/3.00000015.603002.535333-3.0000001.52OD0Oiiirmmaignthaiicl 5 lie RangesRo ITCurrentlotraftleAllcwahleFH3Inc i. unnuDc.eE caseMILK600.0000120.0300200.0000TIKE490.0000253.3333eoi.oooooUP Cl,IOiO. uuo

17、oIMF1N1TY/b,UC0D0J0,0INFINITY19.20000G0.0INFINITYC .03.自來(lái)水輸送問(wèn)題（LP） p95983.1 （驗(yàn)證）求最小值的模型線性規(guī)劃（LP）模型：min z = 160 xii + 130 xi2 + 220 xi3 + 170 xi4 + 140 x21 + 130 x22 + 190 x23 + 150 x24 + 190 x31 + 200 x32 + 230 x33約束條件：xii + xi2 + xi3 + xi4 = 50 x21 + x22 + x23 + x24 = 60 x31 + x32 + x33 = 5030 xii +

18、 x21 + x31 8070 xi2 + x22 + x32 14010 xi3 + x23 + x33 3010 xi4 + x24 30;x11+x21+x3170;x12+x22+x3210;x13+x23+x3310;x14+x24m1(j);for(C(j): sum(R(i):x(i,j)m2(j); x(3,4)=0;end求解報(bào)告：13E Snlntinn Rspnit -二J3.2 （求解）求最大值的模型線性規(guī)劃（LP）模型：max z = 290 xii + 320 x12 + 230 x13 + 280 x14 + 310 x21 + 320 x22 + 260 x23

19、 + 300 x24 + 260 x31 + 250 x32 + 220 x33約束條件：x11 + x12 + x13 + x14 W100 x21 + x22 + x23 + x24 120 x31 + x32 + x33 10030 x11 + x21 + x31 8070 x12 + x22 + x32 14010 x13 + x23 + x33 3010 x14 + x24 50變量均非負(fù)。14模型可以描述為:max z = x p0 x0 i 4 j 4約束條件：4“ Xij h,i =1,2,3 j 13m1j Xj m2j, j =1,2,3,4 i 1X34 = 0變量均非負(fù)

20、。其中 TOC o 1-5 h z 290320230280p=3103202603002602502200_100b= 120：100_m1 = 30 70 10 101m2 - 180 140 30 501(1)按表達(dá)式格式輸入模型。給出輸入模型和求解報(bào)告(比較971 )：輸入的模型：!文件名:p97.lg4;max = 290*x11+320*x12+230*x13+280*x14 +310*x21+320*x22+260*x23+300*x24 +260*x31+250*x32+220*x33;x11+x12+x13+x14100;x21+x22+x23+x24120;x31+x32+

21、x3330;x11+x21+x3170;x12+x22+x3210;x13+x23+x3310;15x14+x2450; end求解報(bào)告:y Solution Report - pSTGlobal pt-iinal solution Xouncl.B700.00D .000000Object ivc value:Infeas ibi1 ities;Total solver iterations:VariableValueReduced CostKll0.00000020.00000XIS100.00000,000000XI30.0000000000區(qū)140.GO2000000X2130 jOQ

22、OOOc.oooooo404000000.000000.onaooo10,00000X2450.00000c.ooooooX3 1SO.DOOOOo. oooooo初工.DOOOOQ20,00000K3330,000000,000000(2)按使用LINGO函數(shù)格式輸入模型。給出輸入模型和求解 報(bào)告(比較97):偎示：把上題的輸入模型作少量修改即可。 輸入的模型：sets!定義集合及變量；R/1.3/:b;!R/1.3/可理解為類型：有3個(gè)元素的數(shù)組。b為定義的變量；C/1.4/:m1,m2;RC(R,C):p,x; !RC(R,C)可理解為3q的數(shù)組類型； endsets data:!對(duì)已知

23、變量賦值;b=100 120 100;m1=30 70 10 10;m2=80 140 30 50;p=290 320 230 280310 320 260 300260 250 220 0; enddatamax=sum(RC:p*x); !min=p(1,1)*x(1,1)+p(1,2)*x(1,2)+p(3,4)*x(3,4);for(R(i):sum(C(j):x(i,j)b(i); !x(i,1)+x(i,2)+x(i,3)+x(i,4)=b(i), im1(j);for(C(j): sum(R(i):x(i,j)m2(j); x(3,4)=0;end求解報(bào)告：16FM Soluti

24、on Eopoct - pDT二叵區(qū)Global optittial Bolutian fouiid. Objective value: I e mm ih i L xt 二曰日: Total solver iterations:8S7D0.0D o.oDaooa 74Uaclab IpB ( 1) B t 2) fi C 3) Ml t L Ml ( 3) Hit 3) (tl ( 4) tl2 1) 43) 叼3) M2 ( 4 F( lf 1 P( 1, 3) P ( b 3) P( 1, 4) P( Zf 】) Pt 2f 2) F( E. 3) F( Z,中 P ( 3, 1) Fl

25、 3, Z) P(3)Fl 3，V JU 1, 1)XI 1, 3)L為 X( Zf 1) 3引 工I 2, 3) SU % 4) 鞏3 1) 工t力2) M 3弘 叼4)Ua lue 100.0000 120,0000 10 . OiOOO 30.00000 70.OOOOO 10 JD0000 10.ooooo 30,00000 140.OOOO 30 SOODOO so.OOO 290.OOOO 320,0000 Z3O.OOOO 2BO.0000 31O.OOOO 320.0000 26O.OOOO 300,0000 26口.OOOO 250,0000 220.0000.OOOO 10

26、0,0000-0000 30,00000 aoooo -0000 SO.IQDOOO 50.00000 0 . 000000 30.00000 .OODDOnPeduced Cost . OOOOO D.OOOOOO ,000000 .OOOOO ,oooooo .ooooo ,oooooo .ooooo ,oooooo , ODOCiaO .oooooo ,oooooo .oooon ,oooooo .ooooo ,oooooo .ooooo ,oooooo .ooooo ,oooooo .ooooo .ooooo .ooo 2n.oooan ,000000 4n口口n20OOOOO ,00

27、000 ,ccoaoo 10,00000 ,000000 ,00000 20.00000 D.DODODO a,0000004.(驗(yàn)證)貨機(jī)裝運(yùn)(LP) p98100模型：決策變量：用xij表示第i種貨物裝入第j個(gè)貨艙的重量(t ),貨艙j=1,2,3分 別表示前倉(cāng)、中倉(cāng)和后倉(cāng)。已知參數(shù)：貨艙j的質(zhì)量限制 WETj,體積限制VOLj；第i種貨物的質(zhì)量wi, 單位質(zhì)量的體積v,利潤(rùn)Pio用行向量表小WET = ( 10, 16, 8 )VOL = (6800, 8700, 5300 )w = ( 18,15, 23, 12 )v = ( 480, 650, 580, 390 )p = (3100

28、, 3800, 3500, 2850 )決策目標(biāo)是最大化總利潤(rùn)，即17444、max z = Pi x-V ）約束條件包括以下4個(gè)方面：1）供裝載的四種貨物的總重量約束，即3、Xj MW, i =1,2,3,4j I2）三個(gè)貨艙的重量限制，即4“ Xij WETj, j =1,2,3i 13）三個(gè)貨艙的空間限制，即4、M% WETfl);a for(c;ing(j): it siun(wu(i):Ar(i)*x(ij)- A OL(j):/rfoi(c；nig(j):foiXcang0c|k#GT#j: !=GT#Jk 大于的含義； $um(wu(i) :x(i JJAVE T (fy=sum

29、(wii(i) :x(i,k)/WET(k);)；end要求： 輸入模型（見(jiàn)99）并求解模型。對(duì)照教材p100的結(jié)果。閱讀LINGO軟件及應(yīng)用.doc和LINGO求解優(yōu)化問(wèn)題.docc19給出模型求解報(bào)告（比較100）:y Solution Report - p99匚后HGlobal optical solution Objective value: Inf easifcii litles:Total soIver iterationsfound.121515.6 .222O446E-15 ie八ModelTitle:貨機(jī)裝運(yùn)（最大值問(wèn)題）VariableWET( 1)ET( 2)IET( 3

30、) 0L( 1) 0L( 2)V0L( 3)1( liW( 4)V( 1) ( 2)V( 3)V( 4)P( 1)P( 2)P( 3)F( 4)X( 1, 1)1, 2)K( 1, 3)X( 2t 1)X( 2, 2)X( 2.3)X( 3, 1)X( 3, 2)X( t 3)X( 4, 1)X( L 2)XC % 3)Value10. 00000 16. 00000 8.000000 6800.000 8700.ODO 5300.00018. OOODO 15. 0000023.00000 12, 0D0D0 480.0000 650.0000 680.0000 39D.OODO 3100.

31、000 3800.000 3500.000 2850.000 0.000000 0. 000000 0.000000 7.OOOOQO 0.000000 8,000000 3.00000012, 94737 口, 000000 0.000000 3.052532 0. 000000Reduced Cost 0. 000000 0,000000 0.000000 0.ODODOO 0. 000000 0.000000 0.000000 0.000000 0. 000000 0. 000000 0 . 000000 0. 000000 0.000000 0. 000000 0.000000 0,0

32、00000 0.0000000. 00000040 0-0000 57.89474 40 0.0000 0.000000 239.4737 0. 000000 0.000000 0. 000000 0.000000 650.0000 0. 000000 650.0000V附：輸入的模型。model:TITLE貨機(jī)裝運(yùn)（最大值問(wèn)題）；!文件名：p99.lg4;!定義集合及變量； setscang/1.3/:WET,VOL; !cang/1.3底示類型：有3個(gè)元素的一維數(shù)組，定義了 兩個(gè)變量；wu/1.4/:w,v,p;link（wu,cang）:x;!link（wu,cang）表示類型：有 4

33、行 3 列的二維數(shù)組；20endsets!對(duì)已知變量賦值;data:WET=10,16,8; VOL=6800,8700,5300;w=18,15,23,12; v=480,650,580,390;p=3100,3800,3500,2850;enddatamax=sum(wu(i):p(i)* sum(cang(j):x(i,j);for(wu(i):sum(cangO):x(i,j)w(i);for(cang(j):sum(wu(i):x(i,j)WET(j);for(cang(j):sum(wu(i):v(i)*x(i,j)VOL(j);for(cang(j):for(cang(k)|k#

34、GT#j: !#GT#是大于的含義;sum(wu(i):x(i,j)/WET(j)= sum(wu(i):x(i,k)/WET(k););end21附1:實(shí)驗(yàn)提示LINGO語(yǔ)法：基本語(yǔ)法.程序以“model號(hào)始，最后以“endg束（兩者均可省略）；. TITLE為標(biāo)題注釋，！為一般注釋；.字母不區(qū)分大小寫；.每條語(yǔ)句必須以分號(hào)”;結(jié)束（英文分號(hào)）；.默認(rèn)決策變量均為非負(fù)；. 洲 =、=形式輸入，它們與 、等效；.乘號(hào)*不能省略；.輸入模型中第1行為目標(biāo)函數(shù)，milk、time、cpct盟對(duì)各約束條件命名， 便于從輸出結(jié)果中查找相應(yīng)信息（缺省時(shí)，LINGO自動(dòng)用數(shù)字按順序?qū)s束 條件命名）；.

35、LINGO模型文件一般以LG4為后綴名。22附2:第4章數(shù)學(xué)規(guī)劃模型（一） 854.1奶制品的生產(chǎn)與銷售第 T量_ _數(shù)學(xué)規(guī)劃模型在上一章中我們看到，建立優(yōu)化模型要確定優(yōu)化的目標(biāo)和尋求的決策.用工 表示決策變量（#）表示目標(biāo)函數(shù).實(shí)際問(wèn)題一般對(duì)決策變量卡的取值范圍有限 制，不妨記作X e 稱為可行域.優(yōu)化問(wèn)題的數(shù)學(xué)模型可表示為min（或 max）f（x），工 w。在第3章/通常是1維或2維變量，n通常是1維或2維的非負(fù)域.實(shí)際中的優(yōu)化問(wèn)題通常有多個(gè)決策變暴，用虐雄向景一（O,寶，.） 表示，目標(biāo)函數(shù)/（工）是多元函數(shù)，可行域門比較復(fù)雜，常用一組不等式（也可以 有等式）鼠（父）三0仆=1,2,，

36、切）來(lái)界定，稱為約束條件.一般地，這類模型可表 述成如下形式min z =J（x）與，匚旦（工）毛0, = 1 ,2 ,m 這里的s,匕（mubjst W ）是受約束于的意思.威然，上述模型屬于多元函數(shù)的條件極值問(wèn)題的范圍,然而許多實(shí)際問(wèn)題歸 結(jié)出的這種形式的優(yōu)化模型，其決策變量個(gè)數(shù)n和約束條件個(gè)數(shù)穆一般較大， 并且最優(yōu)解往往在可行域的邊界上取得，這樣就不能簡(jiǎn)單地用微分法求解，數(shù)學(xué) 規(guī)劃是解決這類問(wèn)題的有效方法.需要指出的是，本章無(wú)意涉及數(shù)學(xué)規(guī)劃（或運(yùn)籌學(xué)）的具體計(jì)算方法，仍然 著重于從數(shù)學(xué)建模的角度，介紹如何建立若干實(shí)際優(yōu)化問(wèn)題的模型,并且在用現(xiàn) 成的數(shù)學(xué)軟件求解后，對(duì)結(jié)果作一些分析4.1奶

37、制品的生產(chǎn)與銷售企業(yè)內(nèi)部的生產(chǎn)計(jì)劃有各種不同的情況.從空間層次看，在工廠級(jí)要根據(jù)外 部需求和內(nèi)部設(shè)備、人力、原料等條件，以最大利潤(rùn)為目標(biāo)制訂產(chǎn)品的生產(chǎn)計(jì)劃， 在車間級(jí)則要根據(jù)產(chǎn)品生產(chǎn)計(jì)劃、工藝流程、資源約束及費(fèi)用參數(shù)等，以最小成 本為目標(biāo)制訂生產(chǎn)作業(yè)計(jì)劃.從時(shí)間層次看，若在短時(shí)間內(nèi)認(rèn)為外部需求和內(nèi)部 資源等不隨時(shí)間變化，可制訂單階段生產(chǎn)計(jì)劃，否則就要制訂多階段生產(chǎn)計(jì)劃，2386 例1加工奶制品的生產(chǎn)計(jì)劃本節(jié)選擇幾個(gè)單階段生產(chǎn)計(jì)劃的實(shí)例，說(shuō)明如何建立這類問(wèn)題的數(shù)學(xué)規(guī)劃 模型，利用軟件求解并對(duì)輸出結(jié)果作一些分析.例1 加工奶制品的生產(chǎn)計(jì)劃問(wèn)題 一奶制品加工廠用牛奶生產(chǎn)AltA.兩種奶制品/桶牛奶可

38、以在甲 類設(shè)備上用12 h加工成3 kg 或者在乙類設(shè)備上用8 h加工成4 kg A史.根據(jù) 市場(chǎng)需求，生產(chǎn)的AIfA2全部能售出.且每千克%獲利24元，每千克A獲利 16元.現(xiàn)在加工廠每天能得到50桶牛奶的供應(yīng).每天正式工人總的勞動(dòng)時(shí)間為 480 h,并且甲類設(shè)備每天至多能加工100 kg A，乙類設(shè)備的加工能力沒(méi)有限制. 試為該廠制訂一個(gè)生產(chǎn)計(jì)劃，使每天獲利最大，并進(jìn)一步討論以下3個(gè)附加 問(wèn)題：1）若用35元可以買到1桶牛奶，應(yīng)否作這項(xiàng)投資？若投資,每天最多購(gòu)買 多少桶牛奶？2）若可以聘用臨時(shí)工人以增加勞動(dòng)時(shí)間，付給臨時(shí)工人的工資最多是每小 時(shí)幾元？3）由于市場(chǎng)需求變化,每千克%的獲利增加

39、到30元,應(yīng)否改變生產(chǎn)計(jì)劃？ 問(wèn)題分析這個(gè)優(yōu)化問(wèn)題的目標(biāo)是使每天的獲利最大，要做的決策是生產(chǎn) 計(jì)劃，即每天用多少桶牛奶生產(chǎn)A-用多少桶牛奶生產(chǎn)A,（也可以是每天生產(chǎn) 多少千克兒,多少，千克A.,決策受到3個(gè)條件的限制：原料（牛奶）供應(yīng)、勞動(dòng) 時(shí)間、甲類設(shè)備的加工能力.按照題目所給，將決策變量、目標(biāo)函數(shù)和約束條件用 數(shù)學(xué)符號(hào)及式子表示出來(lái)，就可得到下面的模型.基本模型決策變:設(shè)每天用O桶牛奶生產(chǎn)A一用物桶牛奶生產(chǎn)冬.目標(biāo)函數(shù)；設(shè)每天獲利為片元.與桶牛奶可生產(chǎn)3盯kg A3獲利24x3%,均 桶牛奶可生產(chǎn)4町kg A工，獲利16 x4/，故”72。+64、約束條件：原料供應(yīng) 生產(chǎn)A1,A）的原料（

40、牛奶）總量不得超過(guò)每天的供應(yīng)，即 町十fW50 ：勞動(dòng)時(shí)間 生產(chǎn)A, .A：的總加工時(shí)間不得超過(guò)每天正式工人總的勞動(dòng)時(shí) 間，即 12% +8巧 W480；設(shè)備能力 A、的產(chǎn)星不得超過(guò)甲類設(shè)備每天的加工能力,即3%宅100；非負(fù)約束 看,盯均不能為負(fù)值，即孫N0,3三0.練上可得 TOC o 1-5 h z max z = 72x1 + 64典（1 ）s t. + x2 W50（ 2）12勺+8與 480（3）24(4)這就是該問(wèn)題的基本模型,由于目標(biāo)函數(shù)和約束條件對(duì)于決策變域而言都是線 性的，所以稱為線性裁劃（Linear Programming,簡(jiǎn)記作LP）.模型分析與假設(shè)從本章下面的實(shí)例可

41、以看到，許多實(shí)際的優(yōu)化問(wèn)題的數(shù)學(xué)模型都是線性規(guī) 劃（特別是在像生產(chǎn)計(jì)劃這樣的經(jīng)濟(jì)管理領(lǐng)域），這不是偶然的.讓我們分析一 下線性規(guī)劃具有哪些特征，或者說(shuō)，實(shí)際問(wèn)題具有什么性質(zhì)，其模型才是線性 規(guī)劃.比例性每個(gè)決策變量對(duì)目標(biāo)函數(shù)的貢獻(xiàn)與該決策變量的取值成正 比#每個(gè)決策變量對(duì)每個(gè)約束條件右端項(xiàng)的“貢獻(xiàn)”，與該決策變量的取值成 正比.可加性各個(gè)決策變量對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”，與其他決策變最的取值無(wú) 關(guān);各個(gè)決策變量對(duì)每個(gè)約束條件右端項(xiàng)的“貢獻(xiàn)”，與其他決策變量的取值 無(wú)關(guān).連續(xù)性 每個(gè)塊策變量的取值是連續(xù)的.比例性和可加性保證了目標(biāo)函數(shù)和約束條件對(duì)于決策變量的線性性，連續(xù) 性則允許得到?jīng)Q策變量的實(shí)數(shù)最

42、優(yōu)解.對(duì)于本例，能建立上面的線性規(guī)劃模型，實(shí)際上是事先作了如下的假設(shè)：L A,AZ兩種奶制品每千克的獲利是與它們各自產(chǎn)量無(wú)關(guān)的常數(shù).每桶牛 奶加工出AttA3的數(shù)量和所需的時(shí)間是與它們各自的產(chǎn)量無(wú)關(guān)的常數(shù)：AtA2每千克的獲利是與它們相互間產(chǎn)量無(wú)關(guān)的常數(shù)，每插牛奶加工出 A, ,A7的數(shù)量和所需的時(shí)間是與它們相互間產(chǎn)量無(wú)關(guān)的常數(shù)；3,加工A一儲(chǔ)的牛奶的桶數(shù)可以是任意實(shí)數(shù).這3條假設(shè)恰好保證了上面的3條性質(zhì).當(dāng)然，在現(xiàn)實(shí)生活中這些假設(shè)只是 近似成立的，比如，AAa的產(chǎn)量很大時(shí)，自然會(huì)使它們每千克的獲利有所減少由于這些假設(shè)對(duì)于書中給新的、經(jīng)過(guò)簡(jiǎn)化的實(shí)際問(wèn)題是如此明顯地成立，本 章下面的例題就不再列

43、出類似的假設(shè)了 .不過(guò)，讀者在打算用線性規(guī)劃模型 解決現(xiàn)實(shí)生活中的實(shí)際問(wèn)題時(shí)，應(yīng)該考慮上面3條性質(zhì)是否近似地滿足模型求解圖解法 這個(gè)線性規(guī)劃模型的決策變陸為2維，用圖解法既簡(jiǎn)單，又便于直 觀地把握線性規(guī)劃的基本性質(zhì).將約束條件（2）、（5）中的不等號(hào)改為等號(hào)，可知它們是孫。巧平面上的5 條直線，依次記為5 人,如圖1.其中LAtL,分別是孫軸和如軸，并且不難判 斷，（2） （5）式界定的可行域是5條直線上的線段所圍成的5邊形OABCD.容25易算出，5 個(gè)頂點(diǎn)的坐標(biāo)為：。（0,。）工（0,50） ,E（2O,3O） , C（ 100/3, 10）, D（100/3,0）.-目標(biāo)函數(shù)（1）中的工

44、取不同數(shù)值時(shí)，在圖1中表示一組平行直線（虛線），稱 等值線族.如工工0是過(guò)。點(diǎn)的直線， 蕓二2 400是過(guò)。點(diǎn)的直線，工=3 040是過(guò) C點(diǎn)的直線，可以看出，當(dāng)這族平行 線向右上方移動(dòng)到過(guò)B點(diǎn)時(shí)力=3 360, 達(dá)到最大值，所以R點(diǎn)的坐標(biāo)（2。，30） 即為最優(yōu)解法=20,2=30.我們直觀地看到，由于目標(biāo)函數(shù)和約束條件都是線性函數(shù)，在2維情形，可行、域?yàn)橹本€段圍成的凸多邊形，目標(biāo)函數(shù)的 等值線為直線，于是最優(yōu)解一定在凸多邊形的某個(gè)頂點(diǎn)取得,圖I模型的圖解法推廣到維情形，可以猜想，最優(yōu)解會(huì)在約束條件所界定的一個(gè)凸多面體 （可行域）的某個(gè)頂點(diǎn)取得.線性規(guī)劃的理論告訴我們，這個(gè)猜想是正確的：軟件

45、實(shí)現(xiàn) 求解線性規(guī)劃有不少現(xiàn)成的數(shù)學(xué)軟件，比如用LINGO軟件就可 以很方便地實(shí)現(xiàn).在LINGO下新建一個(gè)模型文件（即LINGO程序，一般以 “LG4”為后綴名）,像書寫模型（1）（5）一樣,直接輸入；mode 1：max = 72 * xl + 64 * x2 ;milk xl + x2 50 ；t ime 12 * xl + 8 * x2 480 ；cpct S * xl =”形式輸入，它們與“父” J等效輸入模型中第1行 為目標(biāo)函數(shù)milk、 time、 cpct是為F對(duì)各約束條件命名，便于從輸出結(jié)果 中查找相應(yīng)信息（也可以不對(duì)約束命名，此時(shí)LING。會(huì)自動(dòng)用數(shù)字按順序?qū)s 束條件命名）.

46、將文件存儲(chǔ)并命名后，選擇菜單“UNCOISolv/執(zhí)行，即可得到如下輸出：Global optimal solution found,Objective value：3360.0。882689結(jié)果分析Total solver iterations：VariableValue Reduced Cost20,000000.00000030,000000.000000Row Slack or SurplusDual Price1.00000048.000002.0000000.00000013360.000MILK0.000000TIME0.000000CPCT40,00000上面結(jié)果的前3行告訴我

47、們，LINGO求出了模型的全局最優(yōu)解（Global optimal solution），最優(yōu)值為3 360（即最大利潤(rùn)為3 360元），迭代次數(shù)為2 次,接下來(lái)的3行告訴我們，這個(gè)線性規(guī)劃的最優(yōu)解為為=20. =30（即用20 桶牛奶生產(chǎn)Ai ,30桶牛奶生產(chǎn)Ad 對(duì)其中“Reduced Cost”的含義，將在例2 中結(jié)合問(wèn)題3）的討論進(jìn)行說(shuō)明.結(jié)果分析上面的輸出中除了告訴我們問(wèn)題的最優(yōu)解和最優(yōu)值以外，還有許多對(duì)分析 結(jié)果有用的信息，下面結(jié)合題目中提出的3個(gè)附加問(wèn)題，并利用圖解法的直觀給 予說(shuō)明.（1） 3個(gè)約束條件的右端不妨看作3種資源原料、勞動(dòng)時(shí)間、甲類設(shè)備 的加工能力.輸出第8 -11行

48、Slack or Surplu區(qū)給出這3種資源在最優(yōu)解下是否 有剩余：原料MILK,勞動(dòng)時(shí)間TIME的剩余均為。,甲類設(shè)備CPCT尚余 40 kg加工能力.這與圖解法的如下結(jié)果一致：最優(yōu)解在B點(diǎn)（圖1中約束條件 2,3所定義的直線。和L2的交點(diǎn)）取得，表明原料、勞動(dòng)時(shí)間已用完，而甲類設(shè) 備的能力有余,一般稱“資源”剩余為。的約束為緊約束（有效約束）,（2）目標(biāo)函數(shù)可以看作“效益”，成為緊約束的“資源”一旦增加效益”必 然跟著增長(zhǎng),輸出第8 -11行Dual Prices給出這3種資源在最優(yōu)解下“資源”增 加1個(gè)單位時(shí)“效益”的增量：原料MILK增加1個(gè)單位（1桶牛奶）時(shí)利潤(rùn)增長(zhǎng) 48元，勞動(dòng)時(shí)

49、間TIME增加I個(gè)單位（1 h）時(shí)利潤(rùn)增長(zhǎng)2元，而增加非緊約束 CPCT甲類設(shè)備的能力顯然不會(huì)使利潤(rùn)增長(zhǎng).這里，“效益”的增量可以看作 “貸源”的潛在價(jià)值，經(jīng)濟(jì)學(xué)上稱為影子價(jià)格，即1桶牛奶的影子價(jià)格為48元, 1 h勞動(dòng)的影子價(jià)格為2元，甲類設(shè)備的影子價(jià)格為0.讀者可以用直接求解的辦法驗(yàn)證上面的結(jié)論，即將輸入文件中原料約束 MILK右端的50改為51，看看得到的最優(yōu)值（利潤(rùn)）是否恰好增長(zhǎng)48元，用影子價(jià)格的概念很容易回答附加問(wèn)題1）:用35元可以買到1桶牛奶，低 于1桶牛奶的影子價(jià)格，當(dāng)然應(yīng)該做這項(xiàng)投資.類似地，可以回答附加問(wèn)題2）：27聘用臨時(shí)工人以增加勞動(dòng)時(shí)間，付給的工資低于勞動(dòng)時(shí)間的影子

50、價(jià)格才可以增 加利潤(rùn)，所以工資最多是每小時(shí)2.元.（3）目標(biāo)函數(shù)的系數(shù)發(fā)生變化時(shí)（假定約束條件不變），最優(yōu)解和最優(yōu)值會(huì) 改變嗎？這個(gè)問(wèn)題不能簡(jiǎn)單地回答.從圖1看，目標(biāo)函數(shù)的系數(shù)決定了等值線族 的斜率，原題中該斜率（取絕對(duì)值，下同）為72/64 =9/8,介于直線L1的斜率1 與的斜率3/2之間,最優(yōu)解自然在Lx和L2的交點(diǎn)B取得.并且只要目標(biāo)函 數(shù)系數(shù)的變化使得等值線族的斜率仍然在（1 .3/2）范圉內(nèi)，這個(gè)最優(yōu)解就不會(huì) 改變.而當(dāng)目標(biāo)函數(shù)系數(shù)的變化使得等值線族的斜率小于1時(shí)，最優(yōu)解將在4點(diǎn) 取得，大于3/2時(shí)，最優(yōu)解將在C點(diǎn)取得.這種對(duì)目標(biāo)函數(shù)系數(shù)變化的影響的討論，通常稱為對(duì)目標(biāo)函數(shù)系數(shù)的敏

51、感 性分析.LINGO在缺省設(shè)置中不會(huì)給出這種敏感性分析結(jié)果，但可以通過(guò)修改 LINGO選項(xiàng)得到.具體作法是：選擇LINGO I Options”菜單，在彈出的選項(xiàng)卡中 選擇“ General Solvbi然后找到選項(xiàng)“ Dual CompiitalionSH，在下拉框中選中 Prices & Ranges,應(yīng)用或保存設(shè)置.重新運(yùn)行“ LINGO I Solve,然后選擇“ LINGO I菜單，則得到如下輸出:Ranges in which the basis is unchanged：Objective CoefficientVariableXIX2CurrentCoefficient72.

52、0000064.00000AllowableIncrease24.000008.000000RangesAllowableDecrease 8.000000 16.00000Righthand Side RangesRow CurrentAllowableAllowableRHSIncreaseDecreaseMILK50.00000TIME480,0000CPCT100.000010.0000053,33333INFINITY6.66666780*0000040,00000上面輸出的第2 6行“Current Coefticient（當(dāng)前系數(shù)）對(duì)應(yīng)的Allowable Increase*和A

53、llowable Decrease給出了最優(yōu)解不變條件下目標(biāo)函數(shù)系數(shù)的允許變化范圍內(nèi)的系數(shù)為（72 -8,72 +24）,即（64,96）；峋的系數(shù)為（64 - 16,64 + 8）,即（48,72）.注意色系數(shù)的允許范圍需要看系數(shù)64不變，反之亦然.用這個(gè)結(jié)果很容易回答附加問(wèn)題3）：若每千克A1的獲利增加到30元，則 航系數(shù)變?yōu)?0 *3 =90,在允許范圍內(nèi)，所以不應(yīng)改變生產(chǎn)計(jì)劃，（4）對(duì)-資源”的影子價(jià)格作進(jìn)一步的分析.從圖1看，隨著原料（牛奶）的增加，直線/向右上方平移出 與4的交點(diǎn)次它仍是最優(yōu)解）向A點(diǎn)靠近，在902891 例2奶制品的生產(chǎn)銷售計(jì)劃這個(gè)過(guò)程中，每增加I桶牛奶利潤(rùn)增長(zhǎng)4

54、8元（影子彷格）.但是，當(dāng)B點(diǎn)與八點(diǎn) 重合后再增加牛奶就不可能使利潤(rùn)增長(zhǎng)了.這就是說(shuō)，影子價(jià)格的作用（即在最 優(yōu)解下“資源增加】個(gè)單位時(shí)“效益”的增量）是有限制的.這種對(duì)影子價(jià)格在 什么條件下才有意義的討論，通常稱為對(duì)資源約束右端項(xiàng)的敏感性分析.上面輸 出的第712行“Current RH5（當(dāng)前右端項(xiàng)）對(duì)應(yīng)的Allowable IncreaW 和AL lowable Decrmse”給出了影子價(jià)格有意義條件下約束右端項(xiàng)的限制范圍：原料 MILK最多增加10桶牛奶，勞動(dòng)時(shí)間TIME最多增加53.3民現(xiàn)在可以回答附加問(wèn)題1）的第2問(wèn)：雖然應(yīng)該批準(zhǔn)用35元買1桶牛奶的 投資，但每天最多購(gòu)買1。桶牛

55、奶,類似地,可以用低于2元/h的工貿(mào)聘用臨時(shí) 工人以增加勞動(dòng)時(shí)間.但最多增加53. 3 h*需要注意的是：一般情況下LINGO給出的敏感性分析結(jié)果只是充分條件, 如上述“最多增加10桶牛奶”應(yīng)理解為“增加10桶牛奶”一定是有利可圖的，但 并不意味著“增加10桶以上的牛奶”一定不是有利可圖的（對(duì)最大可增加的勞 動(dòng)時(shí)間也應(yīng)該類似地理解），只是此時(shí)無(wú)法通過(guò)敏感性分析直接得到結(jié)論，而需 要看新求解新的模型進(jìn)行判斷.以后我們對(duì)此不再特別進(jìn)行說(shuō)明（同樣，對(duì)目標(biāo) 函數(shù)系數(shù)給出的敏感性分析結(jié)果也只是充分條件）.評(píng)注本例在產(chǎn)品利潤(rùn)、加工時(shí)間等參數(shù)均可設(shè)為常數(shù)的情況下,建立了線 性規(guī)劃模型.線性規(guī)劃模型的三要素是

56、：決策變量、目標(biāo)函數(shù)和約束條件.線性規(guī) 劃模型可以方便地用LINGO軟件求解，得到內(nèi)容豐富的輸出，而且利用其中的 影子價(jià)格和敏感性分析，可對(duì)模型結(jié)果作進(jìn)一步的研究，它們對(duì)實(shí)際問(wèn)題常常是 十分有益的.例2 奶制品的生產(chǎn)銷售計(jì)劃問(wèn)題 例I給出的A、，A3兩種奶制品的生產(chǎn)條件,利潤(rùn)及工廠的“資源”限 制全都不變,為增加工廠的獲利，開(kāi)發(fā)了奶制品的深加工技術(shù)；用2 h和3元加 工費(fèi)，可將1 kg Z加工成0.8 kg高級(jí)奶制品，也可將1 kg A.加工成6 75 kg 高級(jí)奶制品B,每千克瓦能獲利44元，每千克能獲利32元.試為該廠制訂 一個(gè)生產(chǎn)銷售計(jì)劃，使每天的凈利潤(rùn)最大，并討論以下問(wèn)題：（1）若投資

57、30元可以增加供應(yīng)1桶牛奶，投資3元可以增加1 h勞動(dòng)時(shí)間， 應(yīng)否作這些投資？若每天投資150元,可賺回多少？（2）每千克高級(jí)奶制品B1 ,B1的獲利經(jīng)常有10%的波動(dòng)，對(duì)制訂的生產(chǎn)銷 售計(jì)劃有無(wú)影響？若每千克用的獲利下降10%,計(jì)劃應(yīng)該變化嗎？（3）若公司已經(jīng)簽訂了每天銷售10 kg的合同并且必須滿足，該合同對(duì)公 司的利潤(rùn)有什么影響？何題分析要求制訂生產(chǎn)銷售計(jì)劃,決策變量可以像例門那樣，取作每天用 多少桶牛奶生產(chǎn)A1,A1再添上用多少千克A,加工瓦，用多少千克A工加工B?,2992題2(1)答案但是由于問(wèn)題要分析b(1b3的獲利對(duì)生產(chǎn)銷售計(jì)劃的影響，所以決策變量取作 每天的銷售量更方便.目標(biāo)

58、函數(shù)是工廠每天的凈利潤(rùn)b,.b3的獲利之和扣除深加工費(fèi)用.約束條件基本不變，只是要添上A1tA2深加 工時(shí)間的約束.在與例1類似的假定下用線性規(guī)劃模型解決這個(gè)問(wèn)題.基本模型決策變:設(shè)每天銷售.kg Aj/2 kg Aa.x, kg Bl kg 用灼kg A(加工B) kg A?加工B式增設(shè)%也可使下面的模型簡(jiǎn)單).目標(biāo)函數(shù)：設(shè)每天凈利澗為3容易寫出z =24/ + 16% +44% +32% -3xs - 3x6,約束條件：原料供應(yīng) 每天生產(chǎn)A,+/kg,用牛奶(孫+x5)/3桶，每天生產(chǎn)Ag +見(jiàn)網(wǎng),用牛奶(的+打)/4桶，二者之和不得超過(guò)每天的供應(yīng)量50桶；勞動(dòng)時(shí)間 每天生產(chǎn)A-A?的時(shí)間

59、分別為4(如+0)和2(知+&),加工BltB2的時(shí)間分別為2%和2人，二者之和不得超過(guò)總的勞動(dòng)時(shí)間480 h；設(shè)備能力 A1的產(chǎn)量3+%不得超過(guò)甲類設(shè)備每天的加工能力100 kg；非負(fù)約束 孫，3，,x6均為非負(fù).附加約束 】kg A,加工成0.8381,故事=08%,類似地處=0.75駕.由此得基本模型： TOC o 1-5 h z max z = 24/ + 16/ + 44/ + 324 - 3xs -3q(6)s. t. + ； W50(7)344(孫 +如)+2(% +/)+2%+2*6 =30；xll + x21 + x31 =70;xl2 + x22 +x32 = 10 ；xl

60、3 + x23 + x33 =10;xl4 + x24 作這樣的簡(jiǎn)化后得到的解沒(méi)有任何9735例2貨機(jī)裝運(yùn)變化.評(píng)注 本題考慮的是將某種物質(zhì)從若干供應(yīng)點(diǎn)運(yùn)往一些需求點(diǎn)，在供需量 約束條件下使總費(fèi)用最小或總利潤(rùn)最大.這類問(wèn)題一般稱為運(yùn)輸問(wèn)建，是線性規(guī) 劃應(yīng)用最廣泛的領(lǐng)域之一.在標(biāo)準(zhǔn)的運(yùn)輸問(wèn)題中，供需量通常是平衡的，即供應(yīng) 點(diǎn)的總供應(yīng)曷等于需求點(diǎn)的總需求最.本題中供需量不平衡，但這并不會(huì)引起本 質(zhì)的區(qū)別，同樣可以方便地建立線性規(guī)劃模型求解.例2貨機(jī)裝運(yùn)問(wèn)匣 某架貨機(jī)有三個(gè)貨艙：前倉(cāng)、中倉(cāng)、后倉(cāng).三個(gè)貨艙所能裝載的貨物的 最大質(zhì)量和體積都有限制，如表3所示.并且為了保持機(jī)的平衡，三個(gè)貨艙中 實(shí)際裝載