《线性规划原问题与对偶问题地转化及其应用》由会员分享，可在线阅读，更多相关《线性规划原问题与对偶问题地转化及其应用（21页珍藏版）》请在金锄头文库上搜索。
1、word线性规划原问题与对偶问题的转化与其应用摘 要线性规划对偶问题是运筹学中应用较广泛的一个重要分支，它是辅助人们进展科学管理的一种数学方法.线性规划对偶问题能从不同角度为管理者提供更多的科学理论依据，使管理者的决定更加合理准确.本文主要探讨了线性规划原问题与对偶问题之间的关系、线性规划原问题与对偶问题的转化以与对偶理论的应用.本文的研究主要是将复杂的线性规划原问题转化成对偶问题进展解决，简化了线性规划问题，使人们能够快速的找出线性规划问题的最优解.关键词：线性规划；原问题；对偶问题 ；转化Linear Programming is the Original Problem and the
2、Transformation of the Dual Problem and ApplicationsAbstract:Linear programming in operational research is research earlier, rapid development and wide application, the method is an important branch of mature, it is one of the scientific management of auxiliary people mathematical method. Can from di
3、fferent angles to linear programming dual problem for policy makers to provide more scientific theory basis. This article mainly probes into the linear programming problem and the relationship between the dual problem, linear programming problem and the transformation of the dual problem, the applic
4、ation of linear programming dual problem. This article is the plex of the original problem into its dual problem to be solved, simplifies the linear programming problem, enables us to rapidly find the optimal solution of linear programming problem.Keywords:linear programming; the original problem; t
5、he dual problem; conversion目 录1 引言12 文献综述12.1 国内外研究现状12.2 国内外研究现状评价22.3 提出问题23 预备知识2对称形式的原问题23.2 非对称形式的原问题33.3 对偶问题的定义3原问题转化为对偶问题的理论依据44 原问题与对偶问题的转化5 原问题与对偶问题的关系54.2 对称型原问题化为对偶问题64.3 对称型对偶问题转换为原问题94.4非对称型原问题转化为对偶问题10 对偶问题的应用135 结论15主要发现15启示15局限性15努力方向15参考文献16 / 1 引言线性规划问题是运筹学里的一个重要的分支，它的应用比拟广泛，因而是辅助
6、人们进展现代科学管理的一种数学方法.随着线性规划理论的逐步深入，人们发现线性规划问题具有对偶性，即每一个线性问题都伴有另外一个线性问题的产生，两者相互配对，密切联系，反之亦然.我们把线性规划的这个特性称为对偶性.于是，我们将其中的一个问题称为原问题，另一个问题如此称为它的对偶问题.对偶性不仅仅是数学上的理论问题，而且也是线性规划中实际问题的内在经济联系的必然反映.我们通过对对偶问题的深入研究，发现对偶问题能从不同角度对生产计划进展分析，从而使管理者能够间接地获得更多比拟有用的信息.2 文献综述2.1 国内外研究现状在所查阅到的国内外参考文献1-15中，有不少文章是探讨了原问题转化为对偶问题的方
7、法以与对偶性质的证明，并在对偶理论的应用方面有所研究.如郝英奇，胡运权在1、10中主要介绍了线性规划中原问题与对偶问题中的一些根本概念，探究了实际问题中的数学模型以与解.孙君曼，冯巧玲，孙慧君，李淑君等在2中探讨了对偶理论中互补松弛定理在各种情况下的使用方法,使学生更好地掌握互补松弛定理的含义和应用方法.胡运权，郭耀煌，殷志祥等在3、5中系统的介绍了线性规划中原始问题与对偶问题的两种形式.郭鹏，徐玖平等在6、8中用不同例子来说明了原问题转化为对偶问题的必要性. X永新等在9、15中探讨了对偶问题的相关定理以与对偶问题的可行解和最优解之间的假如干性质.李师正，王德胜在11中探讨了如何用计算机计算
8、对偶问题的最优解.岳宏志，蔺小林，孙文喻等在12、14中探讨了对偶理论的证明过程，并用常见的例子来说明对偶理论的根本思想和解题方法. 曾波，叶宗文在13中主要从经济管理的实际问题中阐述了线性规划的根本概念，根本原理，对偶理论，灵敏度分析等.2.2 国内外研究现状评价文献1-15分别探讨了线性规划问题中原问题转化为对偶问题的理论依据以与如何利用对偶理论去解决实际生产问题.文献中主要探讨了对称型的原问题转化为对偶问题的方法.没有全面介绍非对称型的原问题与对偶问题之间转化的具体步骤，而且文献中对原问题转化为对偶问题的步骤提与甚少，大都一带而过，对应用中存在的问题也未给出详细深入的说明.2.3 提出问
9、题在线性规划问题中,根据实际生产中具体情况的需要,我们常常要把原问题与它的对偶问题进展转换,以解决一些复杂的线性规划问题,因而对偶问题的应用较为广泛.但大局部书籍都只介绍了线性规划问题的根底知识，并没有给出原问题与对偶问题转换的具体步骤.因此本文主要探讨了线性规划原问题与对偶问题之间转化的具体步骤，体会不同类型原问题的转化过程.3 预备知识首先我先简单的介绍一些关于线性规划问题中的原问题和对偶问题的一些根本的知识.的原问题我们将满足如下条件的线性规划问题称之为具有对称形式的线性规划问题.这类问题的变量都具有非负约束，当目标函数求极大值时，它的约束条件都取“号，当目标函数求极小值时它的约束条件均
10、取“号. 因而，这类数学模型的特点是：1所有的决策变量都是非负的；2所有的约束条件都是“型；3目标函数是最大化类型.线性规划原问题的对称形式的为： (3.1)3.2 非对称形式的原问题不是所有的线性规划问题都具有对称的形式，我们将没有对称形式的线性规划问题称之为非对称形式的线性规划问题.非对称形式的线性规划问题指的是一般情况下的线性规划问题，即是目标函数值求极小或者求极大；约束条件；，或是无限制的随意的组合.例如： (3.2)3.3 对偶问题的定义在运筹学中，关于对线性规划的对偶规划给出的如下.设给定的线性规划为：(3.2)其中，因此，定义它的对偶问题为： (3.4)其中是行向量. (3.4)
11、是对偶问题，(3.3)是原问题，(3.3)与(3.4)合在一起我们就称为是一对对称形式的对偶规划问题.我们根据线性规划问题中约束条件和变量的对应关系，统一归纳为下所示：项目原问题对偶问题对偶问题原问题约束系数矩阵约束系数矩阵的转置约束条件右端项向量目标函数中的价格系数向量目标函数中的价格系数向量约束条件右端项向量目标函数表14 原问题与对偶问题的转化一对对偶的线性规划问题表示了同一个问题的两个侧面，是从两个角度对同一个研究对象提出的极值问题，两类极值的问题都具有一样的目标函数值.我们发现在很多时候求解对偶问题比原问题更加容易，为决策者提供更多的科学理论依据，因此我们常常需要把原问题转化为对偶问
12、题.一对对偶的线性规划问题具有相互对应的关系：1原问题中的目标函数值是，约束条件是“的形式；对偶问题的，的形式.2原问题的价值系数和对偶问题的右端项对应，原始问题的右端项和对偶问题的价值系数对应.3原问题的变量和对偶问题的约束条件对应，即，原问题中有变量，那么对偶问题就有约束条件；原问题有约束条件，那么对偶问题就有变量.4对偶问题的系数矩阵就是原问题的系数矩阵的转置.用矩阵表示，原问题为：如此对偶问题为：需要注意的是，我们所讨论的对偶问题一定是指一对问题，而原问题和对偶问题是相对的，它们互为对偶问题，一个问题可以是原问题也可以是对偶问题.4.2 对称型原问题转化为对偶问题当线性规划问题为一般形
13、式3.1时，我们将根据下面的四条规如此转换为它的对偶问题：1原问题和它的对偶问题之间的系数矩阵互为转置.2原问题中变量的个数等于它的对偶问题的约束条件的个数.3原问题的右端常数就是对偶问题的目标函数的系数.4原问题的目标函数求极大时，约束条件是“类型，而它的对偶问题的目标函数求极小，约束条件如此为“类型.因此，它的对偶问题可以转变为如下的：例1 生产计划问题某某一公司加工生产甲，乙两种产品，它的市场前景非常的好，销路也不成问题，各种制约因素主要有技术工人、设备台时和原材料供给.制造每吨产品的资源消耗系数、每天的资源限量和售价等参数如表2所示.问题：某某的这家公司应该怎样制定每天的生产计划，才能
14、使它的产量得到最大？甲产品乙产品资源限量人力86320设备68260原材料410300售价元/公斤90150表2分析：为了建立此问题的数学模型，第一，要选定决策变量.第二，要确定问题的目标，即用来评价不同方案优劣的标准，这种目标总是决策变量的函数，称为目标函数.第三，我们把要确定达到目标时所受的限制条件，称之为约束条件.这里要决策的问题是，在现有人力、设备、矿石的限制下，如何确定产量使得产值自大？设和分别表示该公司A，B产品的数量，用z表示产值，如此每天的产值表示为，使其最大化，即，称为目标函数.将制约因素表达出来，即有：人力不超过320工时，为；设备不超过260台时有，；原材料不超过300公
15、斤有，。表述限制条件的数学表达式称为约束条件，由此该问题的数学模型可表示为：上面的问题是一个典型的求解利润最大化的生产计划的问题.题中，“是 “maximize的缩写，意思是“最大化；“是subject to单词的缩写，表示“满足于.因此，上述模型的含义是：在给定的条件限制下，求出使目标函数值达到最大的的值.从数学模型中看出，上面的例题具有下面的三个特征：(1) 用一组决策变量表示问题的一个方案，决策变量的一组取值代表一个具体的方案.通常状况下，决策变量的取值是非负的，局部情况下，还要求决策变量取值为整数.(2) 每个问题都有一个目标，而且都可以用决策变量的线性函数表示.根据问题的不同，要求目
