对偶线性规划理论及其在经济中的应用文献综述

《对偶线性规划理论及其在经济中的应用文献综述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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.对称性对偶问题的对偶是原问题。2.弱对偶性设和分别

5、是问题和的可行解，则3.无界性问题和同时有最优解的充分必要条件是它们同时有可行解。而且，若其中有一个问题无界，则另一个问题无解。4.强对偶性设和分别为和的可行解，则它们分别为和的最优解当且仅当5.互补松弛性设和分别为原问题和对偶问题的可行解，则它们分别为和的最优解当且仅当使用矩阵形式，可得和的互补松弛性条件：6.唯一性问题有非退化的最优基可行解，那么，其对偶规划有唯一的最优解。7.对偶变量的经济解释假定所讨论的是下面的线性规划问题其中——某工厂所拥有的种资源的总量；——生产每件第种产品需消耗第种资源的量。该问题的实际背景是在资源有限的条件下安排生产，以使效益最大。2.2

6、线性规划的对偶原理及其应用2.2.1对偶理论[6]以如下一对问题来表示线性规划问题的对偶：这里表示原问题，表示其对偶问题.注意到两个问题间的变换特点，这里为对偶问题的变量向量，每一个原问题的约束条件，对应一个对偶变量（个）；每一个原问题变量对应一个对偶问题约束条件（个）.原问题为求最大值，则对偶问题为求最小值.原问题与对偶问题中，其目标函数系数与右端常数互换；约束条件系数矩阵互为转置；约束条件符号则按一定规则转换为此首先说明原问题及对偶问题称为对偶的对称形式，它们是互相逆转的，现证明如下.由于上式的对偶问题本身仍旧是一线性规划问题，应用转置矩阵概念，可把它写成如下形式：

7、以表示这个问题的对偶变量，则它的对偶问题为而这个问题即为该问题的左边问题，即原始的原问题.因此得出如下结论：对偶问题的对偶是原问题.2.2.2对偶性的其他问题[7]对偶定理有多种解释，是由许多学者提出并以不同形式发表的，其中包括定理6.16给出的是线性方程组的对偶定理.它的另一种形式是：线性方程组有解当且仅当对任意满足的行向量有成立.这是提出的.下面的系统有且只有一个是可行的：我们将给出线性不等式系统的对偶定理.首先我们给出由原问题导出对偶问题的方法.主要思想是利用原问题的线性约束找到它的最优值的一个下界，即我们线性地合并给定的约束来得到