数学模型数学建模第四次作业整数规划和对策论模型

数学模型第四次作业整数规划和对策论模型4.1实验目的学会建立整数规划模型、对策论模型，学会用lingo软件求解。4.2基本实验工程安排问题三年内有五项工程可以考虑施工，每项工程的期望收入和年度费用如表4.1所示。假定每一项已经选定的工程要在整个三年内完成。目标是要选出使总收入达到最大的那些工程。表4」每项工程的期望收入和年度费用表（单位；千元）费用第一年 第［年 第三年收入费用第一年 第［年 第三年收入1518202410403392204741155861030可用基金252525工程第i个工程未被选中第i个工程被选中解：根据题意，设X=€°i1，i=1,2,3,4,5目标函数为：目标函数为：Max=20x„40x„20x„15x„30xTOC\o"1-5"\h\z1 2 3 4 5限制条件为：€5x„4x„3x„7x„8x…251 2 3 4 5x+7x+9x+4x+6x…25s.t.,1 2 3 4 58x+10x+2x+x+10x…251 2 3 4 5x为0或1J•i使用Lingo编程：model:max=20*x1+40*x2+20*x3+15*x4+30*x5;5*x1+4*x2+3*x3+7*x4+8*x5<=25;1*x1+7*x2+9*x3+4*x4+6*x5<=25;8*x1+10*x2+1*x3+2*x4+10*x5<=25;@bin(x1);@bin(x2);@bin(x3);@bin(x4);@bin(x5);end运行得到结果：Globaloptimalsolutionfound.Objectivevalue: 95.00000Objectivebound: 95.00000Infeasibilities: 0.000000Extendedsolversteps: 0Totalsolveriterations: 0VariableValueReducedCostX11.000000-20.00000X21.000000-40.00000X31.000000-20.00000X41.000000-15.00000X50.000000-30.00000RowSlackorSurplusDualPrice195.000001.00000026.0000000.00000034.0000000.00000044.0000000.000000分析结果易知，总收入达到最大为95（千元），应选第一、二、三、四项工程可以使总收入达到最大。固定费用问题一服装厂生产三种服装，生产不同种类的服装要租用不同的设备，设备租金和其他的经济参数如表4.2所示。假定市场需求不成问题，服装厂每月可用人工工时为2000小时，该厂如何安排生产可以使每月利润达到最大？表4.2服装厂设备租金和其他的经济参数装类服沖设备租金（元）生产成本（元/件）销售价格（元/件）人工工时（小时/件）设备工时（小时/件）设备可用工时西服500028040053300衬衫2000304010.5300羽绒服300020030042300解：根据题意三种服装的利润分别为120元、10元、100元.设xi表示生成第i（i=l,2,3）种服装的数量，，•表示是否生产第i种服装。=J1,生产第i种服装yi=[o,不生产第i种服装列出目标函数：max=120x+10x+100x一（5000y一2000y一3000y）1 2 3 1 2 3列出限制条件：5X]+x2+4x3S20003x1<300y10.5x2<300y22x3<300y3使用Lingo编程求解model:sets:m/1,2,3/:x,y;endsets[obj]max=100*x(1)+10*x(2)+100*x(3)-5000*y(1)-2000*y(2)-3000*y(3);5*x(1)+x(2)+4*x(3)<=2000;3*x(1)<=300*y(1);0.5*x(2)<=300*y(2);2*x(3)<=300*y(3);@for(m(i):x(i)>=0;@bin(y(i)););end得到结果：Globaloptimalsolutionfound.Objectivevalue: 21000.00Objectivebound: 21000.00Infeasibilities: 0.000000Extendedsolversteps: 0Totalsolveriterations: 0VariableValueReducedCostX(1)100.00000.000000X(2)600.00000.000000X(3)150.00000.000000Y(1)1.000000-5000.000Y(2)1.000000-4000.000Y(3)1.000000-12000.00RowSlackorSurplusDualPriceOBJ21000.001.0000002300.00000.00000030.00000033.3333340.00000020.0000050.00000050.000006100.00000.0000007600.00000.0000008150.00000.000000所以三种服装应该都生产，且生产西服100件、衬衫600件、羽绒服150件时可以使每月利润达到最大21000元。串并联系统可靠性问题有一台电器由三个部件组成，这三个部件串联，假如有一个部件发生故障，电器就不能工作。可以通过在每个部件里安装1到2个备份元件来提高该电器的可靠性（不发生故障的概率）。表4.3列出了可靠性和成本费用。假设制造该电器的已有资金共10万元，那么怎样来构造这件电器呢？表4.3每种元件的可靠性及成本费用（单位；万元）并联元件数部件1部件2部件3可靠性费用可靠性费用可靠性费用10.610.730.5220.820.850.7430.930.960.95解：构造集合bujian/1..3/(部件)，yuanjian/1..2/(每个部件可并联的元件数集合)，links(bujian,yuanjian):p,C,R。其中 =,1,给i部件并联个元件八耳二€。，其他列出Lingo程序：model:sets:bujian/1..3/;!部件1,2,3;yuanjian/1..2/;!每个部件可装元件1,2;links(bujian,yuanjian)/1,11,22,12,23,13,2/:p,C,R;!p(i,j)=1,贝V表示部件i上并联j个元件，否则，p(i,j)=0.C,R分别为成本，可靠性；!links中的元素必须罗列出来;endsetsdata:C=123524;R=0.600.800.700.800.500.70;enddata

max=@prod(bujian(I):@sum(yuanjian(J)|@in(links,I,J):p(I,J)*R(I,J)));!整个系统的可靠性,为每个部件的可靠性之积;@for(bujian(I):@sum(yuanjian(J)|@in(links,I,J):p(I,J))=1);@for(links(I,J)|@in(links,I,J):@bin(p(I,J)));!对于每一个部件，并联的元件数是一定的，p(I,J)只能取0或1,且p(I,J)的和为1；@sum(bujian(I):@sum(yuanjian(J)|@in(links,I,J):p(I,J)*C(I,J)))<=10; !总成本小于10(万元);end运行得到如下结果：Linearizationcomponentsadded:TOC\o"1-5"\h\zConstraints: 64Variables: 16Integers: 16Globaloptimalsolutionfound.0.39200000.39200000.39200000.39200000.000000012Objectivebound:Infeasibilities:Extendedsolversteps:Totalsolveriterations:VariableValueReducedCostP(1,1)0.0000000.000000P(1,2)1.0000000.000000P(2,1)1.0000000.000000P(2,2)0.0000000.000000P(3,1)0.0000000.000000P(3,2)1.0000000.000000C(1,1)1.0000000.000000C(1,2)2.0000000.000000C(2,1)3.0000000.000000C(2,2)5.0000000.000000C(3,1)2.0000000.000000C(3,2)4.0000000.000000R(1,1)0.60000000.000000R(1,2)0.80000000.000000R(2,1)0.70000000.000000R(2,2)0.80000000.000000R(3,1)0.50000000.000000R(3,2)0.70000000.000000RowSlackorSurplusDualPrice10.39200001.00000020.0000000.00000030.0000000.00000040.0000000.00000051.0000000.000000因此，此时的最优解可以得到：即在第一个部件上并联两个元件，第二个部件上并联一个元件，第三个部件上并联两个元件，此时系统的在成本允许的情况下稳定性达到最大0.392。二选一约束条件某汽车公司正在考虑生产3种类型的汽车：微型、中型和大型。表4.4给出了每种汽车需要的资源及产生的利润。目前有6000吨钢材和60000小时的劳动时间。要生产一种在经济效益上可行的汽车，这种汽车必须至少生产1000辆。试为该公司制定一个使生产利润达到最大的方案。表442种汽车的资源和利润资源汽车的类型微型中也大型所需钢材（吨）1.535所需劳动时间（小时）302540产生的利润（美元）200030004000解：设X1、X2、X3分别表示生产微型汽车、中型汽车、大型汽车的数量。引入0-1变量，化为整数规划。设yi只取0,1两个值，则生产1000辆或不生产用数学表达为：xi€1000yiye{0,1},i€1,2,3iy€„人生产该车型 0-1变量,0, 不生产该车型目标函数：max=2000*x1+3000*x2+4000*x3;限制条件：1.5*x1+3*x2+5*x3<=6000;30*x1+25*x2+40*x3<=60000;x1<=5000*y1;（取个合理范围）x1>=1000*y1;x2<=5000*y2;x2>=1000*y2;x3<=5000*y3;x3>=1000*y3;x1,x2,x3为整数；用Lingo编程求解：model:max=2000*x1+3000*x2+4000*x3;1.5*x1+3*x2+5*x3<=6000;30*x1+25*x2+40*x3<=60000;x1<=5000*y1;x1>=1000*y1;x2<=5000*y2;x2>=1000*y2;x3<=5000*y3;x3>=1000*y3;@bin(y1);@bin(y2);@bin(y3);@gin(x1);@gin(x2);@gin(x3);End运行得到结果：Objectivevalue:6000000.Objectivebound:6000000.Infeasibilities:0.000000Extendedsolversteps:1Totalsolveriterations:8VariableValueReducedCostX10.000000-2000.000X22000.000-3000.000X30.000000-4000.000Y10.0000000.000000Y21.0000000.000000Y30.0000000.000000RowSlackorSurplusDualPrice16000000.1.00000020.0000000.000000310000.000.00000040.0000000.00000050.0000000.00000063000.0000.00000071000.0000.00000080.0000000.00000090.0000000.000000易知生产中型车2000辆可以使生产利润达到最大为6000000美元。最小覆盖问题某市管辖6个区（区1〜区6）.这个市必须明确在什么地方修建消防站，在保证至少有一个消防站在每个区的15分钟（行驶时间）路程内的情况下，这个市希望修建的消防站最少。表4.5给出了该市各个区之间行驶需要的时间（单位为分钟）。这个市需要多少个消防站，以及它们所在的位置。表4.5该市各个区之间行驶需要的时间（单位；分钟）123区4区56101020303020[X210025352010320250153020区430351501525区530203015014620102025140解：根据题意，设x表示是否在某区建消防站，c表示两区之间是否15分钟内可以到达，使用Lingo编程：model:sets:area/1..6/:x;link(area,area):t,c;endsetsdata:t=***********1002535201020250153020

303515015253020301501420102025140;enddatacalc:@for(link:c=@if(t#le#15,1,0));endcalcmin=@sum(area:x);@for(area:@bin(x));@for(area(i):@sum(area(j):c(i,j)*x*(i))>=1);End因此，若要修建消防站最少，只需在区2因此，若要修建消防站最少，只需在区2、区4建立消防站就可以。解得如下结果：Globaloptimalsolutionfound.Objectivevalue:2.000000Objectivebound:2.000000Infeasibilities:0.000000Extendedsolversteps:0Totalsolveriterations:0VariableValueReducedCostX(1)0.0000001.000000X(2)1.0000001.000000X(3)0.0000001.000000X(4)1.0000001.000000X(5)0.0000001.000000X(6)0.0000001.0000006.对策问题1在一次野餐会上，两个二人组在玩捉迷藏游戏。共有四个隐藏地点（A、B、C和D）,隐藏组的两个成员可以分别藏在四个地点的任何两个,搜寻组人有机会寻找任何两个地点。如果他们都找到了隐藏组的二个人,搜寻组就可以得到一分奖励,假如两个人都没找到,他们就输一分。其它情况下,结果是平局。将这个问题表示成一个二人零和对策,求出搜寻组最优搜寻策略和它们的赢得值。解：设此题目局中人为甲乙两组列出支付函数：乙组（隐藏组）甲组（寻找组）ABACADBCBDCDAB10000-1AC0100-10AD001-100BC00-1100BD0-10010CD-100001因为每行或列得分的和均为0,即局中人得失总和为零,所以该对策为二人零和对策。MODEL:sets:playerA/1..6/:x;playerB/1..6/;

game(playerA,playerB):C;endsetsdata:C=1000010100-10001-10000-11000-10010-100001enddatamax=v_A;@free(v_A);@for(playerB(j):@sum(playerA(i):C(i,j)*x(i))>=v_A);@sum(playerA:x)=1;end得到结果：0.0000000.0000000.0000000.0000005Objectivevalue:Infeasibilities:Totalsolveriterations:VariableValueReducedCostV_A0.0000000.000000X(1)0.50000000.000000X(2)0.0000000.000000X(3)0.0000000.000000X(4)0.0000000.000000X(5)0.0000000.000000X(6)0.50000000.000000因此推出，若搜索组采用50%的概率派出队员去搜索AB和CD的策略，可以得到的赢得值为0。7.对策问题2甲手中有两张牌，各为1点和4点；乙手中有两张牌，各为2点和3点。两人同时各出一张牌，并依据两人所出牌的点数之和来决定各自的收益当点数和为偶数时，甲赢得为两张牌的点数和，乙羸得两张牌的点数差；当点数和为奇数时，甲赢得为两张牌的点数差，乙羸得两张牌的点数和。求甲乙二人各自的最优策略和各自的羸得值。解：根据题意列出支付函数乙23甲1(1,4)(4,2)4(6,2)(1,7)该题为一个典型的二人非常数和对策，每人的收益矩阵是不相同的为双矩阵对策。利用Lingo软件求解：MODEL:sets:optA/1..2/:x;optB/1..2/:y;AXB(optA,optB):Ca,Cb;endsetsdata:Ca=1461;Cb=4227;enddataVa=@sum(AXB(i,j):Ca(i,j)*x(i)*y(j));Vb=@sum(AXB(i,j):Cb(i,j)*x(i)*y(j));@for(optA(i):@sum(optB(j):Ca(i,j)*y(j))<=Va);

@for(optB(j):@sum(optA(i):Cb(i,j)*x(i))<=Vb);@sum(optA:x)=1;@sum(optB:y)=1;@free(Va);@free(Vb);End求得结果：0.2622347E-1220Infeasibilities:0.2622347E-1220Totalsolveriterations:VA2.875000VB3.428571X(1)0.7142857X(2)0.2857143Y(1)0.3750000Y(2)0.6250000CA(1,1)1.000000CA(1,2)4.000000CA(2,1)6.000000CA(2,2)1.000000CB(1,1)4.000000CB(1,2)2.000000CB(2,1)2.000000CB(2,2)7.000000VariableValue计算得到混合对策的平衡点为(5/7,2/7),(3/8,5/8)，此时的各自的赢得值为2.875和3.428571。4.3加分实验(乒乓球团体赛上场队员排序问题)乒乓球团体赛的比赛规则如下：从一个队中挑选出的三名比赛队员和一个队长（可由参赛队员兼任，亦可由其他人员专任）组成。比赛之前，双方队长应抽签决定A、B、C和X、Y、Z的选择，并向裁判提交每个运动员分配到一个字母的队伍名单。现行的比赛顺序：第一场A—X，第二场B—Y，第三场C—Z，第四场A—Y，第五场B—X。每场比赛为三局两胜制。当一个队已经赢得三场个人比赛时，该次比赛应结束。现有甲队挑选出的三名比赛队员分别是：Al、A2、A3，乙队挑选出的三名比赛队员分别是：Bl、B2、B3，根据以往的历史资料，甲队与乙队比赛，甲队运动员在每一局中获胜的概率如表B.1所示。甲队教练将如何安排上场运动员的次序，使得本队获胜的概率最大。建立相应的数学模型，并说明你的理由。如果每一局比赛,A1胜B3的概率改为0.45,A3胜B1的概率改为0.55。在这种情况下，甲队教练将如何调整甲队队员的上场次序？表丄6两队比赛，甲队运动员在每一局中获胜的概率队员3民b3百10.500.550.600.450.500.550.400.450.50解：分析此问题，属于运筹学排序问题推理建立模型如下：这是一个排列问题，用1ingo软件，目标函数：max=@sum(shunxu:p*x);设x(i,j)为0,1变量，X为一个3*3的0,1矩阵，x(i,j)表示第i同学是否在第j同学前面，p为A选手胜B选手的概率=0.500.550.600.450.500.550.400.450.50;约束条件：选手比赛的前后顺序；每阶段只有一名选手比赛。列出Lingo程序：model:sets:aa/1..3/:a;bb/1..3/:b;cc/1..6/:c;ps/1..5/;psc(ps,cc):p;para(aa,bb):p1,p2,p3,p4,p5,p6,x;pp(aa,bb,cc):pb,ppb;endsetsdata:!xyz;p1=0.50.550.600.450.500.550.400.450.50;!yxz;p2=0.550.600.50.500.550.450.450.500.40;!z,x,y;p3=0.600.500.550.550.450.500.500.400.45;!x,z,y;p4=0.500.600.550.450.550.500.400.500.45;!y,z,x;p5=0.550.600.500.500.550.450.450500.40;!z,y,x;p6=0.600.550.500.550.500.450.500.450.40;enddata!yueshu;calc:@for(pp(i,j,k):pb(i,j,1)=p1(i,j));@for(pp(i,j,k):pb(i,j,2)=p2(i,j));@for(pp(i,j,k):pb(i,j,3)=p3(i,j));@for(pp(i,j,k):pb(i,j,4)=p4(i,j));@for(pp(i,j,k):pb(i,j,5)=p5(i,j));@for(pp(i,j,k):pb(i,j,6)=p6(i,j));endcalc@for(bb(j):@sum(aa(i):x(i,j))=1);@for(aa(i):@sum(bb(j):x(i,j))=1);@for(para:@bin(x));@for(pp(i,j,k):ppb(i,j,k)=x(i,j)*pb(i,j,k));@for(psc(i,j):p(i,j)=@sum(pp(i,k,j):ppb(i,k,j)));@for(cc(j):c(j)=p(1,j)*p(2,j)*p(3,j)+p(1,j)*p(2,j)*(1-p(3,j))*p(4,j)*(1-p(5,j))+p(1,j)*p(2,j)*(1-p(3,j))*(1-p(4,j))*p(5,j)+p(1,j)*(1-p(2,j))*p(3,j)*p(4,j)*(1-p(5,j))+p(1,j)*(1-p(2,j))*p(3,j)*(1-p(4,j))*p(5,j)+p(1,j)*(1-p(2,j))*(1-p(3,j))*p(4,j)*p(5,j)+(1-p(1,j))*p(2,j)*p(3,j)*p(4,j)+(1-p(1,j))*p(2,j)*p(3,j)*(1-p(4,j))*p(5,j)+(1-p(1,j))*p(2,j)*(1-p(3,j))*p(4,j)*p(5,j)+(1-p(1,j))*(1-p(2,j))*p(3,j)*p(4,j)*p(5,j));

!@for(cc(i):@free(c));p_sum=@sum(cc(i):c);max=p_sum;end计算得到结果如下：Localoptimalsolutionfound.13.1150013.1150013.1150013.115000.6522560E-15263Objectivebound:Infeasibilities:Extendedsolversteps:Totalsolveriterations:VariableValueReducedCostP_SUM13.115000.000000A(1)0.0000000.000000A(2)0.0000000.000000A(3)0.0000000.000000B(1)0.0000000.000000B(2)0.0000000.000000B(3)0.0000000.000000C(1)0.12150000.000000C(2)0.12500000.000000C(3)0.12100000.000000C(4)0.12375000.000000C(5)12.500000.000000C(6)0.12375000.000000P(1,1)0.60000000.000000P(1,2)0.50000000.000000P(1,3)0.55000000.000000P(1,4)0.55000000.000000P(1,5)0.50000000.000000P(1,6)0.50000000.000000P(2,1)0.45000000.000000P(2,2)0.50000000.000000P(2,3)0.55000000.000000P(2,4)0.45000000.000000P(2,5)0.50000000.000000P(2,6)0.55000000.000000P(3,1)0.45000000.000000P(3,2)0.50000000.000000

P(3,3)0.40000000.000000P(3,4)0.50000000.000000P(3,5)50.000000.000000P(3,6)0.45000000.000000P(4,1)0.0000000.000000P(4,2)0.0000000.000000P(4,3)0.0000000.000000P(4,4)0.0000000.000000P(4,5)0.0000000.000000P(4,6)0.0000000.000000P(5,1)0.0000000.000000P(5,2)0.0000000.000000P(5,3)0.0000000.000000P(5,4)0.0000000.000000P(5,5)0.0000000.000000P(5,6)0.0000000.000000P1(1,1)0.50000000.000000P1(1,2)0.55000000.000000P1(1,3)0.60000000.000000P1(2,1)0.45000000.000000P1(2,2)0.50000000.000000P1(2,3)0.55000000.000000P1(3,1)0.40000000.000000P1(3,2)0.45000000.000000P1(3,3)0.50000000.000000P2(1,1)0.55000000.000000P2(1,2)0.60000000.000000P2(1,3)0.50000000.000000P2(2,1)0.50000000.000000P2(2,2)0.55000000.000000P2(2,3)0.45000000.000000P2(3,1)0.45000000.000000P2(3,2)0.50000000.000000P2(3,3)0.40000000.000000P3(1,1)0.60000000.000000P3(1,2)0.50000000.000000P3(1,3)0.55000000.000000P3(2,1)0.55000000.000000P3(2,2)0.45000000.000000P3(2,3)0.50000000.000000P3(3,1)0.50000000.000000P3(3,2)0.40000000.000000P3(3,3)0.45000000.000000P4(1,1)0.50000000.000000P4(1,2)0.60000000.000000P4(1,3)0.55000000.000000P4(2,1)0.45000000.000000P4(2,2)0.55000000.000000P4(2,3)0.50000000.000000P4(3,1)0.40000000.000000P4(3,2)0.50000000.000000P4(3,3)0.45000000.000000P5(1,1)0.55000000.000000P5(1,2)0.60000000.000000P5(1,3)0.50000000.000000P5(2,1)0.50000000.000000P5(2,2)0.55000000.000000P5(2,3)0.45000000.000000P5(3,1)0.45000000.000000P5(3,2)50.000000.000000P5(3,3)0.40000000.000000P6(1,1)0.60000000.000000P6(1,2)0.55000000.000000P6(1,3)0.50000000.000000P6(2,1)0.55000000.000000P6(2,2)0.50000000.000000P6(2,3)0.45000000.000000P6(3,1)0.50000000.000000P6(3,2)0.45000000.000000P6(3,3)0.40000000.000000X(1,1)0.0000000.000000X(1,2)0.0000000.000000X(1,3)1.0000000.000000X(2,1)1.0000000.1149973E-01X(2,2)0.0000000.000000X(2,3)0.0000000.000000X(3,1)0.0000001.238500X(3,2)1.0000000.000000X(3,3)0.0000000.000000PB(1,1,1)0.50000000.000000PB(1,1,2)0.55000000.000000PB(1,1,3)0.60000000.000000PB(1,1,4)0.50000000.000000PB(1,1,5)0.55000000.000000PB(1,1,6)0.60000000.000000PB(1,2,1)0.55000000.000000PB(1,2,2)0.60000000.000000PB(1,2,3)0.50000000.000000

PB(1,2,4)0.60000000.000000PB(1,2,5)0.60000000.000000PB(1,2,6)0.55000000.000000PB(1,3,1)0.60000000.000000PB(1,3,2)0.50000000.000000PB(1,3,3)0.55000000.000000PB(1,3,4)0.55000000.000000PB(1,3,5)0.50000000.000000PB(1,3,6)0.50000000.000000PB(2,1,1)0.45000000.000000PB(2,1,2)0.50000000.000000PB(2,1,3)0.55000000.000000PB(2,1,4)0.45000000.000000PB(2,1,5)0.50000000.000000PB(2,1,6)0.55000000.000000PB(2,2,1)0.50000000.000000PB(2,2,2)0.55000000.000000PB(2,2,3)0.45000000.000000PB(2,2,4)0.55000000.000000PB(2,2,5)0.55000000.000000PB(2,2,6)0.50000000.000000PB(2,3,1)0.55000000.000000PB(2,3,2)0.45000000.000000PB(2,3,3)0.50000000.000000PB(2,3,4)0.50000000.000000PB(2,3,5)0.45000000.000000PB(2,3,6)0.45000000.000000PB(3,1,1)0.40000000.000000PB(3,1,2)0.45000000.000000PB(3,1,3)0.50000000.000000PB(3,1,4)0.40000000.000000PB(3,1,5)0.45000000.000000PB(3,1,6)0.50000000.000000PB(3,2,1)0.45000000.000000PB(3,2,2)0.50000000.000000PB(3,2,3)0.40000000.000000PB(3,2,4)0.50000000.000000PB(3,2,5)50.000000.000000PB(3,2,6)0.45000000.000000PB(3,3,1)0.50000000.000000PB(3,3,2)0.40000000.000000PB(3,3,3)0.45000000.000000PB(3,3