运筹学实验指导书

Excel自带的宏模块“规划求解”可用于求解线性规划、非线性规划、整数规划的最优解。

规划求解宏模块在Excel普通运行状况下一般不会启动，当需要调用时，可以从工具菜单条中加载宏来启动，其基本步骤如下。

（1） 在工具菜单中选择“加载宏”选型。

（2） 在加载宏对话框中选择“规划求解”选型。

图0-1加载“规划求解”宏

（3） 如果成功加载，则在工具菜单条中会出现“规划求解”选型。 由此，可以运用规划求解宏模块求解任何一个线性规划问题、整数规划问题、非线性规划问题，分别举例说明如下。

例1 营养配餐问题 根据生物营养学理论，一个成年人每天要维持人体正常的生理健康需求，需要从食物中获取3000卡路里热量、55g蛋白质和800mg钙。假定市场上可供选择的食品有猪肉、鸡蛋、大米和白菜，这些食品每千克所含热量和营养成分以及市场价格如表1-1所示。如何选购才能在满足营养的前提下，使购买食品的总费用最小？

表0-1 营养配餐问题数据表

序号 1 2 3 4 食品名称 猪肉 鸡蛋 大米 白菜 热量/卡路里 1200 800 900 200 蛋白质/g 50 60 20 10 钙/mg 400 200 300 500 价格/元/kg 20 8 4 2

1

解，建立该问题的线性规划模型如下：

假设xj（j=1,2,3,4）分别为猪肉、鸡蛋、大米和白菜每天的购买量，则其线性规划模型为：

minz20x18x24x32x41200x1800x2900x3200x4300050x60x20x10x55 1234s.t.400x1200x2300x3500x4800xj0(j1,2,3,4)第一步：需要在Excel中建立该问题的电子表格模型，如图0-2所示。

图0-2 营养配餐问题的Excel表模型

其中单元格B10：E10设置为决策变量单元格，F12设置为目标单元格，F4：F6设置为三个约束条件的左边项，即表示实际获得的营养。目标单元格和约束条件左边项的函数如图0-3所示

图0-3营养配餐问题中的公式设置

函数sumproduct(区域1，区域2)为Excel的常用函数，表示将区域1中对应元素与区域2中对应元素相乘后再相加。

第二步：调用Excel中的“规划求解”宏，并设置目标单元格、可变单元格（即决策变量）、约束条件地址参数，如图0-4所示。

2

图0-4 规划求解参数设置

“规划求解参数”对话框的作用就是让计算机知道模型的各个组成部分放在电子表格中的什么地方，可以通过键入单元格（或单元区域）的地址或用鼠标在电子表格相应的单元格（或单元区域）单击或拖动的方法将有关信息加入对话框相应的位置。具体步骤如下。

（1） 设置目标单元格

在“规划求解参数”对话框中指定目标函数所在单元格的引用位置，此目标单元格经求解后获得某一特定数值、最大值、最小值。

（2） 设置可变单元格

可变单元格指定决策变量所在的各单元格，不含公式，可以有多个单元格或区域，当单元格或区域不连成一片时，各区域之间用逗号隔开。求解是，可变单元格中的数据不断地调整，直到满足约束条件，并使“设置目标单元格”编辑框中指定的单元格达到目标值。可变单元格必须直接或间接与目标单元格相联系。

（3） 添加约束

在“规划求解参数”对话框中单击“添加”按钮就会显示“添加约束”对话框。

图0-5 规划求解添加约束

在添加约束对话框中有3个选项需填写，其中：

1）单元格引用位置，指定需要约束其中数据的单元格或单元格区域，一般在此处添加约束函数不等式左侧的函数表达式的单元格或单元格区域。

2）运算符，对于不同类型的约束条件，可以选定相应的关系运算符来表示约束关系。其中int表示决策变量为整数，bin表示决策变量为二进制变量。 3）约束值，表示约束条件右边的值，在此编辑框中输入数值、右边值单元格引用或区域引用。

4）添加，单击此按钮可以在不返回“规划求解参数”对话框的情况下继续添加其他约束条件。当已经把所有约束条件都一一添加了，只需单击“确定”按

3

钮，返回“规划求解参数”对话框，“约束”栏中已经显示了刚添加的约束。 第三步，单击选项按钮，弹出“规划求解选项”对话框，图0-6所示。

图0-6“规划求解选项”对话框

规划求解选项对话框中的选项可以对求解运算的一些高级属性进行设定，这些高级属性选项如下。

（1） 最长运算时间

在此设定求解过程的时间，可输入的最大值为32767，默认值为100，可以满足大多数小型规划求解的需要，此选择项一般在求解非线性规划时才设置。

（2） 迭代次数

在此设定求解过程中迭代运算的次数，求解过程所花费的时间。可输入的最大值为32767，默认值为100，可以满足大多数小型规划求解的需要，此选择项一般在求解非线性规划时才设置。

（3） 精度

在此输入用于控制求解精度的数字，以确定约束条件单元格中的数值是否满足目标值的上下限。精度一般运用于非线性规划问题，并且必须由一个0-1之间的小数表示。设置的数值越少，精度越低。

（4） 收敛度

在此输入收敛度数值，当最近五次迭代时，目标单元格中数值的变化小于“收敛度”编辑框中设置的数值时，“规划求解”停止运算。收敛度只运用于非线性规划问题，并且必须由一个0-1之间的小数表示。设置的数值越小，收敛度就越高。

（5） 采用线性模型

当模型中所有的关系都是线性的并希望解决线性优化问题时，选中复选框可加速求解进程。

（6） 显示迭代结果

如果选中此复选框，每进行一次迭代后都将中断“规划求解”过程，并显示当前的迭代结果。

（7） 假定非负

对于在“添加约束”对话框的“约束值”编辑框中没有设置下限的可变单元

4

格，假定其下限为0。规划问题一般要求决策变量非负，所以一般都需要选择此选择项。

在本例中，只要选中“采用线性模型”，“假定非负”即可。单击“确定”按钮回到规划求解参数对话框。

第四步：单击规划求解参数对话框中的“求解”按钮，弹出“规划求解结果”

对话框。

图0-7“规划求解结果”对话框

当规划求解得到答案时，“规划求解结果”对话框中会给出下面两条求解结果信息。

（1）“规划求解”找到一个解，可满足所有的约束及最优化要求。这表明按“规划求解选项”对话框中设置的精度，所有的约束条件都已经满足，并且目标单元格达到极大值或极小值，表示已经求出了问题的最优解。

（2）“规划求解”收敛于当前结果，并满足所有的约束条件。这表明目标单元格中的数值在最近5次求解过程中的变化量小于“规划求解选项”对话框中“收敛度”设置的值。“收敛度”中设置的值越小，“规划求解”在计算时就会越精细，但求解过程将花费更多的时间。

当规划求解不能得到最佳结果时，在“规划求解结果”对话框中就会显示下述信息：

（1） 满足所有约束条件，“规划求解”不能进一步优化结果。这表明仅

得到近似值，迭代过程无法得到比显示结果更精确的数值，或是无法进一步提高精度，或是精度值设置得太小，请在“规划求解选型”对话框中试着设置较大的精度值，再运行一次。

（2） 求解达到最长运算时间后停止。这表明在达到最长运算时间

时，没有得到满意的结果，如果保存当前结果并节省下次计算的时间，单击“保存规划求解”或“保存方案”选项即可。

（3） 求解达到最大迭代次数后停止。这表明在达到最大迭代次数时，

仍没有得到满意的结果，增加迭代次数也许有用，但是应该先检查结果确定问题的原因。如果要保存当前结果并节省下次计算的时间，单击“保存规划求解” “保存方案”选项即可。

（4） 目标单元格中数值不收敛。这表明即使满足全部约束条件，目标

单元格数值也只是有增有减但不收敛。这可能是在设置问题时忽略了一项或多项约束条件。请检查工作表中的当前值，确定目标发散的原因，并检查约束条件，然后再次求解。

（5） 规划求解未找到合适的结果。这表明在满足全部约束条件和精度

要求的条件下，“规划求解”无法得到合理的结果，这可能是约束条件不一致所致。请检查约束条件公式或类型选择是否有误。

（6） 规划求解在目标或约束条件单元格中发现错误值。这表明在最近

5

一次运算中，一个或多个公式的元算结果有误。请找到包含错误值的目标单元格或约束条件单元格，修改其中的公式或内容，以得到合理的运算结果。还有可能是在“添加约束”的对话框中键入了无效的名称或公式，或在“约束”编辑框中直接键入了integer或binary。如果要将变量约束为整数，请在“添加约束”对话框的“关系运算符”中选中int。如果要将变量约束为二进制，请选中bin。

本例中，显示“规划求解”找到一个最优解，选中“保存规划求解结果”单选框，单击“确定”按钮可得求解结果。

图0-8营养配餐问题的最优求解结果

从求解结果可知，每天购买3.33kg大米可满足最低营养需求，最少总费用为13.33元。

练习：习题1.13 某饲养场饲养动物出售，设每头动物每天至少需700g蛋白质、30g矿物质、100mg维生素。现有五种饲料可供选用，各种饲料每kg营养成分含量及单价如表所示。要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。（建立问题的线性规划模型，并求解） 饲料 蛋白质g 矿物质g 维生素mg 价格（元/kg） 1 3 1 0.5 0.2 2 2 0.5 1.0 0.7 3 1 0.2 0.2 0.4 4 6 2 2 0.3 5 18 0.5 0.8 0.8

6

实验1 应用Excel求解线性规划

1实验目的：

• 掌握Excel中规划求解宏模块的作用

• 掌握Excel中建立连续投资问题线性规划模型 • 掌握用Excel规划求解宏模块求解以上模型 2实验环境

启动Excel，并加载规划求解

3实验案例：连续投资问题案例分析、数学模型表达及其案例求解 （1）背景介绍：

某公司现有300万元准备在未来的3年内投资，根据考察和洽谈的意向确定了4个可以考虑的项目：

项目1：在3年内，投资人可在每年年初投资，年末可获利20%，每年取息后可将本息一起重新投资，获利率仍为20%。

项目2：在3年内，投资人可在第1年年初投资，两年末可获利50%，取息后，可将本息一起重新投资，但本项目投资最多不得超过200万元。

项目3：在3年内，投资人可在第2年年初投资，两年后可获利60%，本项目投资最多不得超过150万元。

项目4：在3年内，投资人可在第3年年初投资，一年内可获利30%，本项目投资最多不超过100万元。

请协助投资人设计能在第3年内获得最高收益的3年投资计划，建立其线性规划模型。

（2）案例分析及数学模型表达：

投资过程用表1-1描述，其中xij表示第i年对第j项目的投资额。

表1-1 连续投资情况 第1年 第2年 第3年 x11 1.2x11 x12 1.5x12 X21 1.2x21 X23 X31 X34

（1） 每年年初的投资额等于投资资金的。

x11x12300第4年

1.6x23 1.2x31 1.3x34

x21x231.2x11x31x341.5x121.2x21（2） 每年各项目投资额的

x12200x23150

x34100（3） 总目标为第3年末的投资总收益为最大，表示为：

maxz1.6x231.2x311.3x34

（3）案例求解及最优方案

7

将连续投资问题的相关信息输入Excel电子表格，并设置决策变量单元格区域、目标单元格区域和约束条件单元格区域，如图1-1所示。

图1-1连续投资问题的电子表格模型

连续投资模型中的公式设置如表1-2所示：

表1-2 连续投资模型中的公式设置 名称 投资合计 单元格 公式 B7 =sum(B3:B6) D7 =sum(D3:B6) F7 =sum(F3:F6) D9 =C11 投资金额 F9 =E11+E12 C11 =B11*B3 1年末 E11 =D11*D3 2年末 E12 =B12*B4 G11 =F11*F3 3年末 G13 =D13*D5 G14 =F14*F6 B16 =G11+G13+G14 总投资收益 调用规划求解宏模块，规划求解宏模块的参数设置如下： 8

图1-2规划求解宏模块的参数设置

单击“求解”按钮后，规划求解结果如图1-3所示。

图1-3 连续投资问题的最优方案

（4） 练习题1.18的Excel求解。

宏银公司承诺为某建设项目从2003年起的4年中每年初分别提供以下数额贷款：2003年——100万元，2004年——150万元，2005年——120万元，2006年——110万元。以上贷款资金均需于2002年底前筹集齐。但为了充分发挥资金的作用，在满足每年贷款额情况下，可将多余资金分别用于下列投资项目：

1）于2003年初购买A种债券，期限为3年，到期后本息合计为投资额的

140%，但限购60万元；

2）于2003年初购买B种债券，期限为2年，到期后本息合计为投资额的

125%，且限购90万元；

3）于2004年初购买C中债券，期限为2年，到期后本息合计为投资额的

130%，但限购50万元；

9

4）于每年初将任意数额的资金存放于银行，年息4%，于每年底取出。

求宏银公司应如何运用好这笔筹集到的资金，使2002年底需筹集到的资金数额为最少。

10

实验2 应用Excel求解运输问题和整数规划问题

1实验目的

• 掌握Excel中建立运输问题和整数规划问题模型

• 掌握用Excel规划求解宏模块求解运输问题和整数规划问题 2实验环境

启动Excel，并加载规划求解 3实验案例1产品运输问题 （1） 案例背景介绍

某种物资有3个产地A1，A2和A3，其供应量分别是9，4和7，有4个销地B1，B2，B3和B4，需求量分别是6，6，5和3。物资可根据下图所示的交通网络从产地运到销地，网络中各边权数表示两地间的单位运价，给出这个转运问题的运输模型并求出其最优调运方案。

A2 4 8 A1 7 14 B4 16 2 6 A3 7 2 5 3 T2 6 3 2 7 8 T5

图2-1 运输网络线路图

4 B3

T1 4 5 T4 7 T3 11 16 B2 B1

（2） 案例分析及数学模型表达

这可以看成一个带转运点的运输问题，其中产地为A1，A2和A3，销地为B1，B2，B3，B4，转运点为T1，T2，T3，T4和T5。且恰好总产量等于总销量，因此，将所有产量看成可能的转运量，将不能到达点之间的距离表示为一个比较大的数M，M可以看成无穷大，把该运输问题化为一个规范的运输问题。

A1 A2 A3 T1 表2-1产销平衡运输表 T2 T3 T4 T5 B1 B2 B3 B4 发送量 29 24 27 20 20 20 20 20 20 20 20 20 A1 A2 A3 T1 T2 T3 T4 T5 B1 B2 B3 B4

0 4 7 M M M M M M M M 8 4 0 M 7 5 M M M M M M 14 7 M 0 2 6 M M M M M M 16 M 7 2 0 M 4 5 6 M M M 2 M 5 6 M 0 M 3 2 M M M 3 M M M 4 M 0 M M 11 16 M M 11

M M M 5 3 3 0 M M 7 4 M M M M 6 2 M M 0 7 M 8 M M M M M M 11 M 7 0 M M M M M M M M 16 7 M M 0 M M M M M M M M 4 8 M M 0 M 8 14 16 2 3 M M M M M M 0 接收量 20 20 20 20 20 20 20 20 26 26 25 23 ---- （3） 案例求解及最优方案

在案例求解时，将比较大的正数M取为M=100。设置该问题的决策变量单元格区域、目标函数单元格区域和约束条件单元格区域，如图所示。

图2-2产品运输问题的电子表格模型

产品运输问题模型中的公式设置，比如，实际运量N17=sum（B17：M17）；B29=sum（B17：B28）；总运输费用：P30=sumproduct（B3：M14，B17：M28）。

调用规划求解宏模块，规划求解宏模块的参数设置如下：

图2-3产品运输问题模型中的公式设置

单击“求解”按钮后，规划求解结果如下图所示，最优产品运输方案如浅色

12

区域显示的数字。在网络图上标出，即为弧上黑体字显示的数据。

图2-4产品运输问题的最优方案表

A2 [6] 4 A1 7 T1 4 [7] 5 6 3 [4] 2 [6] T3 11 16 T4 7 4 7 8 T5

图2-5最优产品运输分配方案图

[5] B3

[6] B2

[6] B1

14 5 2 [10] B4 8 3 [3] [7] 16 2 7 6 A3 T2

实验案例2仓库位置选择问题 （1） 案例背景介绍

有一家大公司希望开设一些新的仓库，以向销售中心供货，每开设一个新仓库都有一些固定费用。货物将从仓库运输到附近的销售中心。每次运输的运费取决于运输的距离。这两种类型的费用非常不同：仓库开设费用属于投资支出，通常在若干年后将勾销，而运输费用属于运营成本。假设这两种费用可比，为此可能需要以年为单位计算运营费用。

有12个可以建造新仓库的位置，并且需要从这些仓库向12个销售中心供货。表给出了第i个仓库向第j个销售中心供货每吨的单位成本，如表2-2所示。

13

表2-2 满足客户需求所需的运输成本（千欧元）

此外，对每个仓库还有如下信息：仓库建设的固定费用（需要计入目标函数）和仓库的容量上限，这些信息列于表中。

仓库 建设费用 容量上限 1 2 表2-3 仓库建设费用（千欧元）和容量（吨） 3 4 5 6 7 8 9 10 11 12 3500 9000 10000 4000 3000 9000 9000 3000 4000 10000 9000 35000 300 250 100 180 275 300 200 220 270 250 230 180 表4-6列出了各个销售中心（客户）的需求量。 客户 1 需求120 量 2 80 3 75 表2-4 客户需求数据（吨） 4 5 6 7 8 9 100 110 100 90 60 30 10 150 11 95 12 120 任何时候都要保证满足客户需求，可以从多个仓库向同一个客户送货。应在哪些位置开办仓库才能使总的建设成本以及运输成本最低，同时依然能够满足所有客户需求？

（2） 案例分析及数学模型表达

此问题是要确定在12个仓库备选点中应该选择哪些点建设仓库，之后还要确定仓库和客户之间应该如何供货。 1）设yi1,在第i个点建设仓库0，否则，xij表示由第i个仓库向第j个客户供货，ai为第i个

仓库的建设费用，bi为第i个仓库的容量，dj为第j个客户的需求量，cij由第i个仓库 第j个客户供货的单位成本（千欧元/吨）

2）一个建设好的仓库可以向多个客户供货，但是不能超过其容量，表示为：

xj112ijbiyi,i1,2,,12

3）每一个客户的需求必须满足，表示为：

xi112ijdj,j1,2,,12

4）对于不能供货的地点，其运输费用可设为一个较大数，或在求解时直接令相

14

应的决策变量为0。

5）目标是总成本最小，总成本包括仓库建设成本和货物运输成本两部分。表示为：minzaiyicijxij

i1i1i1121212

（3） 案例求解及最优方案

将仓库的位置设置问题的相关信息输入Excel电子表格，并设置决策变量单元格区域、目标单元格区域和约束条件单元格区域。如图2-6所示。

图2-6 仓库位置设置的电子表格模型

仓库位置设置模型中的公式输入如表2-4所示：

名称 单元格 O33 O34 O35 O36 O37 供应O38 合计 O39 O40 O41 O42 O43 O44 容量Q33 乘yi Q34 Q35 Q36 Q37 Q38

公式 表2-4 仓库位置设置模型中的公式输入 名称 单元格 公式 C45 D45 E45 F45 G45 H45 I45 J45 K45 L45 M45 N45 Q40 Q41 Q42 Q43 Q44 Q45 =SUM(C33:C44) =SUM(D33:D44) =SUM(E33:E44) =SUM(F33:F44) =SUM(G33:G44) =SUM(H33:H44) =SUM(I33:I44) =SUM(J33:J44) =SUM(K33:K44) =SUM(L33:L44) =SUM(M33:M44) =SUM(N33:N44) =R40*B40 =R41*B41 =R42*B42 =R43*B43 =R44*B44 =R45*B45 =SUM(C33:N33) =SUM(C34:N34) =SUM(C35:N35) =SUM(C36:N36) =SUM(C37:N37) =SUM(C38:N38) =SUM(C39:N39) =SUM(C40:N40) =SUM(C41:N41) =SUM(C42:N42) =SUM(C43:N43) =SUM(C44:N44) =R33*B33 =R34*B34 =R35*B35 =R36*B36 =R37*B37 =R38*B38 需求合计 容量乘yi 15

目标总费用 Q39 B49 =R39*B39 =SUMPRODUCT(B33:B44,S33:S44)+SUMPRODUCT(B19:M30,C33:N44) 调用规划求解宏模块的参数设置如图2-7所示：

图2-7规划求解宏模块的参数设置

单击“求解”按钮后，规划求解结果如图2-8所示，最优仓库位置设置方案如浅色区域显示的数字，即在位置1、位置4、位置5、位置8、位置9设置仓库，各仓库供应客户货物情况如表所示，仓库设置和货物供应之和的最小费用为18713千欧元。

图2-8仓库位置设置的最优方案

16

4 练习题

（1）1、2、3三个城市每年需分别供应电力320个单位、250个单位和350个单位，由A、B两个电站提供，它们的最大可供电量分别为400个单位和450个单位，单位费用如表所示。由于需要量大于可供量，决定城市1的供应量可减少0-30个单位，城市2的供应量不变，城市3的供应量不能少于270个单位，求总费用最低的分配方案（将可供电量用完）。 1 A 15 B 21 （2）用分支定界法解下列整数规划 maxz2x1x2x1x25x1x206x12x221x1,x20,且为整数 2 3 18 22 25 16 17

实验3 应用Excel求解动态规划问题

1实验目的：

• 掌握Excel中建立动态规划模型

• 掌握用Excel规划求解宏模块求解动态规划模型 2实验环境

启动Excel，并加载规划求解

3实验案例：福特汽车公司最优生产安排计划 （1） 案例背景介绍

福特汽车公司是世界最大的汽车企业之一，每年在中国市场上销售量达到几十万辆。为了在来年有一个好的利润预期，在中国的福特制造商需要做一个良好的生产计划。下表给出了福特公司明年预期的销售量（以千辆为单位计）。此公司的生产能力为每一个45千辆。通过工人加班，可以将产量提高20%，但会将每辆车的生产成本从8万元提高到8.05万元。

1月 30 2月 25 3月 35 表3-1明年的销售预期（千辆） 4月 5月 6月 7月 8月 9月 38 39 42 58 45 52 10月 11月 12月 60 55 70 前一年福特汽车公司的库存量为5千辆，对于库存中的每辆车，在每个月月

底都需要支出0.01万元的存储费用。假定福特公司的库存能力是无限的。现在是1月1日，在下面的12个月里每个月生产和存储多少辆车才能满足此销售预期，并使总成本最小化？

（2） 案例分析及数学模型表达

该问题要确定福特汽车公司每个月的汽车生产量，而汽车生产分为正常生产和加班生产，因此，假设公司第i个月正常生产的汽车数量为xi，第i个月加班生产的汽车数量为yi，第i个月月底时库存的汽车数量为si，第i个月的需求量为di。

每个月生产能力的：xi45000,yi9000 每个月满足销售需求的： 第一个月：x1y15000d1s1 第i个月：xiyisi1disi

目标为总费用最小：minz8xi8.05yi0.01si

i1i1i1121212（3） 案例求解及最优方案

将生产计划的相关数据输入Excel电子表格，并设置决策变量单元格区域、目标函数单元格区域及相应的约束条件区域，如图所示。

18

图3-1福特汽车公司生产计划的电子表格模型

福特汽车生产计划的电子表格模型中的公式设置如表所示。

名称 可提供总量 单元格 I4 I5 I6 I7 I8 I9 I10 I11 I12 I13 I14 I15 合计 B16 =sum（B4：B15） E16 B24 总目标 费用最小 表3-2福特汽车生产计划的电子表格模型中的公式设置 公式 名称 单元格 公式 =B4+E4+D21 K4 =L4+H4 需求总量 =B5+E5+H4 K5 =L5+H5 =B6+E6+H5 K6 =L6+H6 =B7+E7+H6 K7 =L7+H7 =B8+E8+H7 K8 =L8+H8 =B9+E9+H8 K9 =L9+H9 =B10+E10+H9 K10 =L10+H10 =B11+E11+H10 K11 =L11+H11 =B12+E12+H11 K12 =L12+H12 =B13+E13+H12 K13 =L13+H13 =B14+E14+H13 K14 =L14+H14 =B15+E15+H14 K15 =L15+H15 =sum（E4：E15） H16 =sum（H4：H15） =D18*B16+D19*E16+D20*H16 调用规划求解宏模块，规划求解宏模块的参数设置如图所示。

19

图3-2 福特汽车公司生产计划的规划求解参数设置

图3-3福特汽车公司生产计划的规划求解选项设置

20

图3-4福特汽车公司生产计划的最优方案

21

实验4 应用Excel求解网络问题

1实验目的：

• 掌握Excel中建立网络问题模型

• 掌握用Excel规划求解宏模块求解网络问题 2实验环境

启动Excel，并加载规划求解 3实验内容：供水管理问题 （1） 案例背景介绍

图4-1是一个供水网络的示意图，其中节点用1-10标记，表示由水管网络连接起来的城市、水库及泵站。3个城市分别为Gotham市，Metropolis市以及Spider Ville市，它们的供水来源为2个水库。水库1和水库2的供水能力分别为35千立方米/小时和25千立方米/小时。在图中每条管道上都标出了该管道的最大通过量，单位也为千立方米/小时。

35 20 1 水库1 12 25 2 水库2 22 6 15 3 10 10 5 15 6 22 7 10 10Spider ville 20 15 9Metrop10 olis 15 15 4 7 10 8Gotham City 17 图4-1 城市供水网络

现在需要研究现有的供水网络能否满足这些城市的用水量（分别为17,15,20千立方米/小时），请求出此网络的最大流。此网络能否满足这些城市的供水需要？

（2） 案例分析及数学模型表达

这是一个网络最大流问题，首先增加一个虚拟地点11和一个虚拟汇点12，使其成为只有一个起点和一个汇点的网络图，如图4-2所示。

22

35 1 水库1 35 11 25 25 2 水库2 6 20 15 12 3 10 15 4 10 5 15 15 7 10 17 8Gotham City 18 15 9Metrop10 olis 15 22 6 22 7 10 12 20 10Spider ville 20 图4-2 城市供水网络图

决策变量xij表示由节点i流向节点j的流量，dij表示相应弧上的容量。 目标是由节点11流出的流量最大，或由节点12汇入的流量最大，max z=x11,1+x11,2。

约束条件为每条弧上的容量xijdij，以及每一个节点的净流量。

节点i的净流量=流出量 — 流入量=xijxji

jj（3） 案例求解及最优方案

将供水管理问题的相关信息输入Excel电子表格，并设置决策变量单元格区域、目标单元格区域和约束条件单元格区域。

城市供水管理问题模型中的公式设置如表所示。在此模型中设置区域名称“From=$A$3:$A$22，To=$B$3:$B$22，Ship=$C$3:$C$22”。

图4-3城市供水管理问题的电子表格模型

23

表4-1城市供水管理问题模型中的公式设置

名称 Net Flow 单元格 公式 I3 SUMIF(From,H3,Ship)-SUMIF(To,H3,Ship) I4 SUMIF(From,H4,Ship)-SUMIF(To,H4,Ship) I5 SUMIF(From,H5,Ship)-SUMIF(To,H5,Ship) I6 SUMIF(From,H6,Ship)-SUMIF(To,H6,Ship) I7 SUMIF(From,H7,Ship)-SUMIF(To,H7,Ship) I8 SUMIF(From,H8,Ship)-SUMIF(To,H8,Ship) I9 SUMIF(From,H9,Ship)-SUMIF(To,H9,Ship) I10 SUMIF(From,H10,Ship)-SUMIF(To,H10,Ship) I11 SUMIF(From,H11,Ship)-SUMIF(To,H11,Ship) I12 SUMIF(From,H12,Ship)-SUMIF(To,H12,Ship) I13 SUMIF(From,H13,Ship)-SUMIF(To,H13,Ship) I14 SUMIF(From,H14,Ship)-SUMIF(To,H14,Ship) 最大流 B23 =I3 调用规划求解宏模块，规划求解宏模块的参数设置如下：

图4-4规划求解宏模块的参数设置

单击“求解”按钮后，规划求解结果如图4-5所示。

24

图4-5城市供水管理问题的最大流方案

25