x2 x1=0 4 x4=0 2 x3=0 x2=0 x1 0 2 4 最优解为（x1，x2）=（4，0），min z=4
单纯形法
1、用单纯形法求解 maxz=50x1+100x2 x1 + x2≤300 2x1 + x2≤400 x2≤250 x1、x2≥0
解：首先将问题化为标准形式，然后将整个计算过程列在一个表中 Cj 50 100 0 0 0 b CB XB x3 x4 x5 x1↓ x2↓ 0 x3 1 1 1 0 0 300 0 x4 2 1 0 1 0 400 [1] x5 0 0 0 1 250 ← 0 100 0 0 0 0 －z 50 0 x3 1 1 0 -1 50 ← 0 0 x4 2 0 0 1 -1 150 100 x2 0 1 0 0 1 250 0 － 0 0 -100 －z 50 25000 50 x1 1 0 1 0 -1 50 0 x4 0 0 -2 1 1 50 100 x2 0 1 0 0 1 250 0 － -50 0 -50 －z 0 27500 由于σj≤0（j=1，…，5），故X*=（50，250，0，50，0）T， Z*=27500
2、用单纯形法求解 maxz=2x1+x2
－x1 + x2≤5
2x1－5x2≤10 x1、x2≥0
解：用单纯形表实现如表1—10 表1—10 Cj 2 1 0 0 b θ CB XB x2 x3 x4 x1↓ 0 x3 -1 1 1 0 5 — x4 [2] -5 0 1 10 10/4(min) ← 0 2 1 0 0 0 －z 0 x3 0 -3/2 1 1/2 10 2 x1 1 -5/2 0 1/2 5 0 6 0 -1 －z －10 σ2=6 >0，且p2≤0，故该线性规划有无界解（无最优解）。 3、用单纯形法（大M法）求解下列线性规划 maxz=3x1－2x2－x3 x1－2x2 + x3≤ 11 －4x1 + x2 +2x3≥ 3 －2x1 +x3=1 x1、x2、x3≥0
解：化为标准形式
maxz=3x1－2x2－x3 x1－2x2 + x3 + x4 = 11 －4x1 + x2 +2x3－x5 = 3 －2x1+x3=1
x1、x2、x3、x4、x5≥0
在第二、三个约束方程中分别加入人工变量x6、x7，构造如下线性规划问题 maxz=3x1－2x2－x3－Mx6－Mx7 x1－2x2 + x3 + x4 = 11 －4x1 + x2 +2x3－x5 + x6 = 3 －2x1 +x3 +x7 =1 x1、x2、x3、x4、x5、x6、x7≥0 用单纯形进行计算，计算过程见表 -1 0 Cj 3 -1 0 -M -M b CB XB x3 x4 x5 x6 x7 x1↓ x2↓ 0 x4 1 -2 1 1 0 0 0 11 -M x6 -4 1 2 0 -1 1 0 3 -M x7 -2 0 [1] 0 0 0 1 1 -1+M -1+3 0 -M 0 0 4M －z 3-6M M 0 x4 3 -2 0 1 0 0 -1 10 -M x6 0 [1] 0 0 -1 1 -2 1 -1 x3 -2 0 1 0 0 0 1 1 -1+M 0 -3M+ 0 -M 0 M+1 －z 1 1 0 x4 [3] 0 0 1 -2 2 -5 12 -1 -1 3 -1 -1 x2 x3 －z x1 x2 x3 0 -2 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1/3 0 2/3 -1 0 -1 -2/3 -1 -4/3 1 0 -M+1 2/3 1 4/3 -2 1 -M-1 -5/3 2 1 1 2 4 1 -7/3 9 0 0 -M+1/-M+2 -1/3 -1/3 －z 0 －2 3 /3 由于σj≤0（j=1，…，7），且基变量中不含人工变量，故X*=（4，1，9）T， z*=2
4、用单纯形法（大M法）求解下列线性规划 maxz=3x1+2x2 2x1+x2≤ 2 3x1 +4x2≥12 x1、x2≥0
解:化为标准形式后引入人工变量x5得到 maxz=3x1+2x2－Mx5 2x1+x2+x3 = 2 3x1 +4x2－x4+x5 =12 x1、…、x5≥0
用单纯形法计算，过程列于表中。 从表中可以看出，虽然检验数均小于或等于零，但基变量中含有非零的人工变量x5=4，所以原问题无可行解。 3 2 0 0 -M b CB xB x1 x2 x3 x4 x5 0 -M 2 -M x3 x5 -z x2 x5 -z 2 3 3+3M 2 -5 -1-5M [1] 4 2+4M 1 0 0 1 0 0 1 -4 -2-4M 0 -1 -M 0 -1 -M 0 1 0 0 1 0 2 12 12M 2 4 -4+4M 2、用单纯形法求解下述LP问题。
max z?2x1?3x2?x1?2x2?8?4x?16 ?1s.. t??4x2?12?xj?0,j?1,2?解：首先将原问题转化为线性规划的标准型，引入松弛变量x3,x4,x5，
可得：
max z?2x1?3x2?x1?2x2?x3?8?4x?x?16 ?14s.. t??4x2?x5?12?xj?0,j?1,2,?,5?构造单纯形表，计算如下：
cB 0 0 0 0 0 3 2 0 3 2 0 3 cj XB x3 x4 x5 2 3 0 0 0 b 8 16 12 2 16 3 2 8 3 4 4 2 x1 1 4 0 2 [1] 4 0 2 1 0 0 0 1 0 0 0 x2 2 0 [4] 3 0 0 1 0 0 0 1 0 0 0 1 0 x3 1 0 0 0 1 0 0 0 1 －4 0 －2 0 －2 1/2 x4 0 1 0 0 0 1 0 0 0 1 0 0 1/4 1/2 －1/8 x5 0 0 1 0 －1/2 0 1/4 －3/4 －1/2 [2] 1/4 1/4 0 1 0 0 ?i 4 － 3 2 4 － － 4 12 ?j x3 x4 x2 ?j x1 x4 x2 ?j x1 x5 x2 ?j －3/2 －1/8 原问题的最优解为X*?(4,2,0,0,4)T，目标函数最大值为
z*?2*4?3*2?14。
3、用单纯形法求解下述LP问题。
max z?3x1?4x2?2x1?x2?40 ?s.. t?x1?3x2?30?x,x?0?12
解：首先将原问题转化为线性规划的标准型，引入松弛变量x3、x4，可得：
max z?3x1?4x2?2x1?x2?x3?40 ?s.. t?x1?3x2?x4?30?x,x,x,x?0?1234构造单纯形表，计算如下：
cj 3 4 0 0 cB 0 0 XB b 40 30 x1 2 1 3 x2 1 [3] 4 0 1 0 0 1 0 x3 1 0 0 1 0 0 3/5 -1/5 -1 x4 0 1 0 -1/3 1/3 -4/3 -1/5 2/5 -1 ?i 40 10 18 30 x3 x4 ?j 0 4 x3 x2 30 10 [5/3] 1/3 5/3 ?j 3 4 x1 x2 18 4 1 0 0 ?j z*?3*18?4*4?70。
由此可得，最优解为X*?(18, 4, 0, 0)T，目标函数值为