韩伯棠管理运筹学(第三版)第六章单纯形法的灵敏度分析与对偶.ppt

现在从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、C，那么该厂的厂长应该如何来确定合理的租金呢? 设y1，y2，y3分别为设备A、B、C的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润，也就是由于出租可以获得的利润。建立模型要从两方面来考虑： 思路：把生产单位Ⅰ产品所需各设备的台时总租金不应当低于原利润50元，即y1+2y2≥50，否则就不出租还是用于生产Ⅰ产品以获利50元；同样把生产一单位Ⅱ产品所需各设备的台时的总租金也不应当低于原利润100元，即y1+y2+y3≥100，否则这些设备台时就不出租，还是用于生产Ⅱ产品以获利100元。 租金 Ⅰ Ⅱ 资源限量 设备A,y1 1 1 300台时 设备B,y2 2 1 400台时 设备C,y3 0 1 250台时 怎么做？ 一、作为出租者来说: Min f =300y1+400y2+250y3 s.t. Y1+2y2≥50 y1+y2+y3≥100 y1, y2, y3≥0 这样从两个不同的角度来考虑同一个工厂的最大利润(最小租金)的问题，所建立起来的两个线性规划模型就是一对对偶问题，其中任一个叫做原问题，而另外一个就叫对偶问题。下面来研究这两个问题在数学模型上的关系。 他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好， 即min 300y1+400y2+250y3， 这样得到了该问题的数学模型： 二、对于租用者来说: 一样的吗？ 1．求目标函数最大值的线性规划问题中有n个变量m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。 2．原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数项。 Max z =50x1+100x2 min f = 300y1+400y2+250y3 x1+x2≤300 y1+2y2≥50 2x1+x2≤400 y1+y2+y3≥100 x2≤250 y1,y2,y3≥0 x1,x2≥0 3．原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第i 个约束条件的右边常数项就等于对偶问题的目标函数中的第 i个变量的系数。 4．对偶问题的约束条件的系数矩阵A是原问题约束条件的系数矩阵的转置AT 在例4中，对于原问题其约束条件为： X1+X2≤300 2X1+X2≤400 X2≤250 对应的对偶问题的约束条件为： Y1+2Y2≥50 Y1+Y2+Y3≥100 则其对偶问题： min f=bT y AT y≥CT, y≥0, 其中 y=(y1, y2,……, ym)T 用矩阵的形式来表示，则原问题变为： max Z=CX AX≤b X≥0 其中A为m×n矩阵，该