管理运筹学讲义 第2章-线性规划的对偶理论8学时

,第2章线性规划的对偶问题与灵敏度分析,线性规划进一步研究,学习要点,理解线性规划问题的对偶问题构建线性规划问题的对偶模型正确理解对偶规划的基本性质掌握影子价值的涵义及其应用线性规划灵敏度分析,第2章线性规划的对偶问题与灵敏度分析,2.1对偶原理2.2对偶单纯形法2.3灵敏度分析,2.1对偶原理,2.1.1问题的导出2.1.2对偶问题的定义2.1.3对偶定理,对偶问题概念：在线性规划问题中，存在一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规划问题，称为其“对偶”问题。对偶问题是对原问题从另一角度进行的描述，其最优解与原问题的最优解有着密切的联系，在求得一个线性规划最优解的同时也就得到对偶线性规划的最优解，反之亦然。对偶理论就是研究线性规划及其对偶问题的理论，是线性规划理论的重要内容之一。,例2.1某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：,2.1.1问题的提出,【解】设x1，x2，x3分别为产品A，B，C的产量，则线性规划数学模型为：,现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？价格太高对方不愿意接受，价格太低本单位收益又太少。合理的转让价格应是不低于用同等数量资源由自身组织生产活动时所获得的盈利。这一决策问题可用下列线性规划数学模型来表示。,设y1，y2，y3及y4分别表示四种资源的单位收购价格，则从收购者角度考虑出让资源的收益为：,Minw=500y1+450y2+300y3+550y4,表示。企业生产一件产品A用了四种资源的数量分别是9，5，8和7个单位，利润是100,企业出售这些生产一件产品的资源所得的利润不能少于100，即：,同理，对产品B和C有,价格不可能小于零，即有yi0,i=1,4.从而企业的资源价格模型为,保证A产品利润,保证B产品利润,保证C产品利润,这是一个线性规划数学模型，称这一线性规划问题是前面生产计划问题的对偶线性规划问题或对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可写出另一个问题。,2.1.2对偶问题的定义,一、对称形式下线性规划原问题的对偶形式,对称形式的定义是（1）目标函数求极大值时，所有约束条件为号，变量非负；（2）目标函数求极小值时，所有约束条件为号，变量非负。对称形式的线性规划的对偶问题亦是对称形式。,用yi（i=1，2，.，m）代表第i种资源的估价，则其对偶问题的一般形式为：,对称形式的线性规划问题用矩阵形式表示：,或,对偶问题的特点:(1)若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然；(2)原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵；(3)极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。,【例2.2】写出下列线性规划的对偶问题,解：这是一个对称形式的线性规划，设Y=（y1，y2），则有：,【例2.3】写出下列线性规划的对偶问题,解：这是一个对称形式的线性规划，它的对偶问题求最小值，有三个变量且非负，有两个“”约束，即：,原问题和对偶问题的关系可用下面表格的形式来表示（对称形式）：,二、非对称形式的原-对偶问题关系,例2.4写出下述线性规划问题的对偶问题,一般线性规划问题的对偶问题,若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。也可直接按表21中的对应关系写出非对称形式的对偶问题。,将上述原问题与对偶问题的对应关系列于表21,例如，原问题是求最小值，按表2-1有下列关系：,1.第i个约束是“”约束时，第i个对偶变量yj0,2第i个约束是“=”约束时，第i个对偶变量yi无约束；,3当xj0时，第j个对偶约束为“”约束，当xj无约束时，第j个对偶约束为“=”约束。,表21,【例2.5】写出下列线性规划的对偶问题,【解】目标函数求最小值，应将表21的右边看作原问题，左边是对偶问题，原问题有3个约束4个变量，则对偶问题有3个变量4个约束，对照表21的对应关系，对偶问题为：,例2.6,本节以实例引出对偶问题;,介绍了如何写对称与非对称问题的对偶问题;,1.您应该会写任意线性规划的对偶问题；,作业：教材,附:单纯形法矩阵描述,初始单纯行表,经过若干迭代后，基变量为XB，则其系数矩阵应为I,且经过行行的初等变换，XS的系数矩阵I应为B-1,新单纯形表,当B为最优基时，应有非基变量的检验数：CN-CBB-1N0-CBB-10XB的检验数可改写为：CB-CB*I=0综上，有：C-CBB-1A0-CBB-10CBB-1为单纯乘子，令Y=CBB-1则上式可改写为：YACY0,设原问题是（记为LP）：,对偶问题是（记为DP）：,这里A是mn矩阵,X是n1列向量，Y是1m行向量。假设Xs与Ys分别是（LP）与（DP）的松驰变量。,【性质1】对称性对偶问题的对偶是原问题。,证：设原问题是,2.1.3对偶定理,它与下列线性规划问题是等价的：,再写出它的对偶问题。,它与下列线性规划问题是等价的,即是原问题。,由上节内容可知，它的对偶问题是：,【性质2】弱对偶性设X、Y分别为（LP）与（DP）的可行解，则CXYb。,【证】因X、Y是可行解，故有AXb,X0及YAC，Y0,将不等式AXb两边左乘Y,得YAXYb,再将不等式YAC两边右乘X，,故CXYAXYb,这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值(对应特定的可行解)。,得CXYAX,由这个性质可得到下面几个结(推)论：,(1)（LP）的任一可行解的目标值是（DP）的最优值下界；（DP）的任一可行解的目标值是（LP）的最优值的上界；(2)在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；(3)若原问题可行且另一个问题不可行，则原问题具有无界解。注意上述结论（2）及（3）的条件不能少。一个问题有可行解时，另一个问题可能有可行解（此时具有无界解）,也可能无可行解。,St,例2-7：,而对偶问题：,有可行解，由结论（3）知必有无界解。,【性质3】最优性准则定理设X与Y分别是（LP）与（DP）的可行解，则当X、Y是（LP）与（DP）的最优解当且仅当CX=Yb.证明：由弱对偶定理可知，对任意可行解有:CXYb因此对于X和Y也将分别有CXYbCXYb又因为CX=Yb故有YbYbCXCX,【性质4】强对偶定理若原问题（LP）有最优解，那么对偶问题（DP）也有最优解，且目标函数值相等，若一个问题无最优解，则另一问题也无最优解。,【证】两者都有最优解的证明依据弱对偶性推论1；设（LP）有最优解X，那么对于最优基B必有CCBB-1A0与CBB-10，即有YAC与Y0，这里Y=CBB-1，从而Y是可行解，对目标函数有：,由性质3最优性准则知Y是最优解。,【性质5】互补松弛定理设X、Y分别为（LP）与（DP）的可行解，XS和YS是它的松弛变量的可行解，则X和Y是最优解当且仅当,YSX=0和YXS=0,【证】设X和Y是最优解，由性质3，CX=Yb，由于XS和YS是松弛变量，则有,AXXSbYAYS=C,将第一式左乘Y，第二式右乘X得,YAXYXSYbYAXYSX=CX,显然有YXS=YSX,又因为Y、Xs、Ys、X0，所以有,YXS=0和YSX=0,成立。,反之，当YXS=0和YSX=0时，有,YAXYbYAX=CX,显然有Yb=CX,由性质3知Y与X是（LP）与（DP）的最优解。证毕。,性质5告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知Y求X或已知X求Y。,YXS=0和YSX=0,两式称为互补松弛条件。将互补松弛条件写成下式,由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：,（1）当yi0时，XS=0，反之当XS0时yi=0；,注意：对于非对称形式，性质5的结论仍然有效。,【性质6】（LP）的检验数的相反数对应于（DP）的一组基本解。其中第j个决策变量Xj的检验数的相反数对应于（DP）中第j个松弛变量YSj的解，第i个松弛变量XSi的检验数的相反数对应于第i个对偶变量Yi的解。反之，（DP）的检验数（注意：不乘负号）对应于（LP）的一组基本解。证明略。,设原问题是,它的对偶问题是,则原问题单纯形表的检验数行对应对偶问题的一个基解。其对应关系是：,2.2对偶最优解的经济意义,Z*=yb=(y1ym),=b1y1*+b2y2*+bmym*,根据基本性质Xj*,YI*分别是原问题和对偶问题的最优解，带入目标函数有：,Z=,biyi,对求bi的偏导：,z*,bi,=,yi*,yi*影子价格（shadowprice）。,yi*的意义代表在资源最优利用条件下对单位第i种资源的估价（即是对偶问题的最优解）;bi的单位增加量所引起的最优目标函数值的相应增量。,(1)影子价格不是资源的实际价格，反映资源配置与利用情况。(2)影子价格是一种边际价格。在资源最优利用条件下，bi每增加一单位时目标函数z的增量。说明增加哪种资源对经济效益最有利。(3)影子价格是机会成本，预示着资源买进卖出，最终达到均衡的状态。预知哪些资源是稀缺资源而哪些资源不稀缺。(4)根据互补松弛性质，表明生产过程中若某种资源bi未得到充分利用时，该资源影子价格为0；当资源影子价格不为0时，表明该资源已消耗完毕。(5)利用影子价格分析新品的资源效果：定价决策；利用影子价格分析现有产品价格变动的资源紧性；可以帮助分析工艺改变后对资源节约的收益。,例:2-9,y1=5/3,y2=1/3即工时的影子价格为5/3，材料的影子价格为1/3。如果目前市场上材料的价格低于1/3，则企业可以购进材料来扩大生产，反之可以卖掉部分材料。如果有客户以高于5/3的价格购买工时，则可以出售一些工时，反之则相反。,2.3对偶单纯形法,设原问题是（记为LP）：,对偶问题是（记为DP）：,对偶问题是（记为DP）：,根据对偶性质6，可以构造一个求线性规划的另一种方法，即对偶单纯形法。对偶单纯形法并不是求解对偶问题解的方法，而是利用对偶理论求解原问题最优解的方法。对偶单纯形法的条件是：初始表中对偶问题可行，即极大化问题时j0，极小化问题时j0。,对偶单纯形法的计算步骤：,(1)将线性规划的约束化为等式，求出一组基本解，因为对偶问题可行，即全部检验数j0（max）或j0（min）,当基本解可行时，则达到最优解；若基本解不可行，即有某个基变量的解bi0，则进行换基计算；（无解：bi0且所有aij0)(2)先确定出基变量。行对应的变量xl出基；(3)再选进基变量。求最小比值(4)求新的基本解，用初等变换将主元素alk化为l,k列其它元素化为零，得到新的基本解，转到第一步重复运算。,【例2-10】用对偶单纯形法求解,解:先将约束不等式化为等式，再两边同乘以1，得:,用对偶单纯形法，迭代过程如下:,例211用对偶单纯形法求解：,应当注意：,(1)用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解；（2）初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则；（3）最小比值中的绝对值是使得比值非负，在极小化问题时j0，分母aij0这时必须取绝对值。在极大化问题中，j0分母aij4,则目前解不再是最优解,应该用单纯形方法继续求解,否则解不变。即对于C3而言,使最优解不变的条件是C34。,例2-13：价值系数C3从3变为5。,二、价值系数CB发生改变,C1-30;1-4/3C10;1/3C1-10有3/4C13若C13/4则x4进基，x1出基；若3C1则x3或x5进基，x2出基。,C1,C1,C1-3,1-4/3C1,1/3C1-1,例2-14：价值系数X1从2变为1/2。,2.4.3右端常数b发生改变,9/4b19,b1,4b1/3-3,3-b1/3,-3+5b1/3,例2-14：右端常数b1从3变为2。,例2-15：右端常数b1从3变为12。,右端常数b发生改变,3b212,b2,4-b2/3,b2/3-1,-b2/3-5,2.4.4增加一个变量,若企业在计划期内，有新的产品可以生产，则在知道新产品的单位利润，单件资源消耗量时，可以在最优表中补充一列，其中的前m行可以由基矩阵的逆矩阵得到，而检验数行也可以由与其它列相同的方法计算得到。若检验数非正，则原最优解仍为最优，原生产计划不变，不生产这种新产品；否则，当检验数为正时，则应以该变量进基，作单纯形迭代，从而找出新的最优解。,例2-16:增加一种新产品,2.4.5增加一个约束条件,在企业的生产过程中，经常有一些突发事件产生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响，若把目前的最优解代入新增加的约束，能满足约束