2019年 第2章线性规划的对偶理论ppt课件.ppt

《2019年 第2章线性规划的对偶理论ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划问题具有对偶性,即任何一个线性规划问题,都存在另一个线性规划问题问题与之对应.如果把其中一个问题叫做原问题,则另外一个就叫做它的对偶问题.并称这两个相互联系的问题为一对对偶问题.研究对偶问题之间的关系及其性质,就是线性规划的对偶理论(DualityTheory).第2章线性规划的对偶理论§1对偶问题的提出§2原问题与对偶问题§3对偶问题的基本性质§4影子价格§5对偶单纯形法§6灵敏度分析§7参数线性规划常山机器厂用A、B、C三种设备生产I、II两种产品。问该企业应安排生产使总的利润收入为最大。占用设备时间(h)III用于生产的能力设备A2212设备B

2、4016设备C0515利润(元)23例1生产计划问题2-1对偶问题的提出模型s.t.现有四海机器厂,为扩大生产想租常山机器厂的设备,问常山机器厂分别以每小时什么价格才愿意出租自己的设备呢?设设备A,B,C每小时的出租价格分别为y1,y2,和y3元出租条件:租金收入≥生产的获利。四海机器厂接受条件:租金要低LP1LP2原问题对偶问题矩阵形式2-2原问题与对偶问题对应关系：(1)(2)变量的个数约束条件个数=(3)(原)约束条件≥(4)右端项目标函数的系数(对偶)约束条件≥原问题(求极大)c1c2…cn右端项x1x2…xna11a12…a1na21a22…a2n

3、am1am2…amny1y2ymb1b2bmM对偶问题(求极小)右端项原问题(对偶问题)对偶问题(原问题)目标函数max目标函数min目标函数中变量的系数约束条件右端项约束条件右端项目标函数中变量的系数例2写出下列线性规划的对偶问题写出下列线性规划的对偶问题2-3对偶问题的基本性质弱对偶性；强对偶性；最优性;无界性;互补松弛性说明在下面的讨论中,假定线性规划原问题和对偶问题分别如下原问题对偶问题掌握原问题和其对偶问题解之间的关系1.弱对偶性是其对偶问题的可行解，则恒有若是原问题的可行解，证明：原问题对偶问题2.最优性问题的可行解，且有若是原问题的可行解，提示

4、,则是原问题的最优解，是其对偶问题的最优解。设是原问题的最优解，是其对偶问题的最优解。是其对偶3.无界性若原问题(对偶问题)具有无界解,则其对偶问题(原问题)无可行解.说明逆命题不成立。即原问题(对偶问题)无可行解，则其对偶问题(原问题)或无可行解或具有无界解,反证法结合弱对偶性4.强对偶性(对偶定理)若原问题有最优解,则其对偶问题且有证明：将原问题化成标准形式用单纯形法求得最优解，则有即即故是对偶问题的可行解,又因由性质2即可证得。也一定有最优解,5.互补松弛性在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值为非零,则该约束条件取严格等式;反之如

5、果约束条件取严格不等式,则该对应的对偶变量一定为零。即：如果则如果则证明：由弱对偶性知，由最优性知从而因此6.互补的基解线性规划的原问题及其对偶问题之间①存在一对互补的基解,其中原问题的松弛变量对应对偶问题的变量,对偶问题的剩余变量对应原问题的变量；②这些互相对应的变量如果在一个问题的解中是基变量,则在另一问题的解中是非基变量；③将这对互补的基解分别代入对偶问题的目标函数有z=w.说明：原问题的检验数恰好是对偶问题的基解.例3.s.t.原问题对偶问题标准形式最终单纯形表cj→23000CB基bx1x2x3x4x5zj-cj203301001/5400-214

6、/53101/20-1/500101/5x1x4x2cj-12-16-1500CB基by1y2y3y4y5-12y11120-1/20-15y31/50-4/511/5-1/5zj-cj04033原问题变量原问题变量原问题松弛变量原问题松弛变量对偶问题变量对偶问题剩余变量对偶问题变量对偶问题剩余变量说明：1)只需求解其中一个问题,从最优解的单纯形表中同时得到另一个问题的最优解.2)单纯形法迭代的每一步中,原问题及对偶问题解的关系目标函数值原问题对偶问题可行解非可行解可行解非可行解最优z>zmaxz

7、i种资源的拥有量表示对一个单位第i种资源的估价,非市场价格.影子价格说明：1)供求关系影响市场价格;资源的利用影响影子价格.2)影子价格是一种边际价格.在给定的生产条件下,bi每增加1个单位时目标函数的增量3)影子价格又是一种机会成本.若市场价格<影子价格,买进该资源市场价格>影子价格,卖出该资源若市场价格影子价格,4)互补松弛性的实际意义如果则如果则在生产中,若某资源未充分利用时,影子价格为0；当影子价格不为0时,表明该资源在生产中已耗费完毕.5)检验数的经济意义:表示第j种产品的产值表示生产一个单位该种产品所消耗各项资源的影子价格的总和,即产品的隐含成本

8、.若产值<隐含成本,产值>隐含成本,若可安排生产该产