13的课后习题解答及电子课件02第2章整数

1、第 2 章整数规划习题解答2.1解 做变量替换 y x1 x2 ，则有如下关系x1 x2 1 y x1 ， x1 x2 1 y x2 ，从而可以得到如下的线性0 1规划maxz x1 y x3 ， 23 3,x x 1 y x ,121s.t. x1 x2 1 y x2 ,x 0或1， ( j 1,2,3),j y 0或1.2.2解 令 1,在备选校址Bi 建学校,xi0,在备选校址Bi 不建学校，由于小区 A1 可以被备选校址 B1 ，B2 ，B3 处所建的学校覆盖，则有约束条件3 1，类似地，可以写出其它的约束条件，建立如下的 0-1 整数规划模型6 xii 1min3 1,x x 1,2

2、4x3 x5 1,x x 146s.t. 1,35 6 1, x x 1246计算的 Lingo 程序如下m:sets: var/1.6/:x; endsetsmin=sum(var:x); x(1)+x(2)+x(3)1;-7-x(2)+x(4)1;x(3)+x(5)1;x(4)+x(6)1;x(5)+x(6)1; x(1)1; x(2)+x(4)+x(6)1;end求得在备选校址 B1 ， B4 ， B5 建小学。2.3 解 用 j 1,2,3,4 分别表示甲、乙、丙、丁四个企业， cij 表示第i （ i 1,6 ）台设备分配给第 j 个企业创造的利润，引进0 1 变量1,第i台设备分配

3、给第j个企业 ， i 1,6 ， j 1,2,3,4xij0,第i台设备不分配给第j个企业则问题的数学模型为max cij xiji1 j 1646x 1,j 1,2,3,4ij i14 xij 1,i 1,6s.t. j 1x 0或1， i 1,6;j 1,2,3,4ij计算的 Lingo 程序如下:msets:shebei/1.6/; qiye/1.4/; link(shebei,qiye):c,x; endsetsdata:c=4 23456666;677774567889810 8enddatamax=sum(link:c*x);for(qiye(j):sum(shebei(i):x(

4、i,j)1);for(shebei(i):sum(qiye(j):x(i,j)=1); for(link:bin(x);end求得 x14 1， x21 1， x31 1， x43 1 ， x52 1 ， x62 1 。最大利润为44。2.4 解 问题（1）-8-记i 1,2,3,4 分别表示高低杠，平衡木，跳马，体操四项运动。引进决策变量 1,第j个人参加第i个项目， i 1,2,3,4 ， j 1,2,10 xij0， 第j个人不参加第i个项目cij 表示在某种情形下第 j 个人参加第i 个项目的得分建立如下的非线性整数规划模型max cij xiji1 j14 1010 x 6， i 1

5、,2,3,4ij j1 10s.t.4 ij 4x j1 i1总的得分为 212.3。使用计算机进行计算时，首先构造纯文本文件sj.txt，把原始的4个项目，10个人的数据放在纯文件中，然后把分数和概率之间的符号“”替换成空格，具体数据格式如下：8.49.59.29.48.48.89.0109.19.39.59.88.78.99.19.90.15 9.3 0.10.5 9.5 0.10.25 9.6 0.68.48.89.0108.19.19.39.58.49.59.29.49.59.79.80.10.20.60.10.10.50.30.10.150.50.250.10.10.10.68.19

6、.19.39.58.78.99.19.99.09.49.59.78.48.89.00.10.50.30.10.10.20.60.10.10.10.50.30.10.20.68.49.59.29.49.09.29.49.78.38.78.99.39.49.69.79.90.150.50.250.10.10.10.60.20.10.10.60.20.10.10.60.29.49.69.79.98.78.99.19.98.58.78.99.18.49.59.29.40.10.10.60.20.10.20.60.10.10.10.50.30.150.50.250.19.59.79.8108.48.89

7、.0108.38.78.99.38.48.89.29.80.10.10.60.20.10.20.60.10.10.10.60.20.10.10.60.28.48.89.0108.89.29.8108.78.99.19.98.29.39.59.80.10.20.60.10.050.050.50.40.10.20.60.10.10.50.30.18.49.59.29.48.48.89.29.88.48.89.0109.39.59.79.90.150.50.250.10.10.10.60.20.10.20.60.10.10.10.50.39.09.29.49.78.19.19.39.58.29.29

8、.49.69.19.39.59.80.10.10.60.20.10.50.30.10.10.50.30.10.10.10.60.20.1 9.80.1 8.40.2 9.00.6 9.20.1 9.40.1 8.40.1 8.80.6 9.00.2 100.1 8.90.2 9.10.6 9.30.1 9.60.20.150.50.250.10.10.20.60.10.10.10.60.210 0.210 0.1提出最低分的 load sj.txt fen=sj(:,1:2:20);gai=sj(:,2:2:20);for i=1:4for j=1:10程序：low(i,j)=min(fen(

9、4*i-3:4*i,j);endenddlmwrite(data2.txt,low)%把最低分的矩阵写到纯文本文件data2.txt，供Lingo使用求解上述非线性 0-1 整数规划模型的 Lingo 程序：m:sets:xm/1.4/;yd/1.10/:y; links(xm,yd):c,x; endsetsdata:c=file(data2.txt);enddata max=sum(links:c*x);for(xm(i):sum(yd(j):x(i,j)=6);-9-sum(yd(j):x(1,j)*x(2,j)*x(3,j)*x(4,j)=4; for(links:bin(x);for

10、(yd:bin(y); end下面通过巧妙地引进0 1变量1,j,第人参加全能比赛y j0，第j人不参加全能比赛,建立线性0-1整数规划模型max cij xiji1 j14 1010 x 6,i 1,2,3,4ij j1s.t. 4 y j4 xij 3 y j ,j 1,2,10i1 10 y j 4 j1计算的Lingo程序如下：:msets:xm/1.4/;yd/1.10/:y; links(xm,yd):c,x; endsetsdata:c=file(data2.txt);enddata max=sum(links:c*x);for(xm(i):sum(yd(j):x(i,j)=6)

11、; for(yd(j):4*y(j)sum(xm(i):x(i,j);sum(xm(i):x(i,j)4*y(j);for(yd(j):sum(xm(i):x(i,j)=236.2;for(xm(i): for(yd(j): p(i,j)=sum(pm(k): b(i,j,k)*z(i,j,k);for(xm(i): for(yd(j): c(i,j)=sum(pm(k): a(i,j,k)*z(i,j,k);for(xm(i): for(yd(j): sum(pm(k): z(i,j,k)=1); for(yd:bin(y);for(link:bin(x); for(link2: bin(z

12、); end目标函数的最大值为 P 6.9121019 ，说明该队无论以什么阵容出场，获得冠军的可能性几乎是不可能的。根据每个运动员参加每个项目的得分均值，可以得到以该阵容出场时，得分的数学期望为222.9。记Cij 为第 j 个人参加第i 个项目的得分的随S xij Ciji1 j1假设总得分 S 服从正态分布，类似地可以求得最乐观情形下，该队的总得分为236.9。所以 S 212.3,236.9 。量，总得分随量4 10各个Cij 均为相互独立的随E(S) xij E(Cij )i1 j1总分的方差为D(S) xij D(Cij )i1 j1上面已求出 E(S) 222.9 ，计算得4 10量，所以总