例1 用单纯形法解下列问题：
x 4与添加的松弛变量x 5，x 6在约束方程组中其系数列正好构成一个3阶单位阵，它们可以作为初始基变量，初始基可行解为X =（0, 0, 0,10, 8, 4）T
列出初始单纯形表，见表1。
表1
min x 1-2x 2+x 3
s .. t x 1+x 2-2x 3+x 4=10,
2x 1-x 2+4x 3
≤8,
-x 1+2x 2-4x 3≤4, x j ≥0, j =1, , 4.
max -x 1+2x 2-x 3s .. t x 1+x 2-2x 3+x 4
2x 1-x 2+4x 3-x 1+2x 2-4x 3x j ≥0, j =1, ,6.
+x 5
=10, =8, +x 6=4,
解：将原问题化成标准形：
由于只有σ2> 0，说明表中基可行解不是最优解，所以确定x 2为换入非基变量；以x 2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。
θ=min (
1044
, ) =2= 122
因此确定2为主元素（表1中以防括号[]括起），意味着将以非基变量x 2去置换基变量x 6，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x 2的系数列(1, -1, 2)T 变换成x 6的系数列(0, 0, 1)T ，变换之后重新计算检验数。变换结果见表2。
表2
检验数σ3=3>0，当前基可行解仍然不是最优解。继续“换基”，确定2为主元素，即以非基变量x 3置换基变量x 5。变换结果见表3。
表3
*T
此时，3个非基变量的检验数都小于0，σ1= -9/4，σ5= -3/2，σ5= -7/4，表明已求得最优解：X =(0, 12, 5, 8, 0, 0) 。
*T
去除添加的松弛变量，原问题的最优解为：X =(0, 12, 5, 8) , 最小值为-19
例2 用大M 法求解下列问题：
min x 1+x 2-3x 3
s .. t x 1-2x 2+x 3≤11,
2x 1+x 2-4x 3≥3, x 1
解 引进松弛变量x 4、、剩余变量x 5和人工变量x 6、x 7，解下列问题：
-2x 3=1,
x j ≥0, j =1, ,3.
min x 1+x 2-3x 3+0x 4+0x 5+M (x 6+x 7) s .. t x 1-2x 2+x 3+x 4
2x 1+x 2-4x 3x 1
用单纯形法计算如下：
=11=3
-x 5+x 6
-2x 3+x 7=1
x j ≥0, j =1, 2, ,7
由于σ1
θ=min (
11311
, , ) =1= 1211
因此确定1为主元素（表1中以防括号[]括起），意味着将以非基变量x 1去置换基变量x 7，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x 1的系数列(1, 2, 1)T 变换成x 7的系数列(0, 0, 1)T ，变换之后重新计算检验数。变换结果见表2。
由于σ2
由于只有σ3
表4
至此，无负的检验数且基变量中不含人工变量（即人工变量在基可行解中取0值），求得原问题的最优解：x 1=9，
*x 2=1，x 3
*
*
=4，最小目标函数值为-2。
例3 用两阶段法求解下列问题：
max 2x 1-x 2s .. t x 1+x 2≥2,
x 1-x 2≥1, x 1
≤3, x 1, x 2≥0.
解 将原问题化成标准形为：
max 2x 1-x 2s .. t x 1+x 2-x 3
x 1-x 2x 1
-x 4
=2=1+x 5=3
x 1, x 2 , x 5≥0
第一阶段 用单纯形法求解第一阶段的线性规划问题：
min ω=x 6+x 7s .. t x 1+x 2-x 3
+x 6
-x 4
+x 5
=2+x 7=1
=3
x 1-x 2x 1
x 1, x 2 , x 7≥0
求解过程见表1。
表1
T T
因此，第一阶段求得最优解为(x 1, x 2, x 3，x 4, x 5) =(, ,0,0, ，基变量为x 1、x 2和x 5，不包含人工变量。
312232
第二阶段 以第一阶段的最终单纯形表为基础，除去人工变量x 6、x 7及其系数列，恢复目标价值向量为C =（2, -1, 0, 0, 0）T ，重新计算检验数，继续迭代，见表2。
表2
因此，求得原问题的最优解为(x 1, x 2, x 3，x 4, x 5) 例4写出下列问题的Lagrange 函数及该问题的K-T 条件
T
=(3,0,1,2,0)T
，最大目标函数值为6。
min f (x 1, x 2) =(x 1-1) 2+(x 2-2) 2s .. t g 1(x 1, x 2) =x 1+x 2-2≤0
g 2(x 1, x 2) =-x 1≤0g 3(x 1, x 2) =-x 2≤0h 1(x 1, x 2) =-x 1+x 2-1=0
解该问题的Lagrange 函数是
+λ2(-x 2) L (X , λ, μ) =(x 1-1) 2+(x 2-2) 2+λ（）1x 1+x 2-2+λ3(-x 2) +μ(-x 1+x 2-1)
由于
∂L
=2(x 1-1) +λ1-λ2-μ ∂x 1∂L
=2(x 2-2) +λ1-λ3+μ ∂x 2
故该问题的K —T 条件是
⎧2(x 1-1) +λ1-λ2-μ=0⎪2(x -2) +λ-λ+μ=0
13⎪2
⎪⎪λ1(x 1+x 2-2) =0
⎨
⎪λ2x 1=0⎪λ3x 2=0⎪⎪⎩λ1, λ2, λ3≥0
例5 用0.618法求解问题min f (x ) =x -2x +1的近似最优解，已知f (x ) 的单谷区间为[0, 3]，要求最后区间精度ε=0. 5。
x ≥0
3
解 a =0, b =3， x 1=a +0. 382(b -a ) =1. 146，f 1=f (x 1) =0. 2131； x 2=a +0. 618(b -a ) =1. 1854，f 2=f (x 2) =3. 6648； 因为 f 1
a =0, b =x 2=1. 854， x 2=x 1=1. 146, f 2=f 1=0. 2131；
x 1=a +0. 382(b -a ) =0. 708，f 1=f (x 1) =-0. 0611； 因为 f 1
f 2=f 1=-0. 061；1 a =0, b =x 2=1. 146， x 2=x 1=0. 708, 6
x 1=a +0. 382(b -a ) =0. 438，f 1=f (x 1) =0. 208； 因为 f 1>f 2，所以向右搜索，则
, f 1=f 2=-0. 0611； a =0. 438, b =x 2=1. 146，x 1=x 2=0. 7086
x 2=a +0. 618(b -a ) =0. 876，f 2=f (x 2) =-0. 0798； 因为 f 1>f 2，所以向右搜索，则 a =0. 708, b =x 2=1. 146，x 1=x 2=0. 876, f 1=f 2=-0. 0798；
x 2=a +0. 618(b -a ) =0. 9787，f 2=f (x 2) =-0. 0199； 因为b -a =0. 438
x *=
a +b 0. 708+1. 146
==0. 927。 22
例6 用FR 共轭梯度法求解问题min
⎛5⎫2-6
f (x )=x 12+2x 2，要求选取初始点x 0= ⎪, ε=10。
⎝5⎭
⎛10⎫⎛-10⎫⎛2x 1⎫
⎪⎪g =d =-g =解 ∇f (x ) = ，，000 20⎪ -20⎪⎪， 4x ⎪
⎝⎭⎝⎭⎝2⎭
⎛5-10α⎫22
f (x 0+αd 0) =f 5-20α⎪⎪=(5-10α) +2(5-20α) ，
⎝⎭
⎛20⎫
⎪d 51009 令f (x +αd 0) =1800α-500=0，则α0=，于是x =x +α0d 0= ⎪；
d α18 -5⎪
⎪⎝9⎭⎛40⎫⎛400⎫
T ⎪ -⎪g 1g 141819 ⎪， ⎪ 则g 1=∇f (x ) =，g 1=，β0=，d 1=-g 1+β0d 0==T 100209 ⎪ -⎪g 0g 081 ⎪ ⎪
⎝81⎭⎝9⎭
f (x 1+αd 1) = 令
400205020α2
(1-α) 2+(-1+) ， 819819
⎛0⎫d 9
，于是x 2=x 1+α1d 1= f (x 1+αd 1) =0，则α1= 0⎪⎪； d α20⎝⎭
⎛0⎫*2⎛0⎫⎪x =x = 则g 2=∇f (x 2) = ，，故g =0
例7 用内罚函数法求解：
1
(x 1+1) 3+x 212
s .. t x 1-1≥0
min
x 2≥0
解 定义障碍函数 P (x , r k ) =
111
(x 1+1) 3+x 2+r k (+) ， 12x 1-1x 2
用解析法求min P (x , r k ) ， 令
∂P (x , r k ) 1r k
=(x 1+1) 2-=0，
2∂x 14(x 1-1) ∂P (x , r k ) r
=1-k =0， ∂x 2x 22
解得：r k =(x 1, x 2) T =(+2r k , k ) T 。 当r k →0时，r k →=(1, 0) T ，
故=(1, 0) T 是原问题的最优解。
例1 用单纯形法解下列问题：
x 4与添加的松弛变量x 5，x 6在约束方程组中其系数列正好构成一个3阶单位阵，它们可以作为初始基变量，初始基可行解为X =（0, 0, 0,10, 8, 4）T
列出初始单纯形表，见表1。
表1
min x 1-2x 2+x 3
s .. t x 1+x 2-2x 3+x 4=10,
2x 1-x 2+4x 3
≤8,
-x 1+2x 2-4x 3≤4, x j ≥0, j =1, , 4.
max -x 1+2x 2-x 3s .. t x 1+x 2-2x 3+x 4
2x 1-x 2+4x 3-x 1+2x 2-4x 3x j ≥0, j =1, ,6.
+x 5
=10, =8, +x 6=4,
解：将原问题化成标准形：
由于只有σ2> 0，说明表中基可行解不是最优解，所以确定x 2为换入非基变量；以x 2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。
θ=min (
1044
, ) =2= 122
因此确定2为主元素（表1中以防括号[]括起），意味着将以非基变量x 2去置换基变量x 6，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x 2的系数列(1, -1, 2)T 变换成x 6的系数列(0, 0, 1)T ，变换之后重新计算检验数。变换结果见表2。
表2
检验数σ3=3>0，当前基可行解仍然不是最优解。继续“换基”，确定2为主元素，即以非基变量x 3置换基变量x 5。变换结果见表3。
表3
*T
此时，3个非基变量的检验数都小于0，σ1= -9/4，σ5= -3/2，σ5= -7/4，表明已求得最优解：X =(0, 12, 5, 8, 0, 0) 。
*T
去除添加的松弛变量，原问题的最优解为：X =(0, 12, 5, 8) , 最小值为-19
例2 用大M 法求解下列问题：
min x 1+x 2-3x 3
s .. t x 1-2x 2+x 3≤11,
2x 1+x 2-4x 3≥3, x 1
解 引进松弛变量x 4、、剩余变量x 5和人工变量x 6、x 7，解下列问题：
-2x 3=1,
x j ≥0, j =1, ,3.
min x 1+x 2-3x 3+0x 4+0x 5+M (x 6+x 7) s .. t x 1-2x 2+x 3+x 4
2x 1+x 2-4x 3x 1
用单纯形法计算如下：
=11=3
-x 5+x 6
-2x 3+x 7=1
x j ≥0, j =1, 2, ,7
由于σ1
θ=min (
11311
, , ) =1= 1211
因此确定1为主元素（表1中以防括号[]括起），意味着将以非基变量x 1去置换基变量x 7，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x 1的系数列(1, 2, 1)T 变换成x 7的系数列(0, 0, 1)T ，变换之后重新计算检验数。变换结果见表2。
由于σ2
由于只有σ3
表4
至此，无负的检验数且基变量中不含人工变量（即人工变量在基可行解中取0值），求得原问题的最优解：x 1=9，
*x 2=1，x 3
*
*
=4，最小目标函数值为-2。
例3 用两阶段法求解下列问题：
max 2x 1-x 2s .. t x 1+x 2≥2,
x 1-x 2≥1, x 1
≤3, x 1, x 2≥0.
解 将原问题化成标准形为：
max 2x 1-x 2s .. t x 1+x 2-x 3
x 1-x 2x 1
-x 4
=2=1+x 5=3
x 1, x 2 , x 5≥0
第一阶段 用单纯形法求解第一阶段的线性规划问题：
min ω=x 6+x 7s .. t x 1+x 2-x 3
+x 6
-x 4
+x 5
=2+x 7=1
=3
x 1-x 2x 1
x 1, x 2 , x 7≥0
求解过程见表1。
表1
T T
因此，第一阶段求得最优解为(x 1, x 2, x 3，x 4, x 5) =(, ,0,0, ，基变量为x 1、x 2和x 5，不包含人工变量。
312232
第二阶段 以第一阶段的最终单纯形表为基础，除去人工变量x 6、x 7及其系数列，恢复目标价值向量为C =（2, -1, 0, 0, 0）T ，重新计算检验数，继续迭代，见表2。
表2
因此，求得原问题的最优解为(x 1, x 2, x 3，x 4, x 5) 例4写出下列问题的Lagrange 函数及该问题的K-T 条件
T
=(3,0,1,2,0)T
，最大目标函数值为6。
min f (x 1, x 2) =(x 1-1) 2+(x 2-2) 2s .. t g 1(x 1, x 2) =x 1+x 2-2≤0
g 2(x 1, x 2) =-x 1≤0g 3(x 1, x 2) =-x 2≤0h 1(x 1, x 2) =-x 1+x 2-1=0
解该问题的Lagrange 函数是
+λ2(-x 2) L (X , λ, μ) =(x 1-1) 2+(x 2-2) 2+λ（）1x 1+x 2-2+λ3(-x 2) +μ(-x 1+x 2-1)
由于
∂L
=2(x 1-1) +λ1-λ2-μ ∂x 1∂L
=2(x 2-2) +λ1-λ3+μ ∂x 2
故该问题的K —T 条件是
⎧2(x 1-1) +λ1-λ2-μ=0⎪2(x -2) +λ-λ+μ=0
13⎪2
⎪⎪λ1(x 1+x 2-2) =0
⎨
⎪λ2x 1=0⎪λ3x 2=0⎪⎪⎩λ1, λ2, λ3≥0
例5 用0.618法求解问题min f (x ) =x -2x +1的近似最优解，已知f (x ) 的单谷区间为[0, 3]，要求最后区间精度ε=0. 5。
x ≥0
3
解 a =0, b =3， x 1=a +0. 382(b -a ) =1. 146，f 1=f (x 1) =0. 2131； x 2=a +0. 618(b -a ) =1. 1854，f 2=f (x 2) =3. 6648； 因为 f 1
a =0, b =x 2=1. 854， x 2=x 1=1. 146, f 2=f 1=0. 2131；
x 1=a +0. 382(b -a ) =0. 708，f 1=f (x 1) =-0. 0611； 因为 f 1
f 2=f 1=-0. 061；1 a =0, b =x 2=1. 146， x 2=x 1=0. 708, 6
x 1=a +0. 382(b -a ) =0. 438，f 1=f (x 1) =0. 208； 因为 f 1>f 2，所以向右搜索，则
, f 1=f 2=-0. 0611； a =0. 438, b =x 2=1. 146，x 1=x 2=0. 7086
x 2=a +0. 618(b -a ) =0. 876，f 2=f (x 2) =-0. 0798； 因为 f 1>f 2，所以向右搜索，则 a =0. 708, b =x 2=1. 146，x 1=x 2=0. 876, f 1=f 2=-0. 0798；
x 2=a +0. 618(b -a ) =0. 9787，f 2=f (x 2) =-0. 0199； 因为b -a =0. 438
x *=
a +b 0. 708+1. 146
==0. 927。 22
例6 用FR 共轭梯度法求解问题min
⎛5⎫2-6
f (x )=x 12+2x 2，要求选取初始点x 0= ⎪, ε=10。
⎝5⎭
⎛10⎫⎛-10⎫⎛2x 1⎫
⎪⎪g =d =-g =解 ∇f (x ) = ，，000 20⎪ -20⎪⎪， 4x ⎪
⎝⎭⎝⎭⎝2⎭
⎛5-10α⎫22
f (x 0+αd 0) =f 5-20α⎪⎪=(5-10α) +2(5-20α) ，
⎝⎭
⎛20⎫
⎪d 51009 令f (x +αd 0) =1800α-500=0，则α0=，于是x =x +α0d 0= ⎪；
d α18 -5⎪
⎪⎝9⎭⎛40⎫⎛400⎫
T ⎪ -⎪g 1g 141819 ⎪， ⎪ 则g 1=∇f (x ) =，g 1=，β0=，d 1=-g 1+β0d 0==T 100209 ⎪ -⎪g 0g 081 ⎪ ⎪
⎝81⎭⎝9⎭
f (x 1+αd 1) = 令
400205020α2
(1-α) 2+(-1+) ， 819819
⎛0⎫d 9
，于是x 2=x 1+α1d 1= f (x 1+αd 1) =0，则α1= 0⎪⎪； d α20⎝⎭
⎛0⎫*2⎛0⎫⎪x =x = 则g 2=∇f (x 2) = ，，故g =0
例7 用内罚函数法求解：
1
(x 1+1) 3+x 212
s .. t x 1-1≥0
min
x 2≥0
解 定义障碍函数 P (x , r k ) =
111
(x 1+1) 3+x 2+r k (+) ， 12x 1-1x 2
用解析法求min P (x , r k ) ， 令
∂P (x , r k ) 1r k
=(x 1+1) 2-=0，
2∂x 14(x 1-1) ∂P (x , r k ) r
=1-k =0， ∂x 2x 22
解得：r k =(x 1, x 2) T =(+2r k , k ) T 。 当r k →0时，r k →=(1, 0) T ，
故=(1, 0) T 是原问题的最优解。