线性规划的延伸问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,例一、某银行经理计划用一笔资金进行有价证券的投资，可供购进的证券以及其信用等级，到期年限、收益如下表所示，按照规定，市政证券的收益可以免税，其他证券的收益需按,50,的税率纳税，此外还有以下限制：,政府及代办机构的证券总共至少要购进400万元；,所购证券的平均信用等级不超过1.4(信用等级数字越小，信用程度越高)；,所购证券的平均到期年限不超过,5,年。,证券名称,证券种类,信用等级,到期年限,/,年,到期税前收益,/%,A,市政,2,9,4.3,B,代办机构,2,15,5.,4,C,政府,1,4,5.0,D,政府,1,3,4.4,E,市政,5,2,4.5,试问：若该经理有1000万元资金，应如何投资？,如果能够以2.75%的利率借到不超过100万元资金，该经理应如何操作？并考虑利率在什么范围内变化时，投资方案不改变？,在1000万元资金情况下，若证券,A,的税前收益增加为4.5%,投资应否改变？若证券,C,的税前收益减少为4.8%，投资应否改变？,解：（1）设投资证券,A，B，C，D，E,的金额分别为,X1,X2,X3,X4,X5（,百万元），按照规定、限制和1000万元资金约束，其中,B、C、D,类证券到期税前收益要折半，,得线性规划模型 目标函数为税前收益最大,Max=0.043x1+0.027x2+0.025x3+0.022x4+0.045x5,以上的平均信用等级和平均到期年限均是采用加权平均法 进行计算的。,答案为证券,A,，,C,，,E,分别投资,2.182,百万元，,7.364,百万元，,0.454,百万元，最大税后收益为,0.298,百万元。,2）,由于0.298 百万元除以10等于0.0298，大于借款利率2.75%，所以可借款100万元进行追加投资，其模型修改为：,答案为,A，C，E,分别投资2.40百万元，8.10百万元，0.5百万元，最大税后收益为0.3007百万元。,3）如果具有灵敏度分析理论知识，可以采用灵敏度分析法加以处理。但现在在,LINGO,软件的帮助下，我们可以直接用修改模型的手段加以解答。,情形一、修改后的模型为,答案：投资策略不变。即证券,A，C，E,分别投资2.182百万元，7.364百万元，0.454百万元，最大税后收益为0.3027百万元。,情形二、修改后的模型为,答案：投资策略要改变。即证券,A,，,D,，,E,分别投资,3.36,百万元，,6.48,百万元，,0.16,百万元，最大税后收益为,0.29424,百万元。,例二、一家出版社准备在某市建立两个图书销售代理点，向7个区的大学生售书，每个区的大学生数量（单位：千人）已经表示在图纸上，每个销售代理点只能向本区和一个相邻区的大学生售书，这两个销售代理点应该建在何处，才能使面对的大学生数量最大？建立该问题的整数线性规划模型。,1,2,3,5,7,4,6,解：将大学生数量为,34,，,29,，,42,，,21,，,56,，,18,，,71,的区分别标号为,1,，,2,，,3,，,4,，,5,，,6,，,7,区，划出区与区之间的如下相邻关系图：,用0-1变量 表示（）区的大学生由一个销售代理点供应图书（且 相邻），否则 ，建立该问题的整数线性规划模型为 目标函数为人数最多,63,x12+76X13+71X23+50X24+85X25+63X34,+77X45+39X46+92X47+74X56+89X67,答案：用,LINGDO,求解得到：最优解为,X25=X47=1（,其他为0），最优值为177人。,St,：,X12+X13+X23+X24+X25+X34+X45+X46,+X47+X56+X672 (,最多,2,个销售代理点,),X12+X13 1(,与,1,区相连最多,1,个点,),X12+X23+X24+X25,1(,与,2,区相连最多,1,个点,),X13+X23+X34 1(,与,3,区相连最多,1,个点,),X24+X34+X45+X46+X47 1(,与,4,区相连,),X25+X45+X56 1(,与,5,区相连最多,1,个点,),X46+X56+X671(,与,6,区相连最多,1,个点,),X47+X67 1(,与,7,区相连最多,1,个点,),Xij=0,或,1,例三、某储蓄所每天营业时间为上午,9,：,00,到下午,5,：,00,，根据经验，每天不同时间段所需的服务员数量如下：,时间段,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,服务员数量,4,3,4,6,5,6,8,8,储蓄所可以雇佣全时和半时两类服务。全时服务人员每天报酬,100,元，从上午,9,：,00,到下午,5,：,00,工作，但中午,12,：,00,到下午,2:00,之间必须安排一小时的午餐时间。储蓄所每天可以雇佣不超过,3,名的半时服务人员，每个半时服务人员必须连续工作,4,小时，报酬,40,元。问该储,蓄所应如何雇佣全时和半时两类服务员？该储蓄所如果不能雇佣半时服务员，每天至少增加多少费用？如果雇佣半时服务员的数量没有限制，每天可减少多少费用？,解：设储蓄所每天雇佣的全时服务员以12:0013:00为午餐时间的有,x1,名，以13:0014:00为午餐时间的有名,x2,名；半时服务员中从9:00，10:00，11:00，12:00，13:00开始工作的分别为 名。列出线性规划模型 目标函数为费用最少,答案：最优解 ，最小费用为,820,元。,变形一、不能雇佣半时服务员,最优解为 ，最小费用为1100元，即每天至少增加1100-820=280元。,变形二、雇佣半时服务员的数量没有限制,最优解为 ，最小费用为,560,元，即每天可以减少,820-560=260,元。,例五、,一家保姆服务公司专门向顾主提供保姆服务。根据估计，下一年的需求是：春季6000人日，夏季7500人日，秋季5500人日，冬季9000人日。公司新招聘的保姆必须经过5天的培训才能上岗，每个保姆每季度工作（新保姆包括培训）65天。保姆从该公司而不是从顾主那里得到报酬，每人每月工资800元。春季开始时公司拥有120名保姆，在每个季度结束后，将有15的保姆自动离职。,（1）如果公司不允许解雇保姆，请你为公司制定下一年的招聘计划；哪些季度需求的增加不影响招聘计划？可以增加多少？,（2）如果公司在每个季度结束后允许解雇保姆，请为公司制定下一年的招聘计划。,解：1）设四个季度开始时公司新招聘的保姆数量分别为 人，,4,各季度开始时保姆总数量分别为,人。以本年度付出的总报酬最少（即,4,个季度开始时保姆总数量之和最小）为目标，则模型为总人数最少,约束条件如下,（春天，因为新保姆只有,60,天的工作时间）,以下类似有,（夏天）,（冬天）,（秋天）,（春天开始时拥有120名熟练保姆+春天新招聘的保姆应该等于供应春天市场的保姆数）,（夏天开始时拥有春天结束时留下的保姆数,0.85,S1+,夏天新招聘的保姆应该等于供应夏天市场的保姆数）,类似有如下约束,（秋天）,（冬天）,答案：变量是否取整数，结果会有较大的不同，因为在,0.15,的自动离职下，要保证,s2,，,s3,，,s4,为整数，将会大大增加招聘的人数。,2),设四个季度开始时公司新招聘的保姆数量分别为,人，四个季度结束时解雇的保姆数量分别,为人，4个季度开始时保姆总数量分别为,人。则模型为总人数最少,春夏秋冬约束条件如下,（夏天开始时拥有春天结束时留下的保姆数,0.85,S1+,夏天新招聘的保姆春天结束时解聘的保姆数应该等于供应夏天市场的保姆数）,类似有,六：,在甲乙双方的一场战争中，一部分甲方部队被乙方部队包围长达,4,个月，由于乙方封锁了所有水陆交通通道，被包围的乙方部队只能依靠空中交通维持供给。运送,4,个月的供给分别需要,2,次、,3,次、,3,次、,4,次飞行，每次飞行编队由,50,架飞机组成（每架飞机需要,3,名飞行员），可以运送,10,万吨物资，每架飞机每个月只能飞行一次，每名飞行员每月也只能飞行一次，在执行完任务后的返回途中有,20%,的飞机会被乙方击落，相应的飞行员也因此牺牲或失踪。在第一个月开始的时候，甲方拥有,110,架飞机和,330,名熟练的飞行员，在每个月开始时，甲方可以招聘新飞行员和购买新飞机，新飞机必须经过一个月的检查后才可以投入使用，新飞行员必须在熟练飞行员的指导下经过一个月的训练才能投入飞行。1)每名熟练飞行员作为教练每月指导,20,名飞行员（包括他自己在内），每名飞行员,在完成一个月的飞行任务后必须有一个月的带薪假期，假期结束后才能在投入飞行。已知各项费用如下，请你为甲方安排一个飞行计划。,第一个月,第二个月,第三个月,第四个月,新飞机价格,200 195 190 185,闲置的熟练的,飞行员报酬,7 6.9 6.8 6.7,教练和新飞行员,报酬（含培训费）,10 9.9 9.8 9.7,执行任务的熟练,飞行员报酬,9.0.8 9.9.8 9.7,休假的熟练的,飞行员报酬,5.0 4.9 4.8 4.7,2)如果每名熟练飞行员可以作为教练每个月指导,不超过,20,名飞行员,(,包括他自己在内,),进行训练，模型和结果有哪些改变？,解：1)设每月购买新飞机,x1，x2，x3，x4,架，每月闲置飞机,y1，y2，y3，y4,架，每月熟练飞行员任教练的人数,z1，z2，z3，z4,人，每月新招聘飞行员人数,w1，w2，w3，w4,人，每月闲置熟练飞行员人数,s1，s2，s3，s4,人，,每月休假的熟练飞行员人数,t1，t2，t3，t4,人。,第一个月,第二个月,第三个月,第四个月,购新飞机,X1 X2 X3 X4,购机费用,200,X1 195X2 190X3 185X4,闲置飞机数,Y1 Y2 Y3 Y4,教练,Z1 Z2 Z3 Z4,新飞行员,W1 W2 W3 W4,以上两,者费用,10(,z1+w1),9.9(,z2+w2),9.8(,z3+w3),9.7(,z4+w4),执行任务飞行员数与费用,依次为,300,（,9,），,450,（,8.9,），,450,（,9.8,），,600,（,9.7,）,闲置熟练飞行员数与费用,依次为,S1,（,7,）,，S2,（,6.9,）,，S3,（,6.8,）,，S4,（,6.7,）,休假熟练飞行员数与费用依次为,t1,（,5,）,，,t2,（,4.9,）,，,t3,（,4.8,），,t4,（,4.7,）,建立目标函数如下：,Min=200 x1+195x2+190 x3+185x4+10,（,z1+w1,）,+9.9,（,z2+w2,）,+9.8,（,z3+w3,）,+9.7,（,z4+w4,）,+7s1+6.9s2+6.8s3+6.7s4,；,（,由于执行任务的飞行员是定数，其费用是确定的，可以不列入目标函数里；同理，休假熟练飞行员数,1,2,3,4,月为,t1=0,，,t2=300,80%=240,，,t3=450,80%=360,，,t4=450,80%=360,，,其费用也是确定的，不列入目标函数里；因为列在里面也不会影响最优方案,）,飞机数目限制：,第一月,110=100+,y1,；,第二月,150+,y2=80+x1+y1,（,第二月的可用飞机数为第一月执行任务后返回的飞机数,80,，加上第一月闲置的飞机数,y1,，,再加上第一月新购飞机数,x1,，,应该等于第二月执行任务的飞机数,150,，加上第二月闲置的飞机数,y2,）；,第三月,150+,y3=120+x2+y2,；,第四月,200+,y4=120+x3+y3,；,飞行员数目限制：,第一月,330=300+,s1+z1,（,一月执行任务的飞行员数,300,人，加上闲置熟练飞行员数,s1,，,再加上担任教练的熟练飞行员数,z1,），,第三月,s2+z2+w2+240=450+s3+z3,；,第四月,s3+z3+w3+360=600+s4+z4,；,教练与新飞行员比例限制：,19z,1=,w1,19z,2=,w2,19z,3=,w3,19z,4=,w4,以上变量均为非负整数,第二月,s1+z1+w1=450+s2+z2,（,二月可用飞行员数为上月闲置熟练飞行员数,s1,，,加上上月担任教练的熟练飞行员数,z1,，,再加上上月新飞行员数,w1,，,应该等于执行任务的飞行员数,450,人，加上闲置熟练飞行员数,s2,，,再加上担任教练的熟练飞行员数,z2,，,其中一月份执行任务后返回的,240,名飞行员在休假，在三月份才可以进入可飞行状态）；类似有,水库,A,发电站,A,水库,B,发电站,B,四、,某电力公司经营两座发电站，发电站分别位于两个水库上，位置如下图所示。,已知发电站,A,可以将水库,A,的一万立方米的水转换为400千度电能，发电站,B,只能将水库,B,的一万立方米的水转换为200千度电能.发电站,A、B,每个月的最大发电能力分别是60000千度，35000千度。每个月最多有50000千度电能够以200元/千度的价格售出，多余的电能只能够以140元/千度的价格售出。水库,A，B,的其他有关数据如下（单位：万立方米）,水源,B,水源,A,水库,A,水库,B,水库最大蓄水量,2000,1500,水源流入水量,本月,200,40,下月,130,15,水库最小蓄水量,1200,800,水库目前蓄水量,1900,850,请你为该电力公司制定本月和下月的生产经营计划。（千度的非国际单位制单位，1千度1000千瓦时）,解：令,a1，a2,表示,A,水库在本月，下月,A,电站的发电水量；,b1，b2,表示,B,水库在本月，下月,B,电站的发电水量；,c1，c2,表示,A,水库在本月，下月直接放走的水量；,d1，d2,表示,B,水库在本月，下月直接放走的水量；,e1，e2,表示,A,水库在本月末，下月末的库存水量；,f1，f2,表示,B,水库在本月末，下月末的库存水量；,x1，x2,表示本月，下月以高价销售的电量；,y1，y2,表示本月，下月以低价销售的电量；,列出线性规划模型,目标函数为销售收入最大,约束条件为,本月发电量等于本月销售电量,下月发电量等于下月销售电量,A,水库本月守恒,A,水库,下,月守恒,B,水库本月守恒,B,水库,下,月守恒,发电能力限制,水库蓄水量限制,高售价电量限制,答案：,X1=50000,，,X2=50000,，,Y1=45000,，,Y2=45000,，,A1=150,，,B1=175,，,A2=150,，,B2=175,，,C1=0,，,E1=1950,，,C2=645,，,E2=1285,，,D1=0,，,F1=865,，,D2=0,，,F2=1500,最大销售收入为,七：某公司将4种不同含硫量的液体原料（分别记为甲、乙、丙、丁）混合生产两种产品（分别记为,A、B）。,按照生产工艺的要求，原料甲、乙、丁必须首先倒入混合池中混合，混合后的液体再分别与原料丙混合生产,A、B。,已知原料甲、乙、丙、丁的含硫量分别是3，1，2，1（），进货价格分别为6，16，10，15（千元/吨）。产品,A、B,的含硫量分别不能超过2.5，1.5（），售价分别为9，15（千元/吨）。根据市场信息，原料甲、乙、丙的供应没有限制，原料丁的供应量最多为50吨；产品,A、B,的市场需求量分别为100吨、200吨。问应如何安排生产？,解：设,A,中拥有混合液,x1,吨，丙原料,x2,吨；,B,中拥有混合液,y1,吨，丙原料,y2,吨；,又设甲、乙、丁混合液中含量百分比未,s1,，,s2,，,s3,；,显然有,s1+s2+s3=1,。,则,A,的销售收入为,9,（,x1+x2,），,B,的销售收入为,15,（,y1+y2,），,A,中含有原料甲、乙、丁、丙的量为,x1s1,，,x1s2,，,x1s3,，,x2,；,含硫量为,0.03,x1s1+0.01x1s2+0.01x1s3+0.02x2,；,B,中含有原料甲、乙、丁、丙的量为,y1s1,，,y1s2,，,y1s3,，,y2,；,含硫量为,0.03,y1s1+0.01y1s2+0.01y1s3+0.02y2,；,甲原料成本为,6,（,x1s1+y1s1,）；,乙原料成本为,16,（,x1s2+y1s2,）；,丁原料成本为,15,（,x1s3+y1s3,）；,丙原料成本为,10,（,x2+y2,）；,A,产品含硫量百分比限制（,0.03,x1s1+0.01x1s2+0.01x1s3+0.02x2,）（,x1+x2,）,2.5%,；,B,产品含硫量百分比限制（,0.03,y1s1+0.01y1s2+0.01y1s3+0.02y2,）（,y1+y2,）,1.5%,；,市场需求限制,x1+x2=100,；,y1+y2=200,；,丁原料限制,x1s3+y1s,350 ；,以及,s1+s2+s3=1 ；,目标函数为,Max=9,（,x1+x2,）,+15,（,y1+y2,）,6,（,x1s1+y1s1,）,16,（,x1s2+y1s2,）,15,（,x1s3+y1s3,）,10,（,x2+y2,）。,答案：,MAX=350,X2,=,100,Y1,=,100,Y2,=,100,S2,=,0.50,S3,=,0.50,例八、,有,4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：分钟）,秘书初试,主管复试,经理面试,同学甲,13,15,20,同学乙,10,20,18,同学丙,20,16,10,同学丁,8,10,15,这4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8：00，问他们最早何时能离开公司？分成24类逐一求解可得所有面试完成至少需要,84,分钟。面试顺序为,4-1-2-3,（丁,-,甲,-,乙,-,丙）。,解：采用列举法，4名同学的面试顺序共有4！=24种，进行分别讨论。,顺序 1,秘书初试,主管复试,经理面试,甲,13,13+15=28,28+20=48,乙,13+10=23,28+20=48,48+18=6,6,丙,23+20=43,48+16=64,6,6+10=76,丁,43+8=51,64+10=74,7,6+15=91,顺序 2,秘书初试,主管复试,经理面试,甲,13,13+15=28,28+20=48,乙,13+10=23,28+20=48,48+18=6,6,丁,23+8=31,48+10=58,6,6+15=81,丙,31+20=51,58+16=74,81+10=96,顺序 3,秘书初试,主管复试,经理面试,甲,13,13+15=28,28+20=48,丙,13+20=33,33+16=49,49+10=59,乙,33+10=43,49+20=69,69+18=87,丁,43+8=51,69+10=79,87+15=102,