1 线性规划问题 以及可行域与基本可行解 （1）一般形式 ： m i n Z minZ minZ = C 1 C_1 C1​ X 1 X_1 X1​+ C 2 C_2 C2​ X 2 X_2 X2​+ C 3 C_3 C3​ X 3 X_3 X3​+…+ C n C_n Cn​ X n X_n Xn​ a 11 a_{11} a11​ x 1 x_1 x1​+ a 12 a_{12} a12​ x 2 x_2 x2​+ a 13 a_{13} a13​ x 3 x_3 x3​+…+ a 1 n a_{1n} a1n​ x n x_n xn​= b 1 b1 b1 … a m 1 a_{m1} am1​ x 1 x_1 x1​+ a m 2 a_{m2} am2​ x 2 x_2 x2​+…+ a m n a_{mn} amn​ x n x_n xn​>= b m bm bm x j x_{j} xj​>=0 , j j j=1,2,3… q q q, x j x_{j} xj​无限制 , j j j= q q q…n

(2)标准型是约束方程为等号，所有的变量取非负数。对于非负的约束可以通 过引入剩余变量或者松弛变量变为等式，对于无限制的变量可以转化为两个正的变量相减的形式。将目标函数转化为 m i n min min 的形式。

(3) 可行解：满足所有的约束条件的向量（ x 1 x 2 . . . x n x_{1} x_{2}...x_{n} x1​x2​...xn​） T ^T T 可行域 ：可行解的集合 最优解 可行域中目标函数最优的可行解 （4）基本可行解与基本定理 分块 ，分为满秩矩阵B ,以及矩阵N ，由AX =b 得到B x B x_{B} xB​+N x N x_{N} xN​=b x B x_{B} xB​= B − 1 b − B^{-1}b- B−1b− B − 1 N x N B^{-1}Nx_{N} B−1NxN​ 令 x N = 0 x_{N}=0 xN​=0 ，得到了一组解。 基与基向量：设B是秩为m的约束矩阵的A的一个m阶满秩子方阵，B中的列向量称为基向量 基变量 基向量对应的变量称为基变量，同理称为非基变量 基本可行解 当 x B x_{B} xB​>=0 时为基本可行解 （最优解一定是可行解，但不一定是基本可行解，也不一定是基本解） 总结 如果基本可行解的个数有限，可以在基本可行解中寻找最优解

2单纯形表法 主要的思路： 先寻找一个基本可行解，判断是不是最优解，如果不是就寻找一个更好的可行解，如此迭代直到找到最优解或者是问题无界。 首先寻找一个基本可行解： x B x_{B} xB​+ B − 1 N x N = B − 1 b B^{-1}Nx_{N}=B^{-1}b B−1NxN​=B−1b c T x = c B T x B + c N T x N c^{T}x=c^{T}_{B}x_{B}+c^{T}_{N}x_{N} cTx=cBT​xB​+cNT​xN​ (1) 令B对应的检验数为0，对应的目标函数可以写为 c B T B − 1 b − γ T c_{B}^{T}B^{-1}b-\gamma^{T} cBT​B−1b−γT 其中 γ T = ( γ B T , γ N T ) \gamma^{T}=(\gamma^{T}_{B},\gamma_{N}^{T}) γT=(γBT​,γNT​) 从以上的式子中看出当 γ N T \gamma^{T}_{N} γNT​中的系数是小于0 是最优的。 所以根据第一个知识点的回顾，首先将问题转化为标准型的问题，将目标函数中基变量的系数变为0，找到一个基本可行解之后判断是不是最优的，方法很简单看目标函数中的非基变量的系数是不是负的，如果不是那么进行迭代。最终得到最优解，或者是无界。 上述的证明中其实就包含了主要的思路。

3两阶段法 当转化为典式后，基变量不好确定时候可以使用添加人工变量的方式找到这个秩。 引入辅助问题 m i n min min g = ∑ i = n + 1 n + m x i g=\sum_{i=n+1}^{n+m}x_{i} g=∑i=n+1n+m​xi​ s . t . { A x + x a = b x ≥ 0 x a ≥ 0 (1) s.t.\begin{cases} Ax+x_{a}=b \\ x \geq 0 \quad x_{a}\geq0 \end{cases}\tag{1} s.t.{Ax+xa​=bx≥0xa​≥0​(1) 对于辅助问题也是有要求最优值的，先给出辅助问题与原问题之间的关系 给出 如果原问题是最优解的话，辅助问题是的最优值是0，反之也是成立的。 求解辅助问题 l p lp lp会得到以下的情况： （1）问题 g g g的最优解是0,并且人工变量是 非基变量，那么对应到原问题就是有最优解的。 （2）辅助问题的最优解＞0 原问题是没有基本可行解的， （3）辅助问题Lp的最优解等于0，但是存在人工变量是基变量，这种需要进一步的判断。 此时假设人工变量 x r x_{r} xr​是基变量（ n + 1 < r < n + m n+1