164
0 fval= 4 exitflag= 1
上述计算结果表明，fval=4,x2?1,x3?1,x5?1,x6?1,即硕士生最少应学4门课，它们是运筹学、数据结构、计算机模拟、计算机程序． 其中：
数学类：运筹学、数据结构． 运筹学：运筹学、计算机模拟． 计算机类：计算机程序、数据结构．
说明这种选学方案满足每类必修两门课程的要求．而且不难验明，其先修和后修的要求也是满足的．
例7.21 例7.9集装箱装载问题MATLAB程序求解. 解 编写M文件zsgh_10.m: f=-[1,5,2,1,3,2,3,2,8]’; a=[1,0,1,0,0;0,0,0,1,1]; b=[1,1]`;
aeq=[0,1,0,0,-1;1,0,0,1,0]; beq=[0,1]’
[x,fv,ex]=bintprog(f,a,b,aeq,beq); 上述程序执行后，求得 ex=1,fv=－6.3,以及 x=[1,1,0,0,1]’
上述计算结果表明，最佳装箱方案为： 装A1、A2、A3，其最大收入为6.3千元．
例7.22 例7.11指派问题MATLAB程序求解. 解法程序1 编写M文件zsgh_111.m： %目标函数所对应的设计变量的系数
c=[3;8;2;10;3;8;7;2;9;7;6;4;2;7;5;8;4;2;3;5;9;10;6;9;10]; %等式约束
Aeq=[1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1; 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0; 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0; 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0; 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0; 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1]; beq=ones(1,10);
165
%求最优解x和目标函数在x处的值fval [x,fval]=bintprog(c,[],[],Aeq,beq);
%由于x是一列元素，为了使结果更加直观，故排成与效率矩阵E相对应的形式 B=reshape(x,5,5); B' Fval
程序执行后,输出如下： Optimization terminated. ans=
0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 fval= 21
解法程序2 编写M文件zsgh_112.m：
c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5;8 4 2 3 5;9 10 6 9 10]; c=c(:);
a=zeros(10,25); for i=1:5
a(i,(i-1)*5+1:5*i)=1; a(5+i,i:5:25)=1; end
b=ones(10,1);
[x,y]=linprog(c,[],[],a,b,zeros(25,1),ones(25,1)) 程序执行后,输出如下:
Optimization terminated successfully. x =
0.0000 0.0000 0.0000 0.0000 1.0000 0.0000 0.0000 1.0000 0.0000 0.0000 0.0000 1.0000 0.0000 0.0000
166
0.0000 0.0000 0.0000 0.0000 1.0000 0.0000 1.0000 0.0000 0.0000 0.0000 0.0000 y =
21.0000
即求得最优指派方案为x15?x23?x32?x44?x51?1，最优值为21．
7.6 建模实例:两辆平板车的装载问题
两辆平板车的装载问题（1988年美国大学数学建模竞赛B题） 一、问题的提出
有七种规格的包装箱要装到两辆铁路平板车上去，包装箱的宽和高是一样的，但厚度t（以厘米计）及重量w（以千克计）是不同的．如表7-9所示给出了每种包装箱的厚度、重量及数量．每辆平板车有10.2米长的地方可用来装包装箱（像面包片那样），载重为40吨．由于当地货运的限制，对C5、C6、C7类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7厘米．试把包装箱装到平板车上去使得浪费的空间最小．
表7-9 各种包装箱规格表
t w 件数 C1 48.7 2000 8 C2 52.0 3000 7 C3 61.3 1000 9 C4 72.0 500 6 C5 48.7 4000 6 C6 52.0 2000 4 C7 64.0 1000 8 二、问题的分析 这是一个典型的整数规划模型，如果将同类型的各个箱子区别开来，则成为0-1规划模型．
从题目可得出约束条件有： (1) 每辆车载重不超过40吨；
(2) 每辆车上载货厚度不超过1020厘米；
(3) C5、C6、C7类包装箱总厚度不能超过302.7厘米．
从表中数据可得所有箱子的总重量为89吨，厚度总和为2749.5厘米，而两辆车的最大载重为80吨，最大载货空间为2040厘米，因此不能全部装下．
三、模型建立及求解
设装在第一辆车上的箱子件数为xi，装在第二辆车上的箱子件数为yi．令
167
{t1,t2,t3,t4,t5,t6,t7}?{48.7,52.0,61.3,72.0,48.7,52.0,64.0} {w1,w2,w3,w4,w5,w6,w7}?{2,3,1,0.5,4,2,1} {n1,n2,n3,n4,n5,n6,n7}?{8,7,9,6,6,4,8} x?{x1,x2,x3,x4,x5,x6,x7} y?{y1,y2,y3,y4,y5,y6,y7}
则可得此整数规划的数学模型为：
maxz??ti(xi?yi)
i?17?xi?yi?ni,i?1,2,,7?7??wixi?40?i?1?7??wy?40?i?1ii?7?s..t??tixi?1020. ?i?1?7??tiyi?1020?i?1?7??ti(xi?yi)?302.7?i?5?i?1,2,,7?xi,yi为整数，且xi,yi?0，本题可以用分枝定界法求解，得出最优解和最优值为：
x?{4,7,4,3,0,0,0}，y?{4,0,5,3,3,3,0}，z?2039.4．
即总使用空间为2039.4厘米，浪费0.6厘米．
若将第三个条件理解为：对C5、C6、C7类的包装箱在每一辆车的空间（厚度）不能超过302.7厘米，则模型变为
maxz??ti(xi?yi)
i?17 168
?xi?yi?ni,i?1,2,,7?7??wixi?40?i?1?7??wy?40?i?1ii?7?tx?1020?ii??i?1s..t?7. ?ty?1020ii??i?1?7?tx?302.7ii??i?5?7?ty?302.7ii??i?5?i?1,2,,7??xi,yi为整数，且xi,yi?0，MATLAB程序zsgh_12.m
clc;
clear all;
jianshu=[8,7,9,6,3,3,0];
houdu_t=[48.7,52.0,61.3,72.0,48.7,52.0,64.0]; zhongliang_w=[2000,3000,500,4000,2000,2000,1000]; first_che=zeros(10,7); second_che=zeros(10,7); n=0;
for i1=1:8 for i2=1:7 for i3=1:9 for i4=1:6 for i5=1:3 for i6=1:3
i11=jianshu(1,1)-i1; i22=jianshu(1,2)-i2; i33=jianshu(1,3)-i3; i44=jianshu(1,4)-i4; i55=jianshu(1,5)-i5; i66=jianshu(1,6)-i6;
wx1=i1*zhongliang_w(1,1)+i2*zhongliang_w(1,2)+i3*zhongliang_w(1,3)+i4*zhongliang_w(1,4)+i5*zhongliang_w(1,5)+i6*zhongliang_w(1,6);
wx2=i11*zhongliang_w(1,1)+i22*zhongliang_w(1,2)+i33*zhongliang_w(1,3)+i44*zhongliang_w(1,4)+i55*zhongliang_w(1,5)+i66*zhongliang_w(1,6); %重量约束
tx1=i1*houdu_t(1,1)+i2*houdu_t(1,2)+i3*houdu_t(1,3)+i4*houdu_t(1,4)+i5*houdu_t(1,5)+i6*houdu_t(1,6);
tx2=i11*houdu_t(1,1)+i22*houdu_t(1,2)+i33*houdu_t(1,3)+i44*houdu_t(1,4)+i55*houdu_t(1,5)+i66*h