运筹学基础及应用

管理运筹学计划学时31

课程名称

教材名称运筹学基础及应用出版时间1998〜2002

教材哈尔滨工业大学出版

作者胡运权出版社

社

MBA《管理数学（下）一运筹学》

清华大学出版社

指定参考书《运筹学习题集》胡运权出版社

机械工业出版社

《运筹学应用案例》陶谦坎

课程性质、目的与基本要求

此门课程目的在于介绍现代管理的技术和方法，为管理类其它分支如企业管理、人力资

源管理、组织行为学、战略管理、运作管理、财务管理、项目管理、服务管理、公共管理等

学科提供技术和方法的支撑；同时，也为经济研究和其它学科的研究，提供有效的研究工具。

内容与学时分配

0绪论（2学时）

介绍运筹学产生、发展、现状和未来以及运筹学的方法论——系统观和辅助软件工具，

如Lindo,lingo,excel。

第一章线性规划及单纯形法（5学时）

介绍线性规划的建模、线性规划的几何意义、单纯形法的理论和算法、线性规划的经济

意义和在投资、资源计划等经济管理实践中的案例及应用。

第二章对偶理论和灵敏度分析（3学时）

介绍对偶问题的经济学含义（市场博弈）和经济解释（影子价格一边际收益和机会成本）、

对偶理论、对偶单纯形法、参数规划。

第三章运输问题（3学时）

介绍物流管理中的运输网络的建立和运行方案优化，包括铁路、公路、航空、海运中的

物资调运计划。

第四章整数规划（2学时）

介绍分枝定界法、0—1整数规划、互斥投资方案决策、工作分派问题及应用。

第五章目标规划（2学时）

介绍目标规划的模型、图解、单纯形法、灵敏度分析，以及目标管理、项目管理和经济

中的具体案例和应用。

半期考试

第六章动态规划（6学时）

介绍动态规划的原理和模型、最短路问题、静态规划的动态规划法求解。

动态规划的应用：介绍动态规划在多周期投资、多周期生产计划、资源配置中的应用。

第七章图与网络分析（6学时）

介绍基本概念、树、最短路问题、最大流问题、中国邮递员问题等。可用于交通网络建

设、石油运输管线设计、电网设计、城市供水系统设计、大型商业连锁网点设计和经济影响

因素识别。

第八章管理决策理论简介（2学时）

管理决策的基本概念和初步方法。

第九章对策论（博弈论）（自学）

介绍对策论基础及解法及信息经济的有关内容。可用于经济研究中的寻租行为分析、委

托代理关系的分析、企皿联盟的效益分配等。

《管理运筹学》讲义

绪论

第一章线性规划

第二章线性规划的对偶理论和灵敏度分析

第三章运输问题

第四章整数规划与分配问题

第五章目标规划（GP）

第六章网络优化

第七章动态规划

第八章决策分析

第九章对策论（博奕论）

绪论

1.运筹学的成长之路

运筹学产生于西方，其中文译名源于《史记•汉高祖本纪中》中刘邦赞扬张

良的一段话：“夫运筹帷幄之中，决胜千里之外，……”。

作为我国运筹学和系统工程创始人之一的许国志先生关于运筹学的“三（三个

来源：军事、经济、管理）、三（三个组成：运用分析理论、竞争理论、服务理论）、

-（一种方法论：系统方法论）”曾经做出了深刻阐释，对于后学者了解运筹学的

产生和发展颇有启迪。许老的这篇论述——“运筹学的A、B、C”载于《运筹与管

理》的创刊号（1992年1月），初学者不妨找来一读。

图o.1运筹学的“三、三、一”

尽管运筹学诞生于西方，但中国古代先贤却并不缺乏今天为人称颂的那些运筹

思想。

1981年，美国军事运筹学会出版"SystemsAnalysisandModeling…”-书，

称孙武子是世界上第一位军事运筹学的实践家。在孙子质的推理中，渗透着深刻的

量的分析和运筹学的方法论——系统观。

“课攻”：知已知彼，百战不殆；不知彼而知己，一胜一负；不知彼不知己,

每战必殆。

“战篇”：孙子日：凡用兵之法，驰车千驷，革车千乘，带甲十万，千里馈粮。

则内外之费，宾客之用，胶漆之材，车甲之奉，日费千金，然后十万之师举矣。其

用战也，胜久则钝兵挫锐，攻城则力屈，久暴师则国用不足.....

善用兵者，役不再藉，粮不三载，取用于国，因粮于敌，故军食可足也。国之

贫于师者远输，远输则百姓贫；近师者贵卖，贵卖则百姓财竭，财竭则急于丘役。

力屈中原，内虚于家，百姓之费，十去其七；公家之费，破军罢马，甲胃矢弓，戟

盾矛橹，丘牛大车，十去其六。故智将务食于敌，食敌一钟，当吾二十钟；杆一

石，当吾二十布。.....

“计篇”：道、天、地、将、法夫未战而庙算胜者，得算多也；未战而庙

算不胜者，得算少也。多算胜少算，而况于无算乎！吾以此观之，胜负见矣。

——《孙子兵法》（公元前六世纪，春秋时期）

齐王赛马的故事载于《史记•列传第五》，其中无疑闪耀着对策中论及的智慧。

粮食贮运是历朝关注的大事。然而公元前54年汉宣帝时，就比较好地用到了今

天运筹学中解决运输和物流中心选址问题才提出的优化思想。可从史料中寻到的描

述是：由于将关东经水运到长安的运粮路线改为长安附近的弘农、上党、太原等地

就近供应，不仅省掉一半以上的劳力，而且通过设置常平仓，保障了粮食的储备和

供应。

还有一个关于粮食收购的事发生在明神宗时期。

明神宗万历三巳年冬，仓谷殆尽，抚台令各州县用库银2000两买谷，时谷价涨

至每石六钱，而官价仅五钱。开州知府陈霁岩拒不执彳亍。待到庚午年秋（第二年秋），

开州大熟，谷价跌至二钱五，此时才上报巡抚，仅用官银千两，价三钱，就比去年

各州县的总收购量还多，且开州民众深受其益

-《智囊全集》K明H冯梦龙，第二部明智•经理时务•陈霁岩

陈霁岩在进行粮食收购中所采取的策略，既是今天粮食收购保护价政策的早期范本,

乂体现了现代运筹学中两阶段决策问题的处理思想。

宋真宗祥符年间，宫中大火，丁谓主办营建修复宫室。先挖街取土修复宫室，

再将汴水引入挖街后形成的沟壑中使利于建材的长途运输，最后，修复宫室后剩下

的建渣回填沟壑重新还原街道。史称此项工程为“一举而三役济。”以今人的眼光

看，不能不说是运筹学尊崇的系统优化思想的完美体现。

国外古、近代的一些大学者如阿基米得、伦纳多•达•芬奇、伽利略等对

运筹学，特别是军事运筹学的思想和方法的萌芽也有诸多裨益。20世纪初，运筹学

的雏形开始在西方显现。

1909年，丹麦工程师Erlang在哥本哈根电话公司研究电话通讯系统时，发表

了排队论方面的第一篇论文“概率论与电话会话”，从而开创了运筹学分支——排

队论的研究领域。一般认为排队论是研究随机服务系统的一门学科，主要研究各种

伺服系统的统计规律性。

存储论的产生和发展可追溯到19世纪末对银行保持流通现金最佳数量即储备金

的研究。1915年，Harris将这些研究应用于物资订购的最佳批量问题之中。20世

纪五十年代，T.M.Whitin和Arrow,Moran等人的工作奠定了存储论的科学地

位。存储论研究的问题相当广泛，资金储备、材料储存、订货、物资管理系统设计、

仓库管理、人才储备和使用、自然资源合理开发等等。

1916年，英国的兰切斯特仔细研究了19世纪拿破仑时期的英、法、西班牙

Trafalgar海战这一经典的以弱胜强的战例，揭示了“纳尔逊秘诀”中的兵力配置

与胜负的关系，建立了最早的军事运筹模型。

1935〜1938年间，英国为对付德军的空中威胁，在东海岸的Bawdsey成立了

Rowse领导的研究小组。Rowse把这种对战术效率的研究，赋予了"Operational

Research"的名称。这就是运筹学西文名的由来。Bawdsey也由此成为了现代运筹

学的诞生地。美国人很快注意到战争中运筹学的价值，从而也逐渐建立起了各种运

筹研究小组,并命名为uOperationsResearch或OperationsAnalysisv0

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

堪称运筹学的先驱名著之一。其中已提到类似线性规划的模型和“解乘数求解法”。

但是他的工作直到I960年的《最佳资源利用的经济计算》一书出版后，才得到重视。

1975年，康托洛维奇与T.C.Koopmans一起获得了诺贝尔经济学奖。

1944年，VonNeumann和经济学家Morgenstern分析了经济活动中的冲突、

协调、平衡的问题的特征，写出了《对策论与经济行为》一书，奠定了对策论研究

的早期基础。

1947年G.B.Dantzig在研究美国空军军事规划时提出了线性规划的模型和

单纯形解法。并很快引起美国著名经济学家Koopmans的注意，Koopmans为此呼吁

当时年轻的经济学家要关注线性规划。今天，线性规划已成为了运筹学的一个极为

重要的部分。

二战后，英美等国相继组建了更为正式的军事运筹学研究组织，并以兰德公司

(Rand)为首的一些部门开始研究战略性问题。同时，政府和工业部门也开始推行

运筹学的方法。到二十世纪五十年代末，英美两国儿乎所有的工业部门都组建了相

应的运筹学组织。1959年，英、美、法三国运筹学会发起成立了国际运筹学联合会

(IFORS),到1992年，它已包括41个国家和地区。

我国现代运筹学研究始于1956年，在钱学森先生的倡导下，成立了由许国志先

生领导的国内第一个运筹学研究室，并迅速在国内形成了运筹学应用研究的高潮。

返聘体系

存『论||图与网络||排「论||数学、划||对「论||决「论||可靠「理论

-------।/-------

线性规划卜•｛非线性规划11整数规划卜T目标规划

动态规划山随机规划几何规划卜

图Q.2运筹学的体系

时至今日，运筹学已经成为了拥有众多分支的一个学科体系（图0.2）,并与系

统工程密不可分，在应用上逐渐趋向于研究和解决经济管理中大量复杂系统的问题。

2.运筹学的目的和使命

按照《大英百科全书》的解释：“运筹学是一门应用于管理有组织系统的科学”，

“运筹学为掌管这类系统的人提供决策目标和数量分析工具”。因而，运筹学创立

的目的就是为了把科学知识和方法应用于对复杂系统问题的研究中，为实现组织目

标的决策流程提供数量分析基础。在英国为解决战争中关于防御和全球后勤供应有

序化的复杂问题而组建其第一支运筹研究队伍时.，美国的工业企业和一些私人咨询

公司也已开始认识到，运筹学的方法可以应用于非军事性质的问题。私人咨询企业

阿瑟・D•利特尔有限公司，就是最早探索把运筹学用于工业的公司之一。1953年,

管理科学研究所（TIMS）宣称其目标就是“确立、拓展、运用有助于理解管理实践

的科学知识”。因此，运筹学的使命就存在于其实践性之中。

然而，要完成这一使命并非易事。对于过去的大多数人而言，运筹学的语言就

象巫医用的偶像一样，让人莫名其妙。建立模型的仪式（如果称之为仪式的话）、

仪式中所用的数学符号、令人生畏的咒语般的求解，往往激发初学者的敬畏之情。

尽管如此，运筹学作为一门科学，它的来源、组成和方法论都绝非具有如巫术般的

非科学性。因此，在科学精神和使命的指引下，勇于承担使命者在至今的50到60

年间，就构建起了庞大的理论体系、方法体系和技术体系（求解过程的软件化）。

这三个体系为完成运筹学的使命奠定了深厚的基础，并使对运筹学的学习和研究具

备了相当完善的框架。

今天，实践性使命已将运筹学推向了极为广阔的应用范围，实践的发展使得运

筹学的内涵和外延在不断地更新和变化！它的应用范围已遍及社会、经济、管理、

军事、生态等诸多领域，并在本质上（由于其目的和使命使然）显示出相当惊人的

多学科交叉性、交融性。

3.运筹学的工作流程和原则

图0.3运筹学的工作流程

运筹学的工作流程包含了整体系统优化、多学科配合、模型分析和信息技术应用四

个特

点。其基本流程可由图0.3表述,

其中，常用的工具软件有

•Lindo,Lingo：

http://www.lindo.com/cgi/frameset.cgi?left.html;main.html

•Excel

•Mathematics

•Matlab

•Maple

•SAS、SPSS

在建立系统模型的过程中，首先值得注意的是对实际问题的抽象、简化、假设

等前期的工作。这工作的质量好坏直接影响到模型的质量优劣；其次，模型的可处

理性也要予以适当的注意。尽管运筹学的理论、方法和软件工具已具备相当强的功

效，但它们仍不足以解决所有的模型计算工作，而实践问题对时效性乂往往有较高

的要求。因此，研究者必须考虑是否有能力处理所建立的模型；其三，建模过程还

应关注艺术性和系统性。事实上，建模一词，从英文“Modeling”本身看，就具有

艺术的含义，模型在本质上就是关于所研究问题的一幅“漫画”。同时，对实际问

题作出系统思考，是建模的基本要求，它允许依据新的信息作出反馈和不断修改；

最后，对模型的结果分析要极为重视，因为这是模型实践意义的直接体现部分。研

究者要与专业工作者、决策者一道进行深入、细致的分析，才能提出合理、有效的

建议和方案。

为了更有效运用这个工作流程解决实际问题，前英国运筹学会会长托姆林森提

出了六项原则：

(1)合伙的原则。运筹学的工作者应与各方面的人合作，尤其应与专业和实际

部门的人合作。

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

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

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

（5）宽容原则。解决问题的思路要宽，而不应局限于某种特定的研究方法。

（6）平衡原则。要考虑各种矛盾的平衡、关系的平衡。

这六项原则对运筹学的实践者有着较强的指导意义。

4.运筹学与DSS（决策支持系统）

运筹学的出现迅速更新了生产管理的理念，从解决产品结构优化、恰当水平的

存货、生产进度与控制、经济批量生产、质量控制、资本兼并等物质资源的配置问

题开始，到融入全面质量管理、物料需求计划MRP、制造资源计划MRPH、JIT、供

应链管理SCM,可以清楚看到运筹学和系统理论、信息技术的日益扩大的交融趋势。

尽管系统的思考古已有之，从《内经》的阴阳五行、《孙子兵法》的“经五事”（道、

天、地、将、法）、老子强调的自然界的统一性、南宋陈亮的“理一分殊”到古希

腊哲人德谟克利特的“原子论”、亚里士多德的“四因”思想（后人概括为“整体

大于部分之和”），以及近代黑格尔的辩证法，无不充满（朴素的）系统思想。即

使是在20世纪60年代以前的组织和管理理论的领域，系统观点也不是什么新东西。

社会协作系统学派的创始人切斯特•巴纳德（18867961）就曾用过一种基本的系统

框架来描述组织，将组织视为一种社会系统，一种人的相互关系的协作体系，它构

成社会大系统中的一部分，受到社会环境各方面因素的影响。社会协作系统学派对

其他学派的形成（如社会技术系统学派、决策理论学派、系统理论学派）产生了积极

的影响。

但现代系统观念的确立则必须首先归功于生物学家贝塔朗菲（1947）的“一般

系统论”。贝塔朗菲认为有可能制定出一种系统的、理论的、框架来描述现实世界

中的各种关系，而各学科间的相似性可以发展为一种一般系统模式。在这一理论的

指引下，许多管理学家都开始强调管理学研究与分析中的系统方法。以卡斯特、罗

森茨韦克为代表的系统管理学派在20世纪六十年代盛行一时。系统管理学派认为，

从系统的观点来考察和管理企业，有助于提高企业的整体效率，使各个系统和有关

部门的相互联系网络更清楚，更好地实现企业的总目标。他们认为系统方法是形成、

表述和理解管理思想最有效的手段。所谓系统，实质上就是由相互联系或相互依存

的一组事物或其组合所形成的复杂统一体。这些事物可以像汽车发动机上的零件那

样是实物，也可以像人体诸组成部分那样是生物的，还可以像综合起来的管理概念、

原则、理论和方法那样是理论上的。尽管我们给理论规定出界限，以便更清楚地观

察和分析它们，但是所有的系统（也许只有宇宙除外）都同它们的环境在相互起作用，

因而都受到其环境的影响。在这些观点的影响下，企业家将不同的企业视为不同的

动态系统加以经营，以便有序地达到某种预想的结果。正如理查德•舍恩伯格（1990）

所强调的：“企业的技能（如营销、工程、制造）应该结合起来以便与连续的顾客

链联系在一起”。

现代系统思想的出现彻底改变了人们的思维，除了一般系统理论，维纳（1948）

提出的控制论（其内容涉及最优控制、自适应、自组织系统、大系统理论），申农

（1948）提出的信息论、普利高津（20世纪70年代）提出的“耗散结构”理论、

哈肯（1976）提出的协同学理论、托姆（1972）提出的突变理论都极大地丰富了现

代系统理论的体系。这个体系推动了今天关于复杂性组织的研究。

由于管理科学与系统科学的密切关系，运筹学将它的方法论选择为系统的方法

论就不足为奇。美国科学院国际开发署曾出版的一本书中，其书名就将运筹学和系

统分析并列。切克兰特从软硬系统观点对运筹学的重新思考。萨特在20世纪70年

代末提出的系统分析和评价的方法——层次分析法。这些事实都说明运筹学的特点

和性质都包涵了系统性。在运筹学的研究和解决问题的整体过程中，已形成系统问

题提出、系统设计、系统分析、系统实施、系统评价的完整架构。伴随着信息技术

的飞速发展，运筹学对“管理即决策”所要求的决策支持能力也不断增强，从解决

结构化的问题到通过人机交互解决非结构化的问题，从解决确定性的问题到解决不

定性的问题，从解决简单、局部的问题到复杂系统的整体问题，刚性的运筹逐渐走

向了柔性的运筹，关注的“事理”运筹逐渐走向了能关注“人理”的运筹，作业研

究的运筹逐渐走向了战略研究的运筹。因而，运筹学在实践方面已经具备了进入决

策支持系统（DSS）的能力。

5.管理“丛林”中的管理科学和运筹学

管理思想和理论的发展至今已经历了早期管理思想萌发、科学管理时代、社会

人时代和现代管理理论“丛林”四个阶段。处于社会经济各个领域中的组织由于面

临日益复杂的生存环境和内部状态对科学化决策和决策科学化的要求越来越高，即

使是非结构化的问题和战略级的问题，也迫切需要科学方法进行知识挖掘并做出决

策支持。在这样的趋势下，美国管理学者孔茨所论及的涵盖十一个学派的“丛林”

中出现决策理论学派、系统管理学派、数理学派（亦称管理科学学派）就是相当自

然的结果。由于这三个学派在科学方法上的注重，有时人们也把决策学派、系统学

派和数理学派统称为管理科学学派。其代表性的人物有获得1978年度的诺贝尔经济

学奖的西蒙以及马奇、卡斯特、罗森茨韦克、伯法等人。

尽管管理科学（ManagementScience）有极为广泛的一般理解它是研究（人

类在有限的资源空间、无限拓展的技术和能力空间中）发生在实现组织目标的管理

活动中的具有复杂性、不定性、动态性、创新性的社会行为及其规律的一门综合性

交叉学科。因而既包含以定性分析为主的那些管理分支，如组织行为学和战略管理,

同时也包含以定量分析为主的管理分支，如运筹学和管理统计学。但是，管理科学

常常也被人们按照对于管理科学学派的理解加以限定性地阐释和认识——它是一门

应用科学方法，借助数学符号和“关系模式”来阐述计划、组织、控制、决策等管

理职能的“逻辑化推理”程序，寻求有限资源最优配置以实现组织目标并提供有效

决策支持。所以，所谓管理科学就成为了一门制订用于管理决策的优化模型，并把

这种模型通过人机交互系统应用于管理之中，完成组织实现目标的决策推导过程所

需的数理基础的应用科学。

在这种狭义的理解下，运筹学自然成为了管理科学的技术和方法核心。然而，

就算是那些坚持门派之见的管理学者也不得不承认，即使是站在管理科学学派之外

来审视运筹学，毫无疑问，运筹学对于管理的各个学派的研究都是一种强有力的辅

助工具。

尽管运筹学最开始所解决的企业管理问题集中于决策规则可以合理推导的、具有结

构化问题特征的生产管理领域，但是随着运筹学的发展和与其它学科的交融（如系

统科学、计算机科学、心理学等），运筹学也在逐渐从早期的机械论模式（现代行

为科学家往往如此认为管理科学是机械论的延续，并认为行为与数量方法是彼此隔

绝的）向生物模式和社会模式发出衔接的信号。正如胡戈•明期特贝格所说：“人

类最伟大的发明并不是轮子，而是轴。重要的是探明这些领域是如何互补的，以及

怎样将它们结合起来应用于一些重大项目。”立足于这样的观点，运筹学或者管理

科学的周遭将不再有“管理的丛林”，而是一片拓向无尽未来的充满生机的沃野。

管理学大师赫伯特•西蒙为此这样写到：“我们对已取得的进步感到振奋……正在

朝着充满活力的管理科学和基于管理科学的艺术迈进。”

第一章线性规划（重点、难点章节）

1.本章学习要求

（1）应熟悉的内容

a.预备知识：线形代数中的行变换、逆矩阵、秩、线形无关（相关）等基本

概念和计算方法。

（2）应掌握的内容

a.单纯形法的改进

b.大M法

（3）应熟练掌握的内容

a.线性规划模型（一般形式，标准形式，向量矩阵形式，一般形式转化为标

准形式）

b.线性规划解的基本概念（可行解，最优解，基，基向量，基变量，非基变

量，基解，基本可行解和退化的基本可行解，可行基）

c.基、基向量、基变量、基解之间的一一对应关系

d.线性规划的图解

e.单纯形法

(a)线性规划的几何意义(可行域的凸性，顶点和基本可行解的关系)

(b)第一判别定理(最优解的判别)

(c)单纯形表的构成

(d)单纯形法计算

(e)第二判别定理(无最优解的判别)

f.经济管理中的线性规划建模

g.LINDO软件的使用和EXCEL中线性规划的计算

2.本章重点难点分析

重点：线性规划建模，单纯形法

难点：单纯形法中的换基迭代(实质是初等行变换)，线性规划建模，Lindo

软件使用。

由于线性规划是运筹学的最重要的内容之一，因此有必要分别就各节的内容进行分

析。

(1)线性规划模型

a.线性规划的一般形式

特点：目标函数和约束条件都是线性的。

ff•+A+J.

*,“上・*4(・.目■

)

*・八*・1・4(・•士)♦,

♦.4.a

b.线性规划的标准形式及转化

逐«H<1*<Q<3*•口“=♦1

,11*1*,11*1*=.1

MM1fMMMM

««1«1**・■〃=♦,

juxa<AiK20

在将线性规划的一般形式转化为标准形式时，要注意两点：一是某一约束条件为“三”或

形式的不等式时，应“+”一个非负松弛变量或“一”非负松弛变量；二是某个变量不

满足非负约束时，要用新变量替换，以使标准型中所有的变量均满足非负要求。下面，用一个

例子予以说明。

例1（P8例3）MinZ=x,+2x2+3x3

s.t.-2TI+必+©W9

-3xi+©+2©24

3xi-2应-3*3=-6

X\WO,X2NO,尤3任意。

令xi'=一x”则的=一短（新变量替换），且犷-0；

令X3=X3'一冷”（两个新变量替换），且X3‘，X3”》0；

在第一和第二个不等式约束中分别引入松弛变量：X型右，且M，X520,将上述线性规

划的一般形式转化为标准形。

MaxZ'=R-2切一3a3'f）

2%1'+M+（%3f一冗3”）+/4=9

n

3xi'+X2+2（X3'—x3）-x5=4

3xi'+2处+3（均'一与"）=6

",处，右’,冗3”，X4,招20.

c.标准形式的向量矩阵表达（P8）

旭欣式：

MUTZ-CT

AT・♦便求：皿烟由班的,且・4・）

X20

INKMft：CfqQ“

A'

m♦・之，，2：o

««：4•■低息aQ

'■i,■a•0,

由线性规划的向量矩阵形式，可以清楚地看到，线性规划模型的三要素就是资源向量b,

价值向量C,系数矩阵A（一般都假设A是满秩的）。其中，资源向量b表示了稀缺资源的种类

和限度：价值向量c反映了单位产品（广义）所创造的收益或形成的成本；而系数矩阵4是现

有生产技术、生产工艺、管理水平的具体体现。只要这三个要素确定了，相应的线性规划模型

就确定了。

例2目标函数：MaxZ=2vi+3x2

约束条件：*I+2到+必=8

4x,+工4=16

4x2+》5=12

X|,X2,X3,X4,x5NO.

其向量矩阵形式为

o)

UL4JUMM.aM

(2)线性规划解的概念(P9,重点章节)

这•节为学习者构建了线性规划求解所需的基本概念，包含可行解、最优解、基、基向量、

基变量、非基变量、基解、基本可行解、退化的基本可行解、可行基等，且概念间存在紧密的

关系。下面用一个例子予以解释。

例3：目标函数：MaxZ=2XI+3X2

约束条件：X|+2X2+X3=8

4xi+*4=16

4x2+x$=12

为，必，工3，14，15

其矩阵形式为:

MuK-CX

M-b

JT20JPthC-(Z3000)

Q2100r

4・4。0l。・(R4旦日琨

t0400lj

’4、

Ap1

*■盯,6-tf>AM-3£N-5.

a.基：基是线性规划中最基本的概念之一。基是由系数矩阵A中的线

性无关的列向量构成的可逆方阵。用来构成基的列向量称为该基的基向

量。由于选取的列向量不同，基可能有多个（数目最多不超过V）。在

计算基的数目时，将含有相同列向量的基计为一类（个），不考虑其中

列向量的排列顺序。但在对单纯形表计算的过程中，基中列向量的排列

顺序却必须加以注意。上式中所有的基被罗列如下，可以看到基的数目

没有超过片=10个。

q・M4出

par

*-(444)-U44)4叫4oo

,o4o

4-U4叫4o

b.基变量：当基选定后，其对应的基变量和非基变量就被唯一确定下

来。由基变量构成的向量称为基变量向量。如上例中，当基选&・6冗同

时，该基对应的基变量为小，X4,X5,非基变量为xbM，基变量向量为

M，F；又如当基选为36力&时，该基对应的基变量向量

与寸。非基变量为X1,X2.值得注意的是在基变量向量中基变量

的排列顺序要与基中列向量（基向量）的排列顺序一致。

C.基解：当基选定之后，令非基变量全部等于0,此时，通过求解约

束条件形成的方程组（不考虑变量的非负要求）就可以把基变量的值确

定下来。这样得到的解被称为基解。如上例中，当基选为Bi时，令非

基变量/=0=0,则上述约束条件变为如下方程组，

X3=8

冗4=16

%5=12

其基解为x=(0081612)T.

求基解还可利用公式BXB=b进行，因为基是可逆阵，故XB=B-

Ib.由此上例中的基变量的值

再举一例。若选基B3=(P4P5PI)=C：：J,则

81

川(：)即基B3对应的基解x=(800-16

注意：由于非基变量值被设为()，故谈到基解时，常指基变量xB的值。

d.基本可行解：若XB=BTb20,则此时的基解被称为基本可行解；

同时，此基解对应的基被称为可行基。上例中Bi是可行基，因为

“建修呼川；而B3不是可行基，因为叫・卜612/10.

e.退化的基本可行解：若XB=BTbNO,但XB=BTb才0,即存某基

变量的值为0,则此时的基解被称为退化的基本可行解；同时，此基解

对应的基被称为退化的可行基。

f.基、基向量、基变量、基解之间存在----对应关系。

图i.i基、基向量、基变量、基解之间的——对应关系。

(3)线性规划的图解

例4(P10,例4)

MaxZ=2XI+3X2

2芍+2应<12①

X|+2应W8②

4匹W16③

4X2W12④

》0,X220

解：图解法仅针对二元线性规划问题。一般应首先画出可行域和目标函数等于0时的直线，然

后判断目标函数等值线的移动方向。此例中，由于目标函数可变形为：必=-2/3X|+Z/3,Z/3

是目标函数等值线的纵截距。所以，等值线向右上角移动时，Z增加。这个移动过程直至可行

域边界上（4,2）点时停止。此时，Z取得最大值，（4,2）为最优解。

图1.2线性规划的图解法示例

(4)单纯形法(重点、难点)

a.线性规划的几何意义

(a)凸集(P13)：设K是n维欧氏空间的点集，若任意两点x⑴，x(2)£

K,贝!Jx⑴与小)连线上的所有点a?】)+(l—a)x⑵RK,那么称集合

K为凸集。

(b)凸组合：设x⑴/⑵，…小优)是n维欧氏空间中的k个点，若存在

内，n2,…，内，内Wl,M,三1,2,…，左，使X=|11X⑴+M

k)

X⑵+…+gk?,则称X为X⑴，X⑵的凸组合。

(c)凸集的顶点(P14)：设K是凸集，XEK.若X不能被任意两个

不同于它的点X⑴，X⑵£K的凸组合表示，即x=ax⑴+(1—a)x(2),0

<a<lo则称x为K的一个顶点(或极点)。即，若x是集合K的顶

点，则x一定不在K中任意不同于它的两点的连线内。

(d)(P14定理1)线性规划的可行域是凸集。

(e)(P14定理2)线性规划的基本可行解一一对应于可行域的顶点。

(f)线性规划的可行域中的任一点(可行解)都可用可行域的顶点(基

本可行解)的凸组合表示，如果可行域是有界凸集。

(g)(P15定理3)若线性规划有最优解，则最优解一定可在某个基本

可行解上取得，也即在可行域的某个顶点(极点)上取得。

b.最优性的检验与判别（P173-5）

（a）第一判别定理（最优解的判别）

线性规划模型的目标函数为MAXZ时，对于某可行基B（）,若检验向量CBB

-IA-C>0,则与基B对应的基本可行解XB=B1,XN=0为最优解（基本最优解），此时的

基B称为最优基。

线性规划模型的目标函数为MINZ时，对于某可行基B（,若检验向量CBB

一以一CW0,则与基B对应的基本可行解XB=BXN=0为最优解（基本最优解），此时

的基B称为最优基。

为了更好地说明这个定理，我们给出了它的简单推导过程。

仅就求MAX的线性规划问题已化为标准形后的情形予以讨论。

・

设x是任一可行解，B是某个可行基（B%，0）,此基下的基解对应的目标函数值为

且检验向量CBB“A-c》。，

则在约束条件的左右两边同时乘以廿,得到

将此式加到F=cx,则得到

因为CBB^A—c20,x^O,所以，即任一可行解x对应的目标函数值F都

不超过基B的基解对应的目标函数值5、，故，与基B对应的基本可行解XB=B",网=。为

最优解(基本最优解)，此时的基B称为最优基。

注意：教材所定义的检验向量为C-CBB^A,故定理表述略有不同。另外CB是基变量对应的目标函数中的

系数构成的行向量。其分量的排列顺序与基变量的排列顺序一致。如XB=(X4X5X1)T,则CB=(C4C5G).

例5：目标函数：MaxZ=2XI+3X2

约束条件：X\+2Q+/3=8

4xi+工4=16

4%2+欠5=12

礼必，元3,工4,工520

此线性规划问题的向量矩阵形式为

itaxZ-CT

co

K4＞：C-p3。o机依，勺勺5

o(A

400io|-m料5A2

040

当选的基为

・■・，：・8T，・(4)2Q.fl.C・・1!・$・.■口0□)

01/4OVl2I

-21/21400t0-(23000)

(1/a-1/8oj(o40

-(D03/21/80)20

由第一判别定理知，此时的基本可行解为最优解，基为最优基。最优解为XI=4,A-5=4,M=2,

13=工4=0.

C.单纯形表

（a）单纯形表的形式

'如0_|_401%2A电1a

则=（竿拌吟器£）=用憎传$阳

ZAJ,

设基为B1则与此基对应的单纯

形表为:

注意:

①单纯形表中行列记数从0开始，分别为第0,1,…,m行，第0,1,…,n列。

②为求基的逆矩阵简便，一般我们希望系数矩阵A中含有单位阵形式的基。因为，单位阵的逆矩阵就是它本

身。如果这种情形存在时，那么构造第一张单纯形表（初始单纯形表）时，就可用单位阵形式的基作为初始基。

此时，写出第一张单纯形表就非常容易。

③若系数矩阵A中不含有单位阵形式的基，一种“笨”的方法是直接任选一个可行基作为初始基，构造第一

张单纯形表；但一般为避免烦琐的求基的逆矩阵的过程，我们会采用其它的方法进行，这将在后面予以介绍。

0

c

s

fTos

r4^

。lrQl

禧iu

0oLO

J

o。

o)

例

(接例5)

d.单纯形法计算

(a)单纯形法的思想：因为可行基有多个，不可能用穷举法逐一验证，

得到最优基，故采取换基迭代的方法，从容易计算其逆的初始基对应的

单纯形表开始，逐步得到不同的可行基对应的单纯形表，直至找到最优

基对应的单纯形表为止。换基迭代的过程实质上是一个不断改进的过

程。

(b)计算步骤例释(接例6)

①选单位阵形式的基作为初始基，写出初始单纯形表。若检验向量

CBBTA-C中含负的检验数，则非最优，进行换基迭代。否则，停止，已找到最优解。

②确定谁入基：负的最小检验数所对应的系数矩阵中的列向量入基；

③确定主元素：单纯形表上所选入基列中取正值的元素分别与同行第0列的元素相除，

入基列中取得比值最小者的兀素作为此表的主元素，并画框标示；

④确定谁出基：简单地说，主元素在第几行，就将基中第几个基向量换出；也可由单纯

形表中基变量所对应的的列向量是单位坐标向量这一特点，直接观察哪一个单位坐标向量的“1”

元素与主元素同行，从基中被换出的基向量就是表中该单位坐标向量列对应的那一个列向量。

⑤利用换基迭代公式，得到下一张（新的基）单纯形表。

：1力r其中，为

：主元素二对上面这张革纯

'形表而百，—Aon—4j

%=占-=rr=3,s=2o...........

i=0,1,A,m;j=O,1,A,n

⑥重复上述过程，直至找到最优解

例7（接例6）

选单位阵形式的基B=（P3P4P5）作为初始基，写出初始单纯形表。

fxfo-300

\*nn4nn

因检验向量CBB-A-C=（-2-3000）中含负的检验数，故非最优，进行第一次换基迭代。

|②P?三|③主元素的确定：表上入基列中正的元素

为1，4,分别与同行第0列的元素相除,

2/1=2，16/4=4＞显然，比值最小者为2»

mo/眄殖为）由此就将取得此最小值的入基列中的元

索“2”作为此表的主元素，画上框.

按⑤换基迭代后，得到新基B=（P3P4P2）下的单纯形表，执行步骤⑥，从①开始重复操

作。因此时检验向量CBB-A-C：（—20003/4）存在负的检验数，故非最优，按②、

③、④、⑤进行第二次换基迭代。

③主元素的确定(即单纯龙表中画框的

④P,出基

元素)：入基列中正的元素为1,4,分

②PI入基

别与同行第。列的元素相除，2/1=2,

16/4=4＞显然，比值最小者为2,由此

就将取得此最小值的入基列中的元素

“2”作为此表的主元素，画上框.

130020-1/4,

a[4aA).2toio-io

**00-41p]

，3°I0°"J第二次换基迭代后，得到新基B=(PiP4P2)下的单纯

形表，执行步骤⑥，从①开始重复操作。因为此时检验向量CBB'A-C=(0020-1/4)

存在负的检验数，故非最优，进行第三次换基迭代。换基迭代的步骤同上。

第三次换基迭代后得到新基B=(P|P5P2)下的单纯形表为：

,,14003/21/S0

8-01为同).41001/40

400-21/2I

2011/2-1/80

此时检验向量CBB'A-C=(003/21/80)20,由第一判别定理知，已取得最优

解，最优解为x*=(42004)T.

注意：单纯形法换基迭代的实质是初等行变换。

（c）退化与BLAND法则：当存在退化的基本可行解时，可能会出现死

循环的情形。为避免此情形的发生，可运用BLAND法则，即确定谁入

基时，若最小负检验数不唯一，则选位置最靠前的检验数处入基；确定

主元素时，若最小比值不唯一，则将取得最小比值的入基列中位置最靠

前的元素，作为主元素。

（d）无穷多最优解：当最优单纯形表中，某非基变量的检验数为（）时，

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

e.第二判别定理（无最优解的判别）：

（a）线性规划模型的目标为MaxZ时

对某个单纯形表T（B）=（M）（m+i）x（n+i）,若有某检验数如V0,且如W0（/=1,2,…,m）,

则对应的线性规划问题（L）或者无可行解；或者目标函数值Z无（上）界。因此，无最优解。

n®-

（b）线性规划模型的目标为MinZ时

对某个单纯形表T（B）=（%）（m+i）xgi）,若有某检验数如＞0,且如W0（/=1,2,

则对应的线性规划问题（L）或者无可行解；或者目标函数值Z无（下）界。因此，无最优解。

例8（P26〜27例8第二判别定理的应用）：

MaxZ=2xi+3x2

4为W16

哪4即

A-（I0I）C-03Q-Ex，X、》0

人1，42'J

解：因为此时检验数尻2=-3>0,且62=0W0,所以该线性规划问题无最优解。

f.完整的单纯形法的计算步骤（P19）

（5）单纯形法的进一步讨论（P22）

当在系数矩阵A中，找不到单位阵形式的基作为初始基时，一种直观的思想可供借鉴一

构造•个与现在的线性规划有密切关系的新的线性规划问题，通过求解这个新的线性规划问题,

从而找出原线性规划的最优解。这种思想产生了两种做法：大M法、两阶段法，统称人工变量

法。此处，仅介绍其中的大M法。

a.大M法例释（人工变量法之一）

例9MaxZ=-3修+3心