数学模型数学建模 第三次作业 线性规划实验

数学模型第三次作业线性规划实验3.1实验目的与要求学会建立线性规划模型、整数规划模型学会LINGO软件的根本使用方法，求解线性规划和整数规划问题学会对线性规划问题进行灵敏度分析对计算结果进行分析和讨论根本实验1.生产方案安排NWAC电力公司为军事承包商生产4种类型的电缆。每种电缆必须经过4种相继的操作：拼接、焊接、套管和检查。表3.1给出了该问题相关的数据.承包商保证对于四种电缆的每一种最低产量是100个单位。将问题建立成一个线性规划模型，并确定最优的产品进度表基于对偶价格(DnalPrice)，你会推荐增加四种操作中哪一种操作的能力?试解释。对于四种电缆的最低产量要求对NWAC电力公司有利还是不利?试分析解：分析题意，这是一个较为根底的线性规划问题，可以设生产4种电缆数量分别为X1，X2，X3，X4，那么目标函数:MAXXXX约束条件:10.5X1+9.3X2+11.6X3+8.2X4<=480020.4X1+24.6X2+17.7X3+8.2X4<=96003.2X1+2.5X2+3.6X3+5.5X4<=47005.0X1+5.0X2+5.0X3+5.0X4<=4500X1>=100X2>=100X3>=100X4>=100使用LINGO软件进行计算：Maxsubjectto10.5X1+9.3X2+11.6X3+8.2X4<=480020.4X1+24.6X2+17.7X3+8.2X4<=96003.2X1+2.5X2+3.6X3+5.5X4<=47005.0X1+5.0X2+5.0X3+5.0X4<=4500X1>=100X2>=100X3>=100X4>=100End运行得到结果：Globaloptimalsolutionfound.Totalsolveriterations:4VariableValueReducedCostRowSlackorSurplusDualPrice即当X1为100，X2约为190，X3为100，X4为100时可以得到一个最大利润约为$。(2)“DUALPRICE〞〔对偶价格〕列出最优单纯形表中判别数所在行的松弛变量的系数，表示当对应约束有微小变动时，目标函数的变化率，输出结果中对应每一个约束有一个对偶价格。假设其数值为x，表示对应约束中不等式右端项假设增加一个单位，目标函数将增加x个单位〔max型问题〕。当REDUCECOST或DUALPRICE的值为0。表示当微小扰动不影响目标函数。由(1)中得到的结果，其四种能力对应的DUALPRICE如下：RowSlackorSurplusDualPrice因此应该考虑增强第一种技术，即拼接技术。(3)根据第二问的依据，需要分析最低产量要求的对偶价格列出其关系式所对应的Lingo分析结果：RowSlackorSurplusDualPrice易知，只有第二种电缆的最低产量要求对最高利润无影响；第一、第三、第四种电缆产量的最低要求都不利于NWAC电力公司，增加这三种电缆产量的最低要求，都会导致最大利润的减少。2.工程进度问题某城市在未来的五年内将启动四个城市住房改造工程。每项工程有不同的始时间，工程周期也不一样。表3.2提供这些工程的根本数据。工程1和工程4必须在规定的周期内全部完成。必要时，其余的二项工程可以在预算的限制内完成局部。然而，每个工程在它的规定时间内必须至少完成25%.每年底，工程完成的局部立刻入住，并且实现一定比例的收入.例如，如果工程1在第一年完成40%，在第三年完成剩下的60%，在五年方案范围内的相应收入是×50(第二年×50(第三年)+(0.4+0.6)×50(第四年)+(0.4+0.6)×50(第五年)=(4×0.4+2×0.6)×50(单位:万元)。试为工程确定最优的时间进度表，使得五年内的总收入到达最大。解：设X为各项工程的完成进度假设工程1完成进度为X1,将进行工程1所获得的利润表示为：50X11+50(X11+X12)+50(X11+X12+X13)+50假设工程2完成进度为X2,将进行工程2所获得的利润表示为：70X22+70(X22+X23)+70(X22+X23+X24)假设工程3完成进度为X3,将进行工程3所获得的利润表示为：150X31+150(X31+X32)+150(X31+X32+X33)+150(X31+X32+X33+X34)假设工程4完成进度为X4,将进行工程4所获得的利润表示为：20X43+20〔X43+X44〕编辑Lingo语句：Model:max=50*(4*X11+3*X12+2*X13)+70*(3*X22+2*X23+1*X24)+150*(4*X31+3*X32+2*X33+1*X34)+20*(2*X43+1*X44);5000*X11+15000*X31<=3000;5000*X12+8000*X22+15000*X32<=6000;5000*X13+8000*X23+15000*X33+1200*X43<=7000;8000*X24+15000*X34+1200*X44<=7000;8000*X25+15000*X35<=7000;X11+X12+X13=1;X22+X23+X24+X25<=1;X22+X23+X24+X25>=0.25;X31+X32+X33+X34+X35<=1;X31+X32+X33+X34+X35>=0.25;X43+X44=1;End得到运算结果：Globaloptimalsolutionfound.Totalsolveriterations:10VariableValueReducedCostRowSlackorSurplusDualPrice由此制定一个可以获得最大利润的进度方案表：第一年第二年第三年第四年第五年工程160%〔开始〕40%0〔结束〕工程20〔开始〕022.5%77.5%〔结束〕工程30〔开始〕26.7%38.7%34.7%0〔结束〕工程4100%〔开始〕0〔结束〕3、投资问题A1A，B。100,0003编写Lingo程序：model:max=1.7*X3A+4*X2B;X1A+X1B=100000;X2A+X2B-1.7*X1A=0;X3A-1.7*X2A-4*X1B=0;X1A>=0;X1B>=0;X2A>=0;X2B>=0;X3A>=0;End得到结果Globaloptimalsolutionfound.Totalsolveriterations:0VariableValueReducedCostRowSlackorSurplusDualPrice编写Lingo程序：model:max=1.7*X3A+4*X2B;X2A+X2B=170000;X3A-1.7*X2A=0;X1A>=0;X2A>=0;X2B>=0;X3A>=0;End得到结果：Globaloptimalsolutionfound.Totalsolveriterations:0VariableValueReducedCostRowSlackorSurplusDualPrice第一年将钱全部按B方案投入，第三年再将钱全部投入A方案，或者，第一年全投资A，第二年全投资B，都可得到最大钱数680000美金。4.生产方案与库存问题这里题目条件给错，自行改为500这里题目条件给错，自行改为500model:min=37.5*X1A+28*X1B+0.9*(1.25*X1A-500)+0.75*(X1B-1000)+37.5*X2A+28*X2B+0.9*(1.25*X2A-500)+0.75*(X2B-1200)+37.5*X3A+28*X3B;1.25*X1A+1.25*X2A+1.25*X3A=1750;X1B+X2B+X3B=3400;X1A+X1B-3500<=0;X2A+X2B-3500<=0;X3A+X3B-3000<=0;X1A>=400;1.25*X1A-500+1.25*X2A>=500;1.25*X2A-500+1.25*X3A=750;X1B>=1000;X1B-1000+X2B>=1200;X2B-1000+X3B=1200;X1A>=0;X2A>=0;X3A>=0;X1B>=0;X2B>=0;X3B>=0;endGlobaloptimalsolutionfound.Totalsolveriterations:0VariableValueReducedCostRowSlackorSurplusDualPrice5、职员日程安排问题(1)在一个星期中每天安排一定数量的职员，每天需要的职员数如表所示，每个职员每周连续工作五天，休息两天.每天付给每个职员的工资是200元.公司将如何安排每天开始的工作人数，使得总费用最小.(2)假设公司每天工作8小时，周一需要18名职员，共计144小时，以此类推.公司方案雇用全职人员和兼职人员完成公司的工作，其中全职人员每天工作8小时，兼职人员每天工作4小时，无论是全职人员还是兼职人员，均是每周连续工作5天，休息2天.全职人员每小时工资25元，兼职人员每小时工资15元，并且一周内兼职人员的总工作时间不能超过全体职员总工作时间的25%，试问该公司将如何安排职员的工作时间，使解：〔1〕根据题意，设一周七天每天的工作人数为Xi，i=1,2,3,4,5,6,7列出目标函数和限制条件：公司的总花费为〔X1+X4+X5+X6+X7〕*200+〔X1+X2+X5+X6+X7)*200+〔X1+X2+X3+X6+X7〕*200+〔X1+X2+X3+X4+X7〕*200+〔X1+X2+X3+X4+X5〕*200+〔X2+X3+X4+X5+X6〕*200+〔X3+X4+X5+X6+X7〕*200；X1+X4+X5+X6+X7=18;X1+X2+X5+X6+X7=15;X1+X2+X3+X6+X7=12;X1+X2+X3+X4+X7=16;X1+X2+X3+X4+X5=19;X2+X3+X4+X5+X6=14;X3+X4+X5+X6+X7=12;X1>=0;X2>=0;X3>=0;X4>=0;X5>=0;X6>=0;X7>=0;列出Lingo程序：model:min=200*(x1+x4+x5+x6+x7)+200*(x1+x2+x5+x6+x7)+200*(x1+x2+x3+x6+x7)+(x1+x2+x3+x4+x7)*200+(x1+x2+x3+x4+x5)*200+(x2+x3+x4+x5+x6)*200+(x3+x4+x5+x6+x7)*200;x1+x4+x5+x6+x7=18;x1+x2+x5+x6+x7=15;x1+x2+x3+x6+x7=12;x1+x2+x3+x4+x7=16;x1+x2+x3+x4+x5=19;x2+x3+x4+x5+x6=14;x3+x4+x5+x6+x7=12;x1>=0;x2>=0;x3>=0;x4>=0;x5>=0;x6>=0;x7>=0;end分析结果:Globaloptimalsolutionfound.Totalsolveriterations:7VariableValueReducedCostRowSlackorSurplusDualPrice最低本钱为21200元,合理的安排应该是周一7人上班，周二3人，周三1人，周四6人，周五4人，周六2人周天1人这样可以把本钱降至最低.〔2〕设一周之内,工作大全职人员为Ai,兼职人员为Bi,i=1,2,3,4,5,6,7；列出Lingo程序:model:min=(A1+A4+A5+A6+A7)*8*25+(B1+B4+B5+B6+B7)*4*15+(A1+A2+A5+A6+A7)*8*25+(B1+B2+B5+B6+B7)*4*15+(A1+A2+A3+A6+A7)*8*25+(B1+B2+B3+B6+B7)*4*15+(A1+A2+A3+A4+A7)*8*25+(B1+B2+B3+B4+B7)*4*15+(A1+A2+A3+A4+A5)*8*25+(B1+B2+B3+B4+B5)*4*15+(A2+A3+A4+A5+A6)*8*25+(B2+B3+B4+B5+B6)*4*15+(A3+A4+A5+A6+A7)*8*25+(B3+B4+B5+B6+B7)*4*15;(A1+A4+A5+A6+A7)*8+(B1+B4+B5+B6+B7)*4=144;(A1+A2+A5+A6+A7)*8+(B1+B2+B5+B6+B7)*4=120;(A1+A2+A3+A6+A7)*8+(B1+B2+B3+B6+B7)*4=96;(A1+A2+A3+A4+A7)*8+(B1+B2+B3+B4+B7)*4=128;(A1+A2+A3+A4+A5)*8+(B1+B2+B3+B4+B5)*4=152;(A2+A3+A4+A5+A6)*8+(B2+B3+B4+B5+B6)*4=112;(A3+A4+A5+A6+A7)*8+(B3+B4+B5+B6+B7)*4=96;(B1+B4+B5+B6+B7)*4+(B1+B2+B5+B6+B7)*4+(B1+B2+B3+B6+B7)*4+(B1+B2+B3+B4+B7)*4+(B1+B2+B3+B4+B5)*4+(B2+B3+B4+B5+B6)*4+(B3+B4+B5+B6+B7)*4<=(144+120+96+128+152+112+96)*0.25;A1>=0;A2>=0;A3>=0;A4>=0;A5>=0;A6>=0;A7>=0;B1>=0;B2>=0;B3>=0;B4>=0;B5>=0;B6>=0;B7>=0;end分析所得到的结果:Globaloptimalsolutionfound.Totalsolveriterations:9VariableValueReducedCostRowSlackorSurplusDualPrice公司最小的花费为19080因此,容易得出公司应该安排如下:星期一:全职人员6人，兼职人员1人；星期二:全职人员0人，兼职人员5人；星期三:全职人员1人，兼职人员0人；星期四:全职人员6人，兼职人员0人；星期五:全职人员4人，兼职人员0人；星期六:全职人员0人，兼职人员3人；星期日:全职人员0人，兼职人员1人。6、经济均衡问题(1)(单一生产商与单一消费者)。只考虑生产商B和消费者Y情形下的市场清算价格和交易量，生产商B和消费者Y的数据如表所示：(2)(两个生产商与两消费者)。考虑生产商A、B和消费者X、Y.生产商A和消费者X之间的生产与需求关系如表所示，生产商B和消费者Y的数据如表所示，进一步假设，生产商B的国外的企业，每销售1吨产品需要付万元的关税。在这种情况下，市场的清算价格应该是多少？生产商A和生产商B分别生产多少？消费者X和消费者Y分别购置多少？〔题目自己补充了。。。〕解：设生产商A以1，2，3，4〔万元〕的单价售出的产品数量〔单位：t〕分别是A1,A2,A3,A4，消费者X以9，，3，〔万元〕的单价购置的产品数量〔单位：t〕分别是X1,X2,X3,X4；生产商B以2，4，6，8〔万元〕的单价售出的产品数量〔单位：t〕分别是B1,B2,B3,B4，消费者Y以15，8，5，3〔万元〕的单价购置的产品数量〔单位：t〕分别是Y1,Y2,Y3,Y4。假设AX和AY，BX和BY为两种供货途径的供货量。变量之间的关系参见示意图：生产商B生产商BB1,B2,B3,B4生产商AA1,A2,A3,A4消费者Y消费者YX1,X2,X3,X4消费者XX1,X2,X3,X4目标函数仍然是虚拟经销商的总利润，约束条件仍然是四类(供求平衡、供给限制、需求限制和非负限制)，不过这时应该注意供需平衡约束应该是包括示的决策变量之间的关系：AX+AY=A1+A2+A3+A4;BX+BY=B1+B2+B3+B4;AX+BX=X1+X2+X3+X4;AY+BY=Y1+Y2+Y3+Y4;此外的其它约束实际上只是一个简单的变量上界约束。下面直接给出LINGO程序：model:sets:num1/1..4/:c1,c2,c3,c4,d1,d2,A,B,X,Y;num2/1,2/:AXY,BXY;endsetsdata:c1=94.532.25;c2=15853;c3=1234;c4=2468;d1=1344;d2=1234;enddatamax=@sum(num1:c1*x+c2*y-c3*A-c4*B)-2*BXY(1)-1.5*AXY(2);@sum(num1:A)-@sum(num2:AXY)=0;@sum(num1:B)-@sum(num2:BXY)=0;AXY(1)+BXY(1)-@sum(num1:X)=0;AXY(2)+BXY(2)-@sum(num1:Y)=0;@for(num1:@bnd(0,A,2);@bnd(0,X,2);@bnd(0,B,d1);@bnd(0,Y,d2));End求解程序，得到如下结果Globaloptimalsolutionfoundatiteration:0VariableValueReducedCostRowSlackorSurplusDualPrice………………分析结果，可以看到，最优解为A1=A2=A3=X1=X2=2，B1=1，B2=3，Y1=1，Y2=3，Y3=3，AX=BY=4，AY=2，A4=B3=B4=X3=X4=Y4=BX=0。也就是说，生产商A将向消费者Y销售2t产品，生产商B不会向X销售。根据约束条件针即对生产商甲的供需平衡条件，目前的右端项为0，影子价格为－3，意思就是说如果右端项增加一个很少的量〔即生产商A的供给量增加一个很少的量〕，引起的中介损失就是这个小量的倍。可见，此时生产商A的销售单价就是3万元，这就是面对的清算价格。完全类似地，可以知道生产商B面对的清算价格为万元。自然地，消费者X面对的清算价格也是3，消费者Y面对的清算价格也是万元。7、投标问题某地区有5块土地A、B、C、D、E准备拍卖用于开发建设。现收到甲、乙、丙、丁四个投标人的标书，每个投标人对其中的假设干块土地都有购置的兴趣，分别以两个组合包的形式投标，投标价格如表所示，进一步假设，每个投标人最多只能购置其中一个组合包，如果政府希望最大化社会福利，这5块土地该如何出售？并计算其中的交易清算价格。解：设Xij为第几个人第几套方案i=1，2，3，4；j=1，2由土地要卖给不同的人，且没人最多只能购置其中一个组合包，由表的其中的组合将土地全卖完由3总情况：X11和X32;X21和X42;X12和x41建立目标函数：95X11+85X12+60X21+95X22+90X31+71X32+70X41+93X42编辑Lingo程序：model:max=95*X11+85*X12+60*X21+95*X22+90*X31+71*X32+70*X41+93*X42;X11-X32=0;X21-X42=0;X41-X12=0;X22=0;X31=0;X11+X32+X21+X42+X41+X12<2;End计算得到如下结果：Globaloptimalsolutionfound.Totalsolveriterations:0VariableValueReducedCostRowSlackorSurplusDualPrice分析可知，卖给甲第一方案和丙第二套方案可让利益最大收益166元。〔后有加分题〕加分实验〔人力资源方案问题〕为了降低经营本钱，某航空公司想要在本部订票效劳中心合理地安排工作人员，以对顾客提供方便的效劳。订票处每天的办公时间是从早7:00到晚22:00，有六个班组从7:00到9:30之间的每整点和半点开始上班，还有一个班从15:00开始上班。从7:00到8:01之间上班的班组工作8个小时，从8:30到9:31之间开始上班的班组工作小时.第七个班组从15:00开始，只工作7个小时。所有接线员有半个小时的休息时间，但是从8:30到9:31之间开始上班的人休息时间有一个小时.接线员工作三个小时以后才能休息，两个小时内每半个小时安排一次休息时间。这些上班时间和休息时间长度的安排，是为了能够对7：00到22:00一天时间内的工作小时进行“合理〞的分布。表是根据三个月以来订票业务情况的统计结果，它包括到达呼叫的分布和接线员接待顾客所花时间〔效劳时间〕的分布.公司的管理者认为得到的数据有以下特点：一天内不同时间的到达量显示出有很大变化,但不同日期之间是一致的效劳时间的分布根本上随时间平稳半个小时期间的到达分布近似于Poisson分布，虽然平均值不同〔见表3.8).效劳时间分布近似于平均值为分钟的指数分布.公司希望：计算出每个时段需要的接线员数，以便并进行合理的排班〔包括接线员的上下班时间，以及中间的休息时间〕，以便在满足需求的情况下使用较少的员工，来减少运营本钱。考虑到每天需求的变化是非常必要的，特别是顶峰业务时段，如果对效劳的等待时间过长可能会导致了顾客的抱怨，并失去了一些业务。因此，为了保证不丧失呼叫〔以及信誉损失〕，一个接线员答复一次呼叫前的等待时间应该充分短.公司管理部门设定的目标是至少90%的呼叫应该在20秒之内得到回应。公司更关心在这一目标下，每个时段需要的员工数和排班方法，即可以使接线员数与顾客需求之间到达某种平衡，又可以做到使雇用的员工尽可能的少，来降低运营本钱。解：1、模型提出：首先可以肯定的把该话务员调度问题看作是一个排队问题，其根本数学模型采用M/M/S等待制排队模型中的(M/M/S/∞/∞/FCFS)模型进行模拟。我们要解决的问题首先是对人员数目的计算，用最少的人来满足接通率的要求；其次是将这些人员排入班表，并且按照实际的限制要求进行调整，并且输出完整的班表供人员调度的需要。假设如下：假设银行顾客随机到达，并近似服从一个指数分布；假设在多窗口排多个队伍的方式下，每个顾客到达后选择一个窗口排队，排队后坚持不变；假设因为对效劳台来讲，每个需要效劳的人都可以认为是一样的，故总体上谁先打进就先效劳；假设顾客对各效劳人员没有选择权；假设每位顾客所需效劳时间大致相同；假设每位顾客的等待时间为20秒；2、解题思路：假定每个用户的“呼入〞是相互独立的,那么在时间[t1,t2]内“呼入量〞与用户量成正比,与t2-t1成正比,于是在单位时间内,单个用户的“呼入率〞q为:[t1,t2]内的“呼入量〞/{用户量×(t1-t2)}。根据所采集的数据做出每天的“呼入率〞的变化曲线,采用逐步逼近的方法的,在全部曲线之中找出最能代表一般规律的q曲线。其次，用多项式函数对该曲线进行分段拟合，采用最小二乘法求得多项式函数的系数，从而得到分段多项式函数q=f(t)，即可近似作为原数据曲线的解析表达式。记:ρ=λ/μ,其中:λ为顾客到达率,即单位时间内的“呼入量〞；μ为效劳率,即单位时间内每个效劳台可以效劳完的顾客数。由Erlang等待公式：在效劳系统要求顾客满足程度不低于90%(即c<0.1)条件下,研究采用多少效劳台。即在不能按时得到效劳的概率不超过10%的条件下,各时间段应最少排效劳员多少名。根据题意将每天分为30个平均时段，设在t时刻的用户量、“呼入量〞分别为x(t),y(t),假设在一天之内用户量不变x(t)=X，那么在(t1,t2)时段内到达顾客数为：又其中:T为平均通话时间,那么其中的为30个常数，显然ρ与用量X和时段n有关，至此，在给定用户量和时段的情况下，可由Erlang等待公式和题设条件确定最优的效劳台数s,即效劳员人数。3、数学模拟首先，对原始数据进行拟合，计算出可以打进数目的解析表达式。采用多项式函数进行拟合，并通过求解最小二乘法中的正规方程组，得到多项式的各项系数。从1次多项开始试探，逐渐加高次数等直到得到一个误差范围内允许的曲线。1次多项式拟合：LinearmodelPoly1:f(x)=p1*x+p2Coefficients(with95%confidencebounds):p1=-0.2994(-0.5323,-0.06658)p2=16.84(12.71,20.98)偏差太大，跳过2次，直接进行3次拟合：LinearmodelPoly3:f(x)=p1*x^3+p2*x^2+p3*x+p4Coefficients(with95%confidencebounds):p1=0.004625(0.003054,0.006195)p2=-0.278(-0.352,-0.204)p3=4.363(3.367,5.358)p4=-1.137(-4.76,2.486)4次多项式拟合：LinearmodelPoly4:f(x)=p1*x^4+p2*x^3+p3*x^2+p4*x+p5Coefficients(with95%confidencebounds):p1=9.104e-005(-0.0001198,0.0003019)p2=-0.00102(-0.01419,0.01215)p3=-0.1642(-0.4381,0.1096)p4=3.548(1.413,5.684)p5=0.3102(-4.642,5.263)5次多项式拟合：LinearmodelPoly5:f(x)=p1*x^5+p2*x^4+p3*x^3+p4*x^2+p5*x+p6Coefficients(with95%confidencebounds):p1=-4.956e-005(-6.972e-005,-2.941e-005)p2=0.003932(0.002363,0.005501)p3=-0.1078(-0.1522,-0.06339)p4=1.11(0.5565,1.663)p5=-2.482(-5.365,0.4011)p6=7.972(3.274,12.67)此时偏差已经下降到适宜的范围内，那么跳过6次，直接使用7次多项式的拟合结果作为呼入率的解析表达式：Linearmode