MATLAB分支定界法求解例题
题目:min (4*x1+4*x2); 约束条件:2*x1+5*x2<=15,2*x1-2*x2<=5,x1,x2>=0,且都为整数.
把以下程序存为ILP.m，
%============================
function [x,y]=ILp(f,G,h,Geq,heq,lb,ub,x,id,options)
%整数线性规划分支定界法，可求解纯整数规划和混合整数规划。
%y=minf’*x s.t. G*x<=h Geq*x=heq x为全整数或混合整数列向量
%用法
%[x,y]=ILp(f,G,h,Geq,heq,lb,ub,x,id,options)
%参数说明
%lb:解的下界列向量（Default:-int）
%ub:解的上界列向量（Default:int）
%x:迭代初值列向量
%id：整数变量指标列向量，1-整数，0-实数（Default:1）
global upper opt c x0 A b Aeq beq ID options;
if nargin<10,options=optimset({});options.Display='off';
https://www.doczj.com/doc/246140049.html,rgeScale='off';end
if nargin<9,id=ones(size(f));end
if nargin<8,x=[];end
if nargin<7 |isempty(ub),ub=inf*ones(size(f));end
if nargin<6 |isempty(lb),lb=zeros(size(f));end
if nargin<5,heq=[];end
if nargin<4,Geq=[];end
upper=inf;c=f;x0=x;A=G;b=h;Aeq=Geq;beq=heq;ID=id;
ftemp=ILP(lb(:),ub(:));
x=opt;y=upper;
%下面是子函数
function ftemp=ILP(vlb,vub)
global upper opt c x0 A b Aeq beq ID options;
[x,ftemp,how]=linprog(c,A,b,Aeq,beq,vlb,vub,x0,options);
if how <=0
return;
end;
if ftemp-upper>0.00005 %in order to avoid error
return;
end;
if max(abs(x.*ID-round(x.*ID)))<0.00005
if upper-ftemp>0.00005 %in order to avoid error
opt=x';upper=ftemp;
return;
else
opt=[opt;x'];
return;
end;
end;
notintx=find(abs(x-round(x))>=0.00005); %in order to avoid error
intx=fix(x);tempvlb=vlb;tempvub=vub;
if vub(notintx(1,1),1)>=intx(notintx(1,1),1)+1;
tempvlb(notintx(1,1),1)=intx(notintx(1,1),1)+1;
ftemp=IntLP(tempvlb,vub);
end;
if vlb(notintx(1,1),1)<=intx(notintx(1,1),1)
tempvub(notintx(1,1),1)=intx(notintx(1,1),1);
ftemp=IntLP(vlb,tempvub);
end;
%====================================
然后：
clc;clear
f=[4 4]
A=[2 5;2 -2]
b=[15;5]
Aeq=[];beq=[];
LB=[0 0];UB=[];
[xn,yn]=ILp(f,A,b,Aeq,beq,LB,UB,[1 1],1,[])
[x,fval,exitflag]=linprog(f,A,b,Aeq,beq,LB,UB)
结果：
xn =
0 0
yn =
Optimization terminated.
x =
1.0e-013 *
0.299004078674759
0.503948216933779
fval =
3.211809182434153e-013 exitflag =
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.求解方法： 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 =+
1.研究对象 主要研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。随着客观实际的发展，也应用于日常生活问题的解决。 2.运筹学的分支 运筹学的具体内容包括：规划论（包括线性规划、整数规划、非线性规划和动态规划）、图论、排队论、存储论、对策论、决策论。 3.运筹学各分支的求解方法 规划论： 线性规划—单纯形法、表上作业法 整数规划—分支定界法、割平面法、匈牙利法 非线性规划—梯度法（最速下降法、共轭梯度法）、可行方向法、制约函数法 动态规划—逆推解法、顺推解法 图论： 最短路径法、寻求最大流的标号法 决策论： 决策树 4.方法适用范围及特点 5.分支应用领域及具体应用问题 规划论： 应用领域：用电子计算机来处理成千上万个约束条件和变量的大规模线性规划问题，从解决技术问题的最优化，到工业、农业、商业、交通运输业以及决策分析部门都可以发挥作用。 具体问题：计划管理工作中有关安排和估值的问题，解决的主要问题是在给定条件下，按某一衡量指标来寻找安排的最优方案。它可以表示成求函数在满足约束条件下的极大极小值问题。 图论： 应用领域：网络技术 具体问题：最短路、网络最大流、最小费用最大流、中国邮递员问题、完成工程任务的时间最少，距离最短，费用最省 存储论： 应用领域：生产日常生活活动中与存储量有关的问题 具体问题：水电站蓄水问题、工厂生产原料储存、机器制造中工序中生产备件、商店商品储存 对策论： 应用领域：政治、经济、军事活动 具体问题：下棋、打牌、体育比赛；谈判；战争。
决策论： 应用领域：政治、经济、技术 具体问题：企业决策问题、人事管理 5.1市场销售 在广告预算和媒体的选择、竞争性定价、新产品开发、销售计划的制定等方面。 5.2生产计划 在总体计划方面主要是从总体确定生产、储存和劳动力的配合等计划以适应变动的需求计划，主要用线性规划和仿真方法等。此外，还可用于生产作业计划、日程表的编排等。还有在合理下料、配料问题、物料管理等方面的应用。 5.3库存管理 存货模型将库存理论与计算器的物料管理信息系统相结合，主要应用于多种物料库存量的管理，确定某些设备的能力或容量，如工厂的库存、停车厂的大小、新增发电设备容量大小、计算机的主存储器容量、合理的水库容量等。 5.4运输问题 这里涉及空运、水运、公路运输、铁路运输、捷运、管道运输和厂内运输等。包括班次调度计划及人员服务时间安排等问题。 5.5财政和会计 这里涉及预算、贷款、成本分析、定价、投资、证券管理、现金管理等。用得较多的方法是：统计分析、数学规划、决策分析。此外，还有盈亏点分析法、价值分析法等。 5.6人事管理 这里涉及六方面。(1)人员的获得和需求估计；(2)人才的开发，即进行教育和训练；(3)人员的分配，主要是各种指派问题；(4)各类人员的合理利用问题；(5)人才的评价，其中有如何测定一个人对组织、社会的贡献；(6)薪资和津贴的确定等。 5.7设备维修、更新和可靠度、项目选择和评价 如电力系统的可靠度分析、核能电厂的可靠度以及风险评估等。 5.8工程的最佳化设计 在土木、建筑、水利、信息、电子、电机、光学、机械、环境和化工等领域皆有作业研究的应用。 5.9计算器和讯息系统 可将作业研究应用于计算机的主存储器配置，研究等候理论在不同排队规则对磁盘、磁鼓和光盘工作性能的影响。有人利用整数规划寻找满足一组需求档案的寻找次序，利用图论、数学规划等方法研究计算器讯息系统的自动设计。 5.10城市管理 包括各种紧急服务救难系统的设计和运用。如消防队救火站、救护车、警车等分布点的设立。美国曾用等候理论方法来确定纽约市紧急电话站的值班人数。加拿大亦曾研究一城市警车的配置和负责范围，事故发生后警车应走的路线等。此外，诸如城市垃圾的清扫、搬运和处理；城市供水和污水处理系统的规划......等等