对偶问题在经济活动中的应用

1、湖北民族学院理学院毕业论文(设计) 开题报告 题 目 对偶问题在经济活动中的应用 专 业 数学与应用数学 班 级 0209409 学 号 020940907 学生姓名 谌小洋 指导教师 时凌 2013年5月24日一、 选题理由 运筹学是近六十年代发展起来的一门学科。运筹学在生产管理 工程技术 军事作战 科学实验 财政经济 社会科学以及自然科学和其他学科都已去的很多令人瞩目的成果。对偶问题是其中一个重要分支。对偶理论是线性规划最重要的内容之一，其应用范围十分广泛。主要用于研究有限资源的最佳分配问题，即如何对有限的资源做出最佳方式的太欧赔和最有利的使用，以便最从分得发挥资源的效能出过去最佳经济效益

2、。线性规划对偶单纯形法在实际应用中是一种非常有用的算法，线性规划问题是数学的一个重要分支,它们所研究的问题是讨论在众多的方案中什么样的方案是最优的,以及怎么找出这些最优方案.在现实的生产活动中这类问题普遍存在,例如在生产计划安排中,选择什么样的生产方案才能提高产值利润;在原料配给问题中,怎样确定各种成分的比例,才能使提高质量降低成本的目标得以实现:在城市建设规划中,怎样安排工厂、机关、学校、商店、医院、居民区以及其它单位的合理布局,才能方便群众,有利于城区各行各业的发展;在资源的分配问题中,怎样分配有限的资源,使得分配方案既能满足于各方面的基本要求,又能获得好的经济效益。 通过对偶单纯形法能有

3、效地解决最优化问题。本文通过对对偶问题及对偶单纯形法的介绍，并对其结果中所体现的经济现象中的影子价格做相应的解释，以实例完成一整套方法的应用，展现该方法在经济活动实例分析中的应用价值。二、 国内外研究现状综述 在线性规划早期发展中最重要的发现就是对偶问题，即每一个线性规划问题(称为原始问题)都有一个与它对应的对偶线性规划问题（称为对偶问题）。1928年美籍匈牙利数学家 J.von诺伊曼在研究对策论时已发现线性规划与对策论之间存在着密切的联系。两人零和对策可表达成线性规划的原始问题和对偶问题。他于1947年提出对偶理论。1951年G.B.丹齐克引用对偶理论求解线性规划的运输问题，研究出确定检验数

4、的位势法原理。1954年C.莱姆基提出对偶单纯形法，成为管理决策中进行灵敏度分析的重要工具。对偶理论有许多重要应用：在原始的和对偶的两个线性规划中求解任何一个规划时，会自动地给出另一个规划的最优解；当对偶问题比原始问题有较少约束时，求解对偶规划比求解原始规划要方便得多；对偶规划中的变量就是影子价格。三、 设计（论文）方案 通过对偶理论以及社会生产生活中相关现象的探究，发现对偶单纯形法能有效的解决最优化问题，是生产生活更方便。本文通过对对偶问题及对偶单纯形法的介绍，并对其结果中所体现的经济现象中的影子价格做相应的解释，以实例完成一整套方法的应用，展现该方法在经济活动实例分析中的应用价值。四、 重

5、点难点及创新之处 本文的重点在于对偶理论以及对偶理论在社会经济到横祸中的应用，并对其结果中所体现的经济现象中的影子价格做相应的解释，从而完成一整套的方法应用，体现对偶单纯形法在经济活动实例中的应用价值。五、 应收集资料及参考文献（不低于15篇）1 黄培青运筹学 ：管理中的定量方法 M上海 :上海交通大学出版社，20002 胡运权运筹学基础及运用M第四版 .北京 :高等教育出版社，20043 程理民运筹学模型与方法教程M北京: 清华大学出版社，20034 刘满凤 运筹学模型与方法教程例题分析与题解M北京：清华大学出版社，20045 郭耀煌运筹学原理与方法 M西安 :西南交通大学出版社，1998.

6、6 刁在钧. 运筹学.M.第三版.北京: 高等教育出版社 20077 邓成梁. 运筹学的原理和方法M.第二版.武汉：华中科技大学出版社，2001.8 胡运权.运筹学教程M.北京：清华大学出版社，1998.9 耿吉第.影子价格的经济含义及其应用J.数量经济技术研究，1994，（06）：46-47.10林丰岩.影子价格在企业管理中的应用J.价值工程，2006，（7）：15-17.11邓成梁.经济管理数学M.第二版.华中理工大学出版社，2003.12徐光辉.运筹学与基础手册M.北京：科学出版社，1993.13陶树人.技术经济学M.北京：经济管理出版社，1992.14甘应爱.运筹学M.北京：清华大学出

7、版社，1990.15J.富兰克林 著，俞建，顾悦译.数理经济学方法M.贵州人民出版社，198516何建坤.实用线性规划及其计算机程序M.清华大学出版社，1985.6、 进度安排（1） 四月上旬完成相关资料的查阅立即准备工作。（2） 四月中旬通过推相关知识的理解，确定研究的课题以及完成开题报告。（3） 四月下旬到五月上旬完成论文初稿。（4） 之后对论文进行不断的修改。七、指导教师意见指导教师签名：年月日八、专业负责人意见（或开题审查小组意见） 签名：年月日湖北民族学院理学院 数学与应用数学 专业毕业论文(设计)题 目 对偶问题在经济活动中的应用 设 计 人谌 小 洋教学基层组织名 称 教学基层组

8、织负责人 设 计 指 导 教 师 时 凌 评 阅 人 2013年5月15日 摘要 线性规划对偶单纯形法在实际应用中是一种非常有用的算法，线性规划问题是数学的一个重要分支,它们所研究的问题是讨论在众多的方案中什么样的方案是最优的,以及怎么找出这些最优方案.在现实的生产活动中这类问题普遍存在.关键词 线性规划 对偶单纯形法 最优方案 Abstract Dual simple method for linear programming is a very useful method in the practical application.the linear programming is an i

9、mportant branch of mathematics.the question is discussed in a large number of projects what kind of program is optimal .And how to find the optimal solution.These problems exist in practical production activities.Keywords:method for linear dual simple method the optimal scheme 第一章 对偶问题以及原理1.1 对偶问题 对

10、偶问题 每一个线性规划问题都伴随有另一个线性规划问题，称为对偶问题。原来的线性规划问题则称为原始线性规划问题，简称原始问题。对偶问题有许多重要的特征，它的变量能提供关于原始问题最优解的许多重要资料，有助于原始问题的求解和分析。对偶问题与原始问题之间存在着下列关系： 目标函数对原始问题是极大化，而对偶问题则是极小化。 原始问题目标函数中的收益系数是对偶问题约束不等式中的右端常数，而原始问题约束不等式中的右端常数则是对偶问题中目标函数的收益系数。 原始问题和对偶问题的约束不等式的符号方向相反。 原始问题约束不等式系数矩阵转置后即为对偶问题的约束不等式的系数矩阵。 原始问题的约束方程数对应于对偶问题

11、的变量数，而原始问题的变量数对应于对偶问题的约束方程数。 对偶问题的对偶问题是原始问题，这一性质被称为原始和对偶问题的对称性。1.2 对偶模型原始问题 对偶问题 式中max表示求极大值,min表示求极小值,s.t.表示“约束条件为”；为原始问题的目标函数，为对偶问题的目标函数；为原始问题的决策变量列向量，为对偶问题的决策变量行向量;为原始问题的系数矩阵,为原始问题的右端常数列向量，为原始问题的目标函数系数行向量。1.3对偶问题的基本定理 弱对偶定理 若上述原始问题和对偶问题分别有可行解和,则。这个定理表明极大化问题任一可行解的目标函数值总是不大于它的对偶问题的任一可行解的目标函数值。 强对偶定

12、理 若上述原始问题和对偶问题都可行，则它们分别有最优解x*和y*，且。 最优准则定理 若上述原始问题和对偶问题分别有可行解和,且两者的目标函数值相等，即,则两个可行解分别为对应线性规划的最优解。 互补松弛定理 若上述原始问题和对偶问题分别有可行解和，且和分别为它们的松弛变量,则当且仅当时，和分别为它们的最优解。 松弛定理 若上述原始问题和对偶问题分别有可行解和且和分别为它们的松弛变量，则当且仅当 和时, 和分别为它们的最优解。和这两个等式称为互补松弛条件。 对称对偶线性规划 具有对称形式的线性规划的特点是：全部约束条件均为不等式，对极大化问题为，对极小化问题为。全部变量均为非负。列出对称对偶线

13、性规划的步骤是：规定非负的对偶变量，变量数等于原始问题的约束方程数。把原始问题的目标函数系数作为对偶问题约束不等式的右端常数。把原始问题约束不等式的右端常数作为对偶问题的目标函数系数。把原始问题的系数矩阵转置后作为对偶问题的系数矩阵。把原始问题约束条件中的不等号反向作为对偶问题约束条件的不等号。将原始问题目标函数取极大化改成对偶问题目标函数取极小化。 非对称对偶线性规划 有时线性规划并不以对称方式出现，如约束条件并不都是同向不等式，变量可以是非正的或没有符号约束。列写非对称对偶线性规划可参照原始-对偶表（见表）按下列步骤进行：规定对偶变量，变量个数等于原始问题约束不等式数。把原始问题的目标函数

14、系数作为对偶问题约束不等式的右端常数。把原始问题约束不等式的右端常数作为对偶问题的目标函数系数。把原始问题的系数矩阵转置后作为对偶问题的系数矩阵。根据原始问题的约束不等式情况，确定对偶变量的符号约束。 根据原始问题决策变量的符号约束，确定对偶问题约束不等式的符号方向。 对偶问题的最优解 从原始问题的最终单纯形表中（最优单纯形算子）可直接得到对偶问题的最优解。原始问题中松弛变量的检验数对应着对偶问题的解（符号相反）。在用单纯形法时每一步迭代可得到原始问题的可行解和对偶问题的补充解,且,若不是原始问题的最优解，就不是对偶问题的可行解。最后一步迭代得到原始问题的最优解和对偶问题的补充最优解，且。是原

15、始问题的影子价格。1.4对偶单纯行法解题步骤单纯形法求解一般线性规划问题的基本方法，在应用对偶理论时，需要用到对偶单纯行法，就是将单纯行法应用于对偶问题的计算，基本思想是保持对偶问题为可行解（这时一般问题为非可行解）的基础上，通过迭代减小目标函数，当原问题也达到可行解时，即得到了目标函数的最优值，对偶单纯形法的解题步骤如下：（1） 建立初始单纯形表，设表中检验数行的值全部小于等于0，既是对偶问题的一个可行解；（2） 判断最优。检查列的数字，若均为非负，则已得到最优解，停止计算。若列有负分量则转（3) (3)换基迭代。确定换出变量。在单纯形表基解列中从上到下选负量所对应的基变量 出基。确定换入变

16、量。在单纯形表中若所在的行各系数（j=1,2，,n）即所有则无可行解，停止计算：否则在单纯形表中按最小值原则从到右变量进基解，返回（2）。1.5对偶单纯形法的优点及用途（1）初始解可以是非可行解，当检验数都是小于等于零时，就可以经行基变换，这样就避免了增加人工变量，使运算简化。（2） 对变量较少，而约束条件很多的线性规划问题可先将其变为对偶问题，再用对偶单纯形法求解，简化计算。（3） 用于灵敏度分析。1.6对偶问题的经济解释 对偶问题的产生不是凭空的，往往有其实际的经济来源，从对偶问题的基本性质看出，当达到最优解时，原问题与对偶问题的目标函数值相等，即现考虑最优解处，约束方程组右则常数变动对目

17、标函数的影响。求目标函数对的偏导数，可得这说明，若原问题的某一约束条件的约束条件的右则常数增加了一个单位，则由此引起最优目标函数值的增加量，就等于与改约束条件相对应的对偶变量的最优值，这样一开，在有限资条件下使受益最大话这一问题中，即可把对偶变量的最优值看成是相应资源，每一单位对于目标函数的贡献，也就是这些资源被从分利用时所能带来的利益。从而的值就相当于对单位这种资源在实现最大了利益时的一种价格估计，这种估计是针对企业具体产品而存在的一种特出价格。称之为影子价格。一般的，对线性规划问题的求解是确定资源的最优资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种古价直接涉及资源的

18、最有效利用，比如在一个大公司的内部，课借助资源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。又如在社会上可对一些最紧缺的资源借助影子价格，规定使用这种资源，以控制一些经济效益低的企业自觉的节约使用紧缺资源，使有限资源发挥更大的经济效益。有效的利用资源的影子价格指导经济活动是有重大意义的。 第二章 对偶问题的应用举例资源单位消耗产品 A B C 资源限量 劳动力 6 3 5 45 原料 3 4 5 30 单位利润 3 1 5 例一 某场准备生产A,B,C三种产品，需要消耗劳动力和原料两种资源，其有关数据如下表：（1） 用单纯形法确定总利润最大的生产计划。（2）

19、分别求出劳动力和资源的影子价格。若原料不够可到市场上够没，市场价为0.8元/单位。是否要购进？购进多少？利润增加多少？ 解 （1）依题意可得该问题的线性规划模型为： 其中分别为产品A,B,C的产量 该题用单纯形法迭代的过程如下表 31 500基b0456351003034501315010153-101-15610 0-300-1于是最优生产计划是生产A,B产品都是0，生产C产品=6可使得利润最大化，最大利润为30.（2） 劳动力和原料的影子价格分别是0和1，这说明在企业最优按排中，劳动力资源没有用完（实际只用了30单位），而原料资源一耗尽。根据题目书提供的条件很显然应该适量进购原料扩大生产。

20、 设购进的原料为，为保持最优基不变，必须有。而 解得：-3015.因而最多可购进原料12单位，总利润增加（单位）。净利润增加（单位） 例二 某工厂计划在下一个生产周期内生产甲、乙两种产品，要消耗、和三种资源（例如钢材、煤炭和设备），已知每件产品对这三种资源的消耗，这三种资源的现有数量和每件产品可获得利润如下表所示。问如何安排生产计划，使得既能从分利用现有资源，有使总例如最大？资源资源单价消耗产品甲 乙资源限制521702310015150单价例润1018根据问题要求，设决策变量、分别表示下个生产周期产品甲和乙的产量，基于约束条件，本例的数学模型为： 将其化为线性规划的的标准形式为： 其对偶问题

21、是：根据单纯形法求原问题的解，的最优单纯形表如下： 1018000 0 001 10 100 18 010 000 从上表中可以看出，原问题的最优解为;目标函数最优值为。根据互补松弛条件，则有： 即也就是说，原问题中的第一种资源（钢材）的影子价格为，第二种资源（煤炭）的影子价格为，第三种资源（设备台时）的影子价格为。此结果的经济意义为： （1）在现有资源的基础上，若再增加1吨煤，可使总利润增加 万元；若增加1个台时，可使总利润增加 万元。但增加1吨钢材，将不会是利润增加。 （2）对该企业来说，要加强对煤和机器设备的管理，在其不足时，要及时的补充该资源，从而保证生产计划，提高企业利润。同时，企业也可对这些资源采取囤积居奇的策略，即在资源市场价格较低，大量买进资源，以便在这些资源价格上涨时候高价卖出这些资源。 （3）可根据资源的影子价格，分析新产品使用资源的经济效果，一决定新产品是否应该投产。如考虑有两种新产品A和B，他们对资源的消耗定额以及可能获得的单件利润如下表所示，决定他们是否值得投产。资源资源单价消耗产品A B影子价格钢材120煤炭21机时34单价例润109计算产品A和B的相对价值系数： 则由于产品A所能提供的单件利润小于其隐含成本，相对价值系数，故产品A