运筹学目标规划与整数规划.pptVIP

多目标决策问题 弹性约束的处理方法 目标规划解的几何分析 目标规划的求解序贯算法 目标规划的求解多阶段算法 整数线性规划问题的一般形式 整数线性规划问题的分类 整数规划与其松弛问题 全整数规划的求解Gomory割平面方法 松弛问题的最优解 Gomory定理 例题求解 混合整数规划的求解分枝定界方法 例 0-1整数规划 0-1规划的应用-项目投资预算 0-1规划的应用-工厂-销售点配置问题 0-1规划的求解—隐枚举方法 经典指派问题 指派问题的数学模型 例 指派问题的性质 指派问题的求解-匈牙利方法 例题求解 一般指派问题 最大化指派问题 人数和工作数不等的指派问题 一个人可做几项工作的指派问题 某项工作一定不能由某人做的指派问题 割平面： 1 3 2 X 2 X 1 2 2.5 1 5 4 松弛问题3 的最优解 松弛问题2 的最优解 如果选择第二个方程： 分解为： 在松弛问题2中加入约束： 即 形成松弛问题3 没有找到整数解，继续做下去 分枝：当 不符合整数要求时，构造两个约束条件： 加入松弛问题分别形成两个子问题（分枝） 定界：当子问题获得整数规划的一个可行解，则它的目标函数值就构成一个界限 1 3 2 X 2 5 4 X 1 2 3 1 S 解S得： 1 3 2 X 2 5 4 X 1 2 3 1 S2 对S分枝： 构造约束： 和 形成分枝问题S1和S2，得解B和C S1 S A: x1=3/2,x2=10/3 Z=29/6 S2 C: x1=1,x2=7/3 Z=10/3 S1 B: x1=2,x2=23/9 Z=41/9 1 3 2 X 2 5 4 X 1 2 3 1 S2 对S1分枝： 构造约束： 和 形成分枝问题S11和S12，得解D S12 S11无可行解 S A: x1=3/2,x2=10/3 Z=29/6 S2 C: x1=1,x2=7/3 Z=10/3 S1 B: x1=2,x2=23/9 Z=41/9 S11 无可行解 S12 D: x1=33/14,x2=2 Z=61/14 1 3 2 X 2 5 4 X 1 2 3 1 S2 对S12分枝： 构造约束： 和 形成分枝问题S121和S122，得解E和F S121 S122 S A: x1=3/2,x2=10/3 Z=29/6 S2 C: x1=1,x2=7/3 Z=10/3 S1 B: x1=2,x2=23/9 Z=41/9 S11 无可行解 S12 D: x1=33/14,x2=2 Z=61/14 S122 F: x1=2,x2=2 Z=4 S121 E: x1=3,x2=1 Z=4 变量只能取0或1的整数线性规划 模型 变量假设: 模型: 生产厂 顾客需求 销售点 4 5 D C B A 7 II III 2 1 3 I 工厂-销售点配置问题-问题描述 问题: 为使经营成本最低,应开设那些工厂及销售点? 工厂-销售点配置问题-模型参数 工厂-销售点配置问题-模型 最优解（x1,x2,x3)=(1,0,1); z=8 隐枚举方法求解过程 n个员工分配作n项工作，一致的i个员工作的j项工作的成本为cij，i=1,…,n; j=1,…,n。求最佳分配方案。 s.t. 指派问题的解应对应于成本矩阵的不同行与不同列，且总成本最小 cij 定理：对于指派问题，成本矩阵的任一行(或列)减去(或加上)一个相同的数得到的新指派问题与原问题同解 成本矩阵的每一行及每一列减去该行或列的最小数，使每行每列至少有一个0。如果划去这些0所需要的直线数不少于n，则此时就可以求得最优解。 Page:* QSC 华东理工大学 工商经济学院 运筹学 运筹学 目标规划 实际问题决策经常面临的问题： 方案优劣并不以单一准则为目标，而是以多重准则为目标 约束条件并不完全符合严格的刚性条件，具有一定的弹性 可能的弹性约束： 最好等于 最好不大于 最好不小于 实际量＋ d － － d + = 目标值 负偏差变量 正偏差变量 最好等于： 最好不大于： 最好不小于： 顾客访问策略 目标： 访问时间最好不超过680小时； 访问时间最好不少于600小时； 销售收入尽量不少于70,000； 访问老顾客数最好不少于200个； 访问新顾客数最好不少于120个 模型－顾客访问策略 X 100 300 200 600 500 400 X 2 100 200 300 400 500 1 (1) (2) (3) (4) (5) 第一级目标 X 100 300 200 600 500 400 X 2 100 200 300 400 500 1 (1) 第二级目标 X 100 300 200 600 500 400 X 2 100 200 300 400 500 1 (1)