数学建模作业3
线性规划和整数规划实验：
1生产计划安排：
某厂生产A，B，C三种产品，其所需劳动力，材料等有关数据如下： 产品，消耗定额，资源 A B C 可用量（单位） 劳动力 6 3 5 45 材料 3 4 5 30 产品利润（元/件） 3 1 4
要求：
（a）确定获利最大的产品生产计划；
（b）产品A的利润在什么范围内变动时，上述最有计划不变；
（c）如果劳动力数量不增，材料不足时可从市场购买，每单位0.4元，问该厂要不要购进原材料扩大生产，以购多少为宜
（d）如果设计一种新产品D，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？
解：max 3x1+x2+4x3 !利润最大值目标函数 x1,x2,x3分别为ABC的生产数量 st !限制条件
6x1+3x2+5x3<45 !劳动力的限制条件 3x1+4x2+5x3<30 !材料的限制条件 end !结束限制条件
把上面的语句直接复制到lindo中点solve,可以得到以下结果 1.生产产品A5件,C 3件可以得到最大利润,27元 2.A利润在2.4-4.8元之间变动,最优生产计划不变 3.max 3x1+x2+4x3 st
6x1+3x2+5x3<45 end
可得到生产产品B 9件时利润最大,最大利润为36元,应该购入原材料扩大生产,购入15个单位
4.max 3x1+x2+4x3+3x4 st
6x1+3x2+5x3+8x4<45 3x1+4x2+5x3+2x4<30 end gin x1 gin x2 gin x3 gin x4
利润没有增加,不值得生产 2工程进度问题：
某城市在未来的五年内将启动四个城市住房改造工程.每项工程有不同的开始时间，工程周期也不一样.表3.1提供这此项目的基本数据.
工程1和工程4必须在规定的周期内全部完成.必要时，其余的二项工程 可以在预算的限制内完成部分.然而，每个工程在它的规定时间内必须至少完成25%.每年底，工程完成的部分立刻入住，并目实现一定比例的收入.例如，如果工程1在第一年完成40%，在第三年完成剩下的60%，在五年计划范围内的相应收入是0.4 x 50(第二年)+0.4 x 50(第三年)+ }0.4+0.6) x 50(第四年)+ (0.4+0.6) x 50(第五年)=(4x0.4+2x0.6)x50(单位:万元).试为工程确定最优的时间进度表，使得五年内的总收入达到最大.
解：设某年某工程的完成量为Xij，i表示工程的代号（i=1，2，3），j表示年数（j=1，2，3，4，5）如第一年工程1完成X11，工程3完成X31，到第二年工程已完成X12，工程3完成X32。另有一个投入与完成的关系，既第一年投入总费用的40%，该工程在年底就完成40%。 工程1利润： 50 × X11+50 × (X11+X12)+50×(X11+X12+X13)+50×(X11+X12+X13) 工程2利润： 70×X22+70×(X22+X23) +70×(X22+X23+X24) 工程3利润： 150×X31+150×(X31+X32)+150×(X31+X32+X33) +150×(X31+X32+X33+X34) 工程4利润： 20×X43+20×(X43+X44)
Max ( 50 × X11+50 × (X11+X12)+50×(X11+X12+X13)+50×(X11+X12+X13))+ (70×X22+70×(X22+X23) +70×(X22+X23+X24))+( 150×X31+150×(X31+X32)+150×(X31+X32+X33) +150×(X31+X32+X33+X34))+( 20×X43+20×(X43+X44)) s.t. 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≥0.25 X22+X23+X24+X25≤1
X31+X32+X33+X34+X35≥0.25 X31+X32+X33+X34+X35≤1 X43+X44=1 全为大于零的数 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
输出结果：
Global optimal solution found.
Objective value: 523.7500 Total solver iterations: 9
Variable Value Reduced Cost X11 0.000000 0.000000 X12 0.000000 0.000000 X13 1.000000 0.000000 X22 0.000000 20.00000 X23 0.000000 10.00000 X24 0.2250000 0.000000 X31 0.2000000 0.000000 X32 0.4000000 0.000000 X33 0.5333333E-01 0.000000 X34 0.3466667 0.000000 X43 1.000000 0.000000 X44 0.000000 8.000000 X25 0.2500000E-01 0.000000 X35 0.000000 18.75000
Row Slack or Surplus Dual Price
1 523.7500 1.000000 2 0.000000 0.3875000E-01
3 0.000000 0.2875000E-01
4 0.000000 0.1875000E-01
5 0.000000 0.8750000E-02
6 6800.000 0.000000 7 0.000000 6.250000 8 0.7500000 0.000000 9 0.000000 0.000000 10 0.000000 18.75000 11 0.7500000 0.000000 12 0.000000 17.50000 结果分析：
要获得最大利润，需在第一年投资3000万的资金在工程3上，第二年投资6000资金在工程3上，第三年投资5000万在工程1上，1200万在工程4，800万在工程3上，第四年投资1800万在工程2上，5200万在工程3上，第五年投资200万在工程2上，剩余6800万。获得的最大利润523.75万元。
3投资问题
假设投资者有如下四个投资的机会.
(A)在三年内，投资人应在每年的年初投资，每年每元投资可获利息0.2元，每年取息后可重新将本息投入生息.
(B)在三年内，投资人应在第一年年初投资，每两年每元投资可获利息0.5元.两年后取息，可重新将本息投入生息.这种投资最多不得超过20万元.
(C)在三年内，投资人应在第二年年初投资，两年后每元可获利息0.6元，这种投资最多不得超过15万元.
(D)在三年内，投资人应在第三年年初投资，一年内每元可获利息0.4元，这种投资不得超过10万元.假定在这三年为一期的投资中，每期的开始有30万元的资金可供投资，投资人应怎样决定投资计划，才能在第三年底获得最高的收益.
解：用xiA，xiB，xiC，xiD（i＝1，2，3）表示第i年初给项目A，B，C，D的投资金
额，则
max 1.2x3A＋1.6x2C＋1.4x3D s．t．x1A+x1B=30
1.2x1A=x2A+x2C
x3B＋x3A+x3D=1.2x2A+1.5x1B
x1B≤20 x2C≤15 x3D≤10 程序如下： MODEL:
1]max=1.2*X3a+1.6*X2c+1.4*X3d; 2]X1a+X1b=30;
3]X2a+X2c-1.2*X1a=0;
4]X3b+X3a+X3d-1.2*X2a-1.5*X1b=0; 5]@bnd(0,X1b,20); 6]@bnd(0,X2c,15); 7]@bnd(0,X3d,10); END
运行结果如下：
Global optimal solution found at iteration: 4
Objective value: 57.50000
Variable Value Reduced Cost X3A 16.25000 0.000000 X2C 15.00000 -0.1000000 X3D 10.00000 -0.2000000 X1A 12.50000 0.000000 X1B 17.50000 0.000000 X2A 0.000000 0.6000000E-01 X3B 0.000000 1.200000
Row Slack or Surplus Dual Price 1 57.50000 1.000000 2 0.000000 1.800000 3 0.000000 1.500000 4 0.000000 1.200000
因此，第一年在机会A上投资12.5万元，在机会B上投资17.5万元，第二年在机会C上投资15万元，第三年在机会A上投资16.25万元，在机会D上投资10万元，可获得最大收益57.5万元。
四 生产计划与库存问题 不会做
五 志愿者排班问题
(1)一家医院雇用志愿者作为接待处的工作人员，接待时间是从早上8:00到晚上10:00.每名志愿者连续工作3小时，只有在晚上8:00开始工作的人员除外，他们只工作2小时.对于志愿者的最小需求可以近似成2小时间隔的阶梯函数，其函数在早上8:00开始，相应的需求人数分别是4、6、8、6、4、6、8.因为大多数志愿者是退休人员，他们愿意在一天的仟何时间(早上8:00到晚上10:00)提供他们的服务.然而，由于大多数慈善团体竞争他们的服务，所需的数目必须保持尽可能的低.为志愿者的开始时间确定最优的时间表.
(2)在问题Cl)中，考虑到午饭和晚饭，假定没有志愿者愿意在中午12:00和晚上6:00开始工作，确定最优的时间表.
解： 时间段 X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13 X14 人数 8 X1 4 9 X1 X2 10 X1 X2 X3 6 11 X2 X3 X4 12 X3 X4 X5 8 13 X4 X5 X6 14 X5 X6 X7 6 15 X6 X7 X8 16 X7 X8 X9 4 17 X8 X9 X10 18 X9 X10 X11 6 19 X10 X11 X12 20 X11 X12 X13 8 21 X12 X13 X14
(1)假设每个小时段的人数为Xi（i=1~14）
Lingo程序：
min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+X14; x1>=4; x1+x2>=4; x1+x2+x3>=6; x2+x3+x4>=6; x3+x4+x5>=8; x4+x5+x6>=8; x5+x6+x7>=6; x6+x7+x8>=6; x7+x8+x9>=4; x8+x9+x10>=4;
x9+x10+x11>=6; x10+x11+x12>=6; x11+x12+x13>=8; x12+x13+X14>=8; end
运行结果
Global optimal solution found.
Objective value: 32.00000 Total solver iterations: 11
Variable X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13 X14
Row 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Value 4.000000 0.000000 4.000000 2.000000 2.000000 4.000000 0.000000 2.000000 2.000000 4.000000 0.000000 2.000000 6.000000 0.000000 Slack or Surplus 32.00000 0.000000 0.000000 2.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 4.000000 0.000000 0.000000 0.000000 0.000000 Reduced Cost 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 Dual Price -1.000000 -1.000000 0.000000 0.000000 0.000000 -1.000000 0.000000 0.000000 -1.000000 0.000000 0.000000 -1.000000 0.000000 0.000000 -1.000000 结果显示，最少需要34名志愿者参加志愿工作。工作安排如下： 时段 8 9 10 11 12 13 14 15 16 17 18 19 20 21 总数 人数 4 0 4 2 2 4 0 2 2 4 0 2 6 0 32
(2)Lingo程序：
min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+X14; x1>=4; x1+x2>=4; x1+x2+x3>=6; x2+x3+x4>=6; x3+x4>=8; x4+x6>=8; x6+x7>=6; x6+x7+x8>=6; x7+x8+x9>=4; x8+x9+x10>=4; x9+x10>=6; x10+x12>=6; x12+x13>=8;
x12+x13+X14>=8; end
运行结果
Global optimal solution found.
Objective value: Total solver iterations:
Variable X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X13 X14
32.00000 9 Value Reduced Cost 4.000000 0.000000 0.000000 1.000000 6.000000 0.000000 2.000000 0.000000 0.000000 1.000000 6.000000 0.000000 0.000000 0.000000 0.000000 1.000000 4.000000 0.000000 2.000000 0.000000 0.000000 1.000000 4.000000 0.000000 4.000000 0.000000 0.000000 1.000000 Row Slack or Surplus Dual Price 1 32.00000 -1.000000 2 0.000000 -1.000000 3 0.000000 0.000000 4 4.000000 0.000000 5 2.000000 0.000000 6 0.000000 -1.000000 7 0.000000 0.000000 8 0.000000 -1.000000 9 0.000000 0.000000 10 0.000000 0.000000 11 2.000000 0.000000 12 0.000000 -1.000000 13 0.000000 0.000000 14 0.000000 -1.000000 15 0.000000 0.000000 结果显示，最少需要34名志愿者参加志愿工作。工作安排如下： 时段 8 9 10 11 12 13 14 15 16 17 18 19 20 21 总数 人数 4 0 6 2 0 6 0 0 4 2 0 4 4 0 32 六 下料问题
某车间有长度为180cm的钢管（数量充分多），今要将其截为三种不同长度的钢管若干根。具体的说，长度为70cm的管料
100根，而52cm、35cm分别不少于150根和120根，问应采取怎样的截法，才能完成任务，同时使剩下余料最少。
要求：（1）建立合理的下料问题的数学模型。 （2）欢迎对上述模型进行求解。
（3）对不短于20cm长的下脚料中需要20根另作他用，试建立合理下料问题的数学模型并求解。
（写出详细分析过程及程序）
解：数学模型如下，首先分析管子的最佳分割方案，有如下七种： 180 ＝ 70 × 2 ＋ 35 × 1 ＋ 预料5 180 ＝ 70 × 1 ＋ 53 × 2 ＋ 预料4 180 ＝ 70 × 1 ＋ 35 × 3 ＋ 预料5 180 ＝ 53 × 3 ＋ 长度20以上的一个剩余 180 ＝ 53 × 2 ＋ 35 × 2 ＋ 14预料
180 ＝ 53 × 1 ＋ 35 × 3 ＋ 长度20以上的剩余 180 ＝ 35 × 5 ＋ 5 预料
暂时不考虑问题当中的3——对长度大于20的管子的要求 而是使用上面7种管子的最佳分割方法来组合完成前面的需求
解决方法：
解一个方程就可以了
假定七种组合各自数目是x1, x2, x3, ... x7
那么方程就是
x1 * 2 + x2 + x3 = 100 ............(1)
x2 * 2 + x4*3 + x5*2 + x6 > 150 ............(2)
x1 * 1 + x2*3 + x5*2 + x6*3 + x7*5 > 120 ............(3)
min(x1+x2+x3+x4+x5+x6+x7) ............(4) min(x1*4+x2*4+x3*5+x5*14+x7*5) ............(5) 找一本最优化的书籍，就知道如何解这种方程了
其中方程4和方程5应该分别作为条件加以考虑，因为很可能无法同时达到最小
考虑20以上的20根这个需求的话，可以先看上述方程的解能否满足，如果不满足就需要 把上述的7种组合以外，再加入对20以上的短料的分割，然后重新建立方程组
七 最小覆盖问题
ABC是一个小型的货物配送公司，需要每天给五个客户发送货物.表3.3给出了每一条线路上的客户.由于卡车运送能力的约束，所以每一条线路都是事先指定的，例如，在路线1上，卡车的运送容童可以目_只能满足客户1, 2, 3, 4的需求.表3.4给出了ABC总部和客户之间的距离.目标就是找一个路程最短的日常配送方案，以满足五个客户的需求.得出的解中可能有客户会在多条选中的路线上，在配送执行中只选择其中一条路线来服务它.根据这个问题，建立整数线性规划模型，并求出最优解.
解：根据要求应求出最佳的路径。由已知共有6条路线供选择，从给出的各客户离ABC总部的距离我们可以知道各路线距离：x1=80；x2=50；x3=70；x4=52；x5=60；x6=44（将彼此之间的距离相加即可得到）。建立数学模型，编写如下程序：
min=80*x1+50*x2+70*x3+52*x4+60*x5+44*x6; x1+x2+x5>=1; x1+x2+x4+x6>=1; x1+x3+x5+x6>=1; x1+x3+x4+x5>=1; x2+x3+x4+x6>=1; @bin(x1); @bin(x2); @bin(x3); @bin(x4); @bin(x5); @bin(x6);
输入以上程序，运行结果如下： Global optimal solution found.
Objective value: 104.0000 Extended solver steps: 0 Total solver iterations: 0
Variable Value Reduced Cost X1 0.000000 80.00000 X2 0.000000 50.00000 X3 0.000000 70.00000 X4 0.000000 52.00000 X5 1.000000 60.00000 X6 1.000000 44.00000
Row Slack or Surplus Dual Price 1 104.0000 -1.000000 2 1.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000 6 0.000000 0.000000 从上面的结果可以看出，应选择线路5和线路6，这样最短的路程为104英里。
8、加分实验（监控摄像头的最优安装）
在过去几个月里，某小区发生了多次夜间行窃案件.此小区有保安巡逻，但保安人数太少.因此，负责此小区的安全部门决定安装r监控摄像头，以协助保安工作.这此监控摄像头都可以360度旋转，因此，在几条街道的交汇处安装一个摄像头就可以同时对这此街道进行监控.图3.1是此小区的地图，其中给出了需要用闭路电视进行监控的区域范围，并用数字标出了49个可以安装摄像头的位置.应该洗择在哪此位置安装摄像头才能伸需要使用的摄像头数目最少?
解：设xi表示i（i=1,2····49）处是否安装摄像头，为1表示要安装，为0表示不要安装，则目标函数为：
x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22+x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x40+x41+x42+x43+x44+x45+x46+x47+x48+x49； 为了使每条街道都能被拍摄到，我们有： x1+x2>=1; x1+x3>=1; x2+x39>=1;
x2+x41+x42>=1; x39+x40+x41>=1; x3+x4>=1; x4+x5>=1;
x4+x6+x8+x9>=1; x6+x7>=1; x9+x10>=1; x3+x11>=1; x12=1;
x11+x21+x22+x25+x26+x27>=1; x22+x23>=1;
x23+x32+x38>=1; x39=1;
x37+x38+x40>=1; x31+x32>=1; x25+x30>=1; x26+x28>=1; x28+x29>=1;
x30+x31+x33+x37+x43>=1; x33+x34>=1; x34+x35>=1; x35+x36>=1; x46=1;
x43+x44+x45>=1; x44+x49>=1; x45+x47>=1; x47+x48>=1; x24+x25>=1;
x17+x18+x19+x20+x21>=1; x16+x20>=1;
x12+x15+x19>=1; x14+x15+x16>=1; x12+x13+x14>=1;
利用lingo软件进行求解得到：
Global optimal solution found.
Objective value: 19.00000
Variable Value Reduced Cost X2 1.000000 0.000000 X3 1.000000 0.000000 X5 1.000000 0.000000 X6 1.000000 0.000000 X9 1.000000 0.000000 X12 1.000000 0.000000 X16 1.000000 0.000000 X18 1.000000 0.000000 X22 1.000000 0.000000 X25 1.000000 0.000000 X28 1.000000 0.000000 X32 1.000000 0.000000 X33 1.000000 0.000000 X35 1.000000 0.000000 X39 1.000000 0.000000 X40 1.000000 0.000000 X44 1.000000 0.000000 X46 1.000000 0.000000 X47 1.000000 0.000000
为0的在此没写出来，由此我们可以得到，在点
2,3,5,6,9,12,16,18,22,25,28,32,33,35，3940,44,46,47处要安装摄像头，共19个。