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

整数规划和对策论模型实验作业

一、 基本实验

1.工程安排问题

三年内有五项工程可以考虑施工。每项工程的期望收入和年度费用如表4.1.所示。假定每一项已经选定的工程要在整个三年内完成。目标是要选出使总收入达到最大的那些工程。

表4.1 每项工程期望收入和年度费用表（单位：千元）

费用 工程 第一年 1 2 3 4 5 可用基金 5 4 3 7 8 25 第二年 1 7 9 4 6 25 第三年 8 10 2 1 10 25 20 40 20 15 30 收入 解：设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+30*x5, 约束条件为：

5x1+ 4x2+3x3+7x4+ 8x5≤25， X1+ 7x2+9x3+4x4+ 6x5≤25， 8x1+10x2+2x3+ x4+10x5≤25， @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-xueyunqiang-chapter4-1：

从运行结果可知，对项目1、项目2、项目3、项目4投资，可使总收益最大为95万元。

2.固定费用问题

一服装厂生产三种服装，生产不同种类的服装要租用不同的设备，设备租金和其他的经济参数如表4.2所示。假定市场需求不成问题，服装厂每月可用人工工时为2000小时，该厂如何安排生产可使每月的利润最大？

表4.2 服装厂设备租金和其他的经济参数

服装种类 设备租金 （元） 西服 衬衫 羽绒服 5000 2000 3000 生产成本（元/件） 280 30 200 销售价格（元/件） 400 40 300 人工工时设备工时 设备可用工（小时/件） （小时/件） 时 5 1 4 3 0.5 2 300 300 300 解：设x1,x2,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+4x3≤2000， 3x1≤300， 0.5x2≤300， 2x3≤300， X1,x2,x3取正整数。 写成Lingo程序：

Max = (400-280)*x1+(40-30)*x2+(300-200)*x3

-(x1#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个备份原件来提高该电器的可靠性（不发生故障的概率）。表4.3列出了可靠性和成本费用。假设制造该电器的已有资金共10万元，那么怎样来构造这件电器呢？

表4.3 每种原件的可靠性及成本费用（单位：万元）

并联元 件数 1 2 3 部件1 可靠性 0.6 0.8 0.9 费用 1 2 3 部件2 可靠性 0.7 0.8 0.9 费用 3 5 6 部件3 可靠性 0.5 0.7 0.9 费用 3 4 5

解: 假设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.7x21*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+5x33≤10， 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,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*x33<=10; X11+x12+x13=1; X21+x22+x23=1; X31+x32+x33=1; @bin(x11); @bin(x12); @bin(x13); @bin(x21); @bin(x22); @bin(x23); @bin(x31); @bin(x32); @bin(x33);

导入Lingo,见xueyunqiang-chapter4-3:

运行结果见xueyunqiang-chapter4-3:

由运行结果可知，x22=1,x21=1,x33=1.所以，最优方案为部件1选择2个并联元件；部件2选择1个并联元件；部件3选择3个并联元件；总费用为10万 元，系统可靠性为0.504.

4.二选一约束条件

某汽车公司正在考虑生产3种类型的汽车：微型、中型和大型。表4.4给出了每种汽车需要的资源及产生的利润。目前有6000吨钢材和60000小时的劳动时间。要生产一种在经济效益上可行的汽车，这种汽车必须至少生产1000辆。试为该公司制定一个使生产利润达到最大的方案。

表4.4 3种汽车的资源和利润

汽车的类型 资源 微型 所需钢材（吨） 所需劳动时间（小时） 产生的利润（美元） 1.5 30 2000 中型 3 25 3000 大型 5 40 4000 解：设x1,x2,x3分别为生产微型汽车、中型汽车和大型汽车的数量。由于只要xi>0，必须大于1000，因此引入0-1决策变量y1,y2,y3,只要xi<1000,yi=0,反之yi=1. Yi=sign(xi-999), xi<1000,yi=0,不生产；反之yi=1，决策生产.

整理规划问题： 目标函数为：

Max z= y1x1*2000+y2x2*3000+y3x3*4000, 约束条件（s.t.）:

1.5x1y1+ 3x2y2+ 5x3y3≤6000， 30x1y1+25x2y2+40x3y3≤60000， X1≥0，x2≥0,x3≥0, 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,所以生产中型汽车。X2=2000,生产中型 汽车2000辆。故最优方案为生产2000辆中型汽车，总利润为6000000美元。

5.最小覆盖问题

某市管辖6个区（区1-区6）。这个市必须明确在什么地方修建消防站，在保证至少有一个消防站在每个区的15分钟（行驶时间）路程内的情况下，这个市希望修建的消防站最少。表4.5给出了该市各个区之间行驶需要的时间（单位为分钟）。这个市需要多少个消防站，以及他们的所在位置。

表4.5 该市各个区之间行驶需要的时间（单位：分钟）

区1 区2 区3 区4 区5 区6 区1 0 10 20 30 30 20 区2 10 0 25 35 20 10 区3 20 25 0 15 30 20 区4 30 35 15 0 15 25 区5 30 20 30 15 0 14 区6 20 10 20 25 14 0 解：设xi，i=1,2,3,4,5,6为在小区i的建设情况，xi=1,表示在小区i建设消防站，xi=0表示小区i不建设。

Tij为小区i到小区j的时间，为了计算方便我们记如果tij<=15,则赋值1，如果tij>15,记为0.用到#LE#逻辑运算：

区1 区2 区3 区4 区5 区6 区1 1 1 0 0 0 0 区2 1 1 0 0 0 1 区3 0 0 1 1 0 0 区4 0 0 1 1 1 0 区5 0 0 0 1 1 1 区6 0 1 0 0 1 1 要满足条件，即是使得上述tij*xi>=1,j=1,2,3,4,5,6.(易见至少有一项xi=1，如果xi=0,表明不建设消防站，相应与tij的乘积为0.要想满足要求，需要每一项乘积之和至少为1.)

目标函数为建设消防站最少： Min z=x1+x2+x3+x4+x5+x6,

约束条件为：

?i?16( tij#LE#15)*xi≥1，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,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=(1,0,1,0), x3=(1,0,0,1), x4=(0,1,1,0), x5=(0,1,0,1), x6=(0,0,1,1),

则对于搜寻组的赢得值矩阵为：

?10000?1??0100?10?????001?100??A???，

?00?1100??0?10010????100001????隐藏组的赢得矩阵为-A。 利用线性规划法求解：

由于赢得矩阵中有0和-1，不能保证?>0和?>0.将赢得矩阵的每个元素加上2：

?3?2???2A???2?2??1?223223211222221?212??122???

322?232??223??求解问题化为两个互为对偶的线性规划问题： (P’): min x1+x2+x3+x4+x5+x6 s.t. 3x1+2x2+2x3+2x4+2x5+x6≥1， 2x1+3x2+2x3+2x4+x5+2x6≥1， 2x1+2x2+3x3+x4+2x5+2x6≥1， 2x1+2x2+x3+3x4+2x5+2x6≥1，

2x1+x2+2x3+2x4+3x5+2x6≥1， x1+2x2+2x3+2x4+2x5+3x6≥1，

x1,x2, x3,x4,x5,x6≥0.

(D’): may y1+y2+y3+y4+y5+y6 s.t. 3y1+2y2+2y3+2y4+2y5+y6≥1， 2y1+3y2+2y3+2y4+y5+2y6≥1， 2y1+2y2+3y3+y4+2y5+2y6≥1， 2y1+2y2+y3+3y4+2y5+2y6≥1，

2y1+y2+2y3+2y4+3y5+2y6≥1， y1+2y2+2y3+2y4+2y5+3y6≥1， y1,y2, y3,y4,y5,y6≥0.

写成Lingo程序： min =x1+x2+x3+x4+x5+x6;

3*x1+2*x2+2*x3+2*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;

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<=1; y1>=0; y2>=0; y3>=0; y4>=0; y5>=0; y6>=0;

第一个规划求解：

第二个规划求解：

求解得到：

111x?(,0,0,0,0,)T,w?

442111y?(,0,0,0,0,)T,??

442故对策问题的解为：

VG?11??2,VG'?VG?2?0 w?1111x*?VG*x?2(,0,0,0,0,)T?(,0,0,0,0,)T4422

1111y*?VG*y?2(,0,0,0,0,)T?(,0,0,0,0,)T4422 即对于隐藏组和搜寻组分别以1/2的概率选择A,B和C,D(更确切的说是1/2的概率选择A,B,C,D中任意两个，以1/2的概率选择另外两个),最后的结果是平局。

7.对策问题2

甲手中有两张牌，各为1点和4点；乙手中有两张牌，各为2点和3点。两

本文来源：https://www.bwwdw.com/article/q2ua.html