关于线性规划介绍

[拼音]：xianxing guihua

[外文]：linear programming

是数学规划中理论成熟，方法有效，应用最广泛的一个分支。它研究线性的目标函数的极值，而自变量必须满足一组线性等式与不等式组成的约束条件。

线性规划最早的工作始于20世纪30年代。1939年苏联数学家Л.Β.坎托罗维奇发表的名为《生产组织与计划中的数学方法》的小册子，是有关线性规划的最早文献。在这以后，美国也开始研究这个问题，早期最有影响的是F.L.希契科克研究的运输问题及其解。但是，他们的工作都没有受到注意。由于战争的需要，军事中有关规划、计划、侦察、后勤、生产等各方面的问题都陆续被提出来，系统的研究线性规划的解法与应用便被提到日程上来了。1947年，G.B.丹齐克提出了一般的线性规划模型和理论（线性规划的名称也是他首先提出的），以及著名的单纯形方法，从而奠定了数学规划作为一门学科的基石。直到现在，单纯形方法仍然是这门学科中的有力工具。

从50年代起，线性规划的应用逐渐从军事扩大到其它领域。例如，1951年T.C.库普曼斯结合W.列昂季耶夫投入产出模型将线性规划应用于生产问题；J.冯·诺伊曼研究矩阵对策与线性规划的关系，将它应用于经济平衡问题。大型电子计算机的出现对线性规划的理论以及应用的发展起着决定性的作用。在经济领域中广泛地应用线性规划方法，并且利用电子计算机已能解决变量个数达数百万之多的具有特殊结构的大型线性规划问题。

可以用一个简单的例子来说明，一个工厂生产甲、乙两种产品，假设产品甲受某种所需原料的限制，每周最多只能生产8个单位，又假设甲、乙同时需要的另一种原料每周供应60公斤，而生产每单位产品甲需原料5公斤，乙需要2公斤。此外，生产甲、乙需要同一台机器，且单位产品加工时间甲需2小时，乙需4小时，每周机械最多工作80小时。如果甲的单价为15元，乙为10元，若以生产总值最大为目标，且令甲、乙的产量分别为x1，x2，那么，问题是要确定x1与x2的值，使满足约束条件：x1≤8，5x1+2x2≤60，2x1+4x2≤80，x1≥0，x2≥0＝且使目标函数ƒ(x)=15x1+10x2取最大值。下面借助附图来说明这个简单线性规划问题的解的基本性质。

满足约束条件的每一个点称为可行解。可行解的全体组成的集合称为可行解集。在所有可行解中求出一个使目标函数取最大值的可行解，这个可行解称为最优解。

上述问题的可行解集形成图中多边形ABCDE围成的区域，它有5个顶点A，B，C，D，E。如果赋于目标函数一个给定的值d，则称ƒ(x)=d为目标函数的等值线，如图

中虚线所示。在不同的等值线上，目标函数取不同的值，虚线愈向右移动，相应的目标函数值愈大。显然，在顶点C=(5，17.5)处，目标函数ƒ(x)达到可行解集上的最大值。因为虚线再向右移动便离开了可行解集。因此最优解是x1=5，x2=17.5，目标函数的最大值为ƒ(x)=15x1+10x2=250。

上例说明，线性规划的最优解可以在可行解集的某一个顶点上达到。这对于未知变量多于两个和可行解集不是有界的情形也是正确的，是线性规划解的一个基本性质。根据这一性质，为了求最优解，只须比较目标函数在有限个顶点上的值。然而，对于变量和约束条件很多的情形，顶点数目很大，必须采用有效方法和借助于电子计算机来求解，单纯形方法就是基于此性质而建立的计算方法。

1947年由丹齐克建立的解决线性规划问题的有效方法。它解决如下的标准型线性规划问题：

(1)

满足约束条件：

(2)

， (3)

式中m≤n;αij，сj，bj为常数；系数矩阵A=(αij)的秩为m。不失一般性可设bj≥0，i=1， 2，…，m ；minƒ(x)表示求ƒ(x)的极小值。若问题中包含不等式约束αi1x1+…+αinxn≤bj，则可增加一个非负的松弛变量xn+j使之化为等式αi1x1+…+αinxn+xn+j=bj，xn+j≥0。若问题是求目标函数ƒ(x)的最大值，则可等价地化为求-ƒ(x)的最小值。若变量xj无非负要求，则可令再代入各式。例如，通过引进松弛变量x3，x4，x5，前面的举例可化为标准形式

这时，顶点A，B，C，D，E分别对应于可行解:(8，0，0，20，64)，(8，10，0，0，24)，(5，17.5，3，0，0)，(0，20，8，20，0)，(0，0，8，60，80)。它们都只有3个变量取正值，另2个变量取零值，称为基础可行解。一般，满足约束条件(2)、(3)的可行解x=(x1，x2，…，xn)，若其中 n-m个变量取零值，且其他m个变量在(2)中对应的系数矩阵（记作B，称为可行基）非异，则称x为一基础各行解，它对应于可行解集的一个顶点。这m个变量称为基变量，其他n-m个称为非基变量。由前面所叙的线性规划解的基本性质，如果最优解存在，必可在一基础可行解上达到。单纯形方法的基本步骤就是从一个基础可行解迭代到另一个使目标函数得到改进（或至少不退步）的基础可行解，并且通过某种判断准则可以判定它是否为最优解，或判定问题不存在最优解而停止计算。为简化讨论，采用矩阵符号，将问题(1)～(3)写为：

设已知一可行基B，将A分块为A=(B，N)，相应地C =，其中xB的m个分量为基变量，xN的n-m个分量xj(j∈J)为非基变量，J为非基变量的下标集合。于是(5)可写为

(7)

式中 αj表示A的第 j列。记，，则(7)式可写为

， (8)

令xj=0(j∈J)，则(因B为可行基)，故为基础可行解，其相应目标函数值为。考虑任一可行解x，则由(8)，

， (9)

记 。分三种情形讨论：

（1）若所有σj≥0，j∈J，则对任意可行解x，由(9)式有ƒ(x)≥ƒ(x0)，所以x0为最优解；

（2）若有某个σk<0，k∈J，且所有yik≤0，i=1，2，…，m则当取xk>0 而保留其他非基变量为零时，由(8)式有

， (10)

易见xk取任何正值都有x≥0，i=1，…，m ，这时相应的目标函数值随xk增大而无限制减小，因此问题没有有限最优值，计算停止：③若有某个σk<0但某些yik>0，则由(10)式可知，若令

，

其余非基变量保持为零，则所有基变量非负，且基变量xBl=0，以xk取代xBl作为新的基变量，便得到一个新的基础可行解，其相应的目标函数值减少（xk>0时）或不变（当xk=0时）。为了继续进行迭代，须要计算它所对应的y0与yj等。由于新的基峺与B的不同仅在于用αk代替B的第l列，故不难由(8)式导出，与y0，yj的关系：

，

式中当j∈挓J时，定义yij为当i=j，yij=1；当i≠j，yij=0。上述过程不断重复，直到求得最优解或判断问题无有限最优值为止。在用人工进行计算时，往往将(8)与(9)式的系数排列成单纯形表格，在表上进行运算，十分方便有效。

每个线性规划问题都有一个被称为它的对偶问题的线性规划问题与之对应。如线性规划问题(4)～(6)的对偶问题为

式中u=(u1，u2…um)T。在经济上u称为影子价格。线性规划的对偶形式及其重要性和著名的对偶定理，是冯·诺伊曼首先发现的。

若原问题与对偶问题之一有有限最优解，则另一问题亦有有限最优解，且两者的目标函数值相等，即mincTx=maxbTu。若其中之一无有限最优值，则另一问题无可行解。

基于对偶理论，与单纯形法有密切联系的，有对偶单纯形法，原始对偶单纯形法等；由于计算数学、特别是数值代数的发展，单纯形法的具体实现已经有了很大发展，并且形成了许多能够有效解决大型线性规划问题的计算机软件包，但是从理论上讲，单纯形法不是多项式算法(见组合最优化)，苏联数学家Л.Γ.哈奇扬于1979年提出了著名的线性规划多项式算法，或称椭球体算法，从理论上证明了线性规划问题属于p问题，解决了十多年来悬而未决的问题。但只是理论结果，这一方法距离实际应用还很远。1984年，印度数学家N.卡马卡提出一个新的多项式算法──投影算法，在理论上优于椭球体算法，在实际计算效果上，也显示了高速度，引起了运筹学界的重视。

是一类特殊的线性规划问题，它是由Л.Β.坎托罗维奇与F.L.希契科克分别提出的。其基本提法如下：

设某种产品的产地为A1，A2，…，Am；Ai的产量为αi，若欲将产品从产地运往销地B1，B2，…，Bn；Bj的销量为bj，且。已知单位产品从Ai运到Bj的运价为Cij，1≤i≤m，1≤j≤n。问如何调运产品使总的运费最小？

设xij为从Ai运到Bj的产品数量，则上述问题的数学模型为

，

满足约束条件：

对于解决运输问题，较有效的解法是网络流方法和表上作业法。如果将产地和销地及其间的距离在图上表示，且要求的是吨公里数最小，则可以用图上作业法求解。这个方法是50年代初中国粮食部门的同志的经验总结，中国科学院的运筹学工作者从数学上严格论证了它的最优性。图上作业法的要点是：

（1）没有对流，即在任何一段运输路线上没有相对往返的运输；

（2）没有迂回，在一条封闭成圈的回路上，从一点到另一点的运输要走小半圈，若走大半圈就是迂回。

上述方法简单易懂，只需在图上进行计算和调整，便可得到吨公里最小的方案。

参考书目

1. 中国科学院数学研究所运筹室编：《运筹学》，科学出版社，北京，1973。
2. G.B.Dantzig，Lineαr Progrαmming， PrincetonUniv.Press， Princeton， 1963.