欢迎来到天天文库
浏览记录
ID:478408
大小:192.50 KB
页数:10页
时间:2017-08-09
《对偶线性规划理论及其在经济中的应用开题报告》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、开题报告对偶线性规划理论及其在经济中的应用一、选题的背景、意义[1]21世纪中国进入到了一个新的时代,随着经济的快速发展和社会的进步,整个社会运行的各个方面——无论是在政治、经济、文化、科技、军事、外交方面,还是在环境、生态、资源问题方面,都将着眼于解决能否实现的问题扩充到更加重视解决如何优化实现的问题,从解决局部的简单问题扩充到解决系统的复杂问题,从静态地解决问题到动态地解决问题,从解决涉及单一领域的独立发展问题扩充到解决涉及多个领域的协同发展的问题,从通过直接办法解决问题扩充到通过间接的办法解决问题等,都迫切需
2、要线性规划理论及其应用。随着计算机技术的发展和普及,线性规划的应用越来越广泛。它已成为人们合理利用有限资源制定最佳决策的有利工具。二、研究的基本内容与拟解决的主要问题2.1对偶线性规划理论概述2.1.1对偶线性规划理论的发展历程及现状[2][3]线性规划理论产生于20世纪30年代。1939年,苏联数学家康托罗维奇在《生产组织与计划中的数学方法》一书中,最早提出和研究了线性规划问题。1947年,美国数学家丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法─单纯形法,为这门学科奠定了基础。1947年,美国数学
3、家诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域,扩大了它的应用范围和解题能力。1951年,美国经济学家库普曼斯把线性规划应用到经济领域;1960年,康托罗维奇再次发表《最佳资源利用的经济计算》,创立了享誉全球的线性规划要点,对资源最优分配理论做出了贡献。为此,库普曼斯与康托罗维奇一起获1975年诺贝尔经济学奖。1984年,美国贝尔电话实验室的印度数学家卡马卡提出求解线性规划问题的投影尺度法,这是一个有实用意义的新的多项式时间算法。这个算法引起了人们对内点算法的关注,此后相继出现看多种更为简单实用的内点算法。
4、随着计算机技术的发展和普及,线性规划的应用越来越广泛。它已成为人们合理利用有限资源制定最佳决策的有利工具。由于对偶规划问题的全面性,考虑的多面性,现在的很多经济问题都通过对偶规划问题来解决。从而衍生出的影子价格也是现今各大企业在资产经营策略中一个非常重要的交易工具。它的应用已经遍及各大企业的经营策略中。2.1.2对偶问题的基本性质[4][5]给定一个线性规划问题使用向量与矩阵表示形式为1.对称性对偶问题的对偶是原问题。2.弱对偶性设和分别是问题和的可行解,则3.无界性问题和同时有最优解的充分必要条件是它们同时有可行
5、解。而且,若其中有一个问题无界,则另一个问题无解。4.强对偶性设和分别为和的可行解,则它们分别为和的最优解当且仅当5.互补松弛性设和分别为原问题和对偶问题的可行解,则它们分别为和的最优解当且仅当使用矩阵形式,可得和的互补松弛性条件:6.唯一性问题有非退化的最优基可行解,那么,其对偶规划有唯一的最优解。7.对偶变量的经济解释假定所讨论的是下面的线性规划问题其中——某工厂所拥有的种资源的总量;——生产每件第种产品需消耗第种资源的量。该问题的实际背景是在资源有限的条件下安排生产,以使效益最大。2.2线性规划的对偶原理及其
6、应用2.2.1对偶理论[6]以如下一对问题来表示线性规划问题的对偶:这里表示原问题,表示其对偶问题.注意到两个问题间的变换特点,这里为对偶问题的变量向量,每一个原问题的约束条件,对应一个对偶变量(个);每一个原问题变量对应一个对偶问题约束条件(个).原问题为求最大值,则对偶问题为求最小值.原问题与对偶问题中,其目标函数系数与右端常数互换;约束条件系数矩阵互为转置;约束条件符号则按一定规则转换为此首先说明原问题及对偶问题称为对偶的对称形式,它们是互相逆转的,现证明如下.由于上式的对偶问题本身仍旧是一线性规划问题,应用
7、转置矩阵概念,可把它写成如下形式:以表示这个问题的对偶变量,则它的对偶问题为而这个问题即为该问题的左边问题,即原始的原问题.因此得出如下结论:对偶问题的对偶是原问题.2.2.2对偶性的其他问题[7]对偶定理有多种解释,是由许多学者提出并以不同形式发表的,其中包括Fourier(1826),Gordan(1873),Minkowski(1896),Farkas(1901).定理6.16给出的是线性方程组的对偶定理.它的另一种形式是:线性方程组有解当且仅当对任意满足的行向量有成立.这是Fredholm(1903)提出的
8、.下面的系统有且只有一个是可行的:我们将给出线性不等式系统的对偶定理.首先我们给出由原问题导出对偶问题的方法.主要思想是利用原问题的线性约束找到它的最优值的一个下界,即我们线性地合并给定的约束来得到这个下界.对偶问题转化为:最大化此下界.2.2.3对偶规划问题的三种解法介绍[8]例2.1利用对偶转换规则,将下列线性规划模型转换为其对偶规划模型。某原问题的数学
此文档下载收益归作者所有