3.1 线性规划数学模型

线性规划是运筹学的重要分支，是20世纪三四十年代初兴起的一门学科。1947年，美国数学家G.B.Dantzig及其同事提出的求解线性规划的单纯形法及其有关理论具有划时代的意义。他们的工作为线性规划这一学科的建立奠定了理论基础。随着1979年苏联数学家哈奇扬的椭球算法和1984年美籍印度数学家H.Karmarkar算法的相继问世，线性规划的理论更加完备、成熟，实用领域更加宽广。线性规划研究的实际问题多种多样，如生产计划问题、物资运输问题、合理下料问题、库存问题、劳动力问题、最优设计问题等，这些问题虽然出自不同的行业，有着不同的实际背景，但都是属于如何计划、安排、调度的问题，即如何物尽其用、人尽其才的问题。

就模型而言，线性规划数学模型类似于高等数学中的条件极值问题，只是其目标函数和约束条件都限定为线性函数。线性规划数学模型的求解方法目前仍以单纯形法为主要方法。

人们处理的最优化问题，小至简单思索即行决策，大至构成一个大型的科学计算问题都具有三个基本要素，即决策变量、目标函数和约束条件。

● 决策变量：是决策者可以控制的因素，例如根据不同的实际问题，决策变量可以选为产品的产量、物资的运量及工作的天数等。

● 目标函数：是以函数形式来表示决策者追求的目标。例如目标可以是利润最大或成本最小等。对于线性规划，目标函数要求是线性的。

● 约束条件：是决策变量需要满足的限定条件。对于线性规划，约束条件是一组线性等式或不等式。

例3.1 加工奶制品的生产计划

一奶制品加工厂用牛奶生产A1, A2两种奶制品，1桶牛奶可以在设备甲上用12小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产A1, A2全部能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤A1，设备乙的加工能力没有限制。试为该厂制订一个生产计划，使每天获利最大。

进一步讨论以下3个附加问题：

● 若用35元可以买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？

● 若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多每小时几元？

● 由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？

问题分析

这个优化问题的目标是使每天的获利最大，要做的决策是生产计划，即每天用多少桶牛奶生产A1，用多少桶牛奶生产A2（也可以是每天生产多少公斤A1，多少公斤A2），决策受到3个条件的限制：原料（牛奶）供应、劳动时间、设备甲的加工能力。按照题目所给，将决策变量、目标函数和约束条件用数学符号及式子表示出来，就可以得到下面的模型。

模型设计

设每天用x1桶牛奶生产A1，用x2桶牛奶生产A2。设每天获利为z元。x1桶牛奶可生产3x1公斤A1，获利24×3x1, x2桶牛奶可生产4x2公斤A2，获利16×4x2，故z=72x1+64x2。

生产A1, A2的原料（牛奶）总量不得超过每天的供应，即x1+x2≤50；生产A1, A2的总加工时间不得超过每天正式工人总的劳动时间，即12x1+8x2≤480; A1的产量不得超过设备甲每天的加工能力，即3x1≤100; x1, x2均不能为负值，即x1≥0, x2≥0。

从本章下面的实例可以看到，许多实际的优化问题的数学模型都是线性规划（特别是在像生产计划这样的经济管理领域），这不是偶然的。让我们分析一下线性规划具有哪些特征，或者说：实际问题具有什么性质，其模型才是线性规划。

● 比例性：每个决策变量对目标函数的“贡献”，与该决策变量的取值成正比；每个决策变量对每个约束条件右端项的“贡献”，与该决策变量的取值成正比。

● 可加性：各个决策变量对目标函数的“贡献”，与其他决策的取值无关；各个决策变量对每个约束条件右端项的“贡献”，与其他决策变量的取值无关。

● 连续性：每个决策变量的取值是连续的。

比例性和可加性保证了目标函数和约束条件对于决策变量的线性性，连续性则允许得到决策变量的实数最优解。

对于本例，能建立上面的线性规划模型，实际上是事先做了如下的假设：

1．A1, A2两种奶制品每公斤的获利是与它们各自产量无关的常数，每桶牛奶加工出A1, A2的数量和所需的时间是与它们各自产量无关的常数。

2．A1, A2每公斤的获利是与它们相互间产量无关的常数，每桶牛奶加工出A1, A2的数量和所需的时间是与它们相互间产量无关的常数。

3．加工A1, A2的牛奶桶数可以是任意实数。

这3条假设恰好保证了上面的3条性质。当然，在现实生活中这些假设只是近似成立。比如A1, A2的产量很大时，自然会使每公斤的获利有所减少。

当问题非常复杂时，建立数学规划模型已经不是问题的难点，求解模型才是问题的难点。本章将介绍两类专业的数学软件LINDO/LINGO，它们是专门用来解决各种优化问题的数学软件。

美国芝加哥大学的Linus Schrage教授于1980年前后开发了一套专门用于求解最优化问题的软件包，后来又经过了多年的不断完善和扩充，并成立了LINDO系统公司进行商业化运作，取得了巨大成功。这套软件包的主要产品有4种：LINDO, LINGO, LINDO API和What's Best! 。在最优化软件的市场上占有很大的份额，尤其在供微机使用的最优化软件的市场上，上述软件产品具有绝对的优势。在LINDO公司主页上提供的信息，位列全球《财富》杂志500强的企业中，一半以上企业使用上述产品，其中位列全球《财富》杂志25强的企业中有23家使用上述产品。大家可以从该公司的主页上下载上面四种软件的演示版和大量应用例子。演示版与正式版的基本功能是类似的，只是演示版能够求解问题的规模受到严格限制。即使对于正式版，通常也被分成求解包、高级版、超级版、工业版、扩展版等不同档次的版本，不同档次的版本的区别也在于能够求解的问题的规模大小不同。当然，规模越大的版本的销售价格也越昂贵。

LINDO是英文Linear Interactive and Discrete Optimizer字母的缩写形式，即“交互式的线性和离散优化求解器”，可以用来求解线性规划和二次规划；LINGO是英文Linear Interactive and General Optimizer字母的缩写形式，即“交互式的线性和通用优化求解器”，它除了具有LINDO的全部功能外，还可以用于求解非线性规划，也可以用于一些线性和非线性方程组的求解等。LINDO和LINGO软件的最大特色在于可以允许决策变量是整数，而且执行速度很快。LINGO实际上还是最优化问题的一种建模语言，包括许多常用的数学函数供使用者建立优化模型时调用，并可以接受其他数据文件。即使对优化方面的专业知识了解不多的用户，也能够方便地建模和输入、有效地求解和分析实际中遇到的大规模优化问题，并通常能够快速得到复杂优化问题的高质量解。LINDO和LINGO软件能求解的优化模型参见图3-1。

此外，LINDO系统公司还提供了LINDO/LINGO软件与其他开发工具（如C++和Java等语言）的接口软件LINDO API（LINDO Application Program Interface），使LINDO和LINGO软件还能方便地融入用户应用软件的开发中去。最后，What's Best！软件实际上提供了LINDO/LINGO软件与电子表格软件的接口，能够直接集成到电子表格软件中使用。由于上述特点，LINDO、LINGO、LINDO API和What's Best！软件在教学、科研和工业、商业、服务等领域得到了广泛应用。本节只介绍在Microsoft Windows环境下运行的LINDO/LINGO最新版本的使用方法，并包括社会、经济、工程等方面的大量实际应用问题的数学建模和实例求解。需要指出的是，目前LINDO公司已经将LINDO软件从其产品目录中删除，这意味着以后不会再有LINDO软件的新版本了。

程序设计

    max 72x1+64x2
    s.t.x1+x2＜=50 12x1+8x2＜=480 3x1＜=100

运行结果

    LP OPTIMUMFOUND AT STEP      2
          OBJECTIVE FUNCTION VALUE
          1）     3360.000
    VARIABLE          VALUE            REDUCED COST
          X1        20.000000          0.000000
          X2        30.000000          0.000000
          ROW  SLACK OR SURPLUS DUAL PRICES
          2）       0.000000       48.000000
          3）       0.000000           2.000000
          4）       40.000000         0.000000
    NO.ITERATIONS=      2
    RANGES IN WHICH THE BASIS IS UNCHANGED：

                            OBJ COEFFICIENT RANGES
    VARIABLE  CURRENT    ALLOWABLE      ALLOWABLE
                    COEF           INCREASE        DECREASE
        X1       72.000000         24.000000        8.000000
        X2       64.000000         8.000000         16.000000
                            RIGHTHAND SIDE RANGES
    ROW CURRENT   ALLOWABLE        ALLOWABLE
                      RHS          INCREASE        DECREASE
          2       50.000000        10.000000        6.666667
          3      480.000000        53.333332        80.000000
          4      100.000000        INFINITY        40.000000

上面的输出中除了告诉我们问题的最优解和最优值以外，还有许多对分析结果有用的信息。

1．3个约束条件的右端不妨看作3种“资源”：原料、劳动时间、设备甲的加工能力。输出中“SLACK OR SURPLUS”给出这3种资源在最优解下是否有剩余：原料、劳动时间的剩余均为零，设备甲尚余40公斤加工能力。一般称“资源”剩余为零的约束为紧约束（有效约束）。

2．目标函数可以看作“效益”成为紧约束的“资源”一旦增加，“效益”必然跟着增长。输出中“DUAL PRICES”给出这3种资源在最优解下“资源”增加1个单位时“效益”的增量：原料增加1个单位（1桶牛奶）时，利润增长48元；劳动时间增加1个单位（1小时）时，利润增长2元；而增加非紧约束（设备甲的能力）显然不会使利润增长。这里，“效益”的增量可以看作“资源”的潜在价值，经济学上称为影子价格。即1桶牛奶的影子价格为48元，1小时劳动的影子价格为2元，设备甲的影子价格为零。各位可以用直接求解的办法验证上面的结论，即将输入文件中原料约束右端的50改为51，看看得到的最优值（利润）是否恰好增长48元。

3．目标函数的系数发生变化时（假定约束条件不变），最优解和最优值会改变吗？输出中“CORRENT COEF”的“ALLOWABLE INCREASE”和“ALLOWABLE DECREASE”给出了最优解不变条件下目标函数系数的允许范围：x1的系数为（72-8,72+24），即（64, 96）; x2的系数为（64-16,64+8），即（48,72）。注意：x1系数的允许范围需要x2系数64不变，反之亦然。

对“资源”的影子价格做进一步的分析。影子价格的作用是有限制的。输出中“CURRENT RHS”的“ALLOWABLE INCREASE”和“ALLOWABLE DECREASE”给出了影子价格有意义条件下约束右端的限制范围：原料最多增加10桶，劳动时间最多增加53小时。

LINDO程序有以下特点：

● 程序以“MAX”（或“MIN”）开始，表示目标最大化（或最小化）问题，后面直接写出目标函数表达式和约束表达式；

● 目标函数和约束之间用“ST”分开；（或用“s.t.”，“subj ect to”）

● 程序以“END”结束（“END”也可以省略）。

● 系数与变量之间的乘号必须省略。

● 书写相当灵活，不必对齐，不区分字符的大小写。

● 默认所有的变量都是非负的，所以不必输入非负约束。

● 约束条件中的“＜=”及“＞=”可分别用“＜”及“＞”代替。

● 一行中感叹号“! ”后面的文字是注释语句，可增强程序的可读性，不参与模型的建立。

LINDO模型的一些注意事项：

1．变量名由字母和数字组成，但必须以字母开头，且长度不能超过8个字符，不区分大小写字母，包括关键字（如MAX、MIN等）也不区分大小写字母。

2．变量不能出现在一个约束条件的右端（即约束条件的右端只能是常数）；变量与其系数间可以有空格（甚至回车），但不能有任何运算符号（包括乘号“*”等）。

3．模型中不接受括号“（）”和逗号“, ”等符号（除非在注释语句中）。例如：“4（X1+X2）”需写为“4X1+4X2”;“10,000”需写为“10000”。

4．表达式应当已经化简。如不能出现“2X1+3X2-4X1”，而应写成“-2X1+3X2”等。

5．LINDO中已假定所有变量非负。若要取消变量的非负假定，可在模型的“END”语句后面用命令“FREE”。例如，在“END”语句后输入“FREE vname”，可将变量vname的非负假定取消。

6．数值均衡化考虑：如果约束系数矩阵中各非零元的绝对值的数量级差别很大（相差1000倍以上），则称其为数值不均衡。为了避免数值不均衡引起的计算问题，使用者应尽可能自己对矩阵的行列进行均衡化。此时还有一个原则，即系数中非零元的绝对值不能大于100000或者小于0.0001。

例3.2 “菜篮子工程”中的蔬菜种植问题

为缓解我国副食品供不应求的矛盾，农业部于1988年提出建设“菜篮子工程”。蔬菜作为“菜篮子工程”中的主要产品，备受各级政府的重视。到1995年，蔬菜种植的人均占有量已达到世界人均水平。

对于一些中小城市，蔬菜种植采取以郊区和农区种植为主，结合政府补贴的方式来保障城区蔬菜的供应。这样不仅提高了城区蔬菜供应的数量和质量，还带动了郊区和农区菜农种植蔬菜的积极性。

某市的人口近90万，该市在郊区和农区建立了8个蔬菜种植基地，承担全市居民的蔬菜供应任务，每天将蔬菜运送到市区的35个蔬菜销售点。市区有15个主要交通路口，在蔬菜运送的过程中，从蔬菜种植基地可以途经这些交通路口再到达蔬菜销售点。如果蔬菜销售点的需求量不能满足，则市政府要给予一定的短缺补偿。同时市政府还按照蔬菜种植基地供应蔬菜的数量以及路程，发放相应的运费补贴，以此提高蔬菜种植的积极性，运费补贴标准为0.04元/吨·公里。

蔬菜种植基地日蔬菜供应量、蔬菜销售点日蔬菜需求量及日短缺补偿标准、道路交通情况及距离见表3-2至表3-4。

针对下面两个问题，分别建立数学模型，并制订蔬菜运送方案。

（1）为该市设计从蔬菜种植基地至各蔬菜销售点的蔬菜运送方案，使政府的短缺补偿和运费补贴最少；

（2）若规定各蔬菜销售点的短缺量一律不超过需求量的30%，重新设计蔬菜运送方案。

问题分析

第一问，设计从蔬菜种植基地至各蔬菜销售点的蔬菜运送方案，使政府的短缺补偿和运费补贴最少。首先要设计出蔬菜种植基地至各蔬菜销售点的最短距离。在最短距离的基础上，使政府的短缺补偿和运费补贴最少。因此，建立线性规划模型，在上述最短距离的条件下，求目标函数即短缺补偿和运费补贴的最小值。

第二问，在规定了各蔬菜销售点的短缺量一律不超过需求量的30%的条件下，重新设计蔬菜运送方案。将第一问的线性规划模型进行改进，增加上述约束条件，最后求解上述模型。

模型设计

已知有i个生产基地Ai，有j个销售点Bj。首先，计算8个生产基地与35个销售点之间的最短路径D=（dij）8×35, dij表示从生产基地Ai 到销售点Bj的最短路径长度。最短路径算法将在第四章中详细介绍，应用该算法可以得到各生产基地到各销售点的最短路径（见表3-5）。

为该市设计从蔬菜种植基地至各蔬菜销售点的蔬菜运送方案，使政府的短缺补偿和运费补贴最少。生产基地Ai蔬菜供应量分别为ai，销售点Bj蔬菜需求量分别为cj, xij表示从Ai到Bj的运量。每个种植基地的蔬菜运送量为运送到各个销售点运量的总和。有如下约束条件：

政府的短缺补偿和运费补贴最少的目标函数为：

其中，S为总的补偿费用，T为总的运费补贴，Hj为销售点Bj的短缺补偿。总的补偿费用为总的运费补贴与总短缺补偿之和。总的运费补偿函数T为：

其中，η为运费补贴系数。销售点Bj的短缺补偿函数Hj为：

其中，bj为销售点Bj的短缺补偿系数，每个销售点短缺补偿额为该销售点短缺补偿系数与短缺量的乘积。短缺量为该销售点的需求量与8个生产基地运到该销售点的蔬菜量之差。

综上所述，第一问的线性规划模型如下：

使用LINDO求得上述模型可以得到最少补贴为48611元，从结果可以发现：大部分销售点的蔬菜都是只由一个生产基地提供的，另外也只有6个销售点的蔬菜由两个生产基地提供。

为了体现蔬菜生产基地减产1吨及销售点需求增加1吨对政府补偿的影响，利用LINDO的影子价格结果分别画出相应的结果图如图3-2和图3-3所示。

从上图可以看到：蔬菜生产基地减产1吨政府补偿额会增加530元左右，各蔬菜销售点需求增加1吨，政府补偿额会增加120元左右。

如果规定各蔬菜销售点的短缺量一律不超过需求量的30%，加入约束条件：

所以，改进后的运送模型为：

使用LINDO求得上述模型可以得到最少补偿为58054元，从结果可以发现，大部分销售点的蔬菜都是只由一个生产基地提供的，另外由于此时的约束条件更为严格，所以算出的最小补贴为58054元高于第一问的结果，这也是意料中的。

为了体现蔬菜生产基地减产1吨及销售点需求增加1吨对政府补偿的影响，利用LINDO的影子价格结果画出相应的结果图如下：

从上图可以看到：蔬菜生产基地减产1吨政府补偿额会增加700左右，各个蔬菜销售点需求增加1吨，政府补偿额会增加150左右，同样增加额高于第一问的结果。

通过以上两例可以看出：尽管所提问题的内容不同，但从构成数学问题的结构来看却属于同一优化问题，其结构具有如下特征：

（1）目标函数是决策变量的线性函数；

（2）约束条件都是决策变量的线性等式或不等式。

具有以上结构特点的模型就是线性规划模型，简记为LP，它具有一般形式为：