159
假设x为n维决策变量，其线性规划问题具有不等式约束m1个，等式约束m2个，则：c为n维行向量(c1,c2,,cn),x为n维列向量(x1,x2,,xn)T，b为m1维列向量，beq为m2维
列向量，A为m1?n维矩阵，Aeq为m2?n维矩阵.
与在MATLAB中使用intprog求解线性规划问题相类似，对于非MATLAB标准型，要采用相应的方法将其转化成标准型之后才能将相关参数传递给bintprog进行求解.需要注意的有两点，一点要对目标函数求极小，另一点是不等式约束为“≤”，如果不满足这两点要求，则需要对原问题进行转化.
1．输入参数
MATLAB工具箱中的bintprog函数在求解0-1规划问题时，提供的参数为模型参数，初始解参数和算法控制参数.其中模型参数x、c、b、beq、A、和Aeq在5.4.1节的MATLAB标准型中已经介绍过.
X0为线性规划问题的初始解，options为包含算法控制参数的结构变量，我们可以通过optimset命令对这些具体的控制参数进行设置.针对本章中0-1规划问题的求解函数bintprog，介绍其特有的一些参数及其设置方法，如表7-6所示.
表7-6 参数名称 BranchStrategy 参数设置 设置算法中分枝变量的选择策略，当该参数值为mininfeas时，选择最可能为整数的变量进行分枝，即分枝变量最接近0或1，但不等于0或1；当该参数值为maxinfeas(默认)时，选择最不可能为整数的变量进行分枝，即分枝变量最接近0.5 MaxIter 设置算法运行中的最大迭代次数，默认值为100000*设计变量的个数 MaxNodes MaxRLPIter 设置算法搜索的最大节点数，默认值为1000*设计变量的个数 设置算法在求解各个节点的松弛线性规划问题时的最大迭代次数，默认值为100*设计变量的个数 MaxTime NodeDisplayInterval 设置算法运行的最大CPU时间，以秒为单位，默认值为7200s 设置节点显示区间.即在每次显示迭代报告之前搜索节点的数目.默认值为20 160
NodeSearchStrategy TolFun TolXInteger 设置算法中分枝节点的选择策略，当该参数值为df时为深度优先搜索，即选择最下层的孩子节点进行分枝；当该参数值为bn（默认）时为广度优先搜索，即选择目标函数值最优的节点进行分枝 函数计算终止的误差限，其默认值为1e-3 设置判断一个数值是否为正整数的误差限，默认值为1.0e-8，即如果一个数和与其最邻近的正整数之差小于1.0e-8，则被认为是该正整数 TolRLPFun 设置求解松弛线性规划问题的目标函数计算终止误差限，默认值为 1.0e-6 Diagnostics 设置是否显示函数优化中的诊断信息，可以选择on或者off（默认值），该功能主要显示一些退出信息，即bintprog函数运算终止的原因 设置显示信息的级别，当该参数值为off时 ，不显示任何输出信息；当参数值为iter时，将显示每一步迭代的输出信息，iter参数值仅对大型规模算法和中型规模的单纯形算法有效；当参数值为final时，仅显示最终的输出信息 Display 2．输出参数
Bintprog函数返回的输出参数有x,fval,exitflag和output、x和为0-1问题的最优解，fval为0-1规划问题在最优解x处的函数值.
Exitflag返回的是bintprog计算终止时的状态指示，说明算法终止的原因，其取值和其代表的具体原因如表7-7所示.
表7-7 参数exitflag 的物理意义 值 1 0 -2 -4 -5 -6 已经收敛到解x 已经达到最大迭代次数限制options.MaxIter 优化问题无可行解 搜索节点数超过设置的最大节点数 搜索时间超过设置的最大CPU时间options.MaxTime. 在求解某节点的线性松弛问题时进行迭代的次数超过算法设置的在求解各个节点的松弛线性规划问题时的最大迭代次数options.MaxRLP 输出参数output是一个返回优化过程中的相关信息的结构变量，它所包含的的属性及属性代表的意义如表7-8所示.
表7-8 参数output 所包含的的信息
属性名称 属性含义 物理意义 161
output.iterations output.algorithm output.nodes output.time output.nodeSearchStrategy output.message 优化过程的实际迭代次数 优化过程中所采用的具体算法 优化过程中搜索过的节点数目 优化过程中执行算法消耗的CPU时间 优化过程中选择分枝节点的策略 退出信息 output.branchStrategy 优化过程中选择分枝变量的策略 3、命令译解 下面结合bintprog 函数的调用方式和具体参数的含义，说明在MATLAB中如何使用bintprog函数求解线性规划问题.
1）x=bintprof(f)
该函数用格式求解如下的0-1规划问题：
minf?cxs..tx?0,1. 2）x=bintprog(c,A,b)
该函数用格式求解如下的0-1规划问题：
minf?cx?Ax?b s..t?.?x?0,1即在求解1）的基础上添加了不等式约束Ax≤b的0-1规划问题. 3）x=bintprog(c,A,b,Aeq,beq)
该函数用格式求解如下的0-1规划问题：
minf?cx?Ax?b?s..t?Aeq?x?beq. ?x?0,1? 即在求解2）的基础上添加了等式约束Aeq?x?beq的0-1规划问题. 4）x=bintprog(c,A,b,Aeq,beq,x0)
该函数调用格式求解如下形式的0-1规划问题：
minf?cx?Ax?b?s..t?Aeq?x?beq. ?x?0,1? 同时设置求解算法的初始解为x0,如果初始解x0不在0-1规划问题的可行域中，算法将采用默认的初始解.
5）x=bintprog(c,A,b,Aeq,beq,x0,options)
162
用options指定的优化参数进行最小化.可以使用optimset来设置这些参数，其中常用的可设置参数如表5-3所示.
上面的函数调用格式仅仅设置了最优解这一个输出参数，如果需要更多的输出参数，则可以参照下面的调用格式：
[x,fval] = bintprog(...)
在优化计算结束之时返回整数规划问题在解x处的目标函数值fval. [x,fval,exitflag ] = bintprog(...)
在优化计算结束之时返回exitflag值，描述函数计算的退出条件。Exitflag的意义如表5-4所示.
[x , fval, exitflag , output ] = bintprog(...)
在优化计算结束之时返回结构变量output，output的意义如表5-5所示.
0-1规划bintprog的使用要点与线性规划函数linprog的使用要点相同，不重述．
函数bintprog是为求目标函数的最小值而设置的，如需求目标函数f的最大值，则需用函数bintprog求（-f）的最小值，它给出的f的最大值．
例7.17 求解下述0-1规划问题 maxz?x1?2x2?2x3-6x4-4x5
?3x1?2x2-x3?x4?2x5?5?t?2x1?4x2-2x3-x4-2x5?5. s..?x?0或1(i?1,...,5)?i解 编写M文件zsgh_6.m： f=[-1,-2,-2,6,4]';
A=[3,2,-1,1,2;2,4,-2,-1,-2]; b=[5;5];
[x,fval,exitflag,output]=bintprog(f,A,b,[],[]) 上述程序执行之后，求得： ex=1,fv=-5,以及 x=[1,1,1,0,0]
由此得到例7.17的解为：
x1=1，x2=1，x3=1，x4=0，x5=0
目标函数取最大值5.
例7.18 求解下述0-1规划的问题
minz?3x1+7x2-x3?x4
?2x1-x2?x3-x4?1?x-x?6x?4x?8?1234s.t.?
5x?3x?x?5524???xi?0或1(i?1,2,3,4)解 先将约束写成标准形式：
163
-2x1?x2-x3?x4?-1 -x1?x2-6x3-4x4?-8
-5x1-3x2-x4?-5下面给出本题的计算程序zsgh_7.m: f=[3,7,-1,1]’;
a=[-2,1,-1,1;-1,1,-6,-4]; a=[a;-5,-3,0,-1]; b=-[1,8,5]’;
[x,fv,ex]=bintprog(f,a,b,[],[]); ex=1,fv=3,以及 x=[1,0,1,1]’
由此得到例7.18的解为：
当x1=1，x2=0，x3=1，x4=1时，目标函数取最小值3.
例7.19 例7.7资金分配问题MATLAB程序求解. 解 编写M文件zsgh_8.m: f=-[20,40,20,15,30]’;
a=[5,4,3,7,8;1,7,9,4,6;8,10,2,1,10]; b=[25,25,25]’;
[x,fv,ex]=bintprog(f,a,b,[],[]); 上述的程序执行后，求得 ex=1,fv=-95,以及 x=[1,1,1,1,0]’
上述计算结果表明，企业选择第一、第二、第三、第四项工程，能获最大收入95千元．
例7.20 例7.8选课策略MATLAB程序求解. 解 编写M文件zsgh_9.m: f=ones(7,1);
A=[1,1,1,1,0,0,1;0,1,0,1,1,0,1];
A=[A;0,0,1,0,1,1,0;1,0,0,-1,0,0,0,0]; A=[A;0,0,0,1,0,0,-1]; A=-A;
b=[-2,-2,-2,0,0,0,0]’;
[x,fval,exitflag,output]=bintprog(f,A,b[],[]) 程序执行后,输出如下： Optimization terminated. x= 0 1 1 0 1 1