《数学规划建模》PPT课件.ppt

《《数学规划建模》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数学规划建模》PPT课件.ppt（81页珍藏版）》请在三一办公上搜索。

1、第五章 数学规划方法建模,5.1 引言5.2 单纯形法及其理论基础5.3 线性规划模型 A 奶制品生产销售计划 B 自来水输送计划5.4 0-1线性规划模型 A 混合接力队最优组合 B 选课的策略,5.1 引言,线性规划是数学规划学科中研究得最彻底,同时也是应用最广泛的一个分支.本章简要介绍求解线性规划的单纯形法及0-1线性规划的一种解法,以及这些解法在数学软件Matlab中的实现.我们仍然以若干实际问题的整个数学建模过程为主要线索来展开.,数学规划广泛用于解优化问题,优化问题可以说是人们在科技和经济管理方面最常见的实际问题,而数学规划则是解决优化问题的最基本方法.对优化问题进行数学建模时,先

2、要设定决策变量,通常有多个决策变量,用n维向量x=(x1,xn)T表示;其次要确定被优化的目标函数(x的函数):z=f(x).实际问题一般对决策变量有限制,记为xD,D称为可行域,可行域常用一组不等式(包括等式):gi(x)0,i=1,m 来界定.,数学规划,线性规划的一般形式,一般数学规划模型可以表述为:Min(或Max)z=f(x)s.t.gi(x)0,i=1,m 其中,x=(x1,xn)T,Min(Max)表示求最大(小)值;s.t.表示”满足条件:”.线性规划模型(限于线性情况)表述为:Min(或Max)z=c1x1+cnxn s.t.ai1x1+ainxn(或)bi,i=1,m xj

3、(或)dj,j=1,n 其中,ai,bi,ci,dj为已知常数.,线性规划的标准形式,线性规划的特征是:在满足一组线性约束和变量非负的限制条件下,求多变量线性函数的最小值或最大值.这一特征决定了所有线性规划都可以化为唯一的标准形式:Min z=c1x1+cnxn s.t.ai1x1+ainxn=bi,bi0,i=1,m xj 0(即dj=0),j=1,n因此,可以只限于讨论标准型线性规划的求解.,思考题5-1:分别论证各种形式的线性规划模型都可以化为标准型.,线性规划的可行解与最优解,满足全部约束(包括非负约束)条件的向量x=(x1,xn)T 称为线性规划问题的可行解.所有可行解的集合称为可行

4、域.为了保证可行域非空,一般要求nm.使目标函数达到最优值的可行解称为该线性规划的最优解.或者说,最优值既满足约束条件,并且使目标函数达到最优值.,线性规划的一个简例(游戏机问题),游戏机制造商关心的问题是:为了求得最大利润,下一个周期应该生产两种不同型号的游戏机各多少台?有关背景信息是:每台I型机可得利润6个单位,每台型机可得利润4个单位.而生产一台I型和型游戏机需要原料分别为2个单位和3个单位,需工时分别为4个单位和2个单位.计划可用原料为100个单位,可用工时为120个单位.,游戏机问题的数学模型,令x1,x2分别表示I型和型游戏机的生产台数.不难看到,利润函数为z=6x1+4x2,例润

5、最大的要求就是Max z=6x1+4x2约束条件是2x1+3x2100(原材料单位)4x1+2x2120(工时单位)x1,x20(非负数限制)由此可见,游戏机问题归结为一个线性规划模型.,F,x1,x2,A,E,B,D,10,10,60,50,图 5-1,C,解游戏机数学模型的几何图解法,第步:第一个和第三个约束条件确定三角形区域ABF.第二个和第三个约束条件确定三角形区域AED.因此,可行域为:D=ABFADE=四边形域ABCD.第步:对于0+考虑目标函数的等高线(平行直线族):6x1+4x2=.易见,当200时,直线6x1+4x2=与可性域无交点;而当=200时,则与可性域交点为凸四边形的

6、顶点C,这就证明,目标函数在点C取得最大值,点C的坐标为方程组,2x1+3x2=1004x1+2x2=120的解.不难看出这个方程组的解是:x1=x2=20.所以,下一个周期安排生产两种型号的游戏机各20台,便能获取最大利润为z=6(20)+4(20)=200(单位)注:上述图解法说明,线性规划问题的可性域由凸多边形构成,并且最优解在此多边形的顶点达到.,线性规划可行解的几何性质,定理5.1 任一线性规划的可行域都由一个凸集(凸多面体)D=x|pi1x1+pinxn=hi,hi0,i=1,k;x1,xn0构成;如果线性规划存在最优解,则最优解必在可行域的顶点上达到.证明:略.,5.2 单纯形法

7、及其理论基础,按定理5.1,线性规划最优解只能在一个凸多面体的可行域的顶点上达到.由于顶点数目不超过Cnm个,采用”枚举法”,即通过比较所有顶点处目标函数的值,最终可以找到最优解.但枚举不是好算法.例如,当n=60,m=30时,Cnm大于1017,即使在每秒万亿次浮点运算的超级计算机上也要花上几年才能完成.本节介绍1974年G.M.Dantzig提出的一种非常有效的好算法-单纯形法.,单纯形法中数学模型的矩阵表示,将 Min z=c1x1+cnxns.t.ai1x1+ainxn=bi,i=1,m xj0(即dj=0),j=1,n 中约束等式记为Ax=b,其中,A=(aij),b=(b1,bn)

8、T.为保证可行域非空,一般要求nm;并假设 秩(A)=m(否则,可删去一些多余的约束等式).我们更进一步设系数矩阵A的前m列线性无关.最后得 Min z=c1x1+cnxn Ax=b xj0,j=1,n,单纯形法基本思想,根据线性规划的标准型,直接从可性域中的一个基本可行解(定义在下面给出)开始,每一步都转换到另一个新的基本可行解,并且使目标函数值比上一个严格减少,由于基本可行解(凸多面体的可行域顶点)只有有限个,故经有限步后一定得到最优解.,单纯形法的理论推导,令A=(a1,an),aj为A的第j列(向量).因秩(A)=m,故不失一般性,可设A的前m列线性无关(否则存在置换矩阵P使AP的前m

9、列线性无关),即 A=(B,F),B称为基本解矩阵,令 xB(x1,xm)T,xF(xm+1,xn)T,cB(c1,cm)T,cF(cm+1,cn)T,则式可写成 Min z=cBTxB+cFTxF s.t.BxB+FxF=b xB0,xF0,对增广矩阵(A b)=(B F b)进行初等变换,使B化为m阶单位矩阵E:(B F b)(E B-1F B-1b)令b=B-1b,G=B-1F(gij)m(n-m),L=cFT-cBTG(l1,ln-m),则式可等价表示为 Min z=cBTxB+cFTxF s.t.BxB+FxF=b xB0,xF0上述模型中,若令xF=0,则得到xB=B-1b=b,z

10、=cBTB-1b若b0,则x为可行解,称为基本可行解.,又若 L0,则 LxF0,z=cBTB-1b+LxF,Min z=z即为最优解,且在xB=b,xF=0处达到.若存在某1in-m,使li10.为了得到最优解,现在要做的是:在A的后n-m列中取出第j列与A的前m列中某第k列互换,构成新的基本解矩阵B,j,k的确定方法如下:,j满足 minli|li0=bk/gkj 下面说明按上述方式确定k,j后可取一组解x使新的目标函数z值小于z.事实上,取xj=Q,其它xi=0,n-min,ij,于是xk=bk-gkj xj=bk-gkjQ=0.而A的第k列与第j列互换后得到的新基本解矩阵B=(a1,a

11、k-1,aj,ak+1,am)T,由初等矩阵变换性质不难看出:新的基本解矩阵对应的目标函数值比上一步的目标函数值严格减小.上述过程可重复进行,直到某步L0时为止.,单纯形法算法的步骤,对矩阵A作初等变换得到一个基本解矩阵B,无妨设A=(B,F).计算b=B-1b,G=B-1F,L=cFT-cBTG 若 L0,取xB=b,xF=0得最优解,最优值 Min z=cETb,停止.否则,有1i1n-m,使li10,则无最优解;否则,存在某些gii10,取 minli|li0=bk/gkj 令矩阵A中F的第j列与B的第k列互换构成新基本矩阵B,然后回到第步再循环.,单纯形法是很有效的迭代算法,在单纯形算

12、法迭代中,每一步从当前的一个基本可行解出发,或判定它是最优解,或找到一个有更小目标函数值的下一个基本可行解,这个解一定与前面找到过的基本可行解都不同.由于基本可行解只有有限个,故单纯形算法最终将找到最优解而圆满结束.事实证明:即使对很大的m,单纯形算法都能相当快地结束,它是迄今发现的非常有效的算法之一.,单纯形法算法举例,为了说明上述算法,让我们用此算法解例1.例1 求解下列线性规划问题:Max z=2x1+5x2 s.t.x1 4 x23 x1+2x28 x1,x20解 引进松弛变量将它化为等价的标准型:,Min z=-2x1-5x2+0 x3+0 x4+0 x51+x3=4 x2+x4=3

13、 x1+2x2+x5=8 x1,x5 0系数矩阵A的1,2,4列构成可逆矩阵B=(a1,a2,a4),则 cBT=(-2,-5,0),cFT=(0,0).用行初等变换将增广矩阵(Ab)中的1,2,4列化成单位矩阵,于是有b=(4,2,1)T0,G=B-1F=L=cFT-cBTG=(-1/2,5/2).因L的第j=1元为负,故对应的基本可行解x=(4,2,0,1,0)T不是最优解.Q=minibi/gij|gij0=2=b3/g3j,k=3以F第1列对换B第3列,则B=(a1,a2,a3),将增广矩阵中的1,2,3列变换成单位矩阵:,这一次得 G=L=(0,0)-(-2,-5,0)G=(1,2)

14、.因L没有负元,故所得基本可行解x=(2,3,2,0,0)T是最优解.去掉松弛变量的值,即得原问题的最优解为:x1=2,x2=3;最小目标函数值为:z=2x1+5x2=-2(2)-5(3)=-19.,单纯形法的软件实现,求解线性规划有不少现成的软件,例如,Matlab 和 Lindo 等.这些软件甚至不同程度地放宽了标准型的要求.例如,不要求全为等式约束,等等.下面介绍用 Matlab 软件的函数linprog(f,A,b,Aeq,beq)求解线性规划的操作方法.,函数linprog(f,A,b,Aeq,beq)使用范围,函数linprog(f,A,b,Aeq,beq)用来求解更一般的线性规划

15、(比标准型条件宽):Min z=cTx s.t.Axb,Aeqx=beqx其中,约束条件除若干不等式Axb外,还有若干等式Aeqx=beq,A,b;Aeq,beq分别代表二者的系数矩阵及右端向量.若置Aeqx=,beq=,则等式全缺省,函数linprog(f,A,b,Aeq,beq)使用方法,首先,(必要的话)改变z中所有系数的符号把”Max”化为”Min”;把”化为”.其次,输入具体的 c,A,b,Aeq,beq.最后执行行命令:x z=linprog(f,A,b,Aeq,beq)则输出的向量x即为最优解;数z(或-z)即为目标函数最小(大)值.,用函数linprog求解例1,归结为执行下列

16、三条行命令:f=-2 5;A=1 0;0 1;1 2;b=4 3 8;Aeq=;beq=;x z=linprog(f,A,b,Aeq,beq)(注意每次检查输入数据)屏幕最后显示:x=2.0000e+000(x1=2)3.0000e+000(x2=3)z=-1.9000e+001(最大值为19)这个举手之劳的结果与前面费了九牛二虎力气才算出来的结果完一样.(“取负值化Max为Min,最优再取负),例2 用linprog求解下列线性规划,Min z=-24x1-16x2-44x3-32x4+3x5+3x61+3x2+4x5+3x6600 4x1+2x2+6x5+4x6480 x1+x5100 x

17、3-0.8x5=0 x4-0.75x6=0 x1,x60,解:归结为执行下列几条行命令:f=-24-16-44-32 3 3;A=4 3 0 0 4 3;4 2 0 0 6 4;1 0 0 0 1 0 b=600 480 100;Aeq=0 0 1 0-0.8 0;0 0 0 1 0-0.75;beq=0 0;x z=linprog(f,A,b,Aeq,beq)由屏幕最后显示结果得:最优解 x=(0,168,19.2,0,24,0)T 最大值 z=3460.8,5.3 线性规划模型,本节通过若干个实际的优化问题,说明如何建立这类问题的线性规划数学模型,并用Matlab求出最优解及对应的目标函数

18、最优值,同时对结果作一些分析.,优化问题经常面临的问题,在经济管理领域,特别是制定生产计划的最优化决策方面,线性规划十分有用.企业在制定生产计划时主要面临两方面的考虑.首先,要根据外部需求和内部设备,人力,原料供应等条件,追求最大利润;其次,要根据生产计划,工艺流程,资源约束及费用参数等,追求最小成本.我们在数学建模时,一定要注意满足外部需求和内部能力条件,追求利润最大和成本最小等几个方面.,A 奶制品生产销售计划问题,某奶制品厂以牛奶为原料生产两种奶制品A1,A2,1桶牛奶用12小时可以在设备甲 上加工成3公斤A1,或者在设备乙上加工成4公斤A2.根据市场需求生产的A1,A2全部能售出,且每

19、公斤A1获利24元,每公斤A2获利16元.该厂每天能得到50桶牛奶供应,每天工人总的劳动时间为80小时,并且设备甲每天至多能加工100公斤A1,设备乙的加工能力没有限制.制定生产计划使每天获利最大.,与此同时,该厂为增加效益,开发了奶制品深加工技术:用2小时和3元加工费可将1公斤A1加工成0.8公斤高级奶制品B1,也可将1公斤A2加工成0.75公斤高级奶制品B2.每公斤B1能获利44元,每公斤B2能获利32元.试为四种产品制定新的生产与销售计划使每天获利最大.,奶制品生产计划问题建模,决策变量:设每天用x1捅牛奶生产A1,用x2捅牛奶生产A2.目标函数:设每天获利z元.x1捅牛奶生产3x1公斤

20、A1,获利72x1元,x2捅牛奶生产4x2公斤A2,获利64x2元,故z=72x1+64x2.原料约束:每天生产所用牛奶不得超过供应量50公斤:x1+x250.工时约束:每天生产所用工时不得超过480小时:12x1+8x2480.设备甲能力约束:3x1100.,非负约束:x1,x2不能为负值 x1,x2 0.综上所述,问题的数学模型是下列线性规划:Max z=72x1+64x21+x250 3x1100 12x1+8x2480 x1,x2 0用Matlab求得(思考题5-2)最优解为:x=(20,30)(20桶奶生产A1,30桶奶生产A2);目标最优值为:z=3360,思考题5-2:用Matl

21、ab求解奶制品生产计划问题的线性规划模型.,奶制品产销计划问题建模,决策变量:设每天销售x1公斤A1,x2公斤A2,x3公斤B1,x4公斤B2,并用x5公斤A1加工B1,x6公斤A2加工,B2.目标函数:设每天获利z元,易见z=24x1+16x2+44x3+32x4-3x5-3x6.原料约束:每天生产x1+x5公斤A1用奶(x1+x5)/3桶;生产x2+x6公斤A2用奶(x2+x6)/4桶,故应满足约束条件(x1+x5)/3+(x2+x6)/4 50.或等价地4x1+3x2+4x3+3x4600.工时约束:共480小时,生产1公斤A1,A2分别需4,2小时,故 4(x1+x5)+2(x2+x6

22、)480.,设备甲能力约束:x1+x5100.附加约束:因1公斤A1(A2)加工成0.8(0.7)公斤B1(B2),故 x3=0.8x5,x4=0.75x6.非负约束:x1,x6 0.所以数学模型是 Max z=24x1+16x2+44x3+32x4-3x5-3x61+3x2+4x5+3x6600 4x1+2x2+6x5+4x6480 x1+x5100 x3-0.8x5=0 x4-0.75x6=0 x1,x6 0,奶制品产销计划问题求解,解:改目标函数为 Min z=-24x1-16x2-44x3-32x4+3x5+3x6则本数学模型等价于上节末例2中的线性规划问题.在那里我们已用数学软件求得

23、它的解是:x=(0,168,19.2,0,24,0)T,z=3460.8对应答案是:每天生产销售168公斤A2和19.2公斤B1(不出售A1,B2);可获利3460.8元.为此,需用牛奶8桶加工成A1;42(=168/4)桶加工成A2;并将得到的24桶A1全部加工成B1.,B 自来水输送计划的优化问题,背景:某市有甲,乙,丙,丁四个区,自来水由三个水库供应,四个区必须得到保证的基本生活用水量分别为30,70,10,10千吨.但由于水源紧张,三个水库每天最多只能分别供应50,60,50千吨自来水.自来水公司从各水库向各区送水,按地理位置不同分别付出的引水管理费如下:,其中,C水库与丁区之间没有输

24、水管道.其他管理费用都是450元/千吨.公司统一按900元/千吨标准收水费.此外四个区都向公司申请额外用水量分别为每天50,70,20,40千吨.问题:该公司应如何分配供水量,才能获利最大.与此同时,该公司为了增加供水量正在考虑进行水库改造,使三个水库每天的最大供水量都提高一倍.问题:届时供水方案应如何改变?并可增加利润多少?,自来水输送优化问题建模,分析:分配供水量指安排从三个水库送水的方案,目标是获利最多.从问题给出的条件看,三个水库总供水量160千吨小于总需求量300千吨,故每天的水总能全部卖出并获利,于是公司每天总收入是900(50+60+50)=144000元,与送水方案无关.同样,

25、公司其它管理费用450(50+60+50)=72000元也与送水方案无关.所以,要使利润最大,只需使引水管理费用最小即可.当然,送水方案要受水库供应量和四个区的需求量的限制.,决策变量:共11个,它们是A,B,C三个水库(i=1,2,3)分别向甲,乙,丙,丁四个区(j=1,2,3,4)的日供水量xij,i=1,2,3;j=1,2,3,4,不考虑x34(因C水库与丁区之间无输水管道).问题的目标函数从获利最多转化为引水管理费用最少,于是决策目标为Min z=160 x11+130 x12+220 x13+170 x14+140 x21+130 x22+190 x23+150 x24+190 x3

26、1+200 x32+230 x33约束条件:考虑到各区的基本生活用水与额外用水,需求水量限制为,30 x11+x21+x3180,70 x12+x22+x32140,10 x13+x23+x3330,10 x14+x2450 标准化为 x11+x21+x3180,-x11-x21-x31-30,x12+x22+x32140,-x12-x22-x32-70,x13+x23+x3330,-x13-x23-x33-10,x14+x2450,-x14-x24-10 因供大于求,水能全部卖出,故供水为等式约束 x11+x12+x13+x14=50,x21+x22+x23+x24=60,x31+x32+x

27、33=50 所以,数学模型是在非负约束及约束-下求目标函数最小值的线性规划.,自来水输送优化问题求解,解:依次执行下列Matlab行命令:f=160 130 220 170 140 130 190 150 190 220 230;A=1 0 0 0 1 0 0 0 1 0 0;-1 0 0 0-1 0 0 0-1 0 0;0 1 0 0 0 1 0 0 0 1 0;0-1 0 0 0-1 0 0 0-1 0;0 0 1 0 0 0 1 0 0 0 1;0 0-1 0 0 0-1 0 0 0-1;0 0 0 1 0 0 0 1 0 0 0;0 0 0-1 0 0 0-1 0 0 0;b=80-3

28、0 140-70 30-10 50-10;Aeq=1 1 1 1 0 0 0 0 0 0 0;0 0 0 0 1 1 1 1 0 0 0;0 0 0 0 0 0 0 0 1 1 1;,beq=50 60 50;x z=linprog(f,A,b,Aeq,beq)则由屏幕最后显示结果得:最优解x12=50,x22=50,x24=10,x31=40,x33=1其余xij全为0.目标函数最小值 z=24400.最优送水方案是:每天A水库向乙区供水50千吨;B水库向乙,丁区分别供水50,10千吨;C水库向甲,丙区分别供水40,10千吨.最小引水管理费24400元,其它管理费用72000元,公司每日最大

29、利润为 144000-72000-24400=47600元.,自来水输送优化问题建模,分析:如果三个水库每天的供水量都翻了一翻,则公司总供水能力为320千吨,大于总需求量300千吨,不会全部卖出,故需要计算三个水库分别向四个区供应每千吨水的利润,即从收入900元中减去其它管理费450元,再减去相应的引水管理费得下面各水库向各区送水的净利润表:,决策变量仍为上面的11个x12,x33,决策目标改为Max z=290 x11+320 x12+230 x13+280 x14+310 x21+320 x22+260 x23+300 x24+260 x31+250 x32+220 x33由于供水量不能全

30、卖出,应将约束条件-右端增大一倍并改=为:x11+x12+x13+x14100,x21+x22+x23+x24120,x31+x32+x33100 另外,由于每区供水量都能满足,应将约束条件-改为,x11+x21+x31=80,x12+x22+x32=140,x13+x23+x33=30.x14+x24=50,所以,本问题数学模型是在非负约束及约束-下,求目标函数最大值的线性规划.,自来水输送优化问题求解,解:依次执行下列Matlab行命令:f=290 320 230 280 310 320 260 300 260 250 220 A=1 1 1 1 0 0 0 0 0 0 0;0 0 0 0

31、 1 1 1 1 0 0 0;0 0 0 0 0 0 0 0 1 1 1;b=100 120 100;Aeq=1 0 0 0 1 0 0 0 1 0 0;0 1 0 0 0 1 0 0 0 1 0;0 0 1 0 0 0 1 0 0 0 1;0 0 0 1 0 0 0 1 0 0 0 beq=80 140 30 50;x z=linprog(f,A,b,Aeq,beq),则由屏幕最后显示结果得:最优解x12=100,x21=30,x22=40,x24=50,x31=50,x33=30,其余xij全为0.目标函数最大值 z=88700最优送水方案是:每天A水库向乙区供水100千吨;B水库向甲,乙

32、,丁区分别供水30,40,50千吨;C水库向甲,丙区分别供水50,30千吨.三个水库每日总利润最大值为88700元.,运输问题,上面考虑的问题属于所谓运输问题的范畴,即将物资从若干供应点运往一些需求点,在供需约束条件下,使总运输费用最小或总利润最大.标准平衡运输问题的数学模型是:Min z=j=1ni=1mcijxij s.t.j=1nxij=ai,i=1,m i=1mxij=bj,j=1,n xij0,i=1,m,j=1,n其中,xij,cij分别是从供应点i到需求点j的运量及运费单价,ai(bj)是供应点i(需求点j)的供应(需求)量,约束条件是供需平衡等式.,思考题5-3:今有某物资从三

33、个供应点A,B,C调往四个需求点甲,乙,丙,丁.A,B,C的供应量分别是7,4,9;甲,乙,丙,丁的需求量分别是3,6,5,6,运费单价如下表所示.问怎样调运才使总运费最低?,5.4 0-1线性规划模型,在实际优化问题中存在一类所谓的分派问题,其含义如下:有若干项任务,每项任务必须有一人且只能有一人承担,每人也只能承担其中一项,不同人员承担不同任务的收益(或成本)不同.优化目标是:怎样分派各项任务使总收益最大(或总成本最小).本节通过若干个实际的分派问题,说明如何建立这类优化问题的数学模型,并用Matlab求出最优解及对应的目标函数最优值,同时对结果作一些分析.,A 混合接力队的最优组合问题,

34、问题:某学院准备从5名游泳队员中选择4 人组成学院的接力队,参加校运动会的4 100混合泳接力赛.5名队员b1,b5的4种 泳姿(蝶,仰,蛙,自由)a1,a4的百米平 均成绩cij,i=1,5;j=1,4如下表所示.应如何选择4人组成最优的接力队?,问题分析,要求从5名队员选择4人,每人一种泳姿且4人泳姿各不相同,使接力队成绩最好.容易想到的办法是穷举法,组成接力队的方案共5!=120种,逐一计算并作比较即可找出最优方案.显然,这不是解决这类问题的有效办法,随着问题规模变大,穷举法的计算量将是无法接受的.一个好的办法是:用0-1变量表示一个队员是否入选接力队,从而建立这个问题的0-1规划模型,

35、再借助数学软件求解.,建立0-1线性规划模型,引入0-1变量xij,若队员bj参加泳姿ai的比赛,记xij=1,否则记xij=0.根据组成接力队的要求,应满足两个约束条件:每人至多入选4种泳姿之一,应有 j=14xij1,i=1,5 每种泳姿必须有一人入选i=15xij=1,j=1,4当队员bj入选泳姿ai时,其成绩为cijxij,于是接力队的成绩可表为z=j=14i=15cijxij,这就是问题的目标函数.,所以,混合接力队的最优组合问题的数学 模型是下列0-1线性规划问题:Min z=j=14i=15cijxij s.t.j=14xij1,i=1,5 i=15xij=1,j=1,4 xij

36、0,1,i=1,5,j=1,4这类线性规划问题的特点是决策变量只取值1或0,故称为0-1线性规划问题.Matlab的函数bintprog专门用来求解0-1线性规划,下面介绍此函数的使用范围及使用方法,其理论基础从略.,函数bintprog(f,A,b,Aeq,beq)使用范围,函数linprog(f,A,b,Aeq,beq)用来求解一般的标准型0-1线性规划:Min z=cTx s.t.Axb,Aeqx=beq x=0或1 其中,约束条件除若干不等式Axb外,还有若干等式Aeqx=beq,A,b;Aeq,beq分别代表二者的系数矩阵及右端向量.若置A=,b=,则不等式全缺省;若置 Aeq=,b

37、eq=,则等式全缺省.,函数linprog(f,A,b,Aeq,beq)使用方法,首先,(必要的话)改变z中所有系数的符号把”Max z”化为”Min z”;把”化为”.其次,输入具体的f(=c),A,b,Aeq,beq.最后执行行命令:x z=bintprog(f,A,b,Aeq,beq)则输出的x即为最优解;z(或-z)即为目标函数最小(大)值.,混合接力队优化组合问题求解,解:执行下列Matlab行命令:f=66.8 75.6 87 58.6 57.2 66 66.4 53 78 67.8 84.6 59.4 70 74.2 69.6 57.2 67.4 71 83.8 62.4;A=1

38、 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0;0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1b=1 1 1 1 1;beq=1 1 1 1;Aeq=1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0;0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0

39、1 0 0;,0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0;0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1;x z=bintprog(f,A,b,Aeq,beq)由屏幕最后显示结果得:最优解 x14=x21=x32=x43=1,其它xij=0 目标函数最小值 z=253.2=4132即应该选派b1,b2,b3,b4四人组成接力队参加混合泳接力比赛,并分别游自由泳,蝶泳,仰泳,和蛙泳.他们的预期成绩(是一切可能组合中最好成绩)为:4分13秒2.,思考题5-4:在校运会报名时,发现队员b4的蛙泳成绩有较大退步,只有1152;而队员b

40、5训练努力自由泳有明显进步,达到575.问组成接力队的方案应作如何调整?,B 选课策略问题,问题:某大学规定,运筹学专业学生毕业时必须至少修过2门数学课,3门运筹学课和2门计算机课.这些课的编号及信息如下表所示.给出毕业时选课门数最少的一个方案.给出毕业时选课门数少而学分多的一个方案.,选课策略问题的数学模型,用xi=1(0)表示选修(不选)按上表中编号顺序的9门课程的第i门课.问题决策目标为选修课程门数最少,即 Min z=j=19xi.其约束条件包括首先,每人最少要选2门数学课,3门运筹学课和2门计算机课,按表中课程类别划分可将此约束表示为 x1+x2+x3+x4+x52 x3+x5+x6

41、+x8+x93 x4+x6+x7+x92,其次,某些课有先修课的要求,例如,数据结构的先修课是计算机编程,这意味着x4=1蕴涵x7=1,这个条件可表示为x4x7或 x4-x70.同理,最优化方法的先修课是微积分和线性代数的条件可表示为x3x1,x3x2,此二式可合并为一个不等式 2x3-x1-x20.另外有 2x5-x1-x20 x6-x70 x8-x5 0 2x9-x1-x20,所以,选课策略问题的数学模型就是:只取值0或1的9个决策变量x1,x9,满足约束条件-,并使目标函数取最小值的0-1线性规划模型.,选课策略问题数学模型求解,首先,把约束条件-标准化为-x1-x2-x3-x4-x5-

42、2-x3-x5-x6-x8-x9-3-x4-x6-x7-x9-2 其次,输入数据 A=-1-1-1-1-1 0 0 0 0;0 0-1 0-1-1 0-1-1;0 0 0-1 0-1-1 0-1;-1-1 2 0 0 0 0 0 0;0 0 0 1 0 0-1 0 0;-1-1 0 0 2 0 0 0 0;0 0 0 0 0 1-1 0 0;0 0 0 0-1 0 0 1 0;-1-1 0 0 0 0 0 0 2;b=-2-3-2 0 0 0 0 0 0,Aeq=;beq=;f=1 1 1 1 1 1 1 1 1;,核对输入数据正确之后,键入下列行命令:x z=bintprog(f,A,b,A

43、eq,beq)由屏幕最后显示结果得:最优解 x1=x2=x5=x6=x7=x8=1,x3=x4=x9=0 目标函数最小值 z=6即应该选修微积分,线性代数,应用统计,计算机模拟,计算机编程,预测理论等6门课,最小选课门数是6.,思考题5-5:在选课策略问题中,如果一个学生因对最优化方法特有兴趣而把此课定为必选,仍然希望毕业时所学课程门数尽可能少,试给出他(她)的一个选课方案.,关于解的唯一性,一般来说,线性规划问题,包括0-1线性规划问题的解都不是唯一的,例如对选课策略问题,我们先求出一个最优解x=1,1,0,0,1,1,1,1,0;后又在思考题5-5中求得另外一个最优解 x=1,1,1,0,

44、0 1,1,0,1,它们对应的最优目标函数值相等(=6).说明对应选课策略问题的0-1线性规划至少有两个的解,说明它的解不唯一.,我们可以证明 此问题恰有两个解.证:如果我们再把x4=1作为约束条件(表示为-x4-1),求得最优解x=1,1,1,1,1 1,1,0,0,但对应最优目标值已不是6,而是7.说明,此解与上面二解不同,不是选课策略问题的最优解.再注意观察:上面两个最优解恰有一个分量,第4分量,同时为0,由此可见(没有第4分量为1的最优解),选课策略问题只有上述两个解.,思考题5-6:在选课策略问题中如果一个学生在满足学校有关选课规定条件下,希望毕业时所学课程获得的学分数尽可能多,试给

45、出他(她)的一个选课方案.,选课策略问题的数学模型,选课策略问题的数学模型与选课策略问题的数学模型的约束条件完全一样;只是目标函数不同.要求”选课门数少而学分多”意味着同时要求两个决策目标:Min z=j=19xi Max w=5x1+4x2+4x3+3x4+4x5+3x6+2x7+2x8+3x9具有多个决策目标的规划称为多目标规划,前面讲的只有一个目标的规划称为单目标规划.所以,选课策略问题的数学模型是满足约束条件-并有双目标 Min z和 Max w 的0-1线性规划.,双目标规划的一种处理方法,把双目标归结为一个单目标,即令y=z+(1-)w,为闭区间0,1中任一数,并取决策目标为(Ma

46、x w=Min(-w)Min y=z-(1-)w值的大小体现决策者对每个目标的重视程度,例如,某同学觉得学分数和课程数是三七开,故把取为0.7,决策目标为 Min=-0.1(8x1+5x2+5x3+2x4+5x5+2x6-x7-x8+2x9),用Matlab函数bintprog求解这个问题时,与前面求解选课策略问题时的 A,b,Aeq,beq数据完全一样,只需把f改为f=-0.18 5 5 2 5 2-1-1 2;后,再执行行命令bintprog=(f,A,b,Aeq,beq)即可得出 最优解 x=1 1 1 1 1 1 1 0 1,目标函数最小值 z=-2.8.即选修除预测理论外的8门课,共计28学分.,思考题5-7:在选课策略问题中如果一个学生觉得学分数和课程数是二五和七五开,试给出他(她)的一个最优选课方案.,