数据模型和决策ppt课件.ppt

数据、模型与决策,2020/4/26,数据、模型与决策,2,围猫游戏,2020/4/26,数据、模型与决策,3,围猫策略分析,更大范围内围点最短路径分析猫行动的方向隔点围法，在猫跑出包围圈之前围堵薄弱环节,灵敏度分析与最优解的解释,5,线性规划模型的构建,1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件(定性-定量、权重、可行域的设置）一般形式目标函数：Max（Min）z=c1x1+c2x2+cnxn约束条件：s.t.a11x1+a12x2+a1nxn（=,）b1a21x1+a22x2+a2nxn（=,）b2am1x1+am2x2+amnxn（=,）bmx1，x2，xn0,2020/4/26,数据、模型与决策,2020/4/26,数据、模型与决策,6,AB公司,AB公司在这一周内只生产两种产品：产品A和产品B。管理部门必须决定每种产品各生产多少吨。产品A的售价为每吨25美元，产品B的售价为每吨10美元。生产出的全部产品都将被出售。产品A和产品B由多种材料混合而成，这些材料都从仓库中提取。可供这一周使用的三种原材料数量如下：,原料1：12000吨原料2：4000吨原料3：6000吨产品A由60%的原料1和40%的原料2制成产品B由50%的原料1，10%的原料2和40%的原料3制成,2020/4/26,数据、模型与决策,7,有人以1美元/吨的价格提供500吨的原料1，我们是否接受？有人以50美元/吨的价格提供原料2，是否接受？一个公司彻底用完了原料3，而以15美元/吨的价格向我们求购原料3（有多少要多少），我们是否应该卖给他们一些？,如何决策？,2020/4/26,数据、模型与决策,8,例1.某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位、产品才能使工厂获利最多？线性规划模型：目标函数：Maxz=50 x1+100 x2约束条件：s.t.x1+x23002x1+x2400 x2250 x1,x20,9,图解法,(1)分别取决策变量X1,X2为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。,2020/4/26,数据、模型与决策,10,（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。,图解法,2020/4/26,数据、模型与决策,11,（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。,图解法,2020/4/26,数据、模型与决策,12,（4）目标函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。,x1,x2,z=20000=50 x1+100 x2,z=27500=50 x1+100 x2,z=0=50 x1+100 x2,z=10000=50 x1+100 x2,C,B,A,D,E,图解法,2020/4/26,数据、模型与决策,13,建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci,aij,bj变化时，对最优解产生的影响。,灵敏度分析,2020/4/26,数据、模型与决策,2020/4/26,数据、模型与决策,14,例1.目标函数：maxz=50 x1+100 x2约束条件：s.t.x1+x2300(A)2x1+x2400(B)x2250(C)x10(D)x20(E)得到最优解：x1=50，x2=250最优目标值z=27500,15,x1,x2,z=20000=50 x1+100 x2,z=27500=50 x1+100 x2,z=0=50 x1+100 x2,z=10000=50 x1+100 x2,C,B,A,D,E,图解法,2020/4/26,数据、模型与决策,16,改变目标向量,目标函数中的系数ci的灵敏度分析考虑例1的情况，ci的变化只影响目标函数等值线的斜率，目标函数z=50 x1+100 x2在z=x2(x2=z斜率为0)到z=x1+x2(x2=-x1+z斜率为-1)之间时，原最优解x1=50，x2=100仍是最优解。一般情况z=c1x1+c2x2写成斜截式x2=-(c1/c2)x1+z/c2目标函数等值线的斜率为-(c1/c2)，当-1-(c1/c2)0（*）时，原最优解仍是最优解。,17,假设产品的利润100元不变，即c2=100，代到式（*）并整理得0c1100假设产品的利润50元不变，即c1=50，代到式（*）并整理得50c2+假若产品、的利润均改变，则可直接用式（*）来判断。假设产品、的利润分别为60元、55元，则-2-(60/55)-1那么，最优解为z=x1+x2和z=2x1+x2的交点x1=100，x2=200。,2020/4/26,数据、模型与决策,18,约束条件中右边系数bj的灵敏度分析当约束条件中右边系数bj变化时，线性规划的可行域发生变化，可能引起最优解的变化。考虑例1的情况：假设设备台时增加10个台时，即b1变化为310，这时可行域扩大，最优解为x2=250和x1+x2=310的交点x1=60，x2=250。变化后的总利润-变化前的总利润=增加的利润(5060+100250)-(5050+100250)=500，500/10=50元说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。,改变右端向量,19,假设原料A增加10千克时，即b2变化为410，这时可行域扩大，但最优解仍为x2=250和x1+x2=300的交点x1=50，x2=250。此变化对总利润无影响，该约束条件的对偶价格为0。解释：原最优解没有把原料A用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。在一定范围内，当约束条件右边常数增加1个单位时（1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）；（2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）；（3）若约束条件的对偶价格等于0，则最优目标函数值不变。,2020/4/26,数据、模型与决策,20,当有多个系数变化时，需要进一步讨论。百分之一百法则：对于所有变化的目标函数决策系数（约束条件右边常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过100%时，最优解不变（对偶价格不变，最优解仍是原来几个线性方程的解）。*允许增加量=上限-现在值c1的允许增加量为100-50=50b1的允许增加量为325-300=25*允许减少量=现在值-下限c2的允许减少量为100-50=50b3的允许减少量为250-200=50*允许增加的百分比=增加量/允许增加量*允许减少的百分比=减少量/允许减少量,百分百法则,2020/4/26,数据、模型与决策,21,例：c1变为74,c2变为78,则(74-50)/50+(100-78)/50=92%，故最优解不变。b1变为315,b3变为240,则(315-50)/25+(250-240)/50=80%，故对偶价格不变（最优解仍是原来几个线性方程的解）。在使用百分之一百法则进行灵敏度分析时，要注意：1）当允许增加量（允许减少量）为无穷大时，则对任意增加量（减少量），其允许增加（减少）百分比均看作0；2）百分之一百法则是充分条件，但非必要条件；也就是说超过100%并不一定变化；3）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化的情况。这种情况下，只有重新求解。,22,“管理运筹学”软件的输出信息分析,相差值表示相应的决策变量的目标系数需要改进的数量，使得决策变量为正值，当决策变量已为正数时，相差数为零。松弛/剩余变量的数值表示还有多少资源没有被使用。如果为零，则表示与之相对应的资源已经全部用上。对偶价格表示其对应的资源每增加一个单位，将增加多少个单位的最优值。目标函数系数范围表示最优解不变的情况下，目标函数的决策变量系数的变化范围。当前值是指当前的最优解中的系数取值。常数项范围是指约束条件的右端常量。上限值和下限值是指当约束条件的右端常量在此范围内变化时，与其对应的约束条件的对偶价格不变。当前值是指现在的取值。以上计算机输出的目标函数系数和约束条件右边值的灵敏度分析都是在其他系数值不变，只有一个系数变化的基础上得出的！,2020/4/26,数据、模型与决策,23,注意：当约束条件中的常数项增加一个单位时，最优目标函数值增加的数量称之为影子价格。在求目标函数最大时，当约束条件中的常数项增加一个单位时，目标函数值增加的数量就为改进的数量，所以影子价格等于对偶价格；在求目标函数值最小时，改进的数量就是减少的数量，所以影子价格即为负的对偶价格。“管理运筹学”软件可以解决含有100个变量50个约束方程的线性规划问题，可以解决工商管理中大量的问题。如果想要解决更大的线性规划问题，可以使用由芝加哥大学的L.E.Schrage开发的Lindo计算机软件包的微型计算机版本Lindo/PC。,“管理运筹学”软件的输出信息分析,2020/4/26,数据、模型与决策,2020/4/26,数据、模型与决策,24,AB公司,AB公司在这一周内只生产两种产品：产品A和产品B。管理部门必须决定每种产品各生产多少吨。产品A的售价为每吨25美元，产品B的售价为每吨10美元。生产出的全部产品都将被出售。产品A和产品B由多种材料混合而成，这些材料都从仓库中提取。可供这一周使用的三种原材料数量如下：,原料1：12000吨原料2：4000吨原料3：6000吨产品A由60%的原料1和40%的原料2制成产品B由50%的原料1，10%的原料2和40%的原料3制成,2020/4/26,数据、模型与决策,25,目标函数：max25A+10B,2020/4/26,数据、模型与决策,26,有人以1美元/吨的价格提供500吨的原料1，我们是否接受？回答：除非我们要为将来使用原料1做储备才接受，因为我们已经有过量的原料1.有人以50美元/吨的价格提供原料2，是否接受？回答：接受。在500吨以内每增加1吨的原料2，就将会有62.5美元的收益。如果以50美元/吨的价格接受，我们还会有12.5美元/吨的纯收入，总共收入6250美元。,2020/4/26,数据、模型与决策,27,续,一个公司彻底用完了原料3，而以15美元/吨的价格向我们求购原料3（有多少要多少），我们是否应该卖给他们一些？回答：如果他们负责运输，就把6000吨原料3卖给他们。我们放弃了原料3的9.375美元/吨的收益，从而使得B产品的产量为零。如果我们以15美元/吨的价格卖掉6000吨的原料3，总贡献将会有33750美元的增加（15-9.375）*6000。,线性规划在工商管理中的应用,29,人力资源分配的问题,例1某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?,2020/4/26,数据、模型与决策,30,人力资源分配的问题,解：设xi表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6约束条件：s.t.x1+x660 x1+x270 x2+x360 x3+x450 x4+x520 x5+x630 x1,x2,x3,x4,x5,x60,2020/4/26,数据、模型与决策,31,人力资源分配的问题,例2一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？,2020/4/26,数据、模型与决策,32,人力资源分配的问题,解：设xi(i=1,2,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6+x7约束条件：s.t.x1+x2+x3+x4+x528x2+x3+x4+x5+x615x3+x4+x5+x6+x724x4+x5+x6+x7+x125x5+x6+x7+x1+x219x6+x7+x1+x2+x331x7+x1+x2+x3+x428x1,x2,x3,x4,x5,x6,x70,2020/4/26,数据、模型与决策,2020/4/26,数据、模型与决策,33,往往一些服务行业的企业对人力资源的需求一周内像例2所描述的那样变化，而每天的各时间段的需求又像例1往往描述的那样变化，在保证工作人员每天工作8h，每周休息两天的情况下，如何安排能使人员的编制最小呢？,34,生产计划的问题,例3某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？,2020/4/26,数据、模型与决策,35,生产计划的问题,解：设x1,x2,x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。求xi的利润：利润=售价-各成本之和产品甲全部自制的利润=23-(3+2+3)=15元产品甲铸造外协，其余自制的利润=23-(5+2+3)=13元产品乙全部自制的利润=18-(5+1+2)=10元产品乙铸造外协，其余自制的利润=18-(6+1+2)=9元产品丙的利润=16-(4+3+2)=7元可得到xi（i=1,2,3,4,5）的利润分别为15元、10元、7元、13元、9元。,2020/4/26,数据、模型与决策,36,生产计划的问题,通过以上分析,可建立如下的数学模型:目标函数：Max15x1+10 x2+7x3+13x4+9x5约束条件：5x1+10 x2+7x380006x1+4x2+8x3+6x4+4x5120003x1+2x2+2x3+3x4+2x510000 x1,x2,x3,x4,x50,2020/4/26,数据、模型与决策,37,套裁下料问题,例4某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？解：共可设计下列5种下料方案，见下表,设x1,x2,x3,x4,x5分别为上面5种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5约束条件：s.t.x1+2x2+x41002x3+2x4+x51003x1+x2+2x3+3x5100 x1,x2,x3,x4,x50,38,用“管理运筹学”软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。即x1=30;x2=10；x3=0；x4=50；x5=0；只需90根原材料就可制造出100套钢架。注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。,3套裁下料问题,39,投资问题,例5：某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。据测定每万元每次投资的风险指数如右表：问：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？,2020/4/26,数据、模型与决策,40,解：1）确定决策变量：连续投资问题设xij(i=15，j=14)表示第i年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量：Ax11x21x31x41x51Bx12x22x32x42Cx33Dx24,投资问题,2）约束条件：第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是x11+x12=200；第二年：B次年末才可收回投资，故第二年年初有资金1.1x11，于是x21+x22+x24=1.1x11；第三年：年初有资金1.1x21+1.25x12，于是x31+x32+x33=1.1x21+1.25x12；第四年：年初有资金1.1x31+1.25x22，于是x41+x42=1.1x31+1.25x22；第五年：年初有资金1.1x41+1.25x32，于是x51=1.1x41+1.25x32；B、C、D的投资限制：xi230(i=1、2、3、4)，x3380，x24100,投资问题,3）目标函数及模型：a)Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200 x21+x22+x24=1.1x11；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；x51=1.1x41+1.25x32；xi230(i=1、2、3、4)，x3380，x24100 xij0(i=1、2、3、4、5；j=1、2、3、4）,43,投资问题,b)所设变量与问题a相同，目标函数为风险最小，有Minf=x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24在问题a的约束条件中