管理运筹学教程

管理运筹学教程

徐军委编著

2018-10





管理运筹学教程

徐军委编著

企业管理出版社



图书在版编目（CIP）数据

管理运筹学教程/徐军委编著.--北京：企业管理出版社，2018.10

ISBN978-7-5164-1785-0

Ⅰ.①管…Ⅱ.①徐…Ⅲ.①管理学-运筹学-教材Ⅳ.①C931.1

中国版本图书馆CIP数据核字（2018）第216153号

书名：管理运筹学教程

作者：徐军委

责任编辑：张平田天

书号：ISBN978-7-5164-1785-0

出版发行：企业管理出版社

地址：北京市海淀区紫竹院南路17号邮编：100048

网址：http：//

电话：编辑部（010）68701638发行部（010）68701816

电子信箱：qyglcbs@

印刷：北京虎彩文化传播有限公司

经销：新华书店

规格：170毫米×240毫米16开本14.25印张198千字

版次：2018年10月第1版2018年10月第1次印刷

定价：58.00元

版权所有翻印必究·印装有误负责调换



前言

运筹学是一门定量优化的决策科学，是现代管理学的一门重要专业基础课程。它是

20世纪30年代初发展起来的应用性非常强的一门学科。运筹学是应用数学和形式

科学的跨领域研究，利用统计学、数学模型和一些经典算法等方法，帮助人们解决

那些可以用定量方法和有关理论来处理的决策问题，其在社会生活的许多方面都有

重要的应用。

管理运筹学则是利用数学、系统科学、计算机理论、优化原理等学科和理论的最新

成果，研究人们生产生活中遇到的各种量化问题，以便使有限的人、财、物等资源

得到合理运用，取得最大化的收益。管理运筹学内容较丰富，针对管理运筹学自身

的特点，本书只涉及最常见的一些模型和理论，而且更多侧重理论的应用，体现在

以下几点：

一是教学重点的转变。

针对管理运筹学的教学目的和培养目标，本书更多侧重于应用研究。本书考虑到M

ATLAB、SAS、Mathematica、SPSS、Lindo/Lingo、GAMS等工具软件的复杂性，

采用最常见的Excel平台进行求解，即使数学基础薄弱也能很快学会求解过程，但

本书应用Excel工具求解的模型主要为线性规划模型。

二是针对不同读者的应用设置。

对于经济管理类的本科生，本书只要求其理解运筹学各个模块的求解思路，并在此

基础上学会运用Excel去求解较为简单的数学模型；对于有良好数学基础的专业人

士，建议在学会运用Excel求解的基础上，灵活地设计Excel求解模块，以便遇到相

似的问题时，可以在最短时间内得到求解结果。

三是难易程度适中。

本书在编写的过程中，编者特意选择所在高校的两个学生小组进行应用实验，期望

了解数学基础薄弱的学生如何理解运筹学模块和应用过程，并征求他们对于本书主

要章节的意见和建议。结果发现，对于线性规划、运输问题、图论等核心模块，学

生的理解基本到位。因此，本书难易程度适中，适合基础较为薄弱的学生学习。

另外，读者学习本书应该着重培养自己三个方面的能力：运用所学的运筹学模型解

决实际问题的能力、掌握Excel求解管理运筹学问题的基本步骤、学会理解运筹学

模型求解结果所代表的经济和管理意义。

本书在编写过程中，得到了中国劳动关系学院经济管理系两个学生小组的支持和帮

助，在此对俞澜天、李悦、金豪、陈艳、刘鑫、黄珑、郑寒翠、黄初阳、何琎琎、

贾士谊等同学表示感谢。

由于编者水平有限，书中难免存在不足之处，恳请读者不吝赐教。

编者

2018年7月



目录

前言

第一章概述

1.1运筹学简史

1.2运筹学的性质与特点

1.3管理运筹学的主要内容及在工商管理中的应用

1.4管理运筹学的工作步骤

1.5管理运筹学的模型及建模思路

1.6管理运筹学的计算工具

第二章线性规划及其应用

2.1线性规划问题及数学模型

2.1.1线性规划问题的提出

2.1.2线性规划数学模型

2.2线性规划的图解法

2.3单纯形法

2.4案例解析

第三章运输问题

3.1运输问题及数学模型

3.2表上作业法

3.3案例解析

第四章整数规划

4.1整数规划数学模型

4.2整数规划典型解法

4.3整数规划应用案例

第五章动态规划

5.1多阶段决策问题

5.2动态规划的基本概念和基本方程

5.2.1动态规划的基本概念

5.2.2动态规划的基本思想与基本方程

5.3动态规划应用举例

第六章图论和网络模型

6.1图论概述

6.2图论实例

第七章排队论

7.1排队论基本概念

7.1.1排队系统及其基本结构

7.1.2排队系统的三个基本特征

7.1.3排队论的常用术语

7.1.4输入与输出

7.2简单模型（M/M/s模型）

7.2.1M/M/s/系统模型

7.2.2M/M/s/r系统模型

7.2.3M/M/s/m/m系统模型

7.3排队论其他模型选介

7.3.1M/G/1系统模型

7.3.2优化设计模型

第八章存储论

8.1存储论基本概念

8.2确定性存储系统的基本模型

8.3存储论其他模型选介

第九章对策论

9.1对策的概念和分类

9.2矩阵对策的基本定理

9.3矩阵对策的一般解法

9.4其他类型对策简介

第十章目标规划

10.1问题概述

10.2目标规划问题实例

10.3目标规划的图解法

参考文献



第一章概述

运筹学是现代管理学一门重要的专业基础课程，它是20世纪30年代初发展起来的

应用性非常强的一门新兴学科。运筹学是应用数学和形式科学的跨领域研究，利用

统计学、数学模型和算法等方法，帮助人们解决那些可以用定量方法和有关理论来

处理的决策问题。在工业、商业、农业、交通运输、社会管理等领域都有重要的应

用。

本章首先介绍运筹学的历史，其性质与特点以及运筹学研究的主要内容。然后从运

筹学解决问题的角度，总结出运筹学的工作步骤，对运筹学模型的建立与解决进行

重点讨论。最后结合运筹学在管理实践中的应用，浅谈运筹学的发展趋势，使初学

者对管理运筹学概念和方法有初步的认识。

1.1运筹学简史

运筹学产生于第二次世界大战期间，1937年英国部分科学家被邀请去帮助皇家空

军研究雷达的部署和运作问题，目的在于最大限度地发挥数量有限的雷达效用，以

应对德军对英国本土的空袭。1938年波德塞（Bawdsey）雷达站的负责人罗伊（R

owe）提出了优化防空作战系统运行的问题，并用“Operational

Research”（OR）一词作为对这一方面研究的描述，这就是今天仍将运筹学称为OR

的历史由来。1939年从事此方面问题研究的科学家被召集到英国皇家空军指挥总

部，成立了一个由布莱开特（Blacket）领导的军事科技攻关小组；由于其成员学

科性质的多样性，这一最早成立的军事科技攻关小组被戏称为“布莱开特马戏团”。

由于“布莱开特马戏团”的活动是第一次有组织的系统的运筹学活动，所以后人将该

小组的成立作为运筹学产生的标志。此后，OR小组的活动范围不断扩大，从最初

的仅限于空军，逐步扩展到海军和陆军；研究内容也从对军事战术性问题的研究，

逐步扩展到对军事战略性问题的研究。第二次世界大战期间，OR小组成功地解决

了许多重要作战问题，为运筹学的快速发展奠定了基础。

第二次世界大战结束后，除军事方面的应用研究以外，由于组织内与日俱增的复杂

性和专门化所产生的问题，使人们认识到这些问题基本上与战争中曾面临的问题类

似，只是具有不同的现实环境而已，运筹学就这样在工商企业和其他部门中得到了

广泛的应用，形成了比较完备的理论体系，如规划论、排队论、存储论、对策论等

，相继在工业、农业、经济和社会问题等各领域都有应用。1947年，由丹捷格（G

eorge

Dantzig）提出的求解线性规划问题的单纯形法，开启了运筹学方法论快速发展的

历程。电子计算机技术的迅猛发展和广泛应用，使运用运筹学方法解决实际问题变

得可行，又大大促进了运筹学的发展。截至目前，世界上不少国家已成立了致力于

该领域及相关活动的专门学会，美国于1952年成立了运筹学会，后来世界上许多

国家也都逐步成立了运筹学会。1959年，在英、美、法三国的运筹学会基础上发

起成立了国际运筹学联合会（InternationalFederationofOperationsResearch

Societies，IFORS），许多国家或地区的学会已加入该会。此外还有一些地区性组

织，如欧洲运筹学协会（EURO）成立于1975年，亚太运筹学协会（APORS）成立

于1985年。

我国运用运筹学思想解决现实问题的历史可追溯到战国时期，田忌赛马的故事就深

刻地说明了运筹学思想的重要性。但我国系统研究运筹学却起步较晚，20世纪50

年代中期，钱学森、许国志等教授将运筹学由西方引入我国，并结合我国的特点在

国内推广应用。在经济数学方面，特别是投入产出表的研究和应用开展较早，在质

量控制（后改为质量管理）的应用也有特色。在此期间，以华罗庚教授为首的一大

批数学家加入运筹学的研究队伍，使运筹数学的很多分支很快跟上当时的国际水平

。1980年，中国数学会决定成立运筹学分会，并于1982年5月正式加入国际运筹学

联合会。

1.2运筹学的性质与特点

运筹学是一门综合性应用型学科，是在20世纪形成的一门科学。当人们把战时的

运筹研究取得成功的经验在和平时期加以推广应用时，面临着一个广阔的研究领域

。在这一领域中，对于运筹学主要研究和解决什么问题有许多争论，至今仍没有形

成定论，实际上形成了一个在争论中发展运筹学的局面。在这些争论中，至少可以

看出以下特点：

（1）科学性。运筹学原理中引进了大量的数学研究方法，将数学作为一种重要的

解决问题的工具，寻求各种问题的最优方案，所以是一门优化科学，将实际问题通

过抽象的方式，抓住问题的主要矛盾，建立相应的数学模型，从而求解这些问题。

随着生产与管理的规模日益庞大，其间的数量关系也就更加复杂，利用其间的数量

关系来研究这些问题，引进数学研究方法，使得运筹学具有科学性这一大特点。

（2）系统性。运筹学研究问题是从系统的观点出发，研究全局性的问题，研究综

合优化的规律，它是系统工程的主要理论基础。在现实生活中，基于个体利益和思

维习惯，很多时候我们会将许多问题人为分解，或者忽视系统效益，这显然要付出

巨大的代价，全然失去对“整体”的连属感，也不了解自身行动所带来的一连串后果

。运筹学研究的基点就是系统优化的思想。可以说，系统性是运筹学研究和应用的

一个很重要的特征。

（3）应用性。在运筹学术界，有许多人强调运筹学的实用性和对研究结果的执行

效果，并把执行效果看作运筹工作中的一个很重要的组成部分。在运筹学的应用方

面，我们首先会关注实际问题，接着是数学模型的建立，然后到模型求解。得到的

结果也会反馈到实际问题中。一个问题的求解应该是一个闭环管理过程，从现象到

本质，再回归到现象才是一个比较合理的方式。

（4）跨学科性。早期运筹学小组都是由不同领域的专家组成的。他们往往集体研

究问题，并综合运用多种学科的知识来解决实际问题。例如，第二次世界大战时英

国空军成立防空运筹小组，其成员包括数学家、物理学家、天文学家、生物学家和

军事专家等，旨在探讨如何抵御敌人的空袭和潜艇。这种组织形式和组织特点在第

二次世界大战以后应用于经济管理领域，综合运用经济学、管理学、数学、管理学

、物理学、化学等学科的科学方法开展工作。从运筹学的发展来看，这种跨学科的

特点一直伴随其始终，并关乎运筹学应用的成败及应用的广泛程度。

（5）理论和应用相互促进，相得益彰。运筹学的各个分支学科，都是由于实际问

题的需要或以一定的实际问题为背景逐渐发展而来的。初期一些传统学科方向的专

家对运筹学做出了贡献，随后新的人才逐渐涌现，新的理论相继出现，这往往就开

拓出新的领域，如线性规划问题就是在研究生产的组织和计划中出现的。1939年

著名数理经济学者康托洛维奇发表了《生产组织和计划中的数学方法》，堪称运筹

学的先驱名著之一，后来George

Dantzig等人重新进行独立研究使其形成了一套较完整的理论和方法，进而又开拓

了线性规划的应用范围，并相继出现了一批职业的线性规划者。由于他们从事了大

量的实践活动，反过来又进一步促进了线性规划方法论的进一步发展，从而又出现

了椭圆法、内点法等新的求解线性规划的方法。目前运筹学家们仍在孜孜不倦地研

究新技术、新方法，使运筹学这门年轻的学科不断地向前发展。

1.3管理运筹学的主要内容及在工商管理中的应用

运筹学的主要内容一般包括线性规划、非线性规划、整数规划、动态规划、多目标

规划、随机规划、网络分析、排队论、对策论、决策论、存储论、可靠性理论、模

型论、投入产出分析等。它们中的每一部分都有丰富的内容，都可以独立成册。上

述的前六个部分统称为规划论，它们主要是解决两个方面的问题：一个方面的问题

是对于给定的人力、物力和财力，怎样才能发挥其最大效益；另一方面的问题就是

对于给定的任务，怎样才能用最少的人力、物力和财力去完成它。

网络分析主要是研究解决生产组织、计划管理中诸如最短路径问题、最小连接问题

、最小费用流问题以及最优分派问题等。特别是在计划和安排大型的复杂工程时，

网络技术是重要的工具。

人们在生产和消费过程中，都必须储备一定数量的原材料、半成品或商品。存储少

了会因为停工待料或失去销售机会而遭受损失，存储多了又会造成资金积压、原材

料及商品的损耗。因此，如何确定合理的存储量、购货批量和购货周期至关重要，

这便是存储论要解决的问题。

投入产出分析是通过研究多个部门的投入产出所必须遵守的综合平衡原则来制订各

个部门的发展计划，借以从宏观上控制、调整国民经济，以求得国民经济协调合理

地发展。

其中在工商管理领域里的应用应侧重以下几个方面：

（1）市场销售。在广告预算和媒体的选择、竞争性定价、新产品开发、销售计划

的制订等方面。

（2）生产计划。在总体计划方面主要是从总体确定生产、储存和劳动力的配合等

计划以适应变动的需求计划，主要用线性规划法等。此外，还可用于生产作业计划

、日程表的编排，还有在合理下料、配料问题、物料管理等方面的应用。

（3）库存管理。存货模型将库存理论与计算器的物料管理信息系统相结合，主要

应用于多种物料库存量的管理，确定某些设备的能力或容量，如工厂的库存、停车

场的大小、新增发电设备容量大小、计算机的主存储器容量、合理的水库容量等。

（4）运输问题。这里涉及空运、水运、公路运输、铁路运输、管道运输和厂内运

输等，包括班次调度计划及人员服务时间安排等问题。

（5）财务和会计。这里涉及预算、贷款、成本分析、定价、投资、证券管理、现

金管理等。用得较多的方法是统计分析、数学规划、决策分析。此外，还有盈亏点

分析法、价值分析法等。

（6）人事管理。这里涉及六方面，包括：人员的获得和需求估计；人才的开发，

即进行教育和训练；人员的分配，主要是各种指派问题；各类人员的合理利用问题

；人才的评价，其中有如何测定一个人对组织、社会的贡献；薪资和津贴的确定等

。

1.4管理运筹学的工作步骤

运筹学在解决大量实际问题过程中形成了以下几点工作步骤。

（1）提出和形成问题。即要弄清问题的目标、可能的约束、问题的可控变量以及

有关参数，搜集有关资料。

（2）建立模型。即把问题中可控变量、参数和目标与约束之间的关系用一定的模

型表示出来。

（3）求解。用各种手段（主要是数学方法，也可用其他方法）对模型求解。解可

以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要求可由决

策者提出。

（4）解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反映现实问

题。

（5）解的控制。通过控制解的变化过程决定对解是否要做一定的改变。

（6）解的实施。指将解用到实际中必须考虑到实施的问题，如向实际部门讲清解

的用法，在实施中可能产生的问题和所做的修改。

以上过程应反复进行。

1.5管理运筹学的模型及建模思路

运用运筹学在解决问题时，按研究对象不同可构造各种不同的模型。模型是现实世

界的抽象化反映，是研究者对客观现实经过思维抽象后用文字、图表、符号、关系

式以及实体模样描述所认识到的客观对象。运筹学的实质在于建立和使用模型来解

决实际问题。

模型有三种基本形式：形象模型、模拟模型和数学模型。物理复制被称为形象模型

，如飞机模型等。模拟模型也是物理模型，但是在外形上与被建模的对象并不一样

，如汽车上的速度表就是一种模拟模型。数学模型是以一些系统化的符号和数学表

达式或关系式来反映实际问题。目前运筹学中用得最多的是数学模型。

如何将一个现实问题转化为数学模型，也就是建模过程。运筹学模型的几个要素是

目标函数、约束条件、决策变量。建立模型框架需要我们根据要解决的问题思考以

下几个问题。

（1）我们需要什么目标？

（2）通过调节哪些因素可以使得我们达到这一目标？

（3）调节的因素是被动的吗？要与实际情况相符合有什么限制条件吗？

（4）在实现目标的过程中，有哪些约束条件？

（5）这样建立的模型是相对完备的吗？

对以上问题的回答只是提供了一种建立模型的基本框架结果，对于数学规划类的建

模，这种思路也是很有效的。一旦建模和数据准备工作已经完成，我们就可以进入

模型求解阶段。

想要对模型求解就要求我们对算法有一个基本的认识。算法是一系列解决问题的清

晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算

法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷或者不适合某

个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间

或效率来完成同样的任务。

对运筹学的学习，就是要有效率地解决问题，模型和算法的好坏直接影响这一目标

的实现。对于算法的设计，方法有很多种，但步骤却差别不大。举个例子：你现在

要去一个地方，这时候你可能会考虑以下几个问题。

（1）我现在在哪里？

（2）我将要去哪里？

（3）朝哪个方向走？

（4）选择每次走多大一步？

一个迭代算法的思想和例子中的思想是一致的。迭代算法主要就是通过当前点到下

一个点的变化来实现。先找到当前点，这是我们新的起点，然后通过一定的规则到

达下一个点，以下一个点为当前点，继续后面的过程直至终止。对应以上四个问题

，应考虑以下几点。

（1）初始点（我现在在哪里）。

（2）终止准则（我的目标是什么）。

（3）迭代方向（朝哪个方向走）。

（4）迭代步长（选择每步走多远）。

对以上四个问题的回答实际上就是对运筹学原理的探究。当然，作为经济管理类专

业的学生，我们主要还是在了解这些算法思想的基础上，能够做到将这些方法应用

到实际问题之中。

1.6管理运筹学的计算工具

伴随着计算机技术和信息技术的发展，作为运筹学的求解工具也越来越多。主要分

为以下几种。

（1）专业的优化求解工具软件。

MATLAB、SAS、Mathematica、SPSS、Lindo/Lingo、

GAMS等工具软件，这些工具软件大都是由企业开发的，需要具备一定的基础，有

些软件的安装过程比较复杂，对使用者要求较高，但功能十分强大，适合于有一定

基础或者有更多求解需求的操作者。

（2）随相关书配送的专用软件。

一般都封装有十几个或更多固定的分支数学模型，根据不同的数学模型特征，确定

了不同的操作，需要在使用前安装。

（3）在Excel平台下求解。

对每个运筹学模型，可随时在Excel工作表中创建求解界面，Excel能够处理大量的

数据信息，特别适用于数字统计，而且能快速制定表格。对于一般关系的数学模型

，直接用数学模型的算法在Excel电子表格中做成求解模版，对于线性规划这些特

殊的数学模型，可以在Excel电子表格中激活其中的专用模块，并根据不同分支的

数学模型算法特征制作求解模版。对具体问题进行求解时，只需将相关数据输入到

相应的单元格中，便可实现求解。

本书为适应一般读者的需求，采用Excel平台对模型进行求解。



第二章线性规划及其应用

2.1线性规划问题及数学模型

线性规划是运筹学的重要分支，自从单纯形法问世以来，得到了快速发展，目前已

经在工业、农业、国防、科技等领域得到了广泛的应用。单纯形法的求解过程较为

烦琐，本书主要侧重理论的应用，故在此只作介绍，不过多阐述。

应用线性规划模型求解实际问题时，首先要将实际问题抽象成数学模型，然后再对

其求解。对于一个实际问题，若要将其作为一个线性规划问题来处理，必须建立与

实际问题对应的线性规划数学模型。

2.1.1线性规划问题的提出

下面用两个简单的例子来说明如何建立线性规划问题的数学模型。

例2-1某家具厂生产桌子和椅子两种家具，如表2-1所示。

表2-1某家具厂生产家具的相关数据

问：企业应如何安排生产计划，使每月销售收入最大化？

解：用数学语言来描述生产计划的安排，这个过程称为建立数学模型，简称建模。

设：桌子、椅子的生产数量为决策变量，分别用x1，x2表示。因为产量一般是非

负数，所以有x1，x2≥0，称为非负约束。

（1）木工和油漆工可用的加工时间为限制条件，约束了产品的生产量x1，x2。

约束条件如下：

4x1+3x2≤120

2x1+x2≤50

（2）桌子、椅子的生产数量为x1，x2时所得总收入为z，显然z=50x1

+30x2。总收入值达到最大，用公式表达为：

maxz=50x1+30x2

把上述所有数学公式归纳如下：

maxz=50x1+30x2

这就是一个最大化的线性规划模型。

例2-2

有一辆卡车，容积18立方米，载重2.5吨，用来装载如下两种货物：箱装件125千

克/个、0.4立方米/个；包装件20千克/个、1.5立方米/个。

问：如何装件，卡车所装物件的个数最多？

解：根据题意，设箱装件x1个，包装件x2个。

需要满足容积、载量约束条件，即：

容积约束0.4x1+1.5x2≤18

载量约束125x1+20x2≤2500

非负约束x1，x2≥0

目标函数maxz=x1+x2

整理得到下面的形式：

maxz=x1+x2

上述两例中所提出的问题，最终都归结为一组决策变量满足线性规划约束条件的前

提下，实现目标函数最大或最小问题，这种问题称为线性规划问题。一个线性规划

问题的数学模型包括三大部分：目标函数、约束条件和决策变量。

2.1.2线性规划数学模型

（1）线性规划数学模型的特征。

①每一个问题都有一组决策变量xj（j=1，2，…，n），取值通常为非负。

②存在一些约束条件，这些约束条件可以用一组决策变量的线性等式或线性不等

式来表示。

③都有一个要求达到的目标，他们可以用决策变量的线性函数来表示，按这个问

题的不同，要求目标函数实现最小化或最大化。

满足上述三个条件的数学模型称为线性规划模型，其数学语言描述为：

其中，式（1-1）称为目标函数，式（1-2）称为约束条件，式（1-

3）称为非负约束条件。式中，z称为目标，xj

（j=1，2，…，n）称为决策变量，cj（j=1，2，…，n）称为价值系数或目标函数

系数，bi（i=1，2，…，m）称为资源常数或约束右端常数，aij（i=1，2，…，m；

j=1，2，…，n）称为技术系数或约束系数，cj，bi，aij均为常数。

（2）线性规划的标准形式。

我们把满足下列条件的线性规划模型称为线性规划的标准形式，如下式所示：

线性规划问题标准形式的条件：

①目标函数为最大化类型。

②所有的决策变量取非负值。

③约束条件均由等式表示。

④每一约束等式的右端常数均为非负值。

（3）将线性规划化成标准型的方法。

对于不符合标准型的线性规划问题，可以通过下面的方法将数学模型化为标准形式

：

①对于minz型，令z′=-z。

②对于bi＜0，约束条件两边同乘-1。

③约束条件为“≤”时，左端加上一个松弛变量。

④约束条件为“≥”时，左端减去一个剩余变量。

⑤变量xj无约束时，令。

⑥变量xj≤0时，令。

2.2线性规划的图解法

例2-3

某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时

及A、B两种原材料的消耗，如表2-2所示。

表2-2某工厂生产Ⅰ、Ⅱ两种产品的相关数据

该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安

排计划使该工厂获利最多？这问题可以用以下的数学模型来描述，设x1、

x2分别表示在计划期内产品Ⅰ、

Ⅱ的产量。因为设备的有效台时是8，这是一个限制产量的条件，所以在确定产品

Ⅰ、Ⅱ的产量时，要考虑不超过设备的有效台时数，即可用不等式表示为：

x1+2x2≤8

同理，因原材料A、B的限量，可以得到以下不等式：

4x1≤16

4x2≤12

该工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1、x2以得到最

大利润。若用z表示利润，这时z=2x1+

3x2。综合上述，该计划问题可用数学模型表示为：

目标函数maxz=2x1+3x2

满足约束条件：

图解法简单直观，有助于了解线性规划问题求解的基本原理。现对上述例1-

3用图解法求解。在以x1、x2为坐标轴的直角坐标系中，非负条件x1，x2≥0是指第

一象限。例1-3的每个约束条件都代表一个半平面。如约条件x1

+2x2≤8是代表以直线x1+

2x2=8为边界的左下方的半平面，若同时满足x1，x2≥0，x1

+2x2≤8，4x1≤16，和4x1≤12的约束条件的点，必然落在x1、

x2坐标轴和由这三个半平面交成的区域内。由例2-

3中的所有约束条件为半平面交成的区域，即阴影区域（见图2-

2）。阴影区域中的每一个点（包括边界点）都是这个线性规划问题的解（称可行

解），因而此区域是例2-3的线性规划问题的解集合，称它为可行域。

再分析目标函数z=2x1+3x2在这坐标平面上，它可表示以z为参数、-

2/3为斜率的一族平行线：

x2=-（2/3）x1+z/3

位于同一直线上的点，具有相同的目标函数值，因而称它为“等值线”。当z值由小

变大时，直线x2=-（2/3）x1+

z/3沿其法线方向向右上方移动。当移动到Q2点时，使z值在可行域边界上实现最

大化（见图2-3），这就得到了例2-

3的最优解Q2，Q2点的坐标为（4，2）。于是可计算出满足所有约束条件下的最

大值z=14。

图2-1模型的可行解区域

图2-2模型的求解过程

这说明该厂的最优生产计划方案是生产4件产品Ⅰ和生产2件产品Ⅱ，可得最大利

润为14元。

上例中求解得到问题的最优解是唯一的，但对一般线性规划问题，求解结果还可能

出现以下几种情况。

（1）无穷多最优解（多重最优解）。

若将例2-3中的目标函数变为求maxz=2x1

+3x2则表示目标函数中以参数z的这族平行直线与约束条件x1

+2x2≤8的边界线平行。当z值由小变大时，将与线段Q1Q3重合（见图2-

3）。线段Q2

Q3上任意一点都使z取得相同的最大值，这个线性规划问题有无穷多最优解（多重

最优解）。

图2-3无穷多最优解

（2）无界解。

对下述线性规划问题

maxz=x1+x2

用图解法求解结果如图2-4所示。从图2-

4中可以看到，该问题可行域无界，目标函数值可以增大到无穷大。称这种情况为

无界解。

图2-4无界解

（3）无可行解。

如果在例2-3的数学模型中增加一个约束条件-

2x1+x2≥4，该问题的可行域为空集，即无可行解，也不存在最优解。

当求解结果出现第2、

3两种情况时，一般说明线性规划问题的数学模型有错误。前者缺乏必要的约束条

件，后者是有矛盾的约束条件，建模时应注意。

从图解法中直观地见到，当线性规划问题的可行域非空时，它是有界或无界凸多边

形。若线性规划问题存在最优解，它一定在有界可行域的某个顶点得到；若在两个

顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。

图解法虽然直观、简便，但当变量数为三个或三个以上时，它就无能为力。所以在

2.3节中要介绍一种代数法——单纯形法。

2.3单纯形法

单纯形法求解线性规划的思路：一般线性规划问题具有线性方程组的变量数大于方

程个数，这时有不定的解。但可以从线性方程组中找出每一个单纯形，每一个单纯

形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选

择的单纯形。通过上述迭代步骤，直到目标函数实现最大值或最小值。

单纯形法的计算步骤：

①将线性规划标准型化为线性规划的规范型，来获取一个初始可行解。

②将初始基可行解最优性判别，若最优，停止；否则转一下步。

③从初始基可行解向相邻的基可行解转换，且使目标值有所改善，重复第二步和

第三步直到找到最优解。

2.4案例解析

关于线性规划问题的求解，有许多软件可以实现，但最简便易行的求解软件就是E

xcel。首先打开MicrosoftExcel

2010文件，在“文件”中选中“选项”，然后在“Excel选项”中单击“加载项”，然后在“

Excel加载项”中，选中“规划求解加载项”，单击“转到”，然后在数据选项卡中就有

规划求解（见图2-5）。

图2-5规划求解步骤（a）

图2-5规划求解步骤（b）

下面介绍如何在Excel中使用规划求解。

（1）建立Excel工作表，将要求解模型中的每个组成部分放在Excel表格中，用每

一组单元格表示变量，作为可变单元格；用几组单元格分别表示各约束条件和目标

函数的系数；用一些单元格输入公式表示各组系数和变量的关系。

例2-3的线性规划模型求解步骤就可以在Excel中实现。

在图2-6中用单元格B11：C11表示变量x1和x2，用单元格B3：

C3表示变量x1和x2在目标函数中的系数，用单元格B6：C8表示变量x1和x2在约束

条件中的系数，用单元格D6：D8分别表示三个约束条件的左端项，用单元格F6：

F8分别表示三个约束条件的右端项，用单元格F11表示目标函数。

图2-6线性规划模型求解的电子表格设置

对第一个约束条件的左端项x1+

x2，其在单元格中的表示是：在D6的位置上输入“=SUMPRODUCT（B6：

C6，B11：C11）”（见图2-7）。按照同样的方式可以在D7、

D8的位置上如数所代表的约束条件4x1≤16和4x2≤

12的左端项，在F11的位置上输入目标函数2x1+3x2。

图2-7线性规划模型电子表格中的SUMPRODUCT函数

（2）打开“数据”栏中的“规划求解参数”对话框，指定存有目标函数的单元格为目

标单元格，指定表示变量的单元格为可变单元格，建立约束条件（见图2-8）。

图2-8线性规划模型表格的参数设置

在图2-

8中指定单元格F11为目标单元格，由已知条件可知目标是最大化，所以需选中“最

大值”；指定B11：

C11为可变单元格，然后点击“添加”按钮就会弹出“添加约束”对话框，如图2-

9所示。

图2-9“添加约束”对话框

在“添加约束”对话框中，左端输入的是约束条件的左端项，本例中即输入的范围是

D6：D8所代表的单元格，右端输入的是约束条件的右端项，即F6：

F8所代表的单元格，对于两边中间的符号，有个菜单可以选择“≤”或“=”或“≥”，这

样约束条件已经输入完毕。若需要添加更多的约束条件，就点击“添加”按钮，然后

弹出一个新的“添加约束”对话框。若没有其他约束条件需要添加，只要点击“确定”

按钮就回到“规划求解参数”对话框。然后，在“是无约束变量为非负数”前打钩，并

且选择求解方法时选择“单纯线性规划”，选项选取默认值，再点击“求解”按钮，图

2-8描述了在电子表格中建模的过程。

（3）在“规划求解参数”对话框中点击“求解”按钮，即可求出最优解和最优值。在

一般情况下，都会出现图2-

10所示的“规划求解结果”对话框，它说明已经找到最优解。

图2-10规划求解结果对话框

如果模型无可行解或无最优解，对话框会显示“找不到可行解”或“设定的单元格值

未收敛”。对话框还会生成三个报告：运算结果报告、敏感性报告和极限值报告。

例2-3的规划求解结果如图2-11所示。

图2-11例2-3的规划求解结果

从结果可以清晰地看出，通过Excel计算求出的结果与图解法求出的结果是一致的

。

线性规划在工商管理领域应用广泛，主要用于解决生产计划安排、人力资源分配、

网络配送、套裁下料、采购存储、投资组合优化等问题。

（一）生产计划安排问题

公司面临外包协作、

自行生产的问题。甲、乙、丙产品都需要经过铸造、机加工和装配三道工序。铸造

工序中甲、乙可外包，亦可自产，丙必须自产，其余工序必须本厂完成。相关数据

如表2-3所示。

表2-3公司生产甲、乙、丙产品的相关数据

续表

问：为获取最大利润，三种产品各生产多少件？甲、乙的铸件有多少由本公司铸造

？有多少由外包协作？

解：分析题中已知条件，不妨设x1、x2、

x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4、

x5分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。

求xi的利润的公式：

利润=售价-各成本之和

产品甲全部自制的利润=23-（3+2+3）=15（元）

产品甲铸造外协，其余自制的利润=23-（5+2+3）=13（元）

产品乙全部自制的利润=18-（5+1+2）=10（元）

产品乙铸造外协，其余自制的利润=18-（6+1+2）=9（元）

产品丙的利润=16-（4+3+2）=7（元）

可得到xi，i=1，2，3，4，5的利润分别为15、10、7、13、9元。

上述的问题就可以转化成为如下的数学模型：

目标函数：max15x1+10x2+7x3+13x4+9x5

满足约束条件：

从上述模型可知，上述生产计划问题可转化对线性规划模型的求解。

在图2-12中用单元格B11：F11表示变量xi（i=1，2，3，4，5），用单元格B3：

F3表示变量xi（i=1，2，3，4，5）在目标函数中的系数，用单元格B6：

F8表示变量xi（i=1，2，3，4，5）在约束条件中的系数，用单元格G6：

G8分别表示三个约束条件的左端项，用单元格I6：I8分别表示3个约束条件的右端

项，用单元格I11表示目标函数。

图2-12生产计划问题转化为线性规划模型的求解电子表格设置

对第一个约束条件的左端项5x1+10x2+

7x3，其在单元格中的表示是：在G6的位置上输入“=SUMPRODUCT（B6：

F6，B11：F11）”，如图2-13。按照同样的方式可以在G7、

G8的位置上如数所代表的约束条件6x1+4x2+8x3+4x4+4x5≤12000和3x1+2x2+

2x3+3x4+2x5≤10000的左端项，在I11的位置上输入目标函数15x1+10x2+7x3

+13x4+9x5。

图2-13生产计划问题转化为线性规划模型电子表格中的SUMPRODUCT函数

（2）打开“数据”栏中的“规划求解参数”对话框，指定存有目标函数的单元格为目

标单元格，指定表示变量的单元格为可变单元格，建立约束条件（见图2-14）。

在图2-

15中指定单元格I11为目标单元格，由已知条件可知目标是最大化，所以需选中“最

大值”；指定B11：

F11为可变单元格，然后点击“添加”按钮就会弹出“添加约束”对话框，如图2-

15所示。

图2-14生产计划问题转化为线性规划模型的表格的参数设置

图2-15可变单元格的“添加约束”对话框

在“添加约束”对话框中，左端输入的是约束条件的左端项，本例中即输入的范围是

G6：G8所代表的单元格，右端输入的是约束条件的右端项，即I6：

I8所代表的单元格，对于两边中间的符号，选择“≤”，这样约束条件已经输入完毕

。点击“确定”按钮就回到“规划求解参数”对话框。然后，在“是无约束变量为非负数

”前打钩，并且选择求解方法时选择“单纯线性规划”，选项选取默认值，然后点击“

求解”按钮，图2-12描述了在电子表格中建模的过程。

（3）在“规划求解参数”对话框中点击“求解”按钮，即可求出最优解和最优值。在

一般情况下，都会出现图2-

16所示的“规划求解结果”对话框，它说明已经找到最优解。规划求解结果如图2-

17所示。

图2-16生产计划问题转化为线性规划模型的规划求解结果对话框

图2-17生产计划安排问题的规划求解结果

从运算的结果可以很清晰地看出，甲产品自产1600件，产品乙他产600件，才能保

证获得最大利润29400元。

（二）人力资源安排问题

百货商场对售货员的需求如下表。要求售货员每周工作五天，连续休息两天。相关

数据资料如表2-4所示。

问：应该如何安排售货员，满足工作需要，同时使配备的售货员人数最少？

表2-4相关数据资料

解：设xi（i=1，2，…，7）表示星期i开始休息的人数，建立如下的数学模型。

目标函数：minx1+x2+x3+x4+x5+x6+x7

约束条件：

从模型可知，上述人力资源安排问题可转化对线性规划模型的求解。

在图2-18中用单元格B14：H14表示变量xi

（i=1，2，3，4，5，6，7），用单元格B3：H3表示变量xi

（i=1，2，3，4，5，6，7）在目标函数中的系数，用单元格B5：H11表示变量xi

（i=1，2，3，4，5，6，7）在约束条件中的系数，用单元格I5：

I11分别表示7个约束条件的左端项，用单元格K5：

K11分别表示7个约束条件的右端项，用单元格K14表示目标函数。

图2-18人力资源安排问题转化为线性规划模型的求解电子表格设置

对第一个约束条件的左端项x2，x3，x4，x5

，x6，其在单元格中的表示是：在I5的位置上输入“=SUMPRODUCT（B5：

H5，B14：H14）”（见图2-19）。按照同样的方式可以在I6、I7、I8、I9、

I10和I11的位置上如数所代表的其他6个约束条件的左端项，在K14的位置上输入

目标函数x1+x2+x3+x4+x5+x6+x7。

图2-19人力资源安排问题转化为线性规划模型电子表格中的SUMPRODUCT函数

打开“数据”栏中的“规划求解参数”对话框，指定存有目标函数的单元格为目标单元

格，指定表示变量的单元格为可变单元格，建立约束条件。

在图2-

20中指定单元格K14为目标单元格，由已知条件可知目标是最小化，所以需选中“

最小值”；指定B14：

H14为可变单元格，然后点击“添加”按钮就会弹出“添加约束”对话框，如图2-

21所示。

图2-20人力资源安排问题转化为线性规划模型的表格的参数设置

图2-21指定的可变单元格的“添加约束”对话框

在“添加约束”对话框中，左端输入的是约束条件的左端项，本例中即输入的范围是

I5：I11所代表的单元格，右端输入的是约束条件的右端项，即K5：

K11所代表的单元格，对于两边中间的符号，选择“≥”，这样约束条件已经输入完

毕。点击“确定”按钮就回到“规划求解参数”对话框。然后，在“是无约束变量为非负

数”前打钩，并且选择求解方法时选择“单纯线性规划”，选项选取默认值，然后点

击“求解”按钮，图2-18描述了在电子表格中建模的过程。

在“规划求解参数”对话框中点击“求解”按钮，即可求出最优解和最优值。在一般情

况下，都会出现“规划求解结果”对话框（见图2-

22），它说明已经找到最优解。规划求解结果如图2-23所示。

图2-22人力资源安排问题转化为线性规划模型的规划求解结果对话框

图2-23本例的规划求解结果

从运算的结果可以很清晰地看出，星期一开始休息的12人，星期三开始休息的人

数为11人，星期四开始休息的人数为5人，星期六开始休息人为8人，其他时间无

休息人，才能保证需要的售货员人数最少，需要36人。

（三）套裁下料问题

工厂要做100套钢架，每套用长为2.9米，2.1米，1.5米的圆钢各一根。已知原料每

根长7.4米，问：应如何下料，可使所用原料最省？

解：列出所有可能下料方案，如表2-5所示。

表2-5钢架下料的所有可能方案

不妨设按上述方案下料的原材料根数分别为xi

（i=1，2，3，4，5，6，7，8），可考虑建立如下的数学模型。

目标函数：minx1+x2+x3+x4+x5+x6+x7+x8

约束条件：

类似于前两个实验，这里只给出相应的过程图，不再做详细说明。

首先，制作模型的电子表格，如图2-24所示。

图2-24套裁下料问题转化为模型的电子表格设置

其次，在电子表格中填入约束条件，如图2-25所示。

图2-25套裁下料问题转化为模型的电子表格中的SUMPRODUCT函数

再次，设置表格参数，添加约束条件，如图2-26所示。

图2-26套裁下料问题转化为模型的表格的参数设置

最后，进行求解，如图2-27所示。

图2-27套裁下料问题的求解结果

从结果可以很清晰地看出，需要30根圆钢按照方案1套裁，需要10根圆钢按照方案

2套裁，需要50根圆钢按照方案4套裁，共需要90根圆钢就可以满足例题中的需求

。

运筹学在工商管理领域里的其他应用，在此不再一一列出，所有问题的关键就在于

构建模型，然后按照上述步骤都可以用Excel进行求解。

习题

1.将下列线性规划模型转换为标准形式。

（1）maxz=x1+4x2-x3

（2）minz=9x1-3x2+5x3

2.图解线性规划问题，并指出该问题是具有唯一最优解、无穷多最优解、无界解还

是无形可行解。

（1）minz=-2x1+x2

（2）maxz=-x1-3x2

（3）maxz=-3x1+2x2

（4）maxz=x1+x2

3.某化工厂生产某项化学产品，每单位标准重量为1000克，由A、B、

C三种化学物混合而成。产品组成成分是每单位产品中A不超过300克，B不少于15

0克，C不少于200克。A、B、

C每克成本分别为5元、6元、7元。问如何配置此化学产品，才能使成本最低？

4.某产品重量为150千克，用A、

B两种原料制成。每单位A原料成本为2元，每单位B原料成本为8元。该产品至少需

要含14单位B原料，最多含20单位A原料。每单位A、

B原料分别重5千克、10千克，为使成本最小，该产品中A、B原料应各占多少？

5.设某工厂有甲、乙、丙、丁四台机床，生产A、B、C、D、

E、F六种产品。加工每一件产品所需要时间和每一件产品的单价如表2-6所示。

表2-6工厂相关数据表

表中没有填数的表示该机床不参加生产这种产品。现假设在某一时间内，甲、乙、

丙、丁四台机床的最大工作能力分别为850、700、600、

900工时，问这一时段内，每种产品各应生产多少，才能使该厂总收入最大化？

6.一家玩具公司制造三种玩具，每一种要求不同的制造技术。高级的一种需要17个

小时加工装配，8小时检测，每台利润30元；中级的需2小时加工装配，半小时检

测，每台利润5元；低级的需半小时加工装配，10分钟检测，每台利润1元。现公

司可供利用的加工装配时间为500小时，检测时间100小时。市场预测显示，对高

级、中级、低级玩具的需求量分别不超过10台、30台、100台，试制订一个能够使

总利润最大的生产计划。

7.A、

B两种产品，都需要经过前后两道工序加工，每一个单位产品A需要前道工序1小时

和后道工序有2小时，每一个单位产品B需要前道工序2小时和后道工序3小时。可

供利用的前道工序有11小时，后道工序有17小时。

每加工一个单位产品B的同时，会产生两个单位的副产品C，且不需要任何费用，

产品C一部分可售出盈利，其余只能销毁。

出售单位产品A、B、C的利润分别为3、7、

2元，每单位产品C的销毁费为1元，预测表明，产品C最多只能销售13个单位，试

建立使利润最大的生产计划的数学模型。

8.某企业生产甲、乙、丙三种产品，其每单位所消耗工时分别为1.6小时、2.0小时

、2.5小时，每单位所需原料A分别为24千克、20千克、12千克，所需原料B分别为

14千克、10千克、18千克。生产线每月正常工作时间为240小时，原料A、

B的总供应量限制为2400千克和1500千克。生产一个甲、乙、丙产品各可获利润5

25元、678元、812元，试分别建立以下两种情况下的数学模型，不需要计算。

（1）由于每单位丙产品的生产会产生5千克副产品丁，这些副产品丁一部分可以

销售，利润为300元/千克，剩下的会造成污染，每千克需要排污费200元。副产品

丁的需求量为每月不超过150千克。应如何确定生产计划，可使总利润最大？

（2）工厂考虑到产品丙有污染，决定不生产丙而准备在另外的三种产品W、Q、G

中选择1种或2种进行生产，它们所消耗工时、所需原料A、B及利润如表2-

7所示。

表2-7工厂相关资源表

应如何确定生产计划，可使总利润最大？



第三章运输问题

运输问题实际上是一种线性规划问题，当然可以考虑采用单纯形法求解，但本书是

实验教程，更多侧重于方法的应用，所以在阐明理论之后，可采用Excel软件进行

求解。

3.1运输问题及数学模型

运筹学研究领域中的运输问题，则主要是研究单一的运输对象费率确定的运输网络

中的整体配送效率问题。

一般来讲，运输问题可以这样描述。设有m个产地Ai，各地的产量为Si，n个销地Bj

，各地的销量分别是dj，把某物从产地Ai运至销地Bj的运输费率为cij，如何安排运

量，才能在产销平衡的前提下达到总运输费用最小。设xij表示从产地Ai调运到Bj的

运量，z是总运输费用。产销平衡表和单位运价表如表3-1和表3-2所示。

表3-1运输量表

表3-2单位运价表

在产销平衡的条件下，上述问题可转化为数学模型：

当产销不平衡时，会出现下面两种情况。

（1）当产量大于销量时，可假想仓库为另一个销地B，可将产销不平衡问题转化

为产销平衡问题，只不过仓库的单位运价为零。

（2）当产量小于销量时，假想添加一个生产地，即多一个A，可将产销不平衡问

题转化为产销平衡问题，假想生产地的单位运价为零。

上述运输问题具有以下两个特点。

（1）变量xij的悉数列向量只有两个分量为1，其余的都为零。

（2）相互独立的约束方程的个数为m+n-1个。

正因为两个特点，可找到比单纯形法更为简单的方法进行求解，这种方法就是表上

作业法。

3.2表上作业法

表上作业法的求解步骤与单纯形法求解步骤类似，具体步骤如下。

（1）写出运输问题的表格形式，即产销平衡表和单位运价表。

（2）确定初始调运方案（相当于确定初始可行解）。

（3）检验方案是否最优（相当于最优性判别），若是最优，停止计算；若不是，

则继续。

（4）调整调运方案，得到新方案。

（5）重复步骤（3）和（4），直到求出最优调运方案。

例3-1

石家庄北方研究院有三个区，即一区、二区、三区，每年分别需要用煤3000吨、1

000吨、2000吨，由河北临城、山西盂县两处煤矿负责供应，这两处煤矿的价格相

同、质量相同。山西盂县供煤4000吨，河北临城1500吨。单位运价如表3-

3所示，求最低总运费。

表3-3例3-1的单位运价表

解：

首先，做出产销平衡与运价表，如表3-4所示。

表3-4产销平衡和单位运价表

续表

这里假设运输单价M为一个很大的正数，这样就保证了M*

（相应运输量x）也是一个很大的正数，这显然不符合总运费最小的目标，所以（

相应的运输量x）

=0。了解原理后，在使用软件计算时，输入M时不能输入字母M，而是需要输入一

个很大的数，比如1000，再求得最后结果。

然后是比较难的，运输问题的表上作业法，其实质是单纯形法，“套路”与单纯形法

类似，先求出基解（在图像上显示为顶点），然后再比较哪一个基解是最优的。

求解过程如下：

（1）确定初始基本可行解的方法为最小元素法、西北角法（左上角法、阶梯法）

、最大差额法（Vogel概算法、伏格尔法）。Russell概算法。

（2）最优解的判别。

（3）改进运输方案。

本节以最小元素法为例描述整个求解过程，其他方法不再逐一列举。

（1）确定初始基本可行解。

这里的“最小元素”指的是最小运价cij。不同产地销售到同一销地的运价不同，考虑

到运费最低，肯定选择运价最低的满足这一销地，实际情况一般是先把离某一销地

最近产地的产品拿去销地，即就近的先运。可考虑从下面一个比较简单的例题去体

会最小元素法，如表3-5所示。

表3-5最小元素法操作步骤表（1）

首先，在表3-

5中粗线框的数字中找最小的数字，即最小的单位运价，也就是1，对应的是A2到B

1的单位运价。以1的单位运价满足销地B1销量3的x21=3。

表3-6最小元素法操作步骤表（2）

因为B1的销量满足了，所以划去B1列。而A2的产量4给了B1产量3之后还剩产量1

，给单位运价第二低的2，在该单元格的右上角于写上①。于是A2的产量全部分配

完，划去该行，x23=1。

表3-7最小元素法操作步骤表（3）

接着看剩下的最小运费，为A1行的3，将A1产量7分配给B3的销量5-

1=4，还剩下3全分配给B4，划去A1行x13=4，x14=3。

表3-8最小元素法操作步骤表（4）

然后看剩下的最小运费，为A3行的4，以A3的产量9给B2的销量6，划去B2列，x32

=6。剩下3，分配给A3行的最小数5，于是B4销量也满足，划去B4列，x34=3。

A3的产量全部分配完，划去A3行。

表3-9最小元素法操作步骤表（5）

全部划去后，在运价表的基础上写上运量表。

表3-10最小元素法操作步骤表（6）

从表中可以清晰地看出x21=3，x23=1

，x13=4，x14=3，x32=6，x34=3。这就是最小元素法的求解过程。

（2）最优解的判别。

通过步骤（1）得出的方案往往不是最优的，需要对最优性进行判别。对方案最优

性的判别就是求出各个非基变量的检验数，如果都满足大于等于零，就说明任何一

个空格处增加一个单位，总运费就要增加，正好说明当前方案的最优性，如果不是

，要对方案进行调整。

（3）改进运输方案。

如果得到的方案不是最优，可采用闭合回路法对方案进行调整，详见其他运筹学理

论教程，本书不再一一阐明。

3.3案例解析

例3-2某公司从两个产地A1、A2将物品运往三个销地B1、

B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如

表3-11所示，问：应如何调运可使总运输费用最小？

表3-11例3-2的运价表

解：从题中已知条件可知：该问题是产销平衡的运输问题，故可采用Excel中线性

规划方法进行求解。

上述问题的电子表格建模如图3-1所示。

图3-1例3-2的建模电子表格

分别在F11、F12输入sum函数，作为产地的供应求和，同理在C13、D13、

E13位置输入sum函数，作为销地的销量求和。同时在H13位置输入sumproduct函

数，作为总运费的求和，如图3-2所示。

图3-2电子表格中的sum和SUMPRODUCT函数设置

打开“数据”栏中的“规划求解参数”对话框，指定存有目标函数的单元格为目标单元

格，指定表示变量的单元格为可变单元格，建立约束条件（见图3-3）。

图3-3例3-2电子表格的参数设置

在图3-

3中指定单元格H13为目标单元格，由已知条件可知目标是最小化，所以需选中“最

小值”；指定C11：

E12为可变单元格，然后点击“添加”按钮就会弹出“添加约束”对话框，把C13：

E13=C15：E15和F11：F12=H11：

H12添加到约束条件对话框，在“是无约束变量为非负数”前打钩，并且选择求解方

法时选择“单纯线性规划”，选项选取默认值，然后点击“求解”按钮，就可得到本案

例的最优解，如图3-4所示。

图3-4例3-2的规划求解结果

从图3-

4可知，产地A1供应销地B1和B250和150单位的产品，产地A2分别供应销地B1和B

3100和200单位的产品，这样的调运方案可使得总运费最低，共花费2500元。

运用Excel中的线性规划模块对例3-1进行求解。

解：从题中已知条件可知：该问题是产销不平衡的运输问题，可先增加一个假想产

地，然后构建表3-

4一样的产销平衡的运输问题，M值可以设为一个具体的数字，比如1000，故可采

用Excel中线性规划方法进行求解。

上述问题的电子表格建模如图3-5所示。

图3-5建模电子表格

分别在F12、F13和F14处输入sum函数，作为产地的供应求和，同理在C17、

D17、

E17位置输入sum函数，作为销地的需求量求和。同时在H15位置输入SUMPRODUC

T函数，作为总运费的求和。

打开“数据”栏中的“规划求解参数”对话框，指定存有目标函数的单元格为目标单元

格，指定表示变量的单元格为可变单元格，建立约束条件。

在图3-

6中指定单元格H15为目标单元格，由已知条件可知目标是最小化，所以需选中“最

小值”；指定C12：

E14为可变单元格，然后点击“添加”按钮就会弹出“添加约束”对话框，把C15：E15

=C17：E17和F12：F14=H12：

H14添加到约束条件对话框，然后在“是无约束变量为非负数”前打钩，并且选择求

解方法时选择“单纯线性规划”，选项选取默认值，然后点击“求解”按钮，就可得到

本案例的最优解，如图3-7所示。

图3-6电子表格的参数设置

图3-7例3-1的规划求解结果

从图3-

7可知，产地山西盂县供应石家庄北方研究院一区和二区的煤炭量分别为3000吨和

1000吨，产地河北临城供应石家庄北方研究院三区1500吨煤炭，减去假想生产地

生产的500吨煤炭运往三区所耗的费用500000元，这样的调运方案可使得总运费最

低，共花费9200元。

例3-3已知某运输问题的产销平衡表与单位运价表如表3-

12所示，试求最优的调拨方案。

表3-12产销平衡表及单位运价表

解：从题中已知条件可知：该问题中产地的产量和销地的销量是相等的，因此属于

产销平衡的运输问题，故可采用Excel中线性规划方法进行求解。

上述问题的电子表格建模如图3-8所示。

图3-8例3-3的建模电子表格

分别在H12、

H13和H14输入sum函数，对所在行求和，作为各产地的供应求和，同理在C15、

D15、E15、

F15和G15位置输入sum函数，对表格所在列求和，作为各销地的销量。同时在J15

位置输入SUMPRODUCT函数，作为总运费的求和，如图3-8所示。

打开“数据”栏中的“规划求解参数”对话框，指定存有目标函数的单元格为目标单元

格，指定表示变量的单元格为可变单元格，建立约束条件。

图3-9例3-3的电子表格的参数设置

在图3-

9中指定单元格J15为目标单元格，由已知条件可知目标是最小化，所以需选中“最

小值”；指定C12：G14为可变单元格，然后点击“添加”按钮就会弹出“添加约束”对

话框，把H12：H14=J12：J14和C15：G15=C17：

G17添加到约束条件对话框，在“是无约束变量为非负数”前打钩，并且选择求解方

法时选择“单纯线性规划”，选项选取默认值，然后点击“求解”按钮，就可得到本案

例的最优解，求解结果如图3-10所示。

图3-10求解结果

从图3-10可知，产地1供应销地A、B和E的产品数量分别为10、

10和30，产地2供应销地B和C的产品数量分别为10和30，产地3供应销地A和D的产

品数量分别为20和40，这样的调运方案最优，可使得总运费最低，共花费320元。

习题

1.设有三个化肥厂（A、B、C）供应四个地区（Ⅰ、

Ⅱ、Ⅲ、Ⅳ）的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年

产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如表3-

13所示。试求出最节省总运费的化肥调拨方案。

表3-13运价表

2.某厂按合同规定须于当年每个季度末分别提供10、15、25、

20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如

表3-

14所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、

维护等费用0.15万元。要求在完成合同的情况下，做出使该厂全年生产（包括储存

、维护）费用最小的决策。

表3-14生产能力及单位成本表

3.某航运公司承担六个港口城市A、B、C、D、E、

F的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数

如表3-15所示。假定各条航线使用相同型号的船只，又各城市间的航程天数如表3-

16所示。又知每条船只每次装卸货的时间各需1天，则该航运公司至少应配备多少

条船，才能满足所有航线的运货需求？

表3-15各条航线基本信息表

表3-16各城市间航程天数表

4.某百货公司去外地采购A、B、C、D四种规格的服装，数量分别为：A——

1500套，B——2000套，C——3000套，D——

3500套。有三个城市可供应上述规格服装，各城市供应数量分别为：I——

2500套，Ⅱ——2500套，Ⅲ——

5000套。由于这些城市的服装质量、运价和销售情况不同，预计售出后的利润（

元/套）也不同，如表3-

17所示。请帮助该公司确定一个预期盈利最大的采购方案。

表3-17百货公司相关数据表

5.甲、乙、丙三个城市每年需要煤炭的数量分别为：320万吨、250万吨、350万吨

，由A、B两处煤矿负责供应。已知煤炭年供应量分别为：A——400万吨，B——

450万吨。煤矿至各城市的单位运价（万元/万吨）如表3-

18所示。由于需大于供，经研究平衡决定，甲城市供应量可减少0～30万吨，乙城

市需要量应全部满足，丙城市供应量不少于270万吨。试求将供应量分配完又使总

运费为最低的调运方案。

表3-18煤炭调运价格表

6.某造船厂根据合同要从当年起，连续三年年末各提供三条规格型号相同的大型客

货轮。已知该厂这三年内生产大型客货轮的能力及每艘客货轮成本如表3-19所示。

表3-19造船厂生产能力及成本表

已知加班生产时，每艘客货轮成本比正常生产时高出70万元。又知造出来的客货

轮如当年不交货，每艘每积压一年造成积压损失为40万元。在签订合同时，该厂

已储存了两艘客货轮，而该厂希望在第三年末完成合同后还能储存一艘备用。问该

厂应如何安排每年客货轮的生产量，使在满足上述各项要求的情况下，总的生产费

用加积压损失为最少？

7.某公司在3个地方有3个分厂，生产同一种产品，其产量分别为300箱、400箱、5

00箱。需要供应4个销地的销售，这4个销地的产品需求分别为400箱、250箱、55

0箱。3个分厂到4个销地的单位运价如表3-20所示。

表3-203个分厂到4个销地的单位运价表

（1）应如何安排运输方案，使得总运费为最小？

（2）如果2分厂的产量从400箱提高到了600箱，那么应如何安排运输方案，使得

总运费为最小？

（3）如果销地甲的需求从400箱提高到550箱，而其他情况都同a，那该如何安排

运输方案，使得运费为最小？

8.某公司有甲、乙、丙、丁四个分厂生产同一种产品。产量为300、500、400、

10