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

《线性规划原问题与对偶问题的转化及其应用》由会员分享，可在线阅读，更多相关《线性规划原问题与对偶问题的转化及其应用（21页珍藏版）》请在金锄头文库上搜索。

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

2、 the Original Problem and the Transformation ofthe 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 managementof auxiliary people mat

3、hematical method. Can 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

4、 the dual problem, the 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 pro

5、gramming; the original problem; the dual problem; conversion目录1 引言 12 文献综述 12.1 国内外研究现状 12.2 国内外研究现状评价 22.3 提出问题 23 预备知识 23.1 对称形式的原问题 23.2 非对称形式的原问题 33.3 对偶问题的定义 33.4 原问题转化为对偶问题的理论依据 44 原问题与对偶问题的转化 54.1 原问题与对偶问题的关系 54.2 对称型原问题化为对偶问题 64.3 对称型对偶问题转换为原问题 94.4 非对称型原问题转化为对偶问题 104.5 对偶问题的应用 135 结论 155.1

6、主要发现 155.2 启示 155.3 局限性 155.4 努力方向 15参考文献 151 引言线性规划问题是运筹学里的一个重要的分支， 它的应用比较广泛， 因而是辅助人们 进行现代科学管理的一种数学方法 . 随着线性规划理论的逐步深入，人们发现线性规划 问题具有对偶性，即每一个线性问题都伴有另外一个线性问题的产生，两者相互配对， 密切联系，反之亦然 . 我们把线性规划的这个特性称为对偶性 .于是，我们将其中的一个 问题称为原问题，另一个问题则称为它的对偶问题 . 对偶性不仅仅是数学上的理论问题， 而且也是线性规划中实际问题的内在经济联系的必然反映 . 我们通过对对偶问题的深入 研究，发现对偶

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

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

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

10、因此本文主要探讨了线性规划原问题与对偶问题之间转化的具体步骤，体会 不同类型原问题的转化过程 .3 预备知识首先我先简单的介绍一些关于线性规划问题中的原问题和对偶问题的一些基本的 知识.3.1 对称形式的原问题我们将满足下列条件的线性规划问题称之为具有对称形式的线性规划问题 . 这类问 题的变量都具有非负约束，当目标函数求极大值时，它的约束条件都取“ ”号，当目 标函数求极小值时它的约束条件均取“”号. 因而，这类数学模型的特点是： （1）所有的决策变量都是非负的； （ 2）所有的约束条件都是“ ”型；（3）目标函数是最大化 类型.线性规划原问题的对称形式的 一般形式 1为：maxz c1x1

11、 c2x2cn xna1 Xa2 X2a1nXnb1a?1 X222X2a2n Xnb2s.tam1 X1am2 X2amnXnbmXj0( j 1,2,n)(3.1)3.2非对称形式的原问题不是所有的线性规划问题都具有对称的形式， 我们将没有对称形式的线性规划问题 称之为非对称形式的线性规划问题.非对称形式的线性规划问题指的是一般情况下的线性规划问题，即是目标函数值求极小或者求极大；约束条件兰； 兰三二:或是无限制的随意的组合.例如:max z c1 xC2X203X3812X2ai3X3bia?i Xis.ta31 X1a22 X2a23 X3a32 X2a33 X3b2b3(3.2)X1

12、0, X20, x3无约束3.3对偶问题的定义在运筹学中，关于对线性规划的对偶规划给出的 定义如下.(3.2)bm T，C设给定的线性规划为:maX zCXAXbs.tX0其中 XX1,X2, ,Xn T， A aj m n，b b,b2,因此，定义它的对偶问题为:min w Yb(3.4)YA C s.tY 0其中Y ”兀,ym是行向量.（3.4）是对偶冋题，（3.3）是原冋题，（3.3）与（3.4）合在一起我们就称为是一对对称形式的对偶规划问题3.4原问题转化为对偶问题的理论依据我们根据线性规划问题中约束条件和变量的对应关系，统一归纳为下表1所示:项目原问题（对偶问题）对偶问题（原问题）A

13、约束系数矩阵约束系数矩阵的转置b约束条件右端项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件右端项向量目标函数nmaxzcj xjj 1mmin wbi yii 1Xj(j1,n)Xj0变量Xj0Xj无约束有 n个(j 1,n)maij yCji 1m约束条件aij yiCji 1maij yiCji 1有m个(i1, m)naij Xjbij 1约束条件naij Xjbij 1naj Xjbij 1yi(i 1, m)yi 0变量yi 0yi无约束表14 原问题与对偶问题的转化一对对偶的线性规划问题表示了同一个问题的两个侧面， 是从两个角度对同一个研 究对象提出的极值问题，两

14、类极值的问题都具有相同的目标函数值.我们发现在很多时候求解对偶问题比原问题更加容易， 需要把原问题转化为对偶问题 .为决策者提供更多的科学理论依据， 因此我们常常4.1 原问题与对偶问题的关系一对对偶的线性规划问题具有相互对应的关系：(1) 原问 题中的目标函数值 是 max ，约束条件是“ ”的 形式；对偶问题的目标函数值为 min ， 约束条件是“”的形式.(2) 原问题的价值系数和对偶问题的右端项对应，原始问题的右端项和对偶问题的价 值系数对应 .(3) 原问题的变量和对偶问题的约束条件对应，即，原问题中有n个变量，那么对偶问题就有n个约束条件；原问题有m个约束条件，那么对偶问题就有 m个变量.( 4)对偶问题的系数矩阵就是原问题的系数矩阵的转置 .用矩阵表示，原问题为：max z CXAX bs.t.X0则对偶问题为：min w YbYA Cs.t.Y0需要注意的是， 我们所讨论的对偶问题一定是指一对问题， 而原问题和对偶问题是相对的，它们互为对偶问题，一个问题可以是原问题也可以是对偶问题4.2对称型原问题转化为对偶问题当线性规划问题为一般形式(3.1 )时，我们将根据下面的四条规则转换为它的对 偶问题：(1) 原问题和它的对偶问题之间的系数矩阵互为转置 .(2) 原问题中变量的个数等于它的对偶问题的约束条件的个数(3) 原问题的右端常数就是