第4章数学规划模型-姜启源

1、第 4 章数学规划模型在上一章中我们看到，建立优化模型要确定优化的目标和寻求的决策。用x 表示决策变量， f ( x) 表示 目标函数 。实际问题一般对决策变量x 的取值范围有限制， 不妨记作x ， 称为可行域 。优化问题的数学模型可表示为Min (或Max) f ( x), x在第 3 章 x 通常是 1 维或 2 维变量， 通常是 1 维或 2 维的非负域。实际中的优化问题通常有多个决策变量，用n 维向量x( x1 , x2 , xn )T 表示，目标函数f ( x) 是多元函数，可行域 比较复杂，常用一组不等式（也可以有等式）gi (x) 0( i=1,2,m )来界定，称为 约束条件

2、。一般地，这类模型可表述成如下形式Min zf ( x)xs.t. gi (x) 0,i1,2, m这里的 s. t. (subject to)是“受约束于”的意思。显然，上述模型属于多元函数的条件极值问题的范围，然而许多实际问题归结出的这种形式的优化模型，其决策变量个数n 和约束条件个数m 一般较大， 并且最优解往往在可行域的边界上取得，这样就不能简单地用微分法求解，数学规划是解决这类问题的有效方法。需要指出的是，本章无意涉及数学规划（或运筹学）的具体计算方法，仍然着重于从数学建模的角度，介绍如何建立若干实际优化问题的模型，并且在用现成的数学软件求解后，对结果作一些分析。4 1 奶制品的生产

3、和销售企业内部的生产计划有各种不同的情况。从空间层次来看，在工厂级要根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品的生产计划，在车间级则要根据产品生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。从时间层次看，若在短时间内认为外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则就要制订多阶段生产计划。本节选择几个单阶段生产计划的实例，说明如何建立这类问题的数学规划模型，并利用软件求解的输出对结果作一些分析。例 1加工奶制品的生产计划问题一奶制品加工厂用牛奶生产A1, A2 两种奶制品， 1 桶牛奶可以在设备甲上用12 小时加工成3 公斤A1

4、 ，或者在设备乙上用8 小时加工成4 公斤A2 。根据市场需求，生产的A1 ，A2 全部能售出。且每公斤A1 获利24 元，每公斤A2 获利16 元。现在加工厂每天得到50 桶牛奶的供应，每天正式工人总的劳动时间为480 小时，并且设备甲每天至多能加工100 公斤A1 ，设备乙的加工能力没有限制。试为该场制订一个生产计划，使每天获利最大，并进一步讨论以下1) 若用 35 元可以买到3 个附加问题：1 桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？2) 若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？3) 由于市场需求的变化，每公斤 A1 的获利增加到 30 元，

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

6、15; 4 x2 ，故 z 72x164x2 。约束条件：原料供应生产 A1， A2的原料（牛奶）总量不得超过每天的供应，即x1 x2 50桶；劳动时间生产 A1， A2的总加工时间不得超过每天正式工人总的劳动时间，即12x18x2 480 小时；设备能力A1 的产量不得超过设备甲每天的加工能力，即3x1 100；非负约束x1, x2 均不能为负值，即x1 0, x2 0综上可得Maxz72x164x2(1)s. t.x1x2 50(2)12x18x2 480(3)3x1 100(4)x1 0,x2 0(5)这就是该问题的基本模型。由于目标函数和约束条件对于决策变量而言都是线性的，所以称为 线

7、性规划 （ Linear Programming, 简记作 LP ）。模型分析与假设从本章下面的实例可以看到，许多实际的优化问题的数学模型都是线性规划（特别是在像生产计划这样的经济管理领域），这不是偶然的。让我们分析一下线性规划具有哪些特征，或者说：实际问题具有什么性质，其模型才是线性规划。·比例性每个决策变量对目标函数的“贡献”，与该决策变量的取值成正比；每个决策变量对每个约束条件右端项的“贡献”，与该决策变量的取值成正比。·可加性各个决策变量对目标函数的“贡献”，与其它决策变量的取值无关；各个决策变量对每个约束条件右端项的“贡献”，与其它变量的取值无关。·连续

8、性每个决策变量的取值是连续的。比例性和可加性保证了目标函数和约束条件对于决策变量的线性性，连续性则允许得到决策变量的实数最优解。对于本例，能建立上面的线性规划模型，实际上是事先作了如下的假设：1) A1 ， A2 两种奶制品每公斤的获利是与它们各自产量无关的常数，每桶牛奶加工A 1， A 2 的数量和所需的时间是与它们各自的产量无关的常数；2)A1 ， A2 每公斤的获利是与它们相互间产量无关的常数，每桶牛奶加工出A1 ， A2的数量和所需的时间是与它们相互间产量无关的常数；3) 加工 A1 ， A2 的牛奶的桶数可以是任意实数。这 3 条假设恰好保证了上面的 3 条性质。 当然，在现实生活中

9、这些假设只是近似成立的，比如，A1 ， A2 的产量很大时，自然会使它们每公斤的获利有所减少。由于这些假设对于书中给出的、经过简化的实际问题是如此明显地成立，本章下面的例题就不再一一列出类似的假设了。不过，读者在打算用线性规划模型解决现实生活中实际问题时，应该考虑上面 3 条性质是否近似的满足。模型求解图解法 这个线性规划模型的决策变量为线性规划的基本性质。2 维，用图解法既简单，又便于直观地把握将约束条件（2） （ 5）中的不等号改为等号，可知它们是Ox1 x2 平面上的5 条直线，依次记为 L1L 5，如图 1。其中 L 4，L 5 分别是 x2 轴和 x2 轴，并且不难判断， （ 2）（

10、 5）式界定的可行域是 5 条直线上的线段所围成的5 边形 OABCD 。容易算出，5 个顶点的坐标为：O (0,0) ， A (0,50) ， B (20,30)， C (100/3,10) ， D (100/3,0) 。目标函数（ 1）中的 z 取不同数值时，在图族。如 z0 是过 O 点的直线， z2400 是过可以看出，当这族平行线向右上方移动到过点1 中表示一组平行直线（虚线），称等值线D 点的直线， z3040 是过点 C 的直线，。B 时， z3360 ，达到最大值，所以B 点的坐标(20,30)即为最优解：x120, x230 .x2AL 1BL4L2L3COL 5Dx1z=0

11、z=2 400z=3 360图 1模型的图解法我们直观地看到，由于目标函数和约束条件都是线性函数，在2 维情形，可行域为直线段围成的凸多边形，目标函数的等值线都为直线，于是最优解一定在凸多边行的某个顶点取得。推广到 n 维情形，可以猜想，最优解会在约束条件所界定的一个凸多面体（可行域）的某个顶点取得，线性规划的理论告诉我们，这个猜想是正确的。软件实现求解线性规划有不少现成的数学软件，比如用LINDO软件就可以很方便地实现。在LINDO6.1 版本下打开一个新文件，像书写模型（1） （5）一样，直接输入：max 72x1+64x2st2)x1+x2<503)12x1+8x2<4804

12、)3x1<100end注： LINDO 中已规定所有决策变量均为非负，故（5）式不必输入；乘号省略，式中不能有括号，右端不能有数学符号；模型中符号，用，=形式输入，它们与， 等效；输入文件中第1 行为目标函数，2）， 3）， 4）是为了标示各约束条件，便于从输出结果中查找相应信息；程序最后以“end”结束。将文件存储并命名后，选择菜单“Solve”并对提示“DO RANGE （ SENSITIVITY ）ANAL YSIS?”（灵敏性分析）回答“是”LP OPTIMUM FOUND AT STEP，即可得到如下输出：2OBJECTIVE FUNCTION VALUE1) 3360.000

13、VARIABLEVALUEREDUCED COSTX120.0000000.000000X230.0000000.000000ROWSLACK OR SURPLUSDUAL PRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO. ITERATIONS=2RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008

14、.000000X264.0000008.00000016.000000RIGHTHAND SIDE RANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000上面结果的第 3，5，6行明确的告诉我们， 这个线性规划的最优解为x120,x230 ,最优值为 z 3360 ，即用20 桶牛奶生产 A1 ， 30 桶牛奶生产 A2 ，可获最大利润3360 元。注：若对提示： DO RAN

15、GE （ SENSITIVITY）ANAL YSIS? 回答“否”，得到的是上面结果的前 11 行。结果分析上面的输出中除了告诉我们问题的最优解和最优值以外，还有许多对分析结果有用的信息，下面结合题目中提出的3 个附加问题，并利用图解法的直观给予说明。（ 1）3 个约束条件的右端不妨看作3 种“资源”：原料、劳动时间、设备甲的加工能力。输出第 710 行“ SLACK OR SURPPLUS”给出这 3 种资源在最优解下是否有剩余：2）原料， 3）劳动时间的剩余均为零，4）设备甲尚余 40 公斤加工能力。这与图解法的如下结果一致：最优解在 B 点（图 1 中约束条件2，3 所定义的直线 L1

16、和 L2 的交点）取得，表明原料、劳动时间已用完，而设备甲的能力有余。一般称“资源”剩余为零的约束为紧约束（有效约束） 。（ 2）目标函数可以看作“效益”，成为紧约束的“资源”一旦增加， “效益”必然跟着增加。输出第 710 行“ DUAL PRICES ”给出3 种资源在最优解下“资源”增加1 个单位时“效益”的增量： 2）原料增加1 个单位（ 1 桶牛奶）时利润增长48 元， 3）劳动时间增加 1 个单位（ 1 小时）时利润增长2 元，而增加非紧约束4）设备甲的能力显然不会使利润增长。这里， “效益”的增量可以看作“资源”的潜在价值，经济学上称为影子价格 ，即 1 桶牛奶的影子价格为48

17、元， 1 小时劳动的影子价格为2 元，设备甲的影子价格为零。读者可以用直接求解的办法验证上面的结论，即将输入文件中原料约束2）右端的 50改为 51，看看得到的最优值（利润）是否恰好增长48 元。用影子价格的概念很容易回答附加问题1）：用 35 元可以买到 1 桶牛奶，低于 1 桶牛奶的影子价格，当然应该作这项投资。回答附加问题2）：聘用临时工人以增加劳动时间，付给的工资低于劳动时间的影子价格才可以增加利润，所以工资最多是每小时2 元。（ 3）目标函数的系数发生变化时（假定约束条件不变），最优解和最优值会改变吗？这个问题不能简单的回答。从图1 看，目标函数的系数决定了等值线族的斜率，原题中该斜

18、率（取绝对值，下同）为72/64=9/8 ，介于直线L1 的斜率 1 与 L2 斜率 4/3 之间，最优解自然在 L1 和 L2 的交点 B 取得。并且，只要目标函数系数的变化使得等值线族的斜率仍然在（ 1， 4/3）范围内，这个最优解就不会改变。而当目标函数系数的变化使得等值线族的斜率小于 1 时，最优解将在 A 点取得，大于 4/3 时，最优解将在 C 点取得。上面输出的第1317 行“ CURRENT COEF ”的“ ALLOEABLE INCREASE”和“ALLOWABLE DECREASE ”给出了最优解不变条件下目标函数系数的允许变化范围：x1 的系数为（ 72 8，72+24

19、），即（ 64，96）； x2 的系数为（6416，64+8 ），即（ 48，72）。注意： x1系数的允许范围需要 x2 系数 64 不变，反之亦然。用这个结果很容易回答附加问题3）：若每公斤A1 的获利增加到30 元，则 x1 系数变为30× 3=90，在允许范围内，所以不应改变计划。（ 4）对“资源”的影子价格作进一步的分析。从图1 看，随着原料（牛奶）的增加，直线L1 向右上方平移，L1 与 L2 的交点B （它仍是最优解）向A 点靠近，在这个过程中，每增加 1 桶牛奶利润增加48 元（影子价格） 。但是， 当 B 点与 A 点重合后再增加牛奶就不可能使利润增长了。这就是说，

20、影子价格的作用（即在最优解下“资源”增加1 个单位时“效益” 的增量）是有限制的。 上面输出的第1823 行“ CURRENT RHS ”的“ ALLOWABLEINCREASE ”和“ ALLOWABLEDECREASE ”给出了影子价格有意义条件下约束右端的限制范围： 2）原料最多增加10 桶牛奶， 3）劳动时间最多增加53 个小时。现在可以回答附加问题1）的第 2 问：虽然应该批准用35 元买一桶牛奶的投资，但每天最多购买10 桶牛奶。顺便指出，可以用低于每小时2 元的工资聘用临时工人以增加劳动时间，但最多增加53 小时。评注 本例在产品利润、加工时间等参数均可设为常数的情况下，建立了线

21、性规划模型。线性规划模型的三要素是：决策变量、目标函数和约束条件。线性规划模型可以方便地用 LINDO 软件求解，得到内容丰富的输出，利用其中的影子价格和灵敏性分析，可对模型结果作进一步的研究，它们对实际问题常常是十分有益的。例 2奶制品的生产销售计划问题例 1 给出的 A1 ， A2 两种奶制品的生产条件、利润，及工厂的“资源”限制全部不变。为增加工厂的获利，开发了奶制品的深加工技术：用2 小时和 3 元加工费，可将1 公斤 A1 加工成 0.8 公斤高级奶制品 B1 ，也可将 1 公斤 A2 加工成 0.75 公斤高级奶制品B2 ，每公斤 B1 能获利 44 元，每公斤 B2 能获利 32

22、 元。试为该厂制订一个生产销售计划，使每天的净利润最大，并讨论以下问题：1)投资 30 元可以增加供应 1 桶牛奶，投资 3 元可以增加 1 小时劳动时间，应否作这些投资？若每天资 150 元，可赚回多少？2) 每公斤高级奶制品 B1 ， B2 的获利经常有 10%的波动，对制订的生产销售计划有无影响？若每公斤B1 的获利下降10%，计划应该变化吗？问题分析要求制订生产销售计划，决策变量可以像例1 那样，取作每天用多少桶牛奶生产A1 ， A2 ，再添上用多少公斤A1 加工B1 ，用多少公斤A2 加工B2 ，但是问题要分析 B1 ， B2 的获利对生产销售计划的影响，所以决策变量取作A1， A2

23、，B1，B2每天的销售量更方便。目标函数是工厂每天的净利润A1,A2, B1 , B2 的获利之和扣除深加工费用。约束条件基本不变，只是要添上A1 , A2 深加工时间的约束。在例1 类似的假定下用线性规划模型解决这个问题。基本模型决策变量 ：设每天销售 x1公斤 A1 ， x2公斤 A2 ， x3 公斤 B1 ， x4 公斤 B2 ，用 x5 公斤A1 加工 B1 ， x6公斤 A2 加工 B2（增设 x5 ， x6 可使下面的模型简单） 。目标函数:设每天净利润为z，容易写出z24x116x244x332x43x53x6 。约束条件 ：原料供应A1 每天生产 x1x5 公斤，用牛奶 (x1

24、x5 ) / 3 桶， A2 每天生产 x2 x6 公斤，用牛奶 (x2x6 ) / 4 桶，二者之和不得超过每天的供应量50 桶；劳动时间每天生产 A1 ， A2 的时间分别为 4( x1x5 ) 和 2(x2x6 ) ，加工 B1 ， B2 B 2的时间分别为 2x5 和 2x6 ，二者之和不得超过总的劳动时间480 小时；设备能力A1 的产量 x1 x5 不得超过设备甲每天的加工能力100 公斤；非负约束x1 , x2 , , x6 均为非负。附加约束1 公斤 A1 加工成0.8 公斤 B1 ，故 x30.8x5 ，类似地 x4 0.75x6 。由此得基本模型：Max z24x1 16x

25、244x332x43x53x6(6)s .t .x1x5x2x6 50(7)344( x1x5 )2( x2x6 )2x52x6 480(8)x1x5 100(9)x30.8x5(10)x40.75x6(11)x1 , x2 , x3 , x4 , x5 , x6 0(12)这仍然是一个线性规划模型。模型求解用 LINDO 软件求解，输入文件时应将（7）式改写为4x13x24x53x6 600（ 7）（ 8）式改写为4x12x26x54x6 480（8）可得如下输出：LP OPTIMUM FOUND A T STEP2OBJECTIVE FUNCTION VALUE1) 3460.800VAR

26、IABLEVALUEREDUCED COSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACK OR SURPLUSDUAL PRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO. ITERA TIONS=2RANGES IN WHICH THE BASIS

27、IS UNCHANGED:OBJ COEFFICIENT RANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX124.0000001.680000INFINITYX216.0000008.1500002.100000X344.00000019.7500023.166667X432.0000002.026667INFINITYX5-3.00000015.8000002.533334X6-3.0000001.520000INFINITYRIGHTHAND SIDE RANGESROWCURRENTALLOWABLEALLOWABL

28、ERHSINCREASEDECREASE2600.000000120.000000280.0000003480.000000253.33332880.0000004100.000000INFINITY76.00000050.000000INFINITY19.20000160.000000INFINITY0.000000最优解为x10, x2168, x319.2, x40, x524, x60, 最优解为z3460.8 。即每天生产销售168 公斤A2 和19.2 公斤B1 （不出售A1 ， B2 ），可获净利润3460.8元。为此，需用8 桶牛奶加工成A1 ，42桶加工成A2 ，并将得到的2

29、4 公斤A1 全部加工成B1 。和例 1 一样，原料（牛奶） 、劳动时间为紧约束。结果分析利用输出中的影子价格和灵敏性分析讨论以下问题：（ 1）上述结果给出：约束2）， 3）的影子价格分别为3.16 和 3.26，注意到约束2）的影子价格为（13）右端增加1 单位目标函数的增量，由（7）式可知，增加1 桶牛奶可使净利润增长 3.16 ×12=37.92 元，约束 3）的影子价格则说明： 增加 1 小时劳动时间可使净利润增长 3.26 元。所以应该投资 30 元增加供应 1 桶牛奶， 或投资 3 元增加 1 小时劳动时间。若每天投资 150 元，增加供应 5 桶牛奶，可赚回 37.92

30、× 5=189.6 元。但是通过投资增加牛奶的数量是有限制的，输出结果表明，约束2）右端的允许变化范围为（600 280， 600 120），相当于（ 7）式右端的变化范围为（ 50 23.3， 50+10），即最多增加供应 10 桶牛奶。（ 2）上述结果给出了最优解不变条件下目标函数系数的允许变化范围：x3 的系数为（ 44 3.17，44+19.75）； x4 的系数为 （ 32， 32+2.03）。所以当 B1 的获利向下波动10%，或 B2 的获利向上波动10%时，上面得到的生产销售计划不再是最优的，应该重新制订。如若每公斤B1 的获利下降10%，应将原模型（6）式中x3 的

31、系数改为39.6，重新计算，得到的最优解为x10, x2160, x30, x430, x50, x640, 最优值为z3400，即50 桶牛奶全部加工成200 公斤A2 ，出售其中160 公斤，将其余40 公斤加工成30 公斤B2出售，获净利润3400元，可见计划变化很大，这就是说，（最优）生产计划对B1 或B2 获利的波动是很敏感的。你有办法改变这种状况吗？评注与例1 相比，例2 多了两种产品B1 ， B2 ，它们的销售量与A1 ， A2 的加工量之间存在等式关系（ 10），（ 11），虽然可以据此消掉 2 个变量，但是会增加人工计算，并使模型变得复杂。我们建模的原则是尽可能利用原始的数据

32、信息，而把尽量多的计算留给计算机去做。4.2自来水输送与货机装运钢铁、煤炭、水电等生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或者利润最大？各种类型的货物装箱，由于受体积、重量等的限制，如何相互搭配装载，使获利最高，或者装箱数量最少？本节通过两个例子讨论用数学规划模型解决这类问题的方法。例 1自来水输送问题问题某市有甲，乙，丙，丁四个居民区，自来水由A ， B ， C 三个水库供应。四个区每天必须得到保证的基本生活用水量分别为30，70， 10，10 千吨，但由于水源紧张，三个水库每天最多只能分别供应50， 60， 50 千吨自来水。由于地理位置的差别，自来水公司从

33、各水库向各区送水所需付出的引水管理费不同（见表1，其中 C 水库与丁区之间没有输水管道），其他管理费用都是450 元 /千吨。根据公司规定， 各区用户按照统一标准900元 /千吨收费。此外，四个区都向公司申请了额外用水量，分别为每天50， 70，20， 40 千吨。该公司应如何分配供水量，才能获利最多？为了增加供水量，自来水公司正在考虑进行水库改造，使三个水库的每天的最大供水量都提高一倍，问那时供水方案应如何改变？公司利润可增加到多少？引水管理费（元/千吨）甲乙丙丁A160130220170BC190200230/表 1从水库向各区送水的引水管理费问题分析分配供水量就是安排从三个水库向四个区送

34、水的方案，目标是获利最多。而从题目给出的数据看，A ， B ， C 三个水库的供水量160 千吨，不超过四个区的基本生活用水量与额外用水量之和 300 千吨。因而总能全部卖出并获利，于是自来水公司每天的总收入是 900×（ 50+60+50 ） =144000 元，与送水方案无关。同样，公司每天的其他管理费用是 450×（ 50+60+50 ）=72000 元也与送水方案无关。所以，要使利润最大，只需使引水管理费最小即可。另外，送水方案自然要受三个水库的供应量和四个区的需求量的限制。模型建立很明显，决策变量为A， B ，C 三个水库（i=1， 2，3）分别向甲、乙、丙、丁四

35、个区（j=1， 2， 3， 4）的供水量。设水库i向j区的供水量为xij。由于C 水库与丁区之间没有输水管道，即x34 =0，因此只有11 个决策变量。由上分析，问题的目标可以从获利最多转化为引水管理费最少，于是有MinZ160x11130x12220x13170 x14140 x21130x22190x23150 x24190 x31200x32230x33（ 1）约束条件有两类：一类是水库的供应量限制，另一类是各区的需求量限制。由于供水量总能卖出并获利，水库的供应量限制可以表示为x11x12x13x1450（ 2）x21x22x23x2460（3）x31x32x3350（ 4）考虑到各区的

36、基本生活用水量与额外用水量，需求量限制可以表示为30 x11x21x31 80（ 5）70 x12x22x32 140（ 6）10 x13x23x33 30（ 7）10 x14x24 50（8）模型求解（ 1）（ 8）构成一个线性规划模型（当然要加上xij 的非负约束） 。输入 LINDO 求解，得到如下输出：OBJECTIVE FUNCTION VALUE1) 24400.00VARIABLEVALUEREDUCED COSTX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.000000X210

37、.00000010.000000X2250.0000000.000000X230.00000020.000000X2410.0000000.000000X3140.0000000.000000X320.00000010.000000X3310.0000000.000000送水方案为：A 水库向乙区供水50 千吨， B 水库向乙、丁区分别供水50， 10 千吨，C 水库向甲、丙分别供水40， 10 千吨。引水管理费为 24400 元，利润为 144000 72000 24400=47600 元。讨论如果 A ， B ， C 三个水库每天的最大供水量都提高一倍，则公司总供水能力为 320 千吨，大

38、于总需求量300 千吨，水库供水量不能全部卖出，因而不能像前面那样，将获利最多转化为引水管理费最少。此时我们首先需要计算甲、乙、丙、丁四个区供应每千吨水的净利润， 即从收入，三个水库分别向900 元中减去其他管理费450 元，再减去表1 中的引水管理费，得表2。净利润（元 /千吨）甲乙丙丁A290320230280B310320260300C260250220/表 2从水库向各区送水的净利润于是决策目标为MinZ290x11320 x12230x13280 x14310 x21320x22260x23300x24260 x31250 x32220x33（ 9）由于水库供水量不能全部卖出，所以上

39、面约束（2） （ 4）的右端增加一倍的同时，应将等号改成小于、等于号，即x11x12x13x14 100（ 10）x21x22x23x24 120（ 11）x31x32x33 100（12）约束（ 5） （8）不变。将（5）（ 12）构成线性规划模型输入LINDO 求解得到：OBJECTIVE FUNCTION VALUE1) 88700.00VARIABLEVALUEREDUCED COSTX110.00000020.000000X12100.0000000.000000X130.00000040.000000X140.00000020.000000X2130.0000000.000000X

40、2240.0000000.000000X230.00000010.000000X2450.0000000.000000X3150.0000000.000000X320.00000020.000000X3330.0000000.000000送水方案为：A 水库向乙区供水100 千吨，B 水库向甲、乙、丁区分别供水30， 40，50 千吨， C 水库向甲、丙区分别供水50， 30 千吨。总利润为88700 元。其实，由于每个区的供水量都能完全满足，所以上面（5） （8）每个式子左边的约束可以去掉， 右边小于、 等于号可以改写成等号。作这样的简化后得到的解没有任何变化。评注本题考虑的是将某种物质从若干供应点运往一些需求点，在供需量约束条件下使总费用最小，或总利润最大。这类问题一般称为运输问题 ，是线性规划应用最广泛的领域之一。在标准的运输问题中，供需量通常是平衡的，即供应点的总供应量等于需求点的总需求量。本题中供需量量不平衡，但这并不会引起本质的区别，一样可以方便地建立线性规划模型求解。例 2货机装运问题某架货机有三个货舱：前仓、中仓、后仓。三个货舱所能装载的货物的最大重量和体积都有限制，如表3 所示。并且，为了保持飞机的平衡，三个货舱中实际装载货物的