线性规划的对偶理论.ppt

第二章线性规划的对偶理论和灵敏度分析,从经济意义上研究线性规划的对偶问题，通过对对偶问题的研究，从不同的角度对线性规划问题进行分析，从而利用有限的数据，得出更广泛的结果，间接地获得更多的有用信息，为企业经营决策提供更多的科学依据,主要内容,原规划与对偶规划的转换,对偶定理,影子价格的概念和经济学意义,对偶单纯形法,灵敏度分析的目的和主要内容,问题的提出,线性规划对偶问题,线性规划有一个有趣的特性，就是对于任何一个求极大值的线性规划问题都存在一个与其对应的极小值线性规划问题，而且二者之间联系紧密，可以互相转化。,（教材P53-54例题）,从例子中可以看出：,（1）原规划问题为生产计划问题，而其对偶问题为赋予该生产计划可行性的潜在价值问题,（2）原规划的目标函数是从资源拥有者的角度得出利润最大化，而其对偶规划的目标函数是从想获得该资源方的角度得出成本最小化,（3）两个问题共用一套参数，但组合方式不同,原问题和对偶问题的关系,对偶问题在解释资源的影子价格、扩大单纯形法计算方法以及对问题进行灵敏度分析等方面有很多应用。,从表中可以看出对称形式的对偶关系具有如下的对应关系：,目标函数最大最小；约束条件不大于不小于,约束矩阵：一个为另一个的转置,常数向量b和c互换,目标变量皆为非负,线性规划对偶问题,原问题和对偶问题的关系,非对称形式的对偶问题,不具备对称形式的一对线性规划称为非对称形式的对偶问题,转换方式为：,4、若原规划中的某个变量没有非负限制，则在对偶问题中对应的那个约束为等式。,1、将模型统一为规范形式，然后先按对称形式转换,2、对等式约束按（3）或（4）处理,3、若原规划中某个约束为等式，则在对偶规划中与此对应的变量取值没有非负约束,教材P56例题,线性规划对偶问题,原问题和对偶问题的关系,原问题与对偶问题的转换,线性规划对偶问题,原问题和对偶问题的关系,原问题与对偶问题的转换,线性规划对偶问题,原问题和对偶问题的关系,原问题与对偶问题的转换,线性规划对偶问题,对偶理论,从本章的第一个例子可以看出原规划问题追求的是生产利润最大化，而其对偶规划考虑的是比生产更有利的可行性。,线性规划对偶问题,前者的目标函数值应当不大于后者的目标函数值，即,证明：,从原规划的约束条件有,从对偶规划的约束条件有,对偶理论,线性规划对偶问题,推论1（最优性）：,显而易见,推论2（无界性）：,如原规划（P）或其对偶规划（D）具有无界解，则对偶规划（D）或原规划（P）无可行解。,显而易见,注意：改推论不可逆，教材P58,对偶理论,线性规划对偶问题,推论3：,若规划（P）或（D）有可行解，则（P）或（D）有最优解的充要条件是规划（D）或（P）有可行解,例试用对偶理论判断下面线性规划是否有最优解,解：此规划存在可行解,其对偶规划为,对偶理论,线性规划对偶问题,例用对偶理论判断下面线性规划是否存在最优解,其对偶规划为,存在可行解,因此原规划存在最优解,对偶理论,线性规划对偶问题,定理3.2（强对偶性，或称对偶定理）：,若原规划（P）有最优解，则对偶规划（D）也有最优解，反之亦然。且二者最优解的目标函数值相等。,（证明：教材P58-59）,在线性规划问题的最优解中，如果某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，若如果约束条件取严格不等式，则其对偶变量一定为零。,定理3.3（互补松弛性）：,线性规划问题的原问题和对偶问题存在一对互补的基本解，其中原问题的非基变量（松弛变量）对应对偶问题的基变量，而对偶问题的非基变量（松弛变量）对应原问题的基变量。,定理3.4（互补基本解）：,对偶理论,线性规划对偶问题,线性规划问题的原问题和对偶问题存在一对互补的基本解，其中原问题的非基变量（松弛变量）对应对偶问题的基变量，而对偶问题的非基变量（松弛变量）对应原问题的基变量。,定理3.4（互补基本解）：,在单纯形法迭代的每一步：,如果原问题是可行解，而对偶问题非可行解，则,如果对偶问题是可行解，而原问题非可行解，则,如果原问题和对偶问题同为可行解，则为最优解,影子价格,线性规划对偶问题,考虑如下的互为对偶的线性规划,这个价格不是市场价格，而是针对具体企业在一定时期内存在的一种特殊价格，它蕴含在追求最大利润的生产计划之中。资源的市场价格随供求关系而变，而他的影子价格则有赖于资源的利用情况，随企业生产任务、产品结构等情况发生变化而改变。,影子价格,线性规划对偶问题,影子价格的经济含义,影子价格是对现有资源实现最大效益时的一种估价，由此可以决定是否将既有资源出租或投资购买新资源。从这种意义上说，影子价格是一种机会成本。,影子价格,线性规划对偶问题,影子价格的经济含义,一般而言，线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定资源的恰当估价。例如，用于公司内部结算等。,单纯形法中各检验数的经济意义：,即隐含成本,因此，当检验数为正时，说明生产有利，可以在计划中安排。,影子价格,线性规划对偶问题,例：某外贸公司准备购进两种产品A1,A2。购进产品A1,每件需要10元，占用5立方米的空间，待每件A1卖出后，可获纯利润3元；购进产品A2，每件需要15元，占用3立方米的空间，待每件A2卖出后，可获纯利润4元。公司现有资金1400元，有430立方米的仓库空间存放产品，根据这些条件，可以建立求最大的线性规划模型：,影子价格,线性规划对偶问题,求解后的如下的最优单纯形表：,由表中可知最优方案是分别购进A1和A2产品50和60件，最大利润为390元。,假设公司现有闲余资金585元，准备用于投资，增加每立方米仓库需0.8元。问这笔资金是用来投资仓库好呢还是购买产品好？,影子价格,线性规划对偶问题,假设公司现有闲余资金585元，准备用于投资，增加每立方米仓库需0.8元。问这笔资金是用来投资仓库好呢还是购买产品好？,分析：,从表中个可以看出，对应产品和仓库的影子价格分别为11/45和1/9元。,每投资1元用于仓库的边际效益为：1/9/0.8=0.14元,每投资1元用于产品的边际效益为11/45=0.24元,将585元投资购买产品后，最大利润增加为：585*11/45=143元,可以通过新模型求解验证，最优解为,对偶单纯形法,线性规划对偶问题,基本思路,从原规划的一个基本解出发（未必为可行解），其对应一个对偶可行解（检验数非正）。,检验原规划的基本解是否可行（即是否有负分量），如果有小于0的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。,如果得到的基本解的分量皆非负，则该解为最优解。,也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解逐步变为可行，并得到最优解。,对偶单纯形法,线性规划对偶问题,主要步骤,建立初始单纯形表。根据典式形式建立初始对偶单纯形表，此表对应原规划一个基本解。要求：检验数行个元素皆非正，但原规划基本解可以有小于零的分量。,(5)通过循环迭代找出最优解。,对偶单纯形法,线性规划对偶问题,例：用对偶单纯形法求解下面的线性规划,（s.t.）,对偶单纯形法,线性规划对偶问题,解：,(1)引入松弛变量化为标准形,并在约束等式两侧同乘-1，得到,为基变量，此式即为典式形式，并且检验数皆非正，因此可构造初始对偶单纯形表。,对偶单纯形法,线性规划对偶问题,因此，以a22=-3为中心元素，更新表格，并继续迭代,对偶单纯形法,线性规划对偶问题,因此，以a11=-3/5为中心元素，更新表格，并继续迭代,对偶单纯形法,线性规划对偶问题,用对偶单纯形法求解此问题，只经过两次迭代便得到了最优解。如果仍采用单纯形法求解的话，在化成标准形式后，为得到初始基本解，需要加3个人工变量。这样，为了得到问题的最优解，至少需要3次迭代，才能让人工变量出基，显然，计算量大大增加。,对偶单纯形法,线性规划对偶问题,对于有些线性规划问题，如果在开始时不能很快让所有检验数非正，最好还是使用单纯形法求解，免去使所有检验数非负所做的工作。,对偶单纯形法使用于如下形式的模型,在引入松弛变量并华为标准形式后，约束等式两边同乘以-1，能够立即得到检验数全部非正的原规划基本解，可以直接剪力初始对偶单纯形表求解，非常方便。,灵敏度分析,线性规划对偶问题,但实际中由于种种原因，这些系数很难确定，一般只是估值。,对问题求解后需要最这些估值进行一些分析以决定是否需要调整。,另外，周围环境的变化也会使系数发生变化，影响最优解。,灵敏度分析,线性规划对偶问题,（1）变量变化对最优解的影响,灵敏度分析研究的内容：,（2）增加变量或约束对最优解的影响,灵敏度分析采用的方法：,不必重新求解，而是从已经得到的最优解出发，通过对变化数据进行一些简单的计算，便可迅速得到所需要的结果，以及变化后的最优解。,灵敏度分析的步骤：,（教材P67）,灵敏度分析,线性规划对偶问题,由前面的讲述我们知道，对于线性规划模型,s.t.,有,代入,如果,基本解的矩阵表示,灵敏度分析,线性规划对偶问题,检验数的向量表示,由前知检验数可以用如下的形式表示出来：,其中B为可行基，,展开,灵敏度分析,线性规划对偶问题,检验数的向量表示,若令,灵敏度分析,线性规划对偶问题,目标函数系数（cj）的变化,假设只有一个cj发生变化，分两种情况：,研究最优解受数据变化的影响情况主要考虑两个方面:一是解的最优性，即检验数是否仍然非正;一是解的可行性，即基本解的各个分量是否非负。下面的讨论将围绕这两个方面展开。,（1）ck是非基变量,只需考虑其对应的的变化是否会引起最优解的改变,只要满足则最优解不变；否则，最优解将发生变化，需继续迭代求出最优解。,灵敏度分析,线性规划对偶问题,目标函数系数（cj）的变化,（1）ck是非基变量,（2）ck是基变量,对某一非基变量对应的已有的检验数，有,灵敏度分析,线性规划对偶问题,目标函数系数（cj）的变化,（1）ck是非基变量,（2）ck是基变量,（例子：教材P67-68）,灵敏度分析,线性规划对偶问题,目标函数系数（cj）的变化,右端常数（bi）的变化,bi的变化不会引起检验数的变化，但将影响解的可行性,若则最优基保持不变，只需将变化后的b1代入计算即可得到最优解；若出现负值则最优解将发生变化，需要继续迭代。,（例子：教材P69）,增加新的变量,对某一新增变量对应的约束系数列，由有,如果满足所有的则最优解不变,增加一个约束条件,看教材,其实，还有约束系数变动的情形,本章小结,线性规划对偶问题,线性规划问题的特性就是对于任何一个求极大值的线性规划问题都有一个与之对应的求最小值的线性规划问题，这两个问题互为对偶，存在密切关系。线性规划的对偶性在经济学的角度看可以认为是一个问题的两个方面，即优化生产组织和提高资源利用率。,本章首先引人了线性规划的对偶问题，分析了线性规划问题及对偶问题的特征及在形式上相互转换的规则，并介绍了对偶定理，揭示了线性规划与其对偶问题的深刻的内在联系。然后阐述影子价格概念，指出影子价格就是线性规划问题的对偶问题要解决的资源的潜在价值的反映。影子价格可用于知道生产过程中是否投资或转移某种资源的决策。,对偶单纯形法是把单纯形法思想和对偶思想结合的方法，其求解步骤与单纯形法有一定的对应关系，对偶单纯形法有明确的适用范围，是单纯形法的重要补充。,由于在现实中线性规划模型中的各个系数或约束条件在现实生活中可能发生变化，因此需要分析当这些系数发生变化时对原问题解的最优性和可行性的影响，灵敏度分析的目的就在于考察这些变化对优化生产组织的影响，为决策提供参考。,本章知识点,线性规划对偶问题,掌握对偶规划问题的互相转换的方法,线性规划对偶问题的涵义：,（1）对于任何一个求极值的线性规划问题都有一个与之对应的线性规划问题，即对偶问题；（2）对偶规划和原规划互为对偶，二者共用一套参数，可以互相转化；（3）从经济学角度看，原规划和对偶规划是