对偶问题的分析PPT讲稿.ppt

《对偶问题的分析PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《对偶问题的分析PPT讲稿.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、对偶问题的分析1第1页，共53页，编辑于2022年，星期六线性规划原问题线性规划原问题 例例2.1:2.1:某某工工厂厂拥拥有有A A、B B、C C三三种种类类型型的的设设备备，生生产产甲甲、乙乙两两种种产产品品。每每件件产产品品在在生生产产中中需需要要占占用用的的设设备备机机时时数数，每每件件产产品品可可以以获获得得的的利利润润以以及及三三种种设设备可利用的时数如下表所示。求获最大利润的方案。备可利用的时数如下表所示。求获最大利润的方案。产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润（元/件）15001500250025002第

2、2页，共53页，编辑于2022年，星期六一、对偶问题：一、对偶问题：它的对偶问题就是一个价格系统，使在平衡了劳动力它的对偶问题就是一个价格系统，使在平衡了劳动力和原材料的直接成本后，所确定的价格系统最具有竞争力和原材料的直接成本后，所确定的价格系统最具有竞争力 若另外一个工厂要求租用该厂的设备若另外一个工厂要求租用该厂的设备A A、B B、C C，那么，那么该厂应如何确定合理的租金。该厂应如何确定合理的租金。设设 y y1 1，y y2 2，y y3 3 分别为每工时设备分别为每工时设备 A A、B B、C C 的租的租金。金。3.13.1线性规划对偶问题线性规划对偶问题3第3页，共53页，编

3、辑于2022年，星期六设备的租金收入不能低于自己组织生产设备的租金收入不能低于自己组织生产时的获利收入：时的获利收入：3 3y y1 1+2+2y y2 2 15001500（不少于甲产品的利润）（不少于甲产品的利润）2 2y y1 1+y y2 2+3+3y y3 3 25002500（不少于乙产品的利润）（不少于乙产品的利润）用于生产第用于生产第i种产品的资源转让收益不小种产品的资源转让收益不小于生产该种产品时获得的利润于生产该种产品时获得的利润 租方希望在满足上述条件下尽量要求全租方希望在满足上述条件下尽量要求全部设备的总租金越少越好，即部设备的总租金越少越好，即Min W=65yMin

4、 W=65y1 1+40y+40y2 2+75y+75y3 34第4页，共53页，编辑于2022年，星期六 对偶变量的经济意义可以解释为对工时及原材料的单位对偶变量的经济意义可以解释为对工时及原材料的单位对偶变量的经济意义可以解释为对工时及原材料的单位对偶变量的经济意义可以解释为对工时及原材料的单位定价定价定价定价 若工厂自己不生产产品若工厂自己不生产产品A、B和和C，将现有的工时及原，将现有的工时及原材料转而接受外来加工时，那么材料转而接受外来加工时，那么上述的价格系统能保证上述的价格系统能保证上述的价格系统能保证上述的价格系统能保证不亏本又最富有竞争力不亏本又最富有竞争力不亏本又最富有竞争

5、力不亏本又最富有竞争力（包工及原材料的总价格最低）（包工及原材料的总价格最低）当原问题和对偶问题都取得最优解时，这一对线性规划当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的：对应的目标函数值是相等的：Zmax=Wmin=8 5第5页，共53页，编辑于2022年，星期六原问题的对偶问题原问题的对偶问题DPDP：Min Min W W=65=65y y1 1+40+40y y2 2+75+75y y3 3 s.t.3 s.t.3y y1 1+2+2y y2 2 15001500 2 2y y1 1+y y2 2+3+3y y3 3 25002500 y y1 1,y y2

6、 2,y y3 3 0 06第6页，共53页，编辑于2022年，星期六 Max Max z z=1500=1500 x x1 1+2500+2500 x x2 2 s.t.3 s.t.3x x1 1+2+2x x2 2 65 65 2 2x x1 1+x x2 2 40 40 原问题原问题 3 3x x2 2 75 75 x x1 1,x x2 2 0 0 Min Min W W=65=65y y1 1+40+40y y2 2+75+75y y3 3 s.t.3 s.t.3y y1 1+2+2y y2 2 15001500 2 2y y1 1+y y2 2+3+3y y3 3 2500 250

7、0 对偶问题对偶问题 y y1 1,y y2 2,y y3 3 0 0 7第7页，共53页，编辑于2022年，星期六原问题求极大化，对偶问题求极小化原问题求极大化，对偶问题求极小化从约束系数矩阵看：一个模型中为，从约束系数矩阵看：一个模型中为，则另一个模型中为则另一个模型中为AT。一个模型是。一个模型是m个个约束，约束，n个变量，则它的对偶模型为个变量，则它的对偶模型为n个个约束，约束，m个变量。个变量。从数据从数据b、C的位置看：在两个规划模型的位置看：在两个规划模型中，中，b和和C的位置对换。的位置对换。8第8页，共53页，编辑于2022年，星期六对偶问题与原问题的对比对偶问题与原问题的对

8、比原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）目标函数目标函数max 目标函数目标函数min 不同不同 0 约束约束 0 变量变量 不同不同条件条件 =无约束无约束 0 变量变量 0 约束约束 相同相同 无约束无约束 条件条件 =9第9页，共53页，编辑于2022年，星期六 原原问题（或（或对偶偶问题）对偶偶问题（或原（或原问题）目目标函数函数MaxZ目目标函数函数MinF约束条件数：束条件数：m个个 第第i个个约束条件束条件类型型为“”第第i个个约束条件束条件类型型为“”第第i个个约束条件束条件类型型为“=”对偶偶变量数：量数：m个个 第第i个个变量量0 第第i个

9、个变量量0 第第i个个变量是自由量是自由变量量 决策决策变量数：量数：n个个 第第j个个变量量0 第第j个个变量量0 第第j个个变量是自由量是自由变量量 约束条件数：束条件数：n 第第i个个约束条件束条件类型型为“”第第i个个约束条件束条件类型型为“”第第i个个约束条件束条件类型型为“=”10第10页，共53页，编辑于2022年，星期六 例3.1 写出下面线性规划的对偶规划模型11第11页，共53页，编辑于2022年，星期六Max z=x1-x2+5x3-7x4 s.t.x1+3 x2-2 x3+x4=25 2 x1+7x3 +2x4 -60 2 x1+2x2-4x3 30 x4-5 x4 1

10、0 x1,x2,0 x3 ,x4取值无约束12第12页，共53页，编辑于2022年，星期六Min f=25y1 60y2+30y3-5y4+10y5 s.t.y1+2y2+2 y3 1 3 y1 +2y3 -60 -2 y1+7y2-4y3 =5 y1+2y2+y4+y5 =-7 y1 取值无约束 y3,y5 0 y2,y4 013第13页，共53页，编辑于2022年，星期六对称性定理对称性定理 对偶问题的对偶是原问题对偶问题的对偶是原问题。主对偶定理主对偶定理若若若若(LP)(LP)和和和和(DP)(DP)均可行，那么均可行，那么均可行，那么均可行，那么(LP)(LP)和和和和(DP)(DP

11、)均有最优解均有最优解均有最优解均有最优解,且最优且最优且最优且最优值相等。值相等。值相等。值相等。如果原问题有最优解，则其对偶问题也一样具有最优解，且有如果原问题有最优解，则其对偶问题也一样具有最优解，且有如果原问题有最优解，则其对偶问题也一样具有最优解，且有如果原问题有最优解，则其对偶问题也一样具有最优解，且有max z=min wmax z=min w。二、对偶问题的基本性质二、对偶问题的基本性质 14第14页，共53页，编辑于2022年，星期六弱对偶定理弱对偶定理若若 x,y 分别为（分别为（LP)和（和（DP）的可行解，那么）的可行解，那么cTx bTy。推论推论若若LP（或（或DP

12、）可行，那么）可行，那么LP（或（或DP）无有限最优解）无有限最优解(有无有无界解界解)的充分必要条件是的充分必要条件是DP（或（或LP）无可行解。）无可行解。？当？当LP（或（或DP）无可行解时，则）无可行解时，则DP（或（或LP）具有无界解。）具有无界解。极大化问题的任意一个可行解所对应的目标函数值是其对偶问极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。题最优目标函数值的一个下界。极小化问题的任意一个可行解所对应的目标函数值是其对偶极小化问题的任意一个可行解所对应的目标函数值是其对偶极小化问题的任意一个可行解所对应的目标函数值是其对偶极小化问题的任意一个

13、可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。问题最优目标函数值的一个上界。问题最优目标函数值的一个上界。问题最优目标函数值的一个上界。15第15页，共53页，编辑于2022年，星期六 最优性准则定理最优性准则定理若若若若x,yx,y分别分别分别分别(LP)(LP)，(DP)(DP)的可行解的可行解的可行解的可行解,且且且且c cT Tx=bx=bT Ty y，那么，那么，那么，那么x,yx,y分别为分别为分别为分别为(LP)(LP)和和和和(DP)(DP)的最优解。的最优解。的最优解。的最优解。16第16页，共53页，编辑于2022年，星期六三、影子价格三、影子价格 市场价格

14、市场价格市场价格市场价格 影子价格影子价格影子价格影子价格，确切的定义是：，确切的定义是：一个线性规划对偶问题一个线性规划对偶问题一个线性规划对偶问题一个线性规划对偶问题的最优解的最优解的最优解的最优解（简称为（简称为“对偶最优解对偶最优解”）。）。对偶变量对偶变量yi ：代表对一个单位第：代表对一个单位第i种资源的估价。种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产这种估价不是资源的市场价格，而是根据资源在生产中做出的贡献而作的估价。中做出的贡献而作的估价。bi 是线性规划原问题约束条件右端项，它代表第是线性规划原问题约束条件右端项，它代表第i种资种资源的拥有量。源的拥有量。1

15、7第17页，共53页，编辑于2022年，星期六 影子价格是一个向量，它的分量表示最优目影子价格是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。标值随相应资源数量变化的变化率。若若x x*,y y*分别为（分别为（LPLP）和（）和（DPDP）的最优解，）的最优解，那么，那么，c cT T x x*=b bT T y y*。根据根据 w w=b bT Ty y*=b b1 1y y1 1*+b b2 2y y2 2*+b bm my ym m*可知可知 w w/b bi i =y yi i*y yi i*表示表示 b bi i 变化变化1 1个单位对目标个单位对目标W W 产生的影

16、产生的影响，称响，称 y yi i*为为 b bi i的影子价格。的影子价格。18第18页，共53页，编辑于2022年，星期六 企企业业可可以以根根据据现现有有资资源源的的影影子子价价格，对资源的使用有两种考虑：格，对资源的使用有两种考虑：第第一一，是是否否将将设设备备用用于于外外加加工工或或出出租租，若若租租费费高高于于某某设设备备的的影影子子价价格格，可可考虑出租该设备，否则不宜出租。考虑出租该设备，否则不宜出租。第第二二，是是否否将将投投资资用用于于购购买买设设备备，以以扩扩大大生生产产能能力力，若若市市价价低低于于某某设设备备的的影影子子价价格格，可可考考虑虑买买进进该该设设备备，否否

17、则则不不宜买进。宜买进。19第19页，共53页，编辑于2022年，星期六 需需要要指指出出，影影子子价价格格不不是是固固定定不不变变的的，当当约约束束条条件件、产产品品利利润润等等发发生生变变化化时时，有有可可能能使使影影子子价价格格发发生生变变化化。另另外外，影影子子价价格格是是指指资资源源在在一一定定范范围围内内增增加加时时的的情情况况，当当某某种种资资源源的的增增加加超超过过了了这这个个“一一定定的的范范围围”时时，总总利利润润的的增增加加量量则则不不是是按按照照影影子子价价格格给给出出的的数数值值线线性性地地增增加加。这这个个问问题题还还将将在在灵灵敏敏度度分分析析一一节节中中讨论。讨

18、论。20第20页，共53页，编辑于2022年，星期六利用最优单纯形表求对偶问题最优解利用最优单纯形表求对偶问题最优解 标准形式：标准形式：Max Max z z=50 =50 x x1 1+100+100 x x2 2 s.t.s.t.x x1 1+x x2 2+x x3 3 =300=300 2 2x x1 1+x x2 2+x+x4 4=400=400 x x2 2+x+x5 5=250 =250 x x1 1,x,x2 2,x,x3 3,x,x4 4,x,x5 5 0 0四、对偶问题的解四、对偶问题的解21第21页，共53页，编辑于2022年，星期六-c-cB BB B-1-1I IB

19、B=(p p1 1,p,p4 4,p,p2 2)B B-1-1最优解 x1=50 x2=250 x4 =50影子价格影子价格 y y1 1=50 =50 y y2 2=0 =0 y y3 3 =50,=50,y yi i=c cB BB B-1-1 。22第22页，共53页，编辑于2022年，星期六3.1线性规划的对偶问题概念、理线性规划的对偶问题概念、理论及经济意义论及经济意义3.2线性规划的对偶单线性规划的对偶单纯形法纯形法3.3线性规划的灵敏度分析线性规划的灵敏度分析23第23页，共53页，编辑于2022年，星期六 对偶单纯形法的基本思想对偶单纯形法的基本思想 对偶单纯形法的基本思想是：

20、从一个对对偶偶可可行行解解（检验数非正）出发；然后检验原问题的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。24第24页，共53页，编辑于2022年，星期六 如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。25第25页，共53页，编辑于2022年，星期六1.1.建立初始对偶单纯形表建立初始对偶单纯形表,对应一个基本解对应一个基本解,所有检验数所

21、有检验数均非正均非正,转转2 2；2.2.若若b b0,0,则得到最优解则得到最优解,停止停止;否则否则,若有若有b bk k00则选则选b b最最小小的基变量为出基变量的基变量为出基变量,转转3 3 3.3.若所有若所有a akjkj0(0(j j=1,2,=1,2,n n)，则原问题无可行解，则原问题无可行解,停止停止;否则否则,若有若有a akjkj0 0 则选则选 =min=min j j/a akjkja akjkj00=r r/a akrkr那么那么 x xr r为入基变量为入基变量,转转4 4；4.4.作矩阵行变换使入基变量变为单位向量，转作矩阵行变换使入基变量变为单位向量，转2

22、 2。26第26页，共53页，编辑于2022年，星期六对偶单纯形法的适用范围对偶单纯形法的适用范围 适合于解如下形式的线性规划问题适合于解如下形式的线性规划问题在引入松弛变量化为标准型之后，约束等式两侧同在引入松弛变量化为标准型之后，约束等式两侧同乘乘-1-1，能够立即得到检验数全部非正的原规划基，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，本解，可以直接建立初始对偶单纯形表进行求解，非常方便。非常方便。27第27页，共53页，编辑于2022年，星期六例3.2：求解线性规划问题：求解线性规划问题：标准化：标准化：Max z=-2x1-3x2 -4x3 s.t

23、.-x1-2x2-x3+x4=-3 -2x1+x2-3x3+x5=-4 x1,x2,x3,x4,x5 0Min f=2x1+3x2+4x3 S.t.x1+2x2+x3 3 2x1-x2+x3 4 x1,x2,x3 0 28第28页，共53页，编辑于2022年，星期六表格对偶单纯形法29第29页，共53页，编辑于2022年，星期六3.1线性规划的对偶问题概念、理论及线性规划的对偶问题概念、理论及经济意义经济意义3.2线性规划的对偶单纯形法线性规划的对偶单纯形法3.3线性规划的灵敏度分析线性规划的灵敏度分析30第30页，共53页，编辑于2022年，星期六 进一步理解最优单纯性表中各元素进一步理解最

24、优单纯性表中各元素的含义考虑问题的含义考虑问题 Max Max z=c1 x1+c2 x2+cn xn s.t.a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 .am1x1+am2x2+amnxn=bm x1，x2，xn 031第31页，共53页，编辑于2022年，星期六aij 是随工艺技术条件的改变而改变是随工艺技术条件的改变而改变bi 值是根据资源投入后能产生多大经济值是根据资源投入后能产生多大经济效果来决定的一种决策选择效果来决定的一种决策选择Cj 则是容易受到市场条件的影响则是容易受到市场条件的影响32第32页，共53页，编辑于2022年，星期六I

25、IB B-1-1B B=(p p1 1,p,p4 4,p,p2 2)33第33页，共53页，编辑于2022年，星期六b=b+b b=B-1bPj=B-1 Pjj=cj-CBPj=cj-CBB-1Pj=cj-YTPj34第34页，共53页，编辑于2022年，星期六 1.1.价值系数价值系数c c发生变化：发生变化：m 考虑检验数 j=cj-cri arij j=1,2,n i=1 例:Max Max z z=2=2x x1 1+3+3x x2 2+0+0 x x3 3+0+0 x x4 4+0+0 x x5 5s.t.x1 1+2x2 2+x3 3 =8 4x1 1+x4 4 =16 4x2 2

26、+x5 5=12 x1 1,x2 2,x3 3,x4 4,x5 5 0 35第35页，共53页，编辑于2022年，星期六问：问：c c2 2在什么范围内变化，问题的最优解不变在什么范围内变化，问题的最优解不变 30，40可得到 0c24时，原最优解不变。36第36页，共53页，编辑于2022年，星期六 2.2.右端项右端项 b b 发生变化发生变化 先求 b，b=B-1b，b=b+b 若 b1 增加 4，最优解有何变化？37第37页，共53页，编辑于2022年，星期六 0 0.25 0 这里 B B-1=-2 0.5 1 0.5-0.125 0 b=B B-1*bb=(4,0,0)Tb=(0,

27、-8,2)T b=(4,-4,4)T38第38页，共53页，编辑于2022年，星期六用对偶单纯形法进一步求解，可得：x*=(4,3,2,0,0)T f*=1739第39页，共53页，编辑于2022年，星期六 3.3.增加一个变量增加一个变量 增加变量增加变量 x xn n+1+1 则有相应的则有相应的p pn n+1+1,c cn n+1+1 。那么那么 计算出计算出p pn n+1+1=B B-1-1p pn n+1+1,n n+1+1=c cn n+1+1-c cri ri a ariri n n+1+1 填入最优单纯形表填入最优单纯形表,若若 n n+1+1 0 0 则则 最优解不变；最

28、优解不变；否则，进一步用单纯形法求解。否则，进一步用单纯形法求解。40第40页，共53页，编辑于2022年，星期六例3.6:增加x6,p6=(2,6,3)T,c6=5 0 0.25 0 这里 B B-1=-2 0.5 1 0.5-0.125 0 B B-1p6=(2/3,2,)T41第41页，共53页，编辑于2022年，星期六用单纯形法进一步求解，可得：x*=(1,1.5,0,0,0,2)T f*=16.542第42页，共53页，编辑于2022年，星期六 4.4.增加一个约束增加一个约束 增加约束一个之后，把最优解带入新的约束，若满足约束条件则最优解不变，否则作为新的一行，填入最优单纯形表，并

29、通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。43第43页，共53页，编辑于2022年，星期六例3.7:增加3x1+2x215，问最优解有何变化？X=（4，2）T不满足这个约束。首先将约束条件标准化：3x1+2x2+x6=1544第44页，共53页，编辑于2022年，星期六经对偶单纯形法一步，可得最优解为（3.5,2.25,0,0,3,2)T，最优值为13.7545第45页，共53页，编辑于2022年，星期六 5.5.系数矩阵系数矩阵A A中元素发生变化中元素发生变化 第一种情况第一种情况：若相应的变量xj在最终单纯形表中为非基变量，那么aij的变化分析如下：假设

30、 pj 变化，那么，重新计算出B B-1pj 与 j j=cj-cri ari j 填入最优单纯形表，若 j 0 则最 优解不变；否则，进一步用单纯形法求解。46第46页，共53页，编辑于2022年，星期六47第47页，共53页，编辑于2022年，星期六5.5.5.5.系数矩阵系数矩阵系数矩阵系数矩阵A A A A中元素发生变化中元素发生变化中元素发生变化中元素发生变化第二种情况：第二种情况：若相应的变量在最终单纯形表中为基变量，aij的变化将引起B和B-1发生变化。例：美佳公司计划制造，两种家电，已知各制造一件时，分别占用的设备A,B的台时、调试时间、调试工序及每天可用于这两种家电的能力、各

31、出售一件时的获利情况如下表所示。产品产品 设备能力（h）设备A0 05 51515设备B6 62 22424调试工序1 11 15 5利润（元/件）2 21 148第48页，共53页，编辑于2022年，星期六最终单纯型表如下，若家电若家电 每件需设备每件需设备A,BA,B和调试工时变为和调试工时变为8h,4h,1h,8h,4h,1h,该产品该产品的利润为的利润为3 3元元/件，试重新确定该公司的最优生产计划。件，试重新确定该公司的最优生产计划。首先假设增加了变量首先假设增加了变量X X2 2，那么计算其在最终单纯形表中相，那么计算其在最终单纯形表中相应的系数列向量与检验数应的系数列向量与检验数

32、即企业利润最大时生产 7/2件件，3/2件件49第49页，共53页，编辑于2022年，星期六 1 1.25 -7.5 这里 B-1=0 0.25 -0.5 0 -0.25 1.5 B-1p2=(11/2,1/2,1/2)T50第50页，共53页，编辑于2022年，星期六此时原问题与对偶问题均为非可行解51第51页，共53页，编辑于2022年，星期六所以，先将原问题变为可行解x3+4x4-24x5=-9-x3-4x4+24x5+x6=9用此约束等式替代上一个约束等式52第52页，共53页，编辑于2022年，星期六可得最优解为（11/4,15/8,0,0,3/8)T53第53页，共53页，编辑于2022年，星期六