运筹学基础学习笔记 对偶问题

本节知识点

1．  对偶线性规划的概念

设线性规划问题P为

则与之互为对偶的线性规划问题D为

2．  三个定理

定理1：若规划P的第K个约束条件为等式，即

则D中对应的第K个变量Yk 是自由变量(即没有非负的限制)。

        定理2：若线性规划P的第q个变量Xq 是自由变量(即没有非负的限制)，则对偶线性规划问题D中对应的第q个约束条件为等式。

        定理3：设规划P和规划D是互为对偶的，则对于P的任意可行解X和D的任意可行解Y，均有min s ≥ max g .

        注：对偶线性规划的作用之一，是通过原始规划的最优解可以求得其对偶规划的最优解。作用之二，是在求解某个线性规划问题时，先列出其对偶规划，把原规划与对偶规划相比，哪一个规划的约束方程较少，则解该规划较为简便。

本节考核点

    定理1，达到识记层次。

    定理2，达到识记层次。

    定理3，达到识记层次。