预测与决策
线性规划
- 线性规划的可行解区是由一组线性约束条件形成的，从几何意义来说，就是由一些线性解面围割形成的区域，不一定是封闭的多边形或多面体。
- 增加一个约束区域，可行解区要么缩小要么不变。
- 若最优解存在且唯一，则可以从可行解区顶点处比较目标函数值来求解。
线性规划的标准型是线性规划模型的标准形式，其主要特征为：
- 目标函数为极大化类型。
- 所有的约束条件都是等式
- 所有约束方程右端的常数都是非负的。
- 所有决策变量都是非负的。
动态规划
暴力法
供需平衡问题
例题
设三个煤场 A、B、C 分别能供应煤 12、14、10 万吨，三个工厂 X、Y、Z 分别需要煤 11、12、13 万吨，从各煤场到各工厂运煤的单价（百元/吨）见下表。只要选择最优的运输方案，总的运输成本就能降到（）百万元。
| 工厂X | 工厂X | 工厂X | 供应商(万吨) | |
|---|---|---|---|---|
| 煤场A | 5 | 1 | 6 | 12 |
| 煤场B | 2 | 4 | 3 | 14 |
| 煤场C | 3 | 6 | 7 | 10 |
| 需求量(万吨) | 11 | 12 | 13 | 36 |
贪心策略
找当前某个条件下的最小值，动态调整。
如：标出每一列的最小值：
| A | B | C | D | |
|---|---|---|---|---|
| 甲 | 7 | 5 | 2 | 3 |
| 乙 | 9 | 4 | 3 | 7 |
| 丙 | 5 | 4 | 7 | 5 |
| 丁 | 4 | 6 | 5 | 6 |
调整：
| A | B | C | D | |
|---|---|---|---|---|
| 甲 | 7 | 5 | 2 | 3 |
| 乙 | 9 | 4 | 3 | 7 |
| 丙 | 5 | 4 | 7 | 5 |
| 丁 | 4 | 6 | 5 | 6 |
匈牙利算法
- 将关联矩阵每一行减去本行的最小值
| A | B | C | D | ||
|---|---|---|---|---|---|
| 甲 | 7 | 5 | 2 | 3 | -2 |
| 乙 | 9 | 4 | 3 | 7 | -3 |
| 丙 | 5 | 4 | 7 | 5 | -4 |
| 丁 | 4 | 6 | 5 | 6 | -4 |
→
| A | B | C | D | |
|---|---|---|---|---|
| 甲 | 5 | 3 | 0 | 1 |
| 乙 | 6 | 1 | 0 | 4 |
| 丙 | 1 | 0 | 3 | 1 |
| 丁 | 0 | 2 | 1 | 2 |
- 将新的举证非 0 列减去本列的最小值，之后每行每列取 1 个值，保证和最小
| A | B | C | D | |
|---|---|---|---|---|
| 甲 | 5 | 3 | 0 | 1 |
| 乙 | 6 | 1 | 0 | 4 |
| 丙 | 1 | 0 | 3 | 1 |
| 丁 | 0 | 2 | 1 | 2 |
| 0 | 0 | 0 | -1 |
→
| A | B | C | D | |
|---|---|---|---|---|
| 甲 | 5 | 3 | 0 | 0 |
| 乙 | 6 | 1 | 0 | 3 |
| 丙 | 1 | 0 | 3 | 0 |
| 丁 | 0 | 2 | 1 | 1 |
- 带入原参数。