運(yùn)籌學(xué)理論與建模課件

運(yùn)籌學(xué)理論與建模

運(yùn)籌學(xué)理論與建模1主要內(nèi)容第一部分線性規(guī)劃建模方法第二部分整數(shù)規(guī)劃建模方法第三部分指派問題第四部分動(dòng)態(tài)規(guī)劃建模第五部分圖論與網(wǎng)絡(luò)優(yōu)化主要內(nèi)容第一部分線性規(guī)劃建模方法第二部分整數(shù)規(guī)劃建模2第一部分線性規(guī)劃建模方法一、從現(xiàn)實(shí)問題到線性規(guī)劃模型二、線性規(guī)劃模型的求解三、線性規(guī)劃建模實(shí)例第一部分線性規(guī)劃建模方法一、從現(xiàn)實(shí)問題到線性規(guī)劃模型二、3例1加工奶制品的生產(chǎn)計(jì)劃1桶牛奶

3公斤A1

12小時(shí)

8小時(shí)

4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶時(shí)間480小時(shí)至多加工100公斤A1

制訂生產(chǎn)計(jì)劃，使每天獲利最大35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時(shí)工人，付出的工資最多是每小時(shí)幾元?A1的獲利增加到30元/公斤，應(yīng)否改變生產(chǎn)計(jì)劃？每天:一、從現(xiàn)實(shí)問題到線性規(guī)劃模型例1加工奶制品的生產(chǎn)計(jì)劃1桶牛奶3公斤A112小41桶牛奶3公斤A1

12小時(shí)8小時(shí)4公斤A2

或獲利24元/公斤獲利16元/公斤x1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

原料供應(yīng)

勞動(dòng)時(shí)間

加工能力

決策變量

目標(biāo)函數(shù)

每天獲利約束條件非負(fù)約束

線性規(guī)劃模型(LP)時(shí)間480小時(shí)至多加工100公斤A1

50桶牛奶每天1桶牛奶3公斤A112小時(shí)8小時(shí)4公斤A2或獲利25模型分析與假設(shè)

比例性可加性連續(xù)性xi對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”與xi取值成正比xi對(duì)約束條件的“貢獻(xiàn)”與xi取值成正比xi對(duì)目標(biāo)函數(shù)的“貢獻(xiàn)”與xj取值無關(guān)xi對(duì)約束條件的“貢獻(xiàn)”與xj取值無關(guān)xi取值連續(xù)A1,A2每公斤的獲利是與各自產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和時(shí)間是與各自產(chǎn)量無關(guān)的常數(shù)A1,A2每公斤的獲利是與相互產(chǎn)量無關(guān)的常數(shù)每桶牛奶加工出A1,A2的數(shù)量和是與時(shí)間相互產(chǎn)量無關(guān)的常數(shù)加工A1,A2的牛奶桶數(shù)是實(shí)數(shù)線性規(guī)劃模型模型分析與假設(shè)比例性可加性連續(xù)性xi對(duì)目標(biāo)函數(shù)的“貢6A1A2現(xiàn)有資源設(shè)備128臺(tái)時(shí)甲4016公斤乙0412公斤利潤2030（元）制訂生產(chǎn)計(jì)劃,使每天獲利最大

例2

工廠生產(chǎn)兩種產(chǎn)品A1,A2,已知生產(chǎn)單位產(chǎn)品情況如表：設(shè)生產(chǎn)A1、A2分別x1、x2公斤

maxz=20x1+30x2(1)目標(biāo)函數(shù)約束條件決策變量一、從現(xiàn)實(shí)問題到線性規(guī)劃模型A1A2現(xiàn)有資源設(shè)備128臺(tái)時(shí)甲4016公斤乙0412公斤7線性規(guī)劃模型標(biāo)準(zhǔn)型:maxz=c1x1+c2x2+…+cnxn(LP)線性規(guī)劃模型標(biāo)準(zhǔn)型矩陣表示：maxz=cX

max(min)z=c1x1+c2x2+…+cnxn線性規(guī)劃模型一般形式：線性規(guī)劃模型標(biāo)準(zhǔn)型:maxz=c1x1+c2x2+…81.線性規(guī)劃的一般形化為標(biāo)準(zhǔn)型的一般步驟(1)Minf=cX轉(zhuǎn)化為maxz=cX(2)加松弛變量yi

(3)加剩余變量yi(4)若存在可正可負(fù)變量xi

令1.線性規(guī)劃的一般形化為標(biāo)準(zhǔn)型的一般步驟(1)Minf9例將下述線性規(guī)劃問題化為標(biāo)準(zhǔn)型min

z=x1+2x2

3x3無約束標(biāo)準(zhǔn)型maxz=

x12x2+3(x4–x5)+0x6+0x7(1)

x3=

x4x5,x4,x50(2)

x1+x2+x3+x6=7(3)

x1

x2+x3

x7=2例將下述線性規(guī)劃問題化為標(biāo)準(zhǔn)型minz=x1+210合理下料問題有長度為8米的某型號(hào)圓鋼，現(xiàn)需要長度為2.5米的毛坯100根，長度為1.3米的毛坯200根，如何選者下料方式，所需總用料最省?解：可能的下料方式：2.51.3130222314406設(shè)按第i種下料方式的圓鋼xi根，i=1,2,3,4

minz=x1+x2+x3+x4有一組決策變量,約束條件是決策變量的線性等式或不等式,目標(biāo)函數(shù)是決策變量的線性函數(shù),這樣的規(guī)劃問題稱為線性規(guī)劃.記為（LP）合理下料問題有長度為8米的某型號(hào)圓鋼，現(xiàn)需要長度為211例.某小區(qū)一個(gè)24小時(shí)營業(yè)便利店,一

天各時(shí)段所需服務(wù)員最少人數(shù)如下

表.根據(jù)實(shí)際情況,要求每個(gè)服務(wù)員必

須連續(xù)工作八小時(shí),試建立需服務(wù)員

總?cè)藬?shù)最少的排班方案數(shù)學(xué)模型.班次123456時(shí)間2-66-1010-1414-1818-2222-2人48107124解：設(shè)各班次新增服務(wù)員數(shù)分別為x1,x2,x3,x4,x5,x6,則minz=

x1+x2+x3+x4+x5+x6且xi為整數(shù)例.某小區(qū)一個(gè)24小時(shí)營業(yè)便利店,一

天各時(shí)段所需服務(wù)員最少12連續(xù)投資問題某部門計(jì)劃5年內(nèi)用一百萬投資下列項(xiàng)目：A：從第一年到第四年初可投資，次年末回收本利115%B:第三年初可投資，第五年末回收本利125%，投資額≤40萬C:第二年初可投資，第五年末回收本利140%，投資額≤30萬D：每年初可購買公債，當(dāng)年末歸還，利息6%如何投資，五年后獲利最大？解：設(shè)第i年初投資項(xiàng)目A,B,C,D分別為xiA

,xiB

,xiC

,

xiD

萬元,i=1,2,3,4,5x1A+x1D=100,x2A+x2C+x2D=1.06x1D,x3A+x3B+x3D=1.06x2D+1.15

x1A,x4A+x4D=1.06x3D+1.15

x2A,x5D=1.06x4D+1.15

x3A,x2C≤40,x3B≤30,xiA

,xiB

,xiC

,

xiD≥0，i=1,2,3,4,5.MaxZ=1.15x4A

+1.40x2C+1.25x3B+1.06x5Ds.t.連續(xù)投資問題某部門計(jì)劃5年內(nèi)用一百萬投資下列項(xiàng)目：解13二、線性規(guī)劃模型的求解（一）圖解法（n

3時(shí)）（二）單純形法二、線性規(guī)劃模型的求解（一）圖解法（n3時(shí)）（二）單純形14maxz=c

x(LP)可行解：滿足約束條件AX=b,X最優(yōu)解:可行解中使目標(biāo)最優(yōu)的.即X*∈D,且任意X∈D,CX*≥CX可行集：所有可行解的集合的X的值maxz=cx(LP)可行解：滿足約束條件AX=b,15制訂生產(chǎn)計(jì)劃,使每天獲利最大.

工廠生產(chǎn)兩種產(chǎn)品A1,A2,已知生產(chǎn)單位產(chǎn)品情況如下：設(shè)生產(chǎn)A1、A2分別x1、x2公斤

maxz=20x1+30x2(1)A1A2現(xiàn)有資源設(shè)備128臺(tái)時(shí)甲4016公斤乙0412公斤利潤2030（元）制訂生產(chǎn)計(jì)劃,使每天獲利工廠生產(chǎn)兩種產(chǎn)品A1,A2,已設(shè)生產(chǎn)16（一）圖解法（n3時(shí)）(1)在平面上作出可行集ABCD34z=140z=0由圖解法直觀得:n=2時(shí),(LP)的可行集是凸多邊形,最優(yōu)解可以在其某個(gè)頂點(diǎn)處達(dá)到.線性規(guī)劃基本性質(zhì):(LP)的可行集是凸多面體,最優(yōu)解可以在凸多面體的某個(gè)頂點(diǎn)處達(dá)到.線性規(guī)劃求解思路:通過代數(shù)的方法描述高維空間凸多面體的頂點(diǎn),再使用經(jīng)濟(jì)的方法來求出達(dá)到極值的頂點(diǎn).x1x20(2)在可行集中找最優(yōu)解

maxz=20x1+30x2(1)z=60（一）圖解法（n3時(shí)）(1)在平面上作出可行集ABCD3417引入松弛變量x3,x4,x5,化為標(biāo)準(zhǔn)形:（二）單純形法系數(shù)矩陣為引入松弛變量x3,x4,x5,化為標(biāo)準(zhǔn)形:（二）單純形18顯然A的秩為3,任取3個(gè)線性無關(guān)的列向量,如P1,P2,

P3稱為一組基,記為B=(P1,P2,

P3).P1,P2,

P3

稱為基向量,

基向量對(duì)應(yīng)的變量x1,x2,x3稱為基變量,其余列向量

P4,

P5

稱為非基向量,記為N=(P4,

P5).非基對(duì)應(yīng)的變量x4,x5稱為非基變量.A=(B,N),相應(yīng)X=(XB,XN)T,c=(cB,cN)AX=BXB+NXN=b,則XB=B1b

B1

NXN,系數(shù)矩陣為顯然A的秩為3,任取3個(gè)線性無關(guān)的列向量,如P1,P219令非基變量XN=0,解得基變量XB=B-1b,稱(XB,XN)為基本解.解的所有變量的值都非負(fù),則稱為基本可行解,此時(shí)的基稱為可行基.基本可行解對(duì)應(yīng)的目標(biāo)值為f=cBB-1b.

若可行基進(jìn)一步滿足:cN–cBB-1N≥0,則對(duì)一切可行解X,

必有f(x)≥cBB-1b,此時(shí)稱基可行解X=(B-1b,0)T為最優(yōu)解.令非基變量XN=0,解得基變量XB=B-1b,稱20另一個(gè)基本可行解定理：(LP)的可行集的頂點(diǎn)與(LP)的

基本可行解一一對(duì)應(yīng)。單純形法基本思想：目標(biāo)重復(fù)此更優(yōu)過程單純形法基本步驟：不是最優(yōu)解更優(yōu)目標(biāo)重復(fù)此過程(LP)的某個(gè)基本可行解最優(yōu)解(LP)的某個(gè)基基本可行解另一個(gè)基基本可行解最優(yōu)解另一個(gè)基定理：(LP)的可行集的頂點(diǎn)與(LP)的單純形法21即從可行域的一個(gè)頂點(diǎn)(基本可行解)開始,轉(zhuǎn)移到另一個(gè)頂點(diǎn)(另一個(gè)基本可行解)的迭代過程,轉(zhuǎn)移的條件是使目標(biāo)函數(shù)值得到改善(逐步變優(yōu)),當(dāng)目標(biāo)函數(shù)達(dá)到最優(yōu)值時(shí),問題也就得到了最優(yōu)解.頂點(diǎn)轉(zhuǎn)移的依據(jù)？根據(jù)線性規(guī)劃問題的可行域是凸多邊形或凸多面體,一個(gè)線性規(guī)劃問題有最優(yōu)解,就一定可以在可行域的頂點(diǎn)上找到.于是,若某線性規(guī)劃只有唯一的一個(gè)最優(yōu)解,這個(gè)最優(yōu)解所對(duì)應(yīng)的點(diǎn)一定是可行域的一個(gè)頂點(diǎn);若該線性規(guī)劃有多個(gè)最優(yōu)解,那么肯定在可行域的頂點(diǎn)中可以找到至少一個(gè)最優(yōu)解.1.單純形法的基本思想(1)頂點(diǎn)的逐步轉(zhuǎn)移即從可行域的一個(gè)頂點(diǎn)(基本可行解)開始,轉(zhuǎn)移到另22轉(zhuǎn)移條件？轉(zhuǎn)移結(jié)果？

使目標(biāo)函數(shù)值得到改善得到LP最優(yōu)解，目標(biāo)函數(shù)達(dá)到最優(yōu)值（單純形法的由來？）

2．需要解決的問題：

(1)為了使目標(biāo)函數(shù)逐步變優(yōu)，怎么轉(zhuǎn)移？(2)目標(biāo)函數(shù)何時(shí)達(dá)到最優(yōu)——判斷標(biāo)準(zhǔn)是什么？

轉(zhuǎn)移條件？232.單純形法原理（用代數(shù)方法求解LP）勞動(dòng)力原材料利潤A112B143C173現(xiàn)有資源39例1勞動(dòng)力約束原材料約束2.單純形法原理（用代數(shù)方法求解LP）勞動(dòng)力原材料利潤A1124第一步：引入非負(fù)的松弛變量x4,x5,將該LP化為標(biāo)準(zhǔn)型第二步：尋求初始可行基，確定基變量對(duì)應(yīng)的基變量是x4，x5；第三步：寫出初始基本可行解和相應(yīng)的目標(biāo)函數(shù)值兩個(gè)關(guān)鍵的基本表達(dá)式：①用非基變量表示基變量的表達(dá)式第一步：引入非負(fù)的松弛變量x4,x5,將該LP化為標(biāo)25②用非基變量表示目標(biāo)函數(shù)的表達(dá)式請(qǐng)解釋結(jié)果的經(jīng)濟(jì)含義——不生產(chǎn)任何產(chǎn)品,資源全部節(jié)余(x4=3，x5=9),三種產(chǎn)品的總利潤為0！第四步：分析兩個(gè)基本表達(dá)式，看看目標(biāo)函數(shù)是否可以改善？①分析用非基變量表示目標(biāo)函數(shù)的表達(dá)式非基變量前面的系數(shù)均為正數(shù)，所以任何一個(gè)非基變量進(jìn)基都能使z值增加通常把非基變量前面的系數(shù)叫“檢驗(yàn)數(shù)”；②用非基變量表示目標(biāo)函數(shù)的表達(dá)式請(qǐng)解釋結(jié)果的經(jīng)濟(jì)含義——不26②選哪一個(gè)非基變量進(jìn)基？

選x2為進(jìn)基變量（換入變量）問題：能否選其他的非基變量進(jìn)基？

任意一個(gè)

任意一個(gè)正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量

最大正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量

排在最前面的正檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量×③確定出基變量：問題討論x2進(jìn)基意味著其取值從0變成一個(gè)正數(shù)（經(jīng)濟(jì)意義—生產(chǎn)B產(chǎn)品），能否無限增大？當(dāng)x2增加時(shí)，x4，x5如何變化？②選哪一個(gè)非基變量進(jìn)基？任意一個(gè)×③確定出基27現(xiàn)在的非基變量是哪些？具體如何確定換出變量？由用非基變量表示基變量的表達(dá)式

當(dāng)x2增加時(shí),x4,x5會(huì)減小,但有限度——必須大于等于0,以保持解的可行性！于是當(dāng)x2的值從0增加到9/4時(shí),x5首先變?yōu)?，此時(shí)x4=3/4>0,因此選x5為出基變量(換出變量).現(xiàn)在的非基變量是哪些？由用非基變量表示基變量的表達(dá)式當(dāng)28這種用來確定出基變量的規(guī)則稱為“最小比值原則”（或θ原則).如果P1≤0，會(huì)出現(xiàn)什么問題？最小比值原則會(huì)失效！基變換新的基變量——x2,x4；新的非基變量x1,x3,x5；寫出用非基變量表示基變量的表達(dá)式：由可得新的基本可行解:X(1)=(0，9/4，0，3/4，0)T這種用來確定出基變量的規(guī)則稱為“最小比值原則”29⑤寫出用非基變量表示目標(biāo)函數(shù)的表達(dá)式:可得相應(yīng)的目標(biāo)函數(shù)值為z(1)=27/4檢驗(yàn)數(shù)仍有正的,返回①進(jìn)行討論.第五步：上述過程何時(shí)停止？當(dāng)用非基變量表示目標(biāo)函數(shù)的表達(dá)式中,非基變量的系數(shù)(檢驗(yàn)數(shù))全部非正時(shí),當(dāng)前的基本可行解就是最優(yōu)解!

為什么？⑤寫出用非基變量表示目標(biāo)函數(shù)的表達(dá)式:可得相應(yīng)的目標(biāo)函數(shù)值30——分析:用非基變量表示目標(biāo)函數(shù)的表達(dá)式,如果讓負(fù)檢驗(yàn)數(shù)所對(duì)應(yīng)的變量進(jìn)基，目標(biāo)函數(shù)值將下降！三、表格單純形法：

1.初始單純形表的建立

(1)表格結(jié)構(gòu)：

x1x2

x3

x4

x523300bXB11110147013x49x523300z——分析:用非基變量表示目標(biāo)函數(shù)的表達(dá)式,如果讓負(fù)檢驗(yàn)數(shù)31（2）表格設(shè)計(jì)依據(jù)：

把目標(biāo)函數(shù)表達(dá)式改寫成方程的形式，和原有的m個(gè)約束方程組成一個(gè)具有n+m+1個(gè)變量、m+1個(gè)方程的方程組：（2）表格設(shè)計(jì)依據(jù)：32取出系數(shù)寫成增廣矩陣的形式：

xn+1，…，xn+m所對(duì)應(yīng)的系數(shù)列向量構(gòu)成一個(gè)基.用矩陣的初等行變換將目標(biāo)函數(shù)中基變量系數(shù)化為零,這時(shí)變成0，相應(yīng)的增廣矩陣變成如下形式：取出系數(shù)寫成增廣矩陣的形式：xn+1，…，xn+m所對(duì)應(yīng)的33其中，j=1，2，…，n；

增廣矩陣的最后一行就是用非基變量表示目標(biāo)函數(shù)的表達(dá)式,j

(j=1,2,…,n）就是非基變量的檢驗(yàn)數(shù).（3）檢驗(yàn)數(shù)的兩種計(jì)算方法：①利用矩陣的行變換，把目標(biāo)函數(shù)表達(dá)式中基變量前面的系數(shù)變?yōu)?；②使用計(jì)算公式——其中，342.例1的表格單純形法計(jì)算過程：x1x2x3x4x5

23300z111103x4147019

x5

23300z3/4

0

-3/4

1

-1/43/4

x41/417/401/49/4x25/40–9/40-3/4z-27/410-14/3-1/31x1012-1/31/32

x200-1-5/3-1/3z-8從最優(yōu)表可知:該LP的最優(yōu)解是X*=(1,2,0,0,0)T相應(yīng)的目標(biāo)函數(shù)最優(yōu)值是Zmax=8**2.例1的表格單純形法計(jì)算過程：x1x235表格單純形法求解步驟第一步：將LP化為標(biāo)準(zhǔn)型，并加以整理.引入適當(dāng)?shù)乃神Y變量、剩余變量和人工變量,使約束條件化為等式,并且約束方程組的系數(shù)陣中有一個(gè)單位陣.

（這一步計(jì)算機(jī)可自動(dòng)完成）

確定初始可行基，寫出初始基本可行解.第二步：最優(yōu)性檢驗(yàn)計(jì)算檢驗(yàn)數(shù)，檢查：所有檢驗(yàn)數(shù)是否≤0？

是—結(jié)束,寫出最優(yōu)解和目標(biāo)函數(shù)最優(yōu)值;還有正檢驗(yàn)數(shù)—檢查相應(yīng)系數(shù)列≤0？是—結(jié)束,該LP無“有限最優(yōu)解”！不屬于上述兩種情況，轉(zhuǎn)入下一步—基變換.確定是停止迭代還是轉(zhuǎn)入基變換？表格單純形法求解步驟第一步：將LP化為標(biāo)準(zhǔn)型，并加以整理.第36選擇(最大)正檢驗(yàn)數(shù)對(duì)應(yīng)的系數(shù)列為主元列,主元列對(duì)應(yīng)的非基變量為換入變量；

最小比值對(duì)應(yīng)的行為主元行,主元行對(duì)應(yīng)的基變量為換出變量.第三步：基變換確定進(jìn)基變量和出基變量.第四步

換基迭代（旋轉(zhuǎn)運(yùn)算、樞運(yùn)算)利用矩陣的初等行變換把主元列變成單位向量,主元素變?yōu)?,進(jìn)基變量對(duì)應(yīng)的檢驗(yàn)數(shù)變成0,從而得到一張新的單純形表,返回第二步.完成一次迭代，得到新的基本可行解和相應(yīng)的目標(biāo)函數(shù)值.選擇(最大)正檢驗(yàn)數(shù)對(duì)應(yīng)的系數(shù)列為主元列,主元列對(duì)第三37該迭代過程直至下列情況之一發(fā)生時(shí)停止檢驗(yàn)數(shù)行全部變?yōu)榉钦?；（得到最?yōu)解）或主元列≤0（最優(yōu)解無界）停止迭代的標(biāo)志（停機(jī)準(zhǔn)則）該迭代過程直至下列情況之一發(fā)生時(shí)停止停止迭代的標(biāo)志38自來水輸送與貨機(jī)裝運(yùn)生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求點(diǎn)，怎樣安排輸送方案使運(yùn)費(fèi)最小，或利潤最大；運(yùn)輸問題各種類型的貨物裝箱，由于受體積、重量等限制，如何搭配裝載，使獲利最高，或裝箱數(shù)量最少.三、線性規(guī)劃建模實(shí)例自來水輸送與貨機(jī)裝運(yùn)生產(chǎn)、生活物資從若干供應(yīng)點(diǎn)運(yùn)送到一些需求39其他費(fèi)用:450元/千噸

應(yīng)如何分配水庫供水量，公司才能獲利最多？

若水庫供水量都提高一倍，公司利潤可增加到多少？元/千噸甲乙丙丁A160130220170B140130190150C190200230/引水管理費(fèi)例1自來水輸送收入：900元/千噸

支出A：50B：60C：50甲：30；50乙：70；70丙：10；20?。?0；40水庫供水量(千噸)小區(qū)基本用水量(千噸)小區(qū)額外用水量(千噸)（以天計(jì)）其他費(fèi)用:450元/千噸應(yīng)如何分配水庫供水量，公司才能獲40總供水量：160確定送水方案使利潤最大問題分析A：50B：60C：50甲：30；50乙：70；70丙：10；20?。?0；40<總需求量：120+180=300總收入900160=144,000(元)收入：900元/千噸

其他費(fèi)用:450元/千噸

支出引水管理費(fèi)其他支出450160=72,000(元)

使引水管理費(fèi)最小總供水量：160確定送水方案使利潤最大問題分析A：50B：641供應(yīng)限制約束條件需求限制

線性規(guī)劃模型(LP)目標(biāo)函數(shù)

水庫i向j區(qū)的日供水量為xij（x34=0）決策變量

模型建立確定3個(gè)水庫向4個(gè)小區(qū)的供水量供應(yīng)限制約束條件需求限制線性規(guī)劃模型(LP)目標(biāo)函數(shù)水庫42目標(biāo)函數(shù)

總供水量(320)>總需求量(300)每個(gè)水庫最大供水量都提高一倍利潤=收入(900)–其它費(fèi)用(450)

–引水管理費(fèi)利潤(元/千噸)甲乙丙丁A290320230280B310320260300C260250220/供應(yīng)限制B,C類似處理問題討論

確定送水方案使利潤最大需求約束可以不變目標(biāo)函數(shù)總供水量(320)>總需求量(300)每個(gè)水庫43如何裝運(yùn)，使本次飛行獲利最大？

例2貨機(jī)裝運(yùn)

重量（噸）空間(米3/噸）利潤（元/噸）貨物1184803100貨物2156503800貨物3235803500貨物4123902850三個(gè)貨艙中實(shí)際載重必須與其最大載重成比例

前倉：10；6800中倉：16；8700后倉：8；5300飛機(jī)平衡三個(gè)貨艙最大載重(噸),最大容積(米3)

如何裝運(yùn)，使本次飛行獲利最大？例2貨機(jī)裝運(yùn)

重量（噸44決策變量

xij--第i種貨物裝入第j個(gè)貨艙的重量(噸）i=1,2,3,4,

j=1,2,3(分別代表前、中、后倉)模型假設(shè)每種貨物可以分割到任意小；貨機(jī)裝運(yùn)每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；多種貨物可以混裝，并保證不留空隙；模型建立決策變量xij--第i種貨物裝入第j個(gè)貨艙的重量(噸）45貨艙容積

目標(biāo)函數(shù)(利潤)約束條件貨機(jī)裝運(yùn)模型建立貨艙重量

10；680016；87008；5300xij--第i種貨物裝入第j個(gè)貨艙的重量貨艙容積目標(biāo)函數(shù)(利潤)約束條件貨機(jī)裝運(yùn)模型建立貨艙重量46約束條件平衡要求

貨物供應(yīng)

貨機(jī)裝運(yùn)模型建立10；680016；87008；5300xij--第i種貨物裝入第j個(gè)貨艙的重量約束條件平衡要求貨物供應(yīng)貨機(jī)裝運(yùn)模型建立10；680047第二部分整數(shù)規(guī)劃建模方法一、整數(shù)規(guī)劃簡介二、整數(shù)規(guī)劃的分支定界法三、整數(shù)規(guī)劃的建模實(shí)例第二部分整數(shù)規(guī)劃建模方法一、整數(shù)規(guī)劃簡介二、整數(shù)規(guī)劃的分482.1整數(shù)規(guī)劃簡介要求所有xj的解為整數(shù)，稱為純整數(shù)規(guī)劃要求部分xj的解為整數(shù)，稱為混合整數(shù)規(guī)劃對(duì)應(yīng)沒有整數(shù)解要求的線性規(guī)劃稱之為松弛問題整數(shù)規(guī)劃的解是可數(shù)個(gè)的，最優(yōu)解不一定發(fā)生在極點(diǎn)整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其松弛問題的最優(yōu)解且為整數(shù)2.1整數(shù)規(guī)劃簡介要求所有xj的解為整數(shù)，稱為純整數(shù)規(guī)492.2整數(shù)規(guī)劃的分枝定界法3.求解分枝的松弛問題—定界過程設(shè)兩個(gè)分枝的松弛問題分別為問題1和問題2,它們的最優(yōu)解有如下情況:

2.2.1思路與解題步驟只解松弛問題1.在全部可行性域上解松弛問題若松弛問題最優(yōu)解為整數(shù)解，則其也是整數(shù)規(guī)劃的最優(yōu)解2.分枝過程若松弛問題最優(yōu)解中某個(gè)xk=bk不是整數(shù)，令[bk]為bk的整數(shù)部分:構(gòu)造兩個(gè)新的約束條件xk[bk]和xk[bk]+1，分別加于原松弛問題，形成兩個(gè)新的整數(shù)規(guī)劃.2.2整數(shù)規(guī)劃的分枝定界法3.求解分枝的松弛問題—定界50表2.2.1分枝問題解可能出現(xiàn)的情況情況2,4,5找到最優(yōu)解情況3在縮減的域上繼續(xù)分枝定界法情況6問題1的整數(shù)解作為界被保留，用于以后與問題2的后續(xù)分枝所得到的解進(jìn)行比較，結(jié)論如情況4或5序號(hào)問題1問題2說明1無可行解無可行解整數(shù)規(guī)劃無可行解2無可行解整數(shù)解此整數(shù)解即為最優(yōu)解3無可行解整數(shù)解非對(duì)問題2繼續(xù)分枝4整數(shù)解整數(shù)解較優(yōu)的一個(gè)為最優(yōu)解5整數(shù)解,目標(biāo)函數(shù)值優(yōu)于2非整數(shù)解問題1的解即為最優(yōu)解（剪枝）6整數(shù)解整數(shù)解,目標(biāo)函數(shù)值優(yōu)于1問題1停止分枝，其整數(shù)解為界，對(duì)問題2繼續(xù)分枝

表2.2.1分枝問題解可能出現(xiàn)的情況情況2,4,5512.2.2分枝定界法舉例例2.1.1解：松弛問題的最優(yōu)解為x1=2.5,x2=2,OBJ=23由x1=2.5得到兩個(gè)分枝如下：2.2.2分枝定界法舉例例2.1.1解52表2.2.3分枝問題的松弛解問題II的解即原整數(shù)問題的最優(yōu)解可能存在兩個(gè)分枝都是非整數(shù)解的情況，則需要兩邊同時(shí)繼續(xù)分枝，直到有整數(shù)解出現(xiàn)，就可以進(jìn)行定界過程.當(dāng)存在很多變量有整數(shù)約束時(shí)，分枝即廣又深，在最壞情況下相當(dāng)于組合所有可能的整數(shù)解.一般整數(shù)規(guī)劃問題屬于一類未解決的難題，NP-complete，只有少數(shù)特殊問題有好的算法，如任務(wù)分配問題、匹配問題.表2.2.3分枝問題的松弛解問題II的解即原整數(shù)問53例.某廠擬用集裝箱托運(yùn)甲,乙兩種貨物。已知貨物體積(米3/箱)重量(噸/箱)利潤(百元/箱)甲9740乙72090托運(yùn)限制5670問：如何安排利潤最大？設(shè)甲乙分別托運(yùn)x1,x2箱模型建立

IP(1)-(4)稱為與(IP)相對(duì)應(yīng)的線性規(guī)劃(LP)求解(LP)得x1=4.81,x2=1.82,

z=356為整數(shù)例.某廠擬用集裝箱托運(yùn)甲,乙兩種貨物。已知貨物體積(米3/箱54分枝定界法(branchandboundmethod)(IP)x1*,x2*,z

*(LP) x1=4.81,x2=1.82,z0=356(LP1)x1=4,x2=2.1,z0=349X1≤4X1≥5(LP2)x1=5,x2=1.57,z0=341(z*349定界)(LP3)x1=4,x2=2,z0=340X2≤2X2≥3(LP4)x2=3,x1=1.42,z0=327(z*≥340定界)(LP5)x2=1,x1=5.44,z0=308X2≤1(LP6)無可行解X2≥2x1≤4x1≥5分枝：分枝定界法(branchandboundmethod)55應(yīng)如何安排原油的采購和加工

？

例2原油采購與加工市場上可買到不超過1500噸的原油A：購買量不超過500噸時(shí)的單價(jià)為10000元/噸；購買量超過500噸但不超過1000噸時(shí)，超過500噸的部分8000元/噸；購買量超過1000噸時(shí)，超過1000噸的部分6000元/噸.售價(jià)4800元/噸售價(jià)5600元/噸庫存500噸庫存1000噸汽油甲(A50%)原油A原油B汽油乙(A60%)2.3整數(shù)規(guī)劃的建模實(shí)例應(yīng)如何安排原油的采購和加工？例2原油采購與加工56決策變量

目標(biāo)函數(shù)問題分析利潤：銷售汽油的收入購買原油A的支出難點(diǎn)：原油A的購價(jià)與購買量的關(guān)系較復(fù)雜甲(A50%)AB乙(A60%)購買xx11x12x21x224.8千元/噸5.6千元/噸原油A的購買量,原油A,B生產(chǎn)汽油甲,乙的數(shù)量c(x)~購買原油A的支出利潤(千元)c(x)如何表述？決策變量目標(biāo)函數(shù)問題分析利潤：銷售汽油的收入購買原油57原油供應(yīng)

約束條件x

500噸單價(jià)為10千元/噸；500噸x1000噸，超過500噸的8千元/噸；1000噸x1500噸，超過1000噸的6千元/噸。目標(biāo)函數(shù)購買xABx11x12x21x22庫存500噸庫存1000噸原油供應(yīng)約束條件x500噸單價(jià)為10千元/噸；目標(biāo)函58目標(biāo)函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃；對(duì)于用分段函數(shù)定義的c(x)，一般的非線性規(guī)劃軟件也難以輸入和求解；想辦法將模型化簡，用現(xiàn)成的軟件求解.汽油含原油A的比例限制約束條件甲(A50%)AB乙(A60%)x11x12x21x22目標(biāo)函數(shù)中c(x)不是線性函數(shù)，是非線性規(guī)劃；汽油含原油A59整數(shù)規(guī)劃應(yīng)用舉例1.整數(shù)變量2.特殊約束處理3.背包問題4.集合覆蓋問題5.固定費(fèi)用問題整數(shù)規(guī)劃應(yīng)用舉例1.整數(shù)變量601.整數(shù)變量表示不可分割的數(shù)量表示決策變量(0–1整數(shù)變量) 1 表示決策j為“是”

xj=

0 表示決策j為“否”1.整數(shù)變量表示不可分割的數(shù)量61表示決策之間的邏輯關(guān)系，如決策i必須以決策

j的結(jié)果為前提：xi

xj

或

xi=xj

描述互斥的選擇，從多種方案中選一個(gè)方案：

j

xj=1表示決策之間的邏輯關(guān)系，如決策i必須以決策62例某公司有600萬元資金用于投資，有5個(gè)項(xiàng)目列入投資計(jì)劃，各項(xiàng)目投資額和期望收益見下表：項(xiàng)目 投資額(萬元) 投資收益(萬元) 1 210 150 2 300 210 3 100 60 4 130 80 5 260 180 由于技術(shù)原因，投資受到以下約束:在項(xiàng)目1,2和3中必須且只能有一項(xiàng)被選中;項(xiàng)目3和4最多只能被選中一項(xiàng);項(xiàng)目5被選中的前提是項(xiàng)目1被選中;問如何選擇最好的投資方案,使投資收益最大.例某公司有600萬元資金用于投資，有5個(gè)項(xiàng)目列入投由63解：令xi為0-1決策變量,模型為:max

z=150x1+210x2+60x3+80x4+160x5

s.t.210x1+300x2+100x3+130x4+260x5600

x1+x2+x3=1

x3+x41

x5

x1 xi=1或0,i=1,...,5解：令xi為0-1決策變量,模型為:64(1)矛盾約束：同時(shí)出現(xiàn)的矛盾約束 f(x)–50或f(x)0 引入一個(gè)0—1變量y來處理：

f(x)+5M(1

y)和f(x)My

y=1f(x)50和f(x)M

y=0f(x)5

M和f(x)02.特殊約束處理(1)矛盾約束：同時(shí)出現(xiàn)的矛盾約束2.特殊約束處理65(2)絕對(duì)值約束:

f(x)

a(a

0) 約束可寫為：f(x)

a或f(x)

–

a

引入01變量y后，約束可改寫為：

f(x)+a

M(1y)和f(x)+a

My

y=1f(x)+a

0和f(x)+a

M

y=0f(x)+aM和f(x)+a0(2)絕對(duì)值約束:66(3)多中選一的約束在下列n個(gè)約束中，只能有一個(gè)約束有效: fi(x)0 i=1,2,…,n

引入n個(gè)01變量yi,i=1,2,…,n,約束可寫為： fi(x)M(1yi)i=1,2,…,n

y1+y2+…+yn

=1 (3)多中選一的約束673.背包問題例一登山隊(duì)員做登山準(zhǔn)備，需要攜帶的物品有：食品、氧氣、冰鎬、繩索、帳篷、照相機(jī)和通訊設(shè)備。每種物品的重要性系數(shù)和重量見下表：要求背包重量不能超過25公斤，求重要性系數(shù)最大的攜帶物品方案.3.背包問題例一登山隊(duì)員做登山準(zhǔn)備，需要攜帶的物品有：食68令xi為是否攜帶物品i的決策變量：

maxz=20x1+15x2+18x3+14x4+8x5+4x6+10x7

s.t.5x1+5x2+2x3+6x4+12x5+2x6+

4x7

25 xi=1或0，i=1,2,...,7背包問題的一般形式為：

max

z=c1x1+c2x2+…+cnxn

s.t.a1x1+a2x2+…+anxn

b

x1,x2,…

,xn

0令xi為是否攜帶物品i的決策變量：69對(duì)一維背包問題，上例使用的啟發(fā)式算法是很有效的：只要比較ci/ai的比值，依次令有最大的比值的決策變量為1，直到資源b用盡為止。該算法當(dāng)n較大，且ai<<b時(shí)更為準(zhǔn)確.對(duì)一維背包問題，上例使用的啟發(fā)式算法是很704.集合覆蓋問題有集合S={1,2,...,m}被一系列S的子集iS，i=1,2,...,n覆蓋，并要求使用的子集最少.例:

有集合S={1,2,3,4,5},子集1={1,2},2={1,3,5},

3={2,4,5},4={1},5={4,5},求最小的覆蓋子集。解:一個(gè)可能的覆蓋為1,2,3,另一個(gè)為2,3;該問題可以用一個(gè)整數(shù)規(guī)劃來求解： 令xi為是否使用集合i的決策變量4.集合覆蓋問題71Minz=x1+x2+x3+x4+x5s.t.

x1+x2+x41

x1+x3

1

x21

x3+x51

x2+x3+x51 xi=0或1,i=1,...,5Minz=x1+x2+x3+x4+x572例

某城市有6個(gè)區(qū),規(guī)劃建消防站,任何區(qū)發(fā)生火警時(shí)消防車要在15分鐘內(nèi)趕到,各區(qū)間消防車行駛的時(shí)間見下表,求設(shè)置消防站最少的方案.例 某城市有6個(gè)區(qū),規(guī)劃建消防站,任何區(qū)發(fā)生73解：設(shè)xj

為在j地區(qū)設(shè)置消防站的決策(j=1,2,…,6)整數(shù)規(guī)劃問題為：

min

z=

x1+x2+x3+x4+x5+x6

s.t.

x1+x21

x1+x2+x61

x3+x4

1

x3+x4+x5

1

x4+x5+x61

x2+x5+x61 xi=0或1i=1,...,6最優(yōu)解x2=x4=1,在地區(qū)2,4設(shè)消防站.解：設(shè)xj為在j地區(qū)設(shè)置消防站的決策(j=174人們經(jīng)常會(huì)遇到固定費(fèi)用問題,例如要建一條生產(chǎn)線,由生產(chǎn)能力確定的投資規(guī)模是固定的,要建設(shè),就要投入一筆固定數(shù)量資金;再如,如果生產(chǎn)要租用設(shè)備,則不管如何使用該設(shè)備,你都要支付一筆固定的租金,租金一般不隨生產(chǎn)量的變化而變化,求解這類不連續(xù)變化的固定費(fèi)用問題也要借助整數(shù)規(guī)劃.5.固定費(fèi)用問題人們經(jīng)常會(huì)遇到固定費(fèi)用問題,例如要建一條生產(chǎn)5.固定費(fèi)75例:服裝廠可生產(chǎn)西服、襯衫和羽絨服.生產(chǎn)不同服裝要使用不同設(shè)備，該廠可從租賃公司租用這些設(shè)備.假定市場需求不成問題，服裝廠每月可用人工工時(shí)為2000小時(shí)，該廠如何安排生產(chǎn)可使每月利潤最大.設(shè)備租金和其它經(jīng)濟(jì)參數(shù)見下表：例:服裝廠可生產(chǎn)西服、襯衫和羽絨服.生產(chǎn)不76解：令yi為是否租賃i類設(shè)備的決策變量;xi為各類服裝的生產(chǎn)量,具體模型為：Maxz=120x1+10x2+100x35000y12000y21000y3

s.t.5x1+x2+4x32000 3x1－300y10 0.5x2－300y2

0 2x3－300y30

xi0yi=0或1i=1,2,3解：令yi為是否租賃i類設(shè)備的決策變量;xi為各類77第三講指派問題一、指派問題定義二、指派問題的求解三、指派問題的建模實(shí)例第三講指派問題一、指派問題定義二、指派問題的求解三、指派78丁的蛙泳成績退步到1’15”2；戊的自由泳成績進(jìn)步到57”5,組成接力隊(duì)的方案是否應(yīng)該調(diào)整？如何選拔隊(duì)員組成4100米混合泳接力隊(duì)?例1混合泳接力隊(duì)的選拔

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候選人的百米成績窮舉法：組成接力隊(duì)的方案共有5!=120種。丁的蛙泳成績退步到1’15”2；戊的自由泳成績進(jìn)步到57”579目標(biāo)函數(shù)若選擇隊(duì)員i參加泳姿j的比賽，記xij=1,否則記xij=0

0-1規(guī)劃模型

cij(秒)~隊(duì)員i第j種泳姿的百米成績約束條件每人最多入選泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每種泳姿有且只有1人目標(biāo)函數(shù)若選擇隊(duì)員i參加泳姿j的比賽，記xij=1,否則80若干項(xiàng)任務(wù)分給一些候選人來完成，每人的專長不同，完成每項(xiàng)任務(wù)取得的效益或需要的資源就不同,如何分派任務(wù)使獲得的總效益最大，或付出的總資源最少.指派(Assignment)問題：n個(gè)人要完成n項(xiàng)任務(wù)，每項(xiàng)任務(wù)有且只有一人承擔(dān)，每人只能承擔(dān)一項(xiàng)，費(fèi)用不同，怎樣分派使總費(fèi)用最小.若干項(xiàng)任務(wù)分給一些候選人來完成，每人的專長不指派(Assig81模型建立

Cij表示指派第i人做第j項(xiàng)任務(wù)所需成本.指派(Assignment)問題:n個(gè)人要完成n項(xiàng)任務(wù),每項(xiàng)任務(wù)有且只有一人承擔(dān),每人只能承擔(dān)一項(xiàng),費(fèi)用不同,怎樣分派使總費(fèi)用最大.模型建立Cij表示指派第i人做第j項(xiàng)任務(wù)所需成本.指派(A82一份中文說明書需要翻譯成英,日,德,俄4種文字，甲乙丙丁4人翻譯費(fèi)用矩陣如下:一份中文說明書需要翻譯成英,日,德,俄4種文字，甲乙丙丁483可行解矩陣{xij}nn每行每列均有且只有一個(gè)1，其余全為零最優(yōu)解x14

=

x22

=

x33

=

x41

=1，其余xij=0,最優(yōu)值

z=4+4+16+3=27可行解矩陣{xij}nn每行每列均有且只有一個(gè)1，其余全為84匈牙利算法定理1如果從費(fèi)用矩陣{cij}nn中每行元素分別減去一個(gè)常數(shù)ui，從每列元素分別減去一個(gè)常數(shù)vj,所得新的費(fèi)用矩陣{bij}nn的任務(wù)分配問題的最優(yōu)解等價(jià)于原問題的最優(yōu)解.匈牙利算法的基本思路：根據(jù)定理1變換費(fèi)用矩陣,使矩陣中有足夠多的零.若矩陣中存在n個(gè)不同行不同列的零,就找到了最優(yōu)解否則，就尚未找到最優(yōu)解,設(shè)法進(jìn)一步變換矩陣,增加新的零.匈牙利算法定理1如果從費(fèi)用矩陣{cij}nn中每行元85例1有四個(gè)熟練工人，他們都是多面手，有四項(xiàng)任務(wù)要他們完成。若規(guī)定每人必須完成且只完成一項(xiàng)任務(wù)，而每人完成每項(xiàng)任務(wù)的工時(shí)耗費(fèi)如表4.6.1，問如何分配任務(wù)使完成四項(xiàng)任務(wù)的總工時(shí)耗費(fèi)最少？例1有四個(gè)熟練工人，他們都是多面手，有四項(xiàng)任務(wù)要他86匈牙利算法的步驟：第一步：變換費(fèi)用矩陣，使每行每列至少有一個(gè)零行變換：找出每行最小元素，從該行各元素中減去之列變換：找出每列最小元素，從該列各元素中減去之第二步(試分配)：檢查矩陣中是否存在n個(gè)不同行不同列的零檢查規(guī)則2、逐列檢查，找零最少列的某個(gè)零(所在行零較少的)標(biāo)記()，將()標(biāo)記元素同行同列上其它的零打上*標(biāo)記。重復(fù)1,2，直到所有行列檢查完；1、逐行檢查，找零最少行的某個(gè)零(所在列零較少的)標(biāo)記()，將()標(biāo)記元素同行同列上其它的零打上*標(biāo)記；匈牙利算法的步驟：第一步：變換費(fèi)用矩陣，使每行每列至少有一個(gè)873、重復(fù)1、2后，可能出現(xiàn)兩種情況：每行都有一個(gè)(0)，顯然已找到最優(yōu)解，令對(duì)應(yīng)(0)位置的xij=1；b.所有零都已標(biāo)記，但標(biāo)有()的零的個(gè)數(shù)少于m；

開始劃線過程：對(duì)沒有標(biāo)記()的行打

對(duì)打行上所有其它零元素對(duì)應(yīng)的列打再對(duì)打

列上有()標(biāo)記的零元素對(duì)應(yīng)的行打重復(fù)上述過程，直至無法繼續(xù)對(duì)沒有打的行劃橫線，對(duì)所有打的列劃豎線

3、重復(fù)1、2后，可能出現(xiàn)兩種情況：b.所有零都已標(biāo)記，但88b.所有零都已標(biāo)記，但標(biāo)有()的零的個(gè)數(shù)少于m；

開始劃線過程：對(duì)沒有標(biāo)記()的行打

對(duì)打行上所有其它零元素對(duì)應(yīng)的列打再對(duì)打

列上有()標(biāo)記的零元素對(duì)應(yīng)的行打重復(fù)上述過程，直至無法繼續(xù)對(duì)沒有打的行劃橫線，對(duì)所有打的列劃豎線

b.所有零都已標(biāo)記，但標(biāo)有()的零的個(gè)數(shù)少于m；89第三步：進(jìn)一步變換；在未劃線的元素中找最小者，設(shè)為對(duì)未被直線覆蓋的各元素減去對(duì)雙線覆蓋的元素加上對(duì)單線覆蓋的元素保持不變以上步驟實(shí)際上仍是利用定理1第四步：抹除所有標(biāo)記，回到第二步，重新試分配；第三步：進(jìn)一步變換；第四步：抹除所有標(biāo)記，回到第二步，重新試90關(guān)于匈牙利算法的適用條件要求所有cij0若某些cij<0，則利用定理1進(jìn)行變換，使所有bij0(令bij=

cij+M)目標(biāo)函數(shù)為min型1.對(duì)于max∑∑cijxij型目標(biāo)函數(shù)，等效于求min-∑∑cijxij=

min∑∑-cijxij型問題；再利用定理1進(jìn)行變換，使所有bij=

cij+M0，則可采用匈牙利算法2.對(duì)于人數(shù)n大于工作數(shù)mC=[cij]n×m可令cnj=0,j=m+1,m+2,…,n.即增加虛擬工作Jm+1,

Jm+2,

…,

Jn

,其費(fèi)用cnj=0關(guān)于匈牙利算法的適用條件要求所有cij01.對(duì)于max∑913.對(duì)于人數(shù)n小于工作數(shù)ma.若要求每人做一項(xiàng)工作，則同情況2,C=[cij]n×m可令cim=0,i=n+1,n+2,…,m.即增加虛擬人Jm+1,

Jm+2,

…,

Jn,其費(fèi)用cnj=0.b.若要求所有工作有人做，任意兩人做的工作至多差一項(xiàng)？3.對(duì)于人數(shù)n小于工作數(shù)ma.若要求每人做一項(xiàng)工作，則同情況92丁的蛙泳成績退步到1152；戊的自由泳成績進(jìn)步到575,組成接力隊(duì)的方案是否應(yīng)該調(diào)整？如何選拔隊(duì)員組成4100米混合泳接力隊(duì)?例1混合泳接力隊(duì)的選拔

甲乙丙丁戊蝶泳10685721181101074仰泳115610610781142111蛙泳1271064124610961238自由泳5865359457210245名候選人的百米成績窮舉法：組成接力隊(duì)的方案共有5!=120種。丁的蛙泳成績退步到1152；戊的自由泳成績進(jìn)步到5793目標(biāo)函數(shù)若選擇隊(duì)員i參加泳姿j的比賽，記xij=1,否則記xij=0

0-1規(guī)劃模型

cij(秒)~隊(duì)員i第j種泳姿的百米成績約束條件每人最多入選泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每種泳姿有且只有1人目標(biāo)函數(shù)若選擇隊(duì)員i參加泳姿j的比賽，記xij=1,否則94ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.466.857.2787067.475.66667.874.2718766.484.669.683.858.65359.457.262.40000066.857.2787067.475.66667.874.2718766.484.669.683.858.65359.457.262.4j=500000ciji=1i=2i=3i=4i=5j=166.857.2795最優(yōu)解：x14=x21=x32=x43=1,其它變量為0;成績?yōu)?53.2(秒)=4132

甲乙丙丁戊蝶泳10685721181101074仰泳115610610781142111蛙泳1271064124610961238自由泳586535945721024甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.最優(yōu)解：x14=x21=x32=x43=1,96為了選修課程門數(shù)最少，應(yīng)學(xué)習(xí)哪些課程？

例2選課策略要求至少選兩門數(shù)學(xué)課、三門運(yùn)籌學(xué)課和兩門計(jì)算機(jī)課課號(hào)課名學(xué)分所屬類別先修課要求1微積分5數(shù)學(xué)

2線性代數(shù)4數(shù)學(xué)

3最優(yōu)化方法4數(shù)學(xué)；運(yùn)籌學(xué)微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)3數(shù)學(xué)；計(jì)算機(jī)計(jì)算機(jī)編程5應(yīng)用統(tǒng)計(jì)4數(shù)學(xué)；運(yùn)籌學(xué)微積分；線性代數(shù)6計(jì)算機(jī)模擬3計(jì)算機(jī)；運(yùn)籌學(xué)計(jì)算機(jī)編程7計(jì)算機(jī)編程2計(jì)算機(jī)

8預(yù)測理論2運(yùn)籌學(xué)應(yīng)用統(tǒng)計(jì)9數(shù)學(xué)實(shí)驗(yàn)3運(yùn)籌學(xué)；計(jì)算機(jī)微積分；線性代數(shù)選修課程最少，且學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程？

為了選修課程門數(shù)最少，應(yīng)學(xué)習(xí)哪些課程？例2選課策970-1規(guī)劃模型

決策變量

目標(biāo)函數(shù)

xi=1~選修課號(hào)i的課程（xi=0~不選）

選修課程總數(shù)最少約束條件最少2門數(shù)學(xué)課，3門運(yùn)籌學(xué)課，2門計(jì)算機(jī)課.課號(hào)課名所屬類別1微積分?jǐn)?shù)學(xué)2線性代數(shù)數(shù)學(xué)3最優(yōu)化方法數(shù)學(xué)；運(yùn)籌學(xué)4數(shù)據(jù)結(jié)構(gòu)數(shù)學(xué)；計(jì)算機(jī)5應(yīng)用統(tǒng)計(jì)數(shù)學(xué)；運(yùn)籌學(xué)6計(jì)算機(jī)模擬計(jì)算機(jī)；運(yùn)籌學(xué)7計(jì)算機(jī)編程計(jì)算機(jī)8預(yù)測理論運(yùn)籌學(xué)9數(shù)學(xué)實(shí)驗(yàn)運(yùn)籌學(xué)；計(jì)算機(jī)0-1規(guī)劃模型決策變量目標(biāo)函數(shù)xi=1~選修課號(hào)i98先修課程要求最優(yōu)解：

x1=x2=x3=x6=x7=x9=1,其它為0；6門課程，總學(xué)分210-1規(guī)劃模型

約束條件x3=1必有x1=x2=1模型求解（LINDO）課號(hào)課名先修課要求1微積分

2線性代數(shù)

3最優(yōu)化方法微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)編程5應(yīng)用統(tǒng)計(jì)微積分；線性代數(shù)6計(jì)算機(jī)模擬計(jì)算機(jī)編程7計(jì)算機(jī)編程

8預(yù)測理論應(yīng)用統(tǒng)計(jì)9數(shù)學(xué)實(shí)驗(yàn)微積分；線性代數(shù)先修課程要求最優(yōu)解：x1=x2=x3=x6=99學(xué)分最多多目標(biāo)優(yōu)化的處理方法：化成單目標(biāo)優(yōu)化。兩目標(biāo)(多目標(biāo))規(guī)劃

討論：選修課程最少，學(xué)分盡量多，應(yīng)學(xué)習(xí)哪些課程？課程最少以學(xué)分最多為目標(biāo)，不管課程多少。以課程最少為目標(biāo)，不管學(xué)分多少。最優(yōu)解如上，6門課程，總學(xué)分21。最優(yōu)解顯然是選修所有9門課程。學(xué)分最多多目標(biāo)優(yōu)化的處理方法：化成單目標(biāo)優(yōu)化。兩目標(biāo)(多目標(biāo)100第四部分動(dòng)態(tài)規(guī)劃建模4.1動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型4.2資源分配問題4.3生產(chǎn)與存儲(chǔ)問題4.4背包問題第四部分動(dòng)態(tài)規(guī)劃建模4.1動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型1011.動(dòng)態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的一種有效的數(shù)學(xué)方法,它是美國學(xué)者R.bellman在1951年提出的,1957年他的專著《動(dòng)態(tài)規(guī)劃》的問世標(biāo)志著運(yùn)籌學(xué)的一個(gè)重要分支——?jiǎng)討B(tài)規(guī)劃的誕生。動(dòng)態(tài)規(guī)劃(DynamicProgramming)簡介

3.動(dòng)態(tài)規(guī)劃是考察解決問題的一種途徑，其基本思想是：把一個(gè)較復(fù)雜的問題按照階段劃分,分解為若干個(gè)較小的局部問題,然后按照局部問題的遞推關(guān)系,依次作出一系列決策,直至整個(gè)問題達(dá)到總體最優(yōu)的目標(biāo).2.所謂多階段決策問題是指這樣一類問題，該問題的決策過

程是一種在多個(gè)相互聯(lián)系的階段分別作出決策以形成序列

決策的過程，而這些決策均是根據(jù)總體最優(yōu)化這一共同的

目標(biāo)而采取的.1.動(dòng)態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的一種有效的數(shù)學(xué)方動(dòng)102v2v3v4v7v5v9v6v8v10285121310710131128658854【例4.1】最短路徑問題圖4－1表示從起點(diǎn)v1到終點(diǎn)v10之間各點(diǎn)的距離.求v1到v10的最短路徑.圖4－1v1第1階段第2階段第3階段第4階段階段：第5階段狀態(tài)：v1v2,v3,v4v5,

v6v7,

v8,v9

v10v2v3v4v7v5v9v6v8v1028512131071103v2v3v4v7v5v9v6v8v1028512131071013112865885405847圖4－1v1第1階段第2階段第3階段第4階段階段：第5階段1217142019Min{2+5,8+8,6+4}=7v2v3v4v7v5v9v6v8v1028512131071104動(dòng)態(tài)規(guī)劃問題的基本特征：

1.問題具有多階段決策的特征:階段可按時(shí)間劃分，也可按空間劃分.2.每一階段都有相應(yīng)的“狀態(tài)”與之對(duì)應(yīng).3.每一階段的某個(gè)狀態(tài)都面臨若干個(gè)決策，選擇不同的決策將會(huì)導(dǎo)致下一階段不同的狀態(tài)，同時(shí)，不同的決策將會(huì)導(dǎo)致這一階段不同的目標(biāo)函數(shù)值.4.每一階段的最優(yōu)解問題可以遞歸地歸結(jié)為下一階段各個(gè)可能狀態(tài)的最優(yōu)解問題，各子問題與原問題具有完全相同的結(jié)構(gòu).注：動(dòng)態(tài)規(guī)劃解決問題的關(guān)鍵將問題歸結(jié)為一個(gè)遞推過程,建立一個(gè)遞推的指標(biāo)函數(shù)求最優(yōu)解.這種遞推歸結(jié)的過程,稱為“不變嵌入”.動(dòng)態(tài)規(guī)劃問題的基本特征：1.問題具有多1055.狀態(tài)具有無后效性:當(dāng)某階段狀態(tài)確定后，此階段以后過程的發(fā)展不受此階段以前各階段狀態(tài)的影響。如下圖所示：9AB1B2B3D1C1C4C3D2E7812121441213651064C2905.狀態(tài)具有無后效性:當(dāng)某階段狀態(tài)106動(dòng)態(tài)規(guī)劃基本原理:

是將一個(gè)問題的最優(yōu)解轉(zhuǎn)化為求子問題的最優(yōu)解,研究的對(duì)象是決策過程的最優(yōu)化,其變量是流動(dòng)的時(shí)間或變動(dòng)的狀態(tài),最后到達(dá)整個(gè)系統(tǒng)最優(yōu).注：基本原理一方面說明原問題的最優(yōu)解中包含了子問題的最優(yōu)解，另一方面給出了一種求解問題的思路，將一個(gè)難以直接解決的大問題，分割成一些規(guī)模較小的相同子問題，每一個(gè)子問題只解一次，并將結(jié)果保存起來以后直接引用，避免每次碰到時(shí)都要重復(fù)計(jì)算，以便各個(gè)擊破，分而治之，即分治法，是一種解決最優(yōu)化問題的算法策略.動(dòng)態(tài)規(guī)劃求解可分為三個(gè)步驟：分解、求解與合并.動(dòng)態(tài)規(guī)劃基本原理:是將一個(gè)問題的最優(yōu)解轉(zhuǎn)化為求子問題的最優(yōu)107(1)階段：表示決策順序的時(shí)段序列，階段可按時(shí)間或空間劃分,階段數(shù)用變量k表示.4.1.2基本概念(3)決策

xk：從某一狀態(tài)向下一狀態(tài)轉(zhuǎn)移時(shí)所做的選擇,決策變量記為xk，xk是所在狀態(tài)sk的函數(shù).(2)狀態(tài)sk：描述決策過程當(dāng)前特征并且具有無后效性的量.狀態(tài)可以是數(shù)量,也可以是字符,數(shù)量狀態(tài)可以是連續(xù)的,也可以是離散的.每一狀態(tài)可以取不同值,狀態(tài)變量記為sk.各階段所有狀態(tài)組成的集合稱為狀態(tài)集.在狀態(tài)sk下，允許采取決策的全體稱為允許決策集合,記為Dk(sk).各階段所有決策組成的集合稱為決策集.(1)階段：表示決策順序的時(shí)段序列，階段可按時(shí)間或4.1.108(4)策略：從第1階段開始到最后階段全過程的決策構(gòu)成的序列稱為策略，第k階段到最后階段的決策序列稱為子策略.(5)狀態(tài)轉(zhuǎn)移方程:某一狀態(tài)以及該狀態(tài)下的決策，與下一狀態(tài)之間的函數(shù)關(guān)系，記為:sk+1=T(sk,xk)(6)指標(biāo)函數(shù)或收益函數(shù)：是衡量對(duì)決策過程進(jìn)行控制的效果的數(shù)量指標(biāo)，具體可以是收益、成本、距離等指標(biāo).分為k階段指標(biāo)函數(shù)、k子過程指標(biāo)函數(shù)及最優(yōu)指標(biāo)函數(shù).注：某一階段的狀態(tài)與下一階段的狀態(tài)有某