03 第三章 整数规划.pptx

第1页：第三章整数规划与例1

第三章 整数规划 Integer Programming　§1 问题的提出　[eg.1] 用集装箱托运货物。问：甲、乙货物各托运多少箱，使总利润最大？

设 x1 为甲货物托运箱数、x2 为乙货物托运箱数，则

• max z = 20x1 + 10x2
• 5x1 + 4x2 ≤ 24，2x1 + 5x2 ≤ 13
• x1、x2 ≥ 0，且 x1、x2 取整数

第2页：整数规划的图解法

图解法：在 x1 − x2 平面上画出两条约束直线，与坐标轴的交点分别为 4.8（①）与 2.6（②），可行域内的整数点中，最优点为 (4,1)。

• 最优解：x1* = 4，x2* = 1
• 最优值：z_I* = 90

第3页：整数规划最优值的比较

一般地，整数规划的最优解不会优于相应线性规划的最优解：

• 对于 max 问题：z_I* ≤ z_L*
• 对于 min 问题：z_I* ≥ z_L*

本页同时给出整数规划的数学模型（文字与公式以图片形式呈现）。

第4页：分枝定界法

§2 分枝定界法　用单纯形法求解去掉整数约束后的线性规划 LP，得 x_L*；判别其是否为整数解：若为整数解，则 x_I* = x_L*；否则去掉非整数域，把问题分枝为多个 LP 继续求解并定界。

第5页：§3 0-1规划与例2

§3 0-1规划（xi = 0 或 1 的规划）　[eg.2] 选择投资场所：Ai 投资 Bi 元、收益 Ci 元，总投资 ≤ B。问如何选择 Ai，使收益最大？

分析：引入 xi = 1（Ai 选中）、0（Ai 落选），则

• max z = C1x1 + C2x2 + … + C7x7
• x1 + x2 + x3 ≤ 2（东区最多选 2 个）
• x4 + x5 ≥ 1（西区最少选 1 个）
• x6 + x7 ≥ 1（南区最少选 1 个）
• B1x1 + B2x2 + … + B7x7 ≤ B
• xi = 0 或 1

第6页：例3的过滤条件

[eg.3] 求解如下 0-1 规划：max z = 3x1 − 2x2 + 5x3

• x1 + 2x2 − x3 ≤ 2　①
• x1 + 4x2 + x3 ≤ 4　②
• x1 + x2 ≤ 3　③
• 4x2 + x3 ≤ 6　④
• x1、x2、x3 = 0 或 1

解：（1）观察一个可行解 x1 = 1、x2 = x3 = 0，此时 z = 3；（2）增加一个过滤条件 3x1 − 2x2 + 5x3 ≥ 3（记为 *）。

第7页：例3的枚举表与最优解

（3）列表计算：按 (x1, x2, x3) 的八种组合逐行检验约束 ①②③④ 与过滤条件 *，不满足者打「×」并停止计算。

枚举结果：z 值依次为 0、5、−2、3、8、1、6 等，其中 (1, 0, 1) 组合满足全部条件且目标值最大。

• 最优解：x1* = 1，x2* = 0，x3* = 1
• 最大值：z* = 8

本页枚举表在源文件中数字与判断符号粘连严重，无法安全切分为标准单元格，已按文字表述保留，建议对照原课件图片人工还原表格。