运筹学之整数规划.pptVIP

图 例 某公司计划建筑两种类型的宿舍.甲种每幢占地0.25 ×103m2, 乙种每幢地0.4×103m2.该公司拥有土地3×103m2. 计划甲种宿舍不超过 8 幢,乙种宿舍不超过4幢.甲种宿舍每幢利润为10万元，乙种宿舍利润为每幢20万元.问该公司应计划甲、乙两种类型宿舍各建多少幢时,能使公司获利最大 ? 求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。 可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程 当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解 一般整数规划问题属于一类未解决的难题，只有少数特殊问题有好的算法。 练习：用分枝定界法求解整数规划问题  练习：用隐枚举法求解0—1规划问题 例一： 例二、 练习： 改进过滤条件： 8 否 是 1 1 2 0 3 8 (0,1,0) (0,1,1) (4) (3) (2) (1) (0‘) Z值 是否满足条件 条 件 点 (x2,x1,x3) 改进过滤条件： 否 否 否 否 -2 3 1 6 (1,0,0) (1,0,1) (1,1,0) (1,1,1) (4) (3) (2) (1) (0‘) Z值 是否满足条件 条 件 点 (x2,x1,x3) 为了选修课程门数最少，应学习哪些课程 ？ 选课策略 要求至少选两门数学课、三门运筹学课和两门计算机课 课号 课名 学分 所属类别 先修课要求 1 微积分 5 数学 ? 2 线性代数 4 数学 ? 3 最优化方法 4 数学；运筹学 微积分；线性代数 4 数据结构 3 数学；计算机 计算机编程 5 应用统计 4 数学；运筹学 微积分；线性代数 6 计算机模拟 3 计算机；运筹学 计算机编程 7 计算机编程 2 计算机 ? 8 预测理论 2 运筹学 应用统计 9 数学实验 3 运筹学；计算机 微积分；线性代数 0-1规划模型 决策变量 目标函数 xi=1 ~选修课号i 的课程（xi=0 ~不选） 选修课程总数最少 约束条件 最少2门数学课，3门运筹学课， 2门计算机课。 课号 课名 所属类别 1 微积分 数学 2 线性代数 数学 3 最优化方法 数学；运筹学 4 数据结构 数学；计算机 5 应用统计 数学；运筹学 6 计算机模拟 计算机；运筹学 7 计算机编程 计算机 8 预测理论 运筹学 9 数学实验 运筹学；计算机 （0 . 1 . 1 . 0 . 0） 指派问题 一、问题的提出 1、实例 有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如下表所示，问如何分配任务使完成四项任务的总工时耗费最少？ 解：设 则此指派问题的模型为 第一个约束说明第i个人只能完成一个任务。 第二个约束说明第j项任务只能由一人完成。 在实际中经常会遇到这样的问题，有n 项不同的任务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。 （一）、指派问题的数学模型 设n 个人被分配去做n 件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第I 个人去做第j 件工作的的效率（ 时间或费用）为Cij(i=1.2…n;j=1.2…n)并假设Cij ≥0。问应如何分配才能使总效率（ 时间或费用）最高？ 设决策变量 1 分配第i 个人去做第j 件工作 xij = 0 相反 ( I,j=1.2. …n ) 其数学模型为： 二、求解指派问题的理论依据 指派问题的一般形式 1、指派问题是一个特殊的运输问题 2、Koing定理：在原指派问题的效益矩阵中同行同列加上某一常数，所得指派问题与原问题同解。 证明： （二）、解题步骤： 指派问题是0-1 规划的特例，