第三章 对偶理论和灵敏度分析(第1-5节).ppt

1、第1页,第三章,对偶理论和灵敏度分析,第2页,第一节 单纯形法的矩阵描述 第二节 改进单纯形法 第三节 对偶问题的提出 第四节 原问题-对偶问题的关系 第五节 对偶问题的基本性质 第六节 对偶问题的经济解释 第七节 对偶单纯形法 第八节 灵敏度分析 第九节 参数规划,第3页,第一节 单纯形法的矩阵描述,掌握用矩阵描述单纯形法计算过程的作用： 有助于加深对单纯形法的理解。 有助于下面对偶理论和灵敏度分析的学习。,第4页,从而线性规划问题的标准型,第5页,当前单纯形表中的右端常数,当前单纯形表中的非基变量系数列向量,当前单纯形表中的基变量系数列向量总是单位向量,第6页,max z = 2x1 +

2、3x2,例：,解：,max z = 2x1 + 3x2,第7页,已知最终单纯形表中的基变量为 xB=( x1 , x5 , x2 )，则可以直接计算出最终单纯形表中的系数列向量：,当前单纯形表中的非基变量系数列向量,第8页,已知当前单纯形表中的基变量为 xB=( x1 , x5 , x2 )，则可以直接计算出当前单纯形表中的基变量的值：,当前单纯形表中的基变量的值（即右端常数）,第9页,最终单纯形表的形式为：,第10页,将 XB 表达式带入目标函数：,最优目标函数值,第11页,非基变量检验数,基变量检验数,所有检验数：,第12页,已知最终单纯形表中的基变量为 xB=( x1 , x5 , x2

3、 )，则可以直接计算出最终单纯形表中的检验数：,第13页,最终单纯形表：,第14页,总 结 从任一单纯形表（不一定是初始单纯形表）出发，只要能够知道当前单纯形表中的哪几个变量是基变量，就可以直接计算出当前单纯形表。,（1）约束条件系数矩阵：,（2）约束条件右端常数：,（3）检验数：,第15页,只要能够知道当前单纯形表中的哪几个变量是基变量，就可以由初始单纯形表直接计算出当前单纯形表。 要确定当前单纯形表中哪几个变量是基变量，必须要解决的问题： （1）换入变量的确定。 （2）换出变量的确定。,第16页,（1）换入变量的确定,计算所有变量检验数：,（2）换出变量的确定,换入变量：x k,换出变量：

4、x l,第17页,第18页,由此可以看出，B -1 的计算是整个问题的关键,第19页,max z = 2x1 + 3x2,例：,第20页,解：（1）从初始单纯形表出发。,1,2,第21页,3,4,第22页,2,4,（2）从任一单纯形表（非初始单纯形表）出发。,第23页,第24页,例：,第25页,解：加入 松弛变量： x4 剩余变量： x5 人工变量： x6 和 x7 得到：,第26页,第27页,第28页,由此可以看出，当前单纯形表中基变量所对应的B-1 等于在出发单纯形表中，系数列向量为单位向量的变量在当前单纯形表中所对应的列向量组成的矩阵。,第29页,例 已知某最大化线性规划问题用单纯形法求

5、解时的初始单纯形表及最终单纯形表如下表所示，求表中各括号内未知数的值。,第30页,第31页,解：因为基变量所对应的系数列向量为单位向量，故 l = 1 。显然，k = 0。 下面，关键是求 B -1 。,第32页,第33页,第34页,第35页,第36页,第37页,最后可计算出：g = -3/4 。,第38页,例 已知某线性规划问题，用单纯形法计算时得到中间某两步的计算表如下表，试将表中空白处数字填上。,第39页,第40页,解：,1 0 0,8/41 50/41 44/41,0 1 0,0 0 1,第41页,第二节 改进单纯形法,（1）确定初始基变量，并计算初始可行基的逆矩阵B -1 ； （2）

6、检验各非基变量的检验数： 如果j 0，j = m+1, . , n ，则当前解就是最优解，最有解为 B-1b ，停止计算：,第42页,否则 ，转下步；,如果j 0，j = m+1, . , n ，则当前解为唯一最优解； 如果有j ，j = m+1, . , n 中有j = 0，则当前解是最优解，但不唯一，问题有无穷多最优解。,第43页,（3）在 j 0 ，j = m+1, . , n 中，若某个非基变量 xj 的系数列向量 Pk 0，则此问题无界，停止计算，否则转下步；,（4）根据max( j 0 ) = k，来确定 x k 为换入变量（最大检验数有多个时，可任选一个）；,第44页,（5）根据

7、下式来确定 x l 为换出变量：,最小比值有多个时（下一步迭代会出现非基变量 = 0的情况，即退化现象），可任选一个（通常选择下标较小的那个基变量 x l 换出）。,（6）从而确定新的基变量，计算新的可行基的逆矩阵 B -1 。 （7） 重复（2）（6），直到找到问题的最优解。,第45页,max z = 2x1 + 3x2,例：,第46页,解：,max z = 2x1 + 3x2,（1） XB=( x3 , x4 , x5 ),第47页,第48页,（2） XB=( x3 , x4 , x2 ),第49页,（3） XB=( x1 , x4 , x2 ),第50页,（4） XB=( x1 , x5

8、 , x2 ),第51页,第三节 对偶问题的提出,对偶是指对同一问题，从不同角度观察，有两种对立的表述。,一、对偶的定义,周长一定，面积最大的矩形是正方形。,面积一定，周长最小的矩形是正方形。,第52页,正方形,非线性规划,第53页,正方形,非线性规划,第54页,二、对偶问题的提出,问题1 某工厂有 I、II 两种产品，已知生产单位产品所需的设备台时数、原材料 A 的消耗量、原材料B的消耗量，具体数据如表所示。,每生产一件产品 I 可获利 2 元，每生产一件产品 II 可获得3元，问如果自己生产，产品 I 和 II 各应生产多少获利最大？,第55页,又知道，每生产一件产品 I 可获利 2 元，

9、每生产一件产品 II 可获得 3 元，问应如何安排生产计划才能够使得工厂获利最多？,第56页,问题2 某工厂有 I、II 两种产品，已知生产单位产品所需的设备台时数、原材料 A 的消耗量、原材料B的消耗量，具体数据如表所示。,每生产一件产品 I 可获利 2 元，每生产一件产品 II 可获得 3 元，问如不自己生产，而是将设备、原材料 A、原材料 B 等三种资源卖出，定价多少才能将资源卖出？,第57页,设设备台时数售价：y1 资源 A 售价：y2 资源 B 售价：y3,生产产品 I 所需的各种资源的售价总和，不应低于自己生产产品 I 所带来的利润：,生产产品 II 所需的各种资源的售价总和，不应

10、低于自己生产产品 II 所带来的利润：,第58页,从工厂角度来看：越大越好； 从接受者角度来看：越小越好。 所以，工厂只能在满足大于等于自己生产产品所带来的利润的条件下，提出一个尽可能低的出售价格，才能实现其意愿，因此问题的目标函数是极小化。,卖出的总收入为：,第59页,第60页,第61页,第四节 原问题-对偶问题的关系,一、线性规划问题的对称形式,满足下列条件的线性规划问题称为具有对称形式： （1）决策变量满足非负要求。 （2）当目标函数为极大化时，约束条件为。 （3）当目标函数为极小化时，约束条件为。,第62页,原问题,1. 对称形式下原问题-对偶问题的完整表述式：,第63页,对偶问题,第

11、64页,原问题,2. 对称形式下原问题-对偶问题的简化表述式：,第65页,对偶问题,第66页,对偶问题,原问题,3. 对称形式下原问题-对偶问题的矩阵表述式：,第67页,二、对称形式原问题-对偶问题的转化,第68页,第69页,对称形式原问题-对偶问题的转化步骤,（1）max min。 （2）对偶问题的决策变量数 = 原问题的约束条件数。 （3）对偶问题的目标函数系数 = 原问题的约束条件右端常数。 （4）对偶问题的约束条件系数矩阵 = 原问题约束条件系数矩阵的转置矩阵。,第70页,（5）对偶问题的约束条件右端常数 = 原问题的目标函数系数。 （6）约束条件符号：极大化问题，为；极小化问题，为；

12、 （7）决策变量符号均为 0。,第71页,三、非对称形式原问题-对偶问题的转化,非对称形式线性规划问题的处理方式： 如果线性规划的原问题不是对称形式，需要将其转化为对称形式，然后按照对称形式的要求，写出其对偶问题。,第72页,（1）,（2）,（3）,式（2）：,（4）,解：,第73页,式（3）：,式（4）：,第74页,转化后的对称形式为：,第75页,对偶问题为：,设对偶问题的决策变量为：,第76页,原问题,对偶问题,第77页,令：,下面对对偶问题进行简化处理,第78页,原问题,对偶问题,第79页,非对称形式下原问题-对偶问题的关系,第80页,第81页,极大化问题,极小化问题,约束条件符号,决策

13、变量符号,约束条件符号,决策变量符号,一致,相反,第82页,非对称形式原问题-对偶问题的转化步骤,（1）max min。 （2）对偶问题的决策变量数 = 原问题的约束条件数。 （3）对偶问题的目标函数系数 = 原问题的约束条件右端常数。 （4）对偶问题的约束条件系数矩阵 = 原问题约束条件系数矩阵的转置矩阵。,第83页,（5）对偶问题的约束条件右端常数 = 原问题的目标函数系数。 （6）约束条件符号：由下述关系图确定。 （7）决策变量符号：由下述关系图确定。,第84页,极大化问题,极小化问题,约束条件符号,决策变量符号,约束条件符号,决策变量符号,一致,相反,第85页,第五节 对偶问题的基本性

14、质,原问题,对偶问题,第86页,1. 对称性,对偶问题的对偶是原问题。,证：,对偶问题,原问题,第87页,对偶问题,对偶问题的对偶问题,对偶问题,对偶问题,第88页,2. 弱对偶性,证：,若 是原问题的可行解， 是对偶问题的可行解，则存在,第89页,推论,（1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。,第90页,（2）如原问题为无界解，则对偶问题无可行解；反之，如对偶问题为无界解，则原问题无可行解。 （3）如原问题为无可行解，且对偶问题有可行解，则对偶问题为无界解；反之，如对偶问题为无可行解，且原问题有可行解，则

15、原问题为无界解。,第91页,无界解,无可行解,无可行解,无界解,无可行解,此可行解一定为无界解,对偶问题有可行解,第92页,例：,解：,由第一个约束条件可知：无可行解,又因为原问题有可行解(0,0,0),所以原问题为无界解。,第93页,3. 强对偶性（对偶定理）,若原问题及其对偶问题均具有可行解，则两者均具有最优解，且目标函数值相等。,证：,是原问题的最优解,原问题达到最优时，所有检验数均0，即,最优目标函数值为,第94页,为对偶问题的可行解,带入对偶问题的目标函数：,将可行解,而此时：,由弱对偶性的推论（1）可知：,也是对偶问题的最优解。,为对偶问题下界值。,=下界值,故：,第95页,4.

16、可行解是最优解时的性质,证：,若 是原问题的可行解， 是对偶问题的可行解，,为问题的最优解,（1）必要性证明。,第96页,是对偶问题的最优解,是原问题的最优解,为问题的最优解,（2）充分性证明。,由强对偶性可知。,第97页,5. 互补松弛定理,在线性规划问题的最优解中 如果对应某一约束条件的对偶变量值为非零，则该约束条件为严格等式（松弛变量为零）； 如果约束条件为严格不等式（松弛变量不为零），则其对应的对偶变量最优值一定为零。,第98页,若 为原问题的可行解， 为对偶问题的可行解，,第99页,证：,对偶问题标准型,原问题标准型,第100页,如果,根据性质5：,则有,即,为原问题的最优解， 为对

17、偶问题的最优解。,（1）必要性证明,第101页,如果 为原问题的最优解， 为对偶问题的最优解。,根据性质4：,（2）充分性证明,第102页,例：,已知其对偶问题的最优解为：,求问题的最优解。,第103页,解：,（1）,（2）,（3）,（4）,（5）,所以原问题的约束条件为等式。,第104页,代入原问题的约束条件得：,（2）、（3）、（4）为严格不等式,第105页,原问题,对偶问题,6. 对称形式的原问题-对偶问题解的关系,标准型,标准型,第106页,原问题单纯形表的检验数行对应其对偶问题的一个解（不一定是可行解）；最终单纯形表的检验数行对应其对偶问题的最优解。,第107页,对偶问题变量的值=

18、-（原问题中松弛变量的检验数）,对偶问题剩余变量的值= -（原问题中原变量的检验数）,第108页,证：,第109页,由最优解判别性质可知，Y、YS 为最优解。,因为最终单纯形表中所有检验数 0,故,为可行解,又因为,第110页,对称形式的原问题,第111页,原问题的标准型,第112页,对偶问题,第113页,对偶问题的标准型,第114页,第115页,max z = 2x1 + 3x2,例：,min = 8y1 + 16y2+12y3,第116页,min = 8y1 + 16y2+12y3,max z = 2x1 + 3x2,第117页,第118页,第119页,第120页,第121页,第122页,原问题最终单纯形表的检验数行对应