建立线性规划模型

子任务2.1　建立线性规划模型

2.1.1　任务引入

【任务2-1】　某工厂在计划期内安排生产甲、乙两种产品，已知生产单位产品所需的设备台时及A，B两种原材料的消耗情况如表2-1所示，同时已知该厂每生产一件甲产品可获利2元，每生产一件乙产品可获利3元，问应如何安排生产计划，才能使该厂获利最多？

表2-1

【任务2-2】　有A，B，C3个工地，每天A工地需要水泥1700袋，B工地需要水泥1 800袋，C工地需要水泥1500袋。为此，甲、乙两个水泥厂每天生产2300袋水泥和2700袋水泥专门供应3个工地，两个水泥厂至工地的单位运价（千元）如表2-2所示。任务：如何组织调运使总运费最省？

表2-2　两个水泥厂至工地的单位运价

【任务2-3】　某公司从事某种商品的经营，现欲制订本年度10—12月的进货及销售计划。已知该种商品的初始库存量为2000件，而公司仓库最多可存放该种商品10000件，公司拥有的经营资金为80万元。据预测，10—12月的进货及销售价格如表2-3所示。若每个月仅在1号进货1次，且要求在年底时商品的库存达到3000件，根据以上条件，应该如何安排进货及销售计划，使公司获得最大利润。（注：不考虑库存费用）

表2-3　10—12月的进货及销售价格

2.1.2　任务分析

线性规划研究的问题主要有两类：一是给出一定量的人力、物力、财力等资源，如何统筹规划这些有限资源以最大限度地完成任务；二是给定一项任务，如何统筹规划、合理安排，用最少的资源来完成它。这两类问题中都有一个限制条件，即第一类问题是给出一定量的人力、物力和财力等资源，第二类问题是给定一项任务，这种限制条件我们可以用一组线性方程组或线性不等式组来描述。此外，这两类问题中都有在限制条件下所要达到的结果（即目标）：第一类问题的目标是最大限度地完成任务；第二类问题的目标是使用最少的资源。我们可以用一个线性函数来描述这个目标，这些线性函数及线性方程组或线性不等式组即构成了线性规划问题的最基本形态。

任务2-1是线性规划中的典型生产计划问题。

由题意，我们先设x₁和x₂为产品Ⅰ、Ⅱ的生产数量，当然x₁，x₂≥0；

那么，其获利z为两种产品的产量与各自利润的乘积之和，即2x₁+3x₂；

要达到获利最大的目标，可以用函数式表示为：max z=2x₁+3x₂。

在确定产品产量的过程中要考虑的条件有：

设备台时限制：x₁+2x₂≤8

原材料A限制：4x₁≤16　

原材料B限制：4x₂≤12　

这样我们就可以将一个生产计划安排的优化问题用上述4个数学式表示出来。

任务2-2是线性规划中的运输规划问题。

由题意，先设x_ij（i=1，2；j=1，2，3；x_ij≥0）为甲、乙两个生产厂每天分别运到A，B，C三地的产品数量。同样就可以将一个运输的优化问题用一组数学式表示出来。

总运费为两厂至三地的6项运价分别与相应的运量乘积之和。即　x₁₁+1.5x₁₂+2x₁₃+2x₂₁+4x₂₂+2x₂₃

那么要使总运费最低，可以用函数式表示为：minz=x₁₁+1.5x₁₂+2x₁₃+2x₂₁+4x₂₂+2x₂₃；

在产品运输过程中要考虑的条件有：

①甲厂每天生产及供应限制：x₁₁+x₁₂+x₁₃=23

②乙厂每天生产及供应限制：x₂₁+x₂₂+x₂₃=27

③A地每天需要产品限制：x₁₁+x₂₁=17

④B地每天需要产品限制：x₁₂+x₂₂=18

⑤C地每天需要产品限制：x₁₃+x₂₃=15

任务2-3是线性规划中仓储优化问题。

设3个月进货量分别为x₁，x₂，x₃，售货量分别为y₁，y₂，y₃，x_i，y_i≥0，i=1，2，3。该公司的利润应该是每个月销售收入与进货成本的差额之和，当然还应考虑公司本身拥有的经营资金。故公司获得的最大利润可用下式表示：

max z=800000+100y₁-90x₁+100y₂-95x₂+115y₃-98x₃

再考虑各种限制条件。因仓库初始时有一定的库存量，且最多存放商品的数量是固定的，同时，年底要求的库存数量一定，故每个月的进销差额量受到一定的限制，分别为：

x₁-y₁+2000≤10000　　　　　　　　

x₂-y₂+（x₁-y₁+2000）≤10000　　　

x₃-y₃+［x₂-y₂+（x₁-y₁+2000）］=3000

整理后得：max z=800000+100y₁-90x₁+100y₂-95x₂+115y₃-98x₃

x₁-y₁≤8000

x₂-y₂+x₁-y₁≤8000

x₃-y₃+x₂-y₂+x₁-y₁=1000

这4个数学表达式就是使公司获取最大利润的优化进货与销售计划的具体方法。

除了上述三类问题外，线性规划还广泛应用于现代物流管理中的生产配料与下料、设备优化运行、人员合理安排、资源最优利用、最佳投资决策等问题。

上述各例都是求极值的问题，而且是求条件极值的问题。但它们与多元函数微积分中求条件极值的问题不同，后者的限制条件必须是等式的，而且自变量的个数要比限制条件的个数多，这时才能用拉格朗日法求解，而前者却不具备这两个条件。因此用微积分的方法无法求解。这些问题，都是数学规划的研究内容。

以上任务虽然实际意义不同，但它们本质上都属于一类优化问题，其共同特征如下：

①每一个问题都用一组决策变量（x₁，x₂，…，x_n）表示某一方案，具体取定决策变量的一组值就代表一个具体方案。

②存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。

③都有一个要求达到的目标，它可用决策变量的线性函数（也称目标函数）来表示，按具体问题的不同，要求目标函数实现最大化或最小化。

④决策变量（x₁，x₂，…，x_n）的值一般是非负的。

满足以上条件的问题我们称为线性规划问题，其数学模型称为线性规划的数学模型。

2.1.3　知识构建

1）线性规划的发展

线性规划是运筹学的一个基本分支，其应用极其广泛，其作用已为越来越多的人所重视。随着计算机的普及，它快速渗透到工农业生产、商业、军事行动和科学研究的各个方面，为社会节省的财富、创造的价值无法估量。它主要研究在既定的目标和条件下，如何最大限度地发挥有限资源的作用，从而完成最多、最大的任务。简单来讲，也就是资源的最优利用问题，随着其在理论上的不断成熟与完善，在实际中的应用日益广泛与深入，特别是随着计算机技术的发展，处理大规模线性规划问题变得轻松而简捷，使得它所适用的领域更加广泛，从解决技术中的最优化设计到工业、农业、交通运输业、商业等部门的经济规划和管理决策等，都发挥着重要的作用。目前它已成为现代管理科学的重要基础和手段之一。

线性规划思想最早可以追溯到过去人们在经济生活中采用的预算法，这种方法和线性规划基本相同，只不过当时人们没有进行理论和形式上的推敲，对解决复杂问题有些困难罢了。1874年利昂・沃尔拉在其《经济学原理》一书中主张把生产过程中的数量作为生产手段价格和各种商品价格函数的联立方程，虽然这个联立方程只不过是理论形式，实际上是不可能解的，但它表明人们已开始对线性规划的原理进行探索了。在1929年利昂节夫创立的投入、产出分析法，通过控制点把投入、产出作为一次（线性）关系，这个思想对日后线性规划模型的提出产生了直接的影响。到1939年，苏联科学家康托洛维奇总结了他对生产组织的研究，写出了《生产组织与计划中的数学方法》一书，提出了类似线性规划的模型，并给出了“解乘数法”的求解方法，这是线性规划应用于工业生产问题的经典著作，但在当时却未受到重视。1944年，冯・诺依曼和摩根斯坦在《博弈论和经济行为》中指出了对策论与线性规划对偶理论的紧密联系，并在现实中为线性规划理论研究者提供了大力支持。直到1947年，丹捷格发表了有关线性规划的研究成果，才正式提出了线性规划的概念以及求解线性规划的单纯形方法，此后，对线性规划的研究逐渐受到了普遍关注。1960年，康托洛维奇再次发表了《最佳资源利用的经济计算》一书，得到了国内外的一致重视，为此他获得了诺贝尔奖。1979年，苏联科学家哈奇安首次提出求解线性规划问题的一个多项式算法——椭球算法。1984年，卡马卡提出了解线性规划问题的一个新的内点算法，它是一种更为有效的多项式算法，这些算法为线性规划更好地应用于实际提供了完善的理论基础。此外，阿罗、萨谬尔森、西蒙、多夫曼和胡尔威茨等一批科学家也因在线性规划研究中的杰出贡献而获得了诺贝尔奖，通过这些科学家们的努力，如今线性规划已形成了一套完整的理论，并被广泛地运用到生产和科学研究中。

在各类经济活动中，经常会遇到这样的问题：在生产条件不变的情况下，如何通过统筹安排，合理利用现有资源，将其进行最佳分配，改进生产组织或计划，合理安排人力、物力资源，组织生产过程，使总的经济效益最好，这样的问题常常可以化成或近似化成“线性规划”（Linear Programming，LP）问题。线性规划模型就是一种优化资源配置，使企业尽可能取得最佳经济效益的重要数学方法。

2）线性规划研究的主要问题

线性规划研究的主要问题有两类：一是给出一定量的人力、物力、财力等资源，如何统筹规划这些有限资源以最大限度地完成任务；二是给定一项任务，如何统筹规划、合理安排，用最少的资源来完成它。这两类问题中都有一个限制条件：第一类问题是给出一定量的人力、物力和财力等资源；第二类问题是给定一项任务，这种限制条件我们可以用一组线性方程组或线性不等式组来描述。此外，这两类问题中都有在限制条件下所要达到的结果（即目标）：第一类问题的目标是最大限度地完成任务；第二类问题的目标是使用最少的资源。我们可以用一个线性函数来描述这个目标，这些线性函数及线性方程组或线性不等式组即构成了线性规划问题的最基本形态。

2.1.4　任务实施

线性规划模型的目标是企业利润的最大化，在不考虑产品销售情况的理想状态下，将资源尽可能地配置到利润率更高的产品上去，并尽可能减少资源的浪费是实现线性规划模型总目标的关键所在。

步骤一　设置决策变量

决策变量是模型中的可控而未知的因素，经常使用带不同下标的英文字母表示不同的变量，如式2-1中的x_j。

步骤二　建立目标函数

线性规划模型的目标是求系统目标的极值，可以是求极大值，如企业的利润和效率等；也可以是求极小值，如成本和费用等。式2-1即为最优化目标函数，简称目标函数，式中opt即optimize（最优化）的缩写，根据问题要求的不同，可以表示为max（最大化）或min（最小化）。

步骤三　建立约束条件

约束条件是指实现系统目标的限制性因素，通常表现为生产力约束、原材料约束、能源约束、库存约束等资源性约束，也有可能表现为指标约束和需求约束，如2.2.3节介绍的式2-2中的前m个式子。

步骤四　设立非负限制

由于在实际生产问题中，资源总是代表一些可以计量的实物或人力，因而一般不能是负数，如2.2.3节介绍的式2-2中的最后一个式子。

一般线性规划模型可以表示如下：

由式2-1和式2-2两式组成的线性规划模型还可以用下列的矩阵式表示，即

其中，为系数矩阵；C=［c₁，c₂，…，c_n］；X=［x₁，x₂，…，x_n］^T；B=［b₁，b₂，…，b_m］^T；O=［0，0，…，0］^T表示0矩阵。