运 筹 学

运 筹 学复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 设某种物 …… 此处隐藏：2966字，全部文档内容请下载后查看。喜欢就下载吧 ……