运筹学 ( 对偶问题及性质).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-:首先将原问题变形为对称形式.