开题报告信息与计算科学对偶线性规划理论及其在经济中的应用一、选题的背景、意义[1]21世纪中国进入到了一个新的时代，随着经济的快速发展和社会的进步，整个社会运行的各个方面——无论是在政治、经济、文化、科技、军事、外交方面，还是在环境、生态、资源问题方面，都将着眼于解决能否实现的问题扩充到更加重视解决如何优化实现的问题，从解决局部的简单问题扩充到解决系统的复杂问题，从静态地解决问题到动态地解决问题，从解决涉及单一领域的独立发展问题扩充到解决涉及多个领域的协同发展的问题，从通过直接办法解决问题扩充到通过间接的办法解决问题等，都迫切需要线性规划理论及其应用。

随着计算机技术的发展和普及，线性规划的应用越来越广泛。

它已成为人们合理利用有限资源制定最佳决策的有利工具。

二、研究的基本内容与拟解决的主要问题2.1 对偶线性规划理论概述2.1.1 对偶线性规划理论的发展历程及现状[2] [3]线性规划理论产生于20世纪30年代。

1939年，苏联数学家康托罗维奇在《生产组织与计划中的数学方法》一书中，最早提出和研究了线性规划问题。

1947年，美国数学家丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法─单纯形法，为这门学科奠定了基础。

1947年，美国数学家诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。

1951年，美国经济学家库普曼斯把线性规划应用到经济领域；1960年，康托罗维奇再次发表《最佳资源利用的经济计算》，创立了享誉全球的线性规划要点，对资源最优分配理论做出了贡献。

为此，库普曼斯与康托罗维奇一起获1975年诺贝尔经济学奖。

1984年，美国贝尔电话实验室的印度数学家卡马卡提出求解线性规划问题的投影尺度法，这是一个有实用意义的新的多项式时间算法。

这个算法引起了人们对内点算法的关注，此后相继出现看多种更为简单实用的内点算法。

随着计算机技术的发展和普及，线性规划的应用越来越广泛。

它已成为人们合理利用有限资源制定最佳决策的有利工具。

由于对偶规划问题的全面性，考虑的多面性，现在的很多经济问题都通过对偶规划问题来解决。

从而衍生出的影子价格也是现今各大企业在资产经营策略中一个非常重要的交易工具。

它的应用已经遍及各大企业的经营策略中。

2.1.2 对偶问题的基本性质[4] [5]给定一个线性规划问题 1122111211121222221212min ..,,,0n n n n m m m m mn n c x c x c x a a a x b a a a x b s t x b a a a x x x +++⎛⎛⎛⎫⎫⎫ ⎪⎪⎪ ⎪⎪⎪≥ ⎪⎪⎪ ⎪⎪⎪ ⎭⎭⎭⎝⎝⎝≥ 使用向量与矩阵表示形式为 min max ()..()..00T T T T c xw b P s tAx bD s t w A c x w ≥≤≥≥ 1.对称性对偶问题的对偶是原问题。

2.弱对偶性设x 和w 分别是问题()P 和()D 的可行解，则 T Tc x w b ≥3.无界性问题()P 和()D 同时有最优解的充分必要条件是它们同时有可行解。

而且，若其中有一个问题无界，则另一个问题无解。

4.强对偶性设*x 和*w 分别为()P 和()D 的可行解，则它们分别为()P 和()D 的最优解当且仅当 **()T T c x w b =5.互补松弛性设*x 和*w 分别为原问题()P 和对偶问题()D 的可行解，则它们分别为()P 和()D 的最优解当且仅当**1**1()0,1,2,,()0,1,2,,n i ij j i j mj ij i j i b a x w i mc a w x j n==-==-==∑∑ 使用矩阵形式，可得*x 和*w 的互补松弛性条件：****()()0,()0T T w Ax b c w A x -=-=6.唯一性问题()P 有非退化的最优基可行解，那么，其对偶规划()D 有唯一的最优解。

7.对偶变量的经济解释假定所讨论的是下面的线性规划问题 max ()..0T c x P s t Ax b x ≤≥其中 b ——某工厂所拥有的m 种资源的总量；ij a ——生产每件第i 种产品需消耗第i 种资源的量。

该问题的实际背景是在资源有限的条件下安排生产，以使效益最大。

2.2 线性规划的对偶原理及其应用2.2.1 对偶理论[6]以如下一对问题来表示线性规划问题的对偶：:min :max 00P cxD wb s t Ax b s t wA c x w ≥≤≥≥这里P 表示原问题，D 表示其对偶问题.注意到两个问题间的变换特点，这里w 为对偶问题的变量向量，每一个原问题的约束条件，对应一个对偶变量（m 个）；每一个原问题变量对应一个对偶问题约束条件（n 个）.原问题为求最大值，则对偶问题为求最小值.原问题与对偶问题中，其目标函数系数与右端常数互换；约束条件系数矩阵互为转置；约束条件符号则按一定规则转换为此首先说明原问题()P 及对偶问题()D 称为对偶的对称形式，它们是互相逆转的，现证明如下.由于上式的对偶问题本身仍旧是一线性规划问题，应用转置矩阵概念，可把它写成如下形式：min ()..()()0T TT T T T b w s t A w c w --≥-≥以Tx 表示这个问题的对偶变量，则它的对偶问题为 max()..()()0T T T T T T x c s t x A b x --≤-≥而这个问题即为该问题的左边问题，即原始的原问题.因此得出如下结论：对偶问题的对偶是原问题.2.2.2对偶性的其他问题[7]对偶定理有多种解释，是由许多学者提出并以不同形式发表的，其中包括Fourier （1826），Gordan(1873),Minkowski(1896),Farkas(1901).定理6.16给出的是线性方程组的对偶定理.它的另一种形式是：线性方程组Ax b =有解当且仅当对任意满足0yA =的行向量有0yb =成立.这是Fredholm(1903)提出的.下面的系统有且只有一个是可行的：();()0,0.a Ax b b yA yb ==>我们将给出线性不等式系统的对偶定理.首先我们给出由原问题导出对偶问题的方法.主要思想是利用原问题的线性约束找到它的最优值的一个下界，即我们线性地合并给定的约束来得到这个下界.对偶问题转化为：最大化此下界.2.2.3 对偶规划问题的三种解法介绍[8]例2.1 利用对偶转换规则，将下列线性规划模型转换为其对偶规划模型。

某原问题的数学模型如下：12345123451234512345min 23523234233,,,,0z x x x x x x x x x x x x x x x x x x x x =++++++++≥-+++≥≥求解上式的对偶规划问题有三种方法。

第一种是先把上式转换为对偶模型，并让w 对应z ，让y 对应x ，使用普通的单纯形法线性规划程序求解出对偶规划的结果。

使用这种方法求解对偶规划问题，需要手工完成一次由原问题向对偶问题转换的过程，当问题规模较小时，使用这种方法不会出现多大的问题，但是当问题规模较大时，问题就来了，一是转换过程非常繁琐，工作量大；二是特别容易出错，效率很低。

第二种方法是利用计算机程序，直接读取原问题解算过程中自动生成的数据文件，自动地转换原问题为对偶问题，并直接求解，给出对偶规划的结果来。

第三种解法则是利用原问题的求解数据直接获得对偶问题的最优解。

2.2.4最优对偶变量（影子价格）的经济解释[9] [10]我们之所以对线性规划的对偶问题感兴趣，是由于对偶问题的最优解相对于原始线性规划问题有特殊的经济含意，它可以从另一个角度加深我们对原线规划模型最优解的理解。

对于线性规划的原始问题和对偶问题：原始问题 对偶问题求 max Z CX = 求 min Z b λ=满足 满足AX b X =≥ A C λ≥ 设B 为原始问题的最优基，且A 为m m ⨯的矩阵，A 的后n m -列组成子阵D ，C 的后n m -列组成子阵D C ，则此时相对成本向量1b D w C B D C -=-的每个分量都是非负的。

所以有1B D C B D C -≥而最优解为1B X B b -=。

下面就来验证：原始问题的最优基为B 时，其单纯形乘子向量1B C B λ-=即为相应对偶问题的最优解。

由于 1B C B λ-=所以有 111[,][,][,][,]B B B B B D A B D C B B C B D C C B D C C C λλλ---===≥=(因为1B D C B D C -≥)这样，A C λ≥得证。

因此，λ是对偶可行的。

又因为：1B B B b C B b C X λ-==这说明，λ作为对偶变量，其对偶问题目标函数值等于原始问题最优解时的目标函数。

根据对偶定理（如果线性规划的原始问题和对偶问题中，一个存在有限最优解，那么另一个也有最优解，而且相应的目标函数值相等；如果任何一个问题目标函数值无上界，那么另一个问题就无可行解。

）可知，λ应为对偶问题的最优解。

2.2.5 影子价格在企业经营管理中的应用[11] [12]一个线性规划对偶问题的最优解简称为“对偶最优解”，也称为“影子价格”，在经济上可以解释为约束条件所付出的代价。

在计算线性规划问题的检验数时，表示生产该项产品所消耗各项资源的影子价格的总和，即产品的隐含成本。

当产品的产值大于产品的隐含成本时，表明生产该项产品有利，可以安排；当产品的产值小于产品的隐含成本时，表明生产该项产品无利可图，用这些资源来生产别的产品可能更为有利，在生产计划中就不予安排了。

可见，影子价格为生产计划的安排提供了理论依据。

从另外一个角度看，资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。

由于企业生产任务，产品结构等情况发生变化，资源的影子价格也随之改变。

某种资源的影子价格高于市场价格，企业的管理者可以考虑对这种资源进行投入的增加，进而扩大生产规模，获得利润。

随着不断增加资源的投入量，资源的影子价格就会逐渐变小，当资源的影子价格等于市场价格时，就不应再增加该种资源的投入；某种资源的影子价格低于市场价格，企业的管理者应考虑把这种资源的一部分用来生产别的产品，随着减少该种资源的投入，资源的影子价格又会逐渐增加，当资源的影子价格等于市场价格时，不再减少该种资源。

可见，资源的影子价格又是一种机会成本。

对资源在市场价格方面的估算，买卖双方可以用影子价格来协商。

当然在资源的交易中，买方希望以低的价格买入，卖者希望以高的价格出让。

因此，其影子价格就成为买卖双方可接受的资源的合理价格.但即使对同一种资源的影子价格也将随着管理水平的不同和最优决策不同，发生不断的变化。