线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的
 |
| 线性规划 |
线性规划概述编辑本段回目录
在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素.
发展简史编辑本段回目录
法国数学家 J.- B.- J.傅里叶和 C.瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。1947年美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法，为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。1979年苏联数学家Л.Г.哈奇扬提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。
数学模型编辑本段回目录
一般线性规划模型的形式为：
max(或min)
s.t.
(≤,＝或≥)bi (i=1,2,…,m)
xj≥0 (j=1,2,…,n)
式中max表示求极大值；min表示求极小值；s.t.表示受约束于或约束条件是;Z为目标函数;xj为决策变量；aij，bi和cj分别为消耗系数、需求系数和收益系数, 在具体的线性规划问题中具有不同的经济学意义，一般都是已知实数。在线性规划中满足约束条件的一组数(x1,x2,…,xn)称为问题的一个可行解,全体可行解构成的集合称为问题的可行域。在可行域上使目标函数取得极大值（或极小值）的可行解称为问题的最优解，对应的目标函数值称为最优值。
解题算法 编辑本段回目录
求解线性规划问题的基本方法是单纯形法，现在已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。为了提高解题速度，又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题，也可采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解，但实用价值不大。通过图解法求解可以理解线性规划的一些基本概念。
例如，某工厂生产A，B两种产品,已知生产A1千克，耗煤9吨，耗电4千瓦，用劳力3个工；生产B1千克，耗煤4吨，耗电5千瓦，用劳力10个工。已知生产1千克A的利润是500元，生产1千克B的利润是900元。现根据工厂条件，只能提供煤360吨，电力200千瓦,劳力300个工。问如何安排两种产品的生产量，才能使总的利润最大。
设A，B 的产量分别为x1，x2（千克）,则上述问题的线性规划模型是：
max Z＝5x1＋9x2
s.t. 9x1＋4x2≤360
4x1＋5x2≤200
3x1＋10x2≤300
x1≥0，x2≥0
此问题的可行域为图中的多边形区域，即阴影部分。目标函数的等值线为平行于直线 l的平行直线族。将直线l向右上方平行移动，对应的目标函数值逐渐增大,在即将脱离可行域之际，它与可行域的交点便对应于问题的最优解。由此可知,在可行域的顶点B 处,目标函数达到最大值。因此,问题的最优解为:x1＝20千克,x2＝24千克，最大总利润为3.16万元。 
应用问题编辑本段回目录
在工业、农业、商业、行政、军事、公用事业等各个领域，存在着大量的线性规划问题。有些规划问题本身是非线性的，但往往可以通过改变标度或采用分段线性化等方法，转化为线性规划模型。
用线性规划求解的典型问题有运输问题、生产计划问题、配套生产问题、下料和配料问题等。
①运输问题 某产品有n个产地，m个销地。已知各产地的产量和各销地的销量，以及各产地到各销地的单位运价，问如何安排各产地到各销地的运量，使总的运费为最少？
②生产计划问题 用m种资源生产m种产品。已知各种产品每生产一单位可得的利润和所需的各种资源的数量，以及各种资源的限额。问如何计划各种产品的生产量，使总的利润为最大?
③配套生产问题 用若干台机床加工某种产品的各种零件。已知各机床加工不同零件的效率。问如何分配各机床的任务，在零件配套的前提下使一个生产周期内的产量最高？
④下料问题 将一批固定规格的条材或板材裁剪成具有规定尺寸的若干种毛坯，并已设计出若干种下料方式。问采用哪种下料方式，能使各种毛坯满足所需数量，又使总的用料最省？
⑤混合配料问题 用n种原料配制某些含有m种成分的产品。已知各种成分在各种原料中的单位含量，以及各种原料的单价和限额。问怎样混合调配，在满足产量要求和产品所含各种成分的要求下使成本为最低？
线性规划的应用编辑本段回目录
在企业的各项管理活动中,例如计划、生产、运输、技术等问题,线性规划是指从各种限制条件的组合中,选择出最为合理的计算方法,建立线性规划模型从而求得最佳结果.
配图编辑本段回目录
 |
| 线性规划 |
相关连接编辑本段回目录
www.math123.cn/Upfiles/20070903084530.doc
education.ti.com/sites/CHINA/downloads/pdf/math_bj_t10.pdf
wiki.mbalib.com/wiki/线性规划
相关词条编辑本段回目录
数学、应用数学、最优化、非线性规划
参考书目编辑本段回目录
G.Dantzig,Linear ProgrammingandExtensions，PrincetonUniversityPress,Princeton,NewJersey,1963.
S.Gass,LinearProgramming,4thed.，McGraw-Hill,NewYork,1975.
L.S.Srinath,LinearProgramming:PrinciplesandApplications,MacmillanPress,NewYork,1983.
