线性规划
线性规划问题
求
\[\max \sum _{i=1}^nc_jx_j\\ \text{s.t. :}\\ \sum _{t=1}^n a_{it}x_t\le b_i,i\in \Z\cap [1,m_1]\\ \sum _{t=1}^n a_{it}x_t=b_i,i\in \Z\cap (m_1,m_1+m_2]\\ \sum_{t=1}^n a_{it}x_t\ge b_i,i\in (m_1+m_2,m_1+m_2+m_3]\\ x_i\ge 0,\forall i \]网络流是线性规划的特殊形式。
在 \(m=m_1+m_2+m_3\) 个的前三约束中至少有 \(n\) 个约束以等号满足的可行解称为基本可行解。
线性规划基本定理：若线性规划存在最优解，则存在基本可行最优解。
上述定理的重要意义在于，它把一个最优化问题转化为一个组合问题。
若一个线性规划只有等号约束，称其具有标准形式。如果在每个等式中，至少有一个变量的系数为正，且变量只在此出现。这样的线性规划问题叫做约束标准型线性规划问题。
每个方程中找到一个这样的变量，称为基本变量，剩下的是非基本变量。
单纯形法
这样，问题被分成了两个部分：把线性规划转为约束标准型，求解约束标准型线性规划。
先解决约束标准型线性规划。
思路：求出一组解，经过调整（转轴）得到最优解。
先置所有非基本变量为 \(0\)，求出基本变量的解。
有所谓单纯形表，自行体会，，，
第一步：选出其增加也使目标函数增加的，下标最小的非基本变量作为入基变量。找不到则目前就是最优解。此处 \(x_3\) 对应系数是正数，符合条件。\(x_3\) 是入基变量。
第二步：考察限制入基变量的变量中最要紧的限制，让其离基。
如果入基变量所在列的所有元素都是负值，则目标函数无界，已经得到了问题的无界解。
受限的增加量可以用正的入基变量所在列的元素（称为主元素）去除主元素所在行的“常数列”（最左边的列）中元素而得到。所得到数值越小说明受到限制越要紧。
例如此处 \(x_3\) 入基，即要求找到最小的常数除以正对应列值。如果此最大值是负数，即没有限制，那么解无界。比方说，这里 \(x_1\) 主元素是负值不予考虑，\(x_4\) 对应 \(12/4=3\)，\(x_6\) 对应 \(10/3\)，\(3\) 是最小的，取 \(x_4\) 离基。
第三步：转轴变换。目的是执行入基、离基过程并修正单纯形表。
这就是转轴变换后的单纯形表。
对于离基变量的那个方程表示入基变量：
\[x_3=3-\frac 12 x_2+\frac 14x_4 \]在其他行和目标函数消去 \(x_3\)，\(x_3\) 的位置变为 \(x_4\)。
第四步：返回第一步，递归知道得到无界或最优解。
转化方法
看起来，一般线性规划比约束标准型线性规划困难许多，但是我们现在声称这是等难的。
首先把不等式转为等式。每个不等式引入不影响答案的松弛变量即可：例如：
\[x_1+x_2\ge 3\rightarrow x_1+x_2-y_1=3 \]引入人工变量 \(z_i\)，把第 \(i\) 个等式约束加上 \(z_i\)。
然后分二阶段处理：先用 \(f=-\sum z_i\) 当作目标函数，得到的 \(z_i\) 应该全是 \(0\)，否则无解。然后此时 \(z_i\) 应该全是非基本变量，划去 \(z_i\) 的列即可。