北京工业大学-数学建模-整数规划与对策论实验

1、整数规划和对策论模型实验作业一、 基本实验1.工程安排问题三年内有五项工程可以考虑施工。每项工程的期望收入和年度费用如表4.1.所示。假定每一项已经选定的工程要在整个三年内完成。目标是要选出使总收入达到最大的那些工程。表4.1 每项工程期望收入和年度费用表（单位：千元）工程费用收入第一年第二年第三年15182024710403392204741155861030可用基金252525解：设0-1变量xi,i=1,2,3,4,5为工程i,i=1,2,3,4,5的投资情况。Xi=0,说明i项目不投资，xi=1,说明对i项目进行投资。目标项为：Max z=20*x1+40*x2+20*x3+15*x4

2、+30*x5,约束条件为：5x1+ 4x2+3x3+7x4+ 8x525，X1+ 7x2+9x3+4x4+ 6x525，8x1+10x2+2x3+ x4+10x525，bin(xi),i=1,2,3,4,5.写成Lingo程序：Max =20*x1+40*x2+20*x3+15*x4+30*x5;5*x1+ 4*x2+3*x3+7*x4+ 8*x5=25;X1+ 7*x2+9*x3+4*x4+ 6*x5=25;8*x1+10*x2+2*x3+ x4+10*x5=25;bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);运行结果见solution report-xue

3、yunqiang-chapter4-1：从运行结果可知，对项目1、项目2、项目3、项目4投资，可使总收益最大为95万元。2.固定费用问题一服装厂生产三种服装，生产不同种类的服装要租用不同的设备，设备租金和其他的经济参数如表4.2所示。假定市场需求不成问题，服装厂每月可用人工工时为2000小时，该厂如何安排生产可使每月的利润最大？表4.2 服装厂设备租金和其他的经济参数服装种类设备租金（元）生产成本（元/件）销售价格（元/件）人工工时（小时/件）设备工时（小时/件）设备可用工时西服500028040053300衬衫2000304010.5300羽绒服300020030042300解：设x1,x2

4、,x3分别为生产西服，衬衫和羽绒服的数量。目标函数(如果生产西服，收益中减去5000，如果生产衬衫，收益中减去2000，如果生产羽绒服，收益中减去3000.如果不生产，就不减去相应租金)：Max z= (400-280)*x1+(40-30)*x2+(300-200)*x3-(x1#GT#0)*5000-(x3#GT#0)*2000-(x3#GT#0)*3000,约束条件为：5x1+x2+4x32000， 3x1300， 0.5x2300， 2x3300， X1,x2,x3取正整数。写成Lingo程序：Max = (400-280)*x1+(40-30)*x2+(300-200)*x3-(x1

5、#GT#0)*5000-(x2#GT#0)*2000-(x3#GT#0)*3000;5*x1+x2+4*x3=2000; 3*x1=300; 0.5*x2=300; 2*x3=300; gin(x1);gin(x2);gin(x3);程序为xueyunqiang-chapter4-2运行结果见xueyunqiang-chapter4-2：由运行结果可知，生产100件西服，生产600件衬衫，生产150件羽绒服，可使总收益最大，总收益为23000元。3.串并联系统可靠性问题有一台电器由三个部件组成，这三个部件串联，假如有一个部件发生故障，电器就不能工作。可以通过在每个部件里安装1到2个备份原件来提

6、高该电器的可靠性（不发生故障的概率）。表4.3列出了可靠性和成本费用。假设制造该电器的已有资金共10万元，那么怎样来构造这件电器呢？表4.3 每种原件的可靠性及成本费用（单位：万元）并联元件数部件1部件2部件3可靠性费用可靠性费用可靠性费用10.610.730.5320.820.850.7430.930.960.95解: 假设xij, i=1,2,3,j=1,2,3为部件i选择并联原件个数为j。xij为0-1变量，xij=1表明部件i选择并联原件个数j,否则不选择。则系统的总可靠性为各部件可靠性的乘积(xij=0时，指数值为1，对可靠值不影响)：0.6x11*0.8x12*0.9x13*0.7

7、x21*0.8x22*0.9x23*0.5x31*0.7x32*0.9x33目标函数为可靠性最高：Max z=0.6x11*0.8x12*0.9x13*0.7x21*0.8x22*0.9x23*0.5x31*0.7x32*0.9x33，限制条件为：X11+2x12+3x13+3x21+5x22+6x23+2x31+4x32+5x3310，X11+x12+x13=1,X21+x22+x23=1,X31+x32+x33=1,Xij=0 or 1.编写Lingo 程序：Max =pow(0.6,x11)*pow(0.8,x12)* pow(0.9,x13)*pow(0.7,x21)*pow(0.8,

8、x22)*pow(0.9,x23)*pow(0.5,x31)*pow(0.7,x32)*pow(0.9,x33);X11+2*x12+3*x13+3*x21+5*x22+6*x23+2*x31+4*x32+5*x330，必须大于1000，因此引入0-1决策变量y1,y2,y3,只要xi1000,yi=0,反之yi=1. Yi=sign(xi-999), xi1000,yi=0,不生产；反之yi=1，决策生产.整理规划问题：目标函数为：Max z= y1x1*2000+y2x2*3000+y3x3*4000,约束条件（s.t.）:1.5x1y1+ 3x2y2+ 5x3y36000，30x1y1+

9、25x2y2+40x3y360000，X10，x20,x30,Y1=sign(x1-999),Y2=sign(x2-999),Y1=sign(x3-999).写成Lingo程序为：Max = y1*x1*2000+y2*x2*3000+y3*x3*4000;1.5*x1*y1+ 3*x2*y2+ 5*x3*y3=6000;30*x1*y1+25*x2*y2+40*x3*y3=60000;y1=sign(x1-999);y2=sign(x2-999);y1=sign(x3-999);运行结果见xueyunqiang-chapter4-4根据分析结果可知，y2=1,y1=0,y3=0,所以生产中型

10、汽车。X2=2000,生产中型汽车2000辆。故最优方案为生产2000辆中型汽车，总利润为美元。5.最小覆盖问题某市管辖6个区（区1-区6）。这个市必须明确在什么地方修建消防站，在保证至少有一个消防站在每个区的15分钟（行驶时间）路程内的情况下，这个市希望修建的消防站最少。表4.5给出了该市各个区之间行驶需要的时间（单位为分钟）。这个市需要多少个消防站，以及他们的所在位置。表4.5 该市各个区之间行驶需要的时间（单位：分钟）区1区2区3区4区5区6区101020303020区210025352010区320250153020区430351501525区530203015014区62010202

11、5140解：设xi，i=1,2,3,4,5,6为在小区i的建设情况，xi=1,表示在小区i建设消防站，xi=0表示小区i不建设。 Tij为小区i到小区j的时间，为了计算方便我们记如果tij15,记为0.用到#LE#逻辑运算：区1区2区3区4区5区6区1110000区2110001区3001100区4001110区5000111区6010011 要满足条件，即是使得上述tij*xi=1,j=1,2,3,4,5,6.(易见至少有一项xi=1，如果xi=0,表明不建设消防站，相应与tij的乘积为0.要想满足要求，需要每一项乘积之和至少为1.)目标函数为建设消防站最少：Min z=x1+x2+x3+x

12、4+x5+x6,约束条件为：( tij#LE#15)*xi1，j=1,2,3,4,5,6 Xi=0,1.写成Lingo程序：Min =x1+x2+x3+x4+x5+x6;x1+x2 =1;x1+x2+x4 =1;x3+x4 =1;x3+x4+x5 =1;x4+x5+x6=1;x2+x5+x6=1;bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);bin(x6);运行结果见xueyunqiang-chapter4-5： 可见，x2=1,x4=1,只需在小区2和小区4各建立一座消防站即可。6.对策问题1在一次野餐会上，两个二人组在玩捉迷藏游戏。共有四个隐藏地点（A，B

13、,C,D）,隐藏组的两个成员可以分别藏在四个地点的任何两个，搜寻组人有机会寻找任何两个地点。如果他们都找到了隐藏组的二个人，搜寻组就可以得到一分奖励，假如没有把两个人都找到，他们就输一分。其他情况下，结果是平局。将这个问题表示成一个二人零和对策，求出搜寻最优搜寻策略和它们的赢得值。解：对于四个隐藏地点（A,B,C,D）,设隐藏策略为yi,Y1=(1,1,0,0),Y2=(1,0,1,0),Y3=(1,0,0,1),Y4=(0,1,1,0),Y5=(0,1,0,1),Y6=(0,0,1,1),其中1表示选中所对应的地点，0表示未选择所对应的地点。搜寻策略为xi,x1=(1,1,0,0),x2=(

14、1,0,1,0),x3=(1,0,0,1),x4=(0,1,1,0),x5=(0,1,0,1),x6=(0,0,1,1),则对于搜寻组的赢得值矩阵为：，隐藏组的赢得矩阵为-A。利用线性规划法求解：由于赢得矩阵中有0和-1，不能保证0和0.将赢得矩阵的每个元素加上2：求解问题化为两个互为对偶的线性规划问题：(P): min x1+x2+x3+x4+x5+x6s.t. 3x1+2x2+2x3+2x4+2x5+x61， 2x1+3x2+2x3+2x4+x5+2x61， 2x1+2x2+3x3+x4+2x5+2x61， 2x1+2x2+x3+3x4+2x5+2x61，2x1+x2+2x3+2x4+3x

15、5+2x61，x1+2x2+2x3+2x4+2x5+3x61，x1,x2, x3,x4,x5,x60.(D): may y1+y2+y3+y4+y5+y6s.t. 3y1+2y2+2y3+2y4+2y5+y61， 2y1+3y2+2y3+2y4+y5+2y61， 2y1+2y2+3y3+y4+2y5+2y61， 2y1+2y2+y3+3y4+2y5+2y61，2y1+y2+2y3+2y4+3y5+2y61，y1+2y2+2y3+2y4+2y5+3y61，y1,y2, y3,y4,y5,y60.写成Lingo程序：min =x1+x2+x3+x4+x5+x6; 3*x1+2*x2+2*x3+2*

16、x4+2*x5+x6=1; 2*x1+3*x2+2*x3+2*x4+x5+2*x6=1; 2*x1+2*x2+3*x3+x4+2*x5+2*x6=1; 2*x1+2*x2+x3+3*x4+2*x5+2*x6=1;2*x1+x2+2*x3+2*x4+3*x5+2*x6=1;x1+2*x2+2*x3+2*x4+2*x5+3*x6=1;x1+x2+x3+x4+x5+x6=1;x1=0;x2=0;x3=0;x4=0;x5=0;x6=0;max =y1+y2+y3+y4+y5+y6; 3*y1+2*y2+2*y3+2*y4+2*y5+y6=1; 2*y1+3*y2+2*y3+2*y4+y5+2*y6=1

17、; 2*y1+2*y2+3*y3+y4+2*y5+2*y6=1; 2*y1+2*y2+y3+3*y4+2*y5+2*y6=1;2*y1+y2+2*y3+2*y4+3*y5+2*y6=1;y1+2*y2+2*y3+2*y4+2*y5+3*y6=0;y2=0;y3=0;y4=0;y5=0;y6=0;第一个规划求解：第二个规划求解：求解得到：故对策问题的解为： 即对于隐藏组和搜寻组分别以1/2的概率选择A,B和C,D(更确切的说是1/2的概率选择A,B,C,D中任意两个，以1/2的概率选择另外两个),最后的结果是平局。7.对策问题2甲手中有两张牌，各为1点和4点；乙手中有两张牌，各为2点和3点。两人

18、同时各出一张牌，并依据两人所出牌的点数之和来决定各自的收益。当点数和为偶数时，甲赢得为两张牌的点数和，乙赢得两张牌的点数差；当点数和为奇数时，甲赢得为两张牌的点数差，乙赢得两张牌的点数和。求甲乙二人各自的最优策略和各自的赢得值。解：甲的可选策略为（1,4），乙的可选策略为（2,3）.设甲选1点的概率为，则选择4点的概率是1-。设乙选2点的概率是，则选择3点的概率是1-。甲乙的混合策略为，。根据游戏规则，甲乙的赢得矩阵为：甲的赢得值2点3点1点144点61乙的赢得值2点3点1点324点27简化整理为：， ，对于双对策矩阵，分别画出矩阵A各列的最大值和矩阵B各行的最大值。由于没有两个数字下面都划线

19、，因此该对策不存在纯策略下的Nash均衡策略。下面进行混合对策问题求解：对于赢得矩阵A：，所以得到方程组：， (1), (2)方程组（2）利用图示法解方程组：方程组（1）可知=0，=0；或者=5/6,=3/8;或者=1，=1.所以三个平衡点为：对于平衡点对于平衡点对于平衡点综上所述，有三个平衡点：甲选4点，乙选3点，赢得值分别为甲以5/6的概率选1点，1/6的概率选1点，乙以3/8的概率选2点，5/8的概率选3点，甲乙赢得值分别为甲选1点，乙选2点，赢得值分别为二、 加分实验（乒乓球团体赛上场队员排序问题）兵乓球团体赛的比赛规则如下：从一个队中挑选出的三名比赛队员和一个队长（可由参赛队员兼任，

20、亦可由其他人员专任）组成。比赛之前，双方队长应抽签决定A,B,C和Y,Y,Z的选择，并向裁判提交每个运动员分配到一个字母的队伍名单。现行的比赛顺序：第一场A-Y,第二场B-Y,第三场C-Z,第四场A-Y,第五场B-Y.每场比赛为三局两胜制。当一个队已经赢得三场个人比赛时，该次比赛结束。现有甲队挑选出的三名比赛队员分别是：A1,A2,A3,乙队挑选出的三名比赛队员分别是：B1,B2,B3,根据以往的历史资料，甲队与乙队比赛，甲队运动员在每一局中获胜的概率如表4.6所示。表4.6 两队比赛，甲队运动员在每一局中获胜的概率队员B1B2B3A10.500.550.60A20.450.500.55A30

21、.400.450.50你所要完成的问题如下：（1） 甲队教练将如何安排上场运动员的次序，使得本队获胜的概率最大。（2） 如果每一局比赛，A1胜B3的概率改为0.45，A3胜B1的概率改为0.55.在这种情况下，甲队教练将如何调整甲队队员的上场次序？解：（1）有题意可知，甲乙队的上场次序各为六类，分别为：(A1,A2,A3)，(A1,A3,A2)，(A2,A1,A3)， (A2,A3,A1) ，(A3,A1,A2)， (A3,A2,A1).(B1,B2,B3)，(B1,B3,B2)，(B2,B1,B3)， (B2,B3,B1) ，(B3,B1,B2)， (B3,B2,B1).记xij,i=1,2

22、,3，j=1,2,3为Ai对Bj的获胜概率。对于各个策略的情况，甲队在每个策略下的赢得值为五场比赛获胜概率的乘积计算得到如下表：甲赢得值(B1,B2,B3)(B1,B3,B2)(B2,B1,B3)(B2,B3,B1)(B3,B1,B2)(B3,B2,B1)各行最小值(A1,A2,A3)0.030940.033410.030940.036300.033410.036300.03094(A1,A3,A2)0.027230.030000.027230.033410.030000.033410.02723(A2,A1,A3)0.030940.033410.030940.036300.033410.03

23、6300.03094(A2,A3,A1)0.024300.027230.024300.030940.027230.030940.02430(A3,A1,A2)0.027230.030000.027230.033410.030000.033410.02723(A3,A2,A1)0.024300.027230.030380.034030.027230.030940.02430各列最大值0.030940.033410.030940.036300.033410.03630 对于对于各行最小值中的最大值为0.03094，各列最大值中的最小值亦为0.03094.故：对于甲来说(A1,A2,A3)，(A2,

24、A1,A3)是最优纯策略。（2）队员B1B2B3A10.500.550.45A20.450.500.55A30.550.450.50，甲乙队的上场次序各为六类，分别为：(A1,A2,A3)，(A1,A3,A2)，(A2,A1,A3)， (A2,A3,A1) ，(A3,A1,A2)， (A3,A2,A1).(B1,B2,B3)，(B1,B3,B2)，(B2,B1,B3)， (B2,B3,B1) ，(B3,B1,B2)， (B3,B2,B1).记xij,i=1,2,3，j=1,2,3为Ai对Bj的获胜概率。对于各个策略的情况，甲队在每个策略下的赢得值为五场比赛获胜概率的乘积计算得到如下表：甲赢得值

25、(B1,B2,B3)(B1,B3,B2)(B2,B1,B3)(B2,B3,B1)(B3,B1,B2)(B3,B2,B1)各行最小值(A1,A2,A3)0.030940.025060.030940.037430.025060.037430.02506(A1,A3,A2)0.037430.030940.037430.025060.030940.025060.02506(A2,A1,A3)0.030940.025060.030940.037430.025060.037430.02506(A2,A3,A1)0.025060.037430.025060.030940.037430.030940.0250

26、6(A3,A1,A2)0.037430.030940.037430.025060.030940.025060.02506(A3,A2,A1)0.025060.037430.022780.034030.037430.030940.02278各列最大值0.037430.037430.037430.037430.037430.03743乙队在每个策略下的赢得值为五场比赛获胜概率的乘积计算得到如下表：队员B1B2B3A10.500.450.55A20.550.500.45A30.450.550.50甲赢得值(B1,B2,B3)(B1,B3,B2)(B2,B1,B3)(B2,B3,B1)(B3,B1,B

27、2)(B3,B2,B1)各行最小值(A1,A2,A3)0.030940.037430.030940.025060.037430.025060.02506(A1,A3,A2)0.025060.030940.025060.037430.030940.037430.02506(A2,A1,A3)0.030940.037430.030940.025060.037430.025060.02506(A2,A3,A1)0.037430.025060.037430.030940.025060.030940.02506(A3,A1,A2)0.025060.030940.025060.037430.030940.

28、037430.02506(A3,A2,A1)0.037430.025060.041590.027840.025060.030940.02506各列最大值0.037430.037430.041590.037430.037430.03743对于各行最小值中的最大值为0.02506，各列最大值中的最小值亦为0.03743.故：.,下面求解矩阵对策问题：甲的赢得矩阵为：乙的赢得矩阵为：两个矩阵做差，小于零的项赋值-1，大于零的项赋值1，等于零的项赋值0.得到如下甲的赢得矩阵：由于赢得矩阵中有0和-1，不能保证w和v大于零，将每个元素加上2得到：求解问题化为两个互为对偶的线性规划问题：Xi,i=1,2,3,4,5,6为甲采取的策略，yi,i=1,2,3,4,5,6为乙采取的策略。（P）min x1+x2+x3+x4+x5+x6， s.t. 2*x1+3*x2+2*x3+x4+3*x5+x61,x1+2*x2+x3+3*x4+2*x5+3*x61,2*x1+3*x2+2*x3+x4+3*x5+x61,3*x1+x2+3*x3+2*x4+x5+3*x61,x1+2*x2+x3+3*x4+2*x5+3*x61,3*x1+x2+3*