生产管理运筹学软件实例管理分析

序 言

本实验指导书紧密配合《运筹学》课程的理论教学，系统地介绍了教学应用软件WINQSB (Quantitation Systems for Business Plus)和最新的建模与求解方法( Excel Spreadsheet方法)。WINQSB是运筹学上机实验软件，它技术成熟稳定，内容齐全，使用方便，对于加深理解课程内容，提高初学者学习掌握本课程的兴趣具有良好的补充作用。Excel Spreadsheet建模与求解方法是近年来国际上在管理科学教学与应用方面流行而有效的方法。它为管理科学提供了一种问题描述、数据处理、模型建立与求解的有效工具，是在Excel(或其它)背景下就所需求解的问题进行描述与展开，然后建立数学模型，并使用Excel的命令与功能进行预测、模拟、决策、优化等运算与分析。

指导书分为两部分，第一部分是WINQSB的使用，通过五个实验来完成，每个实验主要包括三个方面内容：①内容简介；②操作步骤；③实例分析与操作，另外对WINQSB进行了简要说明。第二部分是Spreadsheet建模与求解方法介绍，以实例的形式说明其中的重点和常用部分，实验内容基本同winQSB，对其余内容感兴趣的同学可参考相关资料自学。五个实验分别为：①线性规划；②灵敏度分析；③运输问题；④整数规划；⑤图与网络分析。

1

目 录

第一部分 WinQSB软件操作指南 ............................... 3

1. WinQSB软件简介 .................................................................................................... 3 2. WinQSB的一般操作 ................................................................................................ 3 3. WinQSB的求解模块 ................................................................................................ 4

第二部分 WINQSB实验内容 .................................. 6

1. 实验教学目的和要求 ............................................................................................ 6 2. 实验项目名称和学时分配 .................................................................................... 6 3. 单项实验的内容和要求 ........................................................................................ 6

实验1：线性规划的WinQSB应用..................................................................... 6 实验1作业 .......................................................................................................... 12 实验2：对偶线性规划的WinQSB应用........................................................... 13 实验2作业 .......................................................................................................... 15 实验3：运输问题的WINQSB应用 ..................................................................... 16 实验4：整数规划的WinQSB应用................................................................... 26 实验4作业 .......................................................................................................... 27 实验5：指派问题的WINQSB应用 ..................................................................... 27 实验5作业 .......................................................................................................... 29 实验6：网络问题的WINQSB应用 ..................................................................... 30 实验6作业 .......................................................................................................... 39

第三部分 Spreadsheet建模与求解 ........................... 41

第一章

Spreadsheet建模..................................................................................... 41 第一节 模型的概念与建立 ................................................................................ 41 第二节 Spreadsheet方法的应用 .................................................................... 41 第二章 应用Spreadsheet方法建立运筹学模型与求解 ..................................... 45

第一节 线性规划问题建模和求解 .................................................................... 45 第二节 运输问题 ............................................................................................ 49 第四节 最大流问题 ........................................................................................ 54

2

第一部分 WinQSB软件操作指南

1. WinQSB软件简介

QSB是Quantitative Systems for Business的缩写，早期的版本是在DOS操作系统下运行的，后来发展成为在Windows操作系统下运行的WinQSB软件，目前已经有2.0版。该软件是由美籍华人Yih-Long Chang和Kiran Desai共同开发，可广泛应用于解决管理科学、决策科学、运筹学及生产管理等领域的问题。该软件界面设计友好，使用简单，使用者很容易学会并用它来解决管理和商务问题，表格形式的数据录入以及表格与图形的输出结果都给使用者带来极大的方便，同时使用者只需要借助于软件中的帮助文件就可以学会每一步的操作。

2. WinQSB的一般操作

（1）安装与启动

点击WinQSB安装程序的Setup，指定安装目录后，软件自动完成安装。读者在使用该软件时，只需要根据不同的问题，调用程序当中的不同模块，操作简单方便。进入某个模块以后，第一项工作就是建立新问题或者打开已经存盘的数据文件。在WinQSB软件安装完成后，每一个模块都提供了一些典型的例题数据文件，使用者可以先打开已有的数据文件，了解数据的输入格式，系统能够解决什么问题，结果的输出格式等内容。例如，打开线性规划文件LP.LPP，系统显示如图A.1的界面。

程序名 菜单栏 标题栏 编辑栏 工具、各式 信息栏

图1-1

（2）数据的录入与保存

数据的录入可以直接录入，同时也可以从Excel或Word文档中复制数据到WinQSB。首先选中要复制的电子表格中单元格的数据，点击复制，然后在WinQSB的电子表格编辑状态下选择要粘贴的单元格，点击粘贴即可。

如果要把WinQSB中的数据复制到office文档中，选中WinQSB表格中要复制的单元格，点击Edit→Copy，to clipboard即可。

数据的保存，只需要点击File→Save as即可，计算结果的保存亦相同，只是注意系统以文本格式（*.txt）保存结果，使用者可以编辑该文本文件。

3

3. WinQSB的求解模块

关于WinQSB的各种模块及其功能，我们在下表中给出详细的说明。

序号 1 Analysis 模块 Acceptance Sampling 文件名 ASA 含义 抽样分析 设分析 具有多时期正常、加班、分时、转包生产量，需求量，存储费用，生2 Aggregate Planning AP 综合计划编制 产费用等复杂的整体综合生产计划的编制方法。将问题归结为线性规划模型或运输问题。 确定型与风险型决策、贝叶斯决3 Decision Analysis DA 决策分析 策、决策树、二人零和对策、蒙特卡罗模拟 4 5 Dynamic Programming Facility Location and Layout DP FLL 动态规划 设备场地布局 最短路问题、背包问题、生产与存储问题 设备产地设计、功能布局、线路均衡布局 简单平均、移动平均、加权移动平6 Forecasting FC 预测 均、线性趋势移动平均、指数平滑、多元线性回归、Holt-Winters季节迭加与乘积算法 Linear 7 Programming Programming 8 Inventory Theory and Systems Job Scheduling ITS 存储论与存储控制系统 作业调度，编制工作进度 经济批量订货、批量折扣、单时期随机模型、多时期动态存储模型、存储控制系统 机器加工排序、流水线车间加工排序 Goal and GP-IGP 目标规划与整数规划 多目标线性规划、线性目标规划 应用范畴 各种抽样分析，抽样方案设计、假Integer Linear Goal 9 JOB Linear 10 11 12 13 and Programming Integer Linear LP- ILP MKPA MRP Net 线性规划与整数规划 马二可夫过程 物料需求计划 网络模型 线性规划、整数规划、对偶、灵敏度分析 转移概率、稳态概率 物料需求计划的编制、成本核算 运输、指派、最大流、最短路、最小树、旅行推销商等问题 Programming Markov Process Material Requirements Planning Network Modeling 有（无）约束条件、目标函数或约14 Nonlinear Programming NLP 非线性规划 束条件非线性、目标函数与约束条件都非线性等规划问题的求解与分析

4

分析 15 Project Scheduling Quadratic Programming 16 and Integer Quadratic QP-IQP 二次规划 Programming 17 Queuing Analysis Queuing Simulation Quality Control Charts System QA 排队分析 PERT-CPM 关键路线法、计划评审技术、网络网络计划 的优化、工程完工时间模拟、绘制甘特图与网络图 求解线性约束、目标函数是二次型的一种非线性规划问题，变量可以取整数 各种排队模型的求解与性能分析、15种分布模型求解、灵敏度分析、服务能力分析、成本分析 18 19

QSS QCC 排队系统模拟 质量控制图 未知到达和服务之间分布、一般排队系统模拟计算 建立各种质量控制图和质量分析

5

第二部分 WINQSB实验内容

课程名称：运筹学/Operations Research 实验总学时数：16

适用专业： 管理科学与工程本科专业

1. 实验教学目的和要求

本实验与运筹学理论教学同步进行。

指导思想：运筹学是管理类学科的专业基础课，重点介绍运筹学模型和方法。对于在实际问题中的应用，往往模型具有较大的规模，常常需要借助于计算机这样的工具，才有可能得到最终的计算结果。经过上机实验，可使学生更好运用课堂上讲授的方法去解决实际问题，检测自己解决实际问题的能力。同时，会加深对实际应用的理解，做到学以致用。

目的：

（1）熟练使用相关软件；

（2）初步学会用运筹学方法解决实际问题； （3）加深对课堂内容的理解和消化。

充分发挥WinQSB软件的强大功能和先进的计算机工具，改变传统的教学手段和教学方法，将软件的应用引入到课堂教学，理论与应用相结合。丰富教学内容，提高学习兴趣。使学生能基本掌握WinQSB软件常用命令和功能。

要求：

（1）熟悉程序的使用 （2）学会对运算结果的分析； （3）学会根据运算结果修正模型。

熟悉WinQSB软件子菜单。能用WinQSB软件求解运筹学中常见的数学模型。 实验考核

（1）出勤检查，上机作业检查；

（2）上机实验考试，占总成绩10％左右。

2. 实验项目名称和学时分配

实验项目 学时分配 一 2 二 2 三 整数规划 2 四 2 五 2 六 网络模型 2 实验名称 线性规划 对偶问题 目标规划 运输问题 3. 单项实验的内容和要求 实验1：线性规划的WinQSB应用

（一）实验目的：安装WinQSB软件，了解WinQSB软件在Windows环境下的文件管理操作，熟悉软件界面内容，掌握操作命令。用WinQSB软件求解线性规划。

（二）内容和要求：安装与启动软件，建立新问题，输入模型，求解模型，结果的简单分析。

6

（三）操作步骤：

1.将WinQSB文件复制到本地硬盘；在WinQSB文件夹中双击setup.exe。 2.指定安装WinQSB软件的目标目录（默认为C:\\ WinQSB）。

3. 安装过程需输入用户名和单位名称（任意输入），安装完毕之后，WinQSB菜单自动生成在系统程序中。

4.熟悉WinQSB软件子菜单内容及其功能，掌握操作命令。

5．求解线性规划。启动程序 开始→程序→WinQSB→Linear and Integer Programming 。 6．学习例题 点击File→Load Problem→lp.lpp, 点击菜单栏Solve and Analyze或点击工具栏中的图标用单纯形法求解，观赏一下软件用单纯形法迭代步骤。用图解法求解，显示可行域，点击菜单栏Option →Change XY Ranges and Colors，改变X1、X2的取值区域（坐标轴的比例），单击颜色区域改变背景、可行域等8种颜色，满足你的个性选择。

下面结合例题介绍WinQSB软件求解线性规划的操作步骤及应用。

例1. 用WinQSB软件求解下列线性规划问题：

maxZ?6x1?5x2?x3?7x4

?x1?2x2?6x3?9x4?260?8x?5x?2x?x?150234?1?s.t. ?7x1?x2?x3?30

?x1?x2?0?x?x?0?34?10?x3?20?x,x,x?0,x无约束4?123解：应用WinQSB软件求解线性规划问题不必化为标准型，如果是可以线性化的模型则

先线性化，对于有界变量及无约束变量可以不用转化，只需要修改系统的变量类型即可，对于不等式约束可以在输入数据时直接输入不等式符号。

（1）启动线性规划（LP）和整数规划（ILP）程序

点击开始→程序→WinQSB→Linear and Integer Programming，显示线性规划和整数规划工作界面（注意菜单栏、工具栏和格式栏随主窗口内容变化而变化）。这一程序解决线性规划（LP）以及整数线性规划（ILP）问题。

IP-ILP的特殊性能包括： ? LP的单纯形法与图形法 ? ILP的分枝定界法 ? 显示单纯形表

? 显示分枝定界法解决方案 ? 执行灵敏性或参数分析 ? 寻求可选择的解决

? 对不可行问题进行不可行分析 ? 用电子表格矩阵式输入问题 ? 用普通模型形式输入问题 ? 定制变量边界与类型 ? 自动生成对偶问题

7

图1-1 LP-ILP模块的主要功能 （2）建立新问题或者打开磁盘中已有的文件

点击File→New Problem建立一个新问题。输入本问题的文件名称lp1（读者可以任意取名），决策变量个数4和约束条件个数5，由于本问题是一个最大化问题，所以选择Maximization，同时可以确定数据的输入形式，一种为表单形式，一种为模型形式。如果我们选择了表单形式，如图2-1所示。

（3）输入数据

按照例1以表格或模型形式输入变量系数和右端常数数据。

决策变量个数

目标函数取极大还是极小进行选择

约束条件个数 数据类型定义 数据输入方式选择： 表单式、一般模型形式

（4）修改变量类型

图1-2 LP-ILP模型基础设定 图1-3种给出了非负连续、非负整数、0-1型和无符号限制或者无约束4种变量类型选项，当选择了某一种类型后系统默认所有变量都属于该种类型。在例1中，10?x3?20，直接将x3中的下界（Lower Bound）改为10，上界（Upper Bound）改为20。把x4设定为无约束（Unrestricted），

表1-1 初始单纯型表

M是一个任意大的正数。 得到如表1-1所示的表格。

（5）修改变量名和约束名。

系统默认变量名为X1，X2，?，Xn，约束名为C1，C2，?，Cm。默认名可以修改，点击菜单栏Edit后，下拉菜单有四个修改选项：修改标题名(Problem Name)、变量名(Variable Name)、约束名(Constraint Name)和目标函数准则(max或min)。由于WinQSB软件支持中文，读者可以输入中文名称。

8

（6）求解

点击菜单栏Solve and Analyze，下拉菜单有三个选项：求解不显示迭代过程（Solve the

Problem）、求解并显示单纯形法迭代步骤(Solve and Display Steps)及图解法(Graphic Method，限两个决策变量)。如选择Solve the Problem，系统直接显示求解的综合报告如表1-2所示，表中的各项含义见表1-5。线性规划问题有最优解或无最优解（无可行解或无界解），系统会给出提示。

表1-2 winqsb线性规划求解的综合报告

由表1-2得到例1的最优解为X?(1.4286,0,20,?98.5714)T，最优值Z??661.4285。同时由表2的第6行提示Alternate Solution Exists!!知原线性规划问题有多重解。

（7）显示结果分析

点击菜单栏result或者点击快捷方式图标，存在最优解时，下拉菜单有9个选项（如下1）~9）），无最优解时有两个选项（如下10）~11））。

1) 只显示最优解(Solution Summary)。

2) 约束条件摘要(Constraint Summary)，比较约束条件两端的值。 3) 对目标函数进行灵敏度分析(Sensitivity Analysis of OBJ)。

4) 对约束条件右端常数进行灵敏度分析(Sensitivity Analysis of RHS)。 5) 求解结果组合报告(Combined Report)，显示详细综合分析报告。

6) 进行参数分析(Perform Parametric Analysis)，某个目标函数系数或约束条件右端常数带

有参数，计算出参数的变化区间及其对应的最优解，属于参数规划内容。 7) 显示最后一张单纯性表(Final Simplex Tableau)。

8) 显示另一个基本最优解(Obtain Alternate Optimal)，存在多重解时，系统显示另一个基本

最优解，然后考虑对基本最优解进行组合可以得到最优解的通解。 9) 显示系统运算时间和迭代次数(Show Run Time and Itration)。

不可行性分析(Infeasibility Analysis)，线性规划问题无可行解时，系统指出存在无可行解的原因，

如将例1的第5个约束改为x3?x4?0，系统显示无可行解并且给出这样的显示报告：

表1-3 winqsb线性规划求解不可行性分析表

这说明第5个约束不可能小于等于零，右端常数至少等于117.1429才可行。

9

（11）无界性分析(Unboundedness Analysis)，线性规划问题存在无界解时，系统指出存在无界解的可能原因。如将目标函数系数c4?7改为c4??7，系统显示无界并且显示：

表1-4 winqsb线性规划求解无界性分析表

系统提示要使线性规划问题有解，应该改变第二个约束条件。

（12）保存结果。求解后将结果显示在顶层窗口，点击File→Save As，系统以文本格式存储计算结果。

（13）将计算表格转换成Excel表格。在计算结果界面中点击File→Copy to Clipboard，系统将计算结果复制到剪贴板，再粘贴到Excel表格中即可。

（8）单纯形表

选择求解并显示单纯形法迭代步骤，系统显示初始单纯性表如表1- 1所示可以发现，系统将X4无约束改写成X4－Neg_X4，即两个非负变量之差；系统将10?x3?20改写成约束C6：

??10，将x3?x3??x3?10，则有x3??10代入约束条件并整理，在表中0?x3?10?10，令x3?，如约束C1： 的x3实际上是x3X1+2X2+6(X3+10)+9X4－Neg_X4+Slack_C1=260

整理后得到表1-5第一行（Slack_C1）。

约束C1，C4，C5，C6加入4个松弛变量Slack_C1，Slack_C4，Slack_C5以及Slack_UB_X3，约束C2减去剩余变量Surplus_C2，然后C2与C3加入2个人工变量Artificial_C2和Artificial_C3，共6个约束12个变量。

表2最后两行为检验数，如X1的检验数C(1)－Z(1)*Big M=6－15M。选X1进基，表2-1最后一列为比值，变量Artificial_C3出基，主元素A(3,1)=7。

下一步点击菜单栏Simplex Iteration选择Next Iteration继续迭代，还可以人工选择进基变量，或直接显示最终单纯形表。

（9）模型形式转换

点击菜单栏Format→Switch to Normal Model Form，将表1-5电子表格转换成表1-6的模型形式，再点击一次转换成表1-5的电子表格。

（10）写出对偶模型

点击菜单栏Format→Switch to Dual Form，系统自动给出线性规划的对偶模型，再点击一次给出原问题模型。

表1-5 初始单纯形表

10

图1-3 标准模型输入形式 附录： 线性规划常用术词汇及其含义

常用术语 含义 常用术语 含义 Alternative Solution Exists 有多重解 Basic and Nonbasic Variable 基变量和非基变量 Basis 基 Basis Status 基变量状态 Branch-and-Bound Mrthod 分支定界法 Cj-Zj 检验数 Combined Report 组合报告 Constraint Summary 约束条件摘要 Constraint 约束条件 Constraint Direction 约束方向 Constraint Status 约束状态 决策变量 Decision Variable 对偶问题 Dual Problem 入基变量 Entering Variable 可行域 Feasible Area 可行解 Feasible Solution 不可行 Infeasible 不可行分析 Infeasibility Analysis 出基变量 Leaving Variable 左端 Left-hand side 上界或下界 Lower or Upper Bound 最优解不变时，价Minimum and Maximum 值系数允许变化范Allowable Cj 围 Minimum and 最优基不变时，资源限Maximum Allowable 量允许变化范围 RHS 右端系数 Objective Function 目标函数 Optimal Solution 最优解 Parametric Analysis 参数分析 Range and Slope of 参数分析的区间和斜Parametric Analysis 率 Reduced Cost 约简成本（价值） Range of Feasibility 可行区间 Range of Optimality 最优区间 Relaxed Problem 松弛问题 Relaxed Optimum 松弛最优 Right-hand Side 右端常数 Sensitivity Analysis of 目标函数的灵敏度分OBJ Coefficients 析 Sensitivity Analysis of 右端常数的灵敏度分Right-Hand-sides 析 Shadow Price 影子价格 Simplex Method 单纯形法 Slack, Surplus or 松弛变量、剩余变量或Artificial Variable 人工变量 Solution Summary 最优解摘要 Subtract(Add) More 减少（增加）约束系数 Than This From A(i,j) 总体贡献 Total Contribution 无界解 Unbounded Solution

11

实验1作业

（1）某昼夜服务公共交通系统每天各时间段（每4小时为一个时间段）所需的值班人员如下表所示。这些值班人员在某时段上班后要连续工作8个小时（包括轮流用膳时间在内）。问该公交系统至少需多少名工作人员才能满足值班的需要。

（2）（任务分配问题）某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？

单位工件所需加工台时数 车床 类 型 工件1 工件2 工件3 0.4 1.1 1.0 甲 乙 0.5 1.2 1.3 单位工件的加工费用 工件1 13 11 工件2 9 12 工件3 10 8 可用台时数 800 900 （3）（厂址选择问题）考虑A、B、C三地，每地都出产一定数量的原料，也消耗一定数量的产品（见表9-15）。已知制成每吨产品需3吨原料，各地之间的距离为：A-B：150km，A-C：100km，B-C：200km。假定每万吨原料运输1km的运价是5000元，每万吨产品运输1km的运价是6000元。由于地区条件的差异，在不同地点设厂的生产费用也不同。问究竟在哪些地方设厂，规模多大，才能使总费用最小？另外，由于其它条件限制，在B处建厂的规模（生产的产品数量）不能超过5万吨。 A、B、C三地出产原料、消耗产品情况表 地点 A B C 作业要求：

（1）建立问题模型、输入选项(电子表格、变量取非负连续)、输入数据、存盘、求解模型、结果存盘、观察结果。

（2）将所有变量取非负整数、求解、观察结果、存盘、打印窗口、打印结果。 (3) 将电子表格格式转换成标准模型。 （4）分析结果。

（5）将结果复制到Excel或Word文档中。

12

年产原料（万吨） 20 16 24 年销产品（万吨） 7 13 0 生产费用（万元/万吨） 150 120 100

实验2：对偶线性规划的WinQSB应用

（一）实验目的：掌握winQSB软件写对偶规划，灵敏度分析和参数分析的操作方法

（二）内容和要求：建立线性规划的对偶问题，求解模型，进行灵敏度分析和参数分析。

（三）操作步骤：

下面结合例题介绍WinQSB软件求解对偶线性规划的操作步骤及应用。

例2：已知线性规划

maxZ?x1?2x2?4x3?x4

?3x1?9x3?5x4?15?6x?4x?x?7x?301234??s.t.?4x2?3x3?4x4?20 ?5x?x?8x?3x?4034?12??xj?0,j?1,2,3,4（1） 写出对偶线性规划，变量用y表示； （2） 求原问题及对偶问题的最优解；

（3） 分别写出价值系数cj及右端常数的最大允许变化范围；

（4） 目标函数系数改为C?(4,2,6,1)，同时常数改为b?(20,40,20,40)，求最优解； （5） 删除第四个约束同时删除第三个变量，求最优解；

（6） 增加一个变量x5，系数为(c5,a15,a25,a35,a45)?(6,5,4,2,3)，求最优解。 解：启动线性规划与整数规划（Linear and Integer Programming），建立新问题，取名为dual1（可任意取名），输入数据得到表2-1，存盘。

表2-1

（1）点击Format→Switch to Dual Form，得到对偶问题的数据表，点击Format→Switch to Normal Model Form，得到对偶模型，点击Edit→Variable Name，分别修改变量名，得到以为变量名的对偶模型，如图2-1所示。

13

图2-1

（2）再求一次对偶返回到原问题，求解显示结果如表2-2，此时最优解为

X?(2,4.25,1,0)T，最优值Z?145。表中影子价格(Shadow Price)对应列的数据就是对偶

问题的最优解为Y?(0.2833.0.025,0.475,0)。

表2-2 最优解详细综合分析报告

（3）由表2-2最后两列可知：

价值系数cj(j?1,2,3,4)最大允许变化范围分别是

[0.8333,4.1667]，[1.333,5.7778]，[1.1667,4.5]，(??,3.4917]；

右端常数bi(i?1,2,3,4)的最大允许变化范围分别是

[5,27.4719]，[16.6667,50]，[0，33.3333]，[30.75,??)。

（4）直接修改表2-1的数据，求解后得到最优解为X?(3.6667,4.25,1,0)T，最优值

Z?29.1667。

（5）将数据修改回原问题，点击Edit→Delete a Constraint，选择要删除的约束C4，ok。点击Edit→Delete a Variable，选择要删除的变量X3，ok。得到如表2-3的模型，求解得到最优

T解为X?(1.6667,5,0)，最优值Z?11.6667。

表2-3

14

（6）调用原问题数据表，点击Edit→Insert a Variable，选择变量名和变量插入的位置，如图2-2，在显示的电子表格中输入数据(6,5,4,2,3)，得到最优解为X?(0,3.5,0,0,3)T，最优值

Z?25。

图2-2

实验2作业

（1）公司打算在三个工厂生产两种新产品，有数据如下：

生产每个单位产品所需时间 工厂1 工厂2 工厂3 单位利润（美元） 门 1小时 0 3小时 300 窗 0 2小时 2小时 500 每周可得时间 4小时 12小时 18小时 求得的最优解是：每周生产门2个，窗6个，总利润为3600美元。

对于研究者提出这个方案，管理层通过讨论后，提出以下问题：

（1） 如果新产品中，有一个产品的单位利润估计值不准确，将会发生怎样的情况？比如：现在估计门的价格单位利润是每个300美元，问，该价格可以在多大程度上偏离实际值，而最优解不变？

（2） 如果两种产品的单位利润都估计不准确呢？

（3） 如果某个工厂的可用时间发生变化，将会对结果产生什么影响？ （4） 如果三个工厂的可用时间都发生变化呢？ 请同学简述一下分析思路。

（2）利博公司的广告组合问题

15

利博公司生产清洁产品，这是一个高度竞争市场，公司为增加市场份额挣扎了多年。管理层决定集中在下列三个主要产品上实行一个大规模的广告运动：（1）一种喷雾去污剂；（2）一种新的液体洗涤剂；（3）一种成熟的洗衣粉。

这一广告活动将采用全国的电视和印刷媒体。管理层为广告运动设定了最低目标：（1）喷雾去污剂必须再增加3％的市场份额；（2）新的洗涤剂必须再洗涤剂市场获得18％的份额；（3）洗衣粉的市场份额必须增加4％。下表给出了这次活动的一些估计数据。

每单位广告增加的市场份额 产品 喷雾去污剂 液体洗涤剂 洗衣粉 单位成本 问题： （1）建模求解：以最低的总成本达到市场份额的目标，需要在每种媒体上作多少广告？ （2）如果液体洗涤剂的市场份额最小增加量从18％增加到36％，重新求解，生成包括最优解和总成本的数据表。

（3）使用（2）的结论确定：a.市场份额最小增加量每增加一个百分比，所增加的成本；b.市场份额最小增加量增加到多大时，每增加一个百分比的成本开始上升？ （4）使用winqsb进行灵敏度报告，描述该报告中（3）所需的信息。

利润（3） maxZ?4x1?2x2?3x3 ?2x1?2x2?4x3?100材料1约束?

?3x1?x2?6x3?100材料2约束?

?3x1?x2?2x3?120材料3约束

??x1，x2，x3?0

1) 写出对偶线性规划，变量用y表示。

2) 求原问题及对偶问题的最优解。

3) 分别写出价值系数cj及右端常数的最大允许变化范围。

4) 目标函数系数改为C＝（5，3，6）同时常数改为b=（120，140，100），求最优解。 5) 增加一个设备约束 和一个变量x4，系数为（c4,a14,a24,a34,a44）=（7，5，4，1，2），求最优解。

6) 在第5问的模型中删除材料2的约束，求最优解。

电视 0％ 3％ －1％ 100万美元 印刷媒体 1％ 2％ 4％ 200万美元 需要的最小增加量 3％ 18％ 4％

实验3：运输问题的WINQSB应用

（一）实验目的：熟悉运用WinQSB软件求解运输问题，掌握操作方法。 （二）内容和要求：建立运输问题模型，输入模型，求解模型。

1、 分析问题，确定供应点、销售点及中转点的名称，以及它们所对应的值； 2、 确定节点间的单位成本或单位利润； 3、 输入已知信息，或调入已存问题；

16

（三）操作步骤：

1．启动程序，开始→程序→winQSB→Network Modeling

2．建立新问题，分别选择Trnsportation Problem、Minimization、Spreadsheet，输入标题、产地数为和销地数为。

3．输入数据，空格可以输入M或不输入任何数据，点击Edit→Node Names，对产地和销地更名。 4．求解并显示和打印最优表及网络图。

在WinQSB软件的网络流模块中，一般运输模型的求解采用的是上面介绍的表上作业法。下面我们以例3的报刊征订、推广费用节省问题为示例，说明怎样应用WinQSB软件计算产销

（四）实例操作

1. 平衡的运输问题

例3. 该问题的产销平衡和运价表，如下表3-1所示。

（1）调用WinQSB软件的子程序Network Modeling，建立一个新问题，弹出对话筐，如右图3-1所示界面，选择Network Flow 或者Transportation Problem（本例我们选择后者），以及Minimization，输入问题的文件名Tran1（读者自己可以任意取名），产地数目3和销地数目3。

图3-1

（2）接着，点击ok，此时弹出一张需要输入数据的表格，对照上表输入数据，并重新命名产地和销地，系统输出如表3-2所示的数据表格。

17

表3-2 运输问题的winqsb显示

（3）点击菜单栏Solve and Analyze，下拉菜单有四个求解方法供选择：Solve the Problem（只求出最优解）、Solve the Display Steps-Network（网络图求解并显示迭代步骤）、Solve the Display Steps-Tableau（表格求解并显示迭代步骤）、Select Initial Solution Method（选择求初始解方法）。初始解求解方法有八种方法供选择： a) b) c) d) e) f) g) h)

Row Minimum（RM）逐行最小元素法

Modified Row Minimum（MRM）修正的逐行最小元素法 Column Minimum（CM）逐列最小元素法

Modified Column Minimum（MCM）修正的逐列最小元素法 NorthWest Corner Method（NWC）西北角法

Matrix Minimum（MM）矩阵最小元素法，即最小元素法 Vogel’s Approximation Method（VAM）Vogel近似法 Russell’s Approximation Method（RAM）Russell近似法

如果不选择，系统缺省方法是逐行最小元素法（RM）。

如果选择最小元素法（MM）、Solve the Display Steps-Tableau，得到如表3-3所示的初始表。由表可以看到入基、出基变量，还可以得到位势即对偶变量（Dual P(i)、Dual P(j)），求出检验数。

表3-3 例3运输问题的初始表格

（4）继续迭代得到最优方案表，如表3-4所示。

18

表3-4 例3运输问题的最优方案

此时，最优调运方案为：中文书刊出口部调运7500册寄往日本、调运2500册寄往中国香港特别行政区、调运5000册寄往韩国，深圳分公司的7500册全部寄往中国香港特别行政区，上海分公司的7500册全部寄往日本，总费用为214000元。

最后，点击菜单栏Results→Graphic Solution，系统以网络图的形式显示最优调运方案，见图3-2.

图3-2 例3运输问题最优解的图示

下面，我们给大家介绍怎样运用WinQSB软件计算产销不平衡的运输问题，以下例水果调运问题为例来说明，这是一个销大于产的问题。

2. 不平衡的运输问题

例4. 水果调运问题。有三个水果生产基地供应四个地区的某种新鲜水果。假定等量的水果在这些地区受欢迎程度相同。各生产基地年产量，各地区年需求量以及从各生产基地到各地区单位水果的运价如表3-5所示，试给出总的运费最节省的水果调运方案。

表3-5 水果调运的基础数据 运价：万元/万吨

19

用软件求解不用把产销不平衡问题化为平衡问题，令c22?M，软件实施步骤和例3 的一样，我们把文件名取为Tran2，输入产地数目3和销地数目4，点击ok后按照表3-5输入数据，得到表格3-6。

表3-6

如果选择西北角法（NWC）、Solve the Display Steps-Tableau，得到如下表所示的初始表。由表可以看到入基、出基变量，还可以得到位势即对偶变量（Dual P(i)、Dual P(j)），求出检验数，见表3-7。

表3-7 例4运输问题的初始表格

继续迭代得到最优方案表，如表3-8所示。此时，最优调运方案为：A1生产基地运送50万吨水果供应B3地区；A2生产基地分别运送20万吨水果供应B1和B3地区；A3生产基地运送40万吨水果供应B1地区，分别运送20万吨水果供应B2和B4地区；B2地区有10万吨水果需求不能满足；总费用为1470万元。

表3-8 例4运输问题的最优方案

20

最后，点击菜单栏Results→Graphic Solution，系统以网络图的形式显示最优调运方案，见图3-3。

图3-3 例4运输问题最优解的图示

3、综合生产计划问题

对于这类问题，读者可以将其化成平衡运输问题来求解，但WinQSB软件提供了此类综合生产计划问题的求解模块。为此，我们举一例介绍WinQSB软件的操作方法。

例5. 某企业未来四个季度的需求量、生产能力及有关费用如表3-9所示，试制定全年总费用最小的生产计划。

表3-9 综合生产计划问题的基础数据 1、各时期预测需求量（件） 2、正常时间生产能力 3、正常时间生产单位成本（千元） 4、加班时间生产能力 5、加班时间生产单位成本（千元） 6、期初存量（+）或延期交货量（—） 7、最小期末存量（安全存量） 8、单位产品每季度贮存费（千元） 9、转包（外协）生产能力 10、转包生产单位产品成本（千元） 第一季度 500 400 1.1 150 1.5 300 0.2 300 1.8 第二季度 950 500 1.3 150 1.5 0.2 300 1.8 第三季度 1600 850 1.2 150 1.5 0.2 300 1.8 第四季度 650 450 1.4 90 1.5 350 0.2 300 1.8 调用WinQSB软件的子程序Aggregate Planning，建立新问题，在选项对话框中选中Transportation Model、Overtime Allowed及Subcontracting Allowed，输入文件名Aggp1（读者自己可以任意取名），计划时期数4和期初存量300。如果期初还要补充上期的缺货量（延迟交货，Backorder），则输入负数，如图3-4所示。

21

图3-4

点击ok，弹出数据输入对话框，输入数据，重命名计划时期，得到表3-10。点击菜单栏Solve and Analyze→Solve the Problem，显示表3-11的生产计划表。点击菜单栏Results→Show Transportation Tableau，显示类似运输问题运价——运量的最优表，限于篇幅，表3-12只显示了一部分内容，这样我们就可以得到完整的生产计划。比如，对于第一季度，期初库存量在第一季度交货；正常时间生产400件产品，第一、二季度分别交货200件；加班时间生产150件产品用于第二季度交货100件，第三季度交货50件；转包生产110件用于第四季度末库存。总费用为5654千元。

表3--10

表3-11

22

表3-12

4、转运问题

WinQSB软件处理转运问题有两种方法，第一种方法是先化为产销平衡运价表，然后运用表上作业法求解，调用子程序Network Modeling→Transportation Problem；第二种方法是将问题看作是一般网络图，不需要将问题转换为产销平衡的运输问题，调用的子程序Network Modeling→Network Flow，输入数据时，中转地与需求地的供应量为零，供应地与中转地的需求量为零，运价按实际发生的运价输入，本地到本地和不可到达空白不需要输入运价。数据输入表格如表3-13所示。

表3-13

点击菜单栏Solve and Analyze→Solve the Problem，显示表3-14的最优运输方案。点击菜单栏Results→Graphic Solution，得到最优运输网络图，如图3-5所示。

23

表3-14

图3-5

实验3作业：

（1）案例分析与求解

特塞格公司（Texago Corporation） 是一家设在美国本土的大型一体化石油公司。这家公司大部分石油在公司自己的油田中生产，所需的其他部分从中东地区进口。公司有大型的配送网络，把石油运送到公司的炼油厂，然后再把石油产品从炼油厂运送到公司的配送中心。

特塞格公司的市场看好。因此管理层决定建立一个新的炼油厂来增加公司的产量，同时增加从中东地区进口的石油数量。接下来所要做的决定是确定在什么地方建设新的炼油厂。

新的炼油厂的加入对整个配送系统都将产生巨大影响，其中包括要确定从每一个出发地运输到炼油厂的原油量，以及从每一个炼油厂运送石油制品到每一个配送中心的数量。因此，影响管理者选择新厂地址有以下三个因素：

? 从出发地运送原油到所有炼油厂（包括新炼油厂）的成本；

? 从所有炼油厂（包括新炼油厂）运送石油制品到每一个配送中心的成本。

? 新的炼油厂的运作成本，包括劳动力成本、税赋、原料（不含原油）成本、能源成

本、保险成本，等等。（资金成本不是一个所要关注的因素，因为任何地点的资金成本几乎都是一样的。）

第一步 收集必要的数据

公司确定了新厂的三个备选地址。

管理者希望每个炼油厂都满负荷运转（包括新厂）。因此运筹学小组需要确定这一条件下每个炼油厂每年需要的原油数量。

当然还需要许多其他大量的数据，我们在此就不一一说明理由了。收集数据整理如下。

24

表1 生产数据

炼油厂 炼油厂1 炼油厂2 炼油厂3 新炼油厂 总量 油田1 油田2 油田3 中东进口 炼油厂1 炼油厂2 炼油厂3 新厂1 新厂2 新厂3 所需量 地点 新厂1 新厂 2 新厂3 炼油厂1 2 4 5 2 每年需要原油（百万桶） 100 60 80 120 360 油田/进口 油田1 油田2 油田3 中东进口 总量 每年原油产量（百万桶） 80 60 100 120 360 表2 向炼油厂运输原油的运输成本数据 向炼油厂运输原油的单位运输成本（百万美元/百万桶） 炼油厂2 4 5 7 2 炼油厂3 5 2 3 5 新厂1 3 1 4 4 新厂2 1 3 5 3 新厂3 3 4 6 4 表3 石油制品运送到配送中心的运输成本数据 把石油制品运输到配送中心的单位成本（百万美元） 配送中心1 5 6 7 8 5 4 100百万桶 配送中心2 2 4 8 6 4 3 80百万桶 配送中心3 6 3 4 3 3 1 80百万桶 配送中心4 8 5 3 2 6 5 100百万桶 表4 新炼油厂的估计运营成本数据 每年运营成本（百万美元） 620 570 530

作业要求：请在上述分析的基础上，确定哪个新厂的地址是最优的。

（2）煤炭销售地1、2、3、4、5每年需要量为11、12、9、10、800万吨；公司有三个煤炭产地1、2、3，年产量分别为15、20、1500万吨。以前使用火车运输，现在火车运输成本上涨了。所以考虑将部分煤炭用轮船运输，但是使用轮船运输将会有一些先期投入。具体数据如下。 源 1 2 3 使用火车运输的成本（千元/吨） 1 61 69 59 2 72 78 66 3 45 60 63 4 55 49 61 5 66 56 47 使用轮船运输的成本（千元/吨） 1 31 36 － 2 38 43 33 3 24 28 36 4 － 24 32 5 35 31 26 25

出发地 1 2 3 使用轮船运输煤炭的先期投资（千元/年） 1 275 293 － 2 303 293 283 3 238 270 275 4 － 250 268 5 285 265 240 要求：请做出最优的运输计划。

—————————————————————————————————————————

实验4：整数规划的WinQSB应用

（一）实验目的：用WinQSB软件求解整数规划（纯整数、混合整数）、0－1规划 （二）内容和要求：建立整数规划问题，输入模型，求解模型。 （三）操作步骤：

运用WinQSB软件求解线性整数规划仍然是调用子程序Linear and Integer Programming，操作时改变变量类型即可。下面以例为例说明这个应用。

例6. 用WinQSB软件求解以下整数规划问题 max z= x1 +4x2 s.t. 14x1 +42x2 ≤196

解：首先启动子程序Linear and Integer Programming，建立新问题，输入类似图3-1的选项。本例中，变量数等于2，约束数等于2，变量类型选非负整数（Nonnegative integer）。然后输入数据，见下表4-1。

表4-1

点击菜单栏

的下拉菜单Solve the Problem得到表4-2所示的最优表。

表4-2

Solve and Analyze

-x1 x1,

+2x2 x2

≤ 5 ≥0

x1, x2 为整数

26

最优解为：x1=5，x2=3，x3=0，x4=4，x5=0，最优值为 z=17。

其他类型的整数规划问题只要改变变量类型即可。

实验4作业：

1.已知某电机运输问题

请问：请如何安排调运方案，即满足用户需要，又使总的运费最少？

2. 某人有一背包可以装10公斤重、0.025m3的物品。他准备用来装甲、乙两种物品，每件物品的重量、体积和价值如下表所示。

（1）请问两种物品各装多少件，所装物品的总价值最大？

（2）假设此人还有一只旅行箱，最大载重量为12公斤，其体积是0.02m3。背包和旅行箱只能选择其一，建立下列几种情形的数学模型并求解，使所装物品价值最大。

1)所装物品不变；

2）如果选择旅行箱，则只能装载丙和丁两种物品，价值分别是4和3，载重量和体积的约束为

1.8x1?0.6x2?121.5x1?2x2?20（3）企业计划生产4000件某种产品，该产品可自己加工、外协加工任意一种形式生产．已知每种生产的固定费用、生产该产品的单件成本以及每种生产形式的最大加工数量（件）限制如下表所示，怎样安排产品的加工使总成本最小．

实验5：指派问题的WINQSB应用

（一）实验目的：熟悉运用WinQSB软件求解指派问题，掌握操作方法。 （二）内容和要求：建立指派问题的数学模型，并用软件求解。

27

（三）求解问题的步骤如下：

1．建立新问题，选择Assignment Problem，在Number of Objects 中输入人数5，Number of Assignments中输入工作数4，选择maximization。

2．输入数据，点击菜单栏Edit/node names，重新命名人名和工作名，求解。 3．写出两题的计算结果。

例7.求下列最大值的指派问题

?21097??154148?? C＝??13141611???415139??在WinQSB软件的网络流模块中，指派问题的求解采用的是上面介绍的匈牙利解法。下面我们上例为示例，说明怎样应用WinQSB软件计算指派问题。

首先，调用WinQSB软件的子程序Network Modeling，建立一个新问题，弹出对话筐，如图5.30所示界面，选择Assignment Problem，输入问题的文件名Assig1（读者自己可以任意取名），人数4及任务数4。

图5-1

然后，点击ok，此时弹出一张需要输入数据的表格，对照上面的信息输入数据，重命名网络节点后得到表5-54，与运输问题的求解方法一样，点击Solve the Display Steps-Tableau时，系统输出匈牙利解法的每一步迭代结果，如表5-3到表5-5所示。点击菜单栏Results→Graphic Solution，以网络图的形式显示结果。

表5-2

28

表5-3 表5-4

表5-5

实验5作业

（1）某汽车公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本（元/件）如下表所示．求最优生产配置方案．

工厂1 工厂2 工厂3 工厂4

（2）某城市开办了第三所中学，需要为每一所学校重新划定这个城市的服务区域。初步划分中，全城被分成人口大致相等的九个区。每个区的中学生人数以及每个区到各个中学的平均近似距离等数据见下表。

各个学区到各个中学的平均距离（公里） 学区1 学区2 学区3 学区4 学区5 中学生人数 中学1 2.2 1.4 0.5 1.2 0.9 中学2 1.9 1.3 1.8 0.3 0.7 中学3 2.5 1.7 1.1 2.0 1.0 500 400 450 400 500 产品1 产品2 产品3 产品4 58 75 65 82 69 50 70 55 180 150 170 200 260 230 250 280 29

学区6 学区7 学区8 学区9 最小招生数 最大招生数 1.1 2.7 1.8 1.5 1200 1800 1.6 0.7 1.2 1.7 1100 1700 0.6 1.5 0.8 0.7 1000 1500 450 450 400 500 学区管理当局还要求，每个区的学生只能到同一个学校就学，每三个区的学生到一个中学上学。

学区管理当局认为，划分入学区域界限的适当目标是要使学生到学校的平均路程最短（即学生上学的总路程最短）。请问，如何为各个区的学生指派一个中学，使得学生上学每天走的总路程最小。

（提示：由于是把区域指派给学校，所以这个问题可以看成是一个指派问题的变形。其中区域是被指派者，学校就是任务。现在，一个任务由三个被指派者来完成。指派问题中以总成本最小为目标，在这里，这个成本换成了每个区的所有学生到学校上学的路程，目标换成了使总路程最小。）

（3）某公司购买了三种不同类型的新机器（各一台），可以安装在五个不同车间。有关数据如下表：

每小时成本（元） 位置 车间1 机器1 机器2 机器3 13 15 4 车间2 16 － 7 车间3 12 13 10 车间4 14 20 6 车间5 15 16 7 请问：如何分配机器到各个车间（每个车间最多分配一种机器），使总的原料加工成本最低。

实验6：网络问题的WINQSB应用

实验目的：

（一）实验目的：掌握不同问题的输入方法，求解网络模型，观察求解步骤，显示并读出结果。

（二）内容和要求：用WinQSB软件求解最小支撑树、最短路、最大流及旅行售货员等问题。 （三）操作步骤：

1．启动程序，开始→程序→winQSB→Network Modeling

2．求最小支撑树：建立新问题，选择Minimal Spanning Tree，输入标题名，网络节点数；输入

30

节点到节点的距离，求解显示最小支撑树。

3．求最短路：建立新问题，选择Shortest Path Problem，输入标题名，网络节点数；输入节点到节点的距离（注意弧的方向），求解选择起点与终点，图示最短路，写出起点到各点的最短路径及路长。

4．求最大流：建立新问题，选择Maximal Flow Problem，输入标题名，网络节点数；输入节点到节点的距离（注意弧的方向），求解选择起点与终点，图示最大流，写出最大流量。

网络模型 Network Modeling (NET) 简要说明

该程序（NET）能够求解三大网络问题：最短路问题，最大流问题和最短树问题；网络模型（NET）用网络来描述问题。最短路问题求解网络中从起点到任一节点的最短路线和最短路长；最大流问题求解网络中从源点到终点的最大流路线和最大流量；最短树问题求解连接网络中所有节点的最小树及其总权数。网络模型（NET）能够求解问题的最大规模：最多分支（弧）600个，最多节点300个。

假设有一个从1开始且数字连续的一定数目节点的网络。可以很方便地输入数据、修改数据、保存问题、调出问题。网络数据按分支（弧）输入，对每一个分支（弧）要输入起点、终点以及连接起终点的权数（距离、容量等）。

1、最小树的WinQSB软件应用

在WinQSB软件的网络流模块中，最小部分树的生成采用的是上面的破圈法。本章几乎所有WinQSB软件计算都要调用子程序Network Modeling。下面以例8为示例，说明怎样应用WinQSB软件计算最小部分树。

例8.

V2 V1 4 2 3

V3 V4 V5 3 7 5 6 45 1

4

1 6 2 7 6 8 8 V6 V8

2 3 4 V7

3 7 V9 V3 图6-1

首先，调用WinQSB软件的子程序Network Modeling，建立一个新问题，弹出对话筐，如图6-1所示界面，选择Minimal Spanning Tree，输入问题的文件名Tree1（读者自己可以任意取名），节点数10。

31

图6-2

然后，点击ok，此时弹出一张需要输入数据的表格，对照图6-1输入表5-1所示的数据，两点间的权数只输一次（上三角）。

表 6-1

点击菜单栏Solve and Analyze，输出表5-2所示的最小部分树结果，最小树长为21。点击菜单栏Results→ Graphic Solution，显示最小部分树的图形，见图6-3。

表 6-2

图6-3

32

2、最短路的WinQSB软件应用举例

在WinQSB软件的网络流模块中，最短路问题的求解采用的是上面介绍的标号法。下面我们以例9的设备更新问题为示例，说明怎样应用WinQSB软件计算最短路问题。

例9. 某单位使用一台生产设备，在每年年底初，单位领导都要决策下年度是购买新设备还是继续使用旧设备。

若购置新设备，需要支付一笔购置费；如果继续使用旧的，则要支付一定的维修费用。 一般说来，维修费随设备使用年限的延长而增加。

根据以往的统计资料，已经估算出设备在各年年初的价格和不同使用年限的年维修费用，分别示于下表。

年份 购置费 使用年限 维修费

分析：对于例9的设备更新问题，我们先要把它转化为一个标准的最短路问题的网络模型。用点vi表示“第i年年初购进一台新设备”这种状态，假设一点v6，表示第5年年底，从vi到

1 5 1 11 2 11 2 6 3 8 4 11 5 18 3 12 4 12 5 15 vi?1,,v6各画一条弧，弧(vi,vj)表示在第i年年初购进的设备一直使用到第j年年初（即第

。每条弧的权数为第i年年初购进的设备使用到第j?1年年底所花费的购置费及维j?1年年底）

修费的总和。例如，弧（v1，v3）的权数应为第1年年初购置设备的价格11与从第2年年初到第3年年底2年的维修费用5+6=11之和，应为22；而弧(v1,v6)的权数应为第1年年初购置设备的价格11与从第1年年初到第5年年底5年的维修费用5+6+8+11+18=48之和，应为59；如此等等，就可以计算出弧(vi,vj)的权数cij。这样，设备更新问题就等价于寻求图6-4中从v1到v6的最短路问题。

图6-4

下面我们应用WinQSB软件来求解设备更新问题。首先，调用WinQSB软件的子程序Network Modeling，建立一个新问题，弹出对话框，如图6-5所示界面，选择Shortest Path Problem，输入问题的文件名Equip1（读者自己可以任意取名），节点数6。

33

图 6-5

然后，点击ok，此时弹出一张需要输入数据的表格，对照图6-4输入表5-7所示的数据，两点间的权数只输一次（上三角）。在这里，本问题是一个有向图，是按照弧的方向输入数据的，如果是无向图，每一条边就必须输入两次，把无向边改变为两条方向相反的弧。

表 6-3

点击菜单栏Solve and Analyze后，WinQSB软件系统提示用户选择图的起点和终点，系统默认从第一个点为起点，最后一个点为终点，如图6-6所示，根据本问题，起点为节点1，终点为节点6。

图 6-6

再点击Solve按钮，系统输出v1到v6的最短路路径和最短路路长，见表5-8所示的最短路求解输出结果，最短路路径为v1→v3→v6，最短路路长为53。

34

表6-8

点击菜单栏Results→Graphic Solution，显示最短路的图形，见图6-7。这里，请大家注意的是，WinQSB软件系统只给出本问题的一个求解结果，实际上，为v1→v4→v6也是一条最短路，最短路路长同样为53。这说明，对于例9的设备更新问题，使得总的支付费用最少的设备更新方案有两个：一个方案为第1年年初购置的新设备使用到第2年年底（第3年年初），第3年年初再购置新设备使用到第5年年底（第6年年初）；另一个方案为第1年年初购置的新设备使用到第3年年底（第4年年初），第4年年初再购置新设备使用到第5年年底（第6年年初）。这两个方案使得总的支付为最小，均为53千元。

图 6-7

图

3、最大流的WinQSB软件应用举例

在WinQSB软件的网络流模块中，最大流问题的求解采用的是上面介绍的标号法。下面我们以例10的石油输送问题为示例，说明怎样应用WinQSB软件计算最大流问题。

首先，调用WinQSB软件的子程序Network Modeling，建立一个新问题，弹出对话筐，如图

6-8所示界面，选择Maximal Flow Problem，输入问题的文件名Flow1（读者自己可以任意取 名），节点数7。

图 6-8

35

然后，点击ok，此时弹出一张需要输入数据的表格，对照图输入数据，输入方法与最短路方法相同，求解方法也与最短路方法一样，系统输出如表6-9所示的最大流求解输出结果，最大流流量为10。点击菜单栏Results→Graphic Solution，显示最大流网络图，见图6-9。

表6-9

图6-9

4、旅行推销商问题与中国邮递员问题

（1）旅行推销商问题

一个推销商从n个城市v1,v2,,vn中某一个城市vi(1?i?n)出发，到其它个n?1城市推销

产品，每个城市都必须访问到并且只经过一次最后回到vi，那么如何安排他的旅行路线使总距离最短，这就是旅行推销商问题（Traveling Salesmen Problem），也称作货郎担问题。 设cij为城市vi到城市vj的距离，定义0-1变量

1 从城市vi旅行到城市vj

xij =

0

nn否则

则旅行推销商问题的数学模型可表示成为一个整数规划问题。

minZ???cijxij i?j

i?1j?1 36

.

?xi?1nij?1j?1,2,n,i?(j )

?xj?1nij?1i?1,2,n,i?(j )s.t

xij?xji?1i?j

xij?xjk?xki?2i?j?k

xij?xjk?xki??xpi?n?2i?j??p

xij?0或1i,j?1,2,n ,虽然旅行推销商问题能够运用整数规划、动态规划等方法求解，但是当n较大时求解就会遇到一定的困难，一种可行且有效的方法是求最小的Hamilton回路。

因而，旅行推销商所走的路线是一个由n个城市构成的交通图G的一个Hamilton回路，旅行推销商问题就是寻找一个总距离最小的Hamilton回路。下面我们举一例来说明怎样运用WinQSB软件求解旅行推销商问题。

例11. 某电动汽车公司与某旅游景区合作，打算在旅游景区内开通无污染无噪音的“绿色交通”路线。图6-11是旅游景区各景点的分布图，其中C、F之间是两条单向通道，边上的数字为汽车通过两点间的正常时间（分钟）。电动汽车公司应该如何设计一条路线，使汽车通过每一处景点一次且总时间最少？

图6-11

解：图6-11中存在Hamilton回路，这是因为在图6-11中，我们可以找到

d(A)?d(D)?6?n?，由定理55.6可得。将上图表示成距离矩阵，如表6-11，两点间没有边

连接的时间为?。

表 6-11

A B C D E F

A ? 16 18 40 ? ? B 16 ? 26 ? ? 42 C 18 26 22 15 30 37

D 40 ? 22 ? 30 ? E ? ? 15 30 ? 28 F ? 42 25 ? 28 ? 调用WinQSB软件的子程序Network Modeling，建立一个新问题，弹出对话筐，如图6-12所示界面，选择Traveling Salesmen Problem，目标函数选择Minimization，输入问题的文件名Travel1（读者自己可以任意取名），输入节点数6。然后，点击ok，此时弹出一张需要输入数据的表格，对照表6-11输入数据，输入数据时应注意弧的方向，无向边对称输入数据，有向弧按弧的方向输入，重命名网络节点后得到表6-12。

图 6-12 表6-12

点击菜单栏Solve and Analyze→Solve the Problem后系统提示用户选择求解方法，对于较大的旅行推销商问题目前还没有有效的解法，系统提供了3种近似解法和1种分支定界法。分支定界法能得到最优解，对于大型问题求解时间可能达数小时。3种近似方法为最近城市法（nearest neighbor heuristic）、逐步包围法（cheapest insertion heuristic）、两两交换改进法（two-way exchange improvement heuristic），不同的方法得到的结果可能不一样，原则是取最短回路的解。 对于本问题，用最近城市法无解、用逐步包围法回路长度为168，用两两交换改进法与分支定界法的结果一样，为156，可作为求解的结果。点击Results→Graphic Solution得到旅行线路图6-13。

图 6-12

38

实验6作业：

（1）宝马公司的汽车配件供应问题。

宝马公司需要做出一个方案，使得下个月从总厂（在德国的斯图加特）运送到洛杉矶的配件

尽可能多，以满足当地忽然增加的需求。当然总厂的配件有足够多供应量。下图是整个可用的配送网络。图中弧上数值是线路容量限制。

鹿特丹 RO 斯图加特 ST 40 50 70 波尔多 BO 50 里斯本 LI 30 新奥尔良 图6-13 宝马公司总厂到斯图加特的配送网络 NO 60 40 70 纽约 NY 80 洛杉矶 LA

（2）宝马公司案例的继续讨论：多个源点和收点情形。

事实上，除了可以从总厂向洛杉矶提供配件之外，还可以从另外一个厂（在德国的柏林）向洛杉矶发给配件。而且讨论认为，只是最大限度满足洛杉矶的需求是不太恰当的，应该保证运送到洛杉矶和西雅图两地配件总量最大。下图（图6.3）是这个扩充之后的配送网络。

60 柏林 BE 20 斯图加特 50 70 ST 40 汉堡 HA 30 40 波士顿 BN 20 10 鹿特丹 RO 波尔多 BO 50 里斯本 NO 60 NY 40 纽约 70 40 80 洛杉矶 LA 西雅图 SE 30 新奥尔良 LI 图6-14 宝马公司的扩展配送网络 提示：其实这个扩充后的网络，可以变化成上面只有一个源和收点的问题。我们可以想像在两个源之外有个总源，柏林和斯图加特的流都是从这个总源来的，只是运输线路容量无限大；同样两个收点之外可以想象有一个总的收点，到西雅图和洛杉矶的配件最后都要送到这个总收点去，同样地，到这个总收点的虚拟线路的容量无限。

（3）某农场发生火灾，消防队接到火情报告后要奔赴农场灭火，路网如图（图6-15）所示，

39

图中边上的数值为该边的路程（公里）。问题：如何走才路程最短？

6 F 8 A D 4 3 3 1 4 3 出发地 6 6 S B G 6 5 5 2 E 2 4 7

4 H C 3 图6-15 消防队到农场的路网图

（4）案例分析： 活动成本最小。

目标地 T 莎拉刚刚高中毕业。在毕业典礼上，她的父母给了她21,000美元的汽车基金帮助她购买并保养一辆使用了+三年的二手车，以供她上大学用。由于开车费用和保养费用随着汽车的老化而飞速上涨，所以莎拉的父母告诉她在接下来的三个夏天里，她可以一次或者几次折价将她的汽车置换成其他使用了三年的二手车。他们还告诉莎拉，在四年后，他们会送给她一辆新车作为大学毕业的礼物。所以莎拉到时肯定会将旧车折价卖出。下表（表6-13）给出每一个时期莎拉购买一辆使用了三年的二手车的相关数据。

表6-13 莎拉每一个时期购买使用一辆使用了三年的二手车的费用数据

购买价格 12000 拥有年份的开车和保养费用 第1年 2000 第2年 3000 第3年 4500 第4年 6500 第1年 8500 最后一年卖出的价值 第2年 6500 第3年 4500 第4年 3000 问题：在接下来的三个夏天里，什么时候莎拉应该折价卖掉汽车（若必要的话），可以使得她在大学四年里买车、开车、保养车的总费用最小？

（5）默登公司的管理层决定铺设最先进的光纤网络，为它的主要中心之间提供高速通信。图6.4中的节点显示了该公司主要中心的分布图。虚线是铺设光纤的可能位置。虚线旁边的数字表示了如果选择在这个位置铺设光纤的需要花费的成本。为了节约成本，不需要每两个中心都有线直接联系起来。现在的问题是要确定需要铺设哪些线路，使得提供给每两个中心之间的高速通信的总成本最低。

7 B 5 G

E 2 2 4

5 C 1 7

A 3 4 1

图 6-16 默登公司的中心连接示意图

40

D 4 F

第三部分 Spreadsheet建模与求解

Spreadsheet方法是近年来美国各大学乃至企业推广的一种管理科学教学与应用的有效方法。Spreadsheet提供了一种描述问题、处理数据、建立模型与求解的有效工具，使得管理科学的理论和方法易于被理解与掌握，大大推动了管理科学方法与技术在企业中的实际应用。

Spreadsheet是在Excel或者Lotus 1-2-3等其他背景下将所需求解的问题进行描述与展开，然后建立数学模型，并使用Excel（或者Lotus 1-2-3）的命令和功能进行预测、决策、模拟、优化等运算与分析。Excel（或者Lotus 1-2-3）的工作表用作描述问题与建立模型时，就被称做Spreadsheet。

本实验指导书旨在帮助学生在运筹学课程中，学习如何运用Excel对复杂的实际系统进行描述与建模，并用计算机求解。由于避免了大量繁琐的数学公式，使得运筹学的理论方法简明直观，容易理解与应用，因此，掌握它有利于运筹学理论的学习，也特别有利于那些注重应用的企业管理人员的学习，为企业决策人员与管理人员掌握与应用运筹学理论提供一个有益的工具。

第一章 Spreadsheet建模

第一节 模型的概念与建立

一、 模型的概念

用管理科学方法求解问题，一般需要建立模型，用定量化方法来描述与分析所研究的问题。模型是对现实系统或情景的一种描述，同时又是对现实系统的一种抽象。

二、建立模型的一般步骤

① 定义问题。定义问题包括确定系统的目标和边界。 ② 调查研究，收集数据。 ③ 建立数学模型。

④ 模型的验证。为检验模型的有效性，需在使用前进行模型的验证。一般可用模型预测近

期变量值，并将该预测值与实际值相比较，以确定模型的有效性。 ⑤ 选择可行方案。

⑥ 模型运行求解，提出推荐的方案。 ⑦ 履行所推荐的方案，并进行评价。

三、模型的特点

① 模型通常是现实的抽象与简化；

② 模型是由与分析问题有关的主要要素构成，并表明这些主要要素之间的关系； ⑧ 模型的精细程度与所要决策问题的需要有关。

第二节 Spreadsheet方法的应用

一、建模与求解过程

下面用一个盈亏平衡分析的例子说明Excel求解的应用。盈亏平衡分析是通过分析产品产量、成本与盈利之间的关系，找出各投资方案在产量、产品价格、单位产品成本等方面的临界值，

41

以判断投资方案在各种不确定因素作用下的盈亏状况，从而为决策提供依据。 例： 盈亏平衡分析

华丽床垫厂生产一种床垫，年固定费用为90000元，生产一个床垫的可变费用为50元，床垫的销售单价为100元。假定市场条件不变，产品价格稳定，所有的产品均能被销售。确定该产品在盈亏平衡点的产量。如果该工厂生产2400个床垫，盈亏情况如何?

解：假设床垫产量用X来表示。

则可建立如下模型：

(1)成本－产量模型

总成本为： C(X)＝90000+50X

上式中，C为生产X个床垫的总成本，它是产量X的函数。

(2)收益－销售量模型

收益为： R(X)＝1OOX

上式中，X为床垫的销售量(在本例中，床垫的销售量等于床垫的生产量)； R(X)为销售X个床垫的总收益，它是产量X的函数。 (3)利润－产量模型

总利润为： P(X)＝R(X)一C(X) ＝1OOX一(90000＋50X) ＝－90000＋50X

上式中，P(X)为总利润，它是X的函数。 (4)盈亏平衡分析

当总利润为零时，达到盈亏平衡。 即有：

P(X)＝一90000+50X＝0

计算可得这时的产量为：

X=1800(个)

(5)若生产2400个床垫，则其利润为：

P(2400)＝-90000+50X2400＝30000(元)。

下面以Microsoft Excel为背景，用Spreadsheet方法描述和求解该例。

打开Excel后，出现工作表。该工作表用作描述问题与建立模型时，称为Spreadsheet。在Spreadsheet上进行盈亏分析的基本步骤如下：

首先在Spreadsheet中进行问题描述。

用地址为B4、B5、B6的单元格分别表示固定费用、单位产品可变费用和产品单价，在这些单元格中分别输入已知数据，见下图2—1。

42

图2—1 已知数据的输入

然后在Spreadsheet中建立模型。可在单元格A9处键入“模型”两个字，以表示以下为模型。用单元格B10表示产品产量(相当于上述X)，它是一个有待于确定的决策变量。由于总成本、总收益与总利润均与该决策变量有关，所以可将单元格B10用一个框围起来以示该决策变量的重要性。

单元格B12、B14、B16分别表示总成本、总收益与总利润。总成本(单元格B12)等于年固定费用与年可变费用之和，其中年可变费用等于单位产品可变费用与产品的产量之积，所以在单元格B12中输入下述公式：

＝B4+B5*Bl0 即 90000＋50X

总收益(单元格B14)等于产品价格与产品产量之积，在单元格B14中输入下述公式： ＝B6*Bl0 即 100X

总利润(单元格B16)等于总收益与总成本之差，在单元格B16中输入公式： ＝B14-B12 即 （90000＋50X）－100X

运用上述模型即可计算出不同产品产量下的盈亏情况。

例如，当产品的产量为2400个时，可在单元格B10中输入2400，即得到此时的总成本、总收益与总利润分别为210000元，240000元与30000元，如上图所示。

最后，我们来确定盈亏均衡点：

盈亏均衡点是总成本等于总收益的点，或总利润等于零的点。前面已经算出，当产量为2400个时，总利润为30000元，所以该点不是盈亏均衡点。可在单元格B10中继续输入其他产量值进行试算，直到总利润为零。

下面介绍两种使用Excel中的命令迅速求出盈亏均衡点产量的方法，第一种方法使用数据表命令，第二种方法使用单变量求解命令。 方法一：数据表命令方法

Excel中的数据表命令可用来计算不同输入下的输出值。

在本例中，可用数据表命令计算不同产量下的盈利值或亏损值，其中，盈利值(或亏损值)为零时所对应的那一个产量，即为盈亏均衡点下的产量。

43

用数据表命令求盈亏点下产量的步骤如下：

第一步：确定输入的决策变量值(即床垫的产量)的范围与计算步长。

前面已计算得到，当床垫的产量为2400个时，总利润为正值，即盈利；在上表的模型中，若在单元格B10中试输入1400，得到总利润为负值，即亏损。

因此，在产量在l400与2400之间，必有一个值使得总利润为零，这个值即为盈亏均衡点的产量。

所以，可将输入范围定为（1400，2400），假设计算步长为200。

第二步：在单元格A22：A27中分别输入从1400至2400、步长为200的产量值。 第三步：在单元格B21中输入计算总利润的公式，即：＝B16，如图2—2所示。

图2—2 数据表计算

第四步：用Excel中的数据表命令计算不同产量下的利润值： ① 用鼠标选择单元格A21：B27的区域；

② 在Excel工作表的菜单栏中，选择“数据(Data)”，如图2—2所示； ③ 选择“模拟运算表”（table）；

④ 出现模拟运算表对话框，在“输入引用列的单元格”一栏中输入“B10”，B10是表示产

量的单元格，这表示模拟运算表要计算的不同产量下的利润。

⑤ 选择“确定”。

这时，表内将出现不同产量所对应的利润值。

从表中数据可见，当产量为1800个时，总利润为零，即盈亏均衡点的产量为1800个。

方法二：单变量求解命令方法

用excel的单变量求解命令可以直接求出利润为零所对应的产量。 第一步：在Excel的菜单栏选择“工具（tool）”；

44

图2—3 单变量求解 第二步：选择“单变量求解(Goal Seek)”；

第三步：这时，出现“单变量求解”对话框。在“目标单元格”一栏中输入地址“B16”(总利润值)，在“目标值”一栏中输入“0”(表示总利润为零)，在“可变单元格”一栏中输入地址“B10”(表示产量)，如图2—4所示。

该对话框的输入表明，下面要寻找的是当总利润为零时对应的产量值，选择“确定”。

图2—4 单变量求解

这时，出现“单变量求解状态”表，如图2—5所示。它表示已经求得了一个解,选择“确定”。这时，在单元格B10中即得到盈亏均衡点的产品产量，为1800个。

图2—5 单变量求解状态

第二章 应用Spreadsheet方法建立运筹学模型与求解

本章以举例的方式介绍用Spreadsheet方法如何建立运筹学模型，并进一步求出最优解。

第一节 线性规划问题建模和求解

例 雅致家具厂生产计划优化问题

雅致家具厂生产4种小型家具，由于该四种家具具有不同的大小、形状、重量和风格，所以它们所需要的主要原料（木材和玻璃）、制作时间、最大销售量与利润均不相同。该厂每天可提

45

供的木材、玻璃和工人劳动时间分别为600单位、1000单位与400小时，详细的数据资料见下表。问：

（1）应如何安排这四种家具的日产量，使得该厂的日利润最大？ （2）家具厂是否愿意出10元的加班费，让某工人加班1小时？

（3）如果可提供的工人劳动时间变为398小时，该厂的日利润有何变化？ （4）该厂应优先考虑购买何种资源？

（5）若因市场变化，第一种家具的单位利润从60元下降到55元，问该厂的生产计划及日利润将如何变化？

表2—1 雅致家具厂基本数据 家 具 类 型 劳 动 时 间 1 2 3 4 可提供量 2 1 3 2 400小时 木 材 4 2 1 2 600单位 玻 璃 6 2 1 2 单位产品利润 最大销售量 （元/件） 60 20 40 30 （件） 100 200 50 100 （小时/件） （单位/件） （单位/件） 1000单位 解：依题意，设置四种家具的日产量分别为决策变量x1,x2,x3,x4,目标要求是日利润最大化，约束条件为三种资源的供应量限制和产品销售量限制。 据此，列出下面的线性规划模型：

MaxZ?60x1?20x2?40x3?30x4①

（木材约束）?4x1?2x2?x3?2x4?600②?③?6x1?2x2?x3?2x4?1000（玻璃约束）?2x1?1x2?3x3?2x4?400（劳动时间约束）④?⑤（家具1需求量约束）?x?100s.t.?1⑥（家具2需求量约束）?x2?200⑦?x3?50（家具3需求量约束）?⑧

（家具4需求量约束）?x4?100?x,x,x,x?0（非负约束）?1234其中X1,X2,X3,X4分别为四种家具的日产量。

下面介绍用Excel中的“规划求解”功能建模与求解。 第一步 在Excel中描述问题、建立模型，如图2—6所示。

46

图2—6 输入数据建立模型

第二步 在“工具”菜单中选择“规划求解”。

图2—7 规划求解

第三步 在“规划求解参数”对话框进行选择如图2—8所示。

图2—8 规划求解参数

第四步 点击“选项”按钮，弹出“规划求解选项”对话框。

图2—9 规划求解选项

第五步 选择“采用线性模型”和“假定非负”，单击“确定”，返回如图2—10所示。单击“求解”，即可求解此题。

47

图2—10 线性规划求解

最后结果如图2—11所示。

图2—11 求解的结果 与此结果对应的敏感性报告如图2—12所示。

图2—12 敏感性报告

48

说明：（1）可变单元格表中，终值对应决策变量的最优解；递减成本指目标函数中决策变量的系数必须改进多少才能得到该决策变量的正数解，改进对最大值为增加，对最小值为减少。（2）允许的增量（或减量）指在保证最优解不变的前提下，目标函数系数的允许变化值。（3）在约束表中，终值是指约束的实际用量；影子价格式指约束条件右边增加（或减少）一个单位，目标值增加（或减少）的数值；这里的允许的增量（或减量）是指在影子价格保持不变的前提下，终值的变化范围。

根据模型运行结果可作出如下分析：

(1)由模型的解可知，雅致家具厂四种家具的最优日产量分别为100件、80件、40件和0件，这时该厂的日利润最大，为9200元。

本问题的敏感性报告如上页表所示。

由上述敏感性报告可进行灵敏度分析，并回答题目中的问题(2)一(5)。

(2)由敏感性报告可知，劳动时间的影子价格为12元，即在劳动时间的增量不超过25小时的条件下，每增加l小时劳动时间，该厂的利润(目标值)将增加12元。

因此，付给某工人10元以增加l小时劳动时间是值得的，可多获利为：

12—10＝2(元)。

(3)当可提供的劳动时间从400小时减少为398小时时，该减少量在允许的减量(100小时)内，所以劳动时间的影子价格不变，仍为12元。

因此，该厂的利润变为：

9200+12X(398—400)＝9 176(元)。

(4)由敏感性报告可见，劳动时间与木材这两种资源的使用量等于可提供量，所以它们的约束条件为“紧”的，即无余量的；而玻璃的使用量为800，可提供量为1000，所以玻璃的约束条件是“非紧”的，即有余量的。

因此，应优先考虑购买劳动时间与木材这两种资源。

(5)由敏感性报告可知，家具1的目标系数(即单位利润)允许的减量为20，即当家具1的单位利润减少量不超过20元时，最优解不变。因此，若家具1的单位利润从60元下降到55元，下降量为5元，该下降量在允许的减量范围内，这时，最优解不变。

因此，四种家具的最优日产量仍分别为100件、80件、40件和0件。 最优值变为：

9200+(55－60)X100＝8 700(元)。

第二节 运输问题

例 海华设备厂均衡运输问题

海华设备厂下设三个位于不同地点的分厂A，B，C，该三个分厂生产同一种设备，设每月的生产能力分别为20台、30台和40台。海华设备厂有四个固定用户，该四个用户下月的设备需求量分别为20台、15台、23台和32台。设各分厂的生产成本相同，从各分厂至各用户的单位设备运输成本如下表所示，而且各分厂本月末的设备库存量为零。问该厂应如何安排下月的生产与运输，才能在满足四个用户需求的前提下使总运输成本最低。

表2—3 海华设备厂运输成本表

分厂—名称 分厂A 分厂B 分厂C 运输成本(元／台) 用户l 用户2 70 80 80 40 100 70 15 用户3 80 110 130 23 用户4 60 50 40 32 月生产能力(吨) 20 30 40 下月设备需求量(吨) 20

49

解：本题可用图2—16所示的网络图描述。

网络图左边的节点表示三个分厂，右边的节点表示四个用户，左、右节点间的连线表示从左边某分厂生产的设备运输到右边某用户，线段上的数字表示单位设备的运输成本。网络图最左边的数字分别为三个分厂的生产能力，最右边的四个数字分别为四个用户的需求量。

总供应量：20十30十40＝90(台)； 总需求量：20十15十23＋32＝90(台)。

即所有供应点的供应量之和等于所有需求点的需求量之和。所以本问题是供需均衡的运输问题。这时，所有供应点的供应量全部供应完毕，而所有需求点的需求量全部满足。

据题意，本问题的决策变量是下月各分厂为各用户生产与运输的设备数量。 可设分厂A下月为四个用户生产和运输的设备数量分别为：

A1,A2,A3,A4(台)；

图2—16 网络图

分厂B下月为四个用户生产和运输的设备数量分别为:B1，B2，B3，B4(台)； 分厂C下月为四个用户生产和运输的设备数量分别为:C1，C2，C3，C4(台)。 本问题的目标函数是总运输成本最小化。 总运输成本的计算公式如下：

总运输成本＝∑(各分厂至各用户的设备运输成本)X(各分厂至各用户的运输量) 因此，该问题的目标函数为：

o.b min 70Al+40A2+80A3+60A4+70Bl+100B2+110B3+50B4+80C1+70C2+130C3+40C4 本问题的约束条件有两个部分，第一部分是需求约束，即各用户从各分厂收到的设备总数不得少于它们的需求量：

A1+Bl+C1＝20 (用户1从三个分厂收到的设备总数应等于其需求量) A2+B2+C2＝15 (用户2从三个分厂收到的设备总数应等于其需求量) A3+B3+C3＝23 (用户3从三个分厂收到的设备总数应等于其需求量) A4+B4+C4＝32 (用户4从三个分厂收到的设备总数应等于其需求量) 第二部分是生产能力约束，即各分厂生产和运输的设备总数不得超过其生产能力：

A1+A2+A3+A4＝20 (分厂A下月生产与运输的设备总数应等于其月生产能力) B1+B2+B3+B4＝30 (分厂B下月生产与运输的设备总数应等于其月生产能力) C1+C2+C3+C4＝40 (分厂C下月生产与运输的设备总数应等于其月生产能力)

最后还有非负约束，即：

A1，A2，A3，A4，B1，B2，B3，B4，C1，C2，C3，C4≥0 (非负约束)

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

o.b min 70Al+40A2+80A3+60A4+70Bl+100B2+

110B3+50B4+80C1+70C2+130C3+40C4

50

本文来源：https://www.bwwdw.com/article/9hjo.html