From 26c4a85872fc6cccd335605b74231849d32d1d39 Mon Sep 17 00:00:00 2001
From: Ir1dXD <sirius.caffrey@gmail.com>
Date: Sat, 6 Jul 2019 13:26:18 +0800
Subject: [PATCH] try to fix mathjax

---
 docs/math/simplex.md | 51 ++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 36 insertions(+), 15 deletions(-)

diff --git a/docs/math/simplex.md b/docs/math/simplex.md
index fb3e8702..4f3dffe1 100644
--- a/docs/math/simplex.md
+++ b/docs/math/simplex.md
@@ -6,9 +6,10 @@
 
 ## 2. 线性规划的一般形式
 
-在约束条件下，寻找目标函数 $$z$$ 的最大值：
+在约束条件下，寻找目标函数 $z$ 的最大值：
+
 $$
-max \ z = x_1 + x_2
+\max \ z = x_1 + x_2
 $$
 
 $$
@@ -28,11 +29,13 @@ $$
 ![kexingyu](./images/kexingyu.jpg)
 
 <center>图1 可行域</center>
+
 ## 4. 线性规划的标准形式
 
 在说明单纯形法的原理之前，需要明白线性规划的标准形式。因为单纯形算法是通过线性规划的标准形来求解的。一般，规定线性规划的标准形式为：
+
 $$
-max \ z = \sum_{j = 1}^{n}c_jx_j
+\max \ z = \sum_{j = 1}^{n}c_jx_j
 $$
 
 $$
@@ -43,8 +46,9 @@ xj \geq 0 , j = 1,2,...,n  \\
 $$
 
 写成矩阵形式：
+
 $$
-max \ z = CX
+\max \ z = CX
 $$
 
 $$
@@ -115,17 +119,22 @@ $$
 
 ### 5.1 几何意义
 
-在标准形中，有 $m$ 个约束条件（不包括非负约束），$n$ 个决策变量，且 $$n \geq m$$。首先选取 $m$ 个基变量$$x_j^{'}(j = 1, 2, \ldots, m )$$，基变量对应约束系数矩阵的列向量线性无关。通过矩阵的线性变换，基变量可由非基变量表示：
+在标准形中，有 $m$ 个约束条件（不包括非负约束），$n$ 个决策变量，且 $n \geq m$。首先选取 $m$ 个基变量 $x_j^{'}(j = 1, 2, \ldots, m )$，基变量对应约束系数矩阵的列向量线性无关。通过矩阵的线性变换，基变量可由非基变量表示：
+
 $$
 x_i^{'} = C_i + \sum_{j = m + 1}^{n}m_{ij}x_j^{'}(i = 1, 2, \ldots , m)
 $$
+
 如果令非基变量等于$0$，可求得基变量的值 ：
+
 $$
 x_i^{'} = C_i
 $$
+
 如果为可行解的话，$C_i$ 大于 $0$ 。那么它的几何意义是什么呢？
 
 还是通过上述具体的线性规划问题来说明：
+
 $$
 max \ z = x_1 + x_2
 $$
@@ -139,26 +148,33 @@ x_1, x_2, x_3, x_4 \geq 0
 $$
 
 如果选择 $x_2$ 、$x_3$ 为基变量，那么令 $x_1$、$x_4$ 等于 $0$ ，可以去求解基变量 $x_2$ 、$x_3$ 的值。对系数矩阵做行变换，如下所示，$x_2=9/2$ ，$x_3=15/2$。
+
 $$
 \left[\begin{array}{ccccc}{\mathrm{X}} & {x_{1}} & {x_{2}} & {x_{3}} & {x_{4}} & {b} \\ {} & {2} & {1} & {1} & {0} & {12} \\ {} & {1} & {2} & {0} & {1} & {9} \\ {\mathrm{C}} & {1} & {1} & {0} & {0} & {z}\end{array}\right] \rightarrow\left[\begin{array}{ccccc}{\mathrm{X}} & {x_{1}} & {x_{2}} & {x_{3}} & {x_{4}} & {b} \\ {} & {\frac{3}{2}} & {0} & {1} & {-\frac{1}{2}} & {\frac{15}{2}} \\ {} & {\frac{1}{2}} & {1} & {0} & {\frac{1}{2}} & {\frac{9}{2}} \\ {\mathrm{C}} & {\frac{1}{2}} & {0} & {0} & {-\frac{1}{2}} & {z-\frac{9}{2}}\end{array}\right]
 $$
+
 $X_1=0$ 表示可行解在 $x$ 轴上；$X_4=0$ 表示可行解在 $x_1+2x_2=9$ 的直线上。那么，求得的可行解即表示这两条直线的交点，也是可行域的顶点，如图所示：
 
 ![kexingyu_point](./images/kexingyu_point.jpg)
 
 <center>图2</center>
+
 所以，通过选择不同的基变量，可以获得不同的可行域的顶点。
 
 ### 5.2 如何判断最优
 
 如前所述，基变量可由非基变量表示：
+
 $$
 x_i^{'} = C_i + \sum_{j = m + 1}^{n}m_{ij}x_j^{'}(i = 1, 2, \ldots , m) 
 $$
+
 目标函数 $z$ 也可以完全由非基变量表示：
+
 $$
 z = z_0 + \sum_{j = m + 1}^{n} \sigma_j x_j^{'}
 $$
+
 当达到最优解时，所有的 $\sigma_j$ 应小于等于 $0$，当存在 $j$，$\sigma_j > 0$ 时，当前解不是最优解，为什么？
 
 当前的目标函数值为 $z_0$ ，其中所有的非基变量值均取 $0$。由之前分析可知，$x_j^{'} = 0$ 代表可行域的某个边界，是 $x_j^{'}$ 的最小值。如果可行解逐步离开这个边界，$x_j^{'}$ 会变大，因为 $\sigma_j > 0$，显然目标函数的取值也会变大，所以当前解不是最优解。我们需要寻找新的基变量。
@@ -172,9 +188,11 @@ $$
 假如我们选择非基变量 $x_s^{'}$ 作为下一轮的基变量，那么被替换基变量 $x_j^{'}$ 在下一轮中作为非基变量，等于 $0$。选择 $x_j^{'}$ 的原则：替换后应该尽量使 $x_s^{'}$ 值最大（因为上面已分析过，目标函数会随着 $x_s^{'}$ 的增大而增大）。
 
 继续通过上面的例子来说明：
+
 $$
 \left[\begin{array}{ccccc}{\mathrm{X}} & {x_{1}} & {x_{2}} & {x_{3}} & {x_{4}} & {b} \\ {} & {2} & {1} & {1} & {0} & {12} \\ {} & {1} & {2} & {0} & {1} & {9} \\ {\mathrm{C}} & {1} & {1} & {0} & {0} & {z}\end{array}\right] \rightarrow\left[\begin{array}{ccccc}{\mathrm{X}} & {x_{1}} & {x_{2}} & {x_{3}} & {x_{4}} & {b} \\ {} & {\frac{3}{2}} & {0} & {1} & {-\frac{1}{2}} & {\frac{15}{2}} \\ {} & {\frac{1}{2}} & {1} & {0} & {\frac{1}{2}} & {\frac{9}{2}} \\ {\mathrm{C}} & {\frac{1}{2}} & {0} & {0} & {-\frac{1}{2}} & {z-\frac{9}{2}}\end{array}\right]
 $$
+
 从最后一行可以看到，$x_1$的系数为 $1/2>0$ ，所以选 $x_2$、$x_3$ 为基变量并没有是目标函数达到最优。下一轮选取 $x_1$ 作为基变量，替换 $x_2$、$x_3$ 中的某个变量。
 
 第一行是符号
@@ -196,8 +214,9 @@ $$
 算法和使用单纯性表求解线性规划相同。
 
 对于线性规划问题：
+
 $$
-max \ x_1 + 14x_2 + 6x_3
+\max \ x_1 + 14x_2 + 6x_3
 $$
 
 $$
@@ -212,7 +231,7 @@ $$
 
 我们可以得到其松弛形式：
 $$
-max \ x_1 + 14x_2 + 6x_3
+\max \ x_1 + 14x_2 + 6x_3
 $$
 
 $$
@@ -240,7 +259,7 @@ $$
 
 其实我们由于每个 $x$ 都大于零，对于 $x_2$ 它的增加是有所限制的，如果 $x_2$ 过大，由于其他的限制条件，就会使得其他的 $x$ 小于零，于是我们应该让 $x_2$ 一直增大，直到有一个其他的 $x$ 刚好等于 $0$ 为止，那么这个 $x$ 就被换出轴。
 
-我们可以发现，对于约束方程 $1$ ，即第一行约束，$x_2$ 最大可以为 $4$（$4/1$），对于约束方程 $4$，$x_2$ 最大可以为 $2$（$6/3$），因此 $x _2$ 最大只能为他们之间最小的那个，这样才能保证每个 $x$ 都大于零。因此使用第 $4$ 行，来对各行进行高斯行变换，使得第二列第四行中的每个 $x$ 都变成零，也包括 $c_2$。这样我们就完成了把 $x_2$ 入轴，$x_7$ 出轴的过程。变换后的单纯性表为：
+我们可以发现，对于约束方程 $1$ ，即第一行约束，$x_2$ 最大可以为 $4$（$4/1$），对于约束方程 $4$，$x_2$ 最大可以为 $2$（$6/3$），因此 $x_2$ 最大只能为他们之间最小的那个，这样才能保证每个 $x$ 都大于零。因此使用第 $4$ 行，来对各行进行高斯行变换，使得第二列第四行中的每个 $x$ 都变成零，也包括 $c_2$。这样我们就完成了把 $x_2$ 入轴，$x_7$ 出轴的过程。变换后的单纯性表为：
 
 | $x_1$   | $x_2$   | $x_3$      | $x_4$   | $x_5$   | $x_6$   | $x_7$       | $b$      |
 | ------- | ------- | ---------- | ------- | ------- | ------- | ----------- | -------- |
@@ -454,6 +473,7 @@ $$
 $n$ 个变量，$m+n$ 个约束，构造 $m * n$ 的矩阵 $A$，$m$ 维向量 $b$，$n$ 维向量 $c$
 
 最大化 $C^Tx$ 满足如下约束条件：
+
 $$
 Ax \leq b
 $$
@@ -518,7 +538,7 @@ $$
 
 也就是说，约束条件只用 $m$ 个，尽管 $B$ 和 $N$ 不断交换，但同一时间还是只有 $m$ 个约束(基本变量)，$n$ 个非基变量，注意改写成松弛型后 $a$ 矩阵实际系数为负。（一个优化 $a[i][e]$为 $0$ 的约束没必要带入了。
 
-$simplex$ 是主过程，基本思想是找到一个 $c[e]>0$ 的，然后找对这个 $e$ 限制最紧的 $l$ ，转动这组 $l,e$，注意精度控制 $eps$，$c[e]>eps$， 还有找 $l$ 的时候 $a[i][e]>eps$ 才行。
+`simplex` 是主过程，基本思想是找到一个 $c[e]>0$ 的，然后找对这个 $e$ 限制最紧的 $l$ ，转动这组 $l,e$，注意精度控制 $eps$，$c[e]>eps$， 还有找 $l$ 的时候 $a[i][e]>eps$ 才行。
 
 ??? note " 例题 [BZOJ1061 志愿者招募](https://www.lydsy.com/JudgeOnline/problem.php?id=1061)"
     题目大意：长度为 $n$ 的序列，第 $i$ 位至少 $b_i$，$m$ 种区间使 $[l_i,r_i] + 1$ 代价为 $a_i$。
@@ -527,7 +547,7 @@ $simplex$ 是主过程，基本思想是找到一个 $c[e]>0$ 的，然后找对
 
 对偶问题 $n$ 个变量，$m$ 个约束
 $$
-Max \ \sum_{i=1}nb_iy_i
+\max \ \sum_{i=1}nb_iy_i
 $$
 
 $$
@@ -602,16 +622,17 @@ int main(){
 
 最大化与最小化互换，常数与目标函数互换，改变不等号，变量与约束对应。
 $$
-Max \ c^T: Ax \leq b, x \geq 0
+\max \ c^T: Ax \leq b, x \geq 0
 $$
 
 $$
-Min \ b^Ty: A^Ty \geq c, t \geq 0
+\min \ b^Ty: A^Ty \geq c, t \geq 0
 $$
 
 $d_{uv}$ 表示 $u,v$ 是否匹配
+
 $$
-Max \ \sum_{(u,v) \in E}c_{uv}d_{uv}
+\max \ \sum_{(u,v) \in E}c_{uv}d_{uv}
 $$
 
 $$
@@ -624,7 +645,7 @@ $$
 
 令 $p_u,p_v$ 为两类约束对偶之后的变量
 $$
-Min \ \sum_{u \in x} p_u + \sum_{v \in Y} p_v
+\min \ \sum_{u \in x} p_u + \sum_{v \in Y} p_v
 $$
 
 $$
@@ -661,4 +682,4 @@ $$
 
 - [线性规划之单纯形法【超详解+图解】](https://www.cnblogs.com/ECJTUACM-873284962/p/7097864.html)
 - [2016国家集训队论文](https://github.com/AngelKitty/review_the_national_post-graduate_entrance_examination/blob/master/books_and_notes/professional_courses/data_structures_and_algorithms/sources/%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F%E8%AE%BA%E6%96%87/%E5%9B%BD%E5%AE%B6%E9%9B%86%E8%AE%AD%E9%98%9F2016%E8%AE%BA%E6%96%87%E9%9B%86.pdf)
-- [算法导论](https://github.com/AngelKitty/review_the_national_post-graduate_entrance_examination/blob/master/books_and_notes/professional_courses/data_structures_and_algorithms/sources/extra_books/%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA(%E5%8E%9F%E4%B9%A6%E7%AC%AC3%E7%89%88).pdf)
\ No newline at end of file
+- [算法导论](https://github.com/AngelKitty/review_the_national_post-graduate_entrance_examination/blob/master/books_and_notes/professional_courses/data_structures_and_algorithms/sources/extra_books/%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA(%E5%8E%9F%E4%B9%A6%E7%AC%AC3%E7%89%88).pdf)
-- 
2.11.0