### 运筹学复习提纲
#### 一、线性规划与目标规划
**线性规划**是运筹学中最基本也是最重要的一个分支，它主要研究如何从一系列满足线性等式或不等式的解中寻找使某一目标函数达到最大值或最小值的最优解。
1. **线性规划的基本概念**
- **决策变量**：模型中的未知数。
- **目标函数**：待优化的目标表达式。
- **约束条件**：限制决策变量取值的条件。
- **可行域**：所有满足约束条件的解构成的集合。
- **最优解**：使得目标函数取得最优值的解。
2. **线性规划的几何意义**
- 在二维空间中，线性规划的可行域通常是一个多边形区域。
- 最优解往往出现在可行域的顶点处。
3. **线性规划的标准形式**
- 所有决策变量非负。
- 目标函数为最大化或最小化线性表达式。
- 约束条件为等式或小于等于的不等式。
4. **线性规划的求解方法**
- **直接观察法**：适用于简单的情况，可以通过图形直观看出最优解的位置。
- **加入松弛变量法**：将不等式约束转化为等式约束，引入松弛变量来表示不等式右侧与左侧的差值。
- **人工变量法**（大M法、两阶段法）
- **大M法**：通过引入足够大的常数M来处理人工变量，使其在最终解中消失。
- **两阶段法**：首先确定可行解是否存在，然后求解原问题。
#### 二、单纯形法
**单纯形法**是一种求解线性规划问题的有效算法，由George Dantzig于1947年提出。
1. **单纯形法的基本步骤**
- 初始化：找到一个初始基可行解。
- 检验：检查当前解是否是最优解。
- 循环：如果当前解不是最优解，则通过迭代改进解。
- 终止：当得到最优解时停止迭代。
2. **单纯形法的矩阵描述**
- 将线性规划问题转换成矩阵形式。
- 通过高斯消元等操作更新系数矩阵。
3. **对偶理论**
- **对偶问题**：对于每一个线性规划问题，都存在一个对应的对偶问题。
- **弱对偶性原理**：任何原问题的一个可行解对应的目标函数值总是不大于其对偶问题的一个可行解对应的目标函数值。
- **强对偶性原理**：若原问题和对偶问题都有可行解，则它们都有最优解，并且这两个最优解的目标函数值相等。
4. **对偶单纯形法**
- 当原问题的单纯形表中存在非基变量的检验数小于零，而基变量的值又全部非正时，可以采用对偶单纯形法。
5. **灵敏度分析**
- **参数变化**：研究当线性规划的问题数据发生微小变化时，最优解的变化情况。
- **范围分析**：确定决策变量的取值范围，在这个范围内，当前的最优基不变。
#### 三、运输问题
**运输问题**是一类特殊的线性规划问题，用于解决物品从多个产地到多个销地的最优运输方案。
1. **运输问题的数学模型**
- 决策变量表示从某产地到某销地的运输量。
- 目标函数为总运输成本最小化。
2. **求解方法**
- **最小元素法**：按照单位运输成本从低到高选择产地和销地，尽可能多地分配运输量。
- **伏格尔法**：先计算每个产地和销地的差额成本，优先选择差额成本最大的产地或销地。
- **表上作业法**：在运输表上通过闭回路调整法不断优化解。
- **特殊情况处理**：
- **无穷多最优解**：当存在多个最优解时，可以通过调整决策变量来获得其他最优解。
- **退化解**：当存在非基变量的检验数为零时，出现退化解。
3. **产销不平衡问题**
- **产大于销**：可以通过设置虚拟销地或就地储存来平衡。
- **销大于产**：可以通过添加虚拟产地来解决。
通过对这些知识点的深入理解和掌握，可以帮助学生更好地准备运筹学的期中考试，并在未来的学习和工作中灵活运用这些理论和方法。
