我们知道,如果线性规划有有限的最优解,那么该最优解一定可以在可行域的顶点上取到。

单纯形法便是从初始顶点开始,通过最优性判别准则判断,若不是最优,则转移到新顶点迭代,新顶点的目标值必然优于上一个,直到找到最优值停止迭代。

可行域的顶点称作基本可行解,下面开始介绍单纯形法的迭代步骤。


1.化标准型

基变量: x3 , x4 , x5 →只出现在其中一个方程且系数为1
非基变量: x1 , x2
基本可行解: X=(x1,x2,x3,x4,x5)T→非基变量取值全为0的可行解
初始基本可行解: X0=(0,0,6,12,2)T


非退化基本可行解:基变量都大于0的基本可行解
退化基本可行解:至少有一个基变量等于0的基本可行解


2.单纯形表

介绍一下该表的各值:
cj xj 对应在目标函数中的系数
CB XB 对应在目标函数中的系数
pj 为 xjT
b: 为约束方程右边的值

检验数(λj=cj-CBpj) : 对于某个基本可行解,若它的检验数都≤0,它便是最优解

目标值(Zj=CBb) : 单纯形表中填的是目标值的相反数,即加上负号

由最优性判别准则(对于某个基本可行解,若它的检验数都≤0,它便是最优解)知道该表不是最优表,于是需要通过变换基本可行解来优化目标值

3.迭代方法

X=(x1,x2,x3,x4,x5)T
X0=(0,0,6,12,2)T→Z0=0
X1=(0,θ,x3‘,x4‘,x5’)T→Z1=4θ↑
maxZ=3x1+4x2=3×0+4×θ=4θ
X1=(θ,0,x3’‘,x4’‘,x5’’)T→Z1=3θ↑
maxZ=3x1+4x2=3×θ+4×0=3θ

选增大倍数大的,即
λk=max{λjj>0}→xk为进基变量
λ2=max{λ12>0}→x2为进基变量

θ=min{6/2,12/2,2/1}=2→x5为离基变量

x3‘=6-2θ=2
x4‘=12-2θ=8
x5‘=2-θ=0
X1=(0,2,2,8,0)T→Z1=8↑

离基变量的确定遵循最小非负比准则

该处p2为(2,2,1)T均>0,若存在≤0的则考虑非负部分即可

X1=(0,2,2,8,0)T→Z1=8↑

由最优性判别准则知该表不是最优表,继续迭代,方法如上,以下列出相应迭代后的表格

X2=(2,2,0,2,0)T→Z2=14↑

X=(3,3/2,0,0,1/2)T→Z=15↑


迭代结束,找到最优解