第五章整数规划(第7讲)讲述.ppt

第五章 整数规划 第五章 整数规划 §1 整数规划问题及其数学模型 §1 整数规划问题及其数学模型 第五章 整数规划 §1 整数规划问题及其数学模型 第五章 整数规划 §1 整数规划问题及其数学模型 第五章 整数规划 第五章 整数规划 第五章 整数规划 第五章 整数规划 第五章 整数规划 * * 第五章 整数规划 最优化方法 Optimizing Methods §1 整数规划问题及其数学模型 §2 整数规划的解法 §3 整数规划的应用举例 在 LP 问题的讨论中，有些最优解是小数 . 但对 于某些具体问题常有要求最优解是整数( 即整数解) . 如决策变量为机器的台数、人数、车辆数 etc. 如果在问题中所有决策变量有整数限制，称为 纯 整数规划( Pure IP ) 或 全整数规划 ( All IP )； 如果在问题中仅部分决策变量有整数限制，称为 混合整数规划( Mixed IP ) ； 如果在问题中决策变量仅取 0 、1，称为 0-1 (整 数) 规划 . Integer Programming 13 24 托运限制 10 5 4 乙 20 2 5 甲 每箱利润（百元） 每箱重量（kg） 每箱体积（m3） 货 物 Example 1 （装载问题） 某厂拟用集装箱托运甲、乙 两种货物，每箱的体积、重量、可获利润及托运限制 如表，问两种货物各托 运几箱，可获利润最大？ Solution: 设 x1、x2 分 别为甲、乙两种货物托 运箱数. 则 这是一个 Pure IP 问题. Example 2 （工厂选址问题） 现准备从 A1、A2、A3 三个地点中选择两个开设工厂，工厂建成后它每月的 产量 ai (i =1,2,3)、三个客户 B1、B2、B3 每月的需求量 bj (j =1,2,3) 及 Ai 至客户 Bj 的单位运价 cij 见表. 45 60 40 bj 90 5 4 6 A3 80 4 3 2 A2 70 3 5 4 A1 ai B3 B2 B1 Bj Ai 已知三工厂每月的经营费用 di (与 产量无关)分别为 100、90、120 .问如 何选址使每月经营和运输费用最低 . Solution: 因为只有三个厂址选两个， ，所以简单的方法 是任取两个厂用运输问题求解，再加上每月的经营 费用比较即可. 设 选地点 Ai 开设工厂 否则 i = 1,2,3 ； xij 为Ai 开设工厂时，从 Ai 至 Bj 的运量 显然 如果 Ai 处开设工厂， 则运量满足： 不开设呢？ 客户端需求满足： 目标（每月的费用）： 这是一个 Mixed IP 问题. 可用于设计分配系统、新生活小区的设置 etc. 在 Ex.2 中，引进 0－1 变量给出了在 n 件任务中, 选择 j 项的约束 又用 来刻画不设 第 i 项任务，则 xij j = 1~n 都不起作用，为零. 可应用于选择性约束条件中 某工厂生产第 j 种产品的数量为 xj ( j =1,2,3) 其使 用的材料在甲、乙中选择一种，其消耗约束分别为： 其他资源约束条件未列出 引进 0－1 变量 y 选择材料甲 选择材料乙 M 为充分大的正数 一般地，假定要在 p个约束条件 中 至少要选择 q 个约束条件得到满足，可引进0-1变量 y Example 3 （背包问题） 假设有人要出发旅行，考虑带七 种物品，每件物品的重量与价值如表. 现在假设他最多带 35kg 物品，问该带 哪几件物品使总价值最大？ 112 16 7 26 13 6 90 15 5 15 3 4 9 3 3 12 4 2 12 3 1 价值 cj 重量 aj 物品 Solution: 如果带第 j 件物品 否则 j = 1~7 这是一个 0-1 规划问题. 一般整数规划中的变量 x ,