function [x,y]=lpint(f,G,h,lb,ub,x,n,id) % 整数线性规划分枝定界法，可求解线性全整数或线性混合整数规划% 此程序基于Matlab优化工具箱的lp函数写成 % 此程序为GreenSim团队原创作品，转载请注明 % 欢迎访问GreenSim团队的主页https://www.doczj.com/doc/b016868444.html,/greensim % y = min f'x subject to: Gx <= h x为整 % x % 用法 % [x,y]=lpint(f,G,h) % [x,y]=lpint(f,G,h,lb,ub) % [x,y]=lpint(f,G,h,lb,ub,x) % [x,y]=lpint(f,G,h,lb,ub,x,n) % [x,y]=lpint(f,G,h,lb,ub,x,n,id) % 参数说明 % x: 最优解列向量 % y: 目标函数最小值 % f: 目标函数系数列向量 % G: 约束条件系数矩阵 % h: 约束条件右端列向量 % lb: 解的的下界列向量(Default: -inf) % ub: 解的的上界列向量(Default: inf) % x: 迭代初值列向量 % n: 等式约束数(Default: 0) % id: 整数变量指标列向量。1-整数，0-实数(Default: 1) % 举例 % min Z=x1+4x2 % s.t. 2x1+x2<=8 % x1+2x2>=6 % x1, x2>=0且为整数 %先将x1+2x2>=6化为 - x1 - 2x2<= -6 %》[x,y]=lpint([1;4],[2 1;-1 -2],[8;-6],[0;0]) % Y. MA & L.J. HU 1999 global upper opt c N x0 A b ID; if nargin<8, id=ones(size(f));end if nargin<7|isempty(n), n=0;end if nargin<6, x=[];end if nargin<5|isempty(ub), ub=inf*ones(size(f));end if nargin<4|isempty(lb), lb=zeros(size(f));end
题目：割平面法及其数值实现 院系：数理科学与工程学院应用数学系 专业：数学与应用数学 姓名学号：*** 1****** *** 1****** *** 1****** *** 1****** 指导教师：张世涛 日期：2015 年 6 月11 日
整数规划与线性规划有着密不可分的关系，它的一些基本算法的设计都是从相应的线性规划的最优解出发的。整数规划问题与我们的实际生活有着密切的联系，如合成下料问题、建厂问题、背包问题、投资决策问题、旅行商问题、生产顺序表问题等都是求解整数模型中的著名问题。所以要想掌握生活中这些解决问题的方法，研究整数规划是必然的路径。用于解决整数规划的方法主要有割平面法，分支定界法，小规模0-1规划问题的解法，指派问题和匈牙利法。本文重要对整数规划中经常用的割平面法加以介绍及使用Matlab 软件对其数值实现。 割平面法从线性规划问题着手,在利用单纯型法的时候,当约束矩阵中出现分数,给出一种"化分为整"的方法。然后在割平面方法来解决整数线性规划的理论基础上,把"化分为整"的方法进行到底，直到求解出最有整数解。 关键词：最优化；整数规划；割平面法；数值实现；最优解；Matlab软件。 Abstract The integer programming are closely related to the linear programming. Some of the basic algorithms of the former are designed from the optimal solution of the corresponding linear programming. What’s more, our daily life has a close relationship with it as well, such as synthesis problem, plant problem, knapsack problem, investment decision problem, traveling salesman problem and production sequence table problems. They are famous questions in solving integer model. So, to study the integer programming is the inevitable way to master the methods of solving these problems in life. The methods used in solving the integer programming include cutting plane method, branch and bound method, and solving the problem of small-scale 0-1 programming, assignment problem and Hungarian method. In this paper, we introduce the cutting plane method and use Matlab to get its numerical implementation in the integer programming. Cutting plane method, giving us a "integrated" method when we meet the constraint matrix scores in the use of simplex method, starts from the linear programming problem. Then, based on the theory of cutting plane method to solve the integer linear programming, we use “integrated” method until the most integer solution is solved. Keywords:Optimization; Integer programming; Cutting plane method; Numerical implementation; Optimal solution; Matlab software.
整数规划分支定界算法matlab通用源程序 %整数规划分支定界算法matlab通用源程序 %各参数的意义同matlab优化工具箱的线性规划函数linprog %调用前，输入参数要化成matlab的标准形式 [x,val]=kfz-f-3(n,f,a,b,aeq,beq,lb,ub) x=zeros(n,1); x1=zeros(n,1); m1=2; m2=1; [x1,val1]=linprog(f,a,b,aeq,beq,lb,ub); if (x1==0) x=x1; val=val1; elseif (round(x1)==x1) x=x1; val=val1; else e1={0,a,b,aeq,beq,lb,ub,x1,val1}; e(1,1)={e1}; zl=0; zu=-val1; while (zu~=zl) for c=1:1:m2 if (m1~=2) if (cell2mat(e{m1-1,c}(1))==1) e1={1,[],[],[],[],[],[],[],0}; e(m1,c*2-1)={e1}; e(m1,c*2)={e1}; continue; end; end; x1=cell2mat(e{m1-1,c}(8)); x2=zeros(n,1); s=0; s1=1; s2=1; lb1=cell2mat(e{m1-1,c}(6)); ub1=cell2mat(e{m1-1,c}(7)); lb2=cell2mat(e{m1-1,c}(6)); ub2=cell2mat(e{m1-1,c}(7)); for d=1:1:n if (abs((round(x1(d))-x1(d)))>0.0001)&(s==0) s=1;
期末考试《运筹学》B 卷 一、单项选择题（在下列每题的四个选项中，只有一个选项是符合试题要求的。请把答案填入答题框中相应的题号下。每小题2分，共20分） 1．单纯形迭代中，出基变量在紧接着的下一次迭代中（ ）立即进基。 A ．会 B ．不会 C ．有可能 D ．不一定 2．线性规划的约束条件为 X 1 + X 2 + X 3 = 3 ，2X 1+ 2X 2+ X 4= 4，X i ≥0（i=1-4）,则基本可行解是（ ） A ．（0，0，4， 3） B ．（0，0，3，4） C ．（2，1，0，-2） D ．（3，0，0，-2） 3．普通单纯形法的最小比值定理的应用是为了保证（ ） A ．使原问题保持可行 B ．使对偶问题保持可行 C ．逐步消除原问题不可行性 D ．逐步消除对偶问题的不可行性 4. 原问题与对偶问题都有可行解，则有（ ） A ．原问题有最优解，对偶问题可能没有最优解 B ．原问题与对偶问题可能都没有最优解 C ．可能一个问题有最优解，另一个问题具有无界解 D ．原问题与对偶问题都具有最优解 5. 求解整数规划问题的分支定界法中，有（ ） A ．最大值问题的目标值是各分支的上界 B ．最大值问题的目标值是各分支的下界 C ．最小值问题的目标值是各分支的上界 D ．以上结论都不对 6．在运输方案中出现退化现象，是指数字格的数目 （ ） A ．等于 m+n B ．等于m+n-1 C ．小于m+n-1 D ．大于m+n-1 7．若运输问题的单位运价表的某一行元素分别加上一个常数k ，最优调运方案将（ ）。 A ．发生变化 B ．不发生变化 C ．A 、B 都有可能 D. 都不对 8．在产销平衡运输问题中，设产地为m 个，销地为n 个，那么解中非零 变量的个数（ ）。 A ．不能大于(m+n-1) B ．不能小于(m+n-1) C ．等于(m+n-1) D ．不确定 9．在运输问题中，每次迭代时，如果有某非基变量的检验数等于零，则该运输问题（ ）。 A ．无最优解 B ．有无穷最优解 C ．有唯一最优解 D ．出现退化解 10．动态规划问题中最优策略具有性质：（ ）。 A ．每个阶段的决策都是最优的 B ．当前阶段以前的各阶段决策是最优的 C ．无论初始状态与初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略 D ．它与初始状态无关 二、判断题（每题1分,共10分）
分支定界法和割平面法 在上学期课程中学习的线性规划问题中，有些最优解可能是分数或消失，但现实中某些 具体的问题，常要求最优解必须是整数，这样就有了对于整数规划的研究。 整数规划有以下几种分类：（1）如果整数规划中所有的变量都限制为（非负）整数，就 称为纯整数规划或全整数规划；（2）如果仅一部分变量限制为整数，则称为混合整数规划； （3）整数规划还有一种特殊情形是0-1规划，他的变量取值仅限于0或1。本文就适用于 纯整数线性规划和混合整数线性规划求解的分支定界法和割平面法，做相应的介绍。 一、分支定界法 在求解整数规划是，如果可行域是有界的，首先容易想到的方法就是穷举变量的所有可行的整数组合，然后比较它们的目标函数值以定出最优解。对于小型问题，变量数量很少，可行的整数组合数也是很小时，这个方法是可行的，也是有效的。而对于大型的问题，可行的整数组合数很大时，这种方法就不可取了。所以我们的方法一般是仅检查可行的整数组合的一部分，就能定出最有的整数解。分支定界法就是其中一个。 分枝定界法可用于解纯整数或混合的整数规划问题。在二十世纪六十年代初 由Land Doig和Dakin等人提出。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。 设有最大化的整数规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作z ；而A的任意可行解的目标函数值将是z*的一个下界z。分枝定界法就是将B的可行域分成子区域再求其最大值的方法。逐步减小z和增大z，最终求到z*。现用下例来说明：例1求解下述整数规划 Max z = 40x「90x2 9X1 7X2 -56 7X1 20X2 - 70 x1,x2 -0 且为整数 解（1）先不考虑整数限制，即解相应的线性规划B，得最优解为： 洛=4.81,x2= 1.82, z 二356 可见它不符合整数条件。这时z是问题A的最优目标函数值z*的上界，记作z。而X1=0, X2=0显然是问题A的一个整数可行解，这时z = 0，是z*的一个下界，记作z，即0w z*< 356。 （2）因为X1X2当前均为非整数，故不满足整数要求，任选一个进行分枝。设选X1进行分枝，于是对原问题增加两个约束条件： x, -〔4.81 丨-4“ 一〔4.811 1 =5 于是可将原问题分解为两个子问题B1和B2 （即两支），给每支增加一个约束条件并不影响问题
1、概念： 分支定界算法(Branch and bound，简称为BB、B&B, or BnB)始终围绕着一颗搜索树进行的，我们将原问题看作搜索树的根节点，从这里出发，分支的含义就是将大的问题分割成小的问题。大问题可以看成是搜索树的父节点，那么从大问题分割出来的小问题就是父节点的子节点了。分支的过程就是不断给树增加子节点的过程。而定界就是在分支的过程中检查子问题的上下界，如果子问题不能产生一比当前最优解还要优的解，那么砍掉这一支。直到所有子问题都不能产生一个更优的解时，算法结束。 2、例子： 用BB算法求解下面的整数规划模型 因为求解的是最大化问题，我们不妨设当前的最优解BestV为-INF，表示负无穷。 1.
首先从主问题分出两支子问题： 通过线性松弛求得两个子问题的upper bound为Z_LP1 = 12.75，Z_LP2 = 12.2。由于Z_LP1 和Z_LP2都大于BestV=-INF，说明这两支有搞头，继续往下。 2. 3.
从节点1和节点2两个子问题再次分支，得到如下结果： 子问题3已经不可行，无需再理。子问题4通过线性松弛得到最优解为10，刚好也符合原问题0的所有约束，在该支找到一个可行解，更新BestV = 10。 子问题5通过线性松弛得到upper bound为11.87>当前的BestV = 10，因此子问题5还有戏，待下一次分支。而子问题6得到upper bound为9<当前的BestV = 10，那么从该支下去找到的解也不会变得更好，所以剪掉！ 4.
对节点5进行分支，得到： 子问题7不可行，无需再理。子问题8得到一个满足原问题0所有约束的解，但是目标值为4<当前的BestV=10，所以不更新BestV，同时该支下去也不能得到更好的解了。 6.
整数规划分支定界法MATLAB程序 1.这种方法绝对能都解出答案，而且答案正确 function [x,val]=fzdj(n,f,a,b,aeq,beq,lb,ub) x=zeros(n,1); x1=zeros(n,1); m1=2; m2=1; [x1,val1]=linprog(f,a,b,aeq,beq,lb,ub); if (x1==0) x=x1; val=val1; elseif (round(x1)==x1) x=x1; val=val1; else e1={0,a,b,aeq,beq,lb,ub,x1,val1}; e(1,1)={e1}; zl=0; zu=-val1; while (zu~=zl) for c=1:1:m2 if (m1~=2) if (cell2mat(e{m1-1,c}(1))==1) e1={1,[],[],[],[],[],[],[],0}; e(m1,c*2-1)={e1}; e(m1,c*2)={e1}; continue; end; end; x1=cell2mat(e{m1-1,c}(8)); x2=zeros(n,1); s=0; s1=1; s2=1; lb1=cell2mat(e{m1-1,c}(6)); ub1=cell2mat(e{m1-1,c}(7)); lb2=cell2mat(e{m1-1,c}(6)); ub2=cell2mat(e{m1-1,c}(7)); for d=1:1:n if (abs((round(x1(d))-x1(d)))>0.0001)&(s==0) s=1; lb1(d)=fix(x1(d))+1;
Linprogdis子程序: function [x,fval,exitflag,output,lambda]=... linprogdis(ifint,f,A,b,Aeq,beq,lb,ub,x0,options) %Title: % 分支定届法求解混合整数线性规划模型 % %初步完成：2002年12月 %最新修订: 2004-03-06 %最新注释：2004-11-20 %数据处理 [t1,t2] = size(b); if t2~=1, b=b';%将b转置为列向量 end %调用线性规划求解 [x,fval,exitflag,output,lambda] = linprog(f,A,b,Aeq,beq,lb,ub,x0,options); if exitflag<=0,%如果线性规划失败，则本求解也失败 return end %得到有整数约束的决策变量的序号 v1=find(ifint==1);%整数变量的index tmp=x(v1);%【整数约束之决策变量】的当前值 if isempty(tmp), %无整数约束，则是一般的线性规划，直接返回即可 return end v2=find(checkint(tmp)==0);%寻找不是整数的index if isempty(v2), %如果整数约束决策变量确实均为整数，则调用结束 return end %第k个决策变量还不是整数解 %注意先处理第1个不满足整数约束的决策变量 k=v1(v2(1)); %分支1：左分支 tmp1=zeros(1,length(f));%线性约束之系数向量 tmp1(k)=1; low=floor(x(k)); %thisA 分支后实际调用线性规划的不等式约束的系数矩阵A %thisb 分支后实际调用线性规划的不等式约束向量b if ifrowinmat([tmp1,low],[A,b])==1 %如果分支的约束已经存在旧的A，b中，则不改变约束 thisA= A; thisb= b;
整数规划分支定界法MATLAB 程序 1.这种方法绝对能都解出答案，而且答案正确function [x,val]=fzdj(n,f,a,b,aeq,beq,lb,ub) x=zeros(n,1); x1=zeros(n,1); m1=2; m2=1; [x1,val1]=linprog(f,a,b,aeq,beq,lb,ub); if (x1==0) x=x1; val=val1; elseif (round(x1)==x1) x=x1; val=val1; else e1={0,a,b,aeq,beq,lb,ub,x1,val1}; e(1,1)={e1}; zl=0; zu=-val1; while (zu~=zl) for c=1:1:m2 if (m1~=2) if (cell2mat(e{m1-1,c}(1))==1) e1={1,[],[],[],[],[],[],[],0}; e(m1,c*2-1)={e1}; e(m1,c*2)={e1}; continue; end; end; x1=cell2mat(e{m1-1,c}(8)); x2=zeros(n,1); s=0; s1=1; s2=1; lb1=cell2mat(e{m1-1,c}(6)); ub1=cell2mat(e{m1-1,c}(7)); lb2=cell2mat(e{m1-1,c}(6)); ub2=cell2mat(e{m1-1,c}(7)); for d=1:1:n if (abs((round(x1(d))-x1(d)))>0.0001)&(s==0) s=1; lb1(d)=fix(x1(d))+1; if (a*lb1<=b) s1=0; end; ub2(d)=fix(x1(d)); if (a*lb2<=b) s2=0; end; end; end; e1={s1,a,b,aeq,beq,lb1,ub1,[],0}; e2={s2,a,b,aeq,beq,lb2,ub2,[],0}; e(m1,c*2-1)={e1}; e(m1,c*2)={e2}; end; m1=m1+1;
分支定界法和割平面法 在上学期课程中学习的线性规划问题中，有些最优解可能是分数或消失，但现实中某些具体的问题，常要求最优解必须是整数，这样就有了对于整数规划的研究。 整数规划有以下几种分类：（1）如果整数规划中所有的变量都限制为（非负）整数，就称为纯整数规划或全整数规划；（2）如果仅一部分变量限制为整数，则称为混合整数规划；（3）整数规划还有一种特殊情形是0-1规划，他的变量取值仅限于0或1。本文就适用于纯整数线性规划和混合整数线性规划求解的分支定界法和割平面法，做相应的介绍。 一、分支定界法 在求解整数规划是，如果可行域是有界的，首先容易想到的方法就是穷举变量的所有可行的整数组合，然后比较它们的目标函数值以定出最优解。对于小型问题，变量数量很少，可行的整数组合数也是很小时，这个方法是可行的，也是有效的。而对于大型的问题，可行的整数组合数很大时，这种方法就不可取了。所以我们的方法一般是仅检查可行的整数组合的一部分，就能定出最有的整数解。分支定界法就是其中一个。 分枝定界法可用于解纯整数或混合的整数规划问题。在二十世纪六十年代初由Land Doig 和Dakin 等人提出。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。 设有最大化的整数规划问题A ，与它相应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z *的上界，记作z ；而A 的任意可行解的目标函数值将是z *的一个下界z 。分枝定界法就是将B 的可行域分成子区域再求其最大值的方法。逐步减小z 和增大z ，最终求到z *。现用下例来说明： 例1 求解下述整数规划 219040Max x x z += ??? ??≥≥+≤+且为整数0,7020756792 12121x x x x x x 解 （1）先不考虑整数限制，即解相应的线性规划B ，得最优解为： 124.81, 1.82,356 x x z === 可见它不符合整数条件。这时z 是问题A 的最优目标函数值z *的上界，记作z 。而X 1=0，X 2=0显然是问题A 的一个整数可行解，这时0=z ，是z * 的一个下界，记作z ，即0≤z *≤356 。 （2）因为X 1X 2当前均为非整数，故不满足整数要求，任选一个进行分枝。设选X 1进行分枝，于是对原问题增加两个约束条件： [][]114.814, 4.8115 x x ≤=≥+= 于是可将原问题分解为两个子问题B 1和B 2（即两支），给每支增加一个约束条件并不影响问题A 的可行域，不考虑整数条件解问题B 1和 B 2 ，称此为第一次迭代。得到最优解
整数线性规划之分支定界法 摘要 最优化理论和方法是在上世纪 40 年代末发展成为一门独立的学科。1947年，Dantaig 首先提出求解一般线性规划问题的方法，即单纯形算法，随后随着工业革命、计算机技术的巨大发展，以及信息革命的不断深化，到现在的几十年时间里，它有了很快的发展。目前，求解各种最优化问题的理论研究发展迅速，例如线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等，各种新的方法也不断涌现，并且在军事、经济、科学技术等方 面应用广泛，成为一门十分活跃的学科。 整数规划（integer programming）是一类要求要求部分或全部决策变量取整数值的数学规划，实际问题中有很多决策变量是必须取整数的。本文主要介绍求解整数线性规划问题的分支定界法及其算法的matlb实现。 关键词：整数线性规划；分支定界法；matlb程序；
1．引言 1.1优化问题发展现状 最优化理论与算法是一个重要的数学分支，它所讨论的问题是怎样在众多的方案中找到一个最优的方案.例如，在工程设计中，选择怎样的设计参数，才能使设计方案既满足要求又能降低成本；在资源分配中，资源有限时怎样分配，才能使分配方案既可以满足各方面的要求，又可以获得最多的收益；在生产计划安排中，怎样设计生产方案才能提高产值和利润；在军事指挥中，确定怎样的最佳作战方案，才能使自己的损失最小，伤敌最多，取得战争的胜利；在我们的生活中，诸如此类问题，到处可见.最优化作为数学的一个分支，为这些问题的解决提供了一些理论基础和求解方法. 最优化是个古老的课题.长期以来，人们一直对最优化问题进行着探讨和研究.在二十世纪四十年代末，Dantzig 提出了单纯形法，有效地解决了线性规划问题，从而最优化成为了一门独立的学科。目前，有关线性规划方面的理论和算法发展得相当完善,但是关于非线性规划问题的理论和算法还有待进一步的研究，实际应用中还有待进一步的完善。传统的非线性全局最优化方法只能求出问题的局部最优解，但由于许多问题的局部最优解不一定是全局最优解，使得传统的非线性最优化方法不能直接成功地应用于求解非线性全局最优化问题。另外，没有一个固定的评判标准来判断得到的局部最优解是否为全局最优解。随着科学技术的发展和计算机计算能力的提高，最优化理论在最近这几年来得到了迅速的发展，涌现出了许多新的算法, 如打洞函数法,填充函数法，lagrangian 乘子函数方法，信赖域方法，虑子方法等。 本文主要介绍求解整数线性规划问题的分支定界法及其算法的matlb实现。 1.2整数线性规划及其数学模型 整数规划主要有以下三大类： （1）全整数规划（all integer programming）：所有的决策变量都取整数值，也称为纯整数规划（pure integer programming）； （2）混合整数规划（mixed integer programming）：仅要求一部分决策变量取整数值； （3）0-1规划（zero-one integer programming）：该类问题的决策变量只能取0或1. 本文主要讨论的整数线性规划问题模型为：
一．线性规划 1.问题背景：线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人 们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源. 线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题 2.求解方法： a.单纯形法： 适用的问题：约束条件全部为≤，右边常数全部为非负，对目标函数的系数没有要求。 min z=3x1-2x2 s.t. x1+2x2≤12 2x1+ x2≤18 x1,x2≥0 求解步骤： STEP 0 将线性规划问题标准化 STEP 1 是否有明显的初始基础可行解，如果有，转STEP 3，否则，转STEP 2。 STEP 2 构造辅助问题，用两阶段法求解辅助问题。如果辅助问题最优解的目标函数值大于0，原问题无可行解，算法终止。否则转STEP 3。 STEP 3 写出单纯形表，将基变量在约束条件中的系数消为单位矩阵，将基变量在目标函数中的系数消为0。转STEP 4。 STEP 4 如果所有非基变量的检验数全为负数或0，则已获得最优解，算法终止。否则，选择检验数为正数并且绝对值最大的非基变量为进基变量。转STEP 5。 STEP 5 如果进基变量在约束条件中的系数全为负数或0，目标函数无界，算法终止。否则根据右边常数和正的系数的最小比值，确定离基变量。转STEP 6。 STEP 6 进基变量列和离基变量行交叉的元素称为主元。对单纯形表进行行变换，将主元变为1，将主元所在列的其他元素变为0。转STEP 4。 b.对偶单纯形法： 适用的问题:约束条件中至少有一个是≥，相应的右边常数为非负，目标函数系数全部为非负。 min z=3x1+2x2 s.t. x1+2x2≥12 2x1+ x2≤18 x1,x2≥0 求解步骤： 步骤1 确定原问题（L）的初始基B，使所有检验数，即是对偶可行解，建立初始单纯形表。 步骤2 检查基变量的取值，若≥0，则已得最优解，计算停；否则求确定单纯形表第L行对应的基变量为旋出变量。 步骤3 若所有,则原问题无可行解，计算停；否则，计算确定对应的为旋入变量。 步骤4 以为主元作（L，K）旋转变换，得新的单纯形表，转步骤2。可以证明，按上述方法进行迭代，所得解始终是对偶可行解。 二．运输问题 1.问题背景：一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产 地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。
缺点： 某些变量要求整数 不能运用到对数，指数函数中 分支界定法： 分枝定界法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。 分枝定界法已经成功地应用于求解整数规划问题、生产进度表问题、货郎担问题、选址问题、背包问题以及可行解的数目为有限的许多其它问题 割平面法： 它的基本思想和分枝界定法基本上一致，首先不考虑变量的整数约束，利用单纯形法求解出线性规划的最优解，如果得到的解是整数那么这个最优解就是原来问题的最优解，如果最优解不是整数解，则就用一张平面将原来的含有最优解的非整数点但不包含整数可行解的点的那一部分可行域切割掉，也就是在原来的整数线性规划的基础上增加适当的线性约束不等式，这个约束不等式就叫切割不等式当其取等号时就是割平面了。此后，继续解这个新得到的整数线性规划，如果得到的新最优解是整数，运算就停止，如果不是整数则继续增加适当的线性约束不等式，直到求出的解满足最优整数要求为止。 通过构造一系列平面来切割掉不含有任何整数可行解的部分，最终获得一个具有整数坐标的顶点的可行域，而该顶点恰好是原整数规划的最优解。割平面法的关键在于，如何构造切割不等式，使增加该约束后能达到真正的切割而且没有切割掉任何整数可行解。 单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。
分支定界法Matlab 程序实现与验证 为了更深入理解分支定界法计算流程，从而决定花费几天时间仔细学习该算法，并编写出该算法的Matlab 计算程序。同时为了后面个人的借鉴学习，编写本文档。在进行分支定界法计算程序编写过程中，通过网络搜索，发现了Matlab2014版之后嵌入了混合整数线性规划求解函数intlinprog，从而也将该函数的使用方法撰写下来。 1 整数规划问题简介 在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常有要求解答必须是整数的情形(称为整数解)。例如：所求解是机器的台数、完成工作的人数或装货的车数等，分数或小数的解答就不合要求。为了满足整数解的要求，初看起来，似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以了。但这常常是不行的，因为化整后不见得是可行解；或虽是可行解，但不一定是最优解。因此，对求最优整数解的问题，有必要另行研究。人们称这样的问题为整数规划(Integer Programming，IP)，整数规划是最近几十年发展起来的规划论中的一个分支。 整数规划中如果所有的变数都限制为(非负)整数，就称为纯整数规划(Pure Integer Programming，PIP)或称为全整数规划(All Integer Programming，AIP)；如果仅一部分变数限制为整数，则称为混合整数计划(Mixed Integer Programming，MIP)。整数规划的一种特殊情形是0-1规划，该规划中变量的取值仅限于0或1，指派问题就是一类典型的0-1规划问题。 现举例说明用前述单纯形法求得的解不能保证是整数最优解。 例1：某厂拟用集装箱托运甲乙两种货物, 每箱的体积、重量、可获利润以及托运所受限制如表1所示。问两种货物各托运多少箱, 可使获得利润为最大? 表1 货物托运示例数据 货物 体积（m3/箱） 重量（百公斤/箱）利润（百元/箱） 甲 5 2 20 乙 4 5 10 托运限制 24（m3） 13百公斤 设1x 、2x 分别为甲、乙两种货物的托运箱数（为非负整数），列该问题的纯 整数规划模型如下： 12max 2010z x x =+
一、编程 利用Matlab的线性规划指令： [x,fval]=linprog(f,A,b,Aeq,beq,lb,ub) 编写计算整数规划函数，输入与输出与上述指令相同 分枝定界法（递归实现） function [x,fval,status] = intprog(f,A,B,I,Aeq,Beq,lb,ub,e) %整数规划求解函数 intprog() % 其中 f为目标函数向量 % A和B为不等式约束 Aeq与Beq为等式约束 % I为整数约束 % lb与ub分别为变量下界与上界 % x为最优解，fval为最优值 %例子: % maximize 20 x1 + 10 x2 % S.T. % 5 x1 + 4 x2 <=24 % 2 x1 + 5 x2 <=13 % x1, x2 >=0 % x1, x2是整数 % f=[-20, -10]; % A=[ 5 4; 2 5]; % B=[24; 13]; % lb=[0 0]; % ub=[inf inf]; % I=[1,2]; % e=0.000001; % [x v s]= IP(f,A,B,I,[],[],lb,ub,,e) % x = 4 1 v = -90.0000 s = 1 % 控制输入参数 if nargin < 9, e = 0.00001; if nargin < 8, ub = []; if nargin < 7, lb = []; if nargin < 6, Beq = []; if nargin < 5, Aeq = []; if nargin < 4, I = [1:length(f)]; end, end, end, end, end, end %求解整数规划对应的线性规划,判断是否有解 options = optimset('display','off'); [x0,fval0,exitflag] = linprog(f,A,B,Aeq,Beq,lb,ub,[],options); if exitflag < 0
实验5 整数规划求解的分支定界法的编程实现 专业班级数学学姓名报告日期. 实验类型：●验证性实验○综合性实验○设计性实验 实验目的：熟练整数规划求解的分支定界法。 实验内容：整数规划求解的分支定界法2个（题目自选1个混合整数规划、1个0-1整数规划） 实验原理整数规划求解的分支定界法，首先确定目标函数的一个初始上下界，然后通过逐步分支使上界减小，下界增大，直到两者相等时，就求出了最优值和最优解。 实验步骤 1 要求上机实验前先编写出程序代码 2 编辑录入程序 3 调试程序并记录调试过程中出现的问题及修改程序的过程 4 经反复调试后，运行程序并验证程序运行是否正确。 5 记录运行时的输入和输出。 预习编写程序代码： 实验报告：根据实验情况和结果撰写并递交实验报告。 实验总结： 参考程序 第一题：混合整数规划
①在lingo中写入如下代码，运行。 max=3*x1+2*x2; 2*x1+3*x2<=14; 2*x1+x2<=9; @gin(x1); @gin(x2); ②结果如下： Global optimal solution found. Objective value: 14.00000 Objective bound: 14.00000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 3 Variable Value Reduced Cost X1 4.000000 -3.000000 X2 1.000000 -2.000000 Row Slack or Surplus Dual Price 1 14.00000 1.000000 2 3.000000 0.000000 3 0.000000 0.000000 可知，最优值为14。此时，x1取4，x2取1。 第二题0-1整数规划 ①在lingo中写入如下代码，运行。 min=2*x1+5*x2+3*x3+4*x4; -4*x1+x2+x3+x4>=0; -2*x1+4*x2+2*x3+4*x4>=4; x1+x2-x3+x4>=1; @bin(x1); @bin(x2); @bin(x3); @bin(x4); ②结果如下： Global optimal solution found. Objective value: 4.000000 Objective bound: 4.000000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost
分支定界法 分支定界法，顾名思义，就是按照定好的界进行分支。这里说的分支意思是“剪枝”。剪的枝是问题解空间树的枝。所谓解空间树，即此问题所有解和中间解形成的树型结构，是有序的。常有排列树和子集树之分，举个例子，n个物品的0-1背包问题的解空间树就是子集树(每个物品都可能为0或1)，而最短路径问题的解空间树是一颗排列树。 分支定界法一般有两种实现形式：1.优先队列法2.FIFO队列法。这与分支定界的思想无太多本质联系，只是前者在一般情况下能更快的求得问题解。分支定界法要对问题的解空间树进行“剪枝”操作以减少对解空间树的搜索。那么问题是，如何“剪枝”？这就要回答如何定界的问题。在分支定界法中，“界”的作用就是用来阻止对不可行分支的搜索的。当解空间树很深时（叶子节点为解），如果能在前面几层就预先的知道了“此路不通”或者“此路不是最优”而停止此路的继续，这样能大幅度的提高算法效率。如何定界要放入具体问题中考虑，一般可以以“理论最大最小”这个概念来求界。以0-1背包问题为例，设所有物品预先已经按照单位价值量递减排列。在解空间树的第i层（此时正在考虑第i个物品是否应该被放入的时刻），设左子树为放入i物品，右子树为不放i物品。那么在确定左子树的上界的时候有：界=当前价值+i
的价值+MaxValue(背包剩余重量-i物品重量);其中的MaxValue为放i后剩余背包容量能获得的最大价值，应该注意的是此最大价值为理论意义上的最大价值，比如在继续放入p个后(按单位价值量递减),放不下第p+1个，此时应该按(Value[p+1]/Weight[p+1])*(WeightLeft)来计p+1物品的价值,(实际中不可能放入零点几个某物品。。。)；右子树的情形类似。 知道了如何定界，那么在实际流程中就要根据当前目标节点的界来剪枝了（是用上界还是下界，具体问题具体分析）。今天准备举个稍微有点挑战的例子---NPC问题中的TSP问题。 在TSP问题中，由于是环路，每个节点都要进出各一次，我们可以将每个节点最小的入度和最小的出度的和累加作为一个下界，这个下界几乎不可能达到！（全部最小出度的和即为下面提到的rcost的初值） 初始时我们创建一个最小堆，表示活节点队列。堆中按照每个节点的下界来划分优先级，下界越小的优先级越高。由于有是要求回路最小值，所以可以先判断此图是否有回路，没有直接返回，有再继续往下做。然后开始解空间树的搜索，广度优先遍历当前点的连通点，用curcost 来存当前的耗费总和，rcost表示当前点到叶子节点最小出度之和，那么一个节点的下界计算为：curcost+rcost-MinOut(当前点);如果此下界小于当前最优值，则将这个连
第五章整数规划 一、填空题 1．用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的（）。 2．在分枝定界法中，若选Xr=4／3进行分支，则构造的约束条件应为（）。 3．已知整数规划问题P0，其相应的松驰问题记为P0’，若问题P0’无可行解，则问题P。（）。 4．在0 - 1整数规划中变量的取值可能是（）或（）。 5．对于一个有n项任务需要有n个人去完成的分配问题，其解中取值为1的变量数为（）个。 6．分枝定界法和割平面法的基础都是用（）求解整数规划。 7．若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中，由X。所在行得X1+1／7x3+2／7x5=13／7，则以X1行为源行的割平面方程为（）。 8．在用割平面法求解整数规划问题时，要求全部变量必须都为（）。 9．用（）求解整数规划问题时，若某个约束条件中有不为整数的系数，则需在该约束两端扩大适当倍数，将全部系数化为整数。 10．求解纯整数规划的方法是割平面法。求解混合整数规划的方法是（）。 11．求解0—1整数规划的方法是隐枚举法。求解分配问题的专门方法是（）。 12．在应用匈牙利法求解分配问题时，最终求得的分配元应是（）。 13.分枝定界法一般每次分枝数量为（）个. 二、单选题 1．整数规划问题中，变量的取值可能是（）。 A．整数B．0或1C．大于零的非整数D．以上三种都可能 2．在下列整数规划问题中，分枝定界法和割平面法都可以采用的是A（）。 A．纯整数规划B．混合整数规划C．0—1规划D．线性规划 3．下列方法中用于求解分配问题的是（）。 A．单纯形表B．分枝定界法C．表上作业法D．匈牙利法 三、多项选择