運籌學優(yōu)化建摸

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

LINDO

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

ST(說明:也可寫成S.T.,

SUCHTHAT

或SUBJECTTO

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

?X1+X2<5?

END

：GO線性規(guī)劃模型（1）線性規(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?線性規(guī)劃模型（2）捷運公司在下一年度的1～4月份的4個月內(nèi)擬租用倉庫堆放物資。已知各月份所需倉庫面積列于下表1-2。倉庫租借費用隨合同期而定，期限越長，折扣越大，具體數(shù)字見表1-3。租借倉庫的合同每月初都可辦理，每份合同具體規(guī)定租用面積和期限。因此該廠可根據(jù)需要，在任何一個月初辦理租借合同。每次辦理時可簽一份合同，也可簽若干份租用面積和租用期限不同的合同。試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所租借費用最少。線性規(guī)劃模型（2）月份

1234所需倉庫面積15102012表1-2表1-3合同租借期限

1個月2個月3個月4個月合同期內(nèi)的租費2800450060007300單位：100m2單位；元/100m2解：設表示捷運公司在第i(i=1,2,3,4)月初簽訂的租期為j(j=1,2,3,4)個月的倉庫面積的合同（單位為100m2)。ⅠⅡⅢⅣⅤ∑≥15∑≥10∑≥20∑≥12目標函數(shù)約束條件線性規(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線性規(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線性規(guī)劃模型（2）整

數(shù)

規(guī)

劃

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

整數(shù)規(guī)劃(integerprogramming)簡稱為IP問題.這里主要討論的是整數(shù)線性規(guī)劃問題,簡稱為ILP問題.例2.0.1

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

設

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

或GINVname表示將變量Vname標示為0-1型或為一般整數(shù)變量。2）INTn或GINn表示將當前模型中前n個變量標示為0-1型變量或為一般整數(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輸出下列結果：

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輸出下列結果：

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ù)線性規(guī)劃問題在LINDO中輸入下列命令：:MINX1+X2+X3+X4+X5+X6?ST?X2+2X3+3X4+4X5+5X6>10000?6X1+5X2+3X3+2X4+X5>20000?END:GIN6:GOLINDO運行后輸出以下結果：STATUS：OPTIMALLPOPTIMUMFOUNDATSTEP3OBJECTIVEVALUE=5200.00000FIXALLVARS.(4)WITHRC>0.400000E-01NEWINTEGERSOLUTIONOF5200.00000ATBRANCH0PIVOT3BOUNDONOPTIMUM:5200.000ENUMERATIONCOMPLETE.BRANCHES=0PIVOTS=3LASTINTEGERSOLUTIONI