Page 126 - 数学建模算法与应用

Mathematical Modeling Algorithms and Applications
数学建模算法与应用

可以证明，如果在没有∨的行和有∨的列之间画一条直线，它可以覆盖矩阵
中的所有元素具有最小数量的零元素的线集，找到最小的未覆盖元素，并将其从
∨线元素中减去。如果将数字添加到∨列中的元素中，则最初选择的 0 元素保持

不变，并且至少有一个未覆盖的元素已被转换变为 0，新矩阵的赋值问题也等价
于原始问题。可以重复上述过程，直到可以做出足够的选择，直到有足够的 0 个
元素。
例如，对例 5 变换后的矩阵再变换，第三行、第五行元素减去 2，第一列元

素加上 2，得

现在已可看出，最优指派为

第五节 对偶理论与灵敏度分析

对偶理论和灵敏度分析构成了线性规划领域的两个核心概念。这些工具不仅
加深了对初始问题架构的理解，而且揭示了模型参数变化时影响最优解的关键数

据。在本章中，我们将深入探讨对偶理论的基本原理、构造对偶问题的技术手段
以及灵敏度分析的实际应用。

一、对偶理论的基本概念

作为线性规划的一个基本组成部分，对偶理论阐明了线性规划的每个实例都
与所谓的“对偶”问题有关。原始问题和对偶问题之间的关系非常密切，这意味
着解决其中一个问题可以间接获得另一个问题的答案，反之亦然。原问题（Primal
Problem）的形式如下：

116