运筹与优化-线性规划部分

# 单纯形法

# 化为标准型

1. 先根据题目要求列出$s.t.$
2. 将$s.t.$ 内不等式全部化为等式：给不等式加上或减去某个 $x_{n}$ : $x_{n} \ge 0$
3. 使等式右边常数 $b \ge 0$
4. 将单变量换成 $\ge 0$ 的形式，如果某变量 $x_{m}$ $\le 0$，则设一个新变量 $x_{m}^{'}$ $\ge 0$ 且 $x_{m}^{'}$ $=$ $-$ $x_{m}$
5. 把自由变量 (无约束变量) $x_{p}$ 改写成 $x_{m}^{'}$ $-$ $x_{m}^{''}$ $=$ $x_{p}$ ，其中 $x_{m}^{'}$ $\ge 0$ , $x_{m}^{''}$ $\ge 0$
6. 将所有单变量写到最后一行

# 填单纯形表

单纯形表如下图所示：

1. 将上一步写出的标准型填入单纯形表
2. 找出单纯形表里的单位矩阵 (一般是自己设的新变量)，依次填入$X_{B}$ 的下面；并将变量对应的$c_{j}$ 依次填入$c_{b}$
3. 将$s.t.$ 中等式右边数字依次填入$b$ 这列

# 检验数计算

计算出 $\sigma _{j}$ $=$ $c_{j}$ $-$ $c_{B1} \cdot X_{j1}$ $-$ $c_{B2} \cdot X_{j2}$ $...$ ，若 $\sigma _{j}$ 均小于 0，则该解为最优解；若$X_{B}$ 列以外的变量对应的$\sigma _{j}$ 有$=0$ 的，则有无穷多组最优解；若存在 $\sigma _{i}$ 大于 0，则该解不为最优解，继续进行下一步换解计算

# 换解计算

1. 找到 $\sigma _{j}$ 行最大的检验数对应的变量 $x_{a}$ (进基变量)，求出 $\theta _{i}$ = $\frac{b_{i}}{x_{a_{i}}}$(不用管$\theta _{i} \le 0$ 的情况，若所有$\theta$ 都 $\le 0$, 则该题为无界解)
2. 寻找 $\theta _{i}$ 最小值对应 $X_{b}$ 列的变量 $x_{b}$ (出基变量)，找到 $x_{a}$ 的列和 $x_{b}$ 的行交叉的数字 m
3. 用 $x_{a}$ 上面的数字替换 $x_{b}$ 前面的数字，同时用 $x_{a}$ 替代 $x_{b}$ ，清空 $\sigma _{j}$ 行与 $\theta _{i}$ 列
4. 将单纯形表内 m 通过初等变换为 1，同列其它元素变换为 0
5. 返回检验数计算

# 对偶问题

# 对偶问题的标准型转换

1. 确定对偶问题中的变量个数$m$，原问题$s.t.$ 中约束条件的个数$m$ 等于对偶问题的变量个数
2. 确定目标函数，$min | max$ $=$ $b_{1} \cdot y_{1}$ $+$ $b_{2} \cdot y_{2}$ $+$ $...$, 其中$min | max$ 由与原问题相反，$b_{1}、b_{2}...b_{m}$ 为约束条件右端常数
3. 确定约束条件个数$n$:$n=$ 原问题中变量个数，从上到下 (设为第$j$ 行) 各约束条件$y_{i}$ 对应为原问题约束条件中从上到下对应的$x_{j}$ 的系数
4. 确定对偶问题约束条件右边常数与符号，$j$ 行约束条件常数对应原问题目标函数$x_{j}$ 的系数，符号可参考下表：

5. 确定对偶问题变量范围：

# 对偶问题的性质

1.A 有最优解，则 A 的对偶问题 B 一定有最优解，且两者取最优解时的目标函数值相同
2.A 的解为无界解，则 A 的对偶问题 B 无可行解
3.A 无可行解，则 A 的对偶问题 B 是无界解或无可行解

# 已知对偶问题最优解求原问题最优解

1. 根据对偶问题写出原问题
2. 改变原问题约束条件，$\ge$ 变为$>$，$\le$ 变为$<$
3. 将对偶问题最优解代入改写后的不等式，若成立则该行变量对应$x_{j}$ $=$ $0$
4. 对偶问题中若最优解$y_{i}^{*} \ne 0$，则将其代入原问题第$i$ 行，同时将约束条件变为等号
5. 联立 3，4 求解即可

# 影子价格

影子价格在理解含义后比较简单，我们只要求出对偶问题的最优解，其对应的便是原问题中各资源的影子价格。
经济意义：
1 单位的某种资源可变为多少单位的收益，
影子价格＞0，对应资源无剩余；
影子价格 = 0，对应资源有剩余

# 灵敏度分析