第二讲整数规划与规划.ppt

第二讲整数规划与规划
*
第1页，此课件共34页哦
什么是整数规划与0-1规划？
定义
规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界 。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界 ，若无作用 =0 。
第二步：比较与剪枝，各分枝的最优目标函数中若有小于 者，则剪掉这枝，即以后不再考虑了。若大于 ， 且不符合整数条件， 则重复第一步骤。 一直到最后得到 = 为止。得最优整数解 。
*
第16页，此课件共34页哦
分析
整数规划关键是找到一下限-最大化问题（或上限-最小化问题），用来剪枝，通过观察法，我们往往可以得到这个下限或上限，但是有没有更好的办法来得到一个相对较好的值呢？
初值选取----蒙特卡洛法
*
第17页，此课件共34页哦
MATALB求解命令
%[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x,id)
%整数线性规划分支定界法，可求解全整数或混合整数线性规划。
% y=min f'*x . G*x<=h Geq*x=heq x为全整数或混合整数列向量。
%[x,y]=IntLp(f,G,h)
%[x,y]=IntLp(f,G,h,Geq,heq)
%[x,y]=IntLp(f,G,h,Geq,heq,lb,ub)
%[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x)
%[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x,id)
%[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x,id,options)
% x:最优解列向量；y:目标函数最小值；f:目标函数系数列向量
% G:约束不等式条件系数矩阵；h:约束不等式条件右端列向量
% Geq:约束等式条件系数矩阵；heq：约束登时条件右端列向量
% lb:自变量下界列向量（default:-inf）
% ub:自变量上界列向量（default:inf）
% x:迭代初值列向量
% id:整数变量指标列向量，1-整数，0-实数（default:1）
% options的设置请参见optimset或linprog
*
第18页，此课件共34页哦
求解例1
f=[-20 -10];
G=[5 4;2 5];
h=[24;13];
[x,y]=IntLp(f,G,h,[],[],[0;0],[inf;inf])

x=[ ] z=90
*
第19页，此课件共34页哦
0-1型整数规划
0-1型整数规划是整数规划中的特殊情形，它的变量xj仅取值0或1。这时xj称为0-1变量，或称二进制变量。xj仅取值0或1这个条件可由下述约束条件：
整数
所代替，是和一般整数规划的约束条件形式一致的。我们先介绍引入0-1变量的实际问题，再研究解法。
*
第20页，此课件共34页哦
例4 投资场所的选定—相互排斥的计划
某公司拟在市东、西、南三区建立门市部。拟议中有7个位置（点）Ai(i=1,2,…,7)可供选择。规定
在东区：由A1,A2,A3三个点中至多选两个；
在西区：由A4,A5两个点中至少选一个；
在南区：由A6,A7两个点中至少选一个。
如选用点Ai，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？
*
第21页，此课件共34页哦
解题时先引入0-1变量xi(i=1,2,…,7),
令：
于是问题可列写成：
*
第22页，此课件共34页哦
例5 关于固定费用的问题（Fixed Cost Problem）
在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决。
某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动成本可能增加。所以必须全面考虑。今设有三种方式可供选择，
令