线性规划对偶理论.ppt

运筹学Operations Research 王　慧 线性规划对偶理论 线性规划对偶理论概述 线性规划对偶问题提出 线性规划对偶问题规范形式 线性规划对偶问题一般形式 线性规划对偶问题基本性质 线性规划对偶问题的经济解释 线性规划对偶理论概述 线性规划对偶理论自1947年提出以来，已经有了很大发展，已成为线性规划的必不可少的重要基础理论。 对偶理论是线性规划中的一个最重要的最有趣的概念。支持对偶理论的基本思想是，每一个线性规划问题都存在一个与其对偶的问题。在求出一个问题解的时候，也同时给出了另一问题的解。 线性规划对偶问题以及对偶理论中对偶定理的运用是线性规划中主要考点。 对偶问题的提出 对偶问题的提出 对偶问题的提出 LP1与LP2 两个线性规划问题的表现形式和系数之间存在许多对应关系。 并且 我们称前者为原问题，后者是前者的对偶问题。 规范形式下对偶关系的一般形式 规范形式下对偶关系的一般形式 规范形式原问题与对偶问题变换规则 线性规划问题对偶问题举例 非规范形式的对偶关系 如何直接写出非对称形式的对偶问题 如何直接写出非对称形式的对偶问题 如何直接写出非对称形式的对偶问题 只要记住规范形式下的对偶关系以及上述规则，就可以准确无误并很快写出其对偶问题。 线性规划对偶问题的基本性质 对偶问题的基本性质应用举例 对偶问题的基本性质应用举例 对偶问题的经济解释---影子价格 对影子价格的进一步讨论 对影子价格的进一步讨论 解方程组得：x 1=－5,x 3=－1, 所以原问题的最优解为 X=（－5，0，－1），最优值Z=－12。 因为y2≠0，所以原问题第二个松弛变量 =0，由y1=0、y2=-2知，松弛变量 　　　 ，故x2=0，则原问题的约束条件为线性方程组： 【性质7】互补对偶性　　LP(max)的检验数的相反数对应于DP(min)的一组基本解. 其中第j个决策变量xj的检验数的相反数对应于（DP）中第j个松弛变量 的解，第i个松弛变量 的检验数的相反数对应于第i个对偶变量yi的解。反之，（DP）的检验数（注意：不乘负号）对应于（LP）的一组基本解。 互补的两个基解所对应的目标值相等。 证明略。 【例3.9】 线性规划 （1）用单纯形法求最优解； （2）写出每步迭代对应对偶问题的基本解； （3）从最优表中写出对偶问题的最优解； 【解】（1）加入松弛变量x4、x5后，单纯形迭代如表2-2所示。 －2 －2 －11 0 0 λj 4 6 1 2 0 －1 4 6 0 1 1 0 x1 x2 表 （3） 0 －3 －5 1↑ 0 λj 1 3→ 0 1 1/2 －1/2 1 3 －1/2 [1/2] 1 0 x1 x5 表 （2） 0 0 1 －2 6↑ λj 2→ 4 0 1 1 0 2 4 －1 0 [2] 1 x4 x5 表 （1） b x5 x4 x3 x2 x1 XB 表3-1 最优解X=（4，6，0），最优值Z=6×4－2×6=12； （2）设对偶变量为y1、y2,松弛变量为y3、y4、y5,Y=（y1、y2、 y3、y4、y5），由性质6得到对偶问题的基本解 （y1、y2、 y3、y4、y5） =（－λ4，－λ5，－λ1，－λ2，－λ3），即 表2－2（1）中λ=（6，－2，1，0，0）， 则Y（1）=（0，0，-6，2，－1） 表2－2（2）中λ=（0，1，－5，－3，0）， 则Y（2）=（3，0，0，－1，5） 表2－2（3）中λ=（0，0，－11，－2，－2）， 则Y（3）=（2，2，0，0，11） （3）因为表3－1（3）为最优解，故 Y（3）=（2，2，0，0，11）为对偶问题最优解； * * 东南大学经济管理学院 电子商务系暨管理工程研究所 wh_whq@126.com 例3.1 写出下列线性规划问题的对偶问题 m个变量 第i个变量≥0 第i个变量≤0 第i个变量无约束 变 量 m个约束 第i个约束≤ 第i个约束≥ 第i个约束为= 约 束 n个约束 第j个约束为≥ 第j个约束为≤ 第j个约束为= 约 束 n个变量 第j个变量≥0 第j 个变量≤0 第j个变量无约束 变 量 ?目标函数min 资源限量（目标函数系数） 约束条件系数矩阵AT(A) 目标函数max 目标函数系数（资源限量） 约束条件系数矩