中国矿业大学运筹学-总复习

运 筹 学

运 筹 学复China University of Mining and Technology

习

运 筹 学例1 求解如下线性规划问题

复

习

max z 2 x1 3x2 x3 x1 3x2 x3 15 2 x 3 x x 18 1 2 3 s.t. x1 x2 x3 3 x1 , x2 , x3 0

-2China University of Mining and Technology

运 筹 学解：加入松弛变量，标准化得

复

习

max z 2 x1 3x2 x3 15 x1 3x2 x3 x4 2 x 3x x x5 18 1 2 3 s.t. x6 3 x1 x2 x3 x1 , x2 , x3 , x4 , x5 , x6 0

建立单纯形表如下：

0 0 x4 0 x5 0 x6 15 18 3

2 x1 1 2 1

3 x2 3 3 1

1 x3 1 1 1

0 x4 1 0 0

0 x5 0 1 0

0 x6 0 0 1-3-

China University of Mining and Technology

运 筹 学0 x4 x5 x6 15 18 3 0 2 x1 1 2 1 2 3 x2 3 3 1 3 1 x3 1 1 1 1 0 x4 1 0 0 0 0 x5 0 1 0 0 0 x6 0 0 1 0

复

习

5 6

x2 x5

5 3

1 3 1

1 0

1 3 2 4 3 0

1 3 1 1 3 1

0 1 0 0

0 0 1 0

15 3 6-4-

4 x6 8 0 3 15 1 0 China University of Mining and Technology

运 筹 学x2 x1 x6 x2 x1 x3

复

习

15 4 3 4 18 3 5 1 20

1 0 1 0 0 0 1 0 0

0 1 0 0 0 1 0 0

0 1 2 4 2 0 0 0

1 2/3 1 5/3 0 1/ 4 1/ 6 5 /12 5/6

0 1/ 3 1

0 0

4

0 4 / 3 1 1 1 0 1/ 3 1/ 3 1/ 3 0 1/ 4 1/ 2 1/ 4 1/ 2

0 1

x1 5, x2 3, x3 1 解毕 max z 20China University of Mining and Technology

-5-

运 筹 学例2 用对偶单纯形法计算

复

习

min w 2 x1 3x2 4 x3 x1 2 x2 x3 3 2 x1 x2 3x3 4 x , x , x 0 1 2 3

-6China University of Mining and Technology

运 筹 学解：为了便于 寻找初始正则 解，将问题变 形为：

复

习

max w ' 2 x1 3 x2 4 x3 x1 2 x2 x3 x4 3 2 x1 x2 3 x3 x5 4 取{x4,x5}为初始正则 解，列单纯形表如下： x , x , x , x , x 0 1 2 3 4 5

-7China University of Mining and Technology

运 筹 学-2XB x4 b -3 x1 -1

复

习

-3x2 -2

-4x3 -1

0x4 1

0x5 0

x5

-40

[-2]-2

1-3

-3-4

0

1

由于初始正则解有负分量，于是取min{-3,-4}=-4 x5为换出变量，取

min{

j 5 j

5 j 0} min{ , , } 1 2 2 4 3

1 51

x1为换入变量，得新基{x4,x1} , 51= -2为主元-8China University of Mining and Technology

运 筹 学基变换的过程：

复

习

1. 主元变为1,即用-2去除单纯形表中基变量x5所在的行；2. 主元所在列的其它元变为0,消去非基变量x1所在的列的 其余元-1,-2; 3. 得新基{x4,x1}的单纯形表 -2 XB x4 x5 b -3 -4 0 x1 -1 [-2] -2 -3 x2 -2 1 -3 -4 x3 -1 -3 -4-9China University of Mining and Technology

0 x4 1 0

0 x5 0 1

运 筹 学基变换的过程： -2 XB x4 x5 b -3 -4 0 x1 -1 [-2] -2 -2 XB x4 x1 b -1 2 4 x1 0 1 0 -3 x2 -2 1 -3 -3 x2 -5/2 -1/2 -4 -4 x3 -1 -3 -4 -4 x3 1/2 3/

2 -1 x4 1 0 0 x5 -1/2 -1/2 -1 0 x4 1 0 0 x5 0 1

复

习

-10China University of Mining and Technology

运 筹 学-2XB x4 x1 b -1 2 4 x1 0 1 0

复

习

-3x2 -5/2 -1/2 -4

-4x3 1/2 3/2 -1 x4 1 0 0 x5 -1/2 -1/2 -1

可见正则解的有负分量，由于x4=1 , 所以取x4为换出变量，取

j 4 1 8 2 min{ 4 j 0} min{ 5 , , } 1 4 j 2 2 5 42x2为换入变量，得新基{x2,x1} , 42=-5/2为主元-11China University of Mining and Technology

运 筹 学进行基变换，得新正则解的单纯形表： -2XB x2 x1 b 2/5 11/5 28/5 x1 0 1 0

复

习

-3x2 1 0 0

-4x3 -1/5 7/5 -3/5 x4 -2/5 -1/5 -8/5 x5 1/5 -2/5 -1/5

此时正则解是可行解，也是最优解。 X*=(11/5,2/5,0,0,0);z*=-28/5-12China University of Mining and Technology

运 筹 学例3

复

习

试用对偶原理求解线性规划问题

min z 2 x1 3 x2 5 x3 2 x4 3 x5 x1 x2 2 x3 x4 3 x5 4 2 x1 x2 3 x3 x4 x5 3 x 0, j 1, 2, 3, 4, 5 j已知其对偶规划的最优解为

y ,y * 1 4 5 * 2

3 5

-13China University of Mining and Technology

运 筹 学解：

复

习

min z 2 x1 3 x2 5 x3 2 x4 3 x5 x1 x2 2 x3 x4 3 x5 4 2 x1 x2 3 x3 x4 x5 3 x 0, j 1, 2, 3, 4, 5 j

该问题的对偶规划为

max w 4 y1 3 y2 y1 2 y2 2 y1 y2 3 2 y1 3 y2 5 y1 y2 2 3 y y 3 2 1 y1 0, y2 0 China University of Mining and Technology

-14-

运 筹 学min z 2 x1 3 x2 5 x3 2 x4 3 x5 x1 x2 2 x3 x4 3 x5 4 2 x1 x2 3 x3 x4 x5 3 x 0, j 1, 2, 3, 4, 5 j利用松紧关系，将最优解* 1

复

习

max w 4 y1 3 y2 y1 2 y2 2 y1 y2 3 2 y1 3 y2 5 y1 y2 2 3 y y 3 2 1 y1 0, y2 0

y ,y 4 5 * 2

3 5

y1 y2 3 2 y1 3 y2 5 松约束 y1 y2 2 y 0, 1 y2 0

代入对偶规划的约束条件得下列约 其对偶约束是紧约束 束是松约束，

x2 0 x3 0 紧约束 x4 0 x x 2x x 3x 4 3 4 5 1 2 2 x1 x2 3 x3 x4 x5 3

-15-

China University of Mining and Technology

运 筹 学设原问题的最优解为* * * * * X * ( x1 , x2 , x3 , x4 , x5 )T ,

复

习

有

* * * x2 x3 x4 0; * * x1 3 x5 4 * * 2 x1 x5 3

x2 0 x3 0 紧约束 x4 0 x x 2x x 3x 4 3 4 5 1 2 2 x1 x2 3 x3 x4 x5 3

求得

* * x1 1, x5 1

X * (1, 0, 0, 0,1)T , z* 5-16China University of Mining

and Technology

运 筹 学

复

习

例4 设某种物资有3个产地 A1,A2,A3, 生产量分别为9, 5,7;有4个销地B1,B2,B3,B4 ,销售量分别为3,8,4, 6 ;已知从Ai到Bj 物资的单位运价见下表。求总运费最小的 调运方案。B1 A1 A2 A3 2 1 8 B2 9 3 4 B3 10 4 2 B4 7 2 5 产量 9 5 7

销量

3

8

4

6

-17China University of Mining and Technology

运 筹 学存在基变量为0的解称为退化解。

复

习

在确定初始基可行解的过程中，如果某一步中出现情况： 当产地Ai处的余量与销地Bj处的需求量相等时，在格(i,j) 填入运量后，产地Ai处的余量与销地Bj处的销量同时为0, 相应地要划去一行和一列。这时就出现了退化。 为了使基变量个数恰好有m+n-1个，应在同时划去的一行 或一列中的某个格中填入数字0,表示这格中的变量是取 值为0的基变量；-18China University of Mining and Technology

运 筹 学伏 格 尔 法 计 算 1用伏格尔法寻找初始基： B1 B2 2 1 8 9 3 4 B3 10 4 2 B4 7 2 5 ai

复

习

行差 5 1 2

A1A2 A3

95 7

bj 列差

3 1

8 1

4 2

6 3

先算出运价表中各行与各列的最小运费与次小运费的差

额，并填入该运价表的最右列和最下行。 从行差或列差中选出最大者，并选择其所在行或列的最 小元素。

A1的行差最大，而其中运价c11最小, 令x11为优先运输路线。 -19China University of Mining and Technology

运 筹 学伏 用伏格尔法寻找初始基： 格 B1 B2 尔 2 9 3 A1 法 1 3 0 A2 计 8 4 0 A3 算 1B3 104 2

复

习

B47 2 5

ai9 9/6 5

行差5 1

7

2

3/0 bj 3 8 4 6 1 1 2 3 列差 令 x min{ 9, 3} 3 11 销地B1的销量3全由产地A1供给，所以x21=x31=0。将x11=3 填到调运方案表中第1行第1列上。 画去运输数据表第一列，A1的产量剩余为9-3=6。得到

新的产销平衡与单位运价表.China University of Mining and Technology

-20-

运 筹 学伏 用伏格尔法寻找初始基： B1 B2 B3 格 3 2 9 10 A1 尔 0 1 3 0 0 4 A2 法 0 8 4 2 计 A3 算 bj 3/0 8 4列差 1 1 1 1 2 2 2 再算出运价表中的行差与列差。 B4的列差最大，而其中运价c24最小,

复 行差 552

习

B4 7 5 2 5 6 6/1 3 3 3

ai 9/6 5/0 5 7

111 222

1

令 x24 min{5,6} 5 产地A2的产量2全供给销地B4,所以x23=x24=0。China University of Mining and Technology

令x24为优先运输路线。

画去运输数据表中第2行，B4的销量还要6-5=1。得新表。

-21-