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

线性规划原问题与对偶问题的转化及其应用摘要线性规划对偶问题是运筹学中应用较广泛的一个重要分支，它是辅助人们进展科学管理的一种数学方法.线性规划对偶问题能从不同角度为管理者提供更多的科学理论依据，使管理者的决定更加合理准确.本文主要探讨了线性规划原问题与对偶问题之间的关系、线性规划原问题与对偶问题的转化以及对偶理论的应用.本文的研究主要是将复杂的线性规划原问题转化成对偶问题进展解决，简化了线性规划问题，使人们能够快速的找出线性规划问题的最优解.关键词：线性规划；原问题；对偶问题；转化LinearProgrammingistheOriginalProblemandtheTransformationoftheDual

ProblemandApplicationsAbstract:Linearprogramminginoperationalresearchisresearchearlier,rapiddevelopmentandwideapplication,themethodisanimportantbranchofmature,itisoneofthescientificmanagementofauxiliarypeoplemathematicalmethod.Canfromdifferentanglestolinearprogrammingdualproblemforpolicymakerstoprovidemorescientifictheorybasis.Thisarticlemainlyprobesintothelinearprogrammingproblemandtherelationshipbetweenthedualproblem,linearprogrammingproblemandthetransformationofthedualproblem,theapplicationoflinearprogrammingdualproblem.Thisarticleisthecomplexoftheoriginalproblemintoitsdualproblemtobesolved,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］为：TOC\o"1-5"\h\z\o"CurrentDocument"maxz-cx+cxdFcx1122nnax+ax++ax<b1111221nn1ax+ax++ax<b2112222nn2(3.1)s.t〈：(3.1)ax+ax++ax<bm11m22mnnmx>0(j=1,2,—,n)3.2非对称形式的原问题不是所有的线性规划问题都具有对称的形式，我们将没有对称形式的线性规划问题称之为非对称形式的线性规划问题.非对称形式的线性规划问题指的是一般情况下的线性规划问题，即是目标函数值求极小或者求极大；约束条件N,-,土；或是无限制的随意的组合.例如：maxz=cx+cx+cxTOC\o"1-5"\h\z112233ax+ax+ax<b1111221331ax+ax+ax=b(3.2)st<2112222332ax+ax+ax<b3113223333x>0,x<0,x无约束

3.3对偶问题的定义(3.2)在运筹学中，关于对线性规划的对偶规划给出的定义⑵如下.设给定的线性规划为：maxz-CX(3.2)IAX<b

s.t<(3.2)IX>0其中X=(x,x，…其中X=(x,x，…,x>，12nA=C.)司mxn因此，定义它的对偶问题为:minw=Yb(3.4)\YA>Cs.t<|Y>0其中Y=（y,y，…,y）是行向量.（3.4）是对偶问题，（3.3）是原问题，（3.3）与（3.4）合在一起我12m们就称为是一对对称形式的对偶规划问题.(3.4)3.4原问题转化为对偶问题的理论依据我们根据线性规划问题中约束条件和变量的对应关系，统一归纳为下表1[3]所示:工程原问题〔对偶问题〕对偶问题〔原问题〕A约束系数矩阵约束系数矩阵的转置b约束条件右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件右端项向量目标函数切maxz=cxj=iminw=祝byi=i变量＜"(j=1,—,n)x>0x<0x.无约束有n个(j=1,…,n)^Eay>cij1ji=1Eay<cij1ji=1Eay=ci1Ji=1J＞约束条件约束条件V有刀个(，=1,…，m)Zax<b,,,,jjIj=1Eax>bijjij=1Eax.=b、j=1y,(i=1,…，m)y,>0yi<0y,无约束＞变量表14原问题与对偶问题的转化一对对偶的线性规划问题表示了同一个问题的两个侧面，是从两个角度对同一个研究对象提出的极值问题，两类极值的问题都具有一样的目标函数值.我们发现在很多时候求解对偶问题比原问题更加容易，为决策者提供更多的科学理论依据，因此我们常常需要把原问题转化为对偶问题.4.1原问题与对偶问题的关系一对对偶的线性规划问题具有才目互对应的关系：〔1〕原问题中的目标函数值是max，约束条件是“＜〃的形式；对偶问题的目标函数值为min,约束条件是“2”的形式.〔2〕原问题的价值系数和对偶问题的右端项对应，原始问题的右端项和对偶问题的价值系数对应.〔3〕原问题的变量和对偶问题的约束条件对应，即，原问题中有〃个变量，那么对偶问题就有〃个约束条件；原问题有m个约束条件，那么对偶问题就有m个变量.〔4〕对偶问题的系数矩阵就是原问题的系数矩阵的转置.用矩阵表示，原问题为：maxz=CX[AX<bs.t.<[X>0那么对偶问题为：minw=Yb(YA>Cs.t.<\Y>0需要注意的是，我们所讨论的对偶问题一定是指一对问题，而原问题和对偶问题是相对的，它们互为对偶问题，一个问题可以是原问题也可以是对偶问题.4.2对称型原问题转化为对偶问题当线性规划问题为一般形式〔3.1〕时，我们将根据下面的四条规那么转换为它的对偶问题：〔1〕原问题和它的对偶问题之间的系数矩阵互为转置.〔2〕原问题中变量的个数等于它的对偶问题的约束条件的个数.〔3〕原问题的右端常数就是对偶问题的目标函数的系数.〔4〕原问题的目标函数求极大时，约束条件是“<‘‘类型，而它的对偶问题的目标函数求极小，约束条件那么为“>''类型.因此，它的对偶问题可以转变为如下的形式[4]:minw=by+bydFby1122mmay+ay+—+ay>c111212m1m1ay+ay+—ay>c121:222m2m2ay+ay+—ay>c1n12n2mnmny>0(i=1,…,n)例1生产方案问题云南一公司加工生产甲，乙两种产品，它的市场前景非常的好，销路也不成问题，各种制约因素主要有技术工人、设备台时和原材料供应.制造每吨产品的资源消耗系数、每天的资源限量和售价等参数如表2所示.问题：云南的这家公司应该怎样制定每天的生产方案，才能使它的产量得到最大？甲产品乙产品资源限量人力86320设备68260原材料410300售价〔元/公斤〕90150表2分析：为了建立此问题的数学模型，第一，要选定决策变量.第二，要确定问题的目标，即用来评价不同方案优劣的标准，这种目标总是决策变量的函数，称为目标函数.第三，我们把要确定到达目标时所受的限制条件，称之为约束条件.这里要决策的问题是，在现有人力、设备、矿石的限制下，如何确定产量使得产值自大？设气和七分别表示该公司A，B产品的数量，用z表示产值，那么每天的产值表示为z=90气+150%，使其最大化，即maxz=90x+150x，称为目标函数将制约因素表达出来，即有：人力不超过320工时，为8x+6x<320；设备不超过260台时有，6x+8x<260；原材料不超过300公斤有，4气+10%<300。表述限制条件的数学表达式称为约束条件，由此该问题的数学模型可表示为:maxz-90x+150x'8x+6x<3206x+8x<260s.t.<124x+10x<300x,x>0.题中，“max〃是上面的问题是一个典型的求解利润最大化的生产方案的问题“maximize"的缩写，意思是“最大化〃；“s.t.〃是〃subjectto”单词的缩写，表示“满足于〃.因此，上述模型的含义是：在给定的条件限制下，求出使目标函数值到达最大的尤，.题中，“max〃是足于从数学模型中看出，上面的例题具有下面的三个特征:⑴用一组决策变量表示问题的一个方案，决策变量的一组取值代表一个具体的方案.通常状况下，决策变量的取值是非负的，局部情况下，还要求决策变量取值为整数.(2)每个问题都有一个目标，而且都可以用决策变量的线性函数表示.根据问题的不同，要求目标实现最大或者最小.(3)决策变量都满足一定的约束条件，而且都可以用决策变量的线性等式或者不等式表示.具备以上三个要素的问题称为线性规划问题，简单地讲，线性规划问题就是求一个线性目标函数在满足一组线性等式〔或不等式方程〕约束条件下的极值问题.例2云南一公司加工生产甲，乙两种产品，市场前景非常的很好，销路也不成问题，各种制约因素主要有技术工人、设备台时和原材料供应.制造每吨产品的资源消耗系数、每天的资源限量和售价等参数如表3所示.现在公司有意转换经营方式，现在将各种资源出租转让，我们假定市场广阔.问题：公司转让资源的价格底线是什么？甲产品乙产品资源限量人力86320设备68260原材料410300售价〔元/公斤〕90150表3我们将例1叫做原问题，将例2叫做对偶问题.原问题的数学模型是:maxz-90x+150x'8x+6x<3206x+8x<260s.t.<12(4.1)4x+10x<300*)12x,x>0分析：现在在对偶问题中我们需要考虑的是，将例题中的三种资源租让或者转出，应该是不少于原来的收益的，否那么这家公司宁愿选择自己继续生产.所以，决策的约束条件应该是：出租制造的产品消耗掉的资源不能少于自己生产该产品的收益；目标函数应该是：资源转让的收益底线.所以，我们设y，y，J分别为人力、设备台时和原123材料的转让或者出租的价格.由于生产1公斤A产品需消耗8个工时，6个台时和4公斤的原材料，可创造产值90元.所以出让生产A产品资源至少应带来90元的产值，即8y1+6y2+4y3>90同理，生产1公斤B产品需耗时4个工时，6个台时和8公斤的原材料，可创造产值150元，出让这些资源所获得的销售收益应满足6y1+8y2+10y3>150上面两个不等式保证了“出售资源所获得的收益不低于自己组织生产所能创造的收益.但是也不能随意要价，否那么由于市场的调节作用将会使资源卖不出去.因此目标函数应该是表达所获的收益的底线，即minw=320*+260七+300j3解：从转让资源的方面考虑，得到此问题的数学模型应是minw=320j1+260七+300j3'8j+6j+4j>90s.t.<6j+8j+10j>150(4.2)j:j,/>03I123评注：通过分析我们可以知道，重新得到的对偶问题是一个非常重要的线性规划问题，它对问题的分析又加深了一步，减少了管理工作中的盲目性，为决策者提供了更多的科学依据.原问题与对偶问题之间是相互对应的关系，原问题与对偶问题是从不同的角度对同一问题进展了分析研究.它们之间存在着很密切的关系，这些关系我们将在通过分析可知.从形式上我们可以看到，在原问题中，制订生产方案有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)的第，个价格指标与问题(4.2)的第，个资源指标对应.(4)问题(4.1)的资源指标与问题(4.2)的价格指标对应，且问题(4.1)的第，个资源指标与问题(4.2)的第i个价格指标对应.(5)问题(4.1)的主约束条件是“X'型的约束条件；而问题(4.2)的主约束条件是“<〃型的约束条件.4.3对称型对偶问题转换为原问题对偶理论中关于线性规划问题里，对偶问题的对偶就是原问题.设原问题为:maxz-CXIAX<b

s.t.<(4.3)IX>0那么对偶问题为:IYA>C

s.t.\(4.4)|Y>0而对偶问题的对偶为:maxf=CZIAZ<bs.tA(4.5)|Z>0由此可见，线性规划问题〔4.3],〔4.5〕的形式是完全一致，因而，原问题和它的对偶问题是互为对偶的关系，也即是对偶问题的对偶就是原问题.4.4非对称型的原问题转化为对偶问题线性规划有时以非对称型出现，那么如何从原始问题写出它的对偶问题，将是下面要讨论的问题.在非对称形式的规划问题中，可以按照下面的对应规那么直接给出它的对偶问题:〔1〕将线性规划问题统一为“max,<〃或“min,>〃的形式，而其中的等式约束按照下面〔2〕，〔3〕中的方法进展处理.〔2〕假设原问题的某个约束条件时等式约束，那么对偶问题中与此约束对应的那个变量取值没有非负限制的.〔3〕假设原问题的某个变量的值没有非负限制，那么在它的偶问题中与此变量对应的约束条件是等式约束.下面对于规那么〔2〕做一些必要的说明，对于规那么〔3〕可以给出类似的证明设原问题中的第一个约束是等式：axHFax=b1111nn1那么，此等式与下面的两个不等式等价：axFFax>bTOC\o"1-5"\h\z1111nn1axFFax<b1111nn1这样，原问题可以写成\o"CurrentDocument"maxz-cxFFcx11nnaxFFax<b1111nn1_ax—.…_ax<—b.1111nn1s.t.<:axFFax<bm11mnnmx.>0,j=1,2,…，m因为就转换为对称形式，所以可以直接写出对偶问题minw=by'—by''+byFFby111122mm

ay'-ay"HFay>ci111mlm1ay'-ay"FFay>c1121m2m1s.t.<s.t.<ay'-ay"FFay>c1n1n1mnm11y',y",y，…,y>0,y没有非负限制112m1这里，我们把看作y=y'-y"，，于是y没有限制，规那么〔2〕的说明完毕.将非对称1111的线性规划问题转换为对称形式时可能会有以下几种情形[5]:〔1〕目标函数的转换设minz-cx+cxFFcx，令z'--z，那么将求最小值的问题转换为求最大1122nn值的问题，即将求minz转化为求max乙，且maxz--cx-cxcx.反之，要将1122nn极大化目标函数转化为极小化目标函数，也可以直接给原目标函数乘以-1，把maxz'改写成minz.〔2〕主约束条件的转换A.将“V”型〔或者“>〃〕的约束条件工A.将“V”型〔或者“>〃〕的约束条件工ax<bj-1〔或工ax>b〕，转化为

ijjij=1“>〃型〔或者“<”型〕的约束条件时，直接将原约束条件两边同乘以：，即Ea.x.>-bj-1〔或2^ax<-b〕j-1B.将“二〃型的约束条件l^ax-b转化为“>〃型或者“<”型的约束条件时，j-1首先将其写成两个不等式约束条件，然后再转化为所需形式的不等式约束条件，即：Jax>Jax>bPST一f£ax>bijjiijji<j-1—5j-1-<£ax<b-£ax>-biijiijjiIj-1Ij-1I£ax-bijjzj-1-£ax<-bj-1£axijjj-1〔3〕非负约束条件的转换A.假设变量Xj没有非负限制，取值可正可负，这时可设两个非负变量*和r，令工=工'一X",X',x">0jjjjjB.假设变量x<0，可令：x=-x',x'>0jjjj例3:请写出以下的线性规划问题的对偶问题maxz=x+2x-5xx+x>22x+x+6x<6

123x—x+3x=1

123x,x,x>0分析：首先将上述非对称型问题转换为我们所熟悉的对称型问题，然后按照对称型s.t.<问题的方法将原问题转化为对偶问题。第一，在第一个约束条件的两边同乘以-1.第二，将第三个约束方程分解成x—x+3x<1和x—x+3x>1再将约束条件123123x—x+3x>1两边同时乘以-1，即—x+x—3x<—1123123解：原问题转换为如下的对称型:maxz=x+2x-5x—x—xV—22x+x+6x<612x—x+3x<1—x+x—3x<—1123x,x,x>0s.t.<现在四个约束，分别对应四个对偶变量j,j,y,j■■，按表1可得到下面的对偶问题:1233minw=—2j+6j+y—y，1233s.t.<一j+2V+j'一j;>11233j2—j3一j3>2—匕+6j+3j'一3j；>—51233j,jj',j">0侦1233再设y-y，=j，代入上面的数学模型就可得出原问题的对偶问题为：333minw=-2j+6j+jf+2J2+J3-1J-J-2s.t.<23—j+6j+3j--5123j,j-0;j无约束123评注：将上面对偶问题同原问题比照发现，无论是对称的形式或者是非对称形式的线性规划问题在写出它的对偶问题时，表格中前四行的对应关系都适应，区别的只是约束条件的形式与其对应变量的取值.4.5对偶问题的应用设有如下线性规划问题：maxz=20x+8x+6x'8x+3x+5x<2592x+x<50

s.t.<124x+3x<150

13x.-0,j=1,2,3它的最优解为X=(0,50,50,9,0,0)t，求对偶问题的最优解.解：根据对偶规那么，我们很容易的写出了原问题的对偶问题:minw=259j+50j+150j|8j1+2j2+4j3-20S.t3j1+j2-85j+3j-6

13Ij「j2,j3-根据对偶性质，有如下对应关系：原问题中的原始变量原问题中的松弛变量

x=0,x=50,x=50x=9,x=0,x=0对偶问题的剩余变量对偶问题的原始变量y1=0,y2N0,y3N0y4N0,y5=0,y6=0将对偶问题标准化为:minw=259y+50y+150y'8y+minw=259y+50y+150y'8y+2y+4y-y=2012343y+y-y=81255y+3y+y=6136由于y,y,y为零，上述约束条件简化为：156由此的对偶问题的最优解为：y=0,y=8,y=2,y=4,y=0,y=0123456评注：线性规划问题中，有时为了计算变得简单，我们常常需要把线性规划问题的原问题转换为它的对偶问题进展解决.5结论5.1主要发现对偶理论是线性规划问题的重要内容之一，任何一个线性规划都有一个伴生的线性规划，称之为原问题的对偶规划问题.本文主要探究了原问题与对偶问题之间的关系，原问题与对偶问题转化的具体步骤和对偶理论的应用.用科学的方法对生产方案进展预测，及时调整、科学决策，使企业决策更加合理.5.2启示线性规划中常常用到对偶问题，它的思想方法是利用线性代数的方法找出线性规划模型中目标函数与约束条件的可行解.同时利用对偶问题能够快速的找出问题的最优解，对解的特性的判断起关键作用.在计算工具不断开展的今天，用对偶问题处理生产、经营上的问题已经越来越广泛.企业经营者可以根据市场的具体情况，建立才目应的数学模型，然后用对偶问题加以分析，科学的为决策者提供理论依据.5.3局限性本文主要研究了对称型与非对称型的线性规划原问题转化为对偶问题的具体步骤.对偶问题是一组线性约束条件下的线性规划问题，它只能处理单个目标函数的优化问题.而实际问题中往往要考虑多个目标函数，这些目标函数之间可能是相互矛盾、相互排斥的.5.4努力方向虽然对偶问题的适用范围很大，但受实际问题中约束条件的制约，只能处理单目标的优化问题，所以研究线性规