matlab在运筹学中的应用

第六讲Matlab在运筹学中的应用一、线性规划求解下列线性规划标准型：Minz=fS.ta*x

baeq*x=beqlb

x

ub一、线性规划[x,fval,exitflag,output,lambda]=linprog(f,a,b,aeq,beq,lb,ub)x:线性规划最优解；fval:最优值；exitflag:输出标记，1表示有解；-1表示无解；output:算法和迭代情况；lambda：存储情况；注意：用linprog时首先要把线性规划变化为标准型,f为列向量一、线性规划例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一、线性规划线性规划的应用设备配备下料问题生产计划安排配料问题投资问题运输问题。。。。。。一、线性规划Maxz=40x1+90x2S.t.

9x1+7x2567x1+20x270x1,x20,整数7二、整数规划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,整数用linprog写出计算步骤二、整数规划二、整数规划分支定界算法（1）去掉整数要求，求出最小值，如为整数解，停止；如不是整数，假设xi=bi不是整数，分支，转向（2）；（2）以原问题或上一子问题为基础，分别添加两个约束，构成两个子问题：xi

[bi]，构成第一个子问题；xi

[bi]+1,构成第二个子问题。[bi]代表bi整数部分的值，可有指令fix(bi)得到；（3）分支原则：（a）无效解不分支（b）整数解不分支（c）虽不是整数解，但其对应的最小值大于已有的整数解的最小值，不分支（d）其他情况都要分支；（4）当不能再分支时，比较所得的整数解，最小值者对应的就是最优解；如果求最大值，可将目标函数反号每次分支都要形成不等式约束，太繁琐，自编指令[a1,a2,b1,b2]=intp(k,n,a,b,p)输入：k:被分支变量的编号；n：矩阵a的列数；p：要分支的变量值；输出：a1：分支后一个不等式约束的左端矩阵，

a2为另一个；b1:分支后一个不等式约束右端项；b2为另一个二、整数规划三、网络最短路求法介绍Floyd算法，可以确定网络上任意两点间的最短距离。该算法适用于有向图和无向图E=[(v1,v2),(v1,v3),(v3,v4),(v1,v4),(v2,v4)]网络权矩阵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三、网络最短路求法functiony=fld(n,d)%从d中找到点i到点r之间的最小距离forr=1:nfori=1:nforj=1:np(j)=d(i,j)+d(j,r);end