04 第四章 整数规划.pptx

第1页：整数规划章节目录

本章共分四节：

• 4.1 整数规划问题的提出
• 4.2 分枝定界法
• 4.3 0-1型整数规划
• 4.4 指派问题

第2页：集装箱装运实例

在求解线性规划问题时，得到的最优解可能是分数或小数，但许多实际问题要求得到的解为整数才行。这种要求线性规划有整数解的问题，称为整数规划（Integer Programming，简称 IP）。

例1：某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如下，问两种货物各装运多少箱，可使获得利润最大？

第3页：整数规划模型与化整问题

设甲、乙两种货物装运箱数分别为 x1 和 x2。显然，x1、x2 都要求为整数，于是可建立整数规划模型如下：

max z = 20x1 + 10x2，满足 5x1 + 4x2 ≤ 24、2x1 + 5x2 ≤ 13、x1, x2 ≥ 0、x1, x2 为整数。

它和线性规划问题的区别

在于多了整数条件这一条

可否通过把不考虑整数要求求得的最优解经过「化整」得到满足整数要求的最优解

不能。如此例可解得 x1 = 4.8、x2 = 0，凑整为 x1 = 5、x2 = 0 就破坏了体积约束，因而不是可行解；如截断小数变为 x1 = 4、x2 = 0，这虽然满足所有约束条件，但不是最优解，因为此时 z = 80，而对 x1 = 4、x2 = 1（也是可行解）有 z = 90

因此有必要专门研究整数规划的解法。

第4页：分枝定界法的提出

分枝定界法是 20 世纪 60 年代由 Land-Doig 和 Dakin 等人提出的。这种方法既可用于纯整数规划问题，也可用于混合整数规划问题，而且便于用计算机求解，所以很快成为解整数规划的最主要的方法。

设有最大化的整数规划问题 R，与它相应的线性规划问题为 R0，分枝定界法据此展开分枝与定界。

第5页：分枝定界法的步骤

分枝定界法的做法：

1. 用观察法求 R 的一个可行解，其目标值便是 R 的最优目标值 z* 的一个下界 z
2. 求解 R0，得 R0 的最优解 x(0) 和最优值 z0。若 x(0) 符合 R 的整数条件，则显然 x(0) 也是 R 的最优解，结束；否则，以 R0 作为一个分枝标明求解的结果，z0 是问题 R 的最优目标值 z* 的一个上界 z̄
3. 分枝。取目标函数值最大的一个枝 Rs，在 Rs 的解中任选一不符合整数条件的变量 xj，其值为 bj，构造两个约束条件 xj ≤ [bj] 和 xj ≥ [bj] + 1。将两个约束条件分别加入问题 Rs，得两个后继规划问题 Rs1 和 Rs2。不考虑整数条件求解这两个后继问题，以每个后继问题为一分枝标明求解的结果
4. 定界。在各分枝中找出目标函数值最大者作为新的上界 z̄；从已符合整数要求的各分枝中找出目标函数值最大者作为新的下界 z，即为 R 的最优目标值 z*（当上界与下界相等时停止）

第6页：分枝定界法算例

例：求解 max z = 40x1 + 90x2，约束 9x1 + 7x2 ≤ 56、7x1 + 20x2 ≤ 70、x1, x2 ≥ 0 且为整数。

• R0：z0 = 356，x1 = 4.81，x2 = 1.82
• R1（x1 ≤ 4）：z1 = 349，x1 = 4.00，x2 = 2.10；R2（x1 ≥ 5）：z2 = 341，x1 = 5.00，x2 = 1.57
• R11（x1 ≤ 4，x2 ≤ 2）：z11 = 340，x1 = 4.00，x2 = 2.00（可行，为整数解）；R12（x1 ≤ 4，x2 ≥ 3）：z12 = 327，x1 = 1.42，x2 = 3.00
• R21（x1 ≥ 5，x2 ≤ 2）：z21 = 308，x1 = 5.44，x2 = 1.00；R22（x1 ≥ 5，x2 ≥ 3）：无可行解

由定界过程，最优整数解为 x1 = 4、x2 = 2，最优值 z = 340。

源文件该页为分枝树排版，各枝的约束（含 x2 ≤ 2、x2 ≥ 3 等）与数值被分散排布，此处按原文给出的数值汇总，建议对照原图核对。

第7页：分枝定界法补充题（残页）

本页源文件仅提取到模型残片「max z = 2x1 + x2」，缺少完整的约束条件与求解过程，疑为分枝定界法的补充练习题（仅有公式图形，文字未提取成功）。建议对照原课件图片补充本页内容。

第8页：0-1型整数规划的定义

0-1型整数规划是整数规划的一种特殊形式，它的变量 xj 仅取值 0 或 1。这种只能取 0 或 1 的变量称为 0-1 变量或二进制变量。

例1：某公司拟在市东、西、南三区建立门市部。拟议中有 7 个位置 Ai（i = 1,2,…,7）可供选择。规定：

1. 在东区，A1、A2、A3 三个点中至多选两个
2. 在西区，A4、A5 两个点中至少选一个
3. 在南区，A6、A7 两个点中至少选一个

如选用 Ai 点，设备投资估计为 bi 元，每年可获利润估计为 ci 元，但投资总额不超过 B 元。问应选择哪几个点可使年利润最大。

第9页：门市部选址模型

引入 0-1 变量 xi（i = 1,2,…,7），令 xi = 1 表示 Ai 点被选用，xi = 0 表示 Ai 点没被选用。于是建立下列模型：

max z = c1x1 + c2x2 + … + c7x7，满足 b1x1 + b2x2 + … + b7x7 ≤ B、x1 + x2 + x3 ≤ 2、x4 + x5 ≥ 1、x6 + x7 ≥ 1、xi = 0 或 1（i = 1,2,…,7）。

第10页：钻井选点的逻辑约束

例2：某油田开发公司打算在 10 个有油气构造处选若干个钻井采油，应满足的条件如下，试写出约束条件：

1. 若开采 8 号，则必须开采 6 号，但开采 6 号不一定开采 8 号：x8 ≤ x6
2. 开采 5 号则不许开采 3 号，反过来也一样：x5 + x3 ≤ 1
3. 8 号和 7 号必须同时开采：x8 = x7
4. 2 号和 4 号至少开采一个：x2 + x4 ≥ 1
5. 1 号、4 号、6 号、9 号开采时最多不能超过两个：x1 + x4 + x6 + x9 ≤ 2

第11页：选择性约束的表示

例3 表示选择性约束：

（1）m 个约束条件只有 k 个起作用

设 m 个约束条件为 Σnj=1 aijxj ≤ bi，引入逻辑变量 yi = 1 表示第 i 个约束条件起作用、yi = 0 表示不起作用，则模型为 Σnj=1 aijxj ≤ bi + (1 - yi)M（M 是一个很大的数），且 Σmi=1 yi = k，yi = 0 或 1

（2）约束条件右端项可能是 m 个值中的某一个

即 Σnj=1 aijxj ≤ b1 或 b2 … 或 bm，则模型为 Σnj=1 aijxj ≤ Σmi=1 biyi，且 Σmi=1 yi = 1，yi = 0 或 1

第12页：固定费用目标函数的表示

例4：设目标函数 F(x) = k + cx（当 x > 0）、F(x) = 0（当 x = 0），试用线性形式表示。

引入逻辑变量 y = 1（x > 0）、y = 0（x = 0），则该目标函数可写为：

F(x) = ky + cx，满足 x ≤ yM、x ≥ 0、y = 0 或 1（也写作 x ≤ My）。

第13页：0-1型整数规划的标准型

求解 0-1 型整数规划可使用分枝定界法。下面用实例说明，先变成标准型，要求如下：

1. 目标函数求极大化。对于目标函数为 min z 的极小化问题，令 z′ = -z，使其变为目标函数为 max z′ 的极大化问题
2. 目标函数中所有变量的系数都为正数。如果目标函数中变量 xj 的系数为负数，令 xj′ = 1 - xj，把模型中的 xj 用 xj′ 代换
3. 变量的排列顺序按变量在目标函数中的系数值从小到大排列

待求解问题：max z = 8x1 + 2x2 - 4x3 - 7x4 - 5x5，约束 3x1 + 3x2 + x3 + 2x4 + 3x5 ≤ 4、5x1 + 3x2 - 2x3 - x4 + x5 ≤ 4，xj = 0 或 1（j = 1,2,…,5）。

源文件该页约束右端项写作 45 与 4，两处疑为连排导致的串字，此处按原文保留，建议对照原图核对。

第14页：0-1规划算例的求解

令 x3′ = 1 - x3，x4′ = 1 - x4，x5′ = 1 - x5，得 max z = 2x2 + 4x3′ + 5x5′ + 7x4′ + 8x1 - 16，约束 -3x2 - x3′ - 3x5′ - 2x4′ + 3x1 ≤ -2、3x2 + 2x3′ - x5′ + x4′ + 5x1 ≤ 6，x2, x3′, x5′, x4′, x1 = 0 或 1。

用分枝定界法求解（分枝树中标注各枝的目标值与可行性，如 z = 8 不可行、z = 4 可行等），可得最优解为 x2 = 0、x3′ = 0、x4′ = 1、x5′ = 1、x1 = 1。

于是，原问题的最优解为 z* = 4，x1* = 1，x2* = 0，x3* = 1 - 0 = 1，x4* = 1 - 1 = 0，x5* = 1 - 1 = 0。

源文件该页分枝树的标注被打散，各枝的 z 值与可行性按原文碎片整理，建议对照原图核对。

第15页：指派问题的提出

例：有一份说明书，需译成英、日、德、俄四种文字。现有甲、乙、丙、丁四个人，他们将说明书译成不同文字所需的时间如下表。问应指派哪个人完成哪项工作，使所需的总时间最少？

一般地，有 n 项任务、n 个完成人，第 i 人完成第 j 项任务的代价为 cij（i, j = 1,2,…,n）。为求得总代价最小的指派方案，引入 0-1 型变量 xij，并令 xij = 1 表示指派第 i 人去完成第 j 项任务，xij = 0 表示不指派。

源文件该页表格各行为倒序连排，此处按「人员 × 英日德俄」结构还原，建议对照原图核对。

第16页：指派问题的数学模型

指派问题的求解，最简便易行的方法是匈牙利法。匈牙利法基于下面的效率矩阵 (cij) = (c11 c12 … c1n；c21 c22 … c2n；…；cn1 cn2 … cnn)。

可见指派问题是 0-1 型整数规划的特例。不难发现，指派问题也是运输问题的特例，其产地和销地数都为 n，各产地的产量和各销地的销量都为 1。数学模型为：

min z = Σni=1 Σnj=1 cijxij，满足 Σnj=1 xij = 1（i = 1,2,…,n）、Σni=1 xij = 1（j = 1,2,…,n）、xij = 0 或 1。

第17页：匈牙利法的基本事实

匈牙利法基于这样一个明显的事实：如果系数矩阵的所有元素满足 cij ≥ 0，而其中有 n 个位于不同行不同列的一组 0 元素，则只要令对应于这些 0 元素位置的 xij = 1，其余的 xij = 0，就得到最优解。

例如系数矩阵 (cij) 中若有这样一组 0 元素，即可直接读出最优指派方案。

源文件该页示例矩阵为连排数字（如 12408702、05133062 等），排列被打散，建议对照原图核对。

第18页：匈牙利法的步骤（一）

第一步：变换系数矩阵，使每行每列都出现 0 元素。

1. 系数矩阵的各行分别减去各行中的最小元素
2. 所得系数矩阵的各列再分别减去各列中的最小元素

第二步：试求最优解。

1. 给只有一个 0 元素（不含划去的 0）的行中的「0」画◎，划去与◎同列的其它「0」
2. 给只有一个 0 元素（不含划去的 0）的列中的「0」画◎，划去与◎同行的其它「0」
3. 重复 (1)、(2)，直到无新的◎画出。若系数矩阵中已无未画◎也未划去的「0」，则已得到最多的◎，转 (5)；否则，便出现了 0 元素的闭回路，转 (4)
4. 从 0 元素的闭回路上任选一个「0」画◎，划去其同行同列的其它「0」，转 (1)
5. 显然，按上述步骤得到的◎是位于不同行不同列的 0 元素，若其个数为 n，则已得到最优解

第19页：匈牙利法的步骤（二）

第三步：用最少的直线覆盖所有 0 元素。

1. 给无◎的行打「√」
2. 给打√行中含有 0 元素的列打「√」
3. 给打√列中含有◎元素的行打「√」
4. 重复 (2)、(3)，直到无新的「√」打出
5. 给没有打√的行画横线，给打√的列画纵线

第四步：变换系数矩阵，增加 0 元素。在未被画线覆盖的其它元素中找出最小元素，各打「√」行减去最小元素，各打「√」列加上最小元素，转第二步。

第20页：五人五任务指派算例

例：求下列指派问题的最小解。

解：依次作行列变换、试指派、最少直线覆盖与矩阵变换，得到最终的指派结果。

于是，此问题的最优解为：甲—B；乙—C；丙—E；丁—D；戊—A，所需的总费用为 min z = 7 + 6 + 9 + 6 + 4 = 32。

源文件该页效率矩阵各行为倒序连排，此处按「人员 × A、B、C、D、E」结构还原，中间变换过程的矩阵建议对照原图核对。

第21页：指派算例的矩阵变换过程

本页演示上例（或同类算例）系数矩阵的逐次变换过程：先各行减去最小元素，再各列减去最小元素，随后反复作最少直线覆盖与增减最小元素的变换，直到矩阵中出现 n 个位于不同行不同列的 0 元素，即得到最优指派。

源文件该页全部为连排数字与矩阵碎片（如 21097、154148、131416、415139 等），已无法安全切分为行列，故不作表格还原，建议对照原图核对。

第22页：指派问题的两点说明

• 若分配问题中人与工作数不等，可仿照产销不平衡运输问题的作法，增加假想的工作数或假想的人数，使人数与工作数相等，并令相应的行或列的效率为 0，再用匈牙利法求解
• 如果分配问题中的目标函数为求极大值，则转为求极小值的方法，再用匈牙利法求解

第23页：