运筹学 ( 对偶问题及性质)ppt课件.ppt

Chapter2对偶理论(DualityTheory)线性规划的对偶模型对偶性质对偶问题的经济解释-影子价格对偶单纯形法灵敏性分析本章主要内容:,生产中需4种设备按A,B,C,D顺序加工,每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表:产品数据表设备产品ABCD产品利润(元/件)甲21402乙22043设备可利用机时数(时)1281612问:充分利用设备机时,工厂应生产甲和乙型产品各多少件才能获得最大利润?:设甲、乙型产品各生产x1及x2件,则数学模型为:反过来问:若厂长决定不生产甲和乙型产品,决定出租机器用于接受外加工,只收加工费,那么4种机器的机时如何定价才是最佳决策?,厂长的最佳决策显然应符合两条: (1)不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则,便构成了新规划的不等式约束条件。(2)竞争性原则。即在上述不吃亏原则下,尽量降低机时总收费,以便争取更多用户。设A、B、C、D设备的机时价分别为y1、y2、y3、y4,则新的线性规划数学模型为:(对偶问题)对偶问题(原问题)(1)对称形式特点:目标函数求极大值时,所有约束条件为≤号,变量非负;目标函数求极小值时,所有约束条件为≥号,(LP),写出(DP)(n>m)项目非基变量基变量XBXNXs0XsbBNIcj-0项目基变量非基变量XBXNXsCBXBB-1bIB-1NB-1cj--CBB-1N-CBB-,迭代后为P’j,则有P’j=B-1Pj当B为最优基时,应有令Y=CBB-1,-1bIB-1NB-1cj-zj0--CBB-1N-CBB-1-Ys2-:首先将原问题变形为对称形式10.