1、 毕业论文文献综述 信息与计算科学 对偶线性规划理论及其在经济中的应用 一、前言部分 任一线性规划问题都存在另一与之伴随的线性规划问题，他们从不同角度对一个实际问题提出并进行描述，组成一对互为对偶的线性规划问题。 什么是“对偶问题”呢？对偶问题实际上是换一个角度来分析原问题。在线性规划分析方法中，假设原问题的目标是尽可能地利用可利用的资源来获得最大化利润的话，那么从问题的另一个侧面来思考问题，目标变成尽可能地利用原问题所给出的利润指标来调整范围条件来减少资源的消耗，于是以原问题目标函数中的决策变量系数作为新问 题的资源，其所形成的线性规划模型就成为对偶问题的线性规划模型。 当原问题与对偶问题的
2、最优化目标函数值相同时，可以揭示公平交易最为根本的东西：无论是从买方看，还是从卖方看，都实现了自己的交易目标最优化。在一桩交易中，卖方总是希望获利最大化，而买方则是希望采购成本最小化，他们的成交底线在哪里呢？从对偶规划的角度看，如果交易双方都是理性交易的话，他们的成交底线应该是相同的，即卖方的利益最大化目标值等于买方的成本最小化目标值。 1 所以，对偶线性规划理论在经济中的应用是很有实用价值，也是很值得研究的。 二、主题部 分 2.1 对偶线性规划理论概述 2.1.1 对偶线性规划理论的发展历程及现状 2 3 线性规划理论产生于 20 世纪 30 年代。 1939 年 ， 苏联数学家康托罗维奇
3、在生产组织与计划中的数学方法一书中 ，最早提出和研究了线性规划问题。 1947 年 ， 美国数学家丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法 单纯形法，为这门学科奠定了基础。 1947 年 ， 美国数学家诺伊曼提出对偶理论 ,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。 1951 年 ， 美国经济学家库普曼斯把线性规划应用到经济领 域 ； 1960 年， 康托罗维奇 再次发表 最佳资源利用的经济计算 ，创立了享誉全球的线性规划要点，对资源最优分配理论做出了贡献。 为此 ， 库普曼斯与康托罗维奇一起获 1975 年诺贝尔经济学奖 。 1984 年 ， 美国贝
4、尔电话实验室的印度数学家卡马卡提出 求 解线性规划问题的 投影尺度法，这是一个有实用意义的 新的多项式时间算法。 这个算法引起了人们对内点算法的关注，此后相继出现看多种更为简单实用的内点算法。随着计算机技术的发展和普及，线性规划的应用越来越广泛。它已成为人们合理利用有限资源制定最佳决策的有利工具。 由于对偶规划问题的全面性 ，考虑的多面性，现在的很多经济问题都通过对偶规划问题来解决。从而衍生出的影子价格也是现今各大企业在资产经营策略中一个非常重要的交易工具。它的应用已经遍及各大企业的经营策略中。 2.1.2 对偶问题的基本性质 4 5 给定一个线性规划问题 1 1 2 21 1 1 2 1 1
5、12 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 使用向量与矩阵表示形式为 m in m a x( ) . . ( ) . .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.强对偶
6、性 设 *x 和 *w 分别为 ()P 和 ()D 的可行解，则它们分别为 ()P 和 ()D 的最优解当且仅当 *()TTc x w b 5.互补松弛性 设 *x 和 *w 分别为原问题 ()P 和对偶问题 ()D 的可行解，则它们分别为 ()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 6.唯一性 问题
7、()P 有非退化的最优基可行解，那么，其对偶规划 ()D 有唯一的最优解。 7.对偶变量的经济解释 假定所讨论的是下面的线性规划问题 m a x( ) . .0TcxP s t Ax bx其中 b 某工厂所拥有的 m 种资源的总量； ija 生产每件第 i 种产品需消耗第 i 种资源的量。 该问题的实际背景是在资源有限的条件下安排生产，以使效益最大。 2.2 线性规划的对偶原理及其应用 2.2.1 对偶理论 6 以如下一对问题来表示线性规划问题的对偶： : m in : m a x. . . .00P c x D wbs t Ax b s t wA cxw这里 P 表示原问题， D 表示其对偶
8、问题 . 注意到两个问题间的变换特点，这里 w 为对偶问题的变量向量，每一个原问题的约束条件，对应一个对偶变量（ m 个）；每一个原问题变量对应一个对偶问题约束条件（ n 个） .原问题为求最大值，则对偶问题为求最小值 .原问题与对偶问题中，其目标函数系数与右端常数互换；约束条件系数矩阵互为转置；约束条件符号则按一定规则转换为此首先说明原问题 ()P 及对偶问题 ()D 称为对偶的对称形式，它们是互相逆转的，现证明如下 . 由于上式的对偶问题本身仍旧是一线性规划问题，应用转置矩阵概念，可把它写成如下形式： m in ( ). . ( ) ( )0TTT T TTbws t A w cw 以 T
9、x 表示这个问题的对偶变量，则它的对偶问题为 m a x ( ). . ( ) ( )0TTT T TTxcs t x A bx 而这个问题即为该问题的左边问题，即原始的原问题 .因此得出如下结论：对偶问题的对偶是原问题 . 2.2.2 对偶性的其他问题 7 对偶定理有多种解释，是由许多学者提出并以不同形式发表的，其中包括( 1 8 2 6 ) , ( 1 8 7 3 ) , ( 1 8 9 6 ) , ( 1 9 0 1 ) .F o u r ie r G o r d a n M in k o w s k i F a r k a s 定理 6.16 给出的是线性方程组的对偶定理 .它的另 一
10、种形式是：线性方程组 Ax b 有解当且仅当对任意满足 0yA 的行向量有 0yb 成立 .这是 (1903)Fredholm 提出的 . 下面的系统有且只有一个是可行的： ( ) ; ( ) 0 , 0 .a A x b b yA yb 我们将给出线性不等式系统的对偶定理 .首先我们给出由原问题导出对偶问题的方法 .主要思想是利用原问题的 线性约束找到它的最优值的一个下界，即我们线性地合并给定的约束来得到这个下界 .对偶问题转化为：最大化此下界 . 2.2.3 对偶规划问题的三种解法介绍 8 例 2.1 利用对偶转换规则，将下列线性规划模型转换为其对偶规划模型。 某原问题的数学模型如下： 1
11、 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 5m in 2 3 5 2 32 3 42 3 3, , , , 0z x x x x xx x x x xx x x x xx x x x x 求解上式的对偶规划问题有三种方法。 第一种是先把上式转换为对偶模型，并让 w 对应 z ，让 y 对应 x ，使用普通的单纯形法线性规划程序求解出对偶规划的结果。使用这种方法求解对偶规划问题，需要手工完成一次由原问题向对偶问题转换的过程，当问题规模较小时，使用这种方法不会出现多大的问题，但是当问题规模较大时，问题就来了，一是转换过程非常繁琐，工作量大；二是特别容易出错，效率很低。 第
12、二种方法是利用计算机程序，直接读取原问题解算过程中自动生成的数据文件，自动地转换原问题为对偶问题，并直接求解，给出对 偶规划的结果来。 第三种解法则是利用原问题的求解数据直接获得对偶问题的最优解。 2.2.4 最优对偶变量（影子价格）的经济解释 9 10 我们之所以对线性规划的对偶问题感兴趣，是由于对偶问题的最优解相对于原始线性规划问题有特殊的经济含意，它可以从另一个角度加深我们对原线规划模型最优解的理解。 对于线性规划的原始问题和对偶问题： 原始问题 对偶问题 求 max Z CX 求 min Zb 满足 满足 0AXbXAC 设 B 为原始问题的最优基，且 A 为 mm 的矩阵， A 的后
13、 nm 列组成子阵 D， C 的后nm 列组成子阵 DC ， 则此时相对成本向量 1bDw C B D C 的每个分量都是非负的。所以有 1BDC B D C 而最优解为 1BX B b 。 下面就来验证：原始问题的最优基为 B 时，其单纯形乘子向量 1BCB 即为相应对偶问题的最优解。 由于 1BCB 所以有 111 , , , , BBB B B DA B D C B B C B DC C B D C C C (因为 1BDC B D C ) 这样， AC 得证。 因此， 是对偶可行的。又因为： 1B B Bb C B b C X 这说明， 作为对偶变量，其对偶问题目标函数值等于原始问题最
14、优解时的目标函数。根据对偶定理（如果线性规划的原始问题和对偶问题中，一个存在有限最优解，那么另一个也有最优解，而且相应的目标函数值相等；如果任何一个问题目标函数值无上界，那么另一个问题就无可行解。） 可知， 应为对偶问题的最优解。 2.2.5 影子价格在企业经营管理中的应用 1112 一个线性规划对偶问题的最优解简称为“对偶最优解”，也称为“影子价格”，在经济上可以解释为约束条件所付出的代价。 在计算线性规划问题的检验数时， 表示生产该项产品所消耗各项资源的影子价格的总和，即产品的隐含成本。当产品的产值大于产品的隐含成本时，表明生产该项产品有利，可以安排；当产品的产值小于产品的隐含成本时，表明
15、生产该项产品无利可图，用这些资源来生产别的产品可能更为 有利，在生产计划中就不予安排了。可见，影子价格为生产计划的安排提供了理论依据。从另外一个角度看，资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务，产品结构等情况发生变化，资源的影子价格也随之改变。某种资源的影子价格高于市场价格，企业的管理者可以考虑对这种资源进行投入的增加，进而扩大生产规模，获得利润。随着不断增加资源的投入量，资源的影子价格就会逐渐变小，当资源的影子价格等于市场价格时，就不应再增加该种资源的投入；某种资源的影子价格低于市场价格，企业的管理 者应考虑把这种资源的一部分用来
16、生产别的产品，随着减少该种资源的投入，资源的影子价格又会逐渐增加，当资源的影子价格等于市场价格时，不再减少该种资源。可见，资源的影子价格又是一种机会成本。对资源在市场价格方面的估算，买卖双方可以用影子价格来协商。当然在资源的交易中，买方希望以低的价格买入，卖者希望以高的价格出让。因此，其影子价格就成为买卖双方可接受的资源的合理价格 .但即使对同一种资源的影子价格也将随着管理水平的不同和最优决策不同，发生不断的变化。因此，企业生产的经营者可通过调整自己的生产计划，保持企业一直处在“ 最优”的状态下，使资源的配置更加合理，使企业的利润不断提高。企业管理水平和技术水平也能在资源的影子价格中体现出来。
17、对于同一种资源，其影子价格高的企业管理水平和技术水平就高，同样的投入产生的效益高于其他企业，这样在资源投入增加时就掌握了主动性，也就增加了获得利润的机会。 三、总结部分 本文总的介绍了对偶线性规划的定义以及一些特殊属性，还有对偶规划的一种延生 影子价格。主要是为了说明以下线性规划在实际应用中两点：一方面考虑在一定资源限制条件下，如何安排生产使工作成果最大；另一方面要求，如何计划生产，使完成既定 任务的前提下，消耗最少。并且在各大企业中的应用已经变得越来越广泛，已经成为一种不可或缺的手段，是为了买卖双方获得双赢利益的最大保障。 13 14 影子价格在对偶规划行业有着很大的发展前景，它也日渐成为企
18、业挖潜革新的途径，且对市场资源的最优配置起着推进作用。它可以预测产品的价格，并作为同类企业经济效益评估指标之一。 15 四、参考文献 1 高红卫 .实用线性规划工具 M.北京：科学出版社， 2007， 1： 119-119. 2 运筹学编写组 .运筹学 M.第三版 .北京 :清华大学出版社， 2005， 6:1-2. 3 张干宗 .线性规划 M.第二版 .武汉 :武汉大学出版社， 2008， 6:1-1. 4 朱德通 .最优化模型与实验 M.上海：同济大学出版社， 2003， 4： 49-50. 5 胡运权，郭耀煌 .运筹学教程 M.第三版 .北京：清华大学出版社， 2007， 4： 55-5
19、7. 6 胡清淮，魏一鸣 .线性规划及其应用 M.北京：科学出版社， 2004， 3： 94-95. 7 Leonid Nison Vaserstein,Christopher Cattelier Byrne.Introduction to Linear Programming to Linear ProgrammingM.Beijing:China Machine Press， 2006， 1： 125-126. 8 高红卫 .线性规划方法应用详解 M.北京：科学出版社， 2004， 7： 101-102. 9 江道琪，何建坤，陈松华 .实用线性规划方法及其支持系统 M.北京：清华大学出版社
20、， 2006， 4： 45-46. 10 张干宗 .线性规划 M.第二版 .武汉：武汉大学出版社， 2008， 6： 92-92. 11 姚军， 苑延华 .浅谈线性规划对偶问题的经济解释 影子价格 J.商业文化， 2009， 12： 270-270. 12 徐渝，贾涛 .运筹学（上册） M.北京：清华大学出版社， 2005， 2： 58-58. 13 邱菀华，冯允成，魏法杰，周泓 .运筹学教程 M.北京：机械工业出版社， 2004， 5:42-42. 14 Frederick S.Hillier,Gerald J.Lieberman.Introduction to Operations Research(Eighth Edition)M.北京：清华 大学出版社， 2006， 1:210-210. 15 宁宣熙，王可定，党耀国 .管理运筹学教程 M.北京：清华大学出版社， 2007， 8:37-37.
