问题的提出

线性规划问题的一般形式为 最大化 (最小化) `z = sum_(j=1)^n c_j x_j`, 满足
`sum_(j=1)^n a_(i j) x_j le (=,ge) b_i`, `quad i = 1, cdots, m`,
`x_j ge 0`, `quad j in S sube {1, 2, cdots, n}`. 标准形式为 最大化 `z = sum_(j=1)^n c_j x_j`, 满足
`sum_(j=1)^n a_(i j) x_j le b_i`, `quad i = 1, cdots, m`,
`x_j ge 0`, `quad j = 1, cdots, n`. 引入记号 `bm A = [a_11, a_12, cdots, a_(1n); a_21, a_22, cdots, a_(2n); vdots, vdots, , vdots; a_(m1), a_(m2), cdots, a_(m n)]`, `bm b = [b_1;b_2;vdots;b_m]`, `bm c = [c_1;c_2;vdots;c_n]`, `bm x = [x_1;x_2;vdots;x_n]`, `bb 0 = [0; 0; vdots; 0]`, 线性规划的标准形式可以写成更加紧凑的形式: `max z = {:bm c:}^T bm x`,
`bm (A x) le bm b`,
`bm x ge bb 0`. 其中不等号表示向量的每一分量均满足该不等式. 为了便于使用下文提到的单纯形法求解线性规划, 再引入松弛形式, 它与标准形式的区别在于将 "`le`" 换成了 "`=`": `max z = {:bm c:}^T bm x`,
`bm (A x) = bm b`,
`bm x ge bb 0`. 因此, 三元组 `(bm A, bm b, bm c)` 就完全决定了一个线性规则的标准形式 (或松弛形式).

我们介绍 (标准形式) 线性规划的相关术语.
• 目标函数 `z={:bm c:}^T bm x`, 它是 `bm x` 的线性函数;
• 约束条件 包括线性约束 `bm(A x) le bm b` 和非负约束 `bm x ge bb 0`;
• 可行解 是指满足约束条件的某个 `bm x`, 全体可行解的集合称为可行域;
• 最优解 使目标函数取得最大值的可行解;

线性规划的标准化 依次进行以下步骤来将线性规划问题化为与原问题等价的标准形式:
1. 若要求 `z` 最小化, 可令 `z' = -z = -{:bm c:}^T bm x`, 从而转化为将 `z'` 最大化;
2. 若存在无约束变量 `x_i`, 可引入新变量 `x_j, x_k ge 0`, 再令 `x_i = x_j - x_k`,
3. 将线性约束化为 "`le`" 的形式. 具体做法是将所有线性等式 `sum_(j=1)^n a_(i j) x_j = b_i` 用等价的两个不等式 `sum_(j=1)^n a_(i j) x_j le b_i` 和 `sum_(j=1)^n a_(i j) ge b_i` 代替, 然后在所有线性不等式 `sum_(j=1)^n a_(i j) x_j ge b_i` 两边同乘以 `-1`.
将线性规划标准形化为松弛形 为每个线性约束引入一个变量 `x_(n+i) = b_i - sum_(j=1)^n a_(i j) x_j`, `quad x_(n+i) ge 0`, `quad i = 1, cdots, m`, 称为松弛变量. 这个变量反映了不等式两边的差, 亦即约束条件的 "松紧" 程度. 用上面的 `m` 个等式代替原线性约束, 就得到等价的松弛形式.

单纯形法

单纯形法 (simplex method) 是 G. Dantzig 于 1947 年提出的经典算法, 它是一种有效求解线性规划的代数算法. 算法在每一步中从单纯形的一个顶点移动到目标值不小于当前值的相邻顶点. 如果当前值达到局部最优, 即所有相邻顶点的目标值不大于当前值时, 算法终止. 可以证明, 此时目标值实际已达到全局最优. 下面通过具体实例来介绍单纯形法.

求解线性规划 `max z = 3 x_1 + x_2 + 2 x_3`,
`x_1 + x_2 + 3 x_3 le 30`,
`2 x_1 + 2 x_2 + 5 x_3 le 24`,
`4 x_1 + x_2 + 2 x_3 le 36`,
`x_1, x_2, x_3 ge 0`.

由于我们对线性规划标准形的约定, 原问题可简记为 `z = 3 x_1 + x_2 + 2 x_3`,
`x_1 + x_2 + 3 x_3 le 30`,
`2 x_1 + 2 x_2 + 5 x_3 le 24`,
`4 x_1 + x_2 + 2 x_3 le 36`. 现在引入松弛变量, 问题化为 `z = 3 x_1 + x_2 + 2 x_3`,
`x_4 = 30 - x_1 - x_2 - 3 x_3`,
`x_5 = 24 - 2 x_1 - 2 x_2 - 5 x_3`,
`x_6 = 36 - 4 x_1 - x_2 - 2 x_3`. 如果令等号右边的所有变量等于零, 就得到一个解 `(0, 0, 0, 30, 24, 36)`, 对应的 `z = 0`. 我们把等号左边的变量称为基变量, 右边的称为非基变量. 观察 `z` 的表达式, 因为 `x_1, x_2, x_3` 前的系数为正, 所以只要增大其中任一变量 (比如 `x_1`), `z` 的值就能增大. 但 `x_1` 的增大受到非负约束的限制, 我们必须保证 `x_4, x_5, x_6` 非负, 即 `x_1 le 30`, `quad 2 x_1 le 24`, `quad 4 x_1 le 36`. 其中最紧的约束是 `x_1 le 9`. 因此最多将 `x_1` 增大到 `9`, 而这时 `x_6 = 0`. 我们把增大一个变量, 而另一变量减小到零的这种操作称作一次旋转, 增大的变量 `x_1` 称为换入变量, 减小到零的变量 `x_6` 称为换出变量. 现在将 `x_1 = 9 - x_2/4 - x_3/2 - x_6/4` 代入各式, 问题化为 `z = 27 + x_2/4 + x_3/2 - (3 x_6)/4`,
`x_1 = 9 - x_2/4 - x_3/2 - x_6/4`,
`x_4 = 21 - (3 x_2)/4 - (5 x_3)/2 + x_6/4`,
`x_5 = 6 - (3 x_2)/2 - 4 x_3 + x_6/2`. 依照前面的做法, 令非基变量等于零, 得到解 `(9, 0, 0, 21, 6, 0)` 和 `z = 27`. 旋转操作确实让 `z` 的值增加了!
继续观察 `z` 的表达式, `x_2, x_3` 的系数仍为正, 我们选择 `x_2` 为换入变量, 通过 `x_2/4 le 9`, `quad (3 x_2)/4 le 21`, `quad (3 x_2)/2 le 6` 确定第三个约束为最紧, 因此换出 `x_5`: `z = 28 - x_3/6 - x_5/6 - (2 x_6)/3`,
`x_1 = 8 + x_3/6 + x_5/6 - x_6/3`,
`x_2 = 4 - (8 x_3)/3 - (2 x_5)/3 + x_6/3`,
`x_4 = 18 - x_3/2 + x_5/2`. 令非基变量等于零, 得到解 `(8, 4, 0, 18, 0, 0)` 和 `z = 28`. 由于 `z` 的表达式中所有系数都为负, 此时不论换入哪个变量都不可能增加 `z` 的值, 因此我们断定最优解已经得到.

解线性规划 `max z = 2 x_1 + 3 x_2`,
`x_1 + 2 x_2 le 8`,
`4 x_1 le 16`,
`4 x_2 le 12`,
`x_1, x_2 ge 0`.

矩阵计算过程如下: `{: z; x_3; x_4; x_5 :}` `[-2, -3, 0, 0, 0; 1, 2, 1, 0, 0; (4), 0, 0, 1, 0; 0, 4, 0, 0, 1]` `{: 0; 8; 16; 12 :}`
`8/1 = 8`, `quad 16/4 = 4`, `quad 12/0 = oo`. `{: z; x_3; x_1; x_5 :}` `[0, -3, 0, 1//2, 0; 0, (2), 1, -1//4, 0; 1, 0, 0, 1//4, 0; 0, 4, 0, 0, 1]` `{: 8; 4; 4; 12 :}`
`4/2 = 2`, `quad 4/0 = oo`, `quad 12/4 = 3`. `{: z; x_2; x_1; x_5 :}` `[0, 0, 3//2, 1//8, 0; 0, 1, 1//2, -1//8, 0; 1, 0, 0, 1//4, 0; 0, 0, -2, -1//2, 1]` `{: 14; 2; 4; 4 :}`
`z` 行系数非负, 算法终止. 最优解为 `(4, 2, 0, 0, 4)`, `z = 14`.

[来自 无懈可击99] 求 `|x-3y+2|+|x+y|+|x|` 的最小值.

因为绝对值函数 `|x| = max(x, -x)`, 问题化为线性规划 `min x3+x4+x5`,
`x-3y+2 le x_3`,
`-x+3y-2 le x_3`,
`x+y le x_4`,
`-x-y le x_4`,
`x le x_5`,
`-x le x_5`,
其中各变量取无约束的实值.

记 `f = |x-3y+2|+|x+y|+|x|`, 熟知最值必在边界上取得: `x = 0 or x = -y or 3y - x = 2` 由后两个等式得到: `y = 0.5`, `x = -0.5`, `f = 0.5`. 和 `x = 0, y = 0 rArr f = 2`,
`x = 0, 3y - x = 2 rArr f = 2//3`. 比较知, `f` 的最小值是 `1//2`.

线性规划求解器（单纯形法）

单纯形法的正确性

• 基 是指 `bm A` 中线性无关的 `m` 个列向量组成的向量组, 其中每个向量 `bm A_i` 称为一个基向量, 相应的 `x_i` 称为一个基变量, 而其余的 `x_j` 称为非基变量.
• 基解 注意松弛形中的约束等式 `bm (A x) = bm b`. 若 `bm A` 的秩为 `m`, 因 `m lt n`, 方程组 `bm (A x) = bm b` 有无穷多解. 不妨设 `bm A` 的前 `m` 列组成一个基, 则方程组化为 `sum_(j=1)^m {:bm A:}_j^T x_j = bm b - sum_(j=m+1)^n {:bm A:}_j^T x_j`. 每取定一组 `(x_(m+1), cdots, x_n)` 的值, 相应地就能得到方程组的一个解. 特别令非基变量 `x_(m+1) = x_(m+2) = cdots = x_n = 0`, 就得到方程组的特解: `bm x = (x_1, x_2, cdots, x_m, 0, cdots, 0)^T`, 称为一个基解. 由以上讨论知方程组的基解与基一一对应. 通常情形, 基解中的非零分量数等于 `m`; 当它小于 `m` 时, 线性规划问题出现退化.
• 基可行解 是指满足非负约束 `bm x ge bb 0` 的基解, 由于基解必然满足等式约束, 基可行解必为可行解. 对应于基可行解的基称为可行基.

设 `D` 是 `n` 维 Euclid 空间的子集, 若对任意 `bm x, bm y in D`, `D` 包含了它们连线上的任一点: `t bm x + (1-t) bm y in D`, `quad t in (0,1)`, 则称 `D` 是凸集. 若 `bm x in D`, 且不存在 `bm y, bm z in D` 使得 `bm x = t bm y + (1-t) bm z`, `quad t in (0, 1)`, 则称 `bm x` 是凸集 `D` 的顶点.

线性规划的可行解 `bm x` 为基可行解当且仅当 `bm x` 的非零分量对应的列向量组线性无关.

`n` 维 Euclid 空间中的有界凸集 `D` 中任意一点 `bm x` 可表示为 `D` 的顶点 `bm x_1, bm x_2, cdots, bm x_k` 的凸组合, 即存在实数 `t_1, t_2, cdots, t_k in [0, 1]` 满足 `sum_(i=1)^k t_i = 1`, 使得 `bm x = sum_(i=1)^k t_i bm x_i`. 特别当 `0 lt t_i lt 1` 时, 称为严格凸组合.

线性规划问题的可行域 `D = {bm x: sum_(i=1)^n bm A_i x_i = bm b, bm x ge 0}` 是凸集.

线性规划的基可行解 `bm x` 与可行域的顶点一一对应.

若可行域有界, 线性规划的目标函数一定能在基可行域的某个顶点上达到最大.

若目标函数在多个顶点处达到最大值, 则它在这些顶点的凸组合上也达到最大值.