第3章 整数线性规划.pptVIP

第3章 整数线性规划 整数线性规划问题 Gomory割平面方法 分枝定界方法 0-1规划 §3.1 整数线性规划问题 引例——建立整数线性规划模型 整数线性规划的数学模型 整数线性规划问题的求解 8 5 0 2 隐枚举方法 × 6 (1, 1, 1) × 1 (1, 1, 0) ∨ 8 0 2 1 1 (1, 0, 1) × 3 (1, 0, 0) × 3 (0, 1, 1) × -2 (0, 1, 0) ∨ 5 －1 1 0 1 (0, 0, 1) ∨ 0 0 0 0 0 (0, 0, 0) 是∨ 否× (0) (1) (2) (3) (4) z 值 满足条件 约束条件 x1 , x2, x3 在实际中经常会遇到这样的问题，有n 项不同的任务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。 (Assignment problem) 3 指派问题 例 有一份中文说明书，需译成英、日、德、俄四种文字,分别记为E、J、G、R. 有甲、乙、丙、丁四人.他们将中文说明书翻译成不同语种说明书的所需时间如下表，问应该指派何人去安排何工作，使所需总时间最少？ 3 指派问题O) yuyingzhao@ 运 筹 学 千里之外 决胜 帷幄之中 运筹 主讲教师 赵玉英 北京林业大学理学院 1 引例——建立整数线性规划模型 例 某公司拟建设A、B两种类型的生产基地若干个，两种类型的生产基地每个占地面积，所需经费，建成后生产能力及现有资源情况如下表所示。问A、B类型基地各建设多少个，可使总生产能力最大？ 1000 2000 生产能力 13000 24 5000 4 2000 5 占地（m2） 费用（万元） 资源限制 B A 2 整数线性规划的数学模型 整数线性规划模型 简称：ILP问题（integer linear programming） 依照决策变量取整要求的不同，整数规划可分为纯整数规划、混合整数规划、0－1整数规划。 例：设整数规划问题 且为整数 3 整数线性规划问题的求解 思路1：可否解决相应的线性规划问题，最后舍入到最近的整数解？ x1 x2 ⑴ ⑵ 3 3 (3/2,10/3) ? 3 整数线性规划问题的求解 思路2：由于纯整数线性规划的可行集合就是一些离散的格点，可否用穷举的方法寻找最优解？ ?当格点个数较少时，这种方法可以； ?对一般的ILP问题，穷举方法无能为力。 ? 目前，常用的求解整数规划的方法有： 割平面法和分枝定界法； 对于特别的0－1规划问题采用隐枚举法和匈牙利法。 3 整数线性规划问题的求解 §3.2 Gomory割平面方法 割平面方法的基本思想 割平面方法的实现——例题 1 割平面方法的基本思想 考虑纯整数线性规划问题： （P） （p0） 问题（P）的松弛问题 x1 x2 ⑴ ⑵ 3 3 问题P和P0的关系： ?P的可行区域是P0的可行区域的子集； ?如果P0无可行解，则P无可行解； ?P0的最优值是P的最优值的一个下界； ?若P0的最优解为整数向量，则它也是P的最优解； （P） （p0） ?如果松弛问题(P0)无解，则(P)无解； ?如果(P0)的最优解为整数向量，则也是(P)的最优解； ?如果(P0)的解含有非整数分量，则对(P0) 增加割平面条件：即对(P0)增加一个线性约束，将(P0)的可行区域割掉一块，使得非整数解恰好在割掉的一块中，但又没有割掉原问题(P)的可行解，得到问题(P1)，重复上述的过程。 1 割平面方法的基本思想 2 割平面方法的实现——例题 解：利用图解法可以看出，最优解为(1,1)T。Gomory割平面法的算法过程如下： 0 x1 x2 2 3 z 1 1 1、去掉整数约束，得到松弛问题，化成标准形式，得到松弛问题的第一张表格： 0 6 0 3 2 1 0 -3 2 0 1 0 1 0 0 2、单纯形