2、线性规划问题对偶问题.pptVIP

2、线性规划问题的对偶问题;;; 假如有一个企业家有一批等待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。因此，他要同家具厂谈判付给该厂每个工时的价格。可以构造一个数学模型来研究如何既使家具厂觉得有利可图肯把资源出租给他，又使自己付的租金最少？; 假设 y1, y2 分别表示每个木工和油漆工工时的租金，则所付租金最小的目标函数可表示为： min s = 120 y1 + 50 y2 目标函数中的系数 120，50 分别表示可供出租的木工和油漆工工时数。; 该企业家所付的租金不能太低，否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能得到的利益： 4 y1 + 2y2 ? 50 3 y1 + y2 ? 30 y1, y2 ? 0; 得到另外一个数学模型： min s = 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)称为原问题， 则模型(2.2)称为对偶问题。 任何线性规划问题都有对偶问题， 而且都有相应的意义。;例2.2 ：常山机器厂生产Ⅰ、Ⅱ两种产品，按工艺资料获得如下资料：;数学模型 max Z=2x1+3x2 s.t. 2x1+2x2 ? 12 4x1 ? 16 5x2 ?15 x1,x2 ? 0 ; 设常山厂将设备A、B、C每h的出租价格为y1,y2,y3; 它的对偶问题为 min w=12y1+16y2+15y3 2y1+4y2 ≥2 2y1 +5y3≥3 y1,y2,y3≥0;把例2.2用矩阵表示： 对偶问题 原问题: Max z=(2,3) ;线性规划的对偶关系： （I） Max z = C x s.t. Ax ? b （2.3） x ? 0 (II) Min w = b’ y s.t. A’y ? C’ （2.4） y ? 0 （2.3)(2.4)称作互为对偶问题。其中一个称为原问题，另一个称为它的对偶问题。;例2-3：写出下列线性规划问题的对偶问题 min w=12x1+8x2 +16x3+12x4 s.t. 2x1+ x2 +4x3 ? 2 2x1+2x2 + 4x4 ? 3 x1，x2 ， x3 ， x4 ? 0 ;解：该问题的对偶问题： max z = 2y1 + 3y2 s.t. 2y1 + 2y2 ? 12 y1 + 2y2 ? 8 4 y1 ? 16 4y2 ? 12