用单纯形法求解线性规划 max Z = 10x1+4x2 2x1+x2<=40 x1+1.5x2<=4 x1+x2>=50 x1>=0、x2>=0

首先将约束条件转化为标准形式： 2x1+x2<=40 → 2x1+x2+x3=40 x1+1.5x2<=4 → x1+1.5x2+x4=4 x1+x2>=50 → -x1-x2+x5=-50

目标函数也可以写成矩阵形式： max Z = [10 4 0 0 0] [x1 x2 x3 x4 x5]T

将所有约束条件和目标函数写成矩阵形式： max Z = [10 4 0 0 0] [x1 x2 x3 x4 x5]T s.t. [2 1 1 0 0] [x1 x2 x3 x4 x5]T <= 40 [1 1.5 0 1 0] [x1 x2 x3 x4 x5]T <= 4 [-1 -1 0 0 1] [x1 x2 x3 x4 x5]T <= -50 [1 0 0 0 0] [x1 x2 x3 x4 x5]T >= 0 [0 1 0 0 0] [x1 x2 x3 x4 x5]T >= 0

下面使用单纯形法求解该线性规划问题。

Step 1: 将约束条件和目标函数写成增广矩阵形式。

[ 2 1 1 0 0 40 ] [ 1 1.5 0 1 0 4 ] [-1 -1 0 0 1 -50 ] [10 4 0 0 0 0 ]

Step 2: 选择进入变量和离开变量。

首先需要选择一个进入变量。根据目标函数，选择$x_1$作为进入变量。

接下来需要选择一个离开变量。计算出每个约束条件的限制比（ratio），即右端常数与进入变量系数的商。注意，只有系数大于0才能作为离开变量的候选。

[ 2 1 1 0 0 40 ] ratio = 40 / 2 = 20 [ 1 1.5 0 1 0 4 ] ratio = 4 / 1 = 4 [-1 -1 0 0 1 -50 ] ratio = -50 / -1 = 50

因为ratio最小的是第二行的4，所以选择$x_2$作为离开变量。

Step 3: 通过高斯消元法进行行变换，使得进入变量系数为1，其他系数为0。

首先将第二行除以1.5，使得$x_2$的系数变为1.0。

[ 2 1 1 0 0 40 ] [2/3 1 0 2/3 0 8/3] [-1 -1 0 0 1 -50 ] [10 4 0 0 0 0 ]

接下来将第一行减去第二行的2倍，使得$x_1$的系数变为1.0。

[5/3 0 1 -4/3 0 8/3 ] [2/3 1 0 2/3 0 8/3 ] [-1 -1 0 0 1 -50 ] [10 4 0 0 0 0 ]

最后将第三行加上第二行，使得$x_2$的系数变为0。

[5/3 0 1 -4/3 0 8/3 ] [2/3 1 0 2/3 0 8/3 ] [1/3 0 0 2/3 1 -42 ] [10 4 0 0 0 0 ]

现在增广矩阵的第一列已经变成了单位矩阵，因此可以得到$x_1=8/3$，$x_2=8/3$，$Z=100/3$。

Step 4: 判断是否达到最优解。

因为目标函数中还存在非基变量$x_3$和$x_4$，因此还需要进行迭代。

首先选择进入变量，计算目标函数中对应系数的值。

[10 4 0 0 0] [x1 x2 x3 x4 x5]T = 10x1 + 4x2 + 0x3 + 0x4 + 0*x5 = 80/3

因为目标函数系数最大的是$x_1$，所以选择$x_1$作为进入变量。

接下来计算每个约束条件的限制比。

[5/3 0 1 -4/3 0 8/3 ] ratio = 8/3 / 5/3 = 8/5 [2/3 1 0 2/3 0 8/3 ] ratio = 8/3 / 2/3 = 4 [1/3 0 0 2/3 1 -42 ] ratio = -42 / 1/3 = -126

因为ratio最小的是第三行的-126，所以选择$x_4$作为离开变量。

进行行变换，使得$x_1$的系数变为1.0，其他系数变为0。

[1 0 3 -8/5 0 16/5 ] [0 1 0 4/5 0 16/5 ] [0 0 0 2/5 1 -126 ] [0 0 0 8/5 0 40/5 ]

现在增广矩阵的第三列已经变成了单位矩阵，因此可以得到$x_1=16/5$，$x_2=16/5$，$Z=120/5=24$。

由于目标函数中已经没有非基变量，因此已经达到最优解。

因此该线性规划问题的最优解为$x_1=16/5$，$x_2=16/5$，$Z=24$。