运筹学教案设计

管理科学与工程学院

系统工程教研室

第1次谀2学时

上欠课复习：

本次课题（或教材章节题目）：绪论、第一章线性规划与单纯形法§1.1实际问题与线

性规划1模型

教学要求：掌握运筹学发展历史、主要分支及工作步骤；掌握线性规划一般形式特点及图

解法。

重点：运筹学的工作步骤、线性规划一般形式、图解法。

难点：线性规划一般形式及特点、线性规划图解法。

教学手段及教具：多媒体教学。

讲授内容及时间分配：

一、运筹学简史25分钟

二、运筹学的主要分支10分钟

三、运筹学的工作步骤10分钟

第一章线性规划与单纯形法

§1.1线性规划的基本概念

§1.1.1线性规划的数学模型20分钟

§1.1.2图解法25分钟

课后作业国411(1)、(4)

《运筹学》

《运筹学教程》

参考资料

《运筹学》

《运筹学应用案例》

注：本页为每次课教案首

第一章绪论

本章内容要点

1、主要介绍博学的简史，运筹学的性质、特点、应用及其发展前景；

2、根据学习本课程的经3斜是出一些建议；

第一节运筹学概况简述

运筹学是一门基础性的应用学科，主要研究系统最优化的问题，通过对建

立的模型求解，为决策者进行决策提供科学依据。

-运筹学简史

运筹学的英文通用名称为“OperationsResearch简称OR,按照原意应

译为运作研究或作战研究。我国翻译成地“运筹学"，这是出于《史记汉高祖

本纪》中，汉高祖刘邦称赞张良日"夫运筹于帷幄之中，决胜于千里之外，吾

不如子房。"这里的,有主持战略、"作战研究"之意，人4、邨具义把它

译为“运筹学"。国内外许多学者公认，这个译法非常恰当。事实上，运筹学的

思想出现得很早。我国历史上的军事和科学技术方面对运筹思想的运用是世界

著名的，公元6世纪春秋时期著名的《孙子兵法》中处处体现了军事运筹的思

想；战国时期的"田忌齐王赛马”故事是对策论的典型范例；刘邦、项羽在楚

汉相争过程中，依靠张良等谋士的计谋，演出了一幕又一幕运筹思想体现的作

战战例；三国时期的战争中更可以举出很多运用运筹思想取得战争胜利的例

子。除军事方面，在我国古代农业、运输、工程技术等方面也有大量体现运筹

思想的实例，如北魏时期科学家贾思勰的《齐民要术》一书就是一部体现运筹

思想合理策划农事的宝贵文献；古代的粮食和物资的调运、都市的规划建设、

水利方面如四川都江堰工程等亦处处反映了运筹思想的运用。

在欧美运筹学早期工作的历史可追溯到20世纪前叶，在1914年提出了军

事运筹学中的兰彻斯特(Lanchester)战斗方程;1917年排队论的用区者丹麦工

程师爱尔朗(Erlang)在哥本哈根电话公司研究电话通讯系统时，提出了排队论

的一些著名公式；本世纪20年代初提出了存贮论的最优批量公式；本世纪30

年代，在商业方面列温逊已经运用运筹思想来分析商业广告和顾客心理等。

这反映出，运筹学注意系统数据采集，分析并研究优化方案的思想是一种

朴素、自然的思想。在实际上，很多人都在自觉，不自觉地运用这个思想。另

一方面，我们常说"魔高一尺，道高一丈"，在竞争中各方共同运用这些思想

解决问题时，就表现为对运筹学内涵的研究、运用能力。

谢^(OperationsResearch,简称OR),作为科学名字是出现在20世

纪30年代末。当时英、美使用雷达作为防空系统的一部分在军事上对付德国的

空袭，从技术上没有问题，但是在实际运用中效果不理怛。为此，一些有关领

域的科学家把“如何合理运用雷达"作为一类新的问题进行研究。由于它与研

究技术问题不同，于是就称作“运作研究"。第二次世界大战期间，英、美军队

中成立了一些专门小组，面对一些实际问题开展了短期的和战术性的研究。例

如，雷达系统有效防空问题，研究设计将雷达信息传送给指挥系统及武器系统

的最佳方案。

运筹学(OperationsResearch,简称OR)，作为科学名字是出现在20世

纪30年代末。当时英、美使用雷达作为防空系统的一部分在军事上对付德国的

空袭，吸支术上没有问题，但是在实际运用中效果不理怛。为此，一些有关领

域的科学家把“如何合理运用雷达”作为一类新的问题进行研究。由于它与研

究技术问题不同，于是就称作“运作研究"。第二次世界大战期间，英、美军队

中成立了一些专门小组，面对一些实际问题开展了短期的和战术性的研究。例

如，雷达系统有效防空问题，研究设计将雷达信息传送给指挥系统及武器系统

的最佳方式、雷达与防空武器的最佳配置等；护航舰队保护商船队的编队问

题，研究当船队遭受德国军队攻击时如何使船队减少损失等；大西洋反潜战问

题，研究如何设计反潜舰艇或飞机投掷深水炸弹的最佳方案等。二次世界大战

后，在英、美军队中相继成立了正式运筹研究组织，以兰德公司(LAND)为首

的一些部门开始着重研究战略性问题。例如，为美国空军评价各种轰炸机系

统，讨论未来的武器系统和未来战争的战略等；研究苏联的军事能力及未来的

预报等。总的来说，在这段时间里运筹学的研究与应用范围主要是与战争相关

的战略、战术方面问题。随着世界性战争的结束，各国的经济建设迅速发展，

世界范围内的剧烈竞争也体现在经济、技术方面，运筹学的研究发展也向这些

方面拓展。由于运筹学适应时代的要求，在近六十年中，它无论从理论上还是

应用上都得到了快速的发展。在应用方面，今天运筹学已经涉及到了服务、管

理、规划、决策、组织、生产、建设等诸多方面，甚至可以说，很难找出它涉

及不到的领域。在理论方面，由于运筹学的需要和刺激而发展起来的一些数学

分支，如数学规划，应用概率与统计，应用组合数学，对策论，数理经济学，

系统科学等等，都得到迅速发展。

20世纪50年代中期，我国著名的科学家钱学森、许国志等将运筹学从西

方引入我国，并结合我国的特点在国内推广应用。自从引入以来，运筹学在我

国已有四十多年的历史。经过这四十多年，运筹学在我国有了很大的发展，确

立了它在经济建设中的地位。但是，运筹学在我国的发展状况与世界其它国家

相比，尚有不小的差距，其中最主要的是认识与基础的问题。

随着科学技术的发展，特别是信息社会的到来，运筹学的内涵不断扩大，

涉及的数学及其它基础科学的知识越来越多，于是熟练掌握并运用这门学科有

效解决实际问题的难度也逐渐加大。根据运筹学发展，数学、计算机科学及其

他新兴学科的最新知识、技术都能很快融合到其中，特别是人的直接参与决

策，使得运筹学发展更进入一个崭新阶段。

为了加强运筹学的研究与应用，国内外成立了许多学术性的组织。最早建

立运筹学会的国家是英国（1948年），接着是美国Q952年）、法国Q956年）、

日本和印度（1957年）等，到1986年为止，国际上已有38个国家和地区建立了

运筹学会或类似的组织。我国的运筹学会成立在1980年。1959年英、美、法

三国的运筹学会发起成立了国际运筹学联合会QFORS）,以后各国的运筹学会纷

纷加入，我国于1982年加入该会。此外还有一些地区性组织如欧洲运筹学协会

（EURO）成立于1976年，亚太母学协会（APORS）成立于1985年等。

二、解

运筹学在早期的应用主要在军事领域，二次大战后运筹学的应用转向民

用。经过几十年的发展，运筹学的应用已经深入到社会、政治、经济、军事、

科学、技术等各个领域，发挥了巨大作用。这里选择几个管理方面的应用给予

简单介绍。

1、生产运作：生产总体计划要求从总体确定生产、存贮^口劳动力的配合规

划以适应波动的需求计划。运筹学的应用主要在生产作业的计划、日程表的编

排、合理下料、酉群斗问题、物料管理等方面；

2、物资库存管理：多种物资库存的系统组织与安排管理，确定某些设备的

能力或容量，如停车场的大小、新增发电设备的容量大小、电子计算机的内存

量、合理的水库容量等。将库存理论与计算机的物资管理信息系统相结合，确

定合理的库存方式、计算最佳的库存量等；

3、物资运输问题：涉及空运、水运、公路运输、铁路运输、管道运输、厂

内运输。常常涉及班次和人员服务时间安排等，需要确定最小成本的运输线

路、物资的调拨、运输工具的调度等；

4、组织人事管理：对人员的需求和使用方面的预测，确定人员编制、人员

合理分配，建立人才评价体系、人才开发的规划、激励机制的研究等；

5、市场营销：广告预算、媒介选择、产品定价、新产品的引入和开发、销

售计划制定、市场模拟研究等:

6、财务管理和会计：各经济项目的预测、预算，贷款、成本分析、证券管

理、现金管理等。常使用的方法有统计分析、数学规划、决策分析、盈亏点分

析法、价值分析:蟾；

7、计算机应用和信息系统开发：运筹学中的数学规划方法、网络图论、排

队论、存储论、模拟与仿真方法等均起到巨大作用；

8、城市管理：各种紧急服务系统的设计和运用、城市垃圾的清扫、搬运和

处理、城市供水和污水处理系统的规划、区域规划、市区交通网络的规划与管

理等。

三、的相

随着运筹学的应用越来越广泛和深入，众多有识之士对运筹学将向哪个方

向发展、如何发展的问题进行了广泛和深入的研究。美国前运筹学会主席邦特

(S.Bonder)认为，运筹学应在三个领域发展：运筹学应用、运筹科学^运筹数

学。并强调发展前两者，从整体讲应协调发展。目前运筹学工作者面临的大量

新问题是：经济、技术、社会、生态和政治等因素交叉在一起的复杂系统。因

此，早在上一世纪70年代末80年代初就有不少运筹学家提出：要注意研究大

系统，注意运筹学与系统分析相结合。美国科学院国际开发署写了一本书，其

书名就把系统分析和运筹学并列。有的运筹学家提出了要从运筹学到系统分析

的报告：由于研究新问题的时间范围很长，因此必须与未来学紧密结合；由于

面临的问题大多是涉及技术、经济、社会、心理等综合因素的研究，在运筹学

中除常用的数学方法以外，还必须引入一些非经典数学的方法和理论等。美国

运筹学家沙旦(T.L.Saaty)在20世纪70年代末提出了层次分析法(AHP),并

认为过去过分强调细巧的数学模型，可是它很难解决那些非结构性的复杂问

题。因此宁可用看起来是简单和粗糙的方法，加上决策者的正确判断恰能解决

实际问题。切克兰特(P.B.Checkland)把传统的运筹学方法称为硬系统思考，

它适用于解决那种结构明确的系统以及战术和技术性问题。硬系统思考方法对

于结构不明确的，有人参与活动的系统无法很好地处理，这就应采用软系统思

考方法，相应的一些概念和方法都应有所变化，如将过分理想化的"最优解"

换成“满意解"等。

目前，运筹学领域工作者上匕较一致的共识是运筹学的发展应注重以下三个

方面：理念更新、实践为本、学科交融。

第二节的内容及特点

-运筹学的分支

我国运筹学的老前辈、中国工程院院士许国志教授等在1992年《运筹与管

理》杂志创刊号发表的“运筹学的ABC"一文提出了运筹学的三个来源是：军

事、管理和经济，同时还讨论了运筹学的三个组成部分：运用分析理论、竞争

理论和随机服务理论即排队论。

由于运筹学涉及到广泛的应用和有关的学科领域，经历数十年的发展形成

了其自身的各个分支。

线性规划是由美国运筹学工作者丹捷格(G.B.Dantzig)在1947年为解决

美国空军在军事规划问题时提出的。丹捷格提出了求解线性规划问题的单纯形

法。歹I」昂节夫的约在1932银合出了投入产出模型。冯・诺伊曼(VomNeumman)

和摩根斯坦(0.Morgenstern)合著的《对策论与经济行为》(1944年)是对^

论的奠基作，同时该书已隐约地指出了对策论与线性规划对偶理论的紧密联

系。回顾历史，为运筹学的建立和发展作出贡献的有物理学家、经济学家、数

学家、其它专业的学者、军官和各行业的实际工作者。

运筹数学的飞快发展，促使并形成了运筹学的许多分支。通常提到的有：

1线性规划

I非线性规则

1整数规划

I目规fell

1动态规划

J随机规划

J模糊规划等

以上人们常常统称之为数学规划，此外还有

I图论与网络

1排队论(随机服务系统理论)

1存贮论

I对策论

决策论

1搜索论

:I维修更新理论

排序与统筹方法

J可靠性和质量管理等

二、运筹学的定义及原则

为了更好地研究和应用，人们希望对运筹学给出一个确切定义，以便更加

深入地明确它的性质和特点。但是，由于本学科复杂的应用科学特征，至今还

没有统一且确切的定义。用以下几个比较有影响的定义来说明运筹学的性质和

特点。

为决策机构在对其控制下业务活动进行决策时，提供以数量化为基础的科

学方法(P.M.Morse&G.E.Kimball);

这个定义首先强调的是科学方法，重视某种研究方法要可以用于整个一类

问题上，并能够控制和进行有组织的活动，而不单是这些研究方法分散和偶然

的应用。另一方面，它强调以量化为基础，必然要用到数学理论和成果。我们

知道，任何决策都包含定量和定性两方面，而定性方面又不能简单地用数学表

示。如政治、社会等因素，只有综合多种因素的决策才是全面的。在这里，运

筹学工作者的职责是为决策者提供可以量化方面的分析，指出那些定性的因

素。

运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解

决实际中提出的专门问题，为决策者选择最优决策提供定量依据；

这个定义表明运筹学具有多学科交叉的特点，例如：综合运用数学、经济

学、心理学、物理学、化学等的一些方法。运筹学是强调最优决策，但是这个

‘最’是过分理想了，在实际生活中很难实现。

I运筹学是一种给出问题坏的答案的艺术，否则的话问题的结果会更坏；

这个定义表明运筹学强调最优决策过分理想，在现实中很难实现，于是用

次优、满意等概念来代替最优。

为了有效地应用运筹学，前英国运筹学学会会长托姆林森提出的下列六条

原则，得到众多运筹学工作者的认同：

(1)合伙原则。是指运筹学工作者要和各方面人，尤其是同实际部门工作

者合作；

(2)催化原则。在多学科共同解决某问题时，要引导人们改变一些常规的

看法；

(3)互相渗透原则。要求多部门彼此渗透地考虑问题，而不是只局限于本

部门；

(4)独立原则。在研究问题时，不应受某人或某部门的特殊政策所左右，

逊立从事工作；

(5)宽容原则。解决问题的思路要宽，方法要多，而不是局限于某种特定

的方法；

(6)平衡原则。要考虑各种矛盾的平衡，关系的平衡。

第三节运筹学的学习与应用

-运筹学研究的工作步骤

由于运筹学与许多的科学领域、各种有关因素有着横向和纵向的联系。为

了有效地应用运筹学，根据运筹学的特征，人们把运筹学研究的工作步骤归纳

为以下几个内容：

(1)目标的规定。确定决策者期望从方案中得到什么。这个目标不应限制在

过分狭小的范围内，也要避免把研究目标作不必要的扩大。

(2)方案计划的研制。实施一项运筹学研究的过程常常是一个创造性过程，

计划的实质是规定出要完成某些不壬务的时间，然后创造性地按时完成这一系

列子任务。这样做能够推动运筹学分析者做出结论，有助于方案的成功。若对

计划的任意延期和误时会导致分析者的消极工作和管理者的漠不关心。

(3)问题的表述。这项工作需要与管理人员的深入讨论，经常包括与其他职

员和业务人员的接触和必要数据的采集，以便了解问题的本质、历史及未来、

问题各个变量之间的关系。这项任务的目的是为研究中的问题内容提供一个模

型框架，并为全部以后的工作确立方向。在这里，第一要考虑问题是否能够分

解为若干串行或并行的子问题；第二要确定模型建立的细节，如问题尺度的确

定，可控制决策变量的确定、不可控制状态变量的确定、有效性度量的确定和

各类参数、常数的确定。

(4)模型的研制。模型是对各变量关系的描述，是正确研制成功解决问题的

关键。构成模型的关系有几种类型，常用的有定义的关系、经验关系和规范关

系等。

(5)模型求解。在这一步应充分考虑现有的计算机应用软件是否适应模型的

条件，解的精度及可行性是否能够达到需要。若没有现成可直接应用的计算机

软件，则献以下两步工作：

①计算手段的拟定。在模型研制的同时，需要研究如何用数值方法求解模

型。其中包括对问题变量性质(确定性、随机性、模糊性)、关系特征(线性，非

线性)、手段(模拟，优化)及使用方法(现有的，新构造的)等的确定；

②程序明细表的编制，程序设计和调试。对于计算过程需要编制程序来实

现计算机运算，运算学研究应包含算法过程的描述，计算流程框图绘制。程序

的实现及调试可以交由程序员完成，或会同程序员完成。

(6)数据收集。把有效性试验和实行方案所需的数据收集起来加以分

析，研究输入的灵敏性，从而可以更准确地估计得到的结果。

(7)解的检验(验证)。验证在运筹学的研究与应用中的重要性无论怎样强

调都不会过分。验证包括两个方面：第一是确定验证模型，包括为验证一致

性、灵敏性，似然性和工作能力而设计的分析和实验；第二是验证的进行，即

把前一步收集的数据用来对模型作完全试验。这样一种试验的结果，往往使模

型必须重新设计，并要求相联系的重编程序。

(8)解方案的实施。有些人认为，在模型验证后任务就完成了，这是不对

的。事实上，一项研究的真正困难往往在解方案实施的这最后一步。很多问题

常常在这时暴露出来，他们会涉及到研制方案的全过程。因此，必须由参与整

个过程的有关人员参与才能解决。

二、鳏的T,函

运筹学建模在理论上，应是属于数学建模的一个部分。因此，运筹学建模

所采用的手段、途径与一般在数学建模中所采用的类似。下面介绍的是根据运

筹学本身的特征来处理建模问题的一般思路。

经过长期、深入的研究和发展，运筹学处理的问题归纳成一系列具有较强

背景和规范特征的典型问题。因此，运筹学建模就要把相当的精力放在将实际

问题合理地描述为某种典型的运筹模型上。在这个过程中,T殳要求运筹学工

作者具有以下几个方面的知识和能力：

(1)熟悉典型运筹模型的特征和它的应用背景；

(2)有分析、理解实际问题的能力，包括广博的知识、搜集信息、资料和数

据的能力;

(3)有抽象分析问题的能力，包括善于抓主要矛盾，善于逻辑思维、推理、

归纳、联想、类比等形成的创新能力；

(4)有运用各类工具知识的能力，包括运用数学、计算机、其它自然科学的

知识和工程技术等的能力；

(5)有试验校正和维护修正模型等的能力。

根据问题本身的情况，运筹学在解决问题时，按研究对象不同可构造各种

不同的模型。模型是研究者对客观现实经过思维抽象后用文字、图表、符号、

关系式以及实体描述所认识到的客观对象。模型的有关参数和关系式比较容易

改变，这样将有助于问题的分析和研究。利用模型可以对所研究的问题进行一

定预测及灵敏度分析等。

目前运筹学中用得最多的是符号或数学模型。建立、构造模型是一种创造

性劳动，成功的模型往往是科学和艺术的结晶，常见的构模方法和思路有以下

丽

(1)直接分析方法。当我们对问题的内在关系、特征等比较熟悉时，可以根

据对问题内在机理的认识直接构造出模型。运筹学中已有不少现存的模型，如

线性规划模型、投入产出模型、排队模型、存贮模型、决策和对策模型等等。

这些模型都有很好的求解方法及求解的软件。有时模型的参数也可直接从问题

本身得到。

(2)类比方法。通过对问题的深入分析，结合经验，常常会发现有些模型的

结构性质是类同的。这就可以互相类比，通过类比把新遇到的问题用已知类似

问题的模型来建立该问题模型。这种情况往往得到的是模型归类，而模型参数

需用其它的方法取得。

(3)模拟方法。利用计算机程序实现对问题的实际运行模拟，可得到有用的

数据。这些数据常用来求得模型参数或对所建立模型进行合理性、正确性的检

验。

(4)数据分析法。利用数据处理的方法分析各数据变量之间的关系是确

定关系，还是相关关系，以及是何种相关等。这种方法还可以用回归分析找出

变量的变化趋势，从而得到合理的数学模型。大量的模型参数求得也常常使用

数据处理的统计方法。另外，回归模型常常就是一个无约束最优化模型。

(5)试验分析法。通过试验分析建模是工程管理中常用的方法。这类方法是

以局部的试验产生数据，经过统计处理得到总体的模型或模型归类。试验分析

更多地用于产生模型参数。

(6)构想法。当有些问题的机理不清，既缺少数据，又不能作试验来获得数

据时，例如一些社会、经济、军事问题等。这种情况下，人们只能在已有的知

识、经验和某些研究的基础上，对于将来可能发生的情况给出逻辑上合理的设

想和描述，然后用已有的方法构造模型，并不断修正完善，直至比较满意为

止。这种方法基于人们的构想。

三、如好运筹学

运筹学是一门基础性的应用学科，主要研究系统最优化的问题，通过对建

立的模型求解，为管理人员作决策提供科学依据。本课程是管理类专业的必修

基础课，为学习有关专业课打好基础，进而为学生毕业后在管理工作中运用模

型技术、数量分析及优化方法打下良好的基础。本课程的主要任务是：

①要求学生掌握运筹学的基本概念、基本原理、基本方法和解题技巧；

②培养学生根据实际问题建立运筹学模型的能力及求解模型的能力；

③培养学生分析解题结果及经济评价的能力;

④培养学生理论联系实际能力及自学能力。

通过教学，培养学生严谨的学风及勤奋刻苦的学习态度和科学的协作精

神。

为了帮助有关人员更好地学习运筹学，根据著者多年的教学实践和体会，

提出如下的一些建议，仅供参考。

学习运筹学要把重点放在分析、理解有关的概念、思路上。在学习过程

中，应该多向自己提问，如一个方法的实质是什么，为什么这样做，怎么做

等。

在认真听课的同时，学习或复习时要掌握以下三个重要环节：

(1)、认真阅读教材和参考资料，以指定教材为主，同时参考其他有关书

籍。一般每一本运筹学教材都有自己的特点，但是基本原理、概念都是一致

的。注意主从，参考资料会帮助你开阔思路，使学习深入。但是，把时间过多

放在参考资料上，会导致思路分散，不利于学好。

(2)、要在理解了基本概念和理论的基础上研究例题，注意例题是为了帮助

你理解概念、理论的。作业练习的主要作用也是这样，它同时还有让你自己检

查自己学习的作用。因此，做题要有信心，要独立完成，不要怕出错。因为，

整个课程是一个整体，各节内容有内在联系，只要学到一定程度，知识融会贯

通起来，你做题的正确性自己就有判断。

(3)、要学会做学习小结。每一节或一章学完后，必须学会用精炼的语言来

叙述该书所学内容。这样，你才能够从较高的角度来看问题，更深刻的理解有

关知识和内容，这就称作“把书读薄"。若能够结合自己参考大量文献后的深入

理解，把相关知识从更深入、广泛的角度进行论述，则称之为"把书读厚”。

第二章线性规划问题及单纯形法

教学要求：1.通过图解法了解线性规划的结构

2.了解线性规划的基本概念与性质

3.单纯形法的理论基础

4.单纯形法的主要过程、单纯形表的构造

5.确定初始可行基的人工变量法、人工变量法

重点：图解法的解题过程，线性规划的基本概念与性质，单纯形法的理论基础

和主要过程，人工变量法的使用。

难点：单纯形法的理论基础。

第一节问题的提出

例1.1生产安排问题。某工厂可生产两种产品，每单位产品所需要的资

源(设备和原料)，所创造的利润,以及工厂每天能提供的各种资源的总量由表

1.1给出。工厂应如何安排两种产品的生产量，才能获得最大的利润？

表1.1

产品I产品n资源总量

设＞（等寸）128

府斗A（公斤）4016

府斗B（公斤）0412

利润（百元）23

分析：1、工厂需要决定每天安排两种产品的产量，在模型中我们用变量表

示，即设每天安排生产产品工、II的数量分别为Xi,X2o这样，变量组（X1,X2

）,或者说向量X=（XLX2）T（以列向量表示）就表示了一种生产方案，称这样的

变Xi,X2为决策变量，相应的向量X为决策变量，X体现了解决问题的一个方

案。

2、需要有一个衡量方案X优劣的指标，在这个问题中，这种指标可用函数

Z=2xi+3X2给出。称这样的函数为目标函数。在这里目标函数值Z为工厂按方

案X=（XI,X2）T生产时，每天可获得的利润。

3、一个可以实施的方案X必须符合工厂所能提供的各种资源量的制约，因此,

中的决策变量X-X2必须满足某些条件，这些条件可用不等式表示，即

设备约束：x1+2x2n8

原料A的约束：4X116

原料B的约束：4x212

称以上不等式为约束条件。

4、根据问题的实际意义有xi,X20,称这一条件为（决策变量的）非负约

束。

5、工厂的目标是选取一个方案X*,在该方案X*下的生产可获得最大的利润

Z*,也就是说要在所有满足约束条件和非负约束的X中，选择一个X*,使相应

于X*的目标函数值Z*达到最大。

这样，该问题的数学模型可用下述的数学结构表示：

maxZ=2XI+3X2

2x8

4X]16

4X2112

l%i,x20

从上述的例子看出，建立数学模型的基本过程是：

1设置决策转；

2给出目标函数；

3确定约束条件和非负约束；

4确定目标函数的优化方向，即优化是对目标函数取最大还是最小。

例1.2任务分配问题。某公司拟生产4种产品，可分配给下属的三个工厂

生产，由于工厂的地理位置和设备不同，每个工厂生产每种产品的成本不相

同，加工能力也不相同。有关数据分别由表1.2和表1.3给出。公司应如何给

下属各工厂分配任务才能保证完成每种产品的任务的条件下，使得公司所花费

的成本最少？

表1.2单位产品成本表

1234

123211917

222202519

319162123

产品产量60805040

表1.3单位产品所需机时表

加工能力

1234

X（日擞）

15253320

24263480

33264280

该例主要说明如何确定约束条件。

例13资金借贷问题。某工厂计划在三个月内开发一项新产品，有A,

B两个型号，目预计第一批至少有A型产品50件，B型产品25件投A市场。由

于在产品开发期间必须支付成本费用，而当产品投入市场后才能获得收益，现

工厂可用于产品开发的内部资金仅有3万元，故需向银行贷款。银行同意给该

厂总数不超过10万元的三个月短期贷款，年利率为12%,同时附加如下的信贷

保证：工厂三个月后的资金（含产品的应收款）不得少于贷款的及应付利息之

和的两倍。关于产品开发的其他数据由表L4给出。在这样的情况下，工厂应

如何考虑产品的生产与向银行贷款的数额？

表1.4

单位产品所需时

单位成本单位售价

产品型号

（元）（元）

组装调试包装

A121500580

B25210001200

加工能力2500150

该例主要说明如何设置决策变量以有利于给出目标函数和确定约束条件。

由于应用贷款生产产品需要支付利息，这就相当于增加了产品的单位成

本，止忸攫号A,B白婵分别为500xl2%+4+500=515方口1030元这

样，在建立数学模型是我们应当考虑应用自有资金和贷款资金生产出的产品间

的差别，为此,设置决策变量如下：

xi:用自有资金生产A型产品的数量,

x2:用贷款资金生产A型产品的数量,

X3:用自有资金生产B型产品的数量，

X4:用贷款资金生产B型产品的数量.

例1.4酣斗问题。某糖果厂用原料A,B,C加工生产三种牌号的糖果。

各种牌号的糖果中对原料A,B,C含量的限制、原料成本、加工费用和售价和

每月原料限量由表L5给出。该厂如何安排生产，才能获得最大利润？

表1.5

含量限制原料成本原料限量

原料

（元/公斤）

牌号1牌号2牌号3（公斤/月）

A口60%U15%无62000

B无无无4.52500

c120%□60%50%31200

加工费(元/公

1.51.20.9

斤)

售价(元/公斤)

15128

该例主要说明较复杂问题的建模。

从上面的例题可以看出，虽然每个问题的实际背景互不相同，但是它们的

数学模型却具有相同的结构，即

(1)存在一组决策变量，对它们可有非负要求；

(2)存在一个以决策变量为自变量的目标函数，且它为线性函数；

(3)存在一组约束条件，且每个条件都是由决策变量构成的不等式或等

式；

(4)结构要求求出这样的变量组，或者说决策向量X,在X满足约束条件

和非负约束的同时，使相应的目标函数值达到最大或者最小。简言之，在一定

条件下使目标函数优化。

称这种数学结构为线性规划，具有这种结构的数学模型为线性规划模型。

线性规划模型的一般表达式为：

max(min)Z。的口c2x2-…g%

为内aux2…aln^](口⑼，

1

氏内口a2xJIa2nx(Ul)t>2

La血为।a成X2口c，D0

XjL0,/L1,2Mn

其中X1,X2,…,Xn为决策变量，其余的量Cj,bi和aij都是常量。

在某些情况下，线性规划模型中也可只对部分决策变量，甚至于不对决策

变量提出非负要求。如前所述，较为复杂的经济管理问题常表示为从众多的方

案（当然，这些方案要满足一定的条件）中，选取一个方案（即决策），使它具

有最好的效果。因此，线性规划模型为经济管理决策提供了一个重要的、有效

的数学工具。

在线性规划问题求解时，我们应当在满足约束条件和非负条件的所有决策

向量中寻找。为此给出如下定义，称满足约束条件和非负条件的决策向量为该

问题的可行解，称全体可行解构成的集合为可行域，常用D表示。称使目标函

数到达最优的可行解为最优解，最优解对应的目标函数值为最优值。所谓求解

线性规划问题是指求出该问题的最优解，或者判断出该问题没有最优解。

第二节图解法

具有两个决策变量的线性规划问题是最简单的线性规划问题，它可用图解

法求解.通过对这种简单的线性规划的讨论可揭示一般线性规划问题的重要特

征，从而寻求求解线性规划问题的方法。

首先通过例子说明两个决策变量的线性规划问题的图解法。

例1.5求解线性规划问题

maxZ=xi+3x2

-Xi+x2<6

-XI+2X2<8

XI>0,X2>0

我们知道，在直角坐标系下，方程aixi+a2x2=b表示平面中的一条直线，不

布aixi+a2x2<b或aiXi+a2X2>b表示一个半平面。当我们在同一平面内表示

出所有约束条件和非负约束表示的半平面时，这些半平面的交集（即公共部

分）就构成了线性规划问题的可行域。

目标函数等值线

图1.1

最优解Z=（4/3,14/3y,最优值为2=46/3。

结论一、线性规划问题的解仅存在以下四种状态，即

1有渴优

2有无穷多个最优解，它们具有相同的目标函数值；

3有无界可行解，或者说无最优解；

4无可行解。

结论二、当线性规划问题的可行域D为空集）时,该问题无可行解。当D

不等于空集时，D为凸集，且若该问题有最优解时，最优解可在D的顶点上达

到。

第2次谡2学时

上次课复习：

线性娥（1一般形式及特点；

线性规划图解法。

本次课题（晦阚＞节题目）：§1.2线性^划解的基本邮

教学要求：掌握线性规划解的基本性质、基可行解的概念及LP解的性质

重点：线性规划的特点、基可行解的概念及LP解的性质

难点：线性规划的基本性质、基可行解的概念。

教学手段及教具：多媒体教学。

讲授内容及时间分配：

上次课复习5分钟

2.1基本概念40分钟

2.2基本定理45分钟

课后作业P441.2(1),1.3

《运筹学》钱颂迪主编清华大学出版社

《运筹学教程》胡运权主编清华大学出版社

参考资料

《运筹学》牛映武主编西安交大出版社

《运筹学应用案例》陶谦坎主编机械工业出版社

第二节线性规划解的基本性质

两个决策变量的线性规划问题的图形解法简单直观而且有效，但这种方法

不能求解一般意义下的线性规划问题，通过对图解法的讨论，我们已在直观上

看到了线性规划问题的一些重要特征，现在再从代数的角度分析这些特征，以

求得线性规划问题的求解方法。

线性规划问题的标解可写成矩阵形式:

maxzlCX

AXb

X0

设Xji,xj2，…，xjm为线性规划问题中的m个变量，若它们对应的系数

向量h,Pj2，…，Pjm，线性无关，则称矩阵

B=[Pjl,Pj2Pjm]

为该线性规划问题的一个基，称Xji,Xj2Xjm为对应于基B的基变量，其

他变量为（对应于B的）非基变量。

设B为线性规划问题的任意一个基，令所有的非基变量为零，就可得到一

个以Xji,Xj2Xjm为未知量的线性方程组，根据线性代数的基本理论，由

B为可逆矩阵，该方程组有唯一解。这样，根据基B可构造出一个满足约束条

件AX=b的X,称X为对应于B的基解。

在基本解中非基变量的取值为零，若还有基变量取值为零，即解X中的非

基分量的个数小于m,称该基本解为退化解。

同时满足非负条件的基解称为基可行解，基可行解对应的基称为可行基。

线性规划具有如下重要的基本性质,

1线性规划问题的可行域为凸集。

2若线性规划问题有可行解，则它必有基本可行解。

3线性规划问题的基本可行解对应于它的可行域的一个顶点。

4若线性规划问题有最优解，则最优解可在它的可行域的某个顶点达

到。

定理的证明中要突出说明线性规划中的一些概念，需要应用到线性代数和

数学分析的基础知识。具体有：

性质1：可行解,集合等相关概念

性质2:应用向量相关性讨论，应用数学分析中的方法，用构造法证明

性质3:应用基本概念，反证法证明

性质4:应用最优解概念和性质的证明方法

线性规划的这些基本性质为求解方法提供了坚实的理论基础。

第3次课_____

上欠课复习：

线性规划的标准形式、特点；

基可行解的概念。

本次课题（或教材章节题目）：§13线性规划问题的单纯形法

教遇求：掌握单纯形法的解弱思路、单纯形法要点和单纯形表

重点：单纯形表；单纯形法则

难点：初始单纯形表；换基迭代法则

教学手段及教具：多媒体教学。

讲授内容及时间分配：

上次课复习及作业10分钟

§13.1单纯形法的解题思路40分钟

§1.3.2单纯形法要点和单纯形表40分钟

课后作业P44L4(1)、(2)

《运筹学》钱颂迪主编清华大学出版社

《运筹学教程》胡运权主编清华大学出版社

参考资料

《运筹学》牛映武主编西安交大出版社

《运筹学应用案例》陶谦坎主编机械工业出版社

第三节线性规划问题的单纯形法(一)

单纯形法是G.B.Dantzig在1947年给出的求解线性规划问题的方法，至今

它仍是求解线性规划问题的主要方法。单纯形法的核心工作是：判定一个基本

可行解是否最优解。在它不是最优解时，寻求一个改进的基本可行解。这样单

纯形法是一个迭代过程，如果最优解存在，可在有限次迭代后求得。因此单纯

形法是一种有效算法且便于在计算机上实现。

线性规划问题的标准形矩阵形式为：

mzxzCX

AXb

X口0

若B为它的一个基，不失一般性，可设B为A中前m列元素构成的子矩

阵。根据B,将A,C,X写成分块矩阵，得：

Xb

>401B,NCCBICNX

~XN~

在AX=b的两端左乘BL得：

11

8MXB(BXeNX"XBBNXNB】b(1.4)

因羊，

1111

Z=CX=CBXB+O^=CB(B-b-BNXN)+CNXN=CBB-b-(CBB-N-CN)XN

(1.5)

或者有Z-CX=O,上式■^为：

2+(朋1!\1<^4=侬为(1.6)

称(1.4)、(1.6)式为线性规划问题对应于基B的正规方程组,(1.5)式

为相应于B的目标函数方程。

令非基变量XN=0,由(1.4)式，XB=B』b,从而对应于B的基本解为。

X。

0

在满足条件

B-ib>0(1.7)

时，X为基本可行解，B为可行基。称(1.7)式为可行条件。

令

X

i"CN口口"1，.2，口J^,ZB□CBBb,

(1.5)式可改写为：

Z.ZB.|nXj

jm\l

根据上面分析可得如下结论：

最优解判定定理设B为可行基，如果向量IN20,则B对应的基本解X

为线性规划问题的最优解，目标函数的最优值为Z=CBB-Ib。

定理表明，向量N在判定一个基本可行解是否为最优解中起着至关重要

的作用。为此，称1N的分量mik为对应的非基变量Xm+k的检验数，在每个非基

变量的检验数都为非负数时，我们就得到了最优解。

T殳情况下，设B为一个基(不一定为可行基)，称条件

CBB^N-CN^O(1.8)

为优化条件。这样，上面的定理可表述为：

若基B满足可行条件和优化条件，则B为最优基。

进f正明以下定理：

设B为可行基，X为相应的基本可行解，如果

1.对每个j=m+l,m+2,…,n,都有匕口0,则X为线性规划问题的唯一最

优解；对每个j=m+l,m+2,…,n,有I小0，但存在口10,若Z。非退化，则

线性规划问题有无穷多最优解。

2.存在」m-0，且矩阵B-1N中的第k个列向量

，则线性规划问题无有界最优解。

3设B为可行解，相应的基可行解*非退化，若存在非基变量期的检验

数k。，且水,匚侬了，中存在可行基8,相应的基可行解为7,使

得

exexo

上述定理的证明要充分利用到线性代数中分块矩阵及性质，分析重点为最

后一个结论，证明方法为构造法，此时，需求得一个改进的基本可行解，这一

过程称为换基运算。需要从原基的非基变量中选取一个变量所作为新基的基变

量（称之为换入变量），从原基的基变量中确定一个变量刈使之成为新基的非

基变量（称之为换出变量），一个重要的结论是选择的原则是（称为最小

xHe

准则）

但也

Imin

出尸）1n（B】P0

讲述中要重点分析这一原则及证明新基为可行基。

换基运算有以下步骤：

L选取换入变量：原则上，换入变量可在具有负检验数的非基变量中任

意选取，但通常的方法是选取一个具有负检验数且绝对值最大的非基变量作为

换入变量，称之为最大。准则。其目的是使目标函数值增加的较快，以有可能

减少迭代次数。

2.确定换出变量：为保证新基为可行基，换出变量不能任意选取，按最

小e准则。

3.求新基下的基本可行解

根据上述的基本理论，单纯形法的基本步骤为：

1求初始可行基；求B满足可行条件B-!b>0;

2优化检3佥；若优化条件CBB1N-CN>0成立，已得最优解，否则换基运

算；

3换基运算：设4为换入变量，在矩阵B』N中对应于XL的列向量为

T

(an,a2i,-ami),BIb=(阮，氏，…即儿

如果每个aki<0,i=l,2,...m,,则表明线性规划问题无有限最优解，否则按最

小6准则，取原基的第k个基变量Xk作为换出变量，称aki为主元素,换基

运算可

通过矩阵的初等变换实现。

第4次谟2学时

第三节线性规划问题的单纯形法（二）

上欠课复习：

单纯形表；

单细缄5!!1;

讲解作业存在问题。

本次课题（或教材章节题目）：§13线性规划问题的单纯形法

教学要求：掌握无穷多最优解与唯一最优解的判别法则、无最优解（无界解）的判定法

则；

掌握求minz的情况。

重点：单纯形判别法则

难点：单纯形判别法则及证明；求minz的情况。

教学手段及教具：多媒体教学。

讲授内容及时间分配：

上次课复习及作业20分钟

1.无穷多最优解与唯一最优解的判别法则25分钟

2.无最优解