第一节-线性规划的对偶问题.ppt

第三章对偶理论与灵敏度分析,3.1线性规划的对偶问题3.2对偶单纯形法3.3灵敏度分析,*,每一个求极大值线性规划问题都有一个与之伴随的求极小值的线性规划问题，这个伴随的线性规划问题称之为它的对偶问题。,3.1线性规划的对偶问题,引例某工厂用甲乙两种资源生产A、B、C、D四种产品，现有资源数、单位产品所需资源数以及单位产品可获利润如下表所示.问如何组织生产能使利润最大？,3.1.1对偶问题的提出,显然，该问题的线性规划模型为：,现在从另一个角度考虑问题。假设该厂不生产A、B、C、D四种产品了，而是将甲、乙两种资源出租给其它单位，其原则是：使别的单位愿意租，又使本单位获利不低于原利润。问如何给甲、乙两种资源定价最合理？,解,设甲、乙两种资源的价格为,设总收入为W，则,约束条件为,比较一下这两个线性规划问题：,原问题,对偶问题,线性规划问题和它的对偶问题之间的关系：,（2）原始问题约束不等式的个数等于对偶问题变量的个数；,（3）原始问题的收益系数，成为对偶问题中约束不等式右端的常数项；,（5）约束不等式，一个全是“”，另一个全是“”；,（4）两个约束方程组的系数矩阵互为转置矩阵,（6）原始问题和对偶问题是相对的，可以互相转化；,（1）目标函数，原始问题是求最大值，对偶问题是求最小值；,对偶问题的矩阵表示：,原问题,对偶问题,对偶问题的矩阵表示：,原问题,对偶问题,对偶问题的矩阵表示：,原问题,对偶问题,例1写出线性规划问题的对偶问题,对称形式：,练习写出下列问题的对偶问题（77页）,非对称形式例3.3写出下面线性规划问题的对偶问题,解先化为对称形式,解先化为对称形式,解先化为对称形式,解先化为对称形式,写出其对偶问题,设对偶问题的变量为,这样的对偶问题与原问题无法对照,？,原问题,对偶问题,对偶关系对应表,练习写出下列问题的对偶问题（77页）,无符号限制,无符号限制,作业写出下列问题的对偶问题,本小节所用课时数：两节第一节课讲完定理3.4第二节课专门讲定理3.5最后两个定理的证明可以不讲不强调抽象晦涩的证明过程多关注对定理的理解和应用,3.1.3对偶问题的基本理论,3.1.3对偶问题的基本理论,定理3.1若和分别是原始问题和对偶问题的任一可行解，则必有,证明：,假设线性规划的原问题和对偶问题分别为,和,定理3.1若和分别是原始问题和对偶问题的任一可行解，则必有,推论1最小值原始问题的任意一个可行解对应的目标函数值是其对偶问题最优值的一个上界,推论2最大值原始问题的任意一个可行解是其对偶问题最优值的一个下界,推论3若原始问题可行，而目标函数无界，则其对偶问题无可行解,例(补充)已知线性规划问题：,试用对偶理论证明该问题的最优值不超过25,解写出其对偶问题,显然，是对偶问题的一个可行解，,它对应的目标函数值为,根据对偶理论，最小值问题的任一可行解都是其对偶问题最优值的一个上界，,定理3.2若和分别是原始问题和对偶问题的可行解，且有，则和分别是原始问题和对偶问题的最优解,证明：设是原始问题的任一可行解,由定理2.1可得,又已知,由的任意性可知，是原始问题的最优解,同理可证是对偶问题的最优解,定理3.3(对偶定理)在互为对偶的线性规划问题中,如果其中一个有最优解,则另一个也有最优解，且它们的最优值相等,证明：假设原始问题为如下的标准形式,则其对偶问题为,无符号限制,最优值为,即是对偶问题的一个可行解,设是原始问题的最优解，它对应的最优基为B，则相应的基变量为,检验数为,令,则,而,由定理3.可知，是对偶问题的最优解,无符号限制,推论1在互为对偶的线性规划问题中，若原始问题的最优基为B，则对偶问题的最优解为,推论2设为原始问题的一个可行解，相应的可行基为B，而为其对偶问题的可行解，则和分别为它们的最优解,定理3.3(对偶定理)在互为对偶的线性规划问题中,如果其中一个有最优解,则另一个也有最优解，且它们的最优值相等,例(补充)已知线性规划问题：,试用对偶理论证明该问题无最优解,解写出对偶问题,若原问题有最优解,则对偶问题也有最优解,但是观察可知,对偶问题无可行解,更不会有最优解，,故原问题无最优解,定理3.4若原始问题的最优解存在，则用单纯形法求解时，其对偶问题的最优解可同时在最优单纯形表上得到，且顺次等于松弛变量或剩余变量对应的检验数的相反数,证明：设原问题和对偶问题分别为,和,引入剩余变量和松弛变量，将约束条件标准化，得到,和,设是原问题的一个基，且,则有,及,目标函数,约束方程,于是对应于基B的单纯形表的检验数行为,再来看对偶问题，,其中，是对应原问题中基变量的松弛变量，是对应原问题中非基变量的松弛变量,原问题单纯形表的检验数行,构成对偶问题的一个基本解,1、若所有分量都大于零，则该解是对偶问题的一个基本可行解；,2、若是最优单纯形表，则该解是对偶问题的最优解,定理3.4若原始问题的最优解存在，则用单纯形法求解时，其对偶问题的最优解可同时在最优单纯形表上得到，且顺次等于松弛变量或剩余变量对应的检验数的相反数,例(补充)求线性规划问题的对偶问题的最优解,标准形式,最优单纯形表,2,301,000,1,x,3,100,1-101,x,5,200,0-11,2,x,例(补充)求线性规划问题的对偶问题的最优解,标准形式,对偶问题,原始问题的最优单纯形表,原始问题的最优解为,对偶问题的最优解为,最优值为,最优值为,2,301,000,1,x,3,100,1-101,x,5,200,0-11,2,x,定理3.4若原始问题的最优解存在，则用单纯形法求解时，其对偶问题的最优解可同时在最优单纯形表上得到，且顺次等于松弛变量或剩余变量对应的检验数的相反数,注：此处原始问题和对偶问题的决策变量都必须是非负的,定理3.5（互补松弛性）若和分别是原始问题和对偶问题的可行解，且和分别为它们的剩余变量和松弛变量，则和当且仅当,和分别为它们的最优解,假设线性规划的原问题和对偶问题分别为,和,设原始问题的变量个数为n，约束个数为m，,则对偶问题的变量个数为m，约束个数为n,原始问题的变量,原始问题的剩余变量,对偶问题的变量,对偶问题的松弛变量,在一对变量中,其中一个大于零,另一个一定等于零,标准形式,标准形式,对偶问题,最优解,标准形式,标准形式,对偶问题,最优解,标准形式,标准形式,对偶问题,最优解,标准形式,标准形式,对偶问题,至少有一个不是最优解,互补松弛条件意味着:,1、若某一决策变量的值大于零,则在其对偶问题中与之对应的约束条件取严格等式;,2、若某一约束条件取严格不等式,则在其对偶问题中与之对应的决策变量值一定为零.,标准形式,标准形式,对偶问题,标准形式,标准形式,对偶问题,互补松弛条件意味着:,1、若某一决策变量的值大于零,则在其对偶问题中与之对应的约束条件取严格等式;,2、若某一约束条件取严格不等式,则在其对偶问题中与之对应的决策变量值一定为零.,证明：,两式相减得,若,则有,定理3.5（互补松弛性）若和分别是原始问题和对偶问题的可行解，且和分别为它们的剩余变量和松弛变量，则和当且仅当,和分别为它们的最优解,由定理3.可知，分别是原问题和对偶问题的最优解,这是必要性的证明，下证充分性,若分别是原问题和对偶问题的最优解,则,又,故,例(补充)已知线性规划问题：,已知其对偶问题的最优解为,试用对偶理论找出原问题的最优解,解写出对偶问题,故原问题的两个约束均取严格等式,是对偶问题的最优解,而当时，对偶问题的第二、三、四约束取严格不等式，故有,于是由原问题的约束条件可得,练习：78页3.3已知线性规划问题：,已知其对偶问题的最优解为,试用对偶理论求出原问题的最优解,答案：,解写出对偶问题,故原问题的两个约束均取严格等式,是对偶问题的最优解,而当时，对偶问题的第一、二、约束取严格不等式，故有,于是由原问题的约束条件可得,作业：78页3.4,78页3.4题答案,解令，并将原问题化为对称形式,写出对称形式的对偶问题,显然，和,分别是原问题和对偶问题的可行解，,而且满足互补松弛性，故它们分别是原始问题和对偶问题的最优解。,练习某线性规划问题的最优单纯形表如下：,（a）写出原线性规划问题并求其最优值；,（b）写出原问题的对偶问题；,（c）直接由表格写出对偶问题的最优解.,其中，是松弛变量，问题的约束为“”形式,答案：,（a）原线性规划问题为：,（b）略；,（c）对偶问题的最优解为,解设最优值为m，在单纯形表上做初等行变换,3.1.4影子价格,（甲资源）,（乙资源）,（利润）,则求原始规划的最优解就是求在有限资源配置下的最佳效益；,设原始问题及其对偶问题分别为如下形式,那么，此时相应的对偶规划的最优解，即变量y的取值对于原问题来说有何经济意义呢？,设是原问题的最优基，和分别为原问题和对偶问题的最优解，和分别是原问题和对偶问题的最优值，则有,其中，是第i种资源的现有总量，,可以看成是每一个单位第i种资源对经济效益所做的贡献；,或者说成是每一个单位第i种资源在原生产安排的机会中所创造的价值；称为第i种资源的影子价格.,注意：影子价格不是资源的市场价格，而是对资源在生产中所做的贡献的估价.,这说明，在给定的条件下,每增加一个单位第i种资源的用量,目标函数值(即总收益)的增量就等于影子价格,例某厂用甲、乙、丙三种原料生产、两种产品，线性规划模型如下,例某厂用甲、乙、丙三种原料生产、两种产品，线性规划模型如下,甲的用量：,乙的用量：,丙的用量：,有剩余,用完,用完,影子价格在管理决策中的作用:,(0)影子价格反映了供求关系和资源的稀缺性：,(1)影子价格告诉企业的经营管理者，增加哪种资源对提高效益有利：,若影子价格高于市场价格,就可以购进该资源；反之，暂时就不要购买了。,影子价格为零，说明供大于求，影子价格越高资源越稀缺,(2)影子价格告诉决策者新的产品是否可以投入生产,例如之前那个工厂打算生产一种新产品,已知单位新产品耗用的三种原料分别是（2,3,2）,而单位新产品的售价是8元,问新产品是否应该生产？,前面已经求出三种原料的影子价格了:,可以生产,(3)当市场价格变动时，可从单纯形表中直接求出各资源的新的影子价格，从而看出各单位资源所创造的新的价值,例如，上例中产品A、B的售价由（6，5）变为（6，6）：,例某厂用甲、乙、丙三种原料生产、两种产品，线性规划模型如下,例某厂用甲、乙、丙三种原料生产、两种产品，线性规划模型如下,例某厂用甲、乙、丙三种原料生产、两种产品，线性规划模型如下,这说明在新的形势下原料丙变得更为重要了.,影子价格为零，说明供大于求，影子价格越高则资源越稀