matlab在運籌學(xué)中的應(yīng)用

第六講Matlab在運籌學(xué)中的應(yīng)用一、線性規(guī)劃求解下列線性規(guī)劃標準型：Minz=fS.ta*x

baeq*x=beqlb

x

ub一、線性規(guī)劃[x,fval,exitflag,output,lambda]=linprog(f,a,b,aeq,beq,lb,ub)x:線性規(guī)劃最優(yōu)解；fval:最優(yōu)值；exitflag:輸出標記，1表示有解；-1表示無解；output:算法和迭代情況；lambda：存儲情況；注意：用linprog時首先要把線性規(guī)劃變化為標準型,f為列向量一、線性規(guī)劃例minz=-3x1-4x2s.t.x1+x2

6

x1+2x2

8

x2

3

x1,x20例minz=-x1-x2s.t.-2x1+x2

4

x1-x2

2x1,x20例：maxz=3x1+2x2s.t.-x1+2x243x1+2x214x1-x2=3x1+x2=5x1,x20一、線性規(guī)劃線性規(guī)劃的應(yīng)用設(shè)備配備下料問題生產(chǎn)計劃安排配料問題投資問題運輸問題。。。。。。一、線性規(guī)劃Maxz=40x1+90x2S.t.

9x1+7x2567x1+20x270x1,x20,整數(shù)7二、整數(shù)規(guī)劃8問題BX1=4.81,X2=1.82,Z=356問題B1X1=4,X2=2.1,Z=349問題B2X1=5,X2=1.57,Z=341問題B4X1=1.42X2=3Z=327問題B3X1=4X2=2Z=340問題B6無可行解問題B5X1=5.44X2=1.00Z=308x14x23x22x15X21x22

例maxz=3x1+2x2s.t.2x1+3x2142x1+x29x1,x20,整數(shù)用linprog寫出計算步驟二、整數(shù)規(guī)劃二、整數(shù)規(guī)劃分支定界算法（1）去掉整數(shù)要求，求出最小值，如為整數(shù)解，停止；如不是整數(shù)，假設(shè)xi=bi不是整數(shù)，分支，轉(zhuǎn)向（2）；（2）以原問題或上一子問題為基礎(chǔ)，分別添加兩個約束，構(gòu)成兩個子問題：xi

[bi]，構(gòu)成第一個子問題；xi

[bi]+1,構(gòu)成第二個子問題。[bi]代表bi整數(shù)部分的值，可有指令fix(bi)得到；（3）分支原則：（a）無效解不分支（b）整數(shù)解不分支（c）雖不是整數(shù)解，但其對應(yīng)的最小值大于已有的整數(shù)解的最小值，不分支（d）其他情況都要分支；（4）當不能再分支時，比較所得的整數(shù)解，最小值者對應(yīng)的就是最優(yōu)解；如果求最大值，可將目標函數(shù)反號每次分支都要形成不等式約束，太繁瑣，自編指令[a1,a2,b1,b2]=intp(k,n,a,b,p)輸入：k:被分支變量的編號；n：矩陣a的列數(shù)；p：要分支的變量值；輸出：a1：分支后一個不等式約束的左端矩陣，

a2為另一個；b1:分支后一個不等式約束右端項；b2為另一個二、整數(shù)規(guī)劃三、網(wǎng)絡(luò)最短路求法介紹Floyd算法，可以確定網(wǎng)絡(luò)上任意兩點間的最短距離。該算法適用于有向圖和無向圖E=[(v1,v2),(v1,v3),(v3,v4),(v1,v4),(v2,v4)]網(wǎng)絡(luò)權(quán)矩陣w=(wij)nn,其中wij=lij(vi,vj)屬于E時wii=0wij=inf(vi,vj)不屬于E時4352v2v3v1v4E=[(v1,v2),(v2,v1),(v1,v3),(v3,v1),(v3,v4),(v4,v3),(v1,v4),(v4,v1),(v2,v4),(v4,v2)]W為對稱矩陣4352v2v3v1v4算法步驟

095316902465202434206166460

0753970246520243420696460973224v1v3v2v5v4三、網(wǎng)絡(luò)最短路求法functiony=fld(n,d)%從d中找到點i到點r之間的最小距離forr=1:nfori=1:nforj=1:np(j)=d(i,j)+d(j,r);end