什么是线性规划?

[拼音]：xianxing guihua

[外文]：linear programming

研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。

法国数学家 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年代后线性规划的应用范围不断扩大。

要对实际规划问题作定量分析，必须先加以抽象，建立数学模型。在建立线性规划模型时，需要有关的专业知识，并要有一定的经验和技巧。建立线性规划模型包括：

（1）明确问题的目标和划定决策实施的范围（包括时间界限），并将目标表达成决策变量的线性函数，称为目标函数。

（2）选定决策变量和参数。决策变量就是待决定的问题的未知量，一组决策变量的取值即构成一个规划方案。决策变量的选定往往需要对问题进行仔细的分析。

（3）建立约束条件。问题的各种限制条件称为约束条件。每一个约束条件均表达成决策变量的线性函数应满足的等式或不等式。约束条件往往不止一个，通常表达成一组线性等式或不等式。线性规划问题就是在决策变量满足一组约束条件的情况下使目标函数达到极大值或极小值。

一般线性规划模型的形式为：

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万元。

在工业、农业、商业、行政、军事、公用事业等各个领域，存在着大量的线性规划问题。有些规划问题本身是非线性的，但往往可以通过改变标度或采用分段线性化等方法，转化为线性规划模型。

用线性规划求解的典型问题有运输问题、生产计划问题、配套生产问题、下料和配料问题等。

（1）运输问题 某产品有n个产地，m个销地。已知各产地的产量和各销地的销量，以及各产地到各销地的单位运价，问如何安排各产地到各销地的运量，使总的运费为最少？

（2）生产计划问题 用m种资源生产m种产品。已知各种产品每生产一单位可得的利润和所需的各种资源的数量，以及各种资源的限额。问如何计划各种产品的生产量，使总的利润为最大?

（3）配套生产问题 用若干台机床加工某种产品的各种零件。已知各机床加工不同零件的效率。问如何分配各机床的任务，在零件配套的前提下使一个生产周期内的产量最高？

（4）下料问题 将一批固定规格的条材或板材裁剪成具有规定尺寸的若干种毛坯，并已设计出若干种下料方式。问采用哪种下料方式，能使各种毛坯满足所需数量，又使总的用料最省？

（5）混合配料问题 用n种原料配制某些含有m种成分的产品。已知各种成分在各种原料中的单位含量，以及各种原料的单价和限额。问怎样混合调配，在满足产量要求和产品所含各种成分的要求下使成本为最低？

参考书目

G.Dantzig,Linear Programming and Extensions，Princeton University Press, Princeton, New Jersey,1963.S.Gass,Linear Programming,4th ed.，McGraw-Hill,New York,1975.L.S.Srinath,Linear Programming: Principles and Applications, Macmillan Press, New York,1983.