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

数学模型第四次作业 整数规划和对策论模型学会建立整数规划模型、对策论模型，学会用LINGO软件求解。4.2 根本实验1. 工程安排问题。假定每一项已经选定的工程要在整个三年内完成。目标是要选出使总收入达到最大的那些工程。解：根据题意，设，i=1,2,3,4,5目标函数为：限制条件为：使用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运行得到结果： Global optimal solution found. Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost Row Slack or Surplus Dual Price分析结果易知，总收入达到最大为95千元，应选第一、二、三、四项工程可以使总收入达到最大。2. 固定费用问题一服装厂生产三种服装，生产不同种类的服装要租用不同的设备，设备租金和其他的经济参数如表4.2所示。假定市场需求不成问题，服装厂每月可用人工工时为2000小时，该厂如何安排生产可以使每月利润达到最大？解：根据题意三种服装的利润分别为120元、10元、100元.设xi表示生成第i(i=1,2,3)种服装的数量，yi表示是否生产第i种服装。列出目标函数：列出限制条件：5x1+x2+4x320003x1300y1x2300y22x3300y3使用Lingo 编程求解：model:sets:m/1,2,3/:x,y;endsetsobjmax=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得到结果：Global optimal solution found. Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost Row Slack or Surplus Dual Price所以三种服装应该都生产，且生产西服100件、衬衫600件、羽绒服150件时可以使每月利润达到最大21000元。3. 串并联系统可靠性问题有一台电器由三个部件组成，这三个部件串联，假设有一个部件发生故障，电器就不能工作。可以通过在每个部件里安装1到2个备份元件来提高该电器的可靠性不发生故障的概率。表4.3列出了可靠性和本钱费用。假设制造该电器的已有资金共10万元，那么怎样来构造这件电器呢？解：构造集合bujian/1.3/部件，yuanjian/1.2/每个部件可并联的元件数集合，links(bujian,yuanjian):p,C,R。其中列出Lingo程序：model:sets:bujian/1.3/; !部件1,2,3;yuanjian/1.2/; !每个部件可装元件1,2;links(bujian,yuanjian)/1,1 1,2 2,1 2,2 3,1 3,2/:p,C,R;!p(i,j)=1，如此表示部件i上并联j个元件，否如此，p(i,j)=0.C,R分别为本钱，可靠性;!links中的元素必须罗列出来;endsetsdata:C=12352 4; 0.50 0.70;enddatamax=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运行得到如下结果：Linearization ponents added: Constraints: 64 Variables: 16 Integers: 16 Global optimal solution found. Extended solver steps: 0 Total solver iterations: 12 Variable Value Reduced Cost Row Slack or Surplus Dual Price因此，此时的最优解可以得到：即在第一个部件上并联两个元件，第二个部件上并联一个元件，第三个部件上并联两个元件，此时系统的在本钱允许的情况下稳定性达到最大0.392。4. 二选一约束条件某汽车公司正在考虑生产3种类型的汽车：微型、中型和大型。表4.4给出了每种汽车需要的资源与产生的利润。目前有6000吨钢材和60000小时的劳动时间。要生产一种在经济效益上可行的汽车，这种汽车必须至少生产1000辆。试为该公司制定一个使生产利润达到最大的方案。解：设X1、X2、X3分别表示生产微型汽车、中型汽车、大型汽车的数量。引入0-1变量，化为整数规划。设yi只取0,1两个值，如此生产1000辆或不生产用数学表达为：目标函数：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; 取个合理X围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运行得到结果：Objective value: 6000000. Objective bound: 6000000. Extended solver steps: 1 Total solver iterations: 8 Variable Value Reduced Cost Row Slack or Surplus Dual Price易知生产中型车2000辆可以使生产利润达到最大为6000000美元。某市管辖6个区区1区6).这个市必须明确在什么地方修建消防站，在保证至少有一个消防站在每个区的15分钟行驶时间路程内的情况下，这个市希望修建的消防站最少。表4.5给出了该市各个区之间行驶需要的时间单位为分钟。这个市需要多少个消防站，以与它们所在的位置。解：根据题意，设x表示是否在某区建消防站，c表示两区之间是否15分钟内可以到达，使用Lingo编程：model:sets:area/1.6/:x;link(area,area):t,c;endsetsdata:t=0 10 203030 2010 0 25 3520 1020 250 1530 2030 35 150 15 25302030 15 0 1420 10 20 25 14 0;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解得如下结果：Global optimal solution found. Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost因此，假设要修建消防站最少，只需在区2、区4建立消防站就可以。6. 对策问题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 = 1 0 0 0 0 -10 1 0 0 -1 00 0 1 -1 0 00 0 -1 1 0 00 -1 0 0 1 0-1 0 0 0 0 1;enddatamax=v_A;free(v_A);for(playerB(j):sum(playerA(i) : C(i,j)*x(i)>=v_A);sum(playerA : x)=1;end得到结果：Global optimal solution found. Total solver iterations: 5 Variable Value Reduced Cost因此推出，假设搜索组采用50%的概率派出队员去搜索AB和CD的策略，可以得到的赢得值为0。7. 对策问题2甲手中有两X牌，各为1点和4点；乙手中有两X牌，各为2点和3点。两人同时各出一X牌，并依据两人所出牌的点数之和来决定各自的收益当点数和为偶数时，甲赢得为两X牌的点数和，乙羸得两X牌的点数差；当点数和为奇数时，甲赢得为两X牌的点数差，乙羸得两X牌的点数和。求甲乙二人各自的最优策略和各自的羸得值。解：根据题意列出支付函数：乙23甲11，44，246，21，7该题为一个典型的二人非常数和对策，每人的收益矩阵是不一样的，为双矩阵对策。利用Lingo软件求解：MODEL:sets:optA/1.2/: x;optB/1.2/: y;AXB(optA,optB) : Ca, Cb;endsetsdata:Ca= 1 4 6 1;Cb=4 22 7;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求得结果： Total solver iterations: 20 Variable Value计算得到混合对策的平衡点为(5/7, 2/7),(3/8, 5/8)，此时的各自的赢得值为2.875和3.428571。4.3 加分实验乒乓球团体赛上场队员排序问题乒乓球团体赛的比赛规如此如下：从一个队中挑选出的三名比赛队员和一个队长可由参赛队员兼任，亦可由其他人员专任组成。比赛之前，双方队长应抽签决定A、B、C和X、Y、Z的选择，并向裁判提交每个运动员分配到一个字母的队伍。现行的比赛顺序：第一场AX，第二场BY，第三场 CZ，第四场 AY，第五场 BX。每场比赛为三局两胜制。当一个队已经赢得三场个人比赛时，该次比赛应完毕。现有甲队挑选出的三名比赛队员分别是：A1、A2、A3，乙队挑选出的三名比赛队员分别是：B1、B2、B3，根据以往的历史资料，甲队与乙队比赛，甲队运动员在每一局中获胜的概率如表B.1所示。1. 甲队教练将如何安排上场运动员的次序，使得本队获胜的概率最大。建立相应的数学模型，并说明你的理由。2. 如果每一局比赛，A1胜B3的概率改为0.45，A3胜B1的概率改为0.55。在这种情况下，甲队教练将如何调整甲队队员的上场次序？解：分析此问题，属于运筹学排序问题。推理建立模型如下：这是一个排列问题，用lingo软件，目标函数：max=sum(shunxu:p*x);设x(i,j)为0，1变量，x为一个3*3的0，1矩阵，x(i,j)表示第i同学是否在第j同学前面，p为A选手胜B选手的概率=0.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:!x y z;0.40 0.45 0.50;!y x z;0.50 0.55 0.45 0.45 0.50 0.40 ;!z,x,y;0.50 0.40 0.45 ;!x,z,y;0.40 0.50 0.45;!y,z,x;0.45 050 0.40;!z,y,x;0.50 0.45 0.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);endcalcfor(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计算得到结果如下：Local optimal solution found. Extended solver steps: 2 Total solver iterations: 63Variable Value Reduced Cost分析结果，出战的顺序应为：A3、A1、A2、A3、A1第二问同理。