【对偶规划及其应用问题研究9200字（论文）】

PAGE21对偶规划及其应用问题研究1绪论························································11.1研究背景及意义···········································11.2国内外研究现状···········································12对偶规划····················································22.1对偶问题·················································22.2对偶单纯形法·············································52.3对偶理论···············································112.4对偶问题的灵敏度分析····································123对偶规划的应用··············································153.1影子价格················································153.2对偶规划应用实例分析···································164结语························································21参考文献·····················································22对偶规划及其应用摘要：对偶规划是线性规划的重要组成部分，对偶问题和原问题之间有着密不可分的关系，其理论和实际应用都具有重要研究意义，对偶规划在经济、工业、生产、军事等方面都起到了不可取代的作用.本文主要对对偶问题、对偶单纯形进行系统阐述，对对偶规划的灵敏度进行分析，并以具体问题为例，更直观地说明对偶规划及其在应用方面的指导作用.关键词：对偶规划，对偶理论，对偶单纯形法，灵敏度分析,影子价格.1绪论1.1研究背景及意义对偶思想最早出现于1928年，数学家JohnvonNeumann在对博弈论进行研究之时，认为二人零和博弈可以用线性规划的原始问题及对偶问题表示出来.直至1939年，苏联数学家LeonidV.Kantorovich初次总结生产中的一系列问题，例如最好地利用原料、当地材料、燃料及运输能力等问题，都属于同一种数学问题即极值问题，而他所首创的解乘数法恰能求解这类问题.这种方法对于现代应用数学具有划时代的意义，开创了解决线性规划问题的先河.经过对对偶问题数年的不懈钻研，JohnvonNeumann于1947年提出对偶理论，此后，线性规划和对偶理论的发展进程得到了极大的推动，对偶规划的理论和解法不断向更深更广的方向延伸，且广泛应用在现实生活中的方方面面.线性规划旨在研究取之有限的资源如何在有竞争的系统中如何分配才是最优的问题，而对偶理论占据线性规划研究中重要的一角.线性规划原问题和对偶问题之间有着千丝万缕的关系，并且具有研究价值.当面临复杂的原问题时，先求解其对偶问题为求解线性规划问题提供了一定的便利.对偶问题的最优解对深入解释线性规划模型经济含义起重要作用.对偶解的经济含义是影子价格，影子价格的实质是对系统资源价格的估计，它可以应用于经济管理中，是一个重要的参考指标.此外，对偶规划在资源利用、生产方案、原料配比等方面也有重要作用.1.2国内外研究现状1.2.1国内研究现状国内对对偶问题的研究较晚，对于对偶问题的研究偏重于对实际的应用.1964年林诒勋[1]在前人已经奠定的线性规划基础之上，参考线性方程组的Fredholm定理，得到另一种求解办法.1978年林锉云[2]对非线性规划的对偶理论进行研究.王长钰[3]将凸对偶规划应用于运价为凸函数的运输问题并研究其解的情况.1981年胡幼青[4]对对偶规划的经济含义影子价格做出了较为全面的介绍.此后，魏力仁[5]，刘序球[6]等人对对偶规划的经济应用做了进一步研究.1986年顾新华、连成平[7]运用对偶原理研究国民经济控制,基于对偶系统指标，给出最优价格制定的模型.2003年，梁治安[8]研究多目标分式规划的对偶模型并得到了相应的对偶定理.2020年，岳东萍[9]对广义高阶不变凸目标规划的对偶性做研究，给出对偶性结果.1.2.2国外研究现状1951年D.Gale，H.W.Kuhn，A.W.Tucher[10]首次提出了线性规划的对偶模型，证明了对偶定理.1953年TjallingC.Koopmans[11]首次成功将线性规划引入生产分析.不同于传统生产和价格理论，他把各种可以使用的生产方法及其使用的程度作为决策变量，推动了资源分配最优理论向前发展.1954年对偶单纯形法由数学家C.Lemke提出，就在同一年，S.Gass和T.Sadi研究并解决了参数规划问题及完成了灵敏度分析的研究证明.1956年A.Tucher提出线性规划中的一条重要定理——互补松弛定理.1962年DuffinR.J.1970年ElmorL.Peterson[12]通过研究Duffin原始公式的对偶无约束几何规划，为理解集合对偶问题的经济学解释提供了一种新的思路，给出最优解的存在性和唯一性的相关新定理.1972年V.A.Sposito[13]研究消去目标函数的下界的线性规划及其对偶线性规划，并给出了显式最优解.1974年A.L.Soyster[14]拓展了凸规划的概念，将目标向量替换为凸集，并公式化对偶问题.1981年G.R.Bitran[15]对非线性多目标优化问题建立了对偶理论，并提出了对偶矩阵的经济解释.1998年G.Giorgi,A.Gucrraggio[16]对广义不变凸向量函数的光滑和非光滑多目标规划进行研究，得到了一些对偶结果.近年来，许多人研究随机动态规划等较为复杂的问题.2020年，VincentGuigues[17]对凸非线性优化问题的随机对偶动态规划进行研究，对动态对偶规划算法进行推广，并应用于市场上投资组合的选择和操作.2对偶规划2.1对偶问题线性规划原问题和对偶问题相伴存在，两者有着千丝万缕的关系.实际上，这两个问题可以看成从待解决问题的不同角度出发建立模型所得到的目标和约束条件.例2.1.1水泥厂为生产甲、乙、丙三种不同品质的水泥需要用到A、B、C、D四种石料，具体要求如下表：表1石料水泥ABCD单件产品收益甲32112000乙41324000丙22343000原材料总量600400300200先考虑使收益最大时的生产安排.设生产甲、乙、丙的数目分别为、、.则模型表示为：..（2.1）现考虑另一种情况：水泥厂决定不安排生产任务，而将厂内所有石料全部出售，此时工厂需要定下一个合理的原材料价格，使原材料价格尽可能低，同时保证工厂收益不减少.在此情况下，设水泥厂拥有的石料A、B、C、D的价格分别为、、、.则此时模型为：..（2.2）上述例子所得的模型（2.1）和模型（2.2）互为原问题和对偶问题.对比两者可以看出，它们之间存在紧密联系：其中一个问题求目标值最大，另一个求目标值最小；两个问题目标函数系数和约束条件的右边互相对应；其中一个问题约束条件左边的系数矩阵是另一个问题的转置[18].下面给出对偶问题的一般表现形式.设线性规划问题..（2.3）则对应的对偶问题为..（2.4）（2.3）和（2.4）可以简写为：....（2.5）其中，，，，是一个阶的矩阵.2.2对偶单纯形法单纯形法是一种用来求解线性规划问题的常用方法.首先引入一些定义.可行解是满足线性规划全部约束条件的向量[18].对给定线性规划问题：，其中是一个阶的矩阵且.将分为一个阶方阵和一个阶矩阵，且.则可以表示为.将也作对应的分割，表示为,其中称为基变量，表示作对应分割后矩阵中相对应的个的分量；称为非基变量，表示矩阵中相对应的个的分量.从而方程组可以表示为.（2.6）又因为可逆，可得，（2.7）则.特别地，令，得到（2.8）称为基本解.若基本解满足非负可行，即，（2.9）则称其为基本可行解[19].单纯形法的原理是在解一直可行的情况下，将一个可行解通过替换基变量得到新的可行解，此过程不断迭代进行下去，直到每一个检验数都非正为止，就能得到线性规划的最优解.矩阵依照上述方法分解后，线性规划可以写为..（2.10）.将（2.7）代入目标函数得（2.11）.令，可得，.若满足，则是一个基本可行解.在上式（2.11）中，称为检验向量，它的一个分量称为检验数，可以表示为，，为非基变量下标的集合.根据检验数的取值可以判断解是否为最优解.定理2.2.1设是一个可行基，是基本可行解，若满足检验数，，则是一个最优解[18,20].证明：对应的目标函数值为.设是任一可行解，由、，可得.所以是最优解.若得到的解为最优解，即线性规划问题已然得到解决，若不是最优解，则要进行换基迭代.这就要通过一些计算确定需要变化的基变量和非基变量，得到另一个基.若结果不是最优解，检验数中至少有一个大于零.只选择非基变量中一个变量成为基变量，其余非基变量仍为零，则有.因为所有的基变量大于等于零，所以有.（2.12）又因为，，只有当时，式（2.12）才有可能不成立，所以有.设，（2.13）这称为确定出基变量的检验准则，设经过检验后确定第个基变量出基，即.令入基变量，改变后的基变量为（2.14）改变后的目标函数为（2.15）得到新的基和目标函数后，再检验其最优性，循环此步骤直至得到最优解，这就是单纯形法的过程.基于单纯形法，对于原问题的单纯形法的原理可以解释为：保持原问题的解始终可行，由一个基本可行解不断迭代，当其对偶问题的解从不可行转变为可行时终止计算，原问题的最优解就是终止时原问题的可行解.因为原问题和对偶问题特殊的对称性，所以对偶单纯形法可以解释为：保持对偶问题的解始终可行，由一个基本可行解不断迭代，当原问题的解从不可行转变为可行时终止计算，对偶问题的最优解就是终止时对偶问题的可行解.根据这一思路，就能完善对偶单纯形法的详细过程.设对偶问题已经得到一个对偶可行解，对这个解进行更新迭代.由（2.9）可知，当条件成立时，原问题的解是可行解，因此最优性检验可能存在以下三种情况：（1）若，则由定理2.2.1可知，该解为最优解.（2）若不成立，则中最少有一个分量.设该分量对应的行向量，其中.①若的所有分量大于等于零，则有.又因为且，所以不可能为正，可知原问题不存在可行解.②若有分量小于零，则此时原问题的解不是可行解，需要进行迭代.替换新基后新的检验数和对偶可行条件可以表示为：，（2.16）其中称为旋转元，且.由，可得.入基变量的检验准则为.（2.17）故只要按照（2.17）选择入基变量，以为旋转元进行换基迭代，经过一系列计算，就可以算得原问题的可行解.综上，对偶单纯形法的步骤如下：（1）找到一个初始对偶可行解.（2）检验是否为最优解.①若，初始解就是最优解，终止计算.②若，且，则该问题不可行，终止计算.③若，且存在，则应进行换基迭代，跳转到步骤（3）.（3）确定入基变量.计算，其中.（4）以为旋转元作旋转变换，跳转到步骤（2）.接下来以一个简单的例子演示对偶单纯形法的具体过程.例2.2.1用对偶单纯形法求解...解：将此线性规划标准化得..以、为初始基，为了方便计算，将标准化后的线性规划的约束条件两边乘-1，有..，，,,，则相应的单纯形表为表20-2-3-400-3-1-2-110-4-21-301为非可行解，但为对偶可行解.因，所以，则为离基变量.，、，有故，为入基变量.以为旋转元进行旋转变换，得到新的单纯形表为表340-4-10-1-101210仍为非可行解.因为，所以，则为离基变量.，、，有故，为入基变量.以为旋转元进行旋转变换，得到新的单纯形表为表4000110，因此最优解为，最优值为.2.3对偶理论由对偶问题的定义式可以得到一些性质，即对偶理论.定理2.3.1设原问题的可行解为，对偶问题的可行解为，则有.证明：由原问题和对偶问题的定义可得，，且，，从而有，即,整理对比得.这个定理也称为弱对偶定理，它表现了线性规划原问题和对偶问题的目标函数值具有一定的大小关系，由该定理进一步可以得到对偶定理.定理2.3.2（对偶定理）原问题和对偶问题存在以下关系[18,21]：（1）原问题有最优解的充要条件是对偶问题有最优解.（2）若原问题无界，则对偶问题无可行解，反之，若对偶问题无界，则原问题无可行解.（3）若、分别是原问题和对偶问题的可行解，若满足，则、分别是原问题和对偶问题的最优解.证明：（1）必要性：设原问题的最优解是，是最优基.由定理2.2.1可推得最优性检验条件和.设是对偶问题的一个可行解，令，有，.由定理2.3.1可得，即是对偶问题的一个下界，且对偶问题的可行域是一个非空的闭凸子集，因此必定存在一个最优解满足上述条件.充分性：由对称性即可得证.（2）因为原问题与对偶问题具有对称性，所以仅需证明一条结论即可.下证：若原问题无界，则对偶问题没有可行解.反证法.假设原问题无界，对偶问题有可行解.由定理2.3.1，原问题的任意可行解有，由该式子可知，就是原问题的一个上界，矛盾.所以若原问题无界，则对偶问题无可行解.（3）充分性：设原问题的可行解为，对偶问题的可行解为，两者满足.设、分别是原问题和对偶问题的任意可行解，由定理2.3.1，满足式子和，可知、分别是原问题和对偶问题的最优解.必要性：设原问题的最优解是，是最优基.由定理2.3.2（1）可知，是对偶问题的一个可行解，有.又由定理2.3.1，有.2.4对偶问题的灵敏度分析建立线性规划模型时各个参数都是固定的，但现实生活中实际情况复杂多变，各种因素都会影响到数据的准确度，因此，对于对偶问题的灵敏度分析是十分重要的.下面对对偶问题目标函数系数变化和约束条件右边项系数变化进行灵敏度分析.2.4.1目标函数系数变化的灵敏度分析对目标函数系数变化的灵敏度分析又可以分成非基变量系数变化和基变量系数变化两种情况.设变化的系数为.（1）是非基变量的系数.设变化量为，若变化后仍保持原来的最优基不变，则需要检验数满足定理2.2.1的条件，即，整理得.所以，在保持最优基不变的情况下，目标函数系数的变化量的取值范围是.（2.18）变化量的取值落在这个范围内时，最优基保持不变.变化量在增加的方向有上界，而在下降的方向无界.即是说变化量的大小增加时，对应的系数对目标函数的贡献随之增加，当变化量超过这个上界时，最优基就会发生变化.变化量下降时，会随之减小，不可能大于零，因此最优基不变.（2）是基变量的系数.若是基变量的系数，则的变化会使跟着变化.设的变化量为.若变化后仍保持原来的最优基不变，则需要检验数满足定理2.2.1的条件，即.（2.19）设第个基变量的系数发生变化，其他保持不变，则有,（2.20）.（2.21）将式（2.20）代入式（2.19）有（2.22）此时要分两种情况讨论.情况一：若，当时，式（2.22）可能不成立，所以有.情况二：若，当时，式（2.22）可能不成立，所以有.综上所述，在保持最优基不变的情况下，目标函数系数的变化量的取值范围是.（2.23）当变化量的取值落在这个范围内时，最优基不变，只有目标函数改变，变化量为.若变化量的取值落在这个范围外，最优基不再是原来的最优基，此时需要进行换基迭代求得最优解.2.4.2约束条件右边项变化的灵敏度分析.约束条件右边项的变化只会影响基变量和目标函数，而不影响检验数.设右边项变化量为，发生变化的参数为，则有，.若要使得到的新基可行，则需要保证基变量非负，于是有.（2.24）其中是的第行第列元素.此时也要分两种情况讨论.情况一：若，当时，式（2.24）有可能不成立，所以有.情况二：若，当时，式（2.34）有可能不成立，所以有.综上所述，在保持最优基不变的情况下，右边项变化量的取值范围是.（2.25）当变化量的取值落在这个范围内时，最优基不变，基变量和目标函数值改变，变化量为.若变化量的取值落在这个范围外，最优基会发生变化.3对偶规划的应用3.1影子价格线性规划讨论的是取之有限的资源如何在有竞争的系统中如何分配才是最优的问题.若将模型（2.3）看成线性规划在经济活动中的应用，可以看作各种资源的可用量，可以看作每种产品或经济活动的利润，可以看作每种产品的产量或经济活动的体量，目标函数可以看作经济活动的总利润[22].线性规划的求解就是求在各种资源可利用量的限制内资源的最优化分配，对偶问题的解就表示各种资源在系统中所处的状态及其变动对总利润的影响，这就是影子价格.影子价格是对系统资源价格的合理估计，不是实际的价格.同时，影子价格是对系统资源价格的最优估计，是系统资源物尽其用，达到最合理分配时的资源价值.而在现实生活中，实际市场价格往往与影子价格不相等.当实际市场价格与影子价格相等时，该资源达到均衡状态，此时资源得到最优分配.为了达到资源均衡状态，就要对实际市场价格和影子价格进行比较大小，对资源实施买入或卖出策略，使企业的利润达到最大.如果实际市场价格比影子价格高，说明该资源的实际价格被过低地估计，此时应该适当购入该资源以获得更高利润；如果实际市场价格比影子价格低，说明该资源的实际价格被过高地估计，应该适当抛售该资源.从另一个方面看，影子价格代表着资源是否稀缺及其稀缺程度.有越高影子价格的资源越稀缺[23].影子价格对经济、生产等方面具有重要意义.其对资源分配有指导性作用，企业决策者可以利用影子价格对企业现有分配方案有更深层的了解，有助于调整企业资源.在企业内外部环境变化的影响下，企业决策者也可以利用影子价格灵活调整对企业的资源，使企业资源得到充分利用，企业利润获得最大化.3.2对偶规划应用实例分析例3.2.1虎丘工厂用A、B两种原料生产甲、乙两种产品，具体的生产情况如下表（配比单位为千克/件）：表5产品原料甲乙原料库存（千克）原料成本（元/千克）A204016001.5B302018002.5售价（元）130160求使销售利润最大使的生产分配.解：设生产甲产品件，生产乙产品件，为总利润，表示为（3.1）建立模型如下：..（3.2）该模型的最优解为，.设原料A的影子价格为，原料B的影子价格为，则模型（3.2）的对偶模型为.（3.3）该模型的解为，.要使利润最大化，生产的安排应是生产甲产品50件，生产乙产品15件，此时最大利润为2000元.由对偶规划的解，，可以知道对偶解的经济含义为：每增加1千克原料A的供应量，工厂的利润会增加1.25元；而增加原料B的供应量，工厂的利润不会发生变化.因为原料A的影子价格为2，所以原料A在生产中属于稀缺资源，增加原料A的供应量可以使总利润增加.根据对模型（3.3）的灵敏度分析，当原料A的库存的允许增加量为2000千克，此时，工厂的总利润增加元.因为原料B的影子价格为0，所以原料B在生产中处于剩余状态，那么决策者可以考虑适当改变原料B的库存，增加工厂的现金流.根据对模型（3.3）的灵敏度分析，原料B的允许减少量为1000，允许增加量为600，即当原料B的库存大于800且小于2400时，生产方案的最大利润不变.因此可以减少800千克原料B的库存，获得2000元的流动资金.影子价格可以用来预测产品价格.在本例中，若北湖工厂是原料A的供应厂商，原料A的交易价格应该在原料A的影子价格和北湖工厂生产原料A的单位成本之间，才能达到共赢.否则，若交易价格比虎丘工厂原料A的影子价格高，虎丘工厂将不会愿意购买北湖工厂的原料A；若交易价格比北湖工厂的单位成本低，北湖工厂将会亏本.由上述可知，原料A的影子价格为2元，若北湖工厂生产原料A的单位成本为1.5元，则原料A的交易价格应该在1.5元和2元之间.例3.2.2某企业旗下有甲、乙两种产品，在南京的A、B两个工厂生产，在工厂加工生产后销往苏南和苏北.企业产品和工厂相关资料如下表.表6出售地区产品类别最大库存（kg）单价（元）销售费用（元）销售费用（元）工厂A工厂B销往苏南产品甲1200013312产品乙1000017412销往苏北产品甲1500016422产品乙750018512表7工厂产品类别生产成本（元/kg）时间定额（小时）时间限额（小时）第一车间第二车间第一车间第二车间工厂A产品甲71.521300030000产品乙62315000工厂B产品甲721800040000产品乙52.5220000现该企业希望做出一些决策提高企业的总利润，那么就需要建立对偶规划，通过影子价格得到启发.解：设为工厂A生产的将销往苏南的产品甲，为工厂B生产的将销往苏南的产品甲，为工厂A生产的将销往苏北的产品甲，为工厂B生产的将销往苏北的产品甲，为工厂A生产的将销往苏南的产品乙，为工厂B生产的将销往苏南的产品乙，为工厂A生产的将销往苏北的产品乙，为工厂B生产的将销往苏北的产品乙，为总利润，表示为（3.4）建立模型如下..（3.5）求解该模型得，，，，，，，.模型（3.5）对应的对偶模型为.（3.6）其中，为销往苏南的产品甲的影子价格，为销往苏北的产品甲的影子价格，为销往苏南的产品乙的影子价格，为销往苏北的产品乙的影子价格，在工厂A第一车间生产的产品甲的影子价格，在工厂A第一车间生产的产品乙的影子价格，在工厂A第二车间生产的产品甲、乙的影子价格，在工厂B第一车间生产的产品甲的影子价格，在工厂B第一车间生产的产品乙的影子价格，在工厂B第二车间生产的产品甲、乙的影子价格.求解模型（3.6）得，，，，，，，，，.由影子价格的结果，该企业决策者可以得到一些启发.由于值最大，所以首要考虑增加销往苏北的产品乙的销售量，这将会提高总利润；由于，其他销售安排无需变动，增加它们的销量对总利润没有影响.其次考虑各车间的生产安排.由于，所以首先考虑的是扩大工厂B第一车间生产产品乙的规模，其次是扩大工厂A第二车间生产规模和工厂B第一车间生产产品甲的规模，最后是扩大工厂A第一车间生产产品乙的规模.由于，所以不用扩大工厂A第一车间生产产品甲的规模，这对增加总利润没有帮助.4结语在运筹学中，线性规划对偶问题是一个重要的研究课题，在基础的对偶问题的基础上，世界对对偶问题的研究不断向更深更广的方向前进.本文主要对对偶问题、对偶单纯形法、对偶理论进行系统阐述，分析不同变量的变化对对偶问题的影响，通过实际案例进行分析，具体说明对偶规划的作用.对偶规划的理论研究和实际应用都具有不可替代的作用，对人类的生产生活具有重要贡献.参考文献[1]林诒勋.线性规划的对偶理论(Ⅰ)[J].郑州大学学报(自然科版),1964(01):9-20.[2]林锉云.非线性规划对偶理论[J].南昌大学学报(理科版),1978(00):77-84.[3]王长钰.一类凸对偶规划与运价为凸函数的运输问题[J].曲阜师院学报(自然科学版),1978(03):17-30.[4]胡幼青.影子价格问题介绍[J].价格理论与实践,1981(05):51-60.[5]魏力仁,米天林,李伯经.数学规划中的影子价格[J].湖南财经学院学报，1982(01):100-108.[6]刘序球.对偶规划问题的经济分析意义[J].江西财经学院学报,1983(02):90-94.[7]顾新华,连成平.试论国民经济控制系统的对偶问题[J].自动化学报，1986(04):333-338.[8]Z.A.Liang,H.X.Huang,P.M.Pardalos.Efficiencyconditionsanddualityforaclassofmultiobjectivefractionalprogrammingproblems[J].JournalofGlobalOpti-mization,2003,27:447-471.[9]岳冬萍.广义高阶不变凸多目标规划的最优性和对偶性[D].西安科技大学,2020.[10]D.Gale,H.W.Kuhn,A.W.Tucker.Linearprogrammingandthetheoryofgames[C].In:Koopamans(Ed)TC,”Activit