线性规划原问题与对偶问题的转化和应用

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

2、nd the 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

3、from different 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

4、 application of linear programming dual problem. This article is the complex 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

5、problem; the dual problem; conversion目 录 TOC o 1-3 h z u HYPERLINK l _Toc4175614711 引言 PAGEREF _Toc417561471 h 1HYPERLINK l _Toc4175614722 文献综述 PAGEREF _Toc417561472 h 1HYPERLINK l _Toc4175614732.1 国外研究现状 PAGEREF _Toc417561473 h 1HYPERLINK l _Toc4175614742.2 国外研究现状评价 PAGEREF _Toc417561474 h 2HYPERLI

6、NK l _Toc4175614752.3 提出问题 PAGEREF _Toc417561475 h 2HYPERLINK l _Toc4175614763 预备知识 PAGEREF _Toc417561476 h 2HYPERLINK l _Toc4175614773.1对称形式的原问题 PAGEREF _Toc417561477 h 2HYPERLINK l _Toc4175614783.2 非对称形式的原问题 PAGEREF _Toc417561478 h 3HYPERLINK l _Toc4175614793.3 对偶问题的定义 PAGEREF _Toc417561479 h 3HYP

7、ERLINK l _Toc4175614803.4原问题转化为对偶问题的理论依据 PAGEREF _Toc417561480 h 4HYPERLINK l _Toc4175614814 原问题与对偶问题的转化5HYPERLINK l _Toc4175614824.1 原问题与对偶问题的关系 PAGEREF _Toc417561482 h 5HYPERLINK l _Toc4175614834.2 对称型原问题化为对偶问题6HYPERLINK l _Toc4175614844.3 对称型对偶问题转换为原问题9HYPERLINK l _Toc4175614854.4非对称型原问题转化为对偶问题10

8、HYPERLINK l _Toc4175614864.5 对偶问题的应用 PAGEREF _Toc417561486 h 13HYPERLINK l _Toc4175614875 结论 PAGEREF _Toc417561487 h 15HYPERLINK l _Toc4175614885.1主要发现 PAGEREF _Toc417561488 h 15HYPERLINK l _Toc4175614895.2启示 PAGEREF _Toc417561489 h 15HYPERLINK l _Toc4175614905.3局限性 PAGEREF _Toc417561490 h 15HYPERLI

9、NK l _Toc4175614915.4努力方向 PAGEREF _Toc417561491 h 15HYPERLINK l _Toc417561492参考文献 PAGEREF _Toc417561492 h 161 引言线性规划问题是运筹学里的一个重要的分支，它的应用比较广泛，因而是辅助人们进行现代科学管理的一种数学方法.随着线性规划理论的逐步深入，人们发现线性规划问题具有对偶性，即每一个线性问题都伴有另外一个线性问题的产生，两者相互配对，密切联系，反之亦然.我们把线性规划的这个特性称为对偶性.于是，我们将其中的一个问题称为原问题，另一个问题则称为它的对偶问题.对偶性不仅仅是数学上的理论问

10、题，而且也是线性规划中实际问题的在经济联系的必然反映.我们通过对对偶问题的深入研究，发现对偶问题能从不同角度对生产计划进行分析，从而使管理者能够间接地获得更多比较有用的信息.2 文献综述2.1 国外研究现状在所查阅到的国外参考文献1-15中，有不少文章是探讨了原问题转化为对偶问题的方法以与对偶性质的证明，并在对偶理论的应用方面有所研究.如郝英奇，胡运权在1、10中主要介绍了线性规划中原问题与对偶问题中的一些基本概念，探究了实际问题中的数学模型以与解.君曼，巧玲，慧君，淑君等在2中探讨了对偶理论中互补松弛定理在各种情况下的使用方法,使学生更好地掌握互补松弛定理的含义和应用方法.胡运权，郭耀煌，殷

11、志祥等在3、5中系统的介绍了线性规划中原始问题与对偶问题的两种形式.郭鹏，徐玖平等在6、8中用不同例子来说明了原问题转化为对偶问题的必要性. 永新等在9、15中探讨了对偶问题的相关定理以与对偶问题的可行解和最优解之间的若干性质.师正，王德胜在11中探讨了如何用计算机计算对偶问题的最优解.岳宏志，蔺小林，文喻等在12、14中探讨了对偶理论的证明过程，并用常见的例子来说明对偶理论的基本思想和解题方法. 曾波，叶宗文在13中主要从经济管理的实际问题中阐述了线性规划的基本概念，基本原理，对偶理论，灵敏度分析等.2.2 国外研究现状评价文献1-15分别探讨了线性规划问题中原问题转化为对偶问题的理论依据以

12、与如何利用对偶理论去解决实际生产问题.文献中主要探讨了对称型的原问题转化为对偶问题的方法.没有全面介绍非对称型的原问题与对偶问题之间转化的具体步骤，而且文献中对原问题转化为对偶问题的步骤提与甚少，大都一带而过，对应用中存在的问题也未给出详细深入的说明.2.3 提出问题在线性规划问题中,根据实际生产中具体情况的需要,我们常常要把原问题与它的对偶问题进行转换,以解决一些复杂的线性规划问题,因而对偶问题的应用较为广泛.但大部分书籍都只介绍了线性规划问题的基础知识，并没有给出原问题与对偶问题转换的具体步骤.因此本文主要探讨了线性规划原问题与对偶问题之间转化的具体步骤，体会不同类型原问题的转化过程.3

13、预备知识首先我先简单的介绍一些关于线性规划问题中的原问题和对偶问题的一些基本的知识.3.1对称形式的原问题我们将满足下列条件的线性规划问题称之为具有对称形式的线性规划问题.这类问题的变量都具有非负约束，当目标函数求极大值时，它的约束条件都取“ QUOTE ”号，当目标函数求极小值时它的约束条件均取“ QUOTE ”号. 因而，这类数学模型的特点是：（1）所有的决策变量都是非负的；（2）所有的约束条件都是“ QUOTE ”型；（3）目标函数是最大化类型.线性规划原问题的对称形式的 QUOTE 为： (3.1)3.2 非对称形式的原问题不是所有的线性规划问题都具有对称的形式，我们将没有对称形式的线

14、性规划问题称之为非对称形式的线性规划问题.非对称形式的线性规划问题指的是一般情况下的线性规划问题，即是目标函数值求极小或者求极大；约束条件；，或是无限制的随意的组合.例如： (3.2)3.3 对偶问题的定义在运筹学中，关于对线性规划的对偶规划给出的如下 QUOTE .设给定的线性规划为： (3.2)其中， QUOTE ，因此，定义它的对偶问题为： (3.4)其中 QUOTE 是行向量. (3.4)是对偶问题，(3.3)是原问题，(3.3)与(3.4)合在一起我们就称为是一对对称形式的对偶规划问题.3.4原问题转化为对偶问题的理论依据我们根据线性规划问题中约束条件和变量的对应关系，统一归纳为下

15、QUOTE 所示：项目原问题（对偶问题）对偶问题（原问题）约束系数矩阵约束系数矩阵的转置约束条件右端项向量目标函数中的价格系数向量目标函数中的价格系数向量约束条件右端项向量目标函数表14 原问题与对偶问题的转化一对对偶的线性规划问题表示了同一个问题的两个侧面，是从两个角度对同一个研究对象提出的极值问题，两类极值的问题都具有一样的目标函数值.我们发现在很多时候求解对偶问题比原问题更加容易，为决策者提供更多的科学理论依据，因此我们常常需要把原问题转化为对偶问题.4.1原问题与对偶问题的关系一对对偶的线性规划问题具有相互对应的关系：（1）原问题中的目标函数值是 QUOTE ，约束条件是“”的形式；对

16、偶问题的， QUOTE 的形式.（2）原问题的价值系数和对偶问题的右端项对应，原始问题的右端项和对偶问题的价值系数对应.（3）原问题的变量和对偶问题的约束条件对应，即，原问题中有 QUOTE 变量，那么对偶问题就有 QUOTE 约束条件；原问题有 QUOTE 约束条件，那么对偶问题就有 QUOTE 变量.（4）对偶问题的系数矩阵就是原问题的系数矩阵的转置.用矩阵表示，原问题为： QUOTE QUOTE 则对偶问题为： QUOTE 需要注意的是，我们所讨论的对偶问题一定是指一对问题，而原问题和对偶问题是相对的，它们互为对偶问题，一个问题可以是原问题也可以是对偶问题.4.2 对称型原问题转化为对偶

17、问题当线性规划问题为一般形式（3.1）时，我们将根据下面的四条规则转换为它的对偶问题：（1）原问题和它的对偶问题之间的系数矩阵互为转置.（2）原问题中变量的个数等于它的对偶问题的约束条件的个数.（3）原问题的右端常数就是对偶问题的目标函数的系数.（4）原问题的目标函数求极大时，约束条件是“ QUOTE ”类型，而它的对偶问题的目标函数求极小，约束条件则为“ QUOTE ”类型.因此，它的对偶问题可以转变为如下的 QUOTE ：例1 生产计划问题一公司加工生产甲，乙两种产品，它的市场前景非常的好，销路也不成问题，各种制约因素主要有技术工人、设备台时和原材料供应.已知制造每吨产品的资源消耗系数、每

18、天的资源限量和售价等参数如表2所示.问题：的这家公司应该怎样制定每天的生产计划，才能使它的产量得到最大？甲产品乙产品资源限量人力86320设备68260原材料410300售价（元/公斤）90150表2分析：为了建立此问题的数学模型，第一，要选定决策变量.第二，要确定问题的目标，即用来评价不同方案优劣的标准，这种目标总是决策变量的函数，称为目标函数.第三，我们把要确定达到目标时所受的限制条件，称之为约束条件.这里要决策的问题是，在现有人力、设备、矿石的限制下，如何确定产量使得产值自大？设 QUOTE 和 QUOTE 分别表示该公司A，B产品的数量，用z表示产值，则每天的产值表示为 QUOTE ，

19、使其最大化，即 QUOTE ，称为目标函数.将制约因素表达出来，即有：人力不超过320工时，为 QUOTE ；设备不超过260台时有， QUOTE ；原材料不超过300公斤有， QUOTE 。表述限制条件的数学表达式称为约束条件，由此该问题的数学模型可表示为：上面的问题是一个典型的求解利润最大化的生产计划的问题.题中，“ QUOTE ”是 “maximize”的缩写，意思是“最大化”；“ QUOTE ”是”subject to”单词 QUOTE 的缩写，表示“满足于”.因此，上述模型的含义是：在给定的条件限制下，求出使目标函数值 QUOTE 达到最大的 QUOTE 的值.从数学模型中看出，上面

20、的例题具有下面的三个特征：(1) 用一组决策变量表示问题的一个方案，决策变量的一组取值代表一个具体的方案.通常状况下，决策变量的取值是非负的，部分情况下，还要求决策变量取值为整数.(2) 每个问题都有一个目标，而且都可以用决策变量的线性函数表示.根据问题的不同，要求目标实现最大或者最小.(3) 决策变量都满足一定的约束条件，而且都可以用决策变量的线性等式或者不等式表示.具备以上三个要素的问题称为线性规划问题，简单地讲，线性规划问题就是求一个线性目标函数在满足一组线性等式（或不等式方程）约束条件下的极值问题.例2 一公司加工生产甲，乙两种产品，市场前景非常的很好，销路也不成问题，各种制约因素主要

21、有技术工人、设备台时和原材料供应.已知制造每吨产品的资源消耗系数、每天的资源限量和售价等参数如表3所示.现在公司有意转换经营方式，现在将各种资源出租转让，我们假定市场广阔.问题：公司转让资源的价格底线是什么？甲产品乙产品资源限量人力86320设备68260原材料410300售价（元/公斤）90150表3我们将例1叫做原问题，将例2叫做对偶问题.原问题的数学模型是： (4.1)分析：现在在对偶问题中我们需要考虑的是，将例题中的三种资源租让或者转出，应该是不少于原来的收益的，否则这家公司宁愿选择自己继续生产.所以，决策的约束条件应该是：出租制造的产品消耗掉的资源不能少于自己生产该产品的收益；目标函

22、数应该是：资源转让的收益底线.所以，我们设， QUOTE ， QUOTE 分别为人力、设备台时和原材料的转让或者出租的价格.由于生产1公斤A产品需消耗8个工时，6个台时和4公斤的原材料，可创造产值90元.所以出让生产A产品资源至少应带来90元的产值，即 QUOTE 同理，生产1公斤B产品需耗时4个工时，6个台时和8公斤的原材料，可创造产值150元，出让这些资源所获得的销售收益应满足 QUOTE 上面两个不等式保证了“出售”资源所获得的收益不低于自己组织生产所能创造的收益.但是也不能随意要价，否则由于市场的调节作用将会使资源卖不出去.因此目标函数应该是表达所获的收益的底线，即 解：从转让资源的方

23、面考虑，得到此问题的数学模型应是 (4.2)评注：通过分析我们可以知道，重新得到的对偶问题是一个非常重要的线性规划问题，它对问题的分析又加深了一步，减少了管理工作中的盲目性，为决策者提供了更多的科学依据.原问题与对偶问题之间是相互对应的关系，原问题与对偶问题是从不同的角度对同一问题进行了分析研究.它们之间存在着很密切的关系，这些关系我们将在通过分析可知.从形式上我们可以看到，在原问题中，制订生产计划有3种设备的总工时构成规划的资源约束，可建立3个约束不等式，其中2种要生产的产品将构成决策变量；而在它的对偶问题中，原问题里的3个资源约束所对应的资源估价正好构成了对偶问题的决策变量，原问题中的2个

24、决策变量对应的2种产品则构成了对偶问题的2个约束条件.小结：通过分析可以得出，问题 QUOTE 和问题 QUOTE 具有下面的关系：(1)问题 QUOTE 的目标函数值求极小；问题 QUOTE 的目标函数值求极大.(2)问题 QUOTE 有2个决策变量和3个主约束条件，问题 QUOTE 有3个决策变量和2个主约束条件.即问题 QUOTE 中决策变量的个数和问题 QUOTE 中主约束条件的个数相等，问题 QUOTE 中的主约束条件的个数和问题 QUOTE 中的决策变量的个数是相等.原因是，问题 QUOTE 的系数矩阵和问题 QUOTE 的系数矩阵是互为转置的.(3)问题 QUOTE 的价格指标与

25、问题 QUOTE 的资源指标对应，且问题 QUOTE 的 QUOTE 指标与问题 QUOTE 的 QUOTE 指标对应.(4)问题 QUOTE 的资源指标与问题 QUOTE 的价格指标对应，且问题 QUOTE 的 QUOTE 指标与问题 QUOTE 的 QUOTE 指标对应.(5)问题 QUOTE 的主约束条件是 “”型的约束条件；而问题 QUOTE 的主约束条件是 “”型的约束条件.4.3对称型对偶问题转换为原问题对偶理论中关于线性规划问题里，对偶问题的对偶就是原问题.设原问题为： (4.3)则对偶问题为： (4.4)而对偶问题的对偶为： (4.5)由此可见，线性规划问题（4.3），（4.5

26、）的形式是完全一致，因而，原问题和它的对偶问题是互为对偶的关系，也即是对偶问题的对偶就是原问题.4.4 非对称型的原问题转化为对偶问题线性规划有时以非对称型出现，那么如何从原始问题写出它的对偶问题，将是下面要讨论的问题.在非对称形式的规划问题中，可以按照下面的对应规则直接给出它的对偶问题:（1）将线性规划问题统一为“ QUOTE ”或“ QUOTE ”的形式，而其中的等式约束按照下面（2），（3）中的方法进行处理.（2）若原问题的某个约束条件时等式约束，则对偶问题中与此约束对应的那个变量取值没有非负限制的.（3）若原问题的某个变量的值没有非负限制，则在它的偶问题中与此变量对应的约束条件是等式约

27、束.下面对于规则（2）做一些必要的说明，对于规则（3）可以给出类似的证明设原问题中的第一个约束是等式：那么，此等式与下面的两个不等式等价：这样，原问题可以写成因为就转换为对称形式，所以可以直接写出对偶问题这里，我们把看作, QUOTE ，于是没有限制，规则（2）的说明完毕.将非对称的线性规划问题转换为对称形式时可能会有以下几种 QUOTE ：（1）目标函数的转换设 QUOTE ，令 QUOTE ，则将求最小值的问题转换为求最大值的问题，即将求 QUOTE 转化为求 QUOTE ，且 QUOTE .反之，要将极大化目标函数转化为极小化目标函数，也可以直接给原目标函数乘以-1，把 QUOTE 改写

28、成 QUOTE .（2）主约束条件的转换A将“ QUOTE ”型（或者“ QUOTE ”）的约束条件 QUOTE （或 QUOTE ），转化为“ QUOTE ”型（或者“”型）的约束条件时，直接将原约束条件两边同乘以，即 QUOTE （或 QUOTE ）B将“=”型的约束条件 QUOTE 转化为“”型或者“”型的约束条件时，首先将其写成两个不等式约束条件，然后再转化为所需形式的不等式约束条件，即：（3）非负约束条件的转换A 若变量没有非负限制，取值可正可负，这时可设两个非负变量 QUOTE 和 QUOTE ，令,B若变量 QUOTE ，可令： QUOTE 例3：请写出下列的线性规划问题的对偶问

29、题分析：首先将上述非对称型问题转换为我们所熟悉的对称型问题，然后按照对称型问题的方法将原问题转化为对偶问题。第一，在第一个约束条件的两边同乘以-1.第二，将第三个约束方程分解成 QUOTE 和 QUOTE 再将约束条件两边同时乘以-1，即 QUOTE 解：原问题转换为如下的对称型：现在四个约束，分别对应四个对偶变量 QUOTE ，按表1可得到下面的对偶问题：再设 QUOTE ，代入上面的数学模型就可得出原问题的对偶问题为：评注：将上面对偶问题同原问题对比发现，无论是对称的形式或者是非对称形式的线性规划问题在写出它的对偶问题时，表格中前四行的对应关系都适应，区别的只是约束条件的形式与其对应变量的

30、取值.4.5对偶问题的应用设有如下线性规划问题：已知它的最优解为 QUOTE ，求对偶问题的最优解.解：根据对偶规则，我们很容易的写出了原问题的对偶问题：根据对偶性质，有如下对应关系：原问题中的原始变量原问题中的松弛变量 QUOTE 对偶问题的剩余变量对偶问题的原始变量 QUOTE 将对偶问题标准化为：由于 QUOTE 为零，上述约束条件简化为：由此的对偶问题的最优解为： QUOTE 评注：线性规划问题中，有时为了计算变得简单，我们常常需要把线性规划问题的原问题转换为它的对偶问题进行解决.5 结论5.1主要发现对偶理论是线性规划问题的重要容之一，任何一个线性规划都有一个伴生的线性规划，称之为原

31、问题的对偶规划问题.本文主要探究了原问题与对偶问题之间的关系，原问题与对偶问题转化的具体步骤和对偶理论的应用.用科学的方法对生产计划进行预测，与时调整、科学决策，使企业决策更加合理.5.2启示线性规划中常常用到对偶问题，它的思想方法是利用线性代数的方法找出线性规划模型中目标函数与约束条件的可行解.同时利用对偶问题能够快速的找出问题的最优解，对解的特性的判断起关键作用.在计算工具不断发展的今天，用对偶问题处理生产、经营上的问题已经越来越广泛.企业经营者可以根据市场的具体情况，建立相应的数学模型，然后用对偶问题加以分析，科学的为决策者提供理论依据.5.3局限性本文主要研究了对称型与非对称型的线性规划原问题转化为对偶问题的具体步骤.对偶问题是一组线性约束条件下的线性规划问题，它只能处理单个目标函数的优化问题.而实际问题中往往要考虑多个目标函数，这些目标函数之间可能是相互矛盾、相互排斥的.5.4努力方向虽然对偶问题的适用围很大，但受实际问题中约束条件的制约，只能处理单目标的优化问题,所以研究线性规划最优解的