整数规划课件解析.pptVIP

整数规划 模型求解 问题举例 二、整数规划 分类 整数规划 纯整数规划：全部决策变量取整数值； 混合整数规划：部分决策变量取整数值； 0-1规划：决策变量取0或1。 等等 原连续规划与整数规划最优解一致； 整数规划无可行解； 整数规划有可行解，但最优解值变差。 解的情况 整数规划最优解不能按照非整数规划最优解简单取整而获得。 常用求解方法 模型求解 分支定界法 隐枚举法：0-1规划 匈牙利法：指派问题 计算机（软件）求解：Lingo、Matlab、蒙特卡洛法等 等等 分支定界法 LP1 x1=1, x2=3 Z(1) ＝16 LP x1=18/11, x2=40/11 Z(0) ＝19.8 LP2 x1=2, x2=10/3 Z(2) ＝18.5 LP21 x1=12/5, x2=3 Z(21) ＝17.4 LP22 无可 行解 LP211 x1=2, x2=3 Z(211) ＝17 LP212 x1=3, x2=5/2 Z(212) ＝15.5 x1≤1 x1≥2 x2≤3 x2≥4 x1≤2 x1≥3 求解对应的非整数规划问题；反复进行分支、定界、剪枝，直至求得整数规划的最优解。 模型求解 隐枚举法（针对0-1规划） 先（试探性）找到一个可行解，代入目标函数得到一个约束条件（过滤条件）；对决策变量的每一个组合（0-1构成）先验证过滤条件（进行过滤），再验证其它约束条件，排除非可行解；改进过滤条件；至结束。 模型求解 计算机（软件）求解 Lingo：线性、非线性、整数规划等； Matlab：通用性较强 蒙特卡罗法：比赛常用 模型求解 Matlab求解整数规划 编程实现分支定界法、隐枚举法等等； bintprog()：求解0-1规划 模型求解 Matlab求解整数规划 例（指派问题）：工作1、2、3、4交甲、乙、丙、丁四人分别完成。由于个人专长不同，完成不同工作所需的时间如表所示。如何分配可使完成四项工作总时间最少。 模型求解 Matlab求解整数规划 模型求解 Matlab求解整数规划 c=[2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9]; Aeq=zeros(8,16); for i=1:4 Aeq(i,((i-1)*4+1):i*4)=1; Aeq(i+4,i:4:16)=1; end beq=ones(8,1); [x,y]=bintprog(c,[],[],Aeq,beq); x=reshape(x,[4,4]),y x = 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 y = 28 指派问题常用匈牙利法求解 模型求解 蒙特卡罗法 蒙特卡罗法（计算机随机性模拟法、统计试验法）是一种基于“随机数”的计算方法，能够比较逼真地描述事物的特点及物理实验过程，可以解决一些数值方法难以解决的问题。通过计算机仿真解决问题，也可以通过模拟检验模型的正确性，是比赛中经常使用的方法。可用于求解各类规划问题 模型求解 蒙特卡罗法 function [f,g]=mengte(x); f=x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)-8*x(1)-2*x(2)-3*x(3)-x(4)-2*x(5); g=[sum(x)-400;x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800; 2*x(1)+x(2)+6*x(3)-200;x(3)+x(4)+5*x(5)-200]; 模型求解 蒙特卡罗法 模型求解 公交公司每天各时段所需司乘人员情况如下： 司乘人员在各时段开始时上班，并连续工作八小时。怎样安排，既能满足工作需要，又配备最少的司乘人员? 问题举例 例1：人力资源分配问题 结束时段 开工时段 1 2 3 4 5 6 6:00-10:00 10:00-14:00 14:00-18:00 18:00-22:00 22:00-2:00 2:00-6:00 1 6:00-10:00 2 10:00-14:00 3 14:00-18:00 4 18:00-22:00 5 22:00-2:00 6 2:00-6:00 每时段需要的人数 60 70 60 50 20 30 例1：人力资源分配问题 问题举例 结束时段 开工时段 1 2 3 4 5 6 6:00-10:00 10:00-14:00 14:00-18:00 18:00-22:00 22:00-2:00 2:00-6:00 1 6:00-10:00 x1 x1 2 1