线性规划

运筹学规划论的一个分支。在满足企业内外部约束的条件下，应用数学的方法使预定目标达到最优。内容可归纳为两个方面：系统的任务已定，如何合理筹划用最少的投入去实现这一任务；投入数量已定，如何对其合理利用使完成的任务最多。前者求极小值，后者求极大值。参见“数学”中的“线性规划”。

---

线性规划

见“企业管理”中的“线性规划”。

---

线性规划

见“规划论”。

线性规划

运筹学理论上最成熟而应用又最广泛的一个分支。它是研究在线性约束条件下使一个线性目标函数最优化（极大或极小化）的数学理论和方法。求解的方法有图上作业法、表上作业法、图解法和单纯形法等。线性规划的数学模型，包括一组约束条件和目标函数两个组成部分。主要应用于经营计划、交通运输、工程建设等方面。
线性规划的价值是：(1)改进计划。在适用的条件下，可以改进管理者的计划技巧，提高管理者的分析能力，它可以在很多可供选择的解法中作周密的检验并系统地寻找最优解法。(2)改进决策。在线性规划的一个解被选中以后，管理人员可修改或附加约束条件或改变目标，计算机可以根据修改的条件再提出一个新的解，供决策者抉择。(3)改进对问题的了解。线性规划模型对分析复杂的问题有较高的效能，能提高管理人员的鉴别力和理解力。
线性规划包括以下基本内容：(1)在线性规划问题中，必须有一个目标函数存在，在求得变量的数值后，能使此目标函数的数值达到最大或最小，如使产量最高、成本最低、资源消耗最小、运输路程最短、利润最多等等。(2)在约束条件下求目标函数的最大值或最小值。所谓约束条件是指资源的限制、市场需要的限制、设备的限制、劳动力的限制等等。(3)目标函数和约束条件式中的各个不等式都是一次式。假如以几何图形表示，这些函数或不等式都是直线。(4)在线性规划问题中，各个变量的系数都是固定的常数。如一个单位生产的产品所需的原材料的数量是固定的等等。(5)所有决策变量的数值，要求是正值或零，不得为负数，若为负数就没有实际的经济意义了。
线性规划模型在经济管理中主要解决以下三方面问题：(1)生产计划问题。在资源已定的情况下如何合理安排生产计划，使产量、利润最多，即求最大值。(2)资源分配问题。在任务已定的情况下，如何统筹安排，做到用最少的资源去完成既定的任务，即求最小值。(3)区域运输规划问题。研究如何将有限的经济资源以最有效的调配方案，运输到各个需要地，既能满足各地的需要量，又能使总的运输费最省。

线性规划Linear Programming

若干个线性等式（或不等式）的约束下求一个线性函数极值的问题。线性规划模型的标准形式为：

其中各b_i(i=1…m)均非负。对于任意一个线性目标函数，无论是求其极大还是极小，也无论各约束条件是等式还是不等式，各b_i是否非负，各变量是否要求非负，都可以通过一定的变换使其变为标准形，标准形也可简记为：

其中C^T＝(C₁…C_n)（向量）为目标函数的系数，Am×n（矩阵）为约束方程的系数。将线性规划模型的一般形式化为标准形式是为了便于运用单纯形法来求解，单纯形法的基本思想是：由线性约束方程在空间中围起的形体一定是一个多边形，而使目标函数达到极值的点（即最优解所代表的点）一定可以在多边形的顶点上找到，因此，我们只需先找到任意一个顶点，然后从这个顶点开始按一定的顺序寻找目标函数值比这个顶点小的下一个顶点。由于多边形的顶点是有限的，因此在经过了有限步的递推之后一定可以找到最优解。单纯形法的每一步操作都是固定而机械的，因此可以通过计算机来求解。在问题比较简单时，也可采用图解法，见图11-5。

图11-5

例：用图解法求解线性规划问题。

((max))Z=x₁+2x₂

图中两条实线分别是x₁+3x₂＝3和3x₁+x₂＝3，可以看出原问题的可行区域是由这两条直线及坐标轴围成的部分。虚线是令Z取常数时的目标直线，图中画了三条，分别是当Z=1,Z=9/4,Z=4时的直线，可以看到通过两条直线交点的目标函数直线既经过了可行域，又没有比它更高的直线了，因此Z=9/4就是最优值，而交点(3/4,3/4)是最优解。

线性规划xianxing guihualinear programming

研究将有限资源(人力、财力、物力、信息等)进行优化分配的方法之一。
线性规划因其数学模型的目标函数和约束条件都是线性函数而得名。它是运筹学的规划论中理论方面最完整、应用较广泛的一个分支。规划论中因数学模型形式和要求不同，除线性规划外，还有非线性规划、动态规划、整数规划、0～1规划、目标规划和随机规划等。
线性规划产生于20世纪30年代末。1939年，前苏联学者康托罗维奇(П·В·КОНТОРОЬЧГ)发表了名为《生产组织与计划中的数学方法》的专著，这一著作的问世标志着线性规划的建立。1949年丹西格(G·B·Dantzig)及其同事们提出了单纯形法，成为解线性规划最普遍有效的方法。以后又有一些学者提出了对偶理论，从而充实和完善了线性规划的理论基础。线性规划的基本思路是，在满足一组约束条件下，使预定的目标函数最优。它研究两个方面的问题，一是任务确定后，如何统筹规划、合理安排，尽量做到以最小的资源去完成任务（极小质问题）；二是在一定资源情况下，如何科学调配与合理使用，使得完成的任务最多（极大质问题）。求解线性规划问题的方法有图解法与单纯形法，由于图解法只适于求解2～3个变量的简单问题，因而一般都采用单纯形法。单纯形法是通过数学方法的迭代过程，从可行解中逐个进行迭代计算，最终求得最优解。
由于在国防经济计划工作中，许多计划模型具有线性或拟线性的特点，因而可以把不同的经济问题，诸如：确定最优生产规模，制定资源分配优化方案，确定最优生产力的配置，拟定最优运输方案等等，都可以归纳为使某些技术经济指标达到极优（最大或最小）的问题。同时，线性计划模型中的目标函数，不仅为评价计划提供了标准和尺度，而且还为计划规定了目标与任务。此外，计划模型还体现了经济效益的原则和反映不同部门及生产要素之间的比例关系。电子计算机一般都备有线性规划程序，应用求解十分方便。另外，线性规划对使用管理人员的数学知识要求也不高，熟练掌握较快。正因为如此，线性规划获得了非常广泛地应用，它已经广泛地用于计划管理、工农业生产、交通运输、区域规划和军事活动等方面。

线性规划

用线性方程或线性不等式规划，由若干约束条件组合并具有一定目标的系统，以求得最优解的数学方法。线性规划是最优化方法之一。用数学语言表达，就是在n个变量(x1,x2，……，xn)必须满足一些线性等式和（或）不等式的条件下，寻求x1，……，xn的一个线性关系的最优解。如在一定的人力、物力、财力、时间等条件下，寻求完成最大的任务量或最小的支出。这个方法是在1947年，美国学者丹西格提出“单纯形法”以后，作为运筹学的一个分支科目发展起来。线性规划的数学模型主要由两个部分组成：（一）约束条件。即对系统所考虑的控制因素加以限制的条件，或者说该系统达到目标时对各因素的限制条件。（二）目标函数。指系统的最优要求。目标为极大化，则目标函数值取极大值，如利润、产值、产量等；目标若极小化，目标函数值取极小值，如成本、工时、距离等。具体问题线性规划的数学模型是各式各样的，为了方便，人们建立了标准化的约束条件和目标函数的数学模型。线性规划的求解方法主要有图解法和单纯形法。图解法即用几何图形的分析方法求解，简便直观，但只适用于两个变量的线性规划问题。单纯形法的计算基础是线性代数。单纯形法是逐步求解的，先求可行解（也可能没有可行解），再逐步改善可行解，使目标函数达到极值（最大或最小值）就是最优解。单纯形法借助计算机可以求解成百上千个变量的线性规划。应用线性规划的系统必须具备下列条件：（一）目标函数可以用极值形式表达。（二）达到目标有不同方法可供选择。（三）目标是有限制条件的。（四）约束条件和目标函数能用线性方程表示。（五）模型中的生产活动有比例性和加法性。模型中的变量是非负值。线性规划应用广泛，从技术问题到工农商、运输、军事等计划管理的决策，从小范围的工作安排到宏观的国民经济计划。在大型的社会舆论调查和读者调查的方案设计以及优化中也是适用的。

线性规划Linear Programming

系在满足一组线性方程或线性不等式约束条件下，使线性目标函数极大或极小的一种最优规划方法。它是由苏联著名学者康托罗维奇1939年提出、1947年美国学者丹齐格 (G.B.Dantzig)从理论和方法上完善，随后得到广泛应用的一种经济数学方法。在农业生产领域中，线性规划主要用于生产计划的最优安排及资源的最优分配。通常根据问题的性质分为两类： (1)极大问题，在资源有限条件下，如何将其合理分配使用，才能使经济效益最大； (2)极小问题，在保证完成既定生产任务和目标要求前提下，如何使资源的消耗降至最低限度。

线性规划linar programming

线性规划是受线性不等式制约的最优化 （最大化和最小化） 目标函数的一种数学技术。线性规划的目的是为管理决策问题确定一最优化表。人们进行线性规划是为了从不同的活动过程中选择最能实现其理想目标的一个。例如，以最低可能成本制造某种产品或某组产品。
把数学规划方法区分为线性的和非线性的是很方便的。就线性规划而言，规划指的是把某个组织的各种活动加以计划或安排。解决复杂的线性规划问题由于电子计算机的发展和广泛应用而变得方便了。线性规划广泛被用来解决日常的决策问题。在商业上，线性规划被用于各种问题，从选择生产有一定营养价值的最便宜的饲料成分到决定最有利的工厂位置。
线性规划方法有悠久的历史渊源。法国重农学派经济学家魁奈的“经济表” (1758) 可以看作是线性规划的一个最初的例证，该经济表把土地所有者、手工业者和农民的作用相互联系起来了。1823年，法国数学家弗里尔(Jean Bastiste Joseph Fourier) 似乎见到了线性规划所含的某些命题。直到本世纪30年代晚期，俄国数学家L·V·康托罗维奇认识到，某些规划问题有着数学结构。
在第二次世界大战期间，线性规划大量发展起来，而且，科学计划技术的应用已变得非常重要。
但在1947年以前，并没有进行过具有重要意义的线性规划的工作。就在1947年有一批经济学家和数学家在美国空军的赞助下开始进行线性规划的工作，他们把W·里昂捷夫在1936年提出的投入产出模型的结构应用于空军。后来，美国经济的第一个线性规划模型同最大化目标函数的目标经济增长结合起来了。

线性规划linear programming

非负变量在线性约束下求线性目标函数最大（或最小）的问题。在经济和生产管理中，许多问题可以近似地表示为线性规划问题(参见“影子价格”)。一个例子是，设某一经济可以分为两个部门，该两部门在一年中的经济活动可用以下投入产出表描述（见表）。

部门	1	2	最终需求		总产出
			国 内	出 口
1	0	0.3	100+c1	w1	x1
2	0.2	0	200+c2	w2	x2
进口	0.3	0.1	可供应劳动量300 可供应资本存量600
劳动	0.3	0.4
资本 存量	0.8	0.7

表中第一直列表示，生产第一部门1亿元产品，需要投入0.2亿元的第二部门的产品、0.3亿元的进口产品和0.3亿元的劳动，还要求有0.8亿元的资本存量，第二直列的意义类似。最终需求分为国内消费和出口，其中的100和200分别为第一、二部门产品在国内的起码消费水平。因为每一部门的总产出应等于投入量，故有

0.3x₂+100+c₁+w₁＝x₁

(1)

0.2x₁+200+c₂+w₂＝x₂

(2)

如果要求进口总额大于出口总额，则有

0.3x₁+0.1x₂>w₁+w₂

(3)

再设劳动的最大供应量不超过300亿元，资本存量的最高限额为600亿元，则有

0.3x₁+0.4x₂≦300

(4)

0.8x₁+0.7x₂≦600

(5)

假设政府的目标是在(1)至(5)的约束下，选择非负的x₁,x₂,w₁,w₂和c₁,c₂，使得国内消费（高于起码水平）之和c₁+c₂达到最大。
令y₁＝x₁,y₂＝x₂,y₃＝c₁,y₄＝c₂,y₅＝w₁,y₆＝w₂,p=(0,0,1,1,0,0),b=(-100,-200,0,300,600)

则问题可写成一个标准的线性规划：

maxp·y
s.t.Ay≤b

y≧0

现在已经有许多求解线性规划的方法，最典型的是单纯形法。

线性规划

运筹学中的一个重要分支。它将一项活动的目标，影响因素及其相互制约等内在联系描述成以线性方程和不等式为表达形式的数学模型，并依此求解管理方案的一种数学方法。线性规划在1939年苏联数学家康托罗维奇的 《生产组织与计划中的数学方法》一书中产生萌芽，在1947年丹捷格提出的单纯形法中获得成熟。线性规划研究两大类问题： 一是当一项任务确定后，如何做到用最少的人力物力资源去完成； 二是如何使用一定数量的人力物力资源去获取最佳的使用效果。在经济管理活动中，这些成果主要被用于解决： (1) 运输问题。寻求在总运费最小的条件下，将某宗物资由若干产地调往若干销地的最佳调运方案。(2) 下料问题。在满足各种规格的毛坯需要量或配套数的条件下，制定使用原材料最省的下料方案。(3) 配料问题。在符合产品质量要求和原料供应量的条件下，制定出使成本最低或质量最高的配方。(4) 生产计划安排问题。在资源一定的条件下，编制使企业获利最大或设备利用率最高的产品品种搭配计划。(5) 分配问题。在条件一定时，确定使完工时间最短或成本最低的任务分配方法。(6) 厂址选择问题。在一定区域内，选择能使产品运费和建厂费用最省的厂址。(7) 设备平面布置问题。在满足生产性质和其他要求的前提下，规划能使所有零件在车间内搬运路线最短的设备布置。(8) 投资方案的选择。在投资额有限的条件 下，确定能使企业获利最多的投资项目或投资方式。用线性规划解决某类经济管理问题时，首先要求这类管理问题是可以数量化的，其次要将它转变成数学模型。它的数学模型包括： 一组用决策变量表示的可行方案以及规定可行方案与有限资源之间关系的约束条件；一个描述预期目标与可行方案关系的目标函数。线性规划问题的数学模型的一般形式是：求 一组变量Xj (j=1,2，…n) 的值，使其满足约束条件

并使目标函数的值最小 （或最大） 。式中： xj代表某方案中的第j个分量，aij代表技术系数 （如单耗）,bi代表有限资源量，cj代表价值系数(如单价单位成本)。 a_ij、b_i、 c_j代表已知量。
运用线性规划解决实际经济管理问题的基本步骤是：设计决策变量； 确定约束条件； 制定目标函数； 求解。求解线性规划问题的基本方法是单纯形法 (见“单纯形法”)。有些较特殊的线性规划问题 （如运输问题） 可用表上作业法或图上作业法求解。不论那种方法，都可借助于计算机求解。只有在决策变量和约束条件较少的条件下，手工计算才是可行的。

线性规划

linear programming