单纯形法

线性规划一般形式

在约束条件下、寻找目标函数 z 的最大值

/[max(or / min) / z = /displaystyle/sum_{j=1}^n c_jx_j //
s.t.
/begin{cases}
/displaystyle/sum_{j=1}^n a_{ij}/ /leq/ (or/ =,/geq)/ b_i/quad(i/ = 1,…,m) //
//
x_j/ /geq / 0 /qquad /qquad /qquad /quad / / / (j/ = 1,…,n)
/end{cases}
/]

线性规划的标准形式

标准形需要满足的条件：

1. 目标函数求最大值 max
2. 约束条件均为等式
3. 所有决策变量均为非负约束
4. 约束条件右端常数项 /(b_i/) 全为非负值

一般来说，规定线性规划的标准形式为：

/[max/ z = /displaystyle/sum_{j=1}^n c_jx_j //
s.t.
/begin{cases}
/displaystyle/sum_{j=1}^n a_{ij}/ =/ b_i/qquad /qquad(i/ = 1,…,m) //
//
x_j/ /geq / 0/ ,/ b_i/ /geq / 0 /qquad (j/ = 1,…,n)
/end{cases}
/]

可以写成矩阵形式：

/[max/ z/ = CX //
AX/ =/ b //
X/ /geq / 0 //
A/ =/
/begin{pmatrix}
a_{11} & a_{12} & /cdots & a_{1n} //
/vdots & /vdots & /ddots & /vdots //
a_{m1} & a_{m2} & /cdots & a_{mn}
/end{pmatrix}
/]

将一般线性规划问题化为标准型：

1. 目标函数极大化。（可通过取相反数实现）
2. 将不等式约束条件通过添加松弛变量得到方法华为等式
   • 约束条件为 /(/leq/) 不等式，则在约束条件的左端加上一个非负的松弛变量；
   • 约束条件为 /(/geq/) 不等式，则在约束条件的左端减去一个非负的松弛变量。
3. 取值无约束的变量：
   • 若存在无约束的变量/(x_k/)，可令 /(x_k/ = x_k^{‘}/ -/ x_k^{”}/)，其中 /(x_k^{‘}，x_k^{”}/ /ge / 0/)。

单纯形法求解

几个基本定理：

• 若线性规划问题存在可行解，则问题的可行域是凸集
  • 引理：线性规划问题的可行解 /(X/ =/ (x_1,/cdots,x_n)^{T}/) 为基可行解的充要条件是 /(X/) 的正分量所对应的系数列向量是线性无关的。
• 线性规划问题的基可行解 /(X/) 对应线性规划问题可行域（凸集）的顶点
• 若线性规划问题有最优解一定存在一个基可行解是最优解

单纯形法求解过程：

1. 化为标准型（要求 /(b /ge 0/)）,确定初始基B，建立初始单纯行表(假设A矩阵中存在单位矩阵)
   
2. 其中:

/[/theta/ =/ /min{(/frac{b_i}{a_{ik}}/ |/ a_{ik}/ >/ 0)}
/]

2. 若 /(/sigma_j/ /le 0/ (j/ =/ m+1,/cdots,n)/)，则已得到最优解，否则转入下一步
3. 若在 /(j/ =/ m+1,/cdots,n/) 中，存在 /(/sigma_k/ >/ 0/), 而 /(P_k/ </ 0/)，则无最优解。
4. 确定换入变量和换出变量
   • 由 /(/max(/sigma_k>0)/ =/ /sigma_k/)，确定 /(x_k/) 为换入变量
   • 由 $$/theta/ =/ /min{(/frac{b_i}{a_{ik}}/ |/ a_{ik}/ >/ 0)}/ = /frac{b_l}{a_{lk}}$$ 确定 /(x_l/) 为换出变量。
5. 以 /(a_{lk}/) 为主元进行迭代
   即将

   /[P_k=
   /begin{pmatrix}
   a_{1k} //
   /vdots //
   a_{lk} //
   /vdots //
   a_{mk}
   /end{pmatrix}
   迭代成
   /begin{pmatrix}
   0 //
   /vdots //
   0 //
   1 //
   0 //
   /vdots //
   0
   /end{pmatrix}
   /to l行
   /]

6. 重复 2~5 步骤

单纯形法进一步讨论

• 人工变量法（大M法）
  • 凑单位矩阵添加人工变量
  • 目标函数中人工变量的系数为足够大的一个负值，用“/(-M/)”表示
• 两阶段法
  • 第一阶段实现求解一个目标函数中只包含人工变量的线性规划问题（令目标函数中其他变量的系数取零），人工变量的系数取某个正的常数（一般取1），在保持原问题约束条件不变的情况下求这个目标函数的极小值
    • 当人工变量取值为0时，目标函数值也为0，这时的最优解就是原线性规划问题的的一个可行解
    • 如果第一阶段求解结果表明最优解的目标函数值不为0，即最优解的基变量中含有人工变量，则表明原线性规划问题无可行解
  • 第一阶段表明问题有可行解时，第二阶段从第一阶段的最终单纯形表出发，去掉人工变量，并按问题原来的目标函数，继续寻找问题的最优解