OR6-对问题.ppt

Chapter6 对偶理论 ( Duality Theory ) 线性规划的对偶模型 设某工厂生产两种产品甲和乙，生产中需4种设备按A，B，C，D顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表 ： 线性规划的对偶模型 解：设甲、乙型产品各生产x1及x2件，则数学模型为： 线性规划的对偶模型 在市场竞争的时代，厂长的最佳决策显然应符合两条： ?（1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。 （2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。 线性规划的对偶模型 把同种问题的两种提法所获得的数学模型用表2表示，将会发现一个有趣的现象。 线性规划的对偶模型 线性规划的对偶模型 （1）对称形式 线性规划的对偶模型 例6.1 写出线性规划问题的对偶问题 线性规划的对偶模型 线性规划的对偶模型 线性规划的对偶模型 线性规划的对偶模型 例6.2 写出下列线性规划问题的对偶问题. 对偶性质 对偶性质 对偶性质 原问题与其对偶问题的变量与解的对应关系： 在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。 对偶性质 对偶性质 对偶性质 推论3：在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行（如D），则该可行的问题目标函数值无界。 对偶性质 性质4 强对偶性：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。 对偶性质 性质5的应用： 该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y＊求X＊或已知X＊求Y＊ 对偶性质 例6.4 已知线性规划 对偶性质 设对偶问题最优解为Y＊＝(y1，y2),由互补松弛性定理可知，X＊和 Y＊满足： 对偶性质 例6.5 已知线性规划 对偶性质 设对偶问题最优解为X＊＝(x1，x2 ，x3)T ,由互补松弛性定理可知，X＊和 Y＊满足： 对偶性质 原问题与对偶问题解的对应关系小结 思考题 判断下列结论是否正确，如果不正确，应该怎样改正？ 对偶问题的经济解释－影子价格 1. 影子价格的数学分析： 对偶问题的经济解释－影子价格 2. 影子价格的经济意义 1）影子价格是一种边际价格 在其它条件不变的情况下，单位资源数量的变化所引起的目标函数最优值的变化。即对偶变量yi 就是第 i 种资源的影子价格。即： 对偶问题的经济解释－影子价格 2）影子价格是一种机会成本 影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市场价格。因此，从另一个角度说，它是一种机会成本。 对偶问题的经济解释－影子价格 3）影子价格在资源利用中的应用 根据对偶理论的互补松弛性定理: Y*Xs=0 , YsX*=0 表明生产过程中如果某种资源bi未得到充分利用时，该种资源的影子价格为0；若当资源资源的影子价格不为0时，表明该种资源在生产中已耗费完。 对偶问题的经济解释－影子价格 4）影子价格对单纯形表计算的解释 对偶单纯形法 对偶单纯形法 对偶单纯形法 对偶单纯形法 对偶单纯形法 对偶单纯形法 对偶单纯形法 对偶单纯形法 本章小结 单纯形表中的检验数 其中cj表示第j种产品的价格; 表示生产该种产品所消耗的各项资源的影子价格的总和,即产品的隐含成本。 当产值大于隐含成本时，即 ，表明生产该项产品有利，可在计划中安排；否则 ，用这些资源生产别的产品更有利，在生产中安排该产品。 勉宋录谨殷醇晰窜帝蚁邹霓煽嫩玉粳九跑绸釉饼裸煞臣揖入蔷躁袱旬毋阿OR6-对偶问题OR6-对偶问题 对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。要简单理解为是求解对偶问题的单纯形法。 对偶单纯形法原理 对偶单纯形法基本思路： 找出一个对偶问题的可行基，保持对偶问题为可行解的条件下，判断XB是否可行（XB为非负），若否，通过变换基解，直到找到原问题基可行解（即XB为非负），这时原问题与对偶问题同时达到可行解，由定理4可得最优解。 卤奋泅弗嗓绑焰辉谱磊职殷膨摩窍畔罢猖秸兆求遵澡乓些侩帛蛹浇充蜡颅OR6-对偶问题OR6-对偶问题 找出一个DP的可行基 LP是否可行 （XB ≥0） 保持DP为可行解情况下转移到LP的另一个基本解 最优解 是 否 循 环 结束 毗漳牢藕涂慢鸽扒苟巫拐钮苗力版峡炙奋笺用瘟补吟魄吧砸丈消卖愚毕骸OR6-对偶问题OR6-对偶问题 例2.9 用对偶单纯形法求解： 解:（1）将模型转化为求最大化问题，约束方程化为等式求出