运筹学单纯形法

In Class


这学期修了门选修,讲到这个算法,觉得挺有意思,写写笔记

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

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

可行域的顶点称作基本可行解


下面开始介绍单纯形法的迭代步骤


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.单纯形表


介绍一下该表的各值:
cjxj 对应在目标函数中的系数
CBXB 对应在目标函数中的系数
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↑


  • X0=(0,0,6,12,2)T→Z0=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↑

    迭代结束,找到最优解


Share on : Twitter, Facebook or Google+