1整数规划的基本特点§2分枝定界法§3割平面法§4分配问题及其解法

在( LP )的最优解 X(0)中，任选一个不符合整数条件 的变量，例如xr= br（不为整数），以 br 表示不超过
br的最大整数。构造两个约束条件
x r≤
br 和xr≥ br＋1
将这两个约束条件分别加入问题( IP ) ，形成两个子 问题( IP1)和( IP2 ) ，再解这两个问题的松弛问题( LP1) 和( LP2) 。 4、修改上、下界：按照以下两点规则进行。 ⑴.在各分枝问题中，找出目标函数值最大者作为新 的上界； ⑵.从已符合整数条件的分枝中，找出目标函数值最 大者作为新的下界。 5、比较与剪枝 ：
定界： 0 Z * 14.75
max Z 3 x1 2 x2 2 x1 x2 9 2 x1 3x2 14 st. x2 2 x 0, x 0 2 1 x1 , x2为整数
max Z 3 x1 2 x2 2 x1 x2 9 2 x1 3x2 14 st. x2 3 x 0, x 0 2 1 x1 , x2为整数
1 若分枝后得到整数解，则这枝不必再分枝。 2 若分枝后得到非整数解, 如果比整数解更好，则这枝继续分枝 3 若分枝后得到非整数解, 如果比整数解更差，则这枝不必再分枝 这里解的好坏是指对应目标函数值的大小
例2 用分枝定界法求解 Max z = 40x1+90x2 s.t. 9x1+7x2 56 7x1+20x2 70 x1，x2 0 x1，x2 整数 ① ② ③ ④ ⑤

分枝定界算法的基本步骤
max Z c j x j
j 1 n
考虑纯整数问题：
n aij x j bi (i 1.2 m) ( IP) j 1 x 0, ( j 1.2 m)且为整数 j

比如下面的例子：
例1.某厂拟用集装箱托运甲乙两种货物，每箱 的体积、重量、可获利润以及托运所受限制如 下表：
货物 体积（每 箱M3) 5 甲 4 乙 托运限制 24 重量(每箱 50kg) 2 5 13 利润(每 箱百元) 20 10
问两种货物各托运多少箱,可使利润最大?
为了满足整数解得要求，初看，似乎只要把已得到的分 数或小数， “舍入化整”就可以了。但是，这常常是不行的， 因为化整后，不一定是可行解，或者虽是可行解，但不一定 是最优解。
整数规划
§1 整数规划及其解法 §2 0-1型整数规划 §3 指派问题
整数规划
1、理解整数规划、0-1规划和指派问题的数学 模型 2、理解整数规划模型的类型 3、理解整数规划的求解方法:分支定界法和割 平面法、0-1规划的隐枚举法和指派问题的 匈牙利法的思想和步骤
求解方法
1、分支定界法 2、割平面法

a x
i 1 ij
n
j
bi yi M (i 1,, m)
y1 + y2 + „ + ym = m –1， yi = 0 或 1 (i=1，„，m)
3、关于固定费用问题
• 在讨论线性规划时，有些问题是要求使 成本最少的方案，那时总设固定成本为 常数，并在线性规划的模型中不必明显 列出。但有些固定成本的问题不能用一 般线性规划来描述，但可改为混合整数 规划来解决。
aj
值最大？
解：设 x j 为决策变量，且 x j 满足如下限制
xj {
1，携带第j件物品 0，不携带第j件物品
，j 1,2, n
则问题的数学模型为
x c j x j max
j 1
n

第五章 整数规划主要内容：1、分枝定界法； 2、割平面法； 3、0－1型整数规划； 4、指派问题。

重点与难点：分枝定界法和割平面法的原理、求解方法，0－1型规划模型的建立及求解步骤，用匈牙利法求解指派问题的方法和技巧。

要 求：理解本章内容，熟练掌握求解整数规划的方法和步骤，能够运用这些方法解决实际问题。

§1 问题的提出要求变量取为整数的线性规划问题，称为整数规则问题（简称IP ）。

如果所有的变量都要求为（非负）整数，称之为纯整数规划或全整数规划；如果仅一部分变量要求为整数，称为混合整数规划。

例1 求解下列整数规划问题211020m ax x x z +=⎪⎪⎩⎪⎪⎨⎧≥≤+≤+为整数21212121,0,13522445x x x x x x x x 如果不考虑整数约束，就是一个线性规划问题（称这样的问题为原问题相应的线性规划问题），很容易求得最优解为：96m ax ,0,8.421===z x x 。

用图解法将结果表示于图中画“+”号的点都是可行的整数解，为满足要求，将等值线向原点方向移动，当第一次遇到“+”号点（1,421==x x ）时得最优解为1,421==x x ，最优值为z=90。

由上例可看出，用枚举法是容易想到的，但常常得到最优解比较困难，尤其是遇到变量的取值更多时，就更困难了。

下面介绍几种常用解法。

§2 分枝定界法分枝定界法可用于解纯整数或混合的整数规划问题。

基本思路：设有最大化的整数规划问题A ，与之相应的线性规划问题B ，从解B 开始，若其最优解不符合A 的整数条件，那么B 的最优值必是A 的最优值*z的上界，记为z ；而A 的任意可行解的目标函数值是*z的一个下界z ，采取将B 的可行域分枝的方法，逐步减少z 和增大z ，最终求得*z 。

现举例说明： 例2 求解A219040m ax x x z +=⎪⎪⎩⎪⎪⎨⎧≥≤+≤+为整数21212121,0,702075679x x x x x x x x 解：先不考虑条件⑤，即解相应的线性规划B （①--④），得最优解=1x 4.81, =2x 1.82,①② ③ ④ ⑤=0z 356（见下图）。

第四章
整数规划与分配问题Fra bibliotek整数规划的特点及作用 分配问题与匈牙利法
分枝定界法 割平面法 应用举例
1 整数规划的特点及应用
在实际问题中，全部或部分变量取值必须是整数。比如人 或机器是不可分割的，选择地点可以设置逻辑变量等。 在一个线性规划问题中要求全部变量取整数值的，称纯整 数线性规划或简称纯整数规划；只要求一部分变量取整 数值的，称为混合整数规划。
0 14 9 3 9 20 0 23 23 0 3 8 0 12 14 0
定理1 如果从分配问题效率矩阵 [aij] 的每一行元素中 分别减去（或加上）一个常数 ui (被称为该行的位势)，从 每一列分别减去（或加上）一个常数 vj（被称为该列的位 势），得到一个新的效率矩阵 [bij]，若其中 bij = aij-ui-vj， 则 [bij] 的最优解等价于 [aij] 的最优解。 A 甲 乙 3 4 B 5 2 A B A B
规划具有类似性质的一大类问题而设计的一种较好的方法。
结合例一来说明分枝定界法的思路和解题步骤： 例1. 求下述整数规划问题的最优解 max z 3 x1 2 x2
2 x1 3 x2 14 x1 0.5 x2 4.5 x , x 0, 且均取整数值 1 2
A 甲
乙
B 7
9
C 9
6
D 7
6
E 9
6
12
8
丙 丁 戊
7 15 4
17 14 10
12 6 7
14 6 10
9 10 9
三、两点说明
1. 分配问题中人数和工作任务不相等时 当人数多于工作任务数时，可以添加假想任务使得人 数与工作任务数相同，因为工作任务是假想的，因此完成 这些任务的时间是零。当任务数多于人数时，可添加假想 的人。这样的方法和运输问题中处理的方法类似。 2. 当问题目标变为求极大时