PAGEPAGE10貨機裝運模型問題重述一架貨機有三個貨艙前艙中艙和后艙三個貨艙所能裝載的貨物的最大重量和體積有限制如下表所示并且為了飛機的平衡三個貨艙共裝載的貨物重量必須與其最大的容許量成比例。前艙中艙后艙重量限制（噸）10168體積限制（立方米）600800500現(xiàn)有四類貨物共該貨機本次飛行裝運，貨物的規(guī)格以及裝運后獲得的利潤如下表重量（噸）空間（立方米/噸）利潤（元/噸）貨物11840300貨物21560300貨物32350300貨物41230250應(yīng)如何安排裝運，使得貨機本次飛行獲利最大？模型假設(shè)：（1）每種貨物可以無限細(xì)分；（2）每種貨物可以分布在一個或者多個貨艙內(nèi)；（3）不同的貨物可以放在同一個貨艙內(nèi)，并且可以保證不留空隙。模型建立：決策變量種貨物放在每個貨艙內(nèi)的重量用xij表示第i種貨物放在第j個貨艙內(nèi)的重量，i=,2,4分別表示貨物1，貨物2，貨物3和貨物4。j=,23分別表示前艙、中艙和后艙。前艙（10中艙（16后艙（8噸）（600立米）（800立米）（500立米）1x1，31，x1x2，2232，x2x3，2333，x3貨物1

貨物2

貨物3

貨物41x2x3

x1+x22+x23

x1+x32+x33x1+x42+x43決策目標(biāo)總利潤的最大化，目標(biāo)函數(shù)為3100(11+12+13)+380(x21+x22+x23)+350(x31+x32+x33)+2850(x41+x42+x43)約束條件：（1）供裝載的四種貨物的總重量約束，??11+12+13≤18??x21+x22+x23≤15??x31+x32+x33≤23x41+x42+x43≤12（2）三個貨艙的空間限制?48011+650x21+580x31+390x41≤6800???48012+650x22+580x32+390x42≤8700??48013+650x23+580x33+390x43≤5300（3）三個貨艙的重量限制?11+x21+x31+x41≤10???12+x22+x32+x42≤16??13+x23+x33+x43≤8（4）三個貨艙裝入重量的平衡約束11+x21+x31+x41

=12+x22+x32+x42=13+x23+x33+x4310168模型求解：使用計算軟件求解（在MTLAB，可以使用lnprg命令解）求解結(jié)果為：(1;x2;x3;x4)=(,,1,1.94,3.05,0)MTLAB實現(xiàn)線性規(guī)劃的運算為了避免這種形式多樣性帶來的不便，Malb中規(guī)定線性規(guī)劃的標(biāo)準(zhǔn)形式為min

cTx

suchthat

Ax≤bAeq?x=beqlb≤x≤ub其中c和x為n維列向量，A、Aeq為適當(dāng)維數(shù)的矩陣，b、beq為適當(dāng)維數(shù)的列向量。例如線性規(guī)劃的Malb準(zhǔn)型為

maxcTxx

suchthat

Ax≥bminx

?cTx

suchthat

?Ax≤?b基本函數(shù)形式為linprog(c,A,b)它的返回值是向量x的值還有其它的一些函數(shù)調(diào)用形（在Matab指窗運行hlpinpog可看到所有的函數(shù)調(diào)用形式，如：[x,val]lnpog(c,Ab,Aebe,LB,UB,,OPTIONS)這里fval回目標(biāo)函數(shù)的值，LB和UB分別是變量x的下界和上界，x0是x的初始值，OPTIONS是控制參數(shù)。注：liprg的式=liprog(f,,b可以求線性規(guī)劃問題inf*xs.t.A*x<=b=liprog(f,,b,e,eq)可以求解線性規(guī)劃問題inf*xst.*x=,eq*x=eqX=LINPROG(f,A,b,Aeqbq,LB,UB以對上述問題中的變量加上范圍約束LB<=X<=UB當(dāng)無下限時可設(shè)為LB=-inf無上限可以設(shè)定UB=infX=LINPROG(f,A,b,Aeqbq,LB,UB,X0)給出了初點X0例1求解列線性規(guī)劃問題maxz=21+3x2?5x3?1+x2+x3=7???21?5x2+x3≥10??1,x2,x3≥0解（i）寫M文件c=[2;3;-5];a=[-2,5,-1];b=-10;aeq=[1,1,1];beq=7;x=linprog(-c,a,b,aeq,beq,zeros(3,1))value=c'*x（ii）將M文件存盤，并命名為exple1.。（iii）Maab指令窗行exaple即可得所求結(jié)果。例2求解性規(guī)劃問題minz=21+3x2+x3?1+4x2+2x3≥8???31+2x2≥6??1,x2,x3≥0解編寫alab程序如：c[;;];a[,,;20;b[;];[,]lno(,a-[,]zr(,))可以化為線性規(guī)劃的幾種類型很多看起來不是線性規(guī)劃的問題也可以通過變換變成線性規(guī)劃的問題來解決。如：例3規(guī)劃問題為mins.t.

|1|+|x2|+L+|xn|Ax≤bn其中x=[1Ln

xT，A和b為相應(yīng)維數(shù)的矩陣和向量。注意到對任意的xi，存在ui,vi>0滿足xi=ui?vi，|xi=ui+vixi+|xi|

|xi|?xi事實上，我們只要取ui

=，vi2

=就可以滿足上面的條件。2這樣，記u=[1

1Lun1

T，v=[v

Lvn

T，從而我們可以把上面的問題變成min

n∑(ui+vi)i1s.t.

?(u?v)≤b?u,v≥0例4mimax

xi?yi}。iyi對于這個問題，如果我們?nèi)=maxyi

xi?yi，這樣，上面的問題就變換成minzs.t.

1?1≤z,L,xn?yn≤z此即我們通常的線性規(guī)劃問題。和例4相似的形式如mamax

axi+byi},mamin

axi+byi}也可以用同樣的方法處理。

iyi

iyi問題重述：

模型二飛行管理問題（1995A）在約1000米高空某邊長10公里的正方形區(qū)域內(nèi)經(jīng)常有若干架飛機作水平飛行。區(qū)域內(nèi)每架飛機的位置和速度向量均由計算機記錄其數(shù)據(jù)以便進行飛行管理當(dāng)一架欲進入該區(qū)域的飛機到達(dá)區(qū)域邊緣時記錄其數(shù)據(jù)后要立即計算并判斷是否會與區(qū)域內(nèi)的其它飛機發(fā)生相撞如果發(fā)生相撞則應(yīng)計算如何調(diào)整各（包括新進入的飛機的飛行方向角，以避免碰撞。現(xiàn)假設(shè)條件如下：1．不相撞的標(biāo)準(zhǔn)為任意兩架飛機的距離大于8里；2．飛機飛行方向角調(diào)整的幅度不應(yīng)超過0度；3．所有飛機的飛行速度均為每小時80公里；4．進入該區(qū)域的飛機在到達(dá)區(qū)域邊緣時，與區(qū)域內(nèi)飛機的距離應(yīng)在0里以上；5．最多需考慮6架飛機；6．不必考慮飛機離開此區(qū)域后的情況。請你對這個避免碰撞的飛行管理問題建立數(shù)學(xué)模型，列出計算步驟，對以下數(shù)據(jù)進行計算（方向角誤差不超過001要求飛機飛行方向角調(diào)整的幅度盡量小。設(shè)該區(qū)域4個頂點的坐標(biāo)（00（10010606錄數(shù)據(jù)為：飛機編號橫坐標(biāo)縱坐標(biāo)方向角（度）110102328585263101520.541550195101020新進入0052注：方向角指飛行方向與x軸正的夾角。問題分析問題是一個在一定約束條件下的最優(yōu)化問題優(yōu)化的目標(biāo)是所有飛機調(diào)整的角度之和最小約束條件是不相撞以及飛機的調(diào)整幅度限制由于不需要考慮飛機飛出區(qū)域后的情況，我們考慮的范圍可以局限在該區(qū)域內(nèi)不相撞。模型假設(shè)：（1）飛機進入?yún)^(qū)域邊緣時，立即作出計算，每架飛機按照計算后的指示立即作方向角改變；（2）每架飛機在整個過程中至多改變一次方向；（3）忽略飛機轉(zhuǎn)向的影（轉(zhuǎn)彎半徑和轉(zhuǎn)彎時間的影響即飛機在接到指令后可以在瞬間調(diào)整好自己的方向；（4）新飛機進入空域時,已空域內(nèi)部飛行的飛機的飛行方向已調(diào)合適，不會碰撞；（5）相同的調(diào)整量對每架飛機影響程度一樣的。模型記號說明：(xit),yit))—t時刻第i架飛機的位置坐標(biāo)i—第i架飛機飛出正方形區(qū)域邊界所需時間v—為飛機的速度iiθ0,θ—第iiiiiiθ—第i架飛機調(diào)整的角度，θ=iii

+Δθi，i=,,L,n模型建立：目標(biāo)函數(shù)：本問題要求所有飛機的調(diào)整角度最小，該目標(biāo)可以有下面幾種方式描述：（a）min

∑|θi|（b）mini

∑(θi)2i2

（c）min

max|θi|不管是哪個目標(biāo)函數(shù)，都是非線性寒暑，因此此問題是一個非線性規(guī)劃問題。約束條件的處理（a）不相撞的條件：(x(t)?x

(t))2+(y(t)?y

(t))2>641≤i≤n?1i+1≤

j≤n0≤t≤minT,T}ijijij其中n為飛機的總架數(shù)。這里xi(t)=xi(0)+vtcosθi，yi(t)=yi(0)+vtsinθi，i=,,L,n；注對于該條件的處理由于條件中涉及到時間t因此屬于函數(shù)的限制問題該條件可以化簡為沒有時間的形式：[max

(xit)?xj

t))2+(yt)?y

t))2]>64

t∈[,mini,Tj

j)]。j（b）調(diào)整角度要求：模型求解：

iiθ=θii

πi+Δθi，|Δθi≤i6

，i=,,L,n。利用非線性規(guī)劃的求解方法可以求出此問題的解對于非線性規(guī)劃問題的解法最優(yōu)化理論中專門有研究，現(xiàn)在比較常見的方法有：0.18法插值法，切線法，二分法，最速下降法共軛梯度法牛頓法變尺度法懲罰函數(shù)法等甚至有些問題可以將非線性規(guī)劃問題轉(zhuǎn)化為線性規(guī)劃問題。在實踐中要求大家掌握實用MTLAB程序計算最優(yōu)解。非線性規(guī)劃知識介紹：在一組等式或不等式的約束下，求一個函數(shù)的最大值（或最小值）問題，其中至少有一個非線性函數(shù)，這類問題稱之為非線性規(guī)劃問題。可概括為一般形式min

f(x)s.t.

hj(x)≤,

j=,L,q

Ngi(x)=,

i=,L,pni其中x=[1Lni

xT稱為模（NP決策變量，f稱為目標(biāo)函數(shù)，g

(i=,L,p)和hj(j=,L,q)稱為約束函數(shù)。另外，gi(x)=0(j=,L,q)稱為不等式的約束。

(i=,L,p)稱為等式約束，hj(x)≤0對于一個實際問題，在把它歸結(jié)成非線性規(guī)劃問題時，一般要注意如下幾點：（i確定供選方案首先要收集同問題有關(guān)的資料和數(shù)據(jù)在全面熟悉問題的基礎(chǔ)上，確認(rèn)什么是問題的可供選擇的方案，并用一組變量來表示它們。（ii）提出追求目標(biāo)：經(jīng)過資料分析，根據(jù)實際需要和可能，提出要追求極小化或極大化的目標(biāo)。并且，運用各種科學(xué)和技術(shù)原理，把它表示成數(shù)學(xué)關(guān)系式。（iii給價值標(biāo)準(zhǔn)在提出要追求的目標(biāo)之后要確立所考慮目標(biāo)“好壞”的價值標(biāo)準(zhǔn)，并用某種數(shù)量形式來描述它。（iv）尋求限制條件：由于所追求的目標(biāo)一般都要在一定的條件下取得極小化或極大化效果因此還需要尋找出問題的所有限制條件這些條件通常用變量之間的一些不等式或等式來表示。注：非線性規(guī)劃的Malb解法Matb中線性規(guī)劃的數(shù)學(xué)模型寫成以下形式min

f(x)??Ax≤B??Aeq?x=Beq?,C(x)≤0Ceq(x)=0其中f(x)是標(biāo)量函數(shù)，,B,Aeq,Beq是相應(yīng)維數(shù)的矩陣和向量，C(x),Ceq(x)是非線性向量函數(shù)。Matlab中命令是XFICNU,0ABe,e,BBNNCNPIN它的返回值是向量x，其中FUN用M文定義的函數(shù)f(x)；X0是x的初始值；ABAqBq定義了線性約束A*X

≤B,Aeq*X

=Beq，如果沒有等式約束，則A[,=],Aeq=[],Beq=[]；LB和UB是變量x的下界和上界，如果上界和下界沒有約束，則L=]U=]如果x無下界則LB=-inf如果x無上界則UB=infNONLCON是用M文件定義的非線性向量函數(shù)C(x),Ceq(x)；OPTIONS定義了化參數(shù)，可以使用Matlab缺省的參數(shù)設(shè)置。例5求下非線性規(guī)劃?minf(x)=x2+x2+812x2?1?x2≥0x2?2??12???

?x2+2=0?1,x2≥0.（i）編寫M文件fun1.mfunctionf=fun1(x);f=x(1)^2+x(2)^2+8;和M文件fun2.mfunction[g,h]=fun2(x);g=-x(1)^2+x(2);h=-x(1)-x(2)^2+2;%等式約束（ii）在aab的命令口依次輸入options=optimset('largescale','off');[x,y]=fmincon('fun1',rand(2,1),[],[],[],[],zeros(2,1),[],...'fun2',options)就可以求得當(dāng)1=,x2=1時，最小值y=10。模型三鋼管下料問題（整數(shù)規(guī)劃模型）某鋼管零售商從鋼管廠進貨，將鋼管按照顧客的要求切割后售出。從鋼管廠進貨時得到的原料鋼管都是9米長現(xiàn)有一客戶需要0根4米長0根6米長和15根8米長鋼管應(yīng)如何下料最節(jié)省？問題分析首先應(yīng)當(dāng)確定哪些切割模式是可行的所謂一個切割模式是指按照客戶需要在原料鋼管上安排切割的一種組合。例如，我們可以將9米長鋼管切割成3根4米長鋼管，余料為7或者將19米長的鋼管切割成46米和8長的鋼管各1根余料為1顯然，可行的切割模式是很多的。其次應(yīng)當(dāng)確定哪些切割模式是合理的通常假設(shè)一個合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸。例如，將9米長鋼管切割成3根4米的管是可行的，但余料為7米可以進一步將7米的料切割成4米鋼管（余料為3或者將7米的余料切割成6米管（余料為1米。在種合理性假設(shè)下，切割模式一共有7種，如表1所示。表1鋼管下料的合理切割模式4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料（米）模式14003=9-6模式23101=9-2-6模式32013=9-8-8模式41203=9-4-2模式51111=9-4-68模式60301=9-8模式70023=9-6問題化為在滿足客戶需要的條件下，按照哪些種合理的模式，切割多少根原料鋼管，最為節(jié)省而所謂節(jié)省可以有兩種標(biāo)準(zhǔn)一是切割后剩余的總余料量最小二是切割原料鋼管的總根數(shù)最少。模型建立：決策變量：xi,i=,,L,7（七種模式切割的原料鋼管的根數(shù)，為非負(fù)正整數(shù)）決策目標(biāo)：模型1：使切割后剩余的總料量最小min

31+x2+3x3+3x4+x5+x6+3x7模型2：切原料鋼管的總根數(shù)最少min

1+x2+x3+x4+x5+x6+x7約束條件滿足顧客要求）41+3x2+2x3+x4+x5≥50x2+2x4+x5+3x6≥20x3+x5+2x7≥15模型求解：對于整數(shù)規(guī)劃（主要是整數(shù)線性規(guī)劃）問題，主要是采用分支定界法求解。即通過無整數(shù)約束下的線性規(guī)劃的解得到整數(shù)約束下的（認(rèn)為整數(shù)規(guī)劃的解應(yīng)當(dāng)在無整數(shù)規(guī)劃的解的附近得到，在MTLB中可以用相應(yīng)的程序計算。對于模型1，計算得最優(yōu)解為(12,,01,,0)，按照模式2切割12根，照模式5切割5根總余料量為7米。對于模型2計算得最優(yōu)解為(1,,,)，按照模式2切割5根，按照式5切割5根，照模式7割5根，共5根，總余量為5米。當(dāng)余料沒有用途時，可以按照模型2的方式確下料方式。鋼管下料問題2：在同樣的問題背景下，增加一種需求：5米10根；但是要求切割模式不超過3問題分析：和上面的模型不一樣的地方在于（1需求量增（這不是最主要的如果僅有這個附加要求，可以仍像上面的方法求解（2）切模式不超過3種（這是主要的條件，因為現(xiàn)在無法確切知道應(yīng)當(dāng)適用哪三種方式）模型建立：（1）使用和上面的模型建立相同的方法。首先分析可能的下料模式如下：模式123456789101112131415164米00000011112223345米00112200130120106米03120112000101008米2010101010000000余料3102131320301123其次建立模型，由于有切割方式不超過3種要求，可以從上述16下料方式中選擇3種進行建這樣做可以象前面的模型一樣求解易理解但是工作量實在太大因為需16要將16種料方式眾人已三種組合都計算一遍有C316

=560中這就意味著需要計算560個模型，最后通過比較這560個型的結(jié)果得到最終的選擇。（2）另外辦法。不預(yù)先指定下料的方式，而是將下料的方式也設(shè)為變量，通過最優(yōu)解的結(jié)果得到選擇的下料方式和下料數(shù)量。設(shè)xi為按第i種模式切割的原料鋼管根數(shù)，i=,23i1,i2,i3,i4分別為第i種切割模式下每根原料鋼管生產(chǎn)4米5米6米和8米的鋼管的數(shù)量（注意，并沒有指定按照哪種方式下料）目標(biāo)函數(shù)：min

1+x2+x3約束條件：（1）滿足求111+12x2+13x3≥50211+22x2+23x3≥10311+32x2+33x3≥20411+42x2+43x3≥15（2）余料制（模式合理要求）16≤411+521+631+41≤1916≤412+522+632+842≤1916≤413+23+633+843≤19（3）整數(shù)束xi,ij均為整數(shù)模型求解：上述問題屬于非線性整數(shù)規(guī)劃問題可以使用一些數(shù)學(xué)軟件求解對于規(guī)模比較大的問題可以通過增加合理的條件減少計算機搜索的區(qū)域便于求解如本例中可以增加條件26≤1+x2+x3≤31；其中1+x2+x3≥26由[4×50+5×10+6×20+8×15]=2619得到而1+x2+x3≤31由一種特殊的下料方式切割成4根4米鋼管需3根割成1根5和2根6鋼管，需0根；切割成2根8米鋼，需8根得到，這種下料方式總共需要31根鋼管。按照模型目標(biāo)中對于具體的模式標(biāo)記沒有限制，可以增加假設(shè)1≥x2≥x3。使用軟件計算得到所選擇的下料模式有：模式1：每原料鋼管切割成2根4米、1根5和1根6鋼管，共10根模式2：每原料鋼管切成3根4和1根6鋼管,共0根；模式3：每原料鋼管切割成2根8米鋼管，共8根原料鋼管總根數(shù)為28。確定下料方式和建立規(guī)劃模型對于一維下料問（如鋼管下料問題當(dāng)規(guī)格不太多，可枚舉下料模式建立整數(shù)線性規(guī)劃模型否則要構(gòu)造整數(shù)非線性規(guī)劃模型求解困難可用縮小可行域的方法進行化簡但要保證最優(yōu)解的存在對于二維下料問題請參考易拉罐的下料問題及補充材料。整數(shù)規(guī)劃的求解方法：常用的整數(shù)規(guī)劃求解方法有：（i）分枝定界法—可求純或混合整數(shù)線性規(guī)劃。（ii）割平法—可求純或混合整數(shù)線性規(guī)劃。（iii）隱枚法—求解“0-1”整數(shù)規(guī)：①過濾枚舉法；②分枝枚舉法。（iv）匈牙法—解決指派問題“0-”規(guī)劃特殊情形。（v）蒙特洛法—求解各種類型規(guī)劃。1．分枝定界法將要求解的整數(shù)規(guī)劃問題稱為問題A，將與它相應(yīng)的線性規(guī)劃問題稱為問題B。（i）解問題B可能得到以下情況之一：（a）B沒有可行解，這時A也沒有可行解，則停止．b）B有最優(yōu)解并符合問題A的整數(shù)條件，B的最優(yōu)解即為A的最優(yōu)解則停止。（c）B有最優(yōu)解，但不符合問題A的整數(shù)條件，記它的目標(biāo)函數(shù)值為z。（ii用觀察法找問題A的一個整數(shù)可行解一般可取xj=,j=,L,n試探求得其目標(biāo)函數(shù)值，并記作z。以z*表示問題A的最優(yōu)目標(biāo)函數(shù)值；這時有z≤z*≤z進行迭代。第一步分枝在B的最優(yōu)解中任選一個不符合整數(shù)條件的變量xj其值為bj以[bj]表示小于bj的最大整數(shù)。構(gòu)造兩個約束條件xj≤[bj]和

xj≥bj]+1將這兩個約束條件分別加入問題B求兩個后繼規(guī)劃問題1和2不考慮整數(shù)條件求解這兩個后繼問題。定界以每個后繼問題為一分枝標(biāo)明求解的結(jié)果與其它問題的解的結(jié)果中找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界z從已符合整數(shù)條件的各分支中找出目標(biāo)函數(shù)值為最大者作為新的下界z，若無作用z不變。第二步比較與剪枝各分枝的最優(yōu)目標(biāo)函數(shù)中若有小于z者則剪掉這枝即以后不再考慮了。若大于z，且不符合整數(shù)條件，則重復(fù)第一步驟。一直到最后得到z*=z為j止。得最優(yōu)整數(shù)解x*,j=,L,n。j例6求解述整數(shù)規(guī)劃Max

z=401+90291+7x2≤56?71+20x2≤70??1,x2≥0

且為整數(shù)解（i）先考慮整數(shù)限制，即解相應(yīng)的線性規(guī)劃B，得最優(yōu)解為：1=809,2=816,z=355.8779可見它不符合整數(shù)條件。這時z是問題A的最優(yōu)目標(biāo)函數(shù)值z*的上界，記作z。而*1=,x2=0顯然是問題A的一個整數(shù)可行解，這時z=0，是z*

的一個下界，記作z，即0≤z*≤356。（ii）因為1,2當(dāng)前均為非整數(shù)，故不滿足整數(shù)要求，任選一個進行分枝。設(shè)選1進行分枝，把可行集分成2個子集：1≤[4.8092]=4，1≥[4.8092]+1=5因為4與5之間無整數(shù)故這兩個子集的整數(shù)解必與原可行集合整數(shù)解一致這一步稱為分枝。這兩個子集的規(guī)劃及求解如下：問題1：

Max

z=401+90291+7x2≤56??71+20x2≤70?0≤1≤,x2≥0最優(yōu)解為：1=,2=,1=349。問題2：

Max

z=401+90291+7x2≤56??71+20x2≤70??1≥,x2≥0最優(yōu)解為：1=.,2=5,1=344。再定界：0≤z*≤349。（iii）對問題1再進行分枝得問題11和12，它們的最優(yōu)解為11:

1=,2=,11=34012:

1=1.43,x2=0,12=327.1412再定界：340≤z*≤341，并將B12

剪枝。（iv）對問題2再進行分枝得問題21和22，它們的最優(yōu)解為21:

1=5.44,x2=0,z22=0822無可行解。將21,22剪枝。于是可以得到原問題的最優(yōu)解為：1=,x2

=,z*=340整數(shù)規(guī)劃的計算機實現(xiàn)：可以在MTLAB中按照分支定界法的思想編程實現(xiàn)；對于0-1規(guī)劃問，MTLAB提供命令bnprog解。MTLAB中0-1規(guī)劃的準(zhǔn)形式：inf*Xs.t.A*X<=b,Aeq*X=beq,中X的每個分量為0或者1。（1）X=BNTPROG(f)求解問題inf*X（2）X=BNTPROG(f,A,b)求解inf*Xs.t.*X<=b（3）X=BNTPROG(f,A,b,Aeq,beq)求解inf*Xs.t.Aeq*X=bq,A*X<=b問題重述：

模型四選課策略問題（多目標(biāo)規(guī)劃）某個學(xué)校規(guī)定，某專業(yè)的學(xué)生畢業(yè)時必須至少學(xué)習(xí)過兩門數(shù)學(xué)課程、三門運籌學(xué)課程和兩門計算機課程。這些課程的編號、名稱、學(xué)分、所屬類別和先修課程要求如下表所示。那么畢業(yè)使學(xué)生最少可以學(xué)習(xí)這些課程中的那些課程如果某個學(xué)生既希望選修課程的數(shù)量少，又希望所獲得的學(xué)分多，它可以選修那些課程？課號課名學(xué)分所屬類別先修課要求1微積分5數(shù)學(xué)2線性代數(shù)4數(shù)學(xué)3最優(yōu)化方法4數(shù)學(xué)；運籌學(xué)微積分；線性代數(shù)4數(shù)據(jù)結(jié)構(gòu)3數(shù)學(xué)；計算機計算機編程5應(yīng)用統(tǒng)計4數(shù)學(xué)；運籌學(xué)微積分；線性代數(shù)6計算機模擬3計算機運籌學(xué)計算機編程7計算機編程2計算機8預(yù)測理論2運籌學(xué)應(yīng)用統(tǒng)計9數(shù)學(xué)實驗3運籌學(xué)計算機微積分；線性代數(shù)模型的建立與求解：用xi,i=,,L9表示選修第i門課程的情況：xi=1表示選修該課程；xi選修該課程。

=0表示不決策目標(biāo)為選修的課程總數(shù)最少，即min

1+x2+L+x9；約束條件：（1）滿足學(xué)分要求（2門學(xué)課程，3運籌學(xué)課程和2門計機課程）1+x2+x3+x4+x5≥2x3+x5+x6+x8+x9≥3x4+x6+x7+x9≥2（2）先修課程要求：（a）數(shù)據(jù)結(jié)構(gòu)的先修課程為計算機編程：x4=1?x7=1轉(zhuǎn)換為x4≤x7；（b）計算機模擬的先修課程為計算機編程：x6≤x7；（c）預(yù)測理論的先修課程為應(yīng)用統(tǒng)計：x8≤x5；（d）最優(yōu)化方法的先修課程為微積分和線性代數(shù)：x3≤1,x3≤x2或者轉(zhuǎn)化為2x3≤1+x2；（e）應(yīng)用統(tǒng)計的先修課程為微積分和線性代數(shù)：x5≤1,x5≤x2者轉(zhuǎn)化為2x5≤1+x2；（f）數(shù)學(xué)實驗的先修課程為微積分和線性代數(shù)：x9≤1,x9≤x2者轉(zhuǎn)化為2x9≤1+x2；（3）0-1限制：xi=1（可以轉(zhuǎn)化為整數(shù)規(guī)劃，0≤xi≤1）模型求解：使用軟件計算得到該問題的解為,,,)即選修的課程為微積分線性代數(shù)、最優(yōu)化方法、計算機模擬、計算機編程和數(shù)學(xué)實驗，總學(xué)分為21。對于第二個問題在課最小的目標(biāo)下也要求使得總的學(xué)分最大因此決策的目標(biāo)除了min

Z=1+x2+L+x9外，還有max

W=51+4x2+4x3+3x4+4x5+3x6+2x7+2x8+3x9因此本問題為兩目標(biāo)規(guī)劃問（多目標(biāo)規(guī)劃是指具有多個決策目標(biāo)的問題相當(dāng)于目標(biāo)函數(shù)為向量函數(shù)的規(guī)劃問題：模型求解：

V?max(?Z,W)。對于多目標(biāo)規(guī)劃問題常使用加權(quán)的方式將多目標(biāo)規(guī)劃問題轉(zhuǎn)化為單目標(biāo)規(guī)劃問題此時需要知道決策者對每個目標(biāo)的偏好程度（即對每個目標(biāo)的重視程度。設(shè)1,λ2，1+λ2=,,2≥0分別表示決策者對兩個目標(biāo)的重視程度則原問題可以轉(zhuǎn)化為下面的單目標(biāo)問題max模型討論：

?1Z+λW。求解該約束單目標(biāo)0-1劃問題可以得到解。（1）1=,λ2=0：最優(yōu)解如上，6課程，總學(xué)分21。（2）λ2=,1=0：最優(yōu)情況為選修所有的9課程。（3在課程最少的前提下以學(xué)分最多為目標(biāo)求解可以增加條件1+L+x9=6得到最優(yōu)解為,,,0)。（4）對學(xué)數(shù)和課程數(shù)加權(quán)形成一個目標(biāo)，如三七開。此時得到的最優(yōu)化問題為max

W?7Z，求得最優(yōu)解為,)，總學(xué)分為2（）也可以討論λ的取值對最優(yōu)解的影響，即考察最優(yōu)解的變化情況。多目標(biāo)規(guī)劃介紹見pdf

模型五動態(tài)規(guī)劃模型問題重（最短路問題某城市需要從A地到G地之間鋪設(shè)煤氣管道方案如下圖所示，每個連線上的數(shù)字表示鋪設(shè)該段管道的成本，問最佳的鋪設(shè)方案（該問題統(tǒng)稱為最短路問題，其他類似的問題有推銷員問題，存貨問題等等，可以用相同的方法解決）模型分析這是一個多階段的決策問題對于多階段的決策問題我們可以嘗試用動態(tài)規(guī)劃的方法加以解決，動態(tài)規(guī)劃問題有一個顯著的特征：拿最短路問題，若已經(jīng)給定從點A至點C的最短路徑則從其上任一中間點B到點C的部分路徑也必然是從B到C的所有可能選擇的路徑中的最短路徑。利用這個性質(zhì)，我們可以從最后一個階段入手，逐步向前遞推，求出各點到終點的最短路線。模型求解：首先將整個管道鋪設(shè)問題分為六個階段：A→B,B→C,C→D,D→E,E→F,F→G。記：sk—第k階段管道的起點；Sk—第k階段管道所有起點的集合；xk—第k階段管道的終點；Xk(sk)—第k階段管道所有以sk為起點的管道的終點集合，簡單記為Xk；dk(sk,xk)—第k階段管道從sk到xk的距離；k—第k階段的起點到終點G的路線；Vk(sk,k)—以sk為第k階段的起點，k為路線，sk到G的距離；fk(sk)—從sk到G的最短距離。按照上面的記號可以發(fā)現(xiàn)：Vk(sk,k)=dk(sk,xk)+Vk1(sk1,k1)；fk(sk)=mindk(sk,xk)+fk1(sk1)|xk∈Xk}；sk1=xk，k=,,1。模型歸結(jié)為求A到G的最短距離，就是計算f1():A→x2→x3→x4→x5→x6→G。當(dāng)k=7時，f7G)=0（假設(shè)7階段為G→G）當(dāng)k=6時，S6={1,2}，x6=G。s6=1,f6(1)=d6(1,G)+f7G)=,V6(1,G)=4；s6=2,f6(2)=d6(2,G)+f7G)=,V6(2,G)=3。當(dāng)k=5時，S5={1,E2,E3}，x5=1,2}。s5=1,X5=X5(1)=1,2}；f5(1)=mind5(1,1)+f6(1),d5(1,2)+f6(2)}=7,5(1,1,G)=7s5=E2,X5=X5(E2)={1,2}；f5(E2)=mind5(E2,1)+f6(1),d5(E2,2)+f6(2)}=,5(E2,2,G)=5s5=E3,X5=X5(E3)=1,2}。f5(E3)=mind5(E3,1)+f6(1),d5(E3,2)+f6(2)}=,5(E3,2,G)=9當(dāng)k=4時，S4={1,D2,3}，s4=1,X4=X4(1)={1,E2}；f4(1)=mind4(1,1)+f5(1),d4(1,E2)+f5(E2)}=7,V4(1,E2,2,G)=7s4=D2,X4=X4(D2)={E2,E3}；f4(D2)=mind4(D2,E2)+f5(E2),d4(D2,E3)+f5(E3)}=,V4(D2,E2,2,G)=6s4=3,X4=X4(3)={E2,E3}。f4(3)=mind4(3,E2)+f5(E2),d4(3,E3)+f5(E3)}=,V4(3,E2,2,G)=8當(dāng)k=3時，S4=1,C2,C3,C4}，s3=1,X3=X31)={1,D2}f31)=mind31,1)+f4(1),d31,D2)+f4(D2)}=1,31,1,E2,2,G)=13s3=C2,X3=X3C2)={1,D2}f3C2)=mind3C2,1)+f4(1),d3C2,D2)+f4(D2)}=1,3C2,1,E2,2,G)=10s3=C3,X3=X3C3)={D2,3}f3C3)=mind3C3,D2)+f4(D2),d3C3,3)+f4(3)}=,。3C3,D2,E2,2,G)=9s3=C4,X3=X3C4)={D2,3}f3C4)=mind3C4,D2)+f4(D2),d4C3,3)+f4(3)}=1,3C4,3,E2,2,G)=12當(dāng)k=2時，S2=1,B2}，s2=1,X2=X2(1)=1,C2,C3}f2(1)=mind2(1,1)+f31),d2(1,C2)+f3C2),d2(1,C3)+f3C3)}=1,V2(1,C2,1,E2,2,G)=13s2=B2,X2=X2(B2)=C2,C3,C4}f2(B2)=mind2(B2,C2)+f3C2),d2(B2,C3)+f3C3),d2(B2,C4)+f3C4)}=1,V2(B2,C3,D2,E2,2,G)=16當(dāng)k=1時，1=,X1=X1()={1,B2}f1()=mind1(,1)+f2(1),d1(,B2)+f2(B2)}=1,1(,1,C2,1,E2,2,G)=18這樣得到最終的結(jié)果，最佳的鋪設(shè)路線為A→1→C2→1→E2→2→G。附：動態(tài)規(guī)劃的基本概念（1）階段：把所給問題的過程，恰當(dāng)?shù)貏澐譃槿舾蓚€相互聯(lián)系的階段，以便能夠按照一定的次序求解。（2）狀態(tài)：過程在該階段所處的各種可能情況。一個階段有若干個狀態(tài)，描述狀態(tài)的變量稱為狀態(tài)變量，sk∈Sk。（3）決策：當(dāng)過程處于某個狀態(tài)時，可以做出不同的決策到達(dá)下階段不同的狀態(tài)。xk(sk)∈Xk表示狀態(tài)為sk時的所有可能的決策。（4）策略：從過程的每個階段的起點到整個過程終點的過程，稱為問題的后部子過程，每段的決策組成的決策序列稱為子策略；從過程的起點到終點的決策序列稱為一個策略，如A→1→C2→1→E2→2→G為一個策略，而其中的一部分1→E2→2→G稱為一個子策略。（5）狀態(tài)轉(zhuǎn)移方程：第k+1階段的狀態(tài)變量sk1與第k階段的狀態(tài)變量sk和決策變量xk之間的關(guān)系。（6）階段效益函數(shù)：衡量該階段決策效果的數(shù)量指標(biāo)dk(sk,xk)（7）目標(biāo)函數(shù)：Vk(sk,k)是定義在第k階段開始至過程終點的子過程上的函數(shù)，表示從k階段狀態(tài)sk開始以k為子策略的目標(biāo)值Vk(sk,k)必須具有遞推關(guān)系一般采用兩種形式：Vk(sk,k)=dk(sk,xk)+Vk1(sk1,k1)或者Vk(sk,k)=dk(sk,xkVk1(sk1,k1)（8）最優(yōu)目標(biāo)函數(shù)：fk(sk)是定義在第k階段開始至過程終點的子過程上的函數(shù)表示從k階段狀態(tài)sk

開始，逐階段到最終狀態(tài)的最優(yōu)目標(biāo)值fk(sk)=min/maxVk(sk,k))。（9）最優(yōu)原理：無論過去的狀態(tài)和策略如何，對前面的決策所形成的狀態(tài)而言，余下的決策必須構(gòu)成最優(yōu)策略，即一個最優(yōu)策略的子策略總是最優(yōu)的。（10）基本方程：反映相鄰兩個階段之間的關(guān)系Vk(sk,k)=dk(sk,xk)+Vk1(sk1,k1)fk(sk)=min/maxdk(sk,xk)+fk1(sk1)|xk∈Xk}sk1=k(sk,xk),k=n,n?,L1建立動態(tài)規(guī)劃數(shù)學(xué)模型的基本思路：（1）將所討論的問題適當(dāng)劃分為多個階段，明確每個階段的決策變量；（2）明確決策變量、階段效益函數(shù)和最優(yōu)值函數(shù)；（3）建立狀態(tài)轉(zhuǎn)移方程；（4）根據(jù)最優(yōu)化原理建立基本方程并求解。需要說明的是，有些投資問題，資源配置的問題也可以用動態(tài)規(guī)劃的方法求解。例7設(shè)某廠有100機器，生產(chǎn)兩種產(chǎn)品B，若投入y臺機器生產(chǎn)A產(chǎn)品，則純收入為5y，若投入y臺機器生產(chǎn)B種產(chǎn)品，則純收入為4y，又知：生產(chǎn)A種產(chǎn)品機器的年折損率為20%生產(chǎn)B產(chǎn)品機器的年折損率為10%問在5年內(nèi)如何安排各年度的生產(chǎn)計劃，才能使總收入最高？解年度階段變量k=,,5。令xk表示第k年初完好機器數(shù)uk表示第k年安排生產(chǎn)A種產(chǎn)品的機器數(shù)則xk?uk為第k年安排生產(chǎn)B種產(chǎn)品的機器數(shù)，且0≤uk則第k+1年初完好的機器數(shù)

≤xk。xk1=1?0.2uk+1?0.)(xk?uk)=0.9xk?0.uk

（2）令vk(xk,uk)表示第k年的純收入，fk(xk)表示第k年初往后各年的最大利潤之和。顯然f6(x6)=0

（13）則fk(xk)=

maxvk(xk,uk)+fk1(xk1)}0≤uk≤xk=maxuk+(xk?uk)+fk1(xk1)}=0≤uk≤xk

maxuk+4xk+fk1(xk1)}0≤uk≤xk

（4）（1）k=5時，由（11）式得f5(x5)=

maxu5+4x5}0≤u5≤5u5+4x5關(guān)于u5求導(dǎo)知其導(dǎo)數(shù)大于零所以u5+4x5在u5等于x5處取得最大值即u5=x5時，f5(x5)=5x5。（2）k=4時，由（11）式得f4(x4)==

maxu4+4x4+5x5}0≤u4≤x4maxu4+4x4+(9x4?u4)}=0≤u4≤x4

maxu4+5x4}0≤u4≤x4當(dāng)u4=x4時，f4(x4)=9x4（3）k=3時，f3(x3)==

maxu3