Optimization Simplex method

线性规划与单纯形法

---

标准形式

对于一般的线性规划有如下的标准矩阵形式

$Max\quad z = c^Tx\\ s.t. \begin{cases} Ax\le b\\ x\ge 0 \end{cases}$

其中$x$为未知变量，A为系数矩阵，$z$为目标函数，$c$为目标系数向量

归纳后有以下特点

• 线性规划模型特点
  1. 决策变量：非负：注意未限制的决策变量
  2. 约束条件：变为等式
  3. 最优化目标：最大化目标
  4. 是线性函数

对于非标准类型可以直接转化为标准型，下面给出具体方法

• 标准形式转化

  1. 极小化目标函数问题：转为极大化目标函数

  2. 约束条件不是等式：引进松弛变量

  3. 变量无符号限制：引进正负变量

  4. 右端存在负值：相反

线性规划的解

• 线性规划解情况
  • 存在有限最优解
    • 唯一最优解、无限最优解
  • 无有限最优解
  • 无最优解
• 基、基变量
  • 代换条件极值，解出一部分值，转化为非条件极值
• 凸集、超平面：已介绍

好的你已经了解了线性规划的标准型

单纯型法

• 基本定义

  首先保证标准型是的系数矩阵$A\in R^{m\times n}$ 的秩为$m$

  矩阵$A$的$C_n^m$个$m$阶子矩阵，其中划分为非奇异矩阵$B$便是矩阵的基，剩余的奇异矩阵为$N$

  则$A = (B,N)$， $x = (x_B,x_N)^T$

  从而

  $Ax=b\Rightarrow Bx_b+Nx_N = b$

  此时对于$x_N$ ，$x_B$有唯一值对应：

  $x_B = B^{-1}b-B^{-1}Nx_N$

  则对于可行解：令非基变量$x_N$为零，则可以得到关于$B$的$m$阶线性方程。此方程得到的值称为基本解

• 基本原理

  定理1：若线性规划问题存在可行解，则线性规划的可行域是凸集

  定理2：线性规划问题的基可行解X对应 可行域（凸集）的顶点

  定理3：若线性规划存在最优解，则一定在可行解上

  然而实际中对于可行域的顶点逐个寻找的时间复杂度过于高，如今流传最广的方法便是单纯形法

  基本步骤如下：

  1. 将矩阵分为标准基与非标准基，确定基本的参数

  2. 存在一种检验数向量使得当存在检验数大于零时表示此解还可优化，若检验数向量$\sigma\le 0$表示已经达到了最优解。 如果达到了最优解则退出，否则向下进行

     并且每一个$x_i$对应一个$\sigma_i$ ，当$\sigma_i>0$是表示此解的数值提升会使得目标函数增加，选择一个$\sigma_i>0$对应的变量$x_j$进行增加，相应的满足等式使得其他的变量减小

  3. 由于所有变量的非负性，在有一个变量变为0时停止。此时达到了另一个”顶点“，重新计算检验数，重复步骤2

  • 检验数的原理

    将上述式子带入到目标函数$z=c^Tx+b$中,已知,$x_B = B^{-1}b-B^{-1}Nx_N$, 有

    $z = c^Tx=c^T_Bx_B+c^T_Nx_N\\ = c_B^T B^{-1}b-(c_B^TB^{-1}N-c^T_N)x_N$

    已知标准形式是最大化目标：且$c_B^T B^{-1}b, \quad x_N$都是定值，所以令

    $\sigma_N = -c_B^TB^{-1}N+c^T_N$

    当$\sigma_N$ 增大即可认为目标函数增大，对于$\sigma_B$作为零处理，所以在增大一个非基变量$x_i$减小基变量$x_j...$可以保证一定会让矩阵想着更优解运行。

  最后对于其他解解的情况，

  • 无穷最优解

    往往是当检验数全为零，或者是得到的解向量存在非基变量不为零，也即该变量的变化对最优化目标无影响。即无穷最优解

  • 无解

    一般来讲很少出现无解的情况。。。往往是在寻找解的过程出现循环，。即无解。可以用bland方法，摄动法，和辞典序法来消除循环的影响。

---

总结

最后简单解释下单纯形法的原理

初始化一个解，从一个极点出发，不断增大减小变量数值也即保证沿着可行域的边界移动，并且保证找到的新极点的目标值比当前目标函数值不减

实际计算往往使用下图表不断迭代进行。了解原理后计算一次便可了解具体算法

参考

1. 最优化：建模、算法与理论 刘浩洋,户将,李勇锋,文再文著

2. 最优化理论与算法 第2版第二版 陈宝林 清华大学出版社

3. 单纯形法判断无解的情况

4. 吴祈宗 运筹学[M].机械工业出版社:,