972线性规划的对偶问题与灵敏度分析

42第2章线性规划的对偶问题与灵敏度分析本章基本要求1、掌握原问题与对偶问题的对应关系；2、熟练写出一般形式的线性规划的对偶问题；3、掌握对偶问题的基本性质，并会应用这些性质；4、明确影子价格的定义及意义；5、准确地在最优单纯形表的检验数中找出各种资源的影子价格；6、理解对偶单纯形法的原理，并正确使用此方法；7、能够熟练准确地就C，B，A中元素发生的变化来进行灵敏度分析，求出新的最优解．在经济活动中，我们可以追求最大利润，也可以追求最低成本，这是一个问题的两种不同的表现形式．反映到数学上，即任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应，反之亦然，如果我们把其中一个叫原问题，则另一个就叫做它的对偶问题，并称这一对互相联系的两个问题为一对对偶问题．本章将讨论线性规划的对偶问题及灵敏度分析，从而加深对线性规划问题的理解，扩大其应用范围．§2.1对偶问题2.1.1对偶线性规划问题的提出什么是对偶线性规划问题，我们举例来回答这个问题．例2.1-1某厂生产甲、乙、丙三种零件，已知生产甲种零件一件需A型机器4台，B型机器2台；生产乙种零件一件需A型机器6台，B型机器5台；生产丙种零件一件需A型机器3台，B型机器4台．又知每生产甲、乙、丙零件各一件可获利润分别为4元、3元、5元，又知该厂有A型机器120台，B型机器100台，问如何组织生产才能使所获利润最大?解设123,,xxx分别是甲、乙、丙三种零件的数量，依题意建立如下线性规划模型：43123123123123max435463120.254100(2.1-1),,0.zxxxxxxstxxxxxx=++++≤⎧⎪++≤⎨⎪≥⎩现假设根据市场条件的变化,工厂的决策者决定不生产甲、乙、丙三种零件，而把A,B两型机器全部租给某公司，那么该公司对A,B两型机器每台应付给工厂多少租金,才既能使花费总的租金最少、又能使工厂接受？从公司角度考虑,一是所付的租金越低越好；二是所付的租金能使工厂接受,即租金不应低于工厂自己生产甲、乙、丙三种零件所获的效益值，否则,工厂宁可自己生产而不出租设备给公司．设公司租用该工厂A型机器每台为1y元，B型机器每台为2y元，在考虑租用机器定价时，能使该厂接受的条件是：公司租用该厂用以生产一件甲零件的A型机器和B型机器的数量所付的租金不应少于4元，即12424.yy+≥同样，公司租用该厂用以生产一件乙零件和一件丙零件的Ａ型机器和Ｂ型机器的数量所付的租金，分别不应少于3元和5元，即1212653,345.yyyy+≥⎧⎨+≥⎩公司在考虑自身的利益时，其目标是使付出的租用该厂A型机器120台和B型机器100台的租金总和最少，即12min120100.wyy=+综上所述，得到数学模型1212121212min120100424,653,.345,,0.wyyyyyystyyyy=++≥⎧⎪+≥⎪⎨+≥⎪⎪≥⎩(2.1-2)上述两个模型（2.1.1）和（2.1.2）是对同一问题的两种不同考虑的数学描述，其间有着一定的内在联系，我们对此进行比较分析，并从中找出规律，两个模型的对应关系有：1）两个问题的系数矩阵互为转置；2）一个问题的变量个数等于另一个问题的约束条件个数；3）一个问题的右端系数是另一个问题的目标函数的系数；4）一个问题的目标函数为极大化，约束条件为“≤”类型，另一个问题的目标函数为极小化，约束条件为“≥”．我们把这种对应关系称为对偶关系，如果把（2.1-1）式称为原问题，则（2.1-2）式则称44为对偶问题．2.1.2对偶问题的形式一、对称型对偶问题定义2.1.1设原线性规划问题为11221111221121122222112212max(2.1-3).,,,0.nnnnnnmmmnnmnzcxcxcxaxaxaxbaxaxaxbstaxaxaxbxxx=++++++≤⎧⎪+++≤⎪⎪⎨⎪+++≤⎪≥⎪⎩LLLLLLLLLL则称下列线性规划问题11221112121112122222112212min.,,,0.mmmmmmnnmnmnmwybybybayayaycayayaycstayayaycyyy=++++++≥⎧⎪+++≥⎪⎪⎨⎪+++≥⎪≥⎪⎩LLLLLLLLLLL（2.1-4）为其对偶问题，其中iy称其为对偶变量．(2.1-3)和(2.1-4)为一对对称型对偶问题．由定义可知:原问题与对偶问题之间有如下的关系：(1)一个问题求最大值，另一个问题求最小值．(2)求最大值问题，约束条件为“≤”；求最小值问题，约束条件为“≥”．(3)原问题中有n个变量jx，对偶问题中就有n个约束条件，原问题中有m个约束条件，对偶问题中就有m个变量iy．(4)原问题目标函数中变量的系数就是对偶问题约束条件的常数项；原问题中约束条件的常数项就是对偶问题目标函数中变量的系数．(5)两个问题的约束条件的系数矩阵互为转置矩阵．依据上述五条关系，可以把原问题与对偶问题之间的关系总结成一个表(见表2.1—1)，很容易从表上看出它们之间的关系．这个表从横向看是原始问题，从纵向看是对偶问题．用矩阵符号表示原始问题(2.1-3)和对偶问题(2.1-4）为45max.0.zCXAXbstX=≤⎧⎨≥⎩(2.15)-min.0.wYbYACstY=≥⎧⎨≥⎩(2.16)-表2.1—1原问题与对偶问题的关系原问题（求极大）1c2c3cLncmaxzminw1x2x3xLnx右侧1b1y11a12a13aL1na1b≤2b2y21a22a23aL2naLLLLLLL2b≤Lmbmy1ma2ma3maLmnamb≤对偶问题︵求极小︶右侧1c≥2c≥3c≥Lnc≥如果对(2.1-6)的目标函数和约束条件的两端分别乘以一1，得min.0.wYbYACstY-=--≤-⎧⎨≥⎩因为minmax()ww-=-，所以max()wYb-=-().0.YACstY-≤-⎧⎨≥⎩根据对称形式的对偶关系，上式的对偶问题为：min'.0.wCXAXbstX=--≥-⎧⎨≥⎩因为min'max('),wwCX=--=-令'zw=-，得(2.1-6)的对偶问题：46max;,0.zCXAXbX=≤⎧⎨≥⎩即原问题的对偶问题的对偶问题是原问题，因而原问题与其对偶问题互为对偶问题,此性质称为原问题和对偶问题的对称性．二、非对称形式的对偶问题由于并非所有线性规划问题都具有对称形式，故下面讨论一般情况下，线性规划问题如何写出其对偶问题．考虑下面的例子．例2.1-2写出下列线性规划问题的对偶问题1212123123123max252(1)266(2).31(3),,0.zxxxxxxxstxxxxxx=-+≥⎧⎪++≤⎪⎨-+=⎪⎪≥⎩解首先把上述非对称型化为对称型．(1)约束条件(1)两边同乘以一1，得122.xx--≤-(2)把(3)分解成1231233131xxxxxx-+≤-+≥再将后一个条件两边同乘以-1改写成12331.xxx-+-≤-这样把原问题化为对称型：1212123123123123max252266.3131,,0.zxxxxxxxstxxxxxxxxx=---≤-⎧⎪++≤⎪⎪-+≤⎨⎪-+-≤-⎪⎪≥⎩设对应上述4个约束条件的对偶变量分别为'1233,,,yyyy，则根据对应关系写出该问题的对偶问题为：47'1233'1233'1233'233'1233min26225.6330,,,0.wyyyyyyyyyyyystyyyyyyy=-++-⎧-++-≥⎪-+-+≥-⎪⎨+-≥⎪⎪≥⎩再设'333yyy=-得12312312323123min26225.630,0;wyyyyyyyyystyyyyy=-++-++≥⎧⎪-+-≥-⎪⎨+≥⎪⎪≥⎩无非负约束例3.1-3将例2.1-2中的2x改为无非负约束变量，即模型为1212123123132max252266.31,0;zxxxxxxxstxxxxxx=-+≥⎧⎪++≤⎪⎨-+=⎪⎪≥⎩无非负约束.写出其对偶问题.解重复例2.1-2中的(1)，(2)，并且令'222xxx=-，其中'220,0xx≥≥，将上述模型化为对称型．'122'122'1223'1223'1223'1223max2552266.3131,,,0.zxxxxxxxxxxstxxxxxxxxxxxx=-+⎧--+≤-⎪+-+≤⎪⎪-++≤⎨⎪-+--≤-⎪⎪≥⎩令对应上述4个约束条件的对偶变量分别为″′3321,,,yyyy，根据对应关系写出其对偶问题为：48'1233'1233'1233'1233'233'1233min26225.56330,,,0.wyyyyyyyyyyyystyyyyyyyyyyy=-++-⎧-++-≥⎪-+-+≥-⎪⎪-+-≥⎨⎪+-≥⎪⎪≥⎩令'333yyy=-，并将第二、第三个约束条件合并得：12312312323123min26225.630,0;wyyyyyyyyystyyyyy=-++-++≥⎧⎪-+=⎪⎨+≥⎪⎪≥⎩无非负约束由以上例子可以看出，若一个问题的第i个约束为“=”，则另一个问题的第i个变量为无非负约束变量；反之，一个问题第j个变量为无非负约束变量，则另一个问题第j个约束为“=”．综上所述，线性规划的原问题与对偶问题的对应关系，可用表2.1-2表示．表2.1—2线性规划的原问题与对偶问题的对应关系原问题(或对偶问题)对偶问题(或原问题)1．目标函数求maxz目标函数求minw2．目标函数中jx的系数为jc第j个约束条件的常数项为jc3．第i个约束条件的常数项为ib目标函数中iy的系数为ib4．约束条件的系数矩阵为A约束条件的系数矩阵为TA5．约束条件有m个对偶变量有m个6．决策变量有n个约束条件有n个7．第i个约束条件为“≤”对偶变量0iy≥8．第i个约束条件为“=”对偶变量iy无非负限制9．第i个约束为“≥”第i个对偶变量0iy≤10．决策变量0jx≥第j个约束条件为“≥”11．决策变量jx无非负限制第j个约束条件为“=”12．第j个变量0jx≤第j个约束条件为≤依据表2.1—2，对于任意给定的一个线性规划问题，均可根据其对应关系直接写出其对49偶问题，而无须化为对称型．例2.1-4设有线性规划问题123412341342341234min23535224..60,0,0,zxxxxxxxxxxxstxxxxxxx=+-+--+≥⎧⎪+-≤⎪⎨++=⎪⎪≤≥≥⎩无非负约束试写出其对偶线性规划问题．解设对偶变量依次为123,,yyy，则按表3.1—2的对应关系，其对偶线性规划问题为：1231213123123123max'546223..32510,0,zyyyyyyystyyyyyyyyy=+++≥⎧⎪-+≤⎪⎪-++≤-⎨⎪-+=⎪⎪≥≤⎩无非负约束.2.1.3对偶问题的基本性质设线性规划原问题为max.0.zCXAXbstX=≤⎧⎨≥⎩(2.17)-其对偶问题为min.0.wYbYACstY=≥⎧⎨≥⎩(2.18)-下面我们来讨论原问题与对偶问题的几条性质．性质1若X为问题(2.1-7)的一个可行解,Y为问题(2.1-8)的一个可行解，则有CXYb≤．该性质说明：原问题的最优值(最大值)是对偶问题目标函数的下界；而对偶问题的最优值(最小值)是原问题的目标函数的上界．性质2若原问题有可行解，但其目标函数无界，则对偶问题无可行解；若对偶问题有可行解，但其目标函数无界，则原问题无可行解．性质3(性质2的逆命题)若原问题有可行解，而对偶问题无可行解，则原问题无界；若对偶问题有可行解，而原问题无可行解，则对偶问题无界．例2.1-5原问题为5012122112max21.33,0.zxxxxstxxxx=+--≤-⎧⎪-+≤⎨⎪≥⎩对偶问题为12122112min32.31,0.wyyyystyyyy=-+--≥⎧⎪-+≥⎨⎪≥⎩原问题有可行解，但由于12,0yy≥，使对偶问题中的约束条件122yy--≥不成立，即对偶问题无可行解，故原问题无上界．性质4(最优准则定理)如果*X,*Y分别是(2.1-7)和(2.1-8