对偶线性规划.ppt

第二章,线性规划的对偶理论,2,任一线性规划问题都存在另一与之伴随的线性规划问题，他们从不同角度对一个实际问题提出并描述，组成一对互为对偶的线性规划问题。,2.1 对偶线性规划问题的提出,对偶线性规划,3,一、对偶线性规划问题,某工厂计划安排生产、两种产品，已知每种单位产品的利润、生产单位产品所需的设备台时及A、B两种原材料的消耗、现有原材料和设备台时的定额如下表所示：,【例1】,原问题的策略:问应如何安排生产才能使工厂获利最大？,现在的策略:假设不生产、产品,而是计划将现有资源出租或出售,从而获得利润,这时需要考虑如何定价才合理?,对偶线性规划,4,设x1、x2分别表示计划生产产品、的单位数量，由题意原问题的模型为：,工厂获得最大利润,符合资源限制,原问题的模型,对偶线性规划,5,改变策略后，需要考虑如何给资源定价的问题！,设y1、y2、y3分别表示出租单位设备台时的租金和出售单位原材料A、B的利润.,y1+4y22，,2y1+4y33,则：,工厂出租设备、原材料的租金要大于生产的利润才合算。,工厂把所有设备台时和资源都出租和出让，用户支付为：,要寻找使租用者支付的租金最少的策略。,新问题的模型,对偶线性规划,6,工厂改变策略以后的数学模型为：,工厂获得相应利润,用户所付租金最少,对偶线性规划,7,联系在于，它们都是关于工厂生产经营的模型,并且使用相同的数据；,原模型和对偶模型既有联系又有区别,区别在于,它们所反映的实质内容是完全不同的：前者是站在工厂经营者的立场上追求工厂的销售收入最大，而后者则是站在谈判对手的立场上寻求应付工厂租金最少的策略。,对偶线性规划,8,所谓对偶规划，就是与线性规划原问题相对应并使用同一组数据按照特定方法形成的另一种反映不同性质问题的线性规划模型。,对偶线性规划,9,二、对偶规划的一般数学模型,原模型与对偶模型有很多的内在联系和相似之处。如原问题如求目标函数最大化，对偶问题即求目标函数最小化；原问题目标函数的系数变成为对偶问题的右边项，而原问题的约束的右边项则变成为对偶问题目标函数的系数；对偶问题的系数矩阵是原问题系数矩阵的转置。就象一个人对着镜子会左右颠倒一样，原问题与对偶问题之间存在着严格的对应关系。,原问题的一般模型可定义为：,相应的对偶问题的一般模型可定义为：,对偶线性规划,问题：如何由原模型写出对偶模型？其规律是什么?,10,三、原问题与对偶问题的对应关系,当我们讨论对偶问题时必定是指一对问题，因为没有原问题也就不可能有对偶问题。原问题和对偶问题总是相依存在的。同时，原问题和对偶问题之间也并没有严格的界线，它们互为对偶，谁都可以是原问题，谁也都可以是对偶问题。,下列的表给出了原问题模型和模型的对应关系，这些也可以看作是一个线性规划原问题转化为对偶问题的一般规律。,原问题线性规划模型,对偶线性规划模型,对偶线性规划,11,原问题为maxZ的线性规划问题对偶关系表,对偶线性规划,12,原问题对偶问题目标函数max 目标函数min,原问题(maxZ)与对偶之关系,原问题(maxZ)口诀:约束决定变量是反号,原问题(maxZ)口诀:变量决定约束是同号,对偶线性规划,13,【解】,由原模型三个约束条件确定对偶模型有三个变量y1,y2,y3,（还可依对偶问题写出原问题）,【例1】写出下列问题的对偶问题：,变量决定约束是同号,约束决定变量是反号,min w=15y1+24y2+5y3,6y2+y3 2,s.t.,y1 0,y2 0,y3 无约束,5y1+2y2+y3 1,对偶线性规划,14,原问题为minS的线性规划问题对偶关系表,对偶线性规划,15,原问题对偶问题目标函数min 目标函数max,原问题(minS)与对偶之关系：,原问题(minS)口诀:约束决定变量是同号,原问题(minS)口诀:变量决定约束是反号,对偶线性规划,16,【解】,由原模型三个约束条件确定对偶模型有三个变量y1,y2,y3,s.t.,（还可依对偶问题写出原问题）,【例2】写出下列问题的对偶问题：,s.t.,1,3,2,1,+,-4,x,x,2x,x10,x20,x3无约束,变量决定约束是反号,约束决定变量是同号,对偶线性规划,17,练习：试求下列线性规划问题的对偶问题,对偶线性规划,练习：试求下列线性规划问题的对偶问题,答案：,s.t.,，,对偶线性规划,变量决定约束是同号,约束决定变量是反号,练习：试求下列线性规划问题的对偶问题,maxZ=5y1+4y2+6y3 y1+2y2 2 y1+2y2+y3 3-3y1+y3-5 y1-y2+y31 y1 0,y2,y3 0,答案：,对偶线性规划,变量决定约束是反号,约束决定变量是同号,原问题目标函数max,原问题(minS)与对偶之关系符号小结,同号,变量,对偶线性规划,约束,反号,约束,变量,对偶问题目标函数min,21,线性规划的对偶理论包括以下几个基本定理。,定理1（对称性定理）,2.2 线性规划的对偶理论,定理2（弱对偶定理）,即对偶问题的对偶是原问题。,设x和y分别是原问题和对偶问题的可行解，则必有cxyb，即原问题的目标值小于对偶问题的目标值,对偶线性规划,22,定理3（无界性）,若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。,反之，若原（对偶）问题有可行解,对偶（原）问题无可行解，则原（对偶）问题一定无界；,定理4（可行解是最优解的性质）,定理5（强对偶定理）,设X*是原问题的可行解，Y*是对偶问题的可行解，当CX*=Y*b时，X*与Y*是最优解。,若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等,一般是：cxyb,对偶线性规划,23,综上所述：原问题与对偶问题解的对应关系,由原问题与对偶问题的解的关系可以判定线性规划的解。,对偶线性规划,24,Min w=2y1+y2 S.t.y1 2y2 1 y1+y2 1 y1 y2 0 y1,y2 0,应用如上关系求解线性规划问题,试用对偶理论证明上述规划问题无最优解。,由第一约束条件可知对偶问题无可行解，则原问题的解无界或无可行解，由于原问题存在可行解，所以解无界。,解 该问题存在可行解，如X=(0，0，0)；,其对偶问题为：,对偶问题无可行解,对偶线性规划,25,定理6（互补松弛定理）,在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。,注：证明过程参见教材59页性质5证明,对偶线性规划,26,【讨论】,互补松弛定理也称松紧定理，它描述了线性规划达到最优时，原问题（或对偶问题）的变量取值和对偶问题（或原问题）约束松紧之间的对应关系。当线性规划问题达到最优时，我们不仅同时得到了原问题和对偶问题的最优解，而且也还得到了变量和约束之间的一种对应关系。互补松弛定理即揭示了这一点。,对偶线性规划,27,线性规划达到最优时的关系：,1.如果原问题的某一约束为紧约束（严格等式:松弛变量为零），该约束对应的对偶变量应大于或等于零；,2.如果原问题的某一约束为松约束（严格不等式:松弛变量大于零），则对应的对偶变量必为零；,3.如果原问题的某一变量大于零该变量对应的对偶约束必为紧约束(严格等式)；,4.如果原问题的某一变量等于零，该变量对应的对偶约束可能是紧约束(严格等式)，也可能是松约束(严格不等式)。,对偶线性规划,28,【又例】应用如上关系求解线性规划问题,22,1/5 3,17/55,7/5 2,3=3,解：写出对偶问题为：Max Z=4y1+3y S.t.y1+2y2 2 y1 y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3 y1,y2 0,已知对偶问题的最优解为 y1=4/5,y2=3/5,试应用对偶理论求解原问题。,x2=0,x3=0,x4=0,等号,又因y1,y2 0，故原问题的两个约束必为紧约束，即,解得：x1=x5=1。,maxZ=5=minS=5,得原问题的最优解X*=(1,0,0,0,1)minS=5,对偶线性规划,29,【练习】已知线性规划问题为：,Max.Z=2x1+4x2+x3+x4 s.t.x1+3x2+x48 2x1+x2 6 x2+x3+x46 x1+x2+x3 9 xj0（j=1,2,3,4）,附 练习答案：y1=4/5,y2=3/5,y3=1,y4=0,已知原问题的最优解为:X*=(2,2,4,0)T，试根据互补松弛定理解出其对偶问题的最优解。,线性规划问题的对偶问题为：Min.Z=8y1+6y2+6y3+9y4 s.t.y1+2y2+y4 2 3y1+y2+y3+y4 4 y3+y4 1 y1+y3 1 yj0（j=1,2,3,4）,对偶线性规划,30,为严格不等式，由互补松弛定知，必有y4=0；,Max Z=2x1+4x2+x3+x4 s.t.x1+3x2+x48 2x1+x2 6 x2+x3+x46 x1+x2+x3 9 xj0（j=1,2,3,4）,8=8,6=6,6=6,89,解之，有：y1=4/5,y2=3/5,y3=1，y4=0,答案：因为原问题的最优解为:X*=(2,2,4,0)T：,又因x1,x2,x30，故对偶问题的前三个约束必为紧约束,线性规划问题的对偶问题为：MinS=8y1+6y2+6y3+9y4 s.t.y1+2y2+y4 2 3y1+y2+y3+y4 4 y3+y4 1 y1+y3 1 yj0（j=1,2,3,4）,等号,对偶线性规划,maxZ=16=minS,得对偶问题的最优解Y*=(4/5,3/5,1,0)minS=16,31,【练习】已知线性规划问题,（1）写出对偶问题；（2）已知原问题的最优解为X*=（2，0，1，1）T，求对偶问题的最优解。,对偶线性规划,32,问题：可否用单纯型法求解原问题的同时求对偶问题的解,结论：用单纯形法求解线性规划时，迭代的每一步在得到原问题一个基本可行解的同时，其：,线性规划原问题及其对偶问题之间存在一对互补的基解，其中原问题的松驰变量对应对偶问题的原变量，对偶问题的剩余变量对应原问题的原变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这两个解代入各自的目标数中有 z=w。,注：证明过程参见教材60页性质6证明,检验数行的-(cj-zj)值是其对偶问题的一个基本解yi；,定理7,对偶线性规划,33,用单纯形法同时求解原问题和对偶问题,原问题是：,maxZ=2x1+x2 5x2 15 6x1+2x2 24 x1+x2 5 x1,x2 0,原问题的标准型是：,maxZ=2x1+x2+0 x3+0 x4+0 x5 5x2+x3=15 6x1+2x2+x4=24 x1+x2+x5=5 xi 0,对偶线性规划,34,maxZ=2x1+x2+0 x3+0 x4+0 x5 5x2+x3=15 6x1+2x2+x4=24 x1+x2+x5=5 xi 0,原问题变量,原问题松驰变量,对偶问题剩余变量y4、y5,对偶问题变量y1、y2、y3,得原问题可行解:X=(0,0,15,24,5)T,对偶问题解:Y*=(0,0,0,-2,-1)T,检验数行的(cj-zj)值是其对偶问题的一个基本解yi；,对偶线性规划,35,得原问题可行解:X=(4,0,15,0,1)T，此时Z=8,同时得对偶问题基础解:Y*=(0,1/3,0,0,-1/3)T，W=8,检验数行的-(cj-zj)值是其对偶问题的一个基本解yi；,对偶线性规划,36,变换单纯形表,此时得原问题最优解:X*=(7/2,3/2,15/2,0,0)T，Z*=17/2,原问题变量,原问题松驰变量,对偶问题剩余变量y4、y5,对偶问题变量y1、y2、y3,则对偶问题最优解:Y*=(0,1/4,1/2,0,0)T，S*=17/2,检验数行的-(cj-zj)值是其对偶问题的一个基本解yi；,对偶线性规划,37,【又例】用单纯形法同时求解原问题和对偶问题,maxZ=100 x1+80 x2 2 x1+4 x2 80 3 x1+x2 60 x1,x2 0,将线性规划问题标准化,maxZ=100 x1+80 x2+0 x3+0 x4 2 x1+4 x2+x3=80 3 x1+x2+x4=60 x1,x2 x3 x4 0,对偶线性规划,38,此时得原问题的最优解：X0=(16,12,0,0)T,maxZ=2560,初等变换,2 x1+4 x2+x3=80 3 x1+x2+x4=60-Z+100 x1+80 x2+0 x3+0 x4=0,-Z x1 x2 x3 x4 b,同时得对偶问题的最优解：y1=14,y2=24,y3=0,y4=0,即Y0=(14,24,0,0)T,minS=2560,对偶线性规划,39,2.3 对偶单纯形方法,原问题是：,原问题的标准型是：,maxw=-15y1-24y2-5y3+0y4+0y5 6y2+y3-y4=25y1+2y2+y3-y5=1 y1,y2,y3,y4,y5 0,利用单纯形法：,maxw=-15y1-24y2-5y3+0y4+0y5-My6-My7 6y2+y3-y4+y6=25y1+2y2+y3-y5+y7=1 y1,y2,y3,y4,y5,y6,y7 0,对偶线性规划,40,一、用对偶单纯形方法解线性规划,对偶单纯形方法是使用对偶原理求解原问题解的一种方法，而不是求解对偶问题解的单纯形方法。与对偶单纯形方法相对应，原已有的单纯形方法称原始单纯形方法。,对偶线性规划,41,【例】用对偶单纯形方法解下述线性规划问题,原问题是：,原问题的标准型是：,maxw=-15y1-24y2-5y3+0y4+0y5 6y2+y3-y4=25y1+2y2+y3-y5=1 y1,y2,y3,y4,y5 0,maxw=-15y1-24y2-5y3+0y4+0y5-6y2-y3+y4=-2-5y1-2y2-y3+y5=-1 y1,y2,y3,y4,y5 0,对偶单纯形方法,对偶线性规划,42,maxw=-15y1-24y2-5y3+0y4+0y5-6y2-y3+y4=-2-5y1-2y2-y3+y5=-1 y1,y2,y3,y4,y5 0,最优解:Y*=(0,1/4,1/2,0,0)T，maxw*=-17/2,MinZ=17/2,对偶线性规划,43,应用对偶单纯形方法之矩阵法,maxw=-15y1-24y2-5y3+0y4+0y5-6y2-y3+y4=-2-5y1-2y2-y3+y5=-1 y1,y2,y3,y4,y5 0,最优解:Y*=(0,1/4,1/2,0,0)T，max w*=-17/2 Min Z=17/2,对偶线性规划,44,两种方法的主要区别在于：,而对偶单纯形方法在整个迭代过程中，则是始终保持对偶问题的可行性即 亦即,，也就是全部检验数0，最后达到全部右边项所有负分量逐步变为全部右边项0,即满足原问题的可行性时为止。,所以,对偶单纯形方法实质就是在保证对偶问题可行的条件下向原问题可行的方向迭代。,原始单纯形方法在整个迭代过程中，始终是保持原问题的可行性，最后达到检验数 即 即maxZ取得最优值时为止。,相当于：直到对偶问题的解可行为止,相当于：即直到原问题的解可行为止,对偶线性规划,45,【例】用对偶单纯形方法解下述线性规划问题,原问题是：,原问题的标准型是：,maxZ=-2x1-3x2-4x3+0 x4+0 x5 x1+2x2+x3-x4=32x1-x2+3x3-x5=4 x1,x2,x3,x4,x5 0,maxw=-2x1-3x2-4x3+0 x4+0 x5-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4 x1,x2,x3,x4,x5 0,对偶线性规划,46,应用对偶单纯形方法之矩阵法,最优解:Y*=(11/5,2/5,0,0,0)T，Maxw=-28/5,maxw=-2x1-3x2-4x3+0 x4+0 x5-x1-2x2-x3+x4=-3-2x1+x2-3x3+x5=-4 x1,x2,x3,x4,x5 0,MinZ*=28/5,对偶线性规划,47,小结：对偶单纯形方法的解题过程一般分为四步,（1）写出与已有的初始基B对应的初始单纯形表。根据模型的标准型，若右边项的数字都为非负，且检验数都为非正，则已得到最优解，计算结束；否则，若右边项中至少有一个负分量，且检验数也仍然非正，则进行如下计算。,（2）确定出基变量。若有：则以对应的变量 xr为出基变量。,（3）确定入基变量。在单纯形表中观察xr所在行的各系数arj，若所有的arj0，则无可行解，停止计算；否则若存在：,，则以xk为入基变量。,（4）以ark为主元按原始单纯形方法的迭代方法进行迭代，得到新的单纯形表。,对偶线性规划,48,对偶单纯形方法的显著优点：,（1）初始解可以是不可行解，当检验数都非正时，即可以进行基的变换，这时不需要引进人工变量，因此就简化了计算。,（2）对于变量个数多于约束方程个数的线性规划问题，采用对偶单纯形法计算量较少。因此对于变量较少、约束较多的线性规划问题,可以先将它转化成对偶问题，然后用对偶单纯形方法求解。,对偶线性规划,49,【另例】用对偶单纯形方法解下述线性规划问题,原问题是：,原问题的标准型是：,maxZ=-9x1+7x2-4x3+0 x4+0 x5 5x1+x2+7x3+x4=5 3x1+4x2+8x3=4 2x1+6x2+8x3-x5=6 x1,x2,x3,x4,x5 0,maxZ=-9x1+7x2-4x3+0 x4+0 x5 5x1+x2+7x3+x4=5 3x1+4x2+8x3=4-2x1-6x2-8x3+x5=-6 x1,x2,x3,x4,x5 0,对偶线性规划,50,此时最优，最优解:Y*=(0,1,0,4,0)T，MaxZ=7,MinZ=-7,对偶线性规划,【练习】用对偶单纯形方法解下述线性规划问题,对偶线性规划,52,2.4 影子价格,从对偶问题的基本性质可以看出，在单纯形法的每步迭代中有目标函数,此时的估价不是市场价格，而是根据资源在生产中的贡献而作的估价。此时的定价区别于市场价格称为影子价格。,对偶线性规划,第i种资源的估价,第i种资源的拥有量,影子价格的意义,1、市场价格主要随市场供求变化；而它的影子价格有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。同样一种资源，若它们在不同企业中发挥的作用不同，对这种资源所做的估价也不同，即影子价格也不同。即：生产任务、结构的改变会影响影子价格。,对偶线性规划,54,2、影子价格是一种边际价格。,yi代表bi每增加一个单位，目标函数z的增量,+1,（1）z*=42 不变，A的边际价格为0,+1,（2）x*=(10/3,13/2)z*=42.5，B的边际价格为0.5,+1,（3）x*=(13/3,6)z*=43，C的边际价格为1,对偶线性规划,影子价格越大，说明这种资源越是相对紧缺，影子价格越小，说明这种资源相对不紧缺。,55,3、资源的影子价格实际上是一种机会成本。市场价格低于影子价格时，企业的决策者应买进资源用于扩大再生产；当某种资源的市场价格高于企业影子价格时，企业的决策者应把已有资源卖掉，以其获得更大的利润。随着资源的买进和卖出，它的影子价格也随之发生变化。,4、生产过程中，如果某种资源bi未得到充分利用时，该种资源的影子价格为0；某种资源的影子价格不为0时，表明该种资源已经耗尽。,由对偶互补松弛定理即可说明,对偶线性规划,对偶线性规划,【例】某工厂准备安排甲、乙、丙三种产品的生产，需要消耗原材料A和B两种资源。为了确定利润最大的生产计划，建立下列线性规划：,其中x1,x2,x3表示甲、乙、丙的产量，经计算得到下列最终单纯形表（x4,x5是松弛变量）。,57,对偶线性规划,根据以上资料，回答下列问题：（1）写出对偶问题的最优解和最优目标函数值；（2）求出原材料B的影子价格。若原材料B不够，可到市场上购买，市场价格为0.8元/单位。问是否要购进？,解：（1）根据对偶问题的基本性质7，最终单纯形表中原问题加入的松弛变量检验数的相反数对应于对偶问题的最优解。,所以，对偶问题的最优解是,最优目标函数值是,（2）原材料B的影子价格是1，所以以0.8元/单位的价格购进原材料B是值得的。,58,灵敏度分析，是指对系统或事物因周围条件变化所表现出的敏感性程度的分析。,在前面讲的线性规划问题中，通常都是假定问题中的aij，bi，cj系数是已知的常数,但实际上这些参数都是一些估计或预测的数字。在现实中，如果市场条件变化，cj值就会发生变化；如果工艺技术条件改变，则aij就会变化；如果资源的可用量发生变化，则bi也会发生变化。,2.5 灵敏度分析,问题：1、参数发生变化时，问题的最优解会有什么变化？2、参数多大的范围内变化时,原最优解保持不变。,对偶线性规划,59,解决方法：,1、当参数变化时，用单纯形法从头计算，看最优解有无变化，但这样做既麻烦又没有必要。2、把个别参数的变化直接在获得最优解的最终单纯形表上反映出来。这样就不需要从头计算，而只需对获得最优解的单纯形表进行审查，看一些数字变化后是否仍满足最优解的条件,如果不满足的话,再从这个表开始进行迭代计算，求得最优解即可。这也就是灵敏度分析。,对偶线性规划,60,灵敏度分析的步骤如下：,1.将参数的改变计算反映到最终单纯形表上来,b*=B-1 b,具体计算方法是，按下列公式计算出由参数aij、bi、cj的变化而引起的最终单纯形表上有关数字的变化：,Pi*=B-1 Pi,s*=c,2.检验原问题是否仍为可行解；即右端常数是否大于0,3.检验对偶问题是否仍为可行解；即检验数是否小于0,4.按下表所列情况得出结论和决定继续计算的步骤。,常数项bi的改变量,系数aij的改变量,目标函数系数cj的改变量,对偶线性规划,此公式是单纯形法利用公式求解的推导结果!,61,解的情况判定表,对偶线性规划,62,一、分析cj变化的影响,目标函数中的系数cj的变化仅仅影响到检验数(cj-zi)的变化。所以将cj 的变化直接反映到最终单纯形表中，只可能出现表中的前两种情况。,【例】已知线性规划问题：,maxZ=2x1+x2 5x2 15 6x1+2x2 24 x1+x2 5 x1,x2 0,用单纯形法求得最终单纯形表如下,对偶线性规划,63,最终单纯形表,试确定：(a)当目标函数变为max Z=5x1+1.5x2时，最优解会出现什么变化；,(b)目标函数变为max Z=(2+l)x1+x2时，l在什么范围变化，最优解不变；,maxZ=2x1+x2 5x2 15 6x1+2x2 24 x1+x2 5 x1,x2 0,maxZ=5x1+1.5 x2 5x2 15 6x1+2x2 24 x1+x2 5 x1,x2 0,对偶线性规划,64,【解】,(a)将目标函数系数的变化直接反映到最终单纯形表中,变量x5的检验数为正，继续迭代；,maxZ=5x1+1.5 x2 5x2 15 6x1+2x2 24 x1+x2 5 x1,x2 0,对偶线性规划,65,继续迭代得下表,即得新最优解x1=4，x2=0，x3=15，x4=0，x5=1,此时MaxZ=20,对偶线性规划,66,(b)将目标函数系数的变化直接反映到最终单纯形表中,为使表中解为最优，应该有,-1/4-1/4l0，-1/2+1/2l0,即得：-1 l1,即：-1 l1时，最优解不变；,对偶线性规划,二、分析bi变化的影响,bi的变化在实际问题中表明可用资源的数量发生变化，其变化b反映到最终单纯形表上只引起基变量列数字变化b*。因此灵敏度分析的步骤为：,1.由b*=B-1b算出b*，将其加到最终表基变量列的数字上；,2.由于其对偶问题仍为可行解（检验行没变），故只需检查原问题是否仍为可行解，再按相应步骤进行。,注:此公式是单纯形法利用公式求解的推导结果!,问题：B与B-1分别是什么？,对偶线性规划,以此题为例讨论B-1的求法,初始单纯形表,最终单纯形表,B,B-1,原理是：(B|I)经过初等变换可化为(I|B-1)，其中I是单位阵,I,I,对偶线性规划,【另例】求B-1,初始单纯形表,B*,B-1,I*,I,对偶线性规划,【另例】求B-1,初始单纯形表,对偶线性规划,最终单纯形表,71,【例】分析bi变化的影响,最终单纯形表,(a)若第2个约束条件右端项由24增大到32，分析最优解变化；,(b)若第2个约束条件变为 6x1+2x224+l，分析l在什么范围内变化，最优不变；,maxZ=2x1+x2 5x2 15 6x1+2x2 24 x1+x2 5 x1,x2 0,maxZ=2x1+x2 5x2 15 6x1+2x2 32 x1+x2 5 x1,x2 0,对偶线性规划,72,【解】(a)第2个约束条件右端项由24增大到32,因,因表中原问题为非可行解，故用对偶单纯形法继续计算,将其加到最终单纯形表的基变量b这一列上得下表,注：B-1扩充了检验行，反映目标值的变化,b*=B-1b,15/2+107/2+23/2-2-17/2-2,35/211/2-1/2-21/2,B-1,对偶线性规划,73,继续迭代得下表,最优值 maxz*=10,即得新最优解 x1=5，x2=0，x3=15，x4=2，x5=0,对偶线性规划,74,【解】(b)若第2个约束条件变为 6x1+2x224+l,因,将其加到最终单纯形表的基变量b这一数列上得下表,15/2+5l/47/2+l/43/2-l/4-17/2-l/4,15/2+5/4l0 l-6,7/2+1/4l0 l-14,3/2-1/4l0 l6,得-6 l 6,即：-6 l6时，最优解不变；,对偶线性规划,75,三、增加一个变量的分析,增加一个变量在实际问题中反映为增加一种新的产品。分析步骤是：,1.计算新变量最终表检验数 sj=cj-zi=cj y*Pj,2.计算新变量最终表约束函数系数向量 Pj*=B-1Pj,3.判定：若sj0，只需将Pj和sj 的值直接反映到最终单纯形表中，原最优解不变；若sj0，则按单纯形法继续迭代计算。,其中cj 是新变量目标函数系数,Pi是新变量约束函数系数，y*是对偶问题的解,对偶线性规划,76,最终单纯形表,【例】上例中,若增加一个变量x6，已知c6=3,P6=(3,4,2)T，试分析最优解的变化。,maxZ=2x1+x2 5x2 15 6x1+2x2 24 x1+x2 5 x1,x2 0,maxZ=2x1+x2+3 x6 5x2+3x6 15 6x1+2x2+4x6 24 x1+x2+2x6 5 x1,x2,x6 0,对偶线性规划,77,【解】,将其反映到最终单纯形表中得下表,因s6=10,故用单纯形法继续计算,增加变量x6，已知c6=3,P6=(3,4,2)T，试分析最优解的变化。,检验数sj=cj-zi=cj y*Pj，Pj*=B-1Pj,对偶线性规划,78,继续迭代得下表,由此得新的解为,x1=7/2，x2=0，x3=51/4，x4=0，x5=0，x6=3/4，Max z*=37/4,对偶线性规划,79,四、分析aij变化的影响,假如xj在最终表中为基变量，则aij的变化将使最终表中的B-1变化，因此有可能出现原问题与对偶问题均为非可行解的情况。,【例】上例中，若c2=3，x2的系数向量变为P2=(8，4，1)T，试分析最优解的变化。,maxZ=2x1+x2 5x2 15 6x1+2x2 24 x1+x2 5 x1,x2 0,maxZ=2x1+3x2 8x2 15 6x1+4x2 24 x1+x2 5 x1,x2 0,对偶线性规划,80,11/21/21/2 3/2,对偶线性规划,【解】同上例,maxZ=2x1+3x2 8x2 15 6x1+4x2 24 x1+x2 5 x1,x2 0,81,继续迭代得下表,因原问题与其对偶问题均为非可行解，通过引入人工变量将原问题转化为可行解，再用单纯形法继续计算。将第一行x3+4x4-24x5=-9 化为标准型-x3-4x4+24x5=9,再加上人工变量 x3 4x4+24x5+x6=9,对偶线性规划,82,因s5 0,故用单纯形法迭代计算,x34x4+24x5+x6=9,对偶线性规划,83,继续迭代得下表,新的最优值为maxz*=89/8,得到新最优解：x1=11/4，x2=15/8，x3=0，x4=0，x5=3/8，x6=0,对偶线性规划,84,五、增加一个约束条件的分析,增加一个约束条件，在实际问题中相当于增添一道工序。分析的方法是先将原来的问题的最优解变量取值代入这个新增的约束条件中，如满足，说明新增约束未起到限制作用，原最优解不变。否则，将新增约束直接反映到最终表中，再进行分析。,【例】上例中，新增添一个约束条件 3x1+2x2 12，试分析最优解的变化。,【解】先将原问题最优解x1=7/2,x2=3/2代入新约束条件，因有,故将约束条件写成3x1+2x2+x6=12，并取x6为基变量，直接反映到最终表中,37/2+23/2=27/212,maxZ=2x1+x2 5x2 15 6x1+2x2 24 x1+x2 5 3x1+2x2 12 x1,x2 0,对偶线性规划,85,得下表,x1与x2的向量不是单位向量，要继续变换,对偶线性规划,3x1+2x2 12 3x1+2x2+x6=12,86,得下表,用对偶单纯形法迭代继续变换,对偶线性规划,87,得下表,新的最优值为max z*=8,得新的最优解为：x1=4，x2=0，x3=15，x4=0，x5=1，x6=0，,对偶线性规划,88,2.7 参数线性规划,参数aij、bi、cj在什么范围内变化时最优解不变是实际问题中常常要研究的问题，当这些参数超出这个范围时，最优解会发生怎样的变化，即为参数线性规划要研究的问题。,【例】线性规划问题,maxZ(l)=2x1+x2 5x2 15 6x1+2x2 24 x1+x2 5+l x1,x2 0,第三个约束右端不断增大，分析最优解会发生怎样的变化？,此时l 0,对偶线性规划,89,参数线性规划求解步骤,1、令l=0求解得最终单纯形表,2、将参数的变化反映到最终单纯形表中；因,对偶线性规划,90,反映到最终单纯形表中,3、让 l逐步增大，观察原问题与对偶问题解的变化，看哪一个首先出现非可行解。,15/2-(15/2)l0,x1=7/2-(1/2)l,x2=3/2+(3/2)l,Z*=17/2+(1/2)l,7/2-(1/2)l0,3/2+(3/2)l0,当0l1 表中解为最优解。此时,对偶线性规划,91,当 l1时，用对偶单纯形法迭代,注：不用讨论7/2-(1/2)l0的情况，因为此时，15/2-(15/2)l也是负的，且绝对值更大。因此出基项仍然是x3（第一行）。,对偶线性规划,92,当 l继续增大，原问题与对偶问题都保持可行解，故计算至此结束。,结论：01,x1=3,x2=3,maxZ=9,对偶线性规划,93,【图示】目标函数Z(l)与l的变化关系图,9,l1,Z=17/2+(1/2)l,l1,Z=9,注：问题中多个参数变化时，应使目标函数z(l)是l的线性函数。,对偶线性规划,94,【例】求解下述参数线性规划问题,maxZ=（2+l)x1+(1+2l)x2 5x2 15 6x1+2x2 24 x1+x2 5 x1,x2 0,【解】按参数线性规划求解问题的第一、二步，令l=0 求得最优解，并将cj的变化值反映到最终单纯形表中。,对偶线性规划,95,反映到最终单纯形表中,当-1/5l1时，表中解为最优解。此时,当l1，变量x4的检验数为正值，用单纯形法继续迭代得,z*=7/2(2+l)+3/2(1+2l)=17/2+13l/2,-1/4+l/40,-1/2-5l/2 0,-1/5l1,当l-1/5，变量x5的检验数为正值，用单纯形法继续迭代得,对偶线性规划,96,当l1，原问题与对偶问题都保持可行解，故计算至此结束。,工厂的最优计划为x1=2，x2=3，z*=2(2+l)+3(1+2l)=7+8l,当l1，变量x4的检验数为正值，用单纯形法继续迭代得,97,当l-1/5时,当 l-1/5时，变量x5的检验数为正值，用单纯形法继续迭代得,对偶线性规划,98,当l-1/5，变量x5的检验数为正值，用单纯形法继续迭代得,当-2l-1/5，原问题与对偶问题都保持可行解，故计算至此结束。,工厂的最优计划为x1=4，x2=0，x3=15，z*=4*(2+l)=8+4l,1/3+5/3l 0,-1/3-1/6l 0,-2l-1/5,l-2,Z(l)8+4l0没必要讨论,对偶线性规划,99,【图示】目标函数Z(l)与l的变化关系图,-1/5,对偶线性规划,当-1/5l1时，z*=17/2+13l/2,当l1，z*=7+8l,当-2l-1/5，z*=8+4l,100,【例】,某文教用品厂利用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人，每天白坯纸供应量为3万kg。如果单独生产各种产品时，每个工人每天生产原稿纸30捆，或日记本30打，或练习本30箱。书籍原材料消耗为：每捆原稿纸用白坯纸10/3kg，每打日记本用白坯纸40/3kg，每箱练习本用白坯纸80/3kg。又知每生产一捆原稿纸可盈利2元，每生产一打日记本可盈利3元，每生产一箱练习本可盈利1元。试决定：（1）在现有生产条件下工厂盈利最大的生产方案；（2）如果白坯纸的供应数量不变，当工人人数不足时，可招收临时工，临时工工资支出为每人每天40元，问该厂要不要招收临时工，招多少人？,对偶线性规划,101,【解】由已知条件得,maxZ=2x1+3x2+x3 1/30 x1+1/30 x2+1/30 x3 100 10/3x1+40/3x2+80/3x3 30000 x1,x2,x3 0,设该厂每天生产原稿纸x1捆，日记本x2打，练习本x3箱。则上述问题的参数规划模型为：,（1）在现有生产条件下工厂求盈利最大的生产方案,对偶线性规划,102,计算过程,maxZ=2x1+3x2+x3 10/3x1+40/3x2+80/3x3 30000 1/30 x1+1/30 x2+1/30 x3 100,x1=1000,x2=2000，maxz=8000,对偶线性规划,103,0l200,l200,Z=8000+10l,Z=18000-40l,所以该厂最多招收200名临时工,当且仅当l=200时，Z最大,maxZ=2x1+3x2+x3-40l10/3x1+40/3x2+80/3x3 300001/30 x1+1/30 x2+1/30 x3100+l,2000-10l1000+40l-8000+40l-50l,（2）用l表示招收的临时工数，则上述问题的参数规划模型为：,104,【图示】目标函数Z(l)与l的变化关系图,0l 200,Z=8000+10l,l200,Z=18000-40l,对偶线性规划,