线性规划原问题及对偶问题的转化及其应用

线性规划原问题与对偶问题的转化及其应用摘要线性规划对偶问题是运筹学中应用较广泛的一个重要分支，它是辅助人们进展科学管理的一种数学方法.线性规划对偶问题能从不同角度为管理者提供更多的科学理论依据，使管理者的决定更加合理准确.本文主要探讨了线性规划原问题与对偶问题之间的关系、线性规划原问题与对偶问题的转化以及对偶理论的应用.本文的研究主要是将复杂的线性规划原问题转化成对偶问题进展解决，简化了线性规划问题，使人们能够快速的找出线性规划问题的最优解.关键词：线性规划；原问题；对偶问题；转化LinearProgrammingistheOriginalProblemandtheTransformationoftheDualProblemandApplicationsAbstract:Linearprogramminginoperationalresearchisresearchearlier,rapiddevelopmentandwideapplication,themethodisanimportantbranchofmature,itisoneofthescientificmanagementofauxiliarypeoplemathematicalmethod.Canfromdifferentanglestolinearprogrammingdualproblemforpolicymakerstoprovidemorescientifictheorybasis.Thisarticlemainlyprobesintothelinearprogrammingproblemandtherelationshipbetweenthedualproblem,linearprogrammingproblemandthetransformationofthedualproblem,theapplicationoflinearprogrammingdualproblem.Thisarticleistheplexoftheoriginalproblemintoitsdualproblemtobesolved,simplifiesthelinearprogrammingproblem,enablesustorapidlyfindtheoptimalsolutionoflinearprogrammingproblem.Keywords:linearprogramming;theoriginalproblem;thedualproblem;conversion目录1 引言12 文献综述12.1 国外研究现状12.2 国外研究现状评价22.3 提出问题23 预备知识23.1 对称形式的原问题33.2 非对称形式的原问题33.3 对偶问题的定义43.4 原问题转化为对偶问题的理论依据44 原问题与对偶问题的转化54.1 原问题与对偶问题的关系54.2 对称型原问题化为对偶问题64.3 对称型对偶问题转换为原问题94.4 非对称型原问题转化为对偶问题104.5 对偶问题的应用155 结论165.1 主要发现165.2 启示175.3 局限性175.4 努力方向17参考文献171引言线性规划问题是运筹学里的一个重要的分支，它的应用比拟广泛，因而是辅助人们进展现代科学管理的一种数学方法.随着线性规划理论的逐步深入，人们发现线性规划问题具有对偶性，即每一个线性问题都伴有另外一个线性问题的产生，两者相互配对，密切联系，反之亦然.我们把线性规划的这个特性称为对偶性.于是，我们将其中的一个问题称为原问题，另一个问题那么称为它的对偶问题.对偶性不仅仅是数学上的理论问题，而且也是线性规划中实际问题的在经济联系的必然反映.我们通过对对偶问题的深入研究，发现对偶问题能从不同角度对生产方案进展分析，从而使管理者能够间接地获得更多比拟有用的信息.2 文献综述2.1 国外研究现状在所查阅到的国外参考文献1-15中，有不少文章是探讨了原问题转化为对偶问题的方法以及对偶性质的证明，并在对偶理论的应用方面有所研究.如郝英奇，胡运权在1、10中主要介绍了线性规划中原问题与对偶问题中的一些根本概念，探究了实际问题中的数学模型以及解.君曼，巧玲，慧君，淑君等在2中探讨了对偶理论中互补松弛定理在各种情况下的使用方法,使学生更好地掌握互补松弛定理的含义和应用方法.胡运权，郭耀煌，殷志祥等在3、5中系统的介绍了线性规划中原始问题与对偶问题的两种形式.郭鹏，徐玖平等在6、8中用不同例子来说明了原问题转化为对偶问题的必要性.永新等在9、15中探讨了对偶问题的相关定理以及对偶问题的可行解和最优解之间的假设干性质.师正，王德胜在11中探讨了如何用计算机计算对偶问题的最优解.岳宏志，蔺小林，文喻等在12、14中探讨了对偶理论的证明过程，并用常见的例子来说明对偶理论的根本思想和解题方法.曾波，叶宗文在13中主要从经济管理的实际问题中阐述了线性规划的根本概念，根本原理，对偶理论，灵敏度分析等.2.2 国外研究现状评价文献1-15分别探讨了线性规划问题中原问题转化为对偶问题的理论依据以及如何利用对偶理论去解决实际生产问题.文献中主要探讨了对称型的原问题转化为对偶问题的方法.没有全面介绍非对称型的原问题与对偶问题之间转化的具体步骤，而且文献中对原问题转化为对偶问题的步骤提及甚少，大都一带而过，对应用中存在的问题也未给出详细深入的说明.2.3 提出问题在线性规划问题中,根据实际生产中具体情况的需要,我们常常要把原问题与它的对偶问题进展转换,以解决一些复杂的线性规划问题,因而对偶问题的应用较为广泛.但大局部书籍都只介绍了线性规划问题的根底知识，并没有给出原问题与对偶问题转换的具体步骤.因此本文主要探讨了线性规划原问题与对偶问题之间转化的具体步骤，体会不同类型原问题的转化过程.3 预备知识首先我先简单的介绍一些关于线性规划问题中的原问题和对偶问题的一些根本的知识.3.1 对称形式的原问题我们将满足以下条件的线性规划问题称之为具有对称形式的线性规划问题.这类问题的变量都具有非负约束，当目标函数求极大值时，它的约束条件都取“号，当目标函数求极小值时它的约束条件均取“号.因而，这类数学模型的特点是：1所有的决策变量都是非负的；2所有的约束条件都是“型；3目标函数是最大化类型.线性规划原问题的对称形式的一般形式1为：maxzc1x1c2x2cnxnaiiXiai2X2a2i Xia 22 X2stami Xiam2 X2ainXnbia2nXnb2(3.i)amn XnbmXj0(ji,2,n)3.2 非对称形式的原问题不是所有的线性规划问题都具有对称的形式，我们将没有对称形式的线性规划问题称之为非对称形式的线性规划问题.非对称形式的线性规划问题指的是一般情况下的线性规划问题，即是目标函数值求极小或者求极大；约束条件=；变量之。，。或是无限制的随意的组合.例如:(3.2)maXzciXic2X2c3X3aiiXiai2X2ai3X3a2ixia22X2a23X3a3ixia32x2a33X3s.tbib2b3Xi0,x20,x3无约束3.3 对偶问题的定义在运筹学中，关于对线性规划的对偶规划给出的定义2如下.设给定的线性规划为:maxzCXstAX bX 0(3.2)其中Xxx2,Xn , Aa。m n , bbib, ,bm T , CC1,C2,cn因此，定义它的对偶问题为:minwYbs.tYAY(3.4)其中Yyi,y2,ym是行向量.（3.4应对偶问题，（3.3）是原问题，（3.3府（3.4冷在一起我们就称为是一对对称形式的对偶规划问题3.4 原问题转化为对偶问题的理论依据我们根据线性规划问题中约束条件和变量的对应关系，统一归纳为下表13所示:工程原问题对偶问题对偶问题原问题A约束系数矩阵约束系数矩阵的转置b约束条件右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件右端项向量目标函数nmaxz$Xjjimminwbiyii1Xj(j1,n)Xj0变量jxj0Xj无约束有n个(j1,n)maijyiCji1m约束条件aijyiCji1maijyiCji1有m个(i1,m)naijXjbij1约束条件n一a。Xjbij1najXjbij1yi(i1,m)yi0变量y0yi无约束表14原问题与对偶问题的转化一对对偶的线性规划问题表示了同一个问题的两个侧面，是从两个角度对同一个研究对象提出的极值问题，两类极值的问题都具有一样的目标函数值.我们发现在很多时候求解对偶问题比原问题更加容易，为决策者提供更多的科学理论依据，因此我们常常需要把原问题转化为对偶问题.4.1 原问题与对偶问题的关系一对对偶的线性规划问题具有相互对应的关系：1原问题中的目标函数值是max,约束条件是“的形式；对偶问题的目标函数值为min,约束条件是“的形式.2原问题的价值系数和对偶问题的右端项对应，原始问题的右端项和对偶问题的价值系数对应.3原问题的变量和对偶问题的约束条件对应，即，原问题中有n个变量，那么对偶问题就有n个约束条件；原问题有m个约束条件，那么对偶问题就有m个变量.4对偶问题的系数矩阵就是原问题的系数矩阵的转置.用矩阵表示，原问题为：maxzCXs.t.AX bX0那么对偶问题为：minwYbs.t.YA CY0需要注意的是，我们所讨论的对偶问题一定是指一对问题，而原问题和对偶问题是相对的，它们互为对偶问题，一个问题可以是原问题也可以是对偶问题.4.2 对称型原问题转化为对偶问题当线性规划问题为一般形式3.1时，我们将根据下面的四条规那么转换为它的对偶问题： 1原问题和它的对偶问题之间的系数矩阵互为转置. 2原问题中变量的个数等于它的对偶问题的约束条件的个数. 3原问题的右端常数就是对偶问题的目标函数的系数. 4原问题的目标函数求极大时，约束条件是“类型，而它的对偶问题的目标函数求极小，约束条件那么为“类型.因此，它的对偶问题可以转变为如下的形式4：min w b1y1b2 y2bm yma11y1a21y2am1ymC1a12y1a22y2am2ymC2s.t.a1ny1a2ny2amnYmCny0(i1,n)例1生产方案问题一公司加工生产甲，乙两种产品，它的市场前景非常的好，销路也不成问题，各种制约因素主要有技术工人、设备台时和原材料供给.制造每吨产品的资源消耗系数、每大的资源限量和售价等参数如表2所示.问题：的这家公司应该怎样制定每天的生产方案，才能使它的产量得到最大？甲产品乙产品资源限量人力86320设备68260原材料410300售价元/公斤90150表2分析：为了建立此问题的数学模型，第一，要选定决策变量.第二，要确定问题的目标，即用来评价不同方案优劣的标准，这种目标总是决策变量的函数，称为目标函数.第三，我们把要确定到达目标时所受的限制条件，称之为约束条件.这里要决策的问题是，在现有人力、设备、矿石的限制下，如何确定产量使得产值自大？设X1和X2分别表示该公司A,B产品的数量，用z表示产值，那么每天的产值表示为z90x1150X2,使其最大化，即maxz90x1150X2,称为目标函数.将制约因素表达出来，即有：人力不超过320工时，为8x16X2320;设备不超过260台时有，6x18x2260;原材料不超过 300公斤有，4x1 10x2300 。表述限制条件的数学表达式称为约束条件，由此该问题的数学模型可表示为：maxz90x1150x28x16x23206x18x2260s.t.4x110x2300x1,x20上面的问题是一个典型的求解利润最大化的生产方案的问题.题中，“max是“maximize的缩写，意思是“最大化；st是subjectto单词的缩写，表示“满足于.因此，上述模型的含义是：在给定的条件限制下，求出使目标函数值到达最大的x1,x2的值.从数学模型中看出，上面的例题具有下面的三个特征：(1) 用一组决策变量表示问题的一个方案，决策变量的一组取值代表一个具体的方案.通常状况下，决策变量的取值是非负的，局部情况下，还要求决策变量取值为整数.(2) 每个问题都有一个目标，而且都可以用决策变量的线性函数表示.根据问题的不同，要求目标实现最大或者最小.(3) 决策变量都满足一定的约束条件，而且都可以用决策变量的线性等式或者不等式表示.具备以上三个要素的问题称为线性规划问题，简单地讲，线性规划问题就是求一个线性目标函数在满足一组线性等式或不等式方程约束条件下的极值问题.例2一公司加工生产甲，乙两种产品，市场前景非常的很好，销路也不成问题，各种制约因素主要有技术工人、设备台时和原材料供给.制造每吨产品的资源消耗系数、每天的资源限量和售价等参数如表3所示.现在公司有意转换经营方式，现在将各种资源出租转让，我们假定市场广阔.问题：公司转让资源的价格底线是什么?甲产品乙产品资源限量人力86320设备68260原材料410300售价元/公斤90150表3我们将例1叫做原问题，将例2叫做对偶问题.原问题的数学模型是:maxz90x1150x28x16x2320(4.1)6x18x2260s.t.4x110x2300x1,x20分析：现在在对偶问题中我们需要考虑的是，将例题中的三种资源租让或者转出,应该是不少于原来的收益的，否那么这家公司宁愿选择自己继续生产.所以，决策的约束条件应该是：出租制造的产品消耗掉的资源不能少于自己生产该产品的收益；目标函数应该是：资源转让的收益底线.所以，我们设y1,y2,y3分别为人力、设备台时和原材料的转让或者出租的价格.由于生产1公斤A产品需消耗8个工时，6个台时和4公斤的原材料，可创造产值90元.所以出让生产A产品资源至少应带来90元的产值，即8y16y24y390同理，生产1公斤B产品需耗时4个工时，6个台时和8公斤的原材料，可创造产值150元，出让这些资源所获得的销售收益应满足6y18y210y3150上面两个不等式保证了“出售资源所获得的收益不低于自己组织生产所能创造的收益但是也不能随意要价，否那么由于市场的调节作用将会使资源卖不出去.因此目标函数应该是表达所获的收益的底线，即minw320y1260y2300y3解：从转让资源的方面考虑，得到此问题的数学模型应是minw320y1260y2300y38y16y24y390s.t.6y18y210y3150(4.2)y1,y2,y30评注：通过分析我们可以知道，重新得到的对偶问题是一个非常重要的线性规划问题，它对问题的分析又加深了一步，减少了管理工作中的盲目性，为决策者提供了更多的科学依据.原问题与对偶问题之间是相互对应的关系，原问题与对偶问题是从不同的角度对同一问题进展了分析研究.它们之间存在着很密切的关系，这些关系我们将在通过分析可知.从形式上我们可以看到，在原问题中，制订生产方案有3种设备的总工时构成规划的资源约束，可建立3个约束不等式，其中2种要生产的产品将构成决策变量；而在它的对偶问题中，原问题里的3个资源约束所对应的资源估价正好构成了对偶问题的决策变量，原问题中的2个决策变量对应的2种产品那么构成了对偶问题的2个约束条件.小结：通过分析可以得出，问题(4.1)和问题(4.2)具有下面的关系：(1)问题(4.1)的目标函数值求极小；问题(4.2)的目标函数值求极大.(2)问题(4.1)有2个决策变量和3个主约束条件，问题(4.2)有3个决策变量和2个主约束条件.即问题(4.1)中决策变量的个数和问题(4.2)中主约束条件的个数相等，问题(4.1)中的主约束条件的个数和问题(4.2)中的决策变量的个数是相等.原因是，问题(4.1)的系数矩阵和问题(4.2)的系数矩阵是互为转置的.(3)问题(4.1)的价格指标与问题(4.2)的资源指标对应，且问题(4.1)的第i个价格指标与问题(4.2)的第i个资源指标对应.(4)问题(4.1)的资源指标与问题(4.2)的价格指标对应，且问题（4.1）的第i个资源指标与问题（4.2）的第i个价格指标对应.（5）（4.（1） 的主约束条件是“型的约束条件；而问题（4.2）的主约束条件是“型4.3对称型对偶问题转换为原问题对偶理论中关于线性规划问题里，对偶问题的对偶就是原问题设原问题为：那么对偶问题为：maxzAX s.t.XminwCX0b (4.3)Yb而对偶问题的对偶为:YA C s.t.Y0(4.4)max fCZAZ s.t.Zb(4.5)4.3，4.5的形式是完全一致，因而，原问题和它的对偶问题是互为对偶的关系，也即是对偶问题的对偶就是原问题4.4 非对称型的原问题转化为对偶问题线性规划有时以非对称型出现，那么如何从原始问题写出它的对偶问题，将是下面要讨论的问题.在非对称形式的规划问题中，可以按照下面的对应规那么直接给出它的对偶问题1将线性规划问题统一为“max,或“min,的形式，而其中的等式约束按照下面2，3中的方法进展处理.2假设原问题的某个约束条件时等式约束，那么对偶问题中与此约束对应的那个变量取值没有非负限制的.3假设原问题的某个变量的值没有非负限制，那么在它的偶问题中与此变量对应的约束条件是等式约束.2做一些必要的说明，对于规那么3可以给出类似的证明设原问题中的第一个约束是等式：那么，此等式与下面的两个不等式等价：这样，原问题可以写成a11x1a11x1a11x1maxzc1x1s.t.a11x1a11x1am1 x1xj 0, ja1n xna1n xna1n xnb1b1b1cn xna1nxnb1a1nxnb1amnxnbm1,2, ,m因为就转换为对称形式，所以可以直接写出对偶问题min w b1y1 b1y1 b2y2bmymaiy1aiiyia12 ylal2 y1s.t.alnyialnyiyi,yi,y2, ,ymam1ym ciam2ymciamn y mci0, y1没有非负限制这里，我们把七看作y1y；y；,于是必没有限制，规那么2的说明完毕.将非对称的线性规划问题转换为对称形式时可能会有以下几种情形5:1目标函数的转换设minzc1x1c2x2cnxn,令zz,那么将求最小值的问题转换为求最大值的问题，即将求minz转化为求maxz,且maxzc1x1c2x2cnxn.反之，要将极大化目标函数转化为极小化目标函数，也可以直接给原目标函数乘以-1,把maxz改写成minz.2主约束条件的转换nbi或 ajxjbi,转化为j 1nA.将“型或者“的约束条件ajxjj1型或者”型的约束条件时，直接将原约束条件两边同乘以一1,即nnaijxjbi或aijxjbij1j1nB.将“二型的约束条件ajxjbi转化为“型或者”型的约束条件时,j1首先将其写成两个不等式约束条件,然后再转化为所需形式的不等式约束条件，即:nnajxjj 1aij xj bi nj 1ajxjj 1naij x j bi1naijxjj 1binajxj j 1najxjj 1bi3非负约束条件的转换A.假设变量着没有非负限制，取值可正可负，这时可设两个非负变量xj和xj,令XjXjXj,Xj,Xj0B.假设变量Xj0,可令：XjXj,Xj0例3:请写出以下的线性规划问题的对偶问题maXzX12x25x3XiX322x1x26x36s.t.x1x23x3X1,X2,X30分析：首先将上述非对称型问题转换为我们所熟悉的对称型问题，然后按照对称型问题的方法将原问题转化为对偶问题。第一，在第一个约束条件的两边同乘以-1.第将第三个约束方程分解成x1X23X31和X1X23X31再将约束条件x1x23x31两边同时乘以-1,即x1x23x3解：原问题转换为如下的对称型:maxzx12x25x3x1X322x1x26x36s.t.x1x23x313X30现在四个约束，分别对应四个对偶变量y1,y2,y3,y3,按表1可得到下面的对偶问题:minw2y16y2VbV3y12y2y3y31y2V3V32y16y23y33y35y1,y2y3,y30再设y3V3、3,代入上面的数学模型就可得出原问题的对偶问题为：minw2y16y2y3yi2y2y1,y2y32s.t.y16y23y35y1,y20;y3无约束评注：将上面对偶问题同原问题比照发现，无论是对称的形式或者是非对称形式的线性规划问题在写出它的对偶问题时，表格中前四行的对应关系都适应，区别的只是约束条件的形式与其对应变量的取值.4.5 对偶问题的应用设有如下线性规划问题：maxz20x18x26x38x13x25x32592x1x250st.4x13x3150为0,j1,2,3它的最优解为X(0,50,50,9,0,0)T,求对偶问题的最优解.解：根据对偶规那么，我们很容易的写出了原问题的对偶问题：minw259y150y2150y38y12y24y3203y1y8s.t.5y13y36y1,y2,y3根据对偶性质，有如下对应关系：原问题中的原始变量原问题中的松弛变量x10,x250,x350x49,x20,x30对偶问题的剩余变量对偶问题的原始变量yi0,y20,y30V40,y50,y60将对偶问题标准化为:minw259yi50y2150y38yi2y24y3y203yiy2y58s.t5yi3y3y6yj0,j1,2,3,4,5,6由于yi,y5,y6为零，上述约束条件简化为：2y24y3V420y283y36由此的对偶问题的最优解为：yi0,y28,y32,y,4,y0,y60评注：线性规划问题中，有时为了计算变得简单，我们常常需要把线性规划问题的原问题转换为它的对偶问题进展解决.5结论5.1 主要发现对偶理论是线性规划问题的重要容之一，任何一个线性规划都有一个伴生的线性规划，称之为原问题的对偶规划问题.本文主要探究了原问题与对偶问题之间的关系，原问题与对偶问题转化的具体步骤和对偶理论的应用.用科学的方法对生产方案进展预测，及时调整、科学决策，使企业决策更加合理5.2 启示线性规划中常常用到对偶问题，它的思想方法是利用线性代数的方法找出线性规划模型中目标函数与约束条件的可行解.同时利用对偶问题能够快速的找出问题的最优解，对解的特性的判断起关键作用.在计算工具不断开展的今天，用对偶问题处理生产、经营上的问题已经越来越广泛.企业经营者可以根据市场的具体情况，建立相应的数学模型，然后用对偶问题加以分析，科学的为决策者提供理论依据.5.3 局限性本文主要研究了对称型与非对称型的线性规划原问题转化为对偶问题的具体步骤对偶问题是一组线性约束条件下的线性规划问题，它只能处理单个目标函数的优化问题而实际问题中往往要考虑多个目标函数，这些目标函数之间可能是相互矛盾、相互排斥的.5.4 努力方向虽然对偶问题的适用围很大，但受实际问题中约束条件的制约，只能处理单目标的优化问题,所以研究线性规划最优解的求解方法是有必要的.因此，线性规划的对偶理论，单纯形法求最优解这些都值得进一步的研究.-word.zl-参考文献1郝英奇.实用应筹学M.:中国人民大学,2011:70-113.2君曼，巧玲，慧君，淑君，秀花.线性规划中原问题与对偶问题转化方法探究J.轻工业学院学报，2001,(2):44-47.3胡运权，郭耀煌.运筹学教程M.：清华大学，2001:50-78.4,成松，永满，宋海草.线性规划中原问题与对偶问题转化的思考J石河子大学院，2010,(7):192-194.5殷志祥，周维.运筹学教程M.：中国科学技术大学，2012:38-64.6牛映武，郭鹏.运筹学M.3版.:交通大学,2013:6-70.7叶扩会.对偶问题转化的教学研究J.学院学报，2012,(2):53-57.8徐久平，胡知能.运筹学M.2版.:科学,2006:30-55.9永新.对偶规划问题根本性质的综合分析及应用J工程学院学报，2008,(3):84-86.10胡运权.运筹学根底及应用M.4版.:高等教育，2004:48-74.11师正，王德胜关于对偶问题及对偶性质J师大学，1996,(2):43-47.12岳宏志，蔺小林，勇，高晓艳.运筹学M.:东北财经大学,2012:105-158.13曾波，叶宗文.线性规划中原问题与其对偶问题之间的转换-计算机解决方案J工商大学学报伯然科学版),2005(5):496-474.14文喻，朱德通，徐成贤.运筹学根底M.:科学,2013:36-56.15白云线性规划中资源的影子价格与边际价值J商业高等专科学校,2007:120-121.在论文即将完成之际，首先感我的指导教师程教师，从开场选题到论文的顺利完成，都离不开程教师的细心指导和关心.他严肃的科学态度，严谨的治学精神，精益求精的工作作风，深深地感染和鼓励着我在论文的写作过程中，在我每次遇到困难时，总能得到程教师的耐心指导，让我豁然开朗.在我情绪低落时，教师总是那么热忱的给予我深深的鼓励和支持.在此向程教师深深地鞠上一躬，感程教师长久以来对我的关心和指导.！同时，我要向数学与信息科学学院的全体教师说一声：你们，在你们的精心指导教育下，我才能得以在这四年里学到了珍贵的知识，你们的教导让我终生受益，在此请承受我诚挚的意.也感学院给我创造了优越的条件，在此向学院的领导表示我最诚挚的敬意！感我们小组成员林瑶，周秀凤，向春运等同学对我论文所做出的帮助，也感全班同学这四年大学生活中在生活上及学习上给与我的帮助.