运筹学期末考试复习.docx

bij,cij)

例1求下图所示网络中的最小费用最大流，弧旁的权是(
M(f(0)),求出从vs到vt的最短路
(vs,v2,v1,vt),如下图中双箭头所示。
解：(1)取初始可行流为零流f(0)、1-2
X2(17)X3-X42-
33
以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会
较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选第
二个式子，并将真分数移到右边得：
C21,、
X2X3233(X3X4)
,、2
了(X3X4)1
33
引入松弛变量s1后得到下式，将此约束条件加到上表中，继续求解。
112
—X3—X4s1一
33343
Cj
1
1
0
0
0
CB
XB
b
x1
x2
x3
x4
s1
1
x1
5/3
1
0
5/6
—1/6
0
1
x2
8/3
0
1
-2/3
1/3
0
0
s1
—2/3
0
0
—1/3
—1/3
1
一Z
-13/3
0
0
—1/6
—1/6
0
Cj
1
1
0
0
0
CB
XB
b
x1
x2
x3
x4
s1
1
x1
5/3
1
0
5/6
-1/6
0
1
x2
8/3
0
1
-2/3
1/3
0
0
s1
—2/3
0
0
-1/3
-1/3
1
一Z
-13/3
0
0
-1/6
-1/6
0
得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解：X*=(0,4),Z=4,
或X*=(2,2),Z=4o
.分支定界法
例：用分枝定界法求解整数规划问题（用图解法计算）
minZx15x2
x1x22
5x16x230
x14
x1,x2。且全为整数
解：首先去掉整数约束，变成一般线性规划问题
minZx15x2
x1x22
5x16x230
x14
x1,x20
用图解法求（LP）的最优解，如图所示。
x1=18/11,x2=40/11
Z（0）=-218/11^（-）
即Z也是（IP）最小值的下限。
对于x1=18/11=,取值x1<1,x1>2对于x2=40/11〜,取值x2<3,x2>4先将（LP）划分为（LP1）和（LP2）,取x1<1,x1>2
记为（IP）
记为（LP）
min Z x1 5x2
x1 x2 2
5x1 6x2 30
（IP 1） x1 4
x1 1
Xi，X2 0且为整数
min Z x1 5x2
x1 X2 2
5x1 6x2 30
（IP2） x1 4
x1 2
x1, x2 0且为整数
有下式：
现在只要求出（LP1）和（LP2）的最优解即可。
先求（LP1）,如图所示。此时B在点取得最优解。
x1=1,x2=3,Z（1）=—16
找到整数解，问题已探明，此枝停止计算。
同理求（LP2），如图所示。
在C点取得最优解。
即x1=2,x2=10/3,
Z（2）=-56/3=—<Z1=-
16
，原问题有比（一16）更小的最优解，但x2不是整数，故利用
3>10/3>4加入条件。
加入条件：x2<3,x2>4有下式:
minZx15x2
minZXi5x2
(IP3)
x1x22
5x16x230
x1Xix2
X1,X2
4
2
3
0且为整数
(IP4)
XiX22
5x16x230
x14
x12
x24
x1,x20且为整数
只要求出（LP3）和（LP4）的最优解即可。
先求（LP3）,如图所示。
此时D在点取得最优解。
即x1=12/5=,x2=3,
Z（3）=-87/5=-<Z=-
但x1=12/5不是整数，可继续分枝。
即x1<2,x1>3。
求（LP4）,如图所示。
无可行解，不再分枝。
在（LP3）的基础上继续分枝。加入条件x1<2,x1>3有下式:
minZx15x2
x1x22
5x16x230
x14
(IP5)x12
x23
x12
x1,x20且为整数
只要求出(LP5)和(LP6)的最优解即可。

minZx15x2
x1x22
5x16x230
x14
(IP6)x12
x23
x13
x1,x20且为整数
先求(LP5),如图所示。
此时E在点取得最