运筹学-第二章 线性规划的对偶理论

1、线性规划的对偶问题胜利家具厂生产两种家具：桌子和椅子。桌子每张50元，椅子每张30元。桌椅的生产需要木工和油漆工。木匠需要4个小时，油漆工需要2个小时来制作一张桌子。木匠需要3个小时，画家需要1个小时来制作一把椅子。这家工厂每个月可以做120个小时的木工活和50个小时的油漆工。询问工厂如何组织生产以最大化每月销售收入。2.1对偶问题，数学模型max g=50x 130 x2s . t . 4x 13 x 2120(2.1)2x1x 250 x 1，x20，如果一个企业家有一批订单等待处理，他打算使用家具厂的木工和油漆工资源来处理他的产品。因此，他不得不与家具厂就每个工作小时支付给工厂的价格进行

2、谈判。我们可以构建一个数学模型来研究如何让家具厂把资源出租给他，即使它觉得有利可图，并让它支付最低的租金。假设Y1 y1、y2分别代表每个木工和油漆工的工作时间的租金，具有最小租金的目标函数可以表示如下：min s=120 y1 50 y2目标函数中的系数120，50分别代表木工和油漆工可用于出租的工作时间的数量。企业家支付的租金不应该太低，否则家具厂的经理会觉得无利可图，拒绝把租金租给他。因此，他支付的租金不应低于家具厂利用这些资源所能获得的收益：4Y12Y2503Y230Y1，Y20，并得出另一个数学模型：min s=120Y 150 Y2S . t . 4Y 12Y 250(2.2)3Y

3、 1Y 230 Y1，Y20，并且模型(2.1)不同于模型(2.2)。关系在于它们都是关于家具厂的模型，并且使用相同的数据，但区别在于本质内容不同模型(2.1)是从家具厂经营者的角度追求最大销售收入，而模型(2.2)是从家具厂竞争对手的角度追求最小租金。如果模型(2.1)被称为原始问题，那么模型(2.2)被称为对偶问题。任何线性规划问题都有对偶问题，它们都有相应的含义。例2.2:常山机械厂生产两种产品。根据工艺数据，得到以下信息：企业生产了多少件两种产品，使总利润和总收入最大化？数学模型max z=2x 1 3 x2 s . t . 2x 1 2x 2 12 4x 1 16 5x 2 15x

4、1，x20，现在某机械厂为了扩大生产租用了长山机械厂拥有的设备资源，并问长山厂愿意以每小时多少价格租用自己的设备？设置常山工厂以每小时y1、y2和y3的速度租赁设备a、b和c；其对偶问题是最小w=12y1 16y2 15y32y1 4y2 22y1 5y33y1，y2，y30，实例2.2用矩阵表示：对偶问题的原始问题是： Max z=(2，3)，线性规划的对偶关系：(I)最大z=c x s t ax b (2.3) x 0 (ii)最小w=b y s t ay c (2.4) y 0 (2.3) (2.4)称为互对偶问题。其中一个叫做原始问题，另一个叫做它的对偶问题。例2-3:写出下列线性规划

5、问题的对偶问题最小w=12x 1 8x 216 x 3 12x 4s . t . 2x 1 2x 2 4x 3 2x 1 2x 2 4x 4 3x 1，x2，x3，x4 0，解决方法：这个问题的对偶问题：最大z=2Y 13 Y2S . t . 2Y 12Y 212Y 284 Y1 64Y 212Y 1，y2 0，例2-4:写出对偶问题最大s=10x 1 x22x 3s . t . x1x 22 x 3 10y 14 x 12 x 例2-5:将对偶问题最小s=x1 2x3x 3s . t . 2x 1 3x 2 5x 3 2 3x 1 2x 2 7x 3 3x 1，x2，x3 0，解：乘(-1)

6、最小s=x1 2x3x 3s . t . 2x 1 3x 2 3x 3 2 y1-3x 1-x2-7x 3-3y 2 x 1，x2，x3 0在第二个约束方程的两侧。 这个问题的对偶问题：最大z=2 y1-3y 2s . t . 2 y1-3y 213 y1-y225 y1-7y 23 y1，y2 0，例2-6:写出对偶问题min s=2x 13 x2-5x 3s . t . x1x 2-x3 52x 1 x3=4x 1，x2，x3 0，解法：把原问题的约束方程写成不等式约束形式：min s=2x 13 x2-5x3x 1 x2-x3 5y 2 x3 4 y2-2x 1-x3 4 y2 y2 写

7、对偶问题max g=5 y14 Y2-4 Y2 s . t . Y12 Y2-2 Y2 2Y 13-Y1 Y2-Y2 -5 Y1，Y2，Y2 0，让y2=y2- y2 得到max g=5 Y14 Y2S . t . Y12Y 22 Y3-Y1Y 2-5Y 10前一个问题称为对称对偶问题。综上所述，其变换形式如下：例2-7:写出下列线性规划的对偶问题：最小z=7x1 4x 2-3x 3s . t-4x 1 2x 2-6x 324-3x 1-6x 2-4x 315 5x 2 3x 3=30x 10，x2值不受约束，x30，最大w=24 y1 15y 230y 3s . t-4 y1-3y 272

8、y1-6y 25y 3=4-6 y1-4y 23y 3-3y 10，y20，y20例2-8:写出双重问题最小值w=3x 1-2x2x 3s . t . x12x 2=1 y1 2x 2-x3-2y 22 x3 3x 3 y3x 1-2x 2 3x 3 4y 4 x 1，x2 0，x3，没有负面限制。在解决方案：中，使用对偶原理来获得最大g=y1-2y 23y 34 y4 s . t . y1 2y 3y 4 32 y1 2y 2-2y 4-2-y2y 33y 4=1y 20，y3，y40，y1没有负约束。定理2.1:(弱对偶定理)有c x(0) y(0) b的基本定理，2.2为任何可行解x(0

9、)，y(0)在相互对偶问题(1)(2)，和定理2.2(最优准则)如果某个可行解的原始问题和某个可行解的对偶问题，定理2.3(对偶定理)如果原始问题有一个最优解，那么对偶问题也有一个最优解，并且最优值相等。性质2.4如果原问题有无界解，它的对偶问题就没有可行解。但是当原问题(对偶问题)没有可行解时，它的对偶问题(原问题)要么没有可行解，要么有无界解。定理2.5(互补松弛)在线性规划问题的最优解中，如果约束条件严格相等，则对应于约束条件的对偶变量值是非零的；相反，如果约束条件是严格不等式，则其对应的对偶变量必须为零。max z=2x 13x 2s . t . 2x 12x 2124 x 1165

10、x 215 x 1，x20，其最优解为(3，3)，但对于第二个约束，它是一个严格的不等式，因此具有性质2.6的对偶问题的最优解是原问题最优表中相应松弛变量检验数的相位。(在线性规划的原问题和对偶问题中，原问题的松弛变量对应于对偶问题的变量，对偶问题的剩余变量是原问题的变量。)，例如：max z=2x 13x 2s . t . 2x 12x 3 12 4x 1x 4 16 5x 2 X5 15x 1，x20，原始问题变量，原始问题松弛变量，对偶问题变量，对偶问题剩余变量，Y2，Y5，Y4，Y3，Y4，2.3影子价格，原始问题和对偶线性规划中的Bi表示第I个资源的占有，而yi表示单位的第I个资源的

11、估价。影子价格不是市场价格，而是随着企业的生产任务和产品结构而变化。影子价格是一种边际价格。Z=bTy *=b1y1 * b2y2 * bmym *我们可以看到，z/bi=yi *，2x2y=12、1、2、3、4、5、6、5、4、3、2、1最大z=2x 13 x2s . t . 2x 12 x 2124 x 165 x 215 x 1、x20、点(3、3)是最佳解决方案，当a的资源变为13小时时，z*=15，z*=16，这意味着边际价格在对偶问题的互补松弛性质中，它意味着某一资源bi没有被充分利用，并且该资源的影子价格为零。如果为，则表示资源已用尽。它是生产这种产品所消耗的各种资源的影子价格的

12、总和，即产品的隐含成本。从影子价格的含义出发，对单纯形法的计算进行了重新检验：当检验次数大于零时，表明生产这种产品是有利的，可以安排生产。2.4例如，对偶单纯形法：求解下列线性规划问题：最小w=12 y1 16 y2 15 y3 s . t . 2 y1 4 y2 22 y1 5 y3 y1，y2，y30被分类为标准形：max w=-12 y1-16 y2-15 y3-2 y1-4 y2y 4=-2-2 y1-55。当bi0时，将对应于min(bi)的行中的Xr作为交换基变量。对应于凌和Y5的列变量是换入基变量，所以x3是换入基变量，-5是主元素，Y4是换出基变量，所以Y1是换入基变量，-2是

13、主元素，所以这个问题的最优解是：Y1=1，Y2=0，Y3=1/5，W=15，对偶单纯形法从对偶可行解开始，然后检查原规划的基本解是否可行，即是否有负分量。如果有一个分量小于零，迭代寻找另一个基本解，它对应于另一个对偶可行解(测试数不是正数)。如果获得的基本解的所有分量都是非负的，则基本解是最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性(即检验数不为正)，从而使原规划的基本解由不可行逐渐变为可行。在什么情况下应该使用对偶单纯形法：应用前提：有一个基的相应基满足：单纯形表的所有测试数行都不是正的(对偶可行)；变量值可以有负数(不可行解)。注意：通过矩阵行变换运算，可以通过使所有相应的变量都为非负来获得最优单纯形表。用对偶单纯形法求解线性规划问题的过程如下：1 .建立一个初始对偶单纯形表，对应一个基本解，所有的测试数都不是正数，转2；2.如果b0，得到最优解并停止；否则，如果有bk0，选择k行的基变量作为基变量，并转到3 3。如果所有的akj0 (j=1，2，n)，原问题没有可行的解决办法，那么停止；否则，如果akj0存在，选择=minj/akjak 0=r/akr，则xr是