第三章 对偶单纯形法

运筹帷幄之中决胜千里之外对偶理论与灵敏度分析第二章 对偶理论与灵敏度分析第一节 对偶问题的提出第二节 线性规划的对偶理论第三节 对偶问题的经济解释第四节 对偶单纯形法【 例 2-1】 某家电厂利用现有资源生产两种产品，有关数据如下表：设备 A设备 B调试工序利润（元）0612521115时24时 5 时产品 产品 D第一节 对偶问题的提出如何安排生产，使获利最多 ？厂家设 产量 产量 设：设备 A 元时设备 B 元时调试工序 元时承租付出的代价最小，且对方能接受。出让代价应不低于用同等数量的资源自己生产的利润。设备 A设备 B调试工序利润（元）0612521115时24时 5 时 D厂家能接受的条件：出让代价应不低于用同等数量的资源自己生产的利润。收购方的意愿：厂家对偶问题原问题承租厂家一对对偶问题第二节 线性规划的对偶理论一 原问题与对偶问题的关系二 对偶问题的基本性质一 原问题与对偶问题的关系1 对称式的对偶“”不等式约束条件的原问题与 “”不等式约束条件的对偶问题，称为 对称式 的一对对偶问题。原问题：max z=c1x1+c2x2+ cnxna11 a12 a1nam1 am2 amn x1xn b1bmx1， x2， ， xn0对偶问题： min =b1y1+b2y2+ bmyma11 a12 a1nam1 am2 amn y1， y2， ， ym0(y1,y2, ym) (c1,c2, cn)max z=CXAXbX0min =YbYA CY0n个变量， m个约束条件m个变量， n个约束条件2 约束条件全部为 “=”的对偶max z=CXAX bX0原问题： max z=CXAXbX0AXb等价max z=CXAXbX0 AX bmax z=CXX0A A Xb bmin =(Y1,Y2)Y1,Y20A A Cb b(Y1,Y2)其中 Y1=(y1, y2, ym)， Y2=(ym+1, ym+2, y2m)等价等价min =YbY为无约束YA Cmin =(Y1 Y2)bY1,Y20(Y1 Y2)A C 令 Y=(Y1 Y2)对偶问题对偶问题3 约束条件为 “”的对偶max z=CXAXbX0原问题：max z=CX AX bX0min =Y1 ( b)Y1( A) CY10min =YbYA CY0等价对偶问题令 Y= Y1对偶问题4 变量 0的对偶max z=CXAXbX0原问题：令 X= X1max z=C ( X1)A ( X1) bX10max z=( C) X1( A )X1 bX10等价min =Y bY ( A) CY0min =Y bY A CY0 对偶问题对偶问题等价5 变量无约束的对偶max z=CXAXbX无约束原问题：令 X=X1 X2 X1， X20max z=CX1 CX2X1,X20AX1 AX2 bmax z=(C, C)X1,X20bX1X2(A, A) X1X2等价min =YbY0Y(A , A) (C, C)对偶min =YbYACY0 YA Cmin =YbYA CY0min =YbYACY0YA C等价等价等价对偶问题6 原问题与对偶问题的关系表原 问题 （或 对 偶 问题 ） 对 偶 问题 （或原 问题 ）目 标 函数 max zn个 变 量变 量 0变 量 0变 量无 约 束目 标 函数 min n个 约 束条件约 束 约 束 约 束 =m个 约 束条件约 束 约 束 约 束 =约 束条件右端 项目 标 函数 变 量系数m个 变 量变 量 0变 量 0变 量无 约 束 目 标 函数 变 量系数约 束条件右端 项【 例 2-2】 试求下述线性规划问题的对偶问题（ P）与 (D)的关系对应表：原 (对 偶 )问题对 偶 (原 )问题目标函数 max 目标函数 min目标函数系数 约束方程常数列约束方程常数列 目标函数系数变量个数 n 约束方程个数 n约束方程个数 m 变量个数 m约束方程 变量 0 0= 无符号约束变量 0 约束方程 0 无符号约束 =系数矩阵 A解 ： （ P）与 (D)的关系对应表：原 (对 偶 )问题对 偶 (原 )问题目标函数 max 目标函数 min目标函数系数 约束方程常数列约束方程常数列 目标函数系数变量个数 n 约束方程个数 n约束方程个数 m 变量个数 m约束方程 变量 0 0= 无符号约束变量 0 约束方程 0 无符号约束 =系数矩阵 A【 例 2-3】 试求下述线性规划原问题的对偶问题解：原问题的对偶问题【 课堂练习 】 （ P）与 (D)的关系对应表：原 问题 对 偶 问题目标函数 max 目标函数 min目标函数系数 约束方程常数列约束方程常数列 目标函数系数变量个数 n 约束方程个数 n约束方程个数 m 变量个数 m约束方程 变量 0 0= 无符号约束变量 0 约束方程 0 无符号约束 =系数矩阵 A构建对偶问题的规则原始 问题 的 目 标 对 偶 问题目 标 约 束 类 型 变 量符号最大化 极小化 = 无限制最小化 极大化 = 无限制要求： 1、将所有约束转换成等式；2、将所有决策变量转换成大于等于。回顾：原问题与对偶问题的关系表原 问题 （或 对 偶 问题 ） 对 偶 问题 （或原 问题 ）目 标 函数 max zn个 变 量变 量 0变 量 0变 量无 约 束目 标 函数 min n个 约 束条件约 束 约 束 约 束 =m个 约 束条件约 束 约 束 约 束 =约 束条件右端 项目 标 函数 变 量系数m个 变 量变 量 0变 量 0变 量无 约 束 目 标 函数 变 量系数约 束条件右端 项二 对偶问题的基本性质1 对称性： 对偶问题的对偶问题是原问题。2 弱对偶性： 若 X(0)是原问题的可行解， Y(0)是对偶问题的可行解，则存在 CX(0) Y(0) b。3 无界性： 若原问题无界解， 则其对偶问题无可行解 。4 最优性： 若 X(0)是原问题的可行解， Y(0)是对偶问题的可行解，且 C X(0) = Y(0) b ，则 X(0)， Y(0)是最优解。5 对偶定理： 若原问题有最优解， 那么对偶问题也有最优解；且目标函数值相等。6 互补松弛性： 若 X(0)是原问题的可行解， Y(0)是对偶问题的可行解，则 YsX(0)=0和 Y(0)Xs=0 当且仅当 X(0)， Y(0)是最优解。其中 Xs和 Ys分别为原问题和对偶问题的松弛变量的可行解 .【 例 2-4】 已知线性规划问题min w=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53xj0， j=1， 2， ， 5已知其对偶问题的最优解为 y1*=4/5， y2*=3/5； z=5。试用对偶理论找出原问题的最优解 。【 例 2-4】 已知线性规划问题解：先写出它的对偶问题max z=4y1+3y2y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1， y20【 例 2-4】 已知线性规划问题将 y1* =4/5,y2* =3/5的值代入约束条件，得 =1/53， =17/55， =7/52它们为严格不等式；由互补松弛性得x2*=x3*=x4*=0。因 y1， y20； 原问题的两个约束条件应取等式，故有x1*+3x5*=4， 2x1*+x5*=3求解后得到 x1*=1,x5*=1； 故原问题的最优解为X*=(1， 0， 0， 0， 1)T； w*=51、 原始问题是利润最大化的生产计划问题单位产品的利润（元 /件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨 /件）剩余的资源（吨）消耗的资源（吨）第三节 对偶问题的经济解释2、 对偶问题资源限量（吨）资源价格（元 /吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解 y1、 y2、 .、ym称为 m种资源的 影子价格 （ Shadow Price）原始和对偶问题都取得最优解时，最大利润 max z=min w3、 资源影子价格的性质从对偶定理可知 ，当达到最优解时，原问题和对偶问题的目标函数值相等，即 z=CX(0)=Y(0)b=CBB-1b .也即 z=CX(0)=Y(0)b=CBB-1b =y1(0)b1+ y2(0) b2 + +y m(0) bm 其中 X(0),Y(0)分别是原问题和对偶问题的最优解。现在考虑在最优解处 ，常数项 bi的微小变动对目标函数值的影响 (不改变原来的最优基 ).求 z对 bi的偏导数，可得：y1(0) zb1, y2(0