数学建模基础知识培训 运筹学理论知识培训 第二章 共38页.pptx

### 数学建模基础知识培训——运筹学理论知识培训第二章知识点详解 #### 一、章节概述 本章主要介绍了线性规划中的一个重要概念——**对偶规划**及其相关的理论和应用，同时还涉及了**灵敏度分析**的概念。通过对本章的学习，读者将能够理解线性规划问题与其对偶问题之间的联系，掌握对偶理论的基本定理，并学会如何通过对偶单纯形法求解线性规划问题。此外，还将学习如何进行灵敏度分析，从而更好地理解和应对实际问题中的不确定性。 #### 二、线性规划的对偶问题 ##### 2.1 线性规划的对偶问题与对偶理论 **1. 对偶问题的提出** - **定义**：对于一个线性规划问题（称为原问题），总可以构造出另一个线性规划问题（称为对偶问题），这两个问题之间存在着密切的联系。 - **例子**：以家具公司生产问题为例，原问题是关于如何安排生产以最大化收益，而对偶问题则是关于如何合理分配资源（如木工和油漆工的劳务）以确保成本最低。 **2. 原问题与对偶问题的对应关系** | 原问题（或对偶问题） | 目标函数 | 变量数量 | 约束数量 | 约束条件 | 目标函数系数 | |------------------------|----------|----------|----------|----------|---------------| | 原问题 | 最大化 | n | m | 不等式 | b | | 对偶问题 | 最小化 | m | n | 不等式 | c | **3. 线性规划对偶理论的主要基本定理** - **定理1**：对称性定理，对偶问题的对偶是原问题。 - **定理2**：若X和Y分别是原问题P和对偶问题D的可行解，则CX≤bTY。 - **定理3**：对偶原理，包括： - P有最优解的充要条件是D有最优解； - 若P无界则D无可行解，反之亦然； - 若X*和Y*分别是P和D的可行解，则它们分别为P和D的最优解的充要条件是CX*=Y*b。 - **定理4**：互补松弛性定理，如果X和Y分别为P和D的可行解，那么它们分别为P和D的最优解的充要条件是(C-YTA)X=0和YT(b-AX)=0。 #### 三、对偶单纯形法 **1. 对偶单纯法的基本思想** - **目的**：求解线性规划问题。 - **特点**：首先找到对偶问题的基本可行解，然后在保持对偶问题可行性的基础上，逐步调整使原问题也变为可行解，最终达到同时解决原问题和对偶问题的目的。 **2. 对偶单纯法计算步骤** 1. **构建初始单纯形表**：使得判别行的所有检验数σj≤0。 2. **确定退出基变量**：选择b列中最小的负值对应的变量作为退出基变量。 3. **确定进入基变量**：基于最小比值原则确定进入基变量。 4. **迭代求解**：重复上述步骤直到原问题也为可行解。 #### 四、灵敏度分析 灵敏度分析是研究当线性规划问题中的参数发生变化时，最优解的变化情况。通过对灵敏度分析的学习，我们可以了解： - **成本系数变化的影响**：当目标函数的成本系数发生变化时，最优解如何变化。 - **资源限制变化的影响**：当约束条件中的右侧常数发生变化时，最优解如何变化。 通过对第二章的学习，不仅可以深入了解线性规划的对偶理论，还能掌握对偶单纯形法的具体计算步骤，并且能够运用灵敏度分析来处理实际问题中的参数变化情况，这对于解决复杂的决策问题具有重要意义。