第三节整数规划模型的解例 整数规划模型
21 9040m a x xxz
5679,21 xxts
70207 21 xx
0,21?xx
且为整数
1
2
3
4
5
1由 — 解得,4
890.355m a x,817.1,809.4 21 zxx
（ 1）若取整：,250,1,4 21 zxx
是可行解，但非最优解，
250340,2,4 21 zxx
（ 2）按四舍五入得：,2,5 21 xx 不是可行解
2因 左边为,59 56?
用穷举法也是不可取的。
因有可行解：
一、分枝定界法设整数规划模型：
（ P）
n
j
jj xcz
1
m in
mibxats i
n
j
jij,,2,1,.
1
0?jx nj,,2,1且为整数,
n
j
jj xcz
1
m in
mibxats i
n
j
jij,,2,1,.
1
,0?jx nj,,2,1
记最优解为,最优目标值为 。X?z
松弛问题：
（ P0）
记可行域为 S0,最优解为 X0,最优目标值为 z0 。
1
2
3
00,zX?
:0P 1 3—
若 整，则0X 0XX
若 非整，
则 分枝
00 ii bx?
zz 0且自然上界
0S
0ib
1S
2S 11,zX?
1 3—:1P ][ 00 ii bx?
22,zX?
1 3—:2P 1][ 00 ii bx
若 整，则剪枝1X
并换上界,z 1z
若 非整，则2X
若,则 剪枝12 zz?
若,则 分枝12 zz?
当前上界
33,zX?
1 3—:3P?,1][ 00 ii bx
44,zX?
1 3—:4P?,1][ 00 ii bx
若 整，则 剪枝3X
若,则换界13 zz 1zz 3z
若,则不换界13 zz?
若 非整，则4X
若 当前上界，则 剪枝?4z
若 当前上界，则 分枝?4z
剪完所有枝 得, 1zzz k?
则
kk XXzz,
最小上界对应的最优解为所求。
2P
对每个子问题,不外乎有以下 三种 可能情况,iP
（ 1） 不可行,则剪枝；
（ 2）其最优解 为 整数解,则剪枝，且iX
当目标值 当前上界时，则换界；?iz
当目标值 当前上界时，则不换界。iz
（ 3）其最优解 为 非整数解,则iX
当目标值 当前上界时，则剪枝；?iz
当目标值 当前上界时，则分枝。iz
注,对于极大化问题，则是 定下界,最大下界对应的整数解为所求。
01 zzzz k
则
kk XXzz,
归纳起来,
例 求解 21 43m i n xxz
1552,21 xxts
522 21 xx
0,21?xx
且为整数
1
2
3
4
5
1
2
3
7654321 1x
2x
0
解松弛问题 P0 可用图解法
0S
zxx 21 43 目标函数等值线
)4.1,9.3(0X?
1S
2S
:0P 1 4
TX )4.1,9.3(0
5.170z
z5.17
TX )1,5.3(1
5.141z
1 4:1P 12?x
12?x
TX )2,5.2(2
5.152z
1 4:2P 22?x
22?x
31?x
TXP )1,3(33
133z
41?x
不可行4P
21?x 31?x
5P
TX )2.2,2(5?
8.145z
不可行6P
13
22?x 32?x 13z换界,
5P
TX )2.2,2(5?
8.145z 13
22?x 32?x
TXP )2,2(77
147z
TXP )3,0(88
128z
分枝
13
换界, 1314z 不换界,14128z?
最优目标值,14z
最优解,TX )2,2(
＃
二,0－ 1规划的解若对每一个变量取 0,1进行分枝，计算量很大。如 的情形：3?n
),,( 321 xxx
),,0( 32 xx ),,1( 32 xx
),0,0( 3x ),1,0( 3x
)0,1,0( )1,1,0()0,0,0( )1,0,0(
),0,1( 3x ),1,1( 3x
)0,1,1( )1,1,1()0,0,1( )1,0,1(
122222 43210共有 个子问题
n个变量的情形共有子问题个数：
1221 212222 1
1
210
nnn?
下面的方法可减少计算量。
1,隐数法设模型为：
n
j
jj xcz
1
m in
mibxasts i
n
j
jiji,,2,1,0.
1
njx j,,2,1,10 或
)0(?jc
若,0?jc,1 jj yx则令 )0( jjjjjj cyccxc有
若约束是,”，可乘（－ 1）?
若约束是“＝”，则可换为：
，i
n
j
jij bxa
1
i
n
j
jij bxa －
1
上述假设 之用处,
当 从取 0变为取 1时，目标值 增加jx jc
验证 当前解 是否为可行解时，只需验证 的符号is
约定,),,,( 21 nxxx?表示原问题
),,0,1( nx? 表示 的子问题 0,1 21 xx
这时 称为 固定变量,21,xx 其余变量称为 自由变量 。
＃
隐数法的基本思想：
从目标函数的最小值 z=0 （ 解点 ）开始,)0,,0,0(?
若该点 可行,则为最优解；
若不可行，则选 分枝变量 分枝（ 原则,其值升为,1”，其余仍取 0，得一 新解点,最接近可行,）? 若新解点可行，则剪枝，定界；
若新解点不可行，则与当前上界比较，确定剪枝或分枝。
直到剪完所有的枝，最小上界对应的可行解为所求。
用此思想 初步 计算 P.25 例 1.21
例 4321 4352m i n xxxxz
04,43211 xxxxsts
044242 43212 xxxxs
0143213 xxxxs
4,3,2,1,10 jx j 或解 对于 ),,,()( 43210 xxxxP
)0,0,0,0( 不可行,因此它不是最优解。
确定分枝变量,若用 分枝，两个子问题为：1x
),,,0( 432 xxx
),,,1( 432 xxx 解点：
)0,0,0,0(
)0,0,0,1( 均“很不可行” 6,4
2分别为：s?若用 分枝，两个子问题为：
2x
),,0,( 431 xxx
),,1,( 431 xxx — 解点,是可行解)0,0,1,0(
因此,为分枝变量。2x 见图对于 P2,431 432m i n xxxz
04,4311 xxxsts
04422 4312 xxxs
014313 xxxs
4,3,2,1,10 jx j 或当前上界）对应的目标值解点 (50)0,0,0,0(z
所以该分枝。
若用 分枝，则两个解点均很不可行，3x
所以取 为分枝变量。4x
若用 分枝，则解 可行，4x )1,0,0,0(
见图
),,,()( 43210 xxxxP
不可行)0,0,0,0(
),,1,()( 4311 xxxP
可行)0,0,1,0(
5?z
50 z
),,0,()( 4312 xxxP
不可行)0,0,0,0(
12?x 02?x
)1,,0,()( 313 xxP
可行)1,0,0,0( 4?z
)0,,0,()( 314 xxP
无可行解
14?x 04?x
540 z
最优解 TX )1,0,0,0( 最优目标值 4z
z0 自然上界一般编程步骤见 P.25
部分枚举法思路,让 最小的 取 1，其余取 0，若是可行解，则为最优解；否则再让次小的 对应的变量升为 1，直到可行为止。
jc
jc jx
例 4321 4352m i n xxxxz
04,43211 xxxxsts
044242 43212 xxxxs
0143213 xxxxs
4,3,2,1,10 jx j 或解 （ 1）解点 )0,0,0,0( 不可行，则转入（ 2）
0z（若可行得 ）
（ 2） 最小，让 取 1，其余取 0得解点1c 2x )0,0,0,1(
因不可行，转入（ 3），若可行则为最优解。
（ 3） 为次小的，则让 取 1，其余取 0得解点
3c 3x
)0,1,0,0(
仍不可行，转入（ 4）
（ 4）,为剩下系数中的最小者 },m i n { 3144 cccc 4c
让 取 1，其余取 0得解点4x )1,0,0,0(
是一可行解，故得：
最优解 TX )1,0,0,0(
最优目标值 44 cz #
2,隐枚举法
0
1
zxc
n
j
jj
先找一可行解,目标值,得过滤条件：0X 0z
因最优目标值,0zz
所以只需在满足过滤条件的解点中找最优者。
例 321 234m i n xxxz
4352,321 xxxts
334 321 xxx
1321 xxx
01,,321 或?xxx
1
2
3
解 找到可行解点 (1,0,0)，对应的 z =4,得过滤条件：
4234 321 xxx 0
32 个解点中只有 4个满足条件,分别是：0
)0,0,1(),,0,1,0(),1,0,0(),0,0,0(
逐点验证约束条件，对可行解，再比较目标值，
最小者为所求。
该过程可列表，见 P.28.
注,滤掉解点的多少与初始可行解有关。 #
21 9040m a x xxz
5679,21 xxts
70207 21 xx
0,21?xx
且为整数
1
2
3
4
5
1由 — 解得,4
890.355m a x,817.1,809.4 21 zxx
（ 1）若取整：,250,1,4 21 zxx
是可行解，但非最优解，
250340,2,4 21 zxx
（ 2）按四舍五入得：,2,5 21 xx 不是可行解
2因 左边为,59 56?
用穷举法也是不可取的。
因有可行解：
一、分枝定界法设整数规划模型：
（ P）
n
j
jj xcz
1
m in
mibxats i
n
j
jij,,2,1,.
1
0?jx nj,,2,1且为整数,
n
j
jj xcz
1
m in
mibxats i
n
j
jij,,2,1,.
1
,0?jx nj,,2,1
记最优解为,最优目标值为 。X?z
松弛问题：
（ P0）
记可行域为 S0,最优解为 X0,最优目标值为 z0 。
1
2
3
00,zX?
:0P 1 3—
若 整，则0X 0XX
若 非整，
则 分枝
00 ii bx?
zz 0且自然上界
0S
0ib
1S
2S 11,zX?
1 3—:1P ][ 00 ii bx?
22,zX?
1 3—:2P 1][ 00 ii bx
若 整，则剪枝1X
并换上界,z 1z
若 非整，则2X
若,则 剪枝12 zz?
若,则 分枝12 zz?
当前上界
33,zX?
1 3—:3P?,1][ 00 ii bx
44,zX?
1 3—:4P?,1][ 00 ii bx
若 整，则 剪枝3X
若,则换界13 zz 1zz 3z
若,则不换界13 zz?
若 非整，则4X
若 当前上界，则 剪枝?4z
若 当前上界，则 分枝?4z
剪完所有枝 得, 1zzz k?
则
kk XXzz,
最小上界对应的最优解为所求。
2P
对每个子问题,不外乎有以下 三种 可能情况,iP
（ 1） 不可行,则剪枝；
（ 2）其最优解 为 整数解,则剪枝，且iX
当目标值 当前上界时，则换界；?iz
当目标值 当前上界时，则不换界。iz
（ 3）其最优解 为 非整数解,则iX
当目标值 当前上界时，则剪枝；?iz
当目标值 当前上界时，则分枝。iz
注,对于极大化问题，则是 定下界,最大下界对应的整数解为所求。
01 zzzz k
则
kk XXzz,
归纳起来,
例 求解 21 43m i n xxz
1552,21 xxts
522 21 xx
0,21?xx
且为整数
1
2
3
4
5
1
2
3
7654321 1x
2x
0
解松弛问题 P0 可用图解法
0S
zxx 21 43 目标函数等值线
)4.1,9.3(0X?
1S
2S
:0P 1 4
TX )4.1,9.3(0
5.170z
z5.17
TX )1,5.3(1
5.141z
1 4:1P 12?x
12?x
TX )2,5.2(2
5.152z
1 4:2P 22?x
22?x
31?x
TXP )1,3(33
133z
41?x
不可行4P
21?x 31?x
5P
TX )2.2,2(5?
8.145z
不可行6P
13
22?x 32?x 13z换界,
5P
TX )2.2,2(5?
8.145z 13
22?x 32?x
TXP )2,2(77
147z
TXP )3,0(88
128z
分枝
13
换界, 1314z 不换界,14128z?
最优目标值,14z
最优解,TX )2,2(
＃
二,0－ 1规划的解若对每一个变量取 0,1进行分枝，计算量很大。如 的情形：3?n
),,( 321 xxx
),,0( 32 xx ),,1( 32 xx
),0,0( 3x ),1,0( 3x
)0,1,0( )1,1,0()0,0,0( )1,0,0(
),0,1( 3x ),1,1( 3x
)0,1,1( )1,1,1()0,0,1( )1,0,1(
122222 43210共有 个子问题
n个变量的情形共有子问题个数：
1221 212222 1
1
210
nnn?
下面的方法可减少计算量。
1,隐数法设模型为：
n
j
jj xcz
1
m in
mibxasts i
n
j
jiji,,2,1,0.
1
njx j,,2,1,10 或
)0(?jc
若,0?jc,1 jj yx则令 )0( jjjjjj cyccxc有
若约束是,”，可乘（－ 1）?
若约束是“＝”，则可换为：
，i
n
j
jij bxa
1
i
n
j
jij bxa －
1
上述假设 之用处,
当 从取 0变为取 1时，目标值 增加jx jc
验证 当前解 是否为可行解时，只需验证 的符号is
约定,),,,( 21 nxxx?表示原问题
),,0,1( nx? 表示 的子问题 0,1 21 xx
这时 称为 固定变量,21,xx 其余变量称为 自由变量 。
＃
隐数法的基本思想：
从目标函数的最小值 z=0 （ 解点 ）开始,)0,,0,0(?
若该点 可行,则为最优解；
若不可行，则选 分枝变量 分枝（ 原则,其值升为,1”，其余仍取 0，得一 新解点,最接近可行,）? 若新解点可行，则剪枝，定界；
若新解点不可行，则与当前上界比较，确定剪枝或分枝。
直到剪完所有的枝，最小上界对应的可行解为所求。
用此思想 初步 计算 P.25 例 1.21
例 4321 4352m i n xxxxz
04,43211 xxxxsts
044242 43212 xxxxs
0143213 xxxxs
4,3,2,1,10 jx j 或解 对于 ),,,()( 43210 xxxxP
)0,0,0,0( 不可行,因此它不是最优解。
确定分枝变量,若用 分枝，两个子问题为：1x
),,,0( 432 xxx
),,,1( 432 xxx 解点：
)0,0,0,0(
)0,0,0,1( 均“很不可行” 6,4
2分别为：s?若用 分枝，两个子问题为：
2x
),,0,( 431 xxx
),,1,( 431 xxx — 解点,是可行解)0,0,1,0(
因此,为分枝变量。2x 见图对于 P2,431 432m i n xxxz
04,4311 xxxsts
04422 4312 xxxs
014313 xxxs
4,3,2,1,10 jx j 或当前上界）对应的目标值解点 (50)0,0,0,0(z
所以该分枝。
若用 分枝，则两个解点均很不可行，3x
所以取 为分枝变量。4x
若用 分枝，则解 可行，4x )1,0,0,0(
见图
),,,()( 43210 xxxxP
不可行)0,0,0,0(
),,1,()( 4311 xxxP
可行)0,0,1,0(
5?z
50 z
),,0,()( 4312 xxxP
不可行)0,0,0,0(
12?x 02?x
)1,,0,()( 313 xxP
可行)1,0,0,0( 4?z
)0,,0,()( 314 xxP
无可行解
14?x 04?x
540 z
最优解 TX )1,0,0,0( 最优目标值 4z
z0 自然上界一般编程步骤见 P.25
部分枚举法思路,让 最小的 取 1，其余取 0，若是可行解，则为最优解；否则再让次小的 对应的变量升为 1，直到可行为止。
jc
jc jx
例 4321 4352m i n xxxxz
04,43211 xxxxsts
044242 43212 xxxxs
0143213 xxxxs
4,3,2,1,10 jx j 或解 （ 1）解点 )0,0,0,0( 不可行，则转入（ 2）
0z（若可行得 ）
（ 2） 最小，让 取 1，其余取 0得解点1c 2x )0,0,0,1(
因不可行，转入（ 3），若可行则为最优解。
（ 3） 为次小的，则让 取 1，其余取 0得解点
3c 3x
)0,1,0,0(
仍不可行，转入（ 4）
（ 4）,为剩下系数中的最小者 },m i n { 3144 cccc 4c
让 取 1，其余取 0得解点4x )1,0,0,0(
是一可行解，故得：
最优解 TX )1,0,0,0(
最优目标值 44 cz #
2,隐枚举法
0
1
zxc
n
j
jj
先找一可行解,目标值,得过滤条件：0X 0z
因最优目标值,0zz
所以只需在满足过滤条件的解点中找最优者。
例 321 234m i n xxxz
4352,321 xxxts
334 321 xxx
1321 xxx
01,,321 或?xxx
1
2
3
解 找到可行解点 (1,0,0)，对应的 z =4,得过滤条件：
4234 321 xxx 0
32 个解点中只有 4个满足条件,分别是：0
)0,0,1(),,0,1,0(),1,0,0(),0,0,0(
逐点验证约束条件，对可行解，再比较目标值，
最小者为所求。
该过程可列表，见 P.28.
注,滤掉解点的多少与初始可行解有关。 #
