運(yùn)籌學(xué)優(yōu)化建摸

運(yùn)籌帷幄之中決勝千里之外運(yùn)籌學(xué)課件緒論Introduction線(xiàn)性規(guī)劃數(shù)學(xué)規(guī)劃非線(xiàn)性規(guī)劃整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃學(xué)科內(nèi)容多目標(biāo)規(guī)劃雙層規(guī)劃組合優(yōu)化最優(yōu)計(jì)數(shù)問(wèn)題網(wǎng)絡(luò)優(yōu)化排序問(wèn)題統(tǒng)籌圖隨機(jī)優(yōu)化對(duì)策論排隊(duì)論庫(kù)存論決策分析可靠性分析運(yùn)籌學(xué)的主要內(nèi)容線(xiàn)性規(guī)劃模型（1）線(xiàn)性(linearprogramming)規(guī)劃主要解決：如何利用現(xiàn)有的資源，使得預(yù)期目標(biāo)達(dá)到最優(yōu)。某公司計(jì)劃制造Ⅰ、Ⅱ兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)備A、B的臺(tái)時(shí)、調(diào)試工序及每天可用于這兩種家電的能力、各售出一件時(shí)的獲利情況，如表1-1所示。問(wèn)該公司應(yīng)制造兩種家電各多少件，使獲取的利潤(rùn)最大？項(xiàng)目ⅠⅡ每天可用能力設(shè)備A(h)設(shè)備B(h)調(diào)試工序(h)06152115245利潤(rùn)（元）21表1-1解：設(shè)公司制造Ⅰ、Ⅱ兩種家電分別為件。問(wèn)題：x1=?x2=?利潤(rùn)Z最大？線(xiàn)性規(guī)劃模型（1）線(xiàn)性規(guī)劃模型設(shè)備A工時(shí)限制：設(shè)備B工時(shí)限制：項(xiàng)目ⅠⅡ每天可用能力設(shè)備A(h)設(shè)備B(h)調(diào)試工序(h)06152115245利潤(rùn)（元）21表1-1項(xiàng)目ⅠⅡ每天可用能力設(shè)備A(h)設(shè)備B(h)調(diào)試工序(h)06152115245利潤(rùn)（元）21表1-1線(xiàn)性規(guī)劃模型調(diào)試工序時(shí)間限制：利潤(rùn)：即要求：目標(biāo)函數(shù)約束條件資源約束非負(fù)約束線(xiàn)性規(guī)劃模型（1）初試LINDO解如下LP問(wèn)題:

LINDO

中己假設(shè)所有的變量都是非負(fù)的,所以非負(fù)約束條件不必再輸入到計(jì)算機(jī)中;LINDO也不區(qū)分變量中的大小寫(xiě)字符(實(shí)際上任何小寫(xiě)字符都將被轉(zhuǎn)換為大寫(xiě)字符);約束條件中的“<=”及“>=”可用“<”及“>”代替.上述問(wèn)題用鍵盤(pán)輸入如下線(xiàn)性規(guī)劃模型（1）：MAX2X1+3X2?

ST(說(shuō)明:也可寫(xiě)成S.T.,

SUCHTHAT

或SUBJECTTO

等）?5X2<15?6X1+2X2<24

?X1+X2<5?

END

：GO線(xiàn)性規(guī)劃模型（1）線(xiàn)性規(guī)劃模型（3）LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)8.500000VARIABLEVALUEREDUCEDCOST

X1

3.5000000.000000

X2

1.500000

0.000000ROWSLACKORSURPLUSDUALPRICES2)7.5000000.0000003)0.0000000.2500004)0.0000000.500000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?線(xiàn)性規(guī)劃模型（2）捷運(yùn)公司在下一年度的1～4月份的4個(gè)月內(nèi)擬租用倉(cāng)庫(kù)堆放物資。已知各月份所需倉(cāng)庫(kù)面積列于下表1-2。倉(cāng)庫(kù)租借費(fèi)用隨合同期而定，期限越長(zhǎng)，折扣越大，具體數(shù)字見(jiàn)表1-3。租借倉(cāng)庫(kù)的合同每月初都可辦理，每份合同具體規(guī)定租用面積和期限。因此該廠可根據(jù)需要，在任何一個(gè)月初辦理租借合同。每次辦理時(shí)可簽一份合同，也可簽若干份租用面積和租用期限不同的合同。試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所租借費(fèi)用最少。線(xiàn)性規(guī)劃模型（2）月份

1234所需倉(cāng)庫(kù)面積15102012表1-2表1-3合同租借期限

1個(gè)月2個(gè)月3個(gè)月4個(gè)月合同期內(nèi)的租費(fèi)2800450060007300單位：100m2單位；元/100m2解：設(shè)表示捷運(yùn)公司在第i(i=1,2,3,4)月初簽訂的租期為j(j=1,2,3,4)個(gè)月的倉(cāng)庫(kù)面積的合同（單位為100m2)。ⅠⅡⅢⅣⅤ∑≥15∑≥10∑≥20∑≥12目標(biāo)函數(shù)約束條件線(xiàn)性規(guī)劃模型（2）:min2800x11+2800x21+2800x31+2800x41+4500x12+4500x22+4500x32+6000x13+6000x23+7300x14?st?x11+x12+x13+x14>15?x12+x13+x14+x21+x22+x23>10?x13+x14+x22+x23+x31+x32>20?x14+x23+x32+x41>12?end:go線(xiàn)性規(guī)劃模型（2）LPOPTIMUMFOUNDATSTEP3OBJECTIVEFUNCTIONVALUE1)118400.0VARIABLEVALUEREDUCEDCOSTX113.0000000.000000X210.0000002800.000000X318.0000000.000000X410.0000001100.000000X120.0000001700.000000X220.0000001700.000000X320.0000000.000000X130.000000400.000000X230.0000001500.000000X1412.0000000.000000線(xiàn)性規(guī)劃模型（2）整

數(shù)

規(guī)

劃

在許多線(xiàn)性規(guī)劃問(wèn)題中,要求最優(yōu)解必須取整數(shù).例如所求的解是機(jī)器的臺(tái)數(shù)、人數(shù)車(chē)輛船只數(shù)等.對(duì)于一個(gè)規(guī)劃問(wèn)題,如果要求全部決策變量都取整數(shù),稱(chēng)為純(或全)整數(shù)規(guī)劃;如果僅要求部分決策變量取整數(shù),稱(chēng)為混合整數(shù)規(guī)劃問(wèn)題.有的問(wèn)題要求決策變量?jī)H取0或l兩個(gè)值,稱(chēng)為0-l規(guī)劃問(wèn)題.

整數(shù)規(guī)劃(integerprogramming)簡(jiǎn)稱(chēng)為IP問(wèn)題.這里主要討論的是整數(shù)線(xiàn)性規(guī)劃問(wèn)題,簡(jiǎn)稱(chēng)為ILP問(wèn)題.例2.0.1

某廠擬用集裝箱托運(yùn)甲乙兩種貨物,每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制見(jiàn)表2.1.問(wèn)每集裝箱中兩種貨物各裝多少箱,可使所獲利潤(rùn)最大?貨物/箱體積/米3重量/百斤利潤(rùn)/百元甲5220乙4510托運(yùn)限制/集裝箱2413表2.1表2.1貨物/箱體積/米3重量/百斤利潤(rùn)/百元甲5220乙4510托運(yùn)限制/集裝箱2413解

設(shè)

分別為甲、乙兩種貨物的托運(yùn)箱數(shù).則這是一個(gè)純整數(shù)規(guī)劃問(wèn)題.其數(shù)學(xué)模型為:求解整數(shù)規(guī)劃IP（整數(shù)規(guī)劃）問(wèn)題的輸入與LP類(lèi)似，但在END標(biāo)志后需定義整型變量。0-1型整數(shù)變量可用INTEGER（可簡(jiǎn)寫(xiě)為INT）命令來(lái)標(biāo)示；其它整數(shù)變量可用GIN命令來(lái)標(biāo)示.標(biāo)示方法有兩種：1）INTEGERVname

或GINVname表示將變量Vname標(biāo)示為0-1型或?yàn)橐话阏麛?shù)變量。2）INTn或GINn表示將當(dāng)前模型中前n個(gè)變量標(biāo)示為0-1型變量或?yàn)橐话阏麛?shù)變量。例3

求解0-1整數(shù)規(guī)劃:max3x1-2x2+5x3?st?x1+2x2-x3<2?x1+4x2+x3<4?x1+x2<3?4x2+x3<6?end:intx1:intx2:intx3:goInt3LINDO輸出下列結(jié)果：

LPOPTIMUMFOUNDATSTEP2OBJECTIVEVALUE=8.00000000NEWINTEGERSOLUTIONOF8.00000000ATBRANCH0PIVOT2RE-INSTALLINGBESTSOLUTION...OBJECTIVEFUNCTIONVALUE1)8.000000VARIABLEVALUEREDUCEDCOSTX1

1.000000-3.000000X2

0.0000002.000000X3

1.000000-5.000000ROWSLACKORSURPLUSDUALPRICES2)

2.0000000.0000003)

2.0000000.0000004)

2.0000000.0000005)

5.0000000.000000例4

求解0-1整數(shù)規(guī)劃在LINDO中輸入下列命令：:min3x1+7x2-x3+x4?st?2x1-x2+x3-x4>1?x1-x2+6x3+4x4>8?5x1+3x2+x4>5?end:int4:goLINDO輸出下列結(jié)果：

LPOPTIMUMFOUNDATSTEP4OBJECTIVEVALUE=2.10526323NEWINTEGERSOLUTIONOF3.00000000ATBRANCH0PIVOT4RE-INSTALLINGBESTSOLUTION...OBJECTIVEFUNCTIONVALUE1)3.000000VARIABLEVALUEREDUCEDCOSTX1

1.0000003.000000X2

0.0000007.000000X3

1.000000-1.000000X4

1.0000001.000000ROWSLACKORSURPLUSDUALPRICES2)

1.0000000.0000003)

3.0000000.0000004)

1.0000000.000000例5求解下列整數(shù)線(xiàn)性規(guī)劃問(wèn)題在LINDO中輸入下列命令：:MINX1+X2+X3+X4+X5+X6?ST?X2+2X3+3X4+4X5+5X6>10000?6X1+5X2+3X3+2X4+X5>20000?END:GIN6:GOLINDO運(yùn)行后輸出以下結(jié)果：STATUS：OPTIMALLPOPTIMUMFOUNDATSTEP3OBJECTIVEVALUE=5200.00000FIXALLVARS.(4)WITHRC>0.400000E-01NEWINTEGERSOLUTIONOF5200.00000ATBRANCH0PIVOT3BOUNDONOPTIMUM:5200.000ENUMERATIONCOMPLETE.BRANCHES=0PIVOTS=3LASTINTEGERSOLUTIONI