运筹学5对偶理论与灵敏度分析.pptx

;;; 如果我们换一个角度，考虑另外一种经营问题。 假如有一个企业家有一批等待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。因此，他要同家具厂谈判付给该厂每个工时的价格。可以构造一个数学模型来研究如何使自己付的租金最少，又使家具厂觉得有利可图肯把资源出租给他？; 假设 y1, y2 分别表示每个木工和油漆工工时的租金，则所付租金最小的目标函数可表示为： min s = 120 y1 + 50 y2 目标函数中的系数 120，50 分别表示可供出租的木工和油漆工工时???。; 该企业家所付的租金不能太低，否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能得到的利益： 4 y1 + 2y2 ? 50 3 y1 + y2 ? 30 y1, y2 ? 0; 于是得到数学模型： min g = 120 y1 + 50 y2 s.t. 4 y1 + 2y2 ? 50 (2.2) 3 y1+ y2 ? 30 y1, y2 ? 0;模型(2.1)和模型(2.2) 既有区别又有联系。联系在于它们都是关于家具厂的模型并且使用相同的数据，区别在于模型反映的内容是不同的。模型(2.1)是站在家具厂经营者立场追求销售收入最大，模型(2.2)是则站在家具厂对手的立场追求所付的租金最少。;如果模型(2.1)称为原问题（P）， 则模型(2.2)称为对偶问题（D）。 任何线性规划问题都有对偶问题。 原问题与对偶问题之间没有严格的界限，它们互为对偶。;;;对称形式的对偶关系;怎样写出非对称形式的对偶问题？ ?根据对应规律（参见对偶关系表）直接写出；;;例1：写出下列线性规划问题的对偶问题 min S = x1 + 2x2 + 3x3 s.t. 2x1+3x2 + 5x3 ? 2 3x1+ x2 + 7x3 ? 3 x1，x2 ， x3 ? 0;该问题的对偶问题： max z = 2 y1 + 3y2 s.t. 2y1+3y2 ? 1 3y1+ y2 ? 2 5y1+7y2 ? 3 y1? 0， y2 ?0;例2：写出下列线性规划问题的对偶问题 min S = 2x1 + 3x2 - 5x3 s.t. x1+ x2 - x3 ? 5 2x1 + x3 = 4 x1，x2 ， x3 ? 0 ;该问题的对偶问题为： max z = 5 y1 + 4y2 s.t. y1 + 2y2 ? 2 y1 ? 3 -y1+ y2 ? -5 y1 ? 0 ，y2 无非负约束 ;练习1：写出下列线性规划问题的对偶问题 min S = 3x1 - 2x2 + x3 s.t. x1+2x2 = 1 2x2 - x3 ? -2 2x1 +x3 ? 3 x1- 2x2 + 3x3 ? 4 x1，x2 ? 0 ， x3 无非负限制 ;练习2、已知下表为求解某线性规划问题的最终单纯形表，表中x4、x5为松弛变量。试： （1）写出线性规划原问题。 （2）写出对偶问题。 （3）求对偶问题的最优解。;练习1答案 解: 对偶问题为： max z = y1-2y2 +3y3 +4y4 s.t. y1+ 2y3 + y4 ? 3 2y1 +2y2