分别用大M法和两阶段法求解如下线性规划问题 max z =10x1+15x2+12x3 约束条件如下 5x1+3x2+x3小于等于9 -5x1+6x2+15x3小于等于15 2x1+x2+x3大于大于5 x1x2x3 ≥0
用大M法求解：
将约束条件转化为等式形式，引入松弛变量和人工变量，得到如下形式：
max z =10x1+15x2+12x3
s.t.
5x1+3x2+x3+s1=9
-5x1+6x2+15x3+s2=15
2x1+x2+x3-s3=5
x1,x2,x3,s1,s2,s3 ≥0
引入人工变量后，目标函数需要加上人工变量的系数，即：
max z =10x1+15x2+12x3+M(s1+s2+s3)
其中M为一个很大的正数，使得人工变量的系数在目标函数中不起作用。
将目标函数和约束条件写成矩阵形式：
max z = [10 15 12 0 0 0] [x1 x2 x3 s1 s2 s3]T
s.t.
[5 3 1 1 0 0] [x1 x2 x3 s1 s2 s3]T = 9
[-5 6 15 0 1 0] [x1 x2 x3 s1 s2 s3]T = 15
[2 1 1 0 0 -1] [x1 x2 x3 s1 s2 s3]T = 5
x1,x2,x3,s1,s2,s3 ≥0
按照大M法的步骤，构造初始单纯形表格：
x1 x2 x3 s1 s2 s3 RHS
z 10 15 12 M M M 0
s1 5 3 1 1 0 0 9 s2 -5 6 15 0 1 0 15 s3 2 1 1 0 0 -1 5
选择系数最大的M（即M的系数为1），将其所在列作为入基变量列，找到离基变量行（即系数为1的那个变量所在的行），进行初等行变换，得到新的单纯形表格：
x1 x2 x3 s1 s2 s3 RHS
z 0 105 102 M -10 M 135
s1 0 3/5 8/5 1/5 -3/5 0 48/5 x1 1 3/5 1/5 1/5 0 -1/5 9/5 s3 0 7/5 3/5 -2/5 3/5 -1/5 7/5
继续进行迭代，选择系数最大的M，将其所在列作为入基变量列，找到离基变量行，进行初等行变换，得到新的单纯形表格：
x1 x2 x3 s1 s2 s3 RHS
z 0 0 321/7 4/7 10/7 M 1415/7
s1 0 0 27/14 1/14 -27/70 1/35 87/35 x1 1 0 2/7 -1/7 3/35 2/35 20/7 s3 0 1 9/35 6/35 -9/70 -1/35 1/7
此时所有M的系数都变成了0，说明人工变量可以全部离基。由于目标函数系数矩阵中的所有元素都是非负的，所以此时可以停止迭代，得到最优解：
x1 = 20/7, x2 = 9/35, x3 = 321/70, z = 1415/7
用两阶段法求解：
将约束条件转化为等式形式，引入松弛变量和人工变量，得到如下形式：
max z =10x1+15x2+12x3
s.t.
5x1+3x2+x3+s1=9
-5x1+6x2+15x3+s2=15
2x1+x2+x3-s3=5
x1,x2,x3,s1,s2,s3 ≥0
将目标函数和约束条件分成两个阶段处理。第一阶段最小化人工变量的和，即：
min z1 = Ms1+Ms2+Ms3
s.t.
5x1+3x2+x3+s1=9
-5x1+6x2+15x3+s2=15
2x1+x2+x3-s3=5
s1,s2,s3 ≥0
其中M为一个很大的正数。
构造初始单纯形表格：
x1 x2 x3 s1 s2 s3 RHS
z1 M M M 1 1 1 0
s1 5 3 1 1 0 0 9 s2 -5 6 15 0 1 0 15 s3 2 1 1 0 0 -1 5
选择系数最小的人工变量（即M的系数为1），将其所在列作为入基变量列，找到离基变量行，进行初等行变换，得到新的单纯形表格：
x1 x2 x3 s1 s2 s3 RHS
z1 0 0 0 1/M 1/M 1/M 3
s1 5 3 1 1 0 0 9 x1 0 9 16 1 1/M 0 6 s3 2 1 1 0 0 -1 5
此时第一阶段结束，如果最优解的目标函数值为0，则继续进行第二阶段，否则问题无解。
在第二阶段中，去掉人工变量，将目标函数和约束条件写成矩阵形式：
max z2 =10x1+15x2+12x3
s.t.
5x1+3x2+x3=9
-5x1+6x2+15x3=15
2x1+x2+x3=5
x1,x2,x3 ≥0
构造初始单纯形表格：
x1 x2 x3 RHS
z2 10 15 12 0
s1 5 3 1 9 s2 -5 6 15 15 s3 2 1 1 5
选择系数最大的目标函数系数（即12的系数），将其所在列作为入基变量列，找到离基变量行，进行初等行变换，得到新的单纯形表格：
x1 x2 x3 RHS
z2 10 15 0 105
s1 5 3 -1 6 s2 5 21 20 30 s3 2 1 0 1
继续进行迭代，选择系数最大的目标函数系数（即15的系数），将其所在列作为入基变量列，找到离基变量行，进行初等行变换，得到新的单纯形表格：
x1 x2 x3 RHS
z2 10 0 15 1415/7
s1 5 0 2/5 49/7 s2 5 0 15/7 57/7 x3 2/5 0 1 3/7
此时所有系数都是非负的，所以可以停止迭代，得到最优解：
x1 = 20/7, x2 = 0, x3 = 321/70, z = 1415/7
原文地址: http://www.cveoy.top/t/topic/buV1 著作权归作者所有。请勿转载和采集!