运筹学_张伯生_案例

《运筹学_张伯生_案例》由会员分享，可在线阅读，更多相关《运筹学_张伯生_案例（69页珍藏版）》请在装配图网上搜索。

1、上海市教委重点课程建设运筹学案例集与Matlab求解上海工程技术大学管理学院运筹学课题组2007年12月目 录 1案例分析与Matlab求解31.1案例分析一与Matlab求解31.2案例分析二与Matlab求解91.3案例分析三与Matlab求解91.4案例分析四与Matlab求解122案例分析与Matlab求解142.1 案例分析一与Matlab求解142.2 案例分析二与Matlab求解172.3 案例分析三与Matlab求解173案例分析与Matlab求解203.1 案例分析一与Matlab求解203.2 案例分析二与Matlab求解233.3 案例分析三与Matlab求解294案例分

2、析与Matlab求解334.1 案例分析334.2 Matlab求解345案例分析与Matlab求解355.1 案例分析一与Matlab求解355.2 案例分析二与Matlab求解406 案例分析与Matlab求解446.1 中国石油天然气集团公司天然气的运送案例分析446.2 中国石油天然气集团公司天然气的运送Matlab求解457 案例分析与Matlab求解477.1 案例分析一与Matlab求解477.2 案例分析二与Matlab求解517.3 案例分析三与Matlab求解548 案例分析与Matlab求解608.1 案例分析608.2 MATLAB求解628.3 MATLAB运行分析6

3、49 案例分析与Matlab求解659.1 案例分析659.2 MATLAB求解669.3 MATLAB运行分析6810 案例分析与Matlab求解6910.1 案例分析6910.2 序列决策例题MATLAB求解721案例分析与Matlab求解1.1案例分析一与Matlab求解1.1.1 案例分析用线性规划测算上海市最低生活标准（以2005年以前数据计算）。建立统一、规范和完善的社会保障体系，是治国安邦的根本大计，也是一项社会主义的基本制度建设。上海市最低生活保障制度从1993年实施以来，已经将近有十几个年头了。在这十几年里，上海的经济文化水平发生了巨大的变化，上海的社会保障体系也在不断地调整

4、和完善。目前，最低生活保障标准已经从1993年的120元增长到了2002年的290元。 最低生活保障制度的概念目前，最低生活保障制度是指世界上绝大多数市场经济国家普遍实行的以保障全体公民基本生存权利为目标的社会救助制度。它的通常做法是，根据维持最起码的生活需求的标准，设立一条最低生活保障线。每一个公民当其收入水平低于最低生活保障线而生活发生困难时，有权利依据国家公布的法定标准和程序获得政府提供的现金和实物救助。 上海建立最低生活保障制度的演进上海于1993年6月1日正式执行上海市城镇最低生活保障制度。1993-2002年最低保障标准及增长率见表1-11。表1-11 最低保障标准历年变化表年份1

5、993199419951996199719981999200020012002最低保障标准120145165185195205280280280290增长率%0.0020.8313.7912.125.415.1336.590.000.003.57 保障对象的范围城市居民最低生活保障制度的保障对象是家庭人均收入低于当地最低生活保障标准的持有非农业户口的城市居民，主要包括以下三类人员：1无生活来源、无劳动能力、无法定赡养人或抚养人的居民；2领取失业救济金期间或失业救济期满仍未能重新就业，家庭人均收入低于最低生活保障标准的居民；3在职人员和下岗人员在领取工资或最低工资、基本生活费后以及退休人员领取退

6、休金后，其家庭人均收入仍低于最低生活保障标准的居民。 保障标准城市居民最低生活保障标准由当地人民政府自行确定。本着既保障基本生活、又有利于克服依赖思想的原则，按照当地基本生活必需品费用和财政承受能力，实事求是地确定保障标准。 最低生活保障标准的测算指标：国际上把最低生活保障线也称为贫困线，是指为度量贫困而制定的针对最起码的生存条件或者相对社会中等生活水平的差距所作的定量化的界定。所以，想要测定最低生活保障线就必须对贫困及贫困线有大体的认识。常用的测定贫困线的方法有：比例法、绝对值法、恩格尔系数法、数学模型法、基本需求法、基期固定法等。 最低生活保障标准中食品部分消费支出的测定 建立目标函数目标

7、函数为每日食品总支出最少 Min Z=CiXi其中，Z表示每人每天食品支出总额。Ci表示第i种食品的市场单价，Xi表示各种食品。约束条件1：每天的营养一定要达到标准Kj。即每天各种食品的消耗量Xi*各种食品每公斤某种营养元素含量Aij*各种食品的可食部分百分比fi相累加，累加的总和要大于或等于这种营养每日需要量。食品的可食部分百分比是指：食品中除去骨头、外壳、内脏等以后剩余的可以食用的重量占食品总重量的比重。即每天的热能、钙、铁等营养素摄入量必须达到一定的标准。用公式可以表示为：AijXifi=Kj（Aij：第i种食品中第j种营养素的含量，Kj：第i种营养素每日需要量标准，fi：第i种食品可食

8、部分比例）。约束条件2：蛋白质、脂肪、碳水化合物占总热量的比重要符合一定的比例。三种营养在体内转化为热能的系数分别为：每克蛋白质4kcal,脂肪9kcal，碳水化合物4kcal。设每种食品蛋白质含量Dia，每种食品脂肪含量Dib，每种食品碳水化合物含量Dic。每日蛋白质总摄入量（DiaXifi）*热能转化系数（4kcal/kg）/每日热能总摄入量（Ai1Xifi）即为每日摄入的蛋白质占热能中的比例。脂肪与碳水化合物的计算也与蛋白质一样。用公式表示为：10%=(4*DiaXifi)/ Ai1Xifi=15%20%=(9*DibXifi)/ Ai1Xifi=25%60%=(4*DicXifi)/

9、Ai1Xifi=70%约束条件3：每日的饮食习惯。ai=Xi0t=i;if max(a1(:,t)=0disp(此问题无界);break;elsedisp(此问题有界);endendendm4%m4.m判断最优解g=q(:,1);for i=1:m+nqq=q(:,i)if g=qqg=qq;z=i;endendif g0if hctth=ct(j,:);y=j+n;endendenddisp(换出变量为);ym7%m7.m 迭代产生新的得到新的单纯形表if yncb(:,y-n)=a1(:,z);endif ync(:,y-n)=f1(:,z);endif ync(:,y)=f1(:,z);

10、 endb=inv(b2)*b;b=b;disp(新的约束矩阵为);a1cb=eye(m,m);m8%m8.m文件形成新常数矩阵和可行解if yn yy=y-n; ee(:,yy)=z; for i=1:m k=ee(:,i); mm(:,k)=b(:,i);end mm(:,y)=0; endendmmm21.2案例分析二与Matlab求解1.2.1 案例分析例1.9 对于例1.1, 此问题的模型建立如下：1.2.2 Matlab求解对于此简单问题，用以上开发出来的程序计算如下：命令：m1 并输入矩阵条件。 m1 请输入变量个数: 2请输入约束条件个数: 3请输入目标函数系数矩阵：4,3请输

11、入约束条件系数矩阵：1,0;0,2;2,3请输入约束条件右端常数矩阵：6,8,8按回车后计算机自动执行程序，结果如下：目标函数已得到最优值 16最优解为:mm = 4 0 2 8 01.3案例分析三与Matlab求解1.3.1 案例分析例1.10 飞乐公司经营一个回收中心，专门从事用三种废弃原材料C、P、H混合调出三种不同规格的产品ABD。根据混合时候各种材料的比例，可将该产品分为不同的等级（参照表1.12）。尽管在混合各种等级产品时允许一定的机动性，但每一等级产品中各种材料的最大值和最小值必须符合下面质量标准的规定（最大值和最小值是根据该材料的重量在该等级产品总重量中的比例来确定的）。在两种

12、较高等级的产品中，有一种特定材料的比例是固定的。已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价，分别见表1.12和表1.13，问该厂应如何安排生产，使利润收入为最大？表1.12产品名称规格要求单价（元kg）原材料C不少于原材料不多于50B原材料C不少于原材料P不多于35D不限25回收中心可以从一些渠道定期收集到所需的固体废弃物，因此，可以获得维持稳定作业的处理量。表1.13给出了中心每天可以收集到每种材料的数量和原材料单价。表1.13原材料名称每天最多供应量（kg）单价（元kg）CPH10010060652535飞乐公司是绿地组织的全资公司，绿地组织是一个专门从事与环境有关业

13、务的组织。管理层决定在表1.12和表1.13所列的约束之内，有效地将各种材料分配到各等级的产品中去，以实现每周的总利润最大。以线性规划的形式建模这是一个混合线性规划问题，为了给该问题建模，首先需要明确该问题所涉及的活动(activities)、资源(resources)、收益(benefits)以及确定的需求(fixed requirements)。这一步的关键在于管理层的目标是将每种材料最优地分配给每一等级的产品。每一种材料与产品的组合都是一个决策：多少材料用于这一等级的产品？这个数量就是活动的水平(level of an activity)。每一种活动对应的是将一种固体废弃物处理混合入每一

14、个等级的产品中去活动的水平是混合入每一等级产品中的一种材料的数量因此，要决策的是每周将多少元的每一种材料加入每一等级的产品中去。因为资源有限，收益受到限制，以及确定的需求，该问题就有了相当多的约束，归纳如下：有限的资源：3种固体废弃物所能获得的数量如表1.13的第二栏所示，此外，表1.12的第二栏还表明材料A和B的用量是有限的，这些有限的资源都将形成资源的约束条件。规定的收益：收益是指所收集和处理的每一种材料。确定需求的约束：1 表 1.12第二栏所示的材料A的原材料C不少于原材料不多于，2 表 1.12第二栏所示的材料B的原材料C不少于原材料P不多于 管理层的目标是使的三种等级的产品所能实现

15、的每天总利润最大，因此，这就是该问题的总绩效测度（overall measure of performance）。1.3.2 Matlab求解如以Ac, Ap分别表示中C的成分，A中的成分，依次类推。根据表1.12有：AC 0.5A, AP 0.25A, BC 0.25B, BP 0.5B (1.1)又有 ：AC + AP +AH=A， BC + BP + BH =B (4.2)将(1.1)逐个代入(4.2)中并整理得：-0.5AC + 0.5 AP + 0.5 AH 0-0.5AC + 0.75 AP - 0.5 AH 0-0.75BC + 0.25 BP + 0.25 BH 0-0.5BC

16、 + 0.5 BP - 0.5 BH 0表1.13表明这些原材料供应量的限额。加入到产品A、B、D的原材料C总量每天不超过100kg，P的总量不超过100kg,H总量不超过60kg,由此：AC + BC + DC100AP + BP + DP100AH + BH + DH60在约束条件中共有9个变量，为计算和叙述的方便，分别用表示令：由此约束条件可表示为：我们的目的是使利润最大化，即产品价格减去原材料的价格为最大。产品价格为：原材料价格：整理后目标函数为：面对如此多变量和约束条件的线性规划问题，如果用手算，那是件很麻烦的事，不仅需要很多时间和耐心，而且容易出错。现在利用计算机程序来计算显得小菜

17、一碟。 首先需要输入矩阵： m1请输入约束条件个数: 7请输入变量个数: 9请输入目标函数系数矩阵：-15,25,15,-30,10,0,-40,0,10请输入约束条件系数矩阵：-1/2,1/2,1/2,0,0,0,0,0,0;-1/4,3/4,-1/4,0,0,0,0,0,0;0,0,0,-3/4,1/4,1/4,0,0,0;0,0,0,-1/2,1/2,-1/2,0,0,0;1,0,0,0,4,0,0,1,0;0,1,0,0,1,0,0,1,0;0,0,1,0,0,1,0,0,1请输入约束条件右端常数矩阵：0,0,0,0,100,100,60按下回车，计算机以迅雷不及掩耳之势就显示了结果。

18、结果如下 ：目标函数已得到最优值 3400最优解为:mm =0 100 60 0 0 0 0 0 0 -80 -60 0 0 100 0 0可以得到，当=100, =60是，最优解是3400。1.4案例分析四与Matlab求解1.4.1 案例分析例1.11 上海地铁公司正准备增加其人民广场的往来班次，因此需要雇用更多的工作人员，但是不知道到底雇用多少数量的工作人员。管理层意识到中介公司的客户提供令人满意的服务水平的同时必须进行成本控制，因此，必须寻找成本与收益之间合意的平衡。于是，要求管理团队研究如何规划人员才能以最小的成本提供令人满意的服务。分析研究新的班次时间表，以确定一天之中不同时段为实

19、现客户满意水平必须工作的工作人员数目。在表1.14的最后一栏显示了这些数目，其中第一列给出对应的时段。表中的其他数据反应了公司与客户服务代理商协会所定协议上的一些规定，这一规定要求每一工作人员工作8小时为一班，各班的时间安排如下：轮班 1： 6:00 AM2:00 PM轮班 2： 8:00 AM4:00 PM轮班 3： 中午8:00 PM轮班 4： 4:00 PM午夜轮班 5： 10:00 PM6:00 AM表1.14 上海地铁公司人员排程问题的数据轮班的时段时段x1x2x3x4x5最少需要代理商的数量6:00 AM8:00 AM8:00 AM10:00 AM10:00 AM中午中午2:00

20、PM2:00 PM4:00 PM4:00 PM6:00 PM6:00 PM8:00 PM8:00 PM10:00 PM10:00 PM午夜午夜6:00 PMx11x 21x 31x 41x 22x 32x 42x 52x 43x 53x 63x 73x 64x 74x 84x 94x 95 x 10 548796587647382435215每个代理商的每日成本170160175180195表1.14中标注xij的部分表示这段时间是有相应轮班的。因为轮班之间的重要程度有差异，所以协议中工资也因轮班所处的时间而不同。每一轮班对代理商的补偿（包括收益）如最底行所示。问题就是，在最底行数据的基础上，

21、确定将多少代理商分派到一天之中的各个轮班中去，以使得人员费用最小，同时必须保证最后一栏中所要求的服务水平的实现。建模这个问题实际上是一个纯成本收益平衡问题。为了建立模型，首先必须明确包含的活动和收益。活动对应于各轮班活动的水平就是分派到那一轮班的代理商数目活动的一个单位是指分派到该轮班的一个代理商因此，线性规划通常是寻找最优活动水平组合的问题，在这里，就可描述为确定最佳的轮班人数。收益对应于时段在每一时段里，活动的收益就是代理商所提供给客户的服务收益的水平由那段时间在岗位的代理商的数目来衡量的1.4.2 Matlab求解问题的目标是： 最小化 成本=所有代理商每日总人力成本 成本=170 x1

22、+160 x2+175 x3+180 x4+195 x5约束： 6:00 AM8:00 AM之间总的代理商数= x1 488:00 AM10:00 AM之间总的代理商数= x1+ x2 7910:00 AM中午之间总的代理商数= x1+ x265中午8:00 AM之间总的代理商数= x1+ x2+ x3872:00 PM4:00 PM之间总的代理商数= x2+ x3644:00 PM6:00 PM之间总的代理商数= x3+ x4736:00 PM8:00 PM之间总的代理商数= x3+ x4828:00 PM10:00 PM之间总的代理商数= x44310:00 PM午夜之间总的代理商数= x

23、4+ x552午夜6:00 PM之间总的代理商数= x515对如此多变量和约束条件的线性规划问题，如果用手算，那是件很麻烦得事，不仅需要很多时间和耐心，而且容易出错。现在利用计算机程序来计算。首先需要输入矩阵： m1请输入约束条件个数: 10请输入变量个数: 5请输入目标函数系数矩阵：170，160，175，180，195请输入约束条件系数矩阵：1,0,0,0,0;1,1,0,0,0;1,1,0,0,0;1,1,1,0,0;0,1,1,0,0;0,0,1,1,0;0,0,1,1,0;0,0,0,1,0;0,0,0,1,1;0,0,0,0,1请输入约束条件右端常数矩阵：48，79，65，87，6

24、4，73，82，43，52，15按下回车，计算机显示了结果。结果如下 ：目标函数已得到最优值 30610可以得到，当x1=48, x2 =31，x3=39, x4=43, x5=15时，最优解是30610。2案例分析与Matlab求解2.1 案例分析一与Matlab求解我们先来看用MATLAB实现对偶单纯形法codeclear;A=; %A代表的矩阵B=; %B代表的矩阵C=; %C代表的矩阵f=y(A,B,C)/codecode%对偶单纯形法function result=y(A,B,C)a=-1*A;row line=size(A);a=a eye(row,row);b=-1*B;c=C

25、zeros(1,row);dex=c; %dex为判别数 basic=line+1:1;line+row; %basic为基可行解X=zeros(1,line);X1=zeros(1,line+row);b1=sort(b);while(b1(1)0) m=0; for i=1:length(b) if(b(i)=0) count=count+1; end end; if(count=length(n) error(无最优解); end seta=dex./n; seta1=-Inf; for i=1:length(seta) if(seta(i)=seta1&n(i)num2 xx,fva=

26、trap2(m,n,e,b1,b2);else xx,fva=trap3(m,n,e,b1,b2);endp=round(xx);beq=b1;b2;A=调运运输表disp(p);B=总运费：disp(fva);trap1.m%trap1.产销平衡functionxx,fv=trap1(m,n,e,b1,b2)p=e;f=p(:);aeq1,aeq2=trb(m,n);aeq=aeq1;aeq2;beq=b1;b2;lb=zeros(m*n,1);x,fval,exitflag,output,lambda=linprog(f,aeq,beq,lb);fv=fval;xx=reshape(x,n

27、,m);xx=xx;trb.m形成运输问题的约束矩阵的指令functionaq1,aq2=trb(m,n)o=ones(1,n);e=eye(n);z1=zeros(m,m*n);for i=1:mz1(i,(i-1)*n+1:i*n)=o;endaq1=z1;z2=e;for i=1:m-1z2=z2,e;endaq2=z2; 运行结果：（Matlab运行截图如下）3.2 案例分析二与Matlab求解3.2.1 产大于销的运输问题例3.3 设有A1、A2、A3三个产地生产某种物资，其产量分别为7t、5t、7t，B1、B2、B3、B4四个销地需要该种物资，销量分别为2t、3t、4t、6t，又知

28、各产销地之间的单位运价表见表3.26，试决定总运费最少的调运方案。表3.26销点B1单价/元销点B2单价/元销点B3单价/元销点B4单价/元产量/t加工厂A1X12X211X33X447加工厂A2X510X63X75X895加工厂A3X97X108X111X1227销量/t2346解: 设为产地运往销地的数量，并标在表3.26上，从表3.26可得下述关系式：（1）总运费函数.（2）x满足约束条件C： ，. ，.至此我们可将所述问题归结为下述线性规划（2）求解. . （1） ， （2）线性规划（2）的解就是最优调运方案，下面给出（2）的MATLAB语言程序：(运行e.m程序文件，判断产销关系后自

29、行调用trap2)trap2.m%trap2.产大于销functionxx,fv=trap(m,n,e,b1,b2)p=e;f=p(:);aq1,aq2=trb(m,n);a=aq1;b=b1;aeq=aq2;beq=b2;lb=zeros(m*n,1);x,fval,exitflag=linprog(f,a,b,aeq,beq,lb);fv=fval;xx=reshape(x,n,m);xx=xx;trb.m形成运输问题的约束矩阵的指令此略，程序同例3.1中一样。运行计算过程分析：（1）形成运输问题的约束矩阵的指令。 ，过程同产销平衡求解相同。（2）产销平衡运输问题求解指令指令。的输入和输出

30、与完全相同.如例3.2是产大于销的运输问题，其中产地3个，销地4个，单位运价矩阵为，产量矩阵为，销量矩阵为。用自编指令求得最优产销矩阵为： 和最小总运费用fv为35元。运行结果：如例3.3中有条件为无限量的，若要用Matlab来求解，首先将其化解为产销平衡的运输表。再使用产销平衡的Matlab程序来计算就可以得出最优方案。具体步骤如下：写出这个问题的产销平衡表（表3.27）和单位运价表（表3.28）。表3.27产量A50B60C50D50销量302070301050表3.28 A161613221717B141413191515C19192023MMDM0M0M0运行e2.m，将以上两表按要求

31、输入MATLAB运算程序，得到最优方案，运行结果如下：（注：表中的M只要输入一个足够大的正数如10000即可）最后得到的最优解如表3.29表3.29产量A5050B20103060C3020050D302050销量3020703010503.2.2 销大于产的运输问题与产大于销的运输问题相似，销大于产也是按照相同的计算方法。例题及程序如下：例3.4 某厂有B1、B2、B3三个分厂，在生产中需要的热水由A1、A2两个锅炉供应。每月各分厂的需求量、锅炉供应量及输送热水的单位运价如表3.30所示。现要确定供水计划，使总运送费用最省。表3.30分厂B1单位/元分厂B2单位/元分厂B3单位/元供应量/t

32、锅炉A1x17x26x38280锅炉A2x48x55x69270需求量/t100320260解： 这是一个销量大于产量的运输问题。现设为两锅炉运热水到各分厂的数量，并标在表3.30上。从表3.30我们不难得到如下结果：（1）运输总费用函数.（2）约束条件C： ，. ，.这样所求问题可写成线性规划： C ， （3）在线性规划（3）中，有不等式约束，也有等式约束。下面给出线性规划（3）的MATLAB语言程序：(运行e.m程序文件，判断产销关系后自行调用trap3)trap3.m%trap3.销大于产function xx,fv=trap3(m,n,e,b1,b2)p=e;f=p(:);aq1,aq

33、2=trb(m,n);aeq=aq1;beq=b1;a=aq2;b=b2;lb=zeros(m*n,1);x,fval,exitflag=linprog(f,a,b,aeq,beq,lb);fv=fval;xx=reshape(x,n,m);xx=xx; trb.m形成运输问题的约束矩阵的指令此略，程序同例3.1中一样。运行计算过程分析：（1）形成运输问题的约束矩阵的指令。 调用函数，产生为产量的约束矩阵，为销量的约束矩阵。（2）销大于产的运输问题的求解指令指令，的输入与输出与完全相同。其中产地2个，销地3个，单位运价矩阵为，产量矩阵为，销量矩阵为。程序执行后得fval3390，x1100，x250，x3130，x40，x5270，x60，至此得到最优调运热水方案。现根据程序中得调运矩阵xx列表，调运方案将更为清楚。表3.31分厂B1分厂B2分厂B3供应量/t锅炉A110050130280锅炉A202700270需求量/t100320260表3.31为最优调运热水方案，其总运费为3390元。运行结果：3.3 案例分析三与Matlab求解3.3.1 案例分