内容发布更新时间 : 2024/6/26 20:01:45星期一 下面是文章的全部内容请认真阅读。

例1 用单纯形法解下列问题：

minx1?2x2?x3

s..tx1?x2?2x3?x4?10,

2x1?x2?4x3?8,

?x1?2x2?4x3?4, xj?0,j?1,?,4.

解：将原问题化成标准形：

max?x1?2x2?x3

s..tx1?x2?2x3?x4?10, 2x1?x2?4x3?x5?8,

?x1?2x2?4x3?x6?4,

xj?0,j?1,?,6.

x4与添加的松弛变量x5，x6在约束方程组中其系数列正好构成一个3阶单位阵，它们可以作为初始基变量，初始基可行解为X=（0, 0, 0,10, 8, 4）T

列出初始单纯形表，见表1。

表1 cj→ CB 0 0 0 cj-zj 基 x4 x5 x6 b 10 8 4 0 -1 x1 1 2 -1 -1 2 x2 1 -1 [2] 2 -1 x3 -2 4 -4 -1 0 x4 1 0 0 0 0 x5 0 1 0 0 0 x6 0 0 1 0 由于只有σ2> 0，说明表中基可行解不是最优解，所以确定x2为换入非基变量；以x2

的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。

??min(1044,)?2? 122因此确定2为主元素（表1中以防括号[]括起），意味着将以非基变量x2去置换基变量x6，

采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x2的系数列(1, -1, 2)T变换成x6的系数列(0, 0, 1)T，变换之后重新计算检验数。变换结果见表2。

表2 cj→ CB 0 0 2 cj-zj 基 x4 x5 x2 b 8 10 2 4 -1 x1 3/2 3/2 -1/2 0 2 x2 0 0 1 0 -1 x3 0 [2] -2 3 0 x4 1 0 0 0 0 x5 0 1 0 0 0 x6 -1/2 1/2 1/2 -1

检验数σ3=3>0，当前基可行解仍然不是最优解。继续“换基”，确定2为主元素，即以非基变量x3置换基变量x5。变换结果见表3。

表3 cj→ CB 0 -1 2 cj-zj 基 x4 x3 x2 b 8 5 12 19 -1 x1 3/2 3/4 1 -9/4 2 x2 0 0 1 0 -1 x3 0 1 0 0 0 x4 1 0 0 0 0 x5 0 1/2 1 -3/2 0 x6 -1/2 1/4 1 -7/4

此时，3个非基变量的检验数都小于0，σ1= -9/4，σ5= -3/2，σ5= -7/4，表明已求得最优

*T解：X?(0,12,5,8,0,0)。去除添加的松弛变量，原问题的最优解为：X*?(0,12,5,8)T,最小

值为-19

例2 用大M法求解下列问题：

minx1?x2?3x3s..tx1?2x2?x3?11,2x1?x2?4x3?3, x1?2x3?1,xj?0,j?1,?,3.

解 引进松弛变量x4、、剩余变量x5和人工变量x6、x7，解下列问题：

minx1?x2?3x3?0x4?0x5?M(x6?x7)s..tx1?2x2?x3?x42x1?x2?4x3x1 用单纯形法计算如下：

表1 cj→ CB 0 M M cj-zj 基 x4 x6 x7 b 11 3 1 4M 1 x1 1 2 [1] 1-3M 1 x2 -2 1 0 1-M -3 x3 1 -4 -2 -3+6M 0 x4 1 0 0 0 0 x5 0 -1 0 M M x6 0 1 0 0 M x7 0 0 1 0 ?11?3

?x5?x6?2x3?x7?1xj?0,j?1,2,?,7由于σ1<σ2< 0，说明表中基可行解不是最优解，所以确定x1为换入非基变量；以x1的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。

??min(11311,,)?1? 1211因此确定1为主元素（表1中以防括号[]括起），意味着将以非基变量x1去置换基变量x7，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x1的系数列(1, 2, 1)T变换成x7的系数列(0, 0, 1)T，变换之后重新计算检验数。变换结果见表2。

表2 cj→ CB 0 M 1 cj-zj 基 x4 x6 x1 b 10 1 1 M+1 1 x1 0 0 1 0 1 x2 -2 [1] 0 1-M -3 x3 3 0 -2 -1 0 x4 1 0 0 0 0 x5 0 -1 0 M M x6 0 1 0 0 M x7 -1 -2 1 3M-1

由于σ2<σ3< 0，说明表中当前基可行解仍不是最优解，所以确定x2为换入非基变量；以x2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。因此确定1为主元素，意味着将以非基变量x2去置换基变量x6，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x2的系数列(-2, 1, 0)T变换成x6的系数列(0, 1, 0)T，变换之后重新计算检验数。变换结果见表3。

表3 cj→ CB 0 1 1 cj-zj 基 x4 x2 x1 b 12 1 1 2 1 x1 0 0 1 0 1 x2 0 1 0 0 -3 x3 [3] 0 -2 -1 0 x4 1 0 0 0 0 x5 -2 -1 0 1 M x6 2 1 0 M-1 M x7 -5 -2 1 M+1 由于只有σ3< 0，表中当前基可行解仍不是最优解，所以确定x3为换入非基变量；又由于x3的系数列的正分量只有3，所以确定3为主元素，意味着将以非基变量x3去置换基变量x4，对约束方程组的系数增广矩阵实施初等行变换，将x3的系数列(3, 0, -2)T变换成x4的系数列(1, 0, 0)T，变换之后重新计算检验数。变换结果见表4。

表4

cj→ CB -3 1 1 cj-zj 基 x3 x2 x1 b 4 1 9 -2 1 x1 0 0 1 0 1 x2 0 1 0 0 -3 x3 1 0 0 0 0 x4 1/3 0 2/3 1/3 0 x5 -2/3 -1 -4/3 1/3 M x6 2/3 1 4/3 M-1/3 M x7 -5/3 -2 -7/3 M-2/3

至此，无负的检验数且基变量中不含人工变量（即人工变量在基可行解中取0值），求得

**?1，x3?4，最小目标函数值为-2。 原问题的最优解：x1?9，x2*

例3 用两阶段法求解下列问题：

max2x1?x2s..tx1?x2?2,

x1?x2?1,x1?3,x1,x2?0.

解 将原问题化成标准形为：

max2x1?x2s..tx1?x2?x3x1?x2x1?x4?2?1?x5?3

x1,x2?,x5?0第一阶段 用单纯形法求解第一阶段的线性规划问题：

min??x6?x7s..tx1?x2?x3

?x6?x4?x5?2?x7?1?3

x1?x2x1x1,x2?,x7?0求解过程见表1。

表1

cj→ CB 1 1 0 cj-zj 1 0 0 cj-zj 0 0 0 cj-zj x2 x1 x5 x6 x1 x5 基 x6 x7 x5 b 2 1 3 3 1 1 2 1 1/2 3/2 3/2 0 0 x1 1 [1] 1 -2 0 1 0 0 0 1 0 0 0 x2 1 -1 0 0 [2] -1 1 -2 1 0 0 0 0 x3 -1 0 0 1 -1 0 0 1 -1/2 -1/2 1/2 0 0 x4 0 -1 0 1 1 -1 1 -1 1/2 -1/2 1/2 0 0 x5 0 0 1 0 0 0 1 0 0 0 1 0 1 x6 1 0 0 0 1 0 0 1 1/2 1/2 -1/2 2 1 x7 0 1 0 0 -1 1 -1 2 -1/2 1/2 -1/2 1 313TT因此，第一阶段求得最优解为(x1,x2,x3，x4,x5)?(,,0,0,)，基变量为x1、x2和

222x5，不包含人工变量。

第二阶段 以第一阶段的最终单纯形表为基础，除去人工变量x6、x7及其系数列，恢复目标价值向量为C =（2, -1, 0, 0, 0）T，重新计算检验数，继续迭代，见表2。

表2

cj→ CB -1 2 0 cj-zj 0 2 0 cj-zj 0 2 0 cj-zj x4 x1 x3 x4 x1 x3 基 x2 x1 x5 b 1/2 3/2 3/2 5/2 1 2 1 2 2 3 1 6 2 x1 0 1 0 0 0 1 0 0 0 1 0 0 -1 x2 1 0 0 0 2 0 -1 -3 1 -1 -1 -1 0 x3 -1/2 -1/2 1/2 1/2 -1 -1 [1] 2 0 0 1 0 T0 x4 [1/2] -1/2 1/2 3/2 1 0 0 0 1 0 0 0 0 x5 0 0 1 0 0 0 1 0 1 1 1 -2 因此，求得原问题的最优解为(x1,x2,x3，x4,x5)数值为6。

例4 用K—T条件求下列问题

?(3,0,1,2,0)T，最大目标函

minf(x1,x2)?(x1?1)2?(x2?2)2s..tx1?x2?2?0?x1?x2?0?0

?x1?x2?1?0解 该问题的Lagrange函数是

L(X,?,?)?(x1?1)2?(x2?2)2??（）-?2x1??3x2??(?x1?x2?1) 1-x1?x2?2由于

?L?2(x1?1)??1??2?? ?x1?L?2(x2?2)??1??3?? ?x2故该问题的K—T条件是