1、 本科 毕业论文 （ 设计 ） （ 20 届） 对偶线性规划理论及其在经济中的应用 所在学院 专业班级 信息与计算科学 学生姓名 学号 指导教师 职称 完成日期 年 月 I 摘要 :对偶线性规划是运筹学的一个重要分支，并应用到社会各个方面。本文首先介绍了对偶线性规划理论产生的背景，以及它的发 展历程和发展方向。接着叙述了解决对偶线性规划问题的方法及其算法。我们通过分析问题建立数学模型，使用适当方法求出最优解，并对其进行分析得到该问题的最优值。最后运用对偶线性规划理论来解决相关实际问题，即它被应用的过程。 关键词 :对偶线性规划；数学模型；最优解 . II The Theory of Dual
2、Linear Programming and its Application in economics Abstract:Dual linear programming is an important branch of operations research, and its applied to all aspects of the society. In this paper the background of the dual linear programming theory, the development history and direction of dual linear
3、programming theory are introduced. Then the methods and algorithms of solving the dual linear programming problems are described. We can build a mathematical model by analyzing the problem,obtain an optinum solution in the proper way and analyze the solution to obtain the optimal value of the dual l
4、inear problem. Finally, the relational practical problem is solved by using the dual linear programming theory. That is the process of its application. Keywords:dual linear programming; mathematical models; optimal value. III 目 录 1. 绪论 . 1 2. 对偶线性规划理论的概述 . 3 2.1 对偶线性规划理论的发展历程及现状 . 3 2. 2 对偶问题的基本性质 .
5、 3 3 线性规划的对偶原理及其应用 . 6 3.1 对偶理论 . 6 3.2 对偶性的其他问题 . 8 3.3 对偶规划问题的三种解法介绍 . 9 3.4 最优对偶变量（影子价格）的经济解释 . 11 3.5 影子价格在企业经营管理中的应用 . 18 4. 结论 . 21 致 谢 . 错误 !未定义书签。 参考文献 . 22 1 1. 绪论 任一线性规划问题都存在另一与之伴随的线性规划问题，他们从不同角度对一个实际问题提出并进行描述，组成一对互为对偶的线性规划问题。 什么是“对偶问题”呢？对偶问题实际上是换一个角度来分析原问题。在线性规划分析方法中，假设原问题的目标是尽可能地利用可利用的资源
6、来获得最大化利润的话，那么从问题的另一个侧面来思考问题，目标变成尽可能地利用原问题所给出的利润指标来调整范围条件来减少资源的消耗，于是以原问题目标函数中的决策变量系数作为新问题的资源，其所形成的线性规划模型就成为对偶问题 的线性规划模型。 当原问题与对偶问题的最优化目标函数值相同时，可以揭示公平交易最为根本的东西：无论是从买方看，还是从卖方看，都实现了自己的交易目标最优化。在一桩交易中，卖方总是希望获利最大化，而买方则是希望采购成本最小化，他们的成交底线在哪里呢？从对偶规划的角度看，如果交易双方都是理性交易的话，他们的成交底线应该是相同的，即卖方的利益最大化目标值等于买方的成本最小化目标值。
7、1 所以，对偶线性规划理论在经济中的应用是很有实用价值，也是很值得研究的。 我国加入 WTO 之后，融入经济全球化的速度不断加快，竞争日趋激烈，为了适应新的生存环境，企业的经营理念就必须不断深化。产品（业务）经营、资产经营、资本经营三管齐下，确保企业的竞争力处在最好水平，这种由全球性的优秀企业所创造的经营理念也将成为我国所有成功企业的经营理念。其中，资产经营将成为各类企业保持竞争力的一种普遍行为。 资产经营的主要内容是企业的业务重组和资产重组。而在资产经营策略中，交易价格底线的确定往往是意见困难的事情。价格底线订高了，担心交易不成，损失机会；价格底线订低了，又担心交易吃亏了，损失利益。究竟采取
8、什 么策略才能保证既不会丧失机会又不至于吃亏呢？一种策略是，决策层事先不了解价格底线也不给出价格底线，让业务人员处在无底线约束的状况下与交易对象进行谈判，在谈判的过程中不断地了解对方的意图和信息，并且将信息反馈到决策层，由决策层根据对方的意图来确定价格底线，并据此确定最后的交易价格。 2 另一种策略是，决策层事先安排资产评估分析人员对拟进行交易的标的物进行评估，并提出转让或购入资产的价格底线的专业性建议，再让业务人员带着决策底线去现场谈判，在谈判中进一步了解信息，并且将信息反馈到决策层，由决策层根据不冲信息对价格底 线建议进行修正，然后最终确定交易价格。 粗看起来，两种策略差不多，并且似乎前者
9、更灵活一些，更有可能抓住机会，获得更多的利益。其实，真正能做到既抓住交易机会，又不会损失合理利益，既能保证原则性，又可以现实灵活性的策略是第二种。 因此，第一种策略是一个基于对手理性的决策过程，而第二种策略则是一个基于自我理性的决策过程。与一个理性的交易对手打交道，第一种策略的最优交易结果是不赔不赚，而第二种策略的最差结果是不赔不赚。 不赔不赚交易可以称为对等交易。从逻辑上看，采用第一种策略与一个理性的交易对手进行交易，不能导致交 易的对等结果必然出现，在与一个非理性的交易对手进行交易时，也不能保证交易本身是对等的或者是对己方有利的，因此它不是一个好的策略。而采用第二种策略，在与一个理性的交易
10、对手进行交易时，可以保证交易本身不会劣于对等的结果，在与一个非理性的交易对手金乡交易时，还有可能获得优于对等的交易结果，因此它是一个好的策略。 有人或许要问，既然对等交易不赔也不赚，为什么还要劳民伤财地进行呢？请注意，这里所谓的“对等”概念，是就交易本身而言的。双方都不吃亏的交易就叫“对等”交易。但这里边并没有包括对等交易目的这个关键内容。如果通 过交易，双方都能打到优化各自资产或者是业务结构的目的，形成新的资产增值机会，那么，通过对等交易所获得的最终结果将是“双赢”，尽管可能存在交易的一方通过交易获得的资产增殖潜力比另一方更大些的情形，但是，只要双方同时都扩大了自身资产的增殖潜力，那就可以称
11、为“双赢”。这就是对一些理性的经营者在交易中只关心自己是否得到了应该得到的钱，而不过问交易对手可能赚多少钱这种日益流行的经济学现象的合理解释。 而影子价格正是确定交易底线的基本依据！ 3 2. 对偶线性规划理论的概述 2.1 对偶线性规划理论的发展历程及现状 2 3 线性规划理论产生于 20 世纪 30 年代。 1939 年 ， 苏联数学家康托罗维奇在生产组织与计划中的数学方法一书中 ，最早提出和研究了线性规划问题。 1947 年 ， 美国数学家丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法 单纯形法，为这门学科奠定了基础。 1947 年 ， 美国数学家诺伊曼提出对偶理论 ,开创
12、了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。 1951 年 ， 美国经济学家库普曼斯把线性规划应用到经济领域 ； 1960 年， 康托罗维奇 再次发表 最佳资源利用的经济计算 ，创立了享誉全球的线性 规划要点，对资源最优分配理论做出了贡献。 为此 ， 库普曼斯与康托罗维奇一起获 1975 年诺贝尔经济学奖 。 1984 年 ， 美国贝尔电话实验室的印度数学家卡马卡提出 求 解线性规划问题的 投影尺度法，这是一个有实用意义的 新的多项式时间算法。 这个算法引起了人们对内点算法的关注，此后相继出现看多种更为简单实用的内点算法。随着计算机技术的发展和普及，线性规划的应用越来越广泛。它
13、已成为人们合理利用有限资源制定最佳决策的有利工具。 由于对偶规划问题的全面性，考虑的多面性，现在的很多经济问题都通过对偶规划问题来解决。从而衍生出的影子价格也 是现今各大企业在资产经营策略中一个非常重要的交易工具。它的应用已经遍及各大企业的经营策略中。 2. 2 对偶问题的基本性质 4 5 给定一个线性规划问题 1 1 2 21 1 1 2 1 112 1 2 2 2 2 21212m in., , , 0nnnnmmm m m nnc x c x c xa a a xba a a x bstxba a ax x x 使用向量与矩阵表示形式为 4 m in m a x( ) . . ( ) .
14、 .00TTTTc x w bP s t A x b D s t w A cxw1. 对称性 对偶问题的对偶是原问题。 2. 弱对偶性 设 x 和 w 分别是问题 ()P 和 ()D 的可行解，则 TTc x wb 3. 无界性 问题 ()P 和 ()D 同时有最优解的充分必要条件是它们同时有可行解。而且，若其中有一个问题无界，则另一个问题无解。 4. 强对偶性 设 *x 和 *w 分别为 ()P 和 ()D 的可行解，则它们分别为 ()P 和 ()D 的最优解当且仅当 *()TTc x w b 5. 互补松弛性 设 *x 和 *w 分别为原问题 ()P 和对偶问题 ()D 的可行解，则它们分
15、别为 ()P 和 ()D 的最优解当且仅当 *1*1( ) 0 , 1 , 2 , ,( ) 0 , 1 , 2 , ,ni ij j ijmj ij i jib a x w i mc a w x j n 使用矩阵形式，可得 *x 和 *w 的互补松弛性条件： * * * *( ) ( ) 0 , ( ) 0TTw A x b c w A x 5 6. 唯一性 问题 ()P 有非退化的最优基可行解，那么，其对偶规划 ()D 有唯一的最优解。 7. 对偶变量的经济解释 假定所讨论的是下面的线性规划问题 m ax( ) . .0TcxP s t Ax bx其中 b 某工厂所拥有的 m 种资源的总
16、量； ija 生产每件第 i 种产品需消耗第 i 种资源的量。 该问题的实际背景是在资源有限的条件下安排生产，以使效益最大。 6 3 线性规划的对偶原理及其应用 3.1 对偶理论 6 以如下一对问题来表示线性规划问题的对偶： : m in : m a x. . . .00P c x D w bs t Ax b s t w A cxw这里 P 表示原问题， D 表示其对偶问题 . 注意到两个问题间的变换特点，这里 w 为对偶问题的变量向量，每一个原问题的约束条件，对应一个对偶变量（ m 个）；每一个原问题变量对应一个对偶问题约束条件（ n 个） .原问题为求最大值，则对偶问题为求最小值 .原问题
17、与对偶问题中，其目标函数系数与右端常数互换；约束条件系数矩 阵互为转置；约束条件符号则按一定规则转换为此首先说明原问题 ()P 及对偶问题 ()D 称为对偶的对称形式，它们是互相逆转的，现证明如下 . 由于上式的对偶问题本身仍旧是一线性规划问题，应用转置矩阵概念，可把它写成如下形式： m in ( ). . ( ) ( )0TTT T TTbws t A w cw 以 Tx 表示这个问题的对偶变量，则它的对偶问题为 m a x ( ). . ( ) ( )0TTT T TTxcs t x A bx 而这个问题即为该问题的左边问题，即原始的原问题 .因此得出如下的推论： 推论 3.1 对偶问题的对偶是原问题 . 任何形式的线性规划问题都能找到其对偶问题。对标准形式的线性规划问题：
