线性规划及其应用线性规划的对偶理论精品文稿.ppt

《线性规划及其应用线性规划的对偶理论精品文稿.ppt》由会员分享，可在线阅读，更多相关《线性规划及其应用线性规划的对偶理论精品文稿.ppt（15页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1第1页，本讲稿共15页 3.4 线性规划对偶理论线性规划对偶理论2重庆大学经济与工商管理学院 肖智 (3.4-1)(3.4-1)上述问题是企业利用已有的资源上述问题是企业利用已有的资源,通过自己加工、生产通过自己加工、生产出产品进行销售而获得收入。企业是利润最大化为目标。出产品进行销售而获得收入。企业是利润最大化为目标。因此，因此，对于该问题对于该问题也可也可考虑另一种经营问题，即出租（或考虑另一种经营问题，即出租（或出让）资源，来出让）资源，来获得收入。该问题的关键是确定资源的价获得收入。该问题的关键是确定资源的价格，特别是要确定资源的价格在什么条件下，使格，特别是要确定资源的价格在什么条

2、件下，使出租（或出租（或出让）资源出让）资源所获的最少收入与自己生产所获最大收入相同所获的最少收入与自己生产所获最大收入相同.为此，不妨假设木工与油漆工的单位工时租金分别为：为此，不妨假设木工与油漆工的单位工时租金分别为：y y1 1和和y y2 2，可得数学模型如下：，可得数学模型如下：第2页，本讲稿共15页 3.4 线性规划对偶理论线性规划对偶理论3重庆大学经济与工商管理学院 肖智 (3.4-2)(3.4-2)上述问题显然也是线性规划问题。通常称模型上述问题显然也是线性规划问题。通常称模型(3.4-1)(3.4-1)与模型与模型(3.4-2)(3.4-2)互为对偶问题；若称模型互为对偶问题

3、；若称模型(3.4-1)(3.4-1)为原问题，为原问题，则称模型则称模型(3.4-2)(3.4-2)为模型为模型(3.4-1)(3.4-1)的对偶问题。的对偶问题。2 2、原问题与对偶问题一般矩阵形式：、原问题与对偶问题一般矩阵形式：原问题原问题 对偶问题对偶问题（P P）（D D）(3.4-3)(3.4-3)第3页，本讲稿共15页 3.4 线性规划对偶理论线性规划对偶理论4重庆大学经济与工商管理学院 肖智二、如何将原问题转化为对偶问题二、如何将原问题转化为对偶问题 1 1、转化原则：、转化原则：表表3.4-1 3.4-1 对偶关系对应表对偶关系对应表 原问题（或对偶问题）原问题（或对偶问题

4、）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 maxZ maxZ 目标函数目标函数minWminW变变量量n n个个约约束束条条件件n n个个0000无限制无限制约约束束条条件件mm个个变变量量mm个个0000无限制无限制约束条件右边常数项约束条件右边常数项目标函数变量系数目标函数变量系数目标函数变量系数目标函数变量系数约束条件右边常数项约束条件右边常数项第4页，本讲稿共15页 3.4 线性规划对偶理论线性规划对偶理论5重庆大学经济与工商管理学院 肖智2 2、例、例3.4.23.4.2 原问题：原问题：(3.4-5)(3.4-5)对偶问题：对偶问题：(3.4-6)(3.4-6)第

5、5页，本讲稿共15页 3.4 线性规划对偶理论线性规划对偶理论6重庆大学经济与工商管理学院 肖智三、线性规划的对偶理论三、线性规划的对偶理论 如果不特别说明，原问题（如果不特别说明，原问题（P P）和对偶问题（）和对偶问题（DD）由式）由式(3.4-3)(3.4-3)定义。定义。定理定理3.4.13.4.1：(对称性定理对称性定理)对偶问题的对偶是原问题。对偶问题的对偶是原问题。定理定理3.4.23.4.2：(弱对偶定理弱对偶定理)设设X X，Y Y分别是（分别是（P P）和（）和（D D）的可行解，）的可行解，则则CXYbCXYb。定理定理3.4.33.4.3：(对偶定理对偶定理)（P P）

6、和（）和（D D）存在以下对应关系）存在以下对应关系:（1 1）（）（P P）有最优解的充要条件是（）有最优解的充要条件是（DD）有最优解；）有最优解；（2 2）若（若（P P）无界，则（）无界，则（DD）不可行；）不可行；（3 3）若（）若（D D）无界，则（）无界，则（P P）不可行；）不可行；第6页，本讲稿共15页 3.4 线性规划对偶理论线性规划对偶理论7重庆大学经济与工商管理学院 肖智（4 4）若）若X X*，Y Y*分别是分别是（P P）和（）和（DD）的可行解，则它们分）的可行解，则它们分 别为（别为（P P）和（）和（D D）的最优解的充要条件是：）的最优解的充要条件是：CXC

7、X*=Y=Y*b b定理定理3.4.43.4.4：(互补松弛定理互补松弛定理)如果如果X X，Y Y分别是分别是（P P）和（）和（DD）的可行解，它们分别）的可行解，它们分别为（为（P P）和（）和（DD）的最优解的充要条件是：）的最优解的充要条件是：(C-YA)X=0(C-YA)X=0和和Y(b-AX)=0Y(b-AX)=0四、对偶解的经济含义四、对偶解的经济含义 1 1、对偶解与影子价格、对偶解与影子价格 对偶解（对偶解（Y=CY=CB BB B-1-1）的经济含义是资源的单位改变量）的经济含义是资源的单位改变量引起的目标函数值的改变量。人们通常用价值量来衡量目引起的目标函数值的改变量。

8、人们通常用价值量来衡量目标函数值的大小，因此对偶解也具有价值的内涵，通常又标函数值的大小，因此对偶解也具有价值的内涵，通常又被称为影子价格。被称为影子价格。第7页，本讲稿共15页 3.4 线性规划对偶理论线性规划对偶理论8重庆大学经济与工商管理学院 肖智 影子价格是对偶解的一个十分形象的名称，它既表明影子价格是对偶解的一个十分形象的名称，它既表明对偶解是对系统内部资源的一种客观估价，又表明它是一对偶解是对系统内部资源的一种客观估价，又表明它是一种虚拟的价格种虚拟的价格(或价值的映象或价值的映象)而不是真实的价格。而不是真实的价格。2 2、影子价格的特点：、影子价格的特点：1 1）影子价格是对系

9、统资源的一种最优估价，只有系统达）影子价格是对系统资源的一种最优估价，只有系统达 到最优状态时才可能赋予该资源这种价值。因此，也有人到最优状态时才可能赋予该资源这种价值。因此，也有人称之为最优价格。称之为最优价格。2 2）影子价格的取值与系统的价值取向有关，并受系统状）影子价格的取值与系统的价值取向有关，并受系统状态变化的影响。系统内部资源数量和价格的任何变化都会态变化的影响。系统内部资源数量和价格的任何变化都会引起影子价格的变化，从这种意义上讲，它是一种动态的引起影子价格的变化，从这种意义上讲，它是一种动态的价格体系。价格体系。3 3）对偶解）对偶解影子价格的大小客观地反映资源在系统内影子价

10、格的大小客观地反映资源在系统内第8页，本讲稿共15页 3.4 线性规划对偶理论线性规划对偶理论9重庆大学经济与工商管理学院 肖智的稀缺程度。如果某资源在系统内供大于求，尽管它有实的稀缺程度。如果某资源在系统内供大于求，尽管它有实实在在的市场价格，但它的影子价格为零。这一事实表明实在在的市场价格，但它的影子价格为零。这一事实表明,增加该资源的供应不会引起系统目标的任何变化。如果某增加该资源的供应不会引起系统目标的任何变化。如果某资源是稀缺资源，其影子价格必然大于零。影子价格越高资源是稀缺资源，其影子价格必然大于零。影子价格越高,资源在系统中越稀缺。资源在系统中越稀缺。4 4）影子价格是一种边际价

11、值，它与经济学中边际成本的）影子价格是一种边际价值，它与经济学中边际成本的概念相同。因而在经济管理中有十分重要应用价值。企业概念相同。因而在经济管理中有十分重要应用价值。企业管理者可以根据资源在本企业内影子价格的大小决定企业管理者可以根据资源在本企业内影子价格的大小决定企业的经营策略。然而，对偶解准确的经济意义有时要根据模的经营策略。然而，对偶解准确的经济意义有时要根据模型构造的方法来确定。模型构造方法的不同有时会导致对型构造的方法来确定。模型构造方法的不同有时会导致对对偶解的不同解释。对偶解的不同解释。3 3、影子价格在企业经营策略中的应用、影子价格在企业经营策略中的应用第9页，本讲稿共15

12、页 3.4 线性规划对偶理论线性规划对偶理论10重庆大学经济与工商管理学院 肖智 1 1）如果某资源的影子价格高于市场价格，表明该资源在）如果某资源的影子价格高于市场价格，表明该资源在 系统内有获利能力，应买入该资源。系统内有获利能力，应买入该资源。2 2）如果某资源的影子价格低于市场价格，表明该资源在）如果某资源的影子价格低于市场价格，表明该资源在 系统内一无获利能力，应卖出该资源。系统内一无获利能力，应卖出该资源。3 3）如果某资源的影子价格等于市场价格，表明该资源在）如果某资源的影子价格等于市场价格，表明该资源在 系统内处于平衡状态，既不用买入，也不必卖出。系统内处于平衡状态，既不用买入

13、，也不必卖出。4 4、检验数与边际贡献、检验数与边际贡献 因为因为 ，所以，检验数也可解释为产，所以，检验数也可解释为产品对目标函数的边际贡献，即：增加该产品的单位生产量品对目标函数的边际贡献，即：增加该产品的单位生产量给目标函数带来的贡献。给目标函数带来的贡献。检验数与每一个变量相对应，当线性规划问题达到最检验数与每一个变量相对应，当线性规划问题达到最优时，检验数总是小于或等于零优时，检验数总是小于或等于零(对极大化问题对极大化问题)。这意味。这意味第10页，本讲稿共15页 3.4 线性规划对偶理论线性规划对偶理论11重庆大学经济与工商管理学院 肖智着在最优状态下，每个变量对目标函数的边际贡

14、献都小于着在最优状态下，每个变量对目标函数的边际贡献都小于或等于零。或等于零。检验数所代表的边际贡献有和影子价格一样的特点，检验数所代表的边际贡献有和影子价格一样的特点，它是在系统达到最优时对变量的一种估价。它的取值也受它是在系统达到最优时对变量的一种估价。它的取值也受系统状态的影响，并会随系统的变化而变化。系统状态的影响，并会随系统的变化而变化。5 5、影子价格与资源的关系、影子价格与资源的关系 如果某资源在系统内的影子价格大于零如果某资源在系统内的影子价格大于零(y(yj jo)o)，该资，该资源必是紧缺资源，对应的约束为紧约束源必是紧缺资源，对应的约束为紧约束(b(bi i-a-ai i

15、x xo)o)；否则；否则,若该资源在系统内仍有剩余，系统一定还未达到最优状态若该资源在系统内仍有剩余，系统一定还未达到最优状态,因为继续利用该资源可使目标进一步得到改善。另一方面因为继续利用该资源可使目标进一步得到改善。另一方面,如果某资源在系统内有剩余，资源约束为松约束如果某资源在系统内有剩余，资源约束为松约束(b(bi i-a-ai ix x0)0)时，其对偶解必为零时，其对偶解必为零(y(yj j0)0)，否则，若对偶解大于零，否则，若对偶解大于零，第11页，本讲稿共15页 3.4 线性规划对偶理论线性规划对偶理论12重庆大学经济与工商管理学院 肖智增加该资源的使用还可使目标得到改善。

16、增加该资源的使用还可使目标得到改善。同样道理，在最优状态下，当变量的检验数小于零时同样道理，在最优状态下，当变量的检验数小于零时(c(cj j-yp-ypj j0)0)，说明生产该产品的边际贡献是负的，在最优，说明生产该产品的边际贡献是负的，在最优计划中不该生产它，因此，该变量必为零计划中不该生产它，因此，该变量必为零(x(xj j0)0)。另一。另一方面，当变量大于零时方面，当变量大于零时(x(xj j0)0)，该变量检验数，该变量检验数(边际贡献边际贡献)必为零必为零(c(cj j一一ypypj j0)0)，否则，无论边际贡献取正值或负值，否则，无论边际贡献取正值或负值,相应地增加或降低该

17、产品的产量都可使目标得到改善。相应地增加或降低该产品的产量都可使目标得到改善。五、对偶问题的求解方法五、对偶问题的求解方法 1 1、对偶解的求法、对偶解的求法 1 1）直接求对偶问题的解；）直接求对偶问题的解；2 2）求原问题的最优解时，求得对偶解）求原问题的最优解时，求得对偶解Y=CY=CB BB B-1-1 3 3）对偶单纯形）对偶单纯形7 7、例：对例、例：对例3.4.13.4.1用上述方法用上述方法2)2)得原问题的最优单纯形表得原问题的最优单纯形表第12页，本讲稿共15页 3.4 线性规划对偶理论线性规划对偶理论13重庆大学经济与工商管理学院 肖智2 2、例：对例、例：对例3.4.1

18、3.4.1用上述方法用上述方法2)2)得原问题的最优单纯形表得原问题的最优单纯形表表表3.4-2 3.4-2 最优单纯形表最优单纯形表 cj50 3000bxB CBx1x2x3x4x304 43 31 10 0120120 x402 21 10 01 15050 j505030300 00 00 0 x300 01 11 1-2-22020 x150501 11/21/20 01/21/22525j0 05 50 0-25-2512501250 x230300 01 11 1-2-22020 x150501 10 0-1/2-1/23/23/21515j0 00 0-5-5-15-1513501350第13页，本讲稿共15页 3.4 线性规划对偶理论线性规划对偶理论14重庆大学经济与工商管理学院 肖智原问题的最优解为：原问题的最优解为：X X*=(15,20)=(15,20)T T，最优值为：，最优值为：Z Z*=1350=1350对偶问题的最优解为：对偶问题的最优解为：Y Y*=(5,15)=(5,15)，最优值为：，最优值为：WW*=1350=1350 第14页，本讲稿共15页 3.4 线性规划对偶理论线性规划对偶理论15重庆大学经济与工商管理学院 肖智 THE END 第15页，本讲稿共15页