【管理课堂】《管理运筹学》精选

徐老师

【管理课堂】《管理运筹学》精选


第一章  绪    论

运筹学研究人类对各种资源的运用及筹划活动，其目的在于了解和发现这种运用及筹划活动的基本规律，以便发挥有限资源的最大效益，达到总体最优化的目标。运筹学在商业活动和行政事务中的早期应用可以追溯到几个世纪以前，系统的运筹学理论则起源和发展于20世纪40年代前后。在不到100年的历程中，它发展迅速，运用广泛，成效显著，如今已经成为一门独立的基础学科和应用科学，在工业、农业、商业、国防、科技等诸多方面都发挥了巨大的作用。管理运筹学是运筹学与人文科学交叉后形成的，管理运筹学运用运筹学的基础理论和方法研究解决工商管理实践活动中需要定量决策的问题，在经济管理界的应用十分广泛和深入，已成为现代化管理不可或缺的强有力工具。

通过本章的学习，可以了解运筹学的起源与发展、运筹学学科释义以及运筹学主要分支的研究对象和内容，初步了解管理运筹学模型的构建及研究方法，并通过运筹学在管理工作中的应用案例，对管理运筹学要解决的问题及达到的效果有一个基本认识。

第一节  运筹学的起源与发展一、运筹学的起源

运筹学作为一门科学是在20世纪40年代前后发展起来的，但是它的某些分支却形成得更早些，它的某些思想萌芽甚至可以追溯到上古时期。

朴素的运筹学思想在中国古代历史发展中源远流长。早在公元前6世纪春秋时期，著名的军事家孙武所著的《孙子兵法》就是当时军事运筹思想的集中体现。公元前4世纪战国时期，孙膑的“斗马术”则蕴涵着对策论的某些思想。“孙膑斗马术”说的是春秋战国时期齐王与田忌赛马的事。齐王和田忌赛马，规定各自从自己的上、中、下三个等级的马中各选一匹来参赛，说好输一匹付出千金，胜一匹可获千金。当时齐王的上、中、下三马均比田忌的强。前两局比赛，田忌用上、中、下三马对齐王上、中、下三马，结果田忌均以0∶3输掉。当时，田忌的谋士孙膑一直在场观赛，就给他出了主意，叫他用下马对齐王的上马，中马对齐王的下马，上马对齐王的中马，结果以2∶1胜了齐王，以劣胜优，可见古人早已研究过在多个策略中选择最优策略的运筹思想了。公元前3世纪楚汉相争中，刘邦称誉张良“夫运筹帷幄之中，决胜千里之外”，是对其运筹思想的高度评价。北宋时期的沈括关于行军作战中军粮供应与行军进退关系的分析计算则是更具有现代意义的运筹范例。国外也有这样的史例，如公元前212年古希腊科学家阿基米德曾应海伦皇帝的邀请，为叙拉古(Syracuse)城策划粉碎罗马海军对该城的围攻。这在国外许多有影响的运筹学著作中被认为是所知最早的运筹学活动，然而比我国的这类活动晚了许多年。

除军事运筹思想的成功应用之外，在我国古代一些浩大的工程活动中也有大量运筹思想的应用典籍。最著名的是“丁渭修皇宫”，故事发生在宋真宗祥福年间，宰相丁渭主持皇宫失火后的修复工作。由于取土的地方太远太费工，他就让人在皇宫前大街上取土烧砖。没几天大街就挖成了大沟，他把汴河的堤挖开使水流入沟中，各处来的竹木排筏和船运杂材就经过沟中运到宫门前面，工程完毕后，再将废砖碎瓦等填回沟中，修复大街。这个办法使“取土、运料、回填废料”三件事一下子都办了，而且“计省费以亿万计”。这种施工方案是对工程中的人力、物力、财力等资源进行的最佳统筹安排，是运筹学的核心思想。类似的事例还有宋仁宗庆历年间，黄河决口封堵过程采用了分阶段作业方案，把该方案从经济、人力和效果各方面与旧方案进行比较，论证了分阶段作业优于一次作业。更远年代的如西汉首都长安的选址、水陆枢纽的设计及对宫殿、街道、市井等的统筹布局以及汉宣帝时在首都长安的粮食供应与储存中实现合理物流的运筹思想等。

尽管这些朴素的运筹思想在国内和国外的历史中都可以找到不少的记载，但由于古代社会生产力水平低下，生产组织结构简单，人们在生产实践和其他实践中从事的管理活动也不复杂，对面临的各种决策问题并不需要十分高深的定量分析方法就能解决，所以各种运筹思想的萌芽只是停留在自发地和零星地应用在个别问题上，远没有形成一种系统的科学方法。

18世纪英国发起第一次工业革命以后，随着近代资本主义生产的迅速发展，生产规模越来越大，生产组织机构日趋复杂，人们在经济管理中面临着越来越复杂的决策问题。传统的经济模式和定性分析已不能作出满意解释，促使人们萌生运用定量分析的方法去进行尝试的初步愿望，而当时数学科学的新成果也为此准备了基本工具，使人们这种愿望成为可能并开始变为现实。特别自20世纪泰勒(F. W. Taylor)提出科学管理以后，吸引了更多的人去尝试运用数量方法研究已经提出的各种管理问题，并且取得了一些重要成果。例如：

1736年，欧拉解决了著名的哥尼斯堡七桥问题，为“图论”的发展奠定了基础。

1905年，丹麦电话工程师爱尔朗(A. K. Erlang)开始研究运用数学模型解释电话自动拨号设备在不同时间内服务频数的波动现象，1917年，他发表了这方面的研究成果，初步奠定了“排队论”的理论基础。

1915年，哈里斯(F. W. Harris)推导出物资储备的简单经济订货批量公式，开创了“存储论”研究的先河。

1921年，法国数学家波雷尔(Emile Borel)首次撰文讨论“对策论”的问题。

1931年，里昂惕夫(W. W. Leontief)开始研究美国经济部门之间投入与产出关系的平衡模型，该模型已具线性规划模型的雏形。

以上事实表明，这一时期人们已从不同层次和不同角度展开了数量方法的理论研究和应用研究，并且促成了运筹学某些分支的奠定。但由于当时生产实践对数量方法的需求还不够迫切，加上数学和计算手段的限制，致使许多应用研究未进一步获得显著成果。

二、运筹学的发展

运筹学概念和方法的系统提出是在20世纪第二次世界大战期间。二次大战期间，英国对德国宣战。由于英国是一个岛国，英伦三岛上任何一块陆地到海岸的距离都不超过70英里，这个距离，德国的轰炸机只需17分钟就能飞到，因而防空就成了英国政府的首要任务。英军如何能够尽早地发现敌机，使自己的防空战斗机有时间起飞、爬高并能在敌机深入到中心区之前进行迎击呢？为了解决这个问题，英国政府于1934年12月成立了防空科学调查委员会，以研究当前的科学技术到底有多少能用来加强目前的防空。直到1935年初，这个委员会在研究死光的过程中，提供了一种用无线电对飞机定位的可能，于是全面开展了今天我们称之为雷达的研究工作。直到1938年，才确认雷达在探测飞机的技术上是可行的。1938年7月，英国在沿岸建了四个雷达站，并进行了一次防空演习，但结果令人失望，因为单个雷达可以探测飞机，而多个雷达同时工作就会导致无线电波互相干扰，使接收到的信息相互矛盾，也就是整个雷达系统不能协调地开展工作。为了使这些雷达站接收到的信息协调一致，建立一个反空袭雷达控制系统势在必行。1940年8月，在得过诺贝尔奖金的物理学家布莱克特教授领导下成立了一个研究小组。这个特殊小组第一次应用了Operational Research这个名词，意思是军事活动研究(简称OR，又译为操作研究或作业研究)。当时这个小组包括物理学家、数学家、生理学家、天文学家、军官等人，人们戏称它为“布莱克特马戏团”。这个OR小组对雷达系统的应用进行了模拟试验，最后有效地解决了这个问题。后来研究工作从空军扩展到海军和陆军，不久美国、加拿大等国也成立了OR小组，在“二战”期间成功解决了许多非常复杂的战略和战术问题，比如飞机出击的时间和队形、商船护航的规模、水雷的布置、对深水潜艇的袭击以及战略轰炸等。从此，以OR命名的一门新兴学科就初步创立起来。

第二次世界大战结束后，从事这项活动的许多专家转移到经济部门、民用企业、大学和研究所。OR的研究中心也从英国转移到了美国，从军事部门转移到了管理部门，研究的范围也渐趋扩大。20世纪50年代，由于大规模新兴工业的出现，同行业间的竞争加剧，迫切需要对大型工业复杂的生产结构和管理关系进行研究，做出科学的分析和设计；产品更新换代的加速，使得生产者必须密切注意市场情况和消费者的心理分析；计算机的出现，使需要大型运算的复杂问题的解决得以实现。管理的需要使OR这门学科得到迅速发展，其标志是1949年线性规划理论的建立；1951年非线性规划理论的创立；1954年网络流理论的建立；1955年随机规划的创立以及1958年整数规划理论的创立。其他，如排队论、存储论和马氏决策理论也在同期得到了迅速的发展。与此同时，大批专门从事OR研究的公司和研究所也相继成立，如RAND公司就成立于1949年，世界上第一份OR杂志于1950年出现，第一个OR学会“美国OR学会”于1952年成立。到20世纪50年代末期，英美两国几乎所有工业部门都建立了相应的组织。1959年，英、美、法三国发起成立了国际运筹学会联合会(IFORS)，进入21世纪，已有48个国家或地区的OR组织成为其正式会员。

在中国，现代OR的研究是从20世纪50年代后期开始的。在钱学森、华罗庚、许国志等老一辈科学家的推动下，Operational Research被引入中国，并根据古代汉书中“运筹于帷幄之中，决策于千里之外”所表达的思想与这门学科的内涵和背景的一致，把这门学科定名为“运筹学”。1956年，我国第一个运筹学小组在中国科学院力学研究所成立，并于1958年组建成运筹学研究室。同年，中国科学院数学研究所在华罗庚教授的领导下也开始从事运筹学的研究，并于1959年建立了运筹学研究室。从那时开始，在钱学森、华罗庚、许国志、越民义教授的直接指导和积极参与下，运筹学在中国取得了蓬勃的发展。运筹学中的“图上作业法”、“打麦场的选址问题”和“中国邮递员问题”就是在那个时期提出并研究解决的典型问题。华罗庚先生从1965年起的10年中走出中国科学院研究所，在全国推广“优选法”和“统筹法”，对中国运筹学的研究和运用起到了极大的推动作用。1980年，中国数学学会运筹学分会在山东济南成立，1982年加入国际运筹学会联合会并创刊《运筹学杂志》。1991年中国运筹学会正式成立并开始定期主办学术会议。一批学者走出国门积极与国外同行进行交流，取得了令国外同行瞩目的成果，为我国经济建设和国际学术地位的确立做出了极大贡献。

第二节  运筹学释义与分支一、运筹学释义

运筹学使用科学的方法去研究人类对各种资源的运用及筹划活动的基本规律，以便发挥有限资源的最大效益，达到总体全局优化的目标。这里的“资源”是广义的，既包括物质材料，也包括人力设备；既包括技术装备，也包括社会结构。由于运筹学研究的广泛性和复杂性，学术界对运筹学还没有一个明确的定义，现筛选出以下几个定义来说明运筹学的研究对象及特点。

英国运筹学会给运筹学下的定义是：运筹学是一系列科学方法的应用。在工业、商业、政府部门及国防中，用这些方法处理大量的人员、机器、材料和资金等复杂问题。这种方法的特点是科学地建立系统模型，包括度量各种因素，例如分析机会和风险，以此预测和比较各种决策、策略或控制的结果，使管理机构科学地确定它的政策及其行动。

美国运筹学会的定义为：运筹学是研究用科学方法来决定在资源不充分的情况下如何最好的设计人-机系统，并使之最好运行的一门学科。

中国大百科全书的释义为：运筹学是用数学方法研究经济、民政和国防等部门在内外环境的约束下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案。

有关运筹学的定义和研究虽有不同，但都表明：运筹学是一门独立的新兴科学，有它本身特定的研究对象，它有自成系统的基础理论，以及相对独立的研究方法和工具。它的发展与社会科学、技术科学和军事科学的发展紧密相关，已成为工程与管理学科不可缺少的基础性学科。它的方法和实践已在科学管理、工程技术、社会经济、军事决策等方面起着重要的作用并已产生巨大的经济效益和社会效益。同时，运筹学以越来越快的速度渗透到信息科学、生命科学、材料科学和能源科学等前沿基础性研究中去，又成为这些学科所不可缺少的研究工具。总之，运筹学是一门基础性、交叉性、实用性均很强的学科。

中国运筹学会将运筹学学科按其内涵分成三大部类：第一类是运筹学的基础理论，包括规划理论、随机运筹理论、组合及网络优化理论、决策理论；第二类是有特定对象的运筹学理论与方法，包括工业运筹学，农业运筹学，交通运输运筹学，公用事业运筹学，军事运筹学，金融、市场、保险运筹学等；第三类是运筹学同其他自然科学和人文科学的交叉，例如计算运筹学、工程技术运筹学、管理运筹学，生命科学运筹学等。本书取名《管理运筹学》，根据《中国企业管理百科全书》可释义管理运筹学是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理的一门学科。

管理运筹学作为一门定量决策科学，利用数学、计算机科学以及其他科学的新成就，研究经济管理系统中运行的数量化规律，合理使用与统筹安排人力、物力、财力等资源，为决策者提供有依据的决策方案，以实现最有效的管理并获得满意的经济效益和社会效益。它具有如下主要特点。

(1)
管理运筹学研究和解决问题的基础是最优化技术，并强调系统整体最优。管理运筹学针对研究的经济问题，从系统的观点出发，以整体最优为目标，研究各组成部分的功能及其相互间的影响关系，解决各组成部分之间的利害冲突，求出使所研究的经济问题达到满意效果的解，并寻找一个好的行动方案付诸实施。

(2)
管理运筹学研究和解决问题的优势是应用各学科交叉的方法，具有综合性。经济系统有人、财、物，其投入产出的过程会涉及工程技术、生理、心理、仿生、艺术等学科的知识，要有不同学科知识专长、多方面专家经过共同协作集体努力才能获得成果。

(3)
管理运筹学研究和解决问题的方法具有显著的系统分析特征，要将一个经济系统用数学描述，不管使用什么方法，几乎都需要建立数学模型和利用计算机求解，这为大型经济问题实现科学决策提供了可能。

(4)
管理运筹学研究和解决问题的过程具有连续性。经济问题的决策会受到企业内外各种因素的影响，预测和实施过程中的数据会根据变化不断修正，因此，只有通过连续研究才能最大限度获得符合经济运行规律的解。

(5)
管理运筹学具有强烈的实践性。管理运筹学的目的在于解决实际经济运行系统中的问题，它所使用的全部假设和数学模型无非都是解决实际问题的工具，因此，繁杂的计算原理和过程可以简化或舍弃，重点应是对结果的分析和应用。

二、运筹学分支1．线性规划

线性规划(linear programming)是解决在线性约束条件下追求最大或最小的线性目标函数的方法。例如，当管理者在现有的条件下追求最大利润或在完成任务的前提下追求最小成本的时候，如果现有条件(或完成任务的前提)的约束可以用数学上变量的线性等式或不等式来表示，最大利润(或最小成本)的目标也可以用变量的线性函数来表示，那么这样的问题就可以用线性规划的方法来解决。线性规划建模相对简单，有通用算法和计算机软件，是运筹学中应用最为广泛的一个分支。用线性规划求解的典型问题有运输问题、生产计划问题、下料问题、混合配料问题、人力资源调配问题等。

当线性规划要求某些决策变量或全部变量的解是整数时，就称为整数规划(integer programming)。

2．非线性规划

当线性规划模型中目标函数或约束条件不全是线性的，对这类模型的研究便构成非线性规划(nonlinear programming)的分支。由于大多数工程物理量的表达式是非线性的，因此非线性规划在各类工程的优化设计中得到较多的应用。它是优化设计的有力武器。

3．动态规划

动态规划(dynamic programming)是研究多阶段决策过程最优化的一个运筹学分支。有些经济管理活动由一系列相互关联的阶段组成，在每个阶段依次进行决策，而且上一阶段的输出状态就是下一阶段的输入状态，各阶段决策之间互相关联，因而构成一个多阶段的决策过程。动态规划研究多阶段决策过程的总体优化，即从系统总体出发，要求各阶段决策所构成的决策序列使目标函数值达到最优。

4．图论与网络分析

生产管理中经常遇到工序间的合理衔接搭配问题，设计中经常遇到研究各种管道、线路的通过能力，以及仓库、附属设施布局等问题。这种模型把研究对象用节点表示，对象之间的关系用边(或弧)来表示，点、边的集合构成了图。图论是研究由节点和边所组成的图形的数学理论和方法。图论中的重要问题是网络，将庞大复杂的工程和管理问题用网络描述，可以使解决方法达到最优化。

5．存储论

存储论(inventory theory)是研究物资管理、采购设备、资源的一套数学理论。如工厂生产需储备一定的原材料和零部件，如果储备太多，积压了资金，造成了浪费，如果储备太少，可能会造成生产上的停工待料，因此就必须根据生产活动的连续性决定最佳存储量，使得订购费、库存费以及缺货所带来的损失的费用总和为最小。

6．排队论

排队论(queueing theory)是研究排队拥挤现象的一门科学。在生产和生活中，存在着大量有形和无形的拥挤和排队现象。排队系统由顾客和服务机构组成。从顾客的立场出发，希望多设服务机构，以减少排队现象和时间；而从服务机构的立场出发，显然服务机构愈多，则人力、物力和开支也愈大，服务成本增多是不经济的。那么，究竟设置多少个服务机构才能减少排队现象，缩短排队时间，又不造成服务成本的升高呢？这个问题就是排队论研究的主要课题。

排队论可用来解决电话局、水库、港口码头、飞机跑道等的设计问题以及一些军事问题。

7．博弈论

博弈论(game theory)是描述和研究斗争态势的抽象模型并给斗争双方提供对策方法的一门数学理论，也称为对策论。分析存在利害关系的两个主体的行动及其结果时采用的模型叫做博弈。

在博弈中，人们总希望自己取胜，但由于博弈有对手，所以每一方为取胜所做的努力往往会受到对手的干扰。因此，人们要想获得尽可能好的结局，就必须考虑对手可能怎样决策，从而选出自己的对策。对策选择不同，其最后的结局会差别很大，如“孙膑斗马术”。博弈论可用于商品、消费者、生产者之间的供求平衡分析，利益集团间的协商和谈判，以及军事上各种作战模型的研究等。

8．决策论

决策是指为最优地达到目标，依据一定的准则，对若干备选行动的方案进行的抉择。决策论(decision theory)研究在决策环境不确定和风险情况下对几种备选方案进行决策的准则和方法。

第三节  管理运筹学模型与研究方法

很多学科在研究中广泛使用实验的方法，但管理运筹学研究的系统往往不能搬到实验室来，代替的方法是建立这个问题的数学或模拟的模型。管理运筹学研究和解决问题的核心是正确建立模型和使用模型。学习管理运筹学最重要的技巧就是提高对管理运筹学数学模型的表达、运算和分析能力，成功的模型往往是科学和艺术的结晶。

管理运筹学模型的一般形式可作如下表述。

目标的评价准则：      

约束条件：
s.t.

式中，xj为决策变量，Z为目标函数，gi为约束条件。模型的目标是在满足约束条件的前提下，使目标函数达到最大或最小。

目标函数可以是单一的，也可以是多个的。当目标函数和约束条件都是线性函数时，称模型为线性的，否则称为非线性模型。当模型中不含随机因素时，称它为确定模型，否则称为随机模型。当可控变量只取离散值时，称为离散模型，否则称为连续模型。

应用管理运筹学解决实际问题的工作步骤一般如下所述。

(1)
提出并形成问题。任何管理上的决策问题在进行定量分析前，都需要认真地进行定性分析。首先要提出问题，明确问题的实质及关键所在，这就要求对经济系统进行深入的调查和分析，确定问题的界限，选准问题的目标。

(2)
建立模型。模型是对现实世界的事物、现象、过程和系统的简化描述，是对实际问题的抽象概括和严格的逻辑表达。如在经济管理中，对人力、设备、材料、资金的利用安排都可以归纳为所谓资源的分配利用问题，可建立起一个统一的规划模型，对规划模型的研究和优化代替了对一个个具体问题的分析解决。模型还为应用计算机来解决实际问题搭起了桥梁。

(3)
分析并求解问题。根据所建模型的性质及其数学特征，选择适当的求解方法，求出模型的最优解、次最优解和满意解。

(4)
检验并评价模型。模型分析和计算得到结果以后，尚需按照它能否解决实际问题，主要考虑达成目标的情况，选择合适的标准，并通过一定的方法对模型结构和一些基本参数进行评价，以检验它们是否准确无误，否则就要考虑改换或修正模型，增减计算过程中所用到的资料或数据。

(5)
应用或实施模型的解。经过反复检查以后，最终应用或实施模型的解，就是提供给决策者一套有科学依据的并为解决问题所需要的数据、信息或方案，以辅助决策者在处理问题时做出正确的决策和行动方案。

需要指出的是，经济管理系统存在着大量的不确定性和非定量因素，因此，管理运筹学仅仅依靠数学模型做定量分析很难处理好系统的优化问题。所以其研究方法已经开始出现向将定量分析、定性分析及计算机模拟等相结合的综合优化分析方法发展的趋势。

第四节  管理运筹学的应用

根据中国运筹学会提出的关于运筹学学科分类的意见，管理运筹学是运筹学同人文科学的交叉。其实，运筹学诞生的主要土壤就是管理，既是管理科学发展的需要，也是管理科学研究深化的标志。管理运筹学的主要分支，如规划论(含线性规划、整数规划、动态规划等)、排队论、存储论、对策论等就是在解决生产管理实际中遇到的各类优化问题中逐渐发展完善起来的。

比如，规划论主要研究计划管理工作中有关安排和估计的问题，以确定适应需求的生产、储存和劳动力安排等计划，谋求最大的利润和最小的成本。一般可以归纳为在满足既定的要求下，按某一衡量指标来寻求最优方案的问题。应用规划论的典型例子如“运输问题”，即将某种物资从一个地点运送到另一个地点，要求在供销平衡的同时，定出流量与流向，使总运输成本最低。20世纪50年代后期，运筹学在中国的应用就集中在运输问题上，其中一个广为流传且容易明白的例子就是“打麦场的选址问题”，目的在于解决当时手工收割为主的情况下如何节省人力和时间。国际运筹学界著名的“中国邮递员问题”模型也是在那个时期由管梅谷教授提出的。有关部门曾运用线性规划进行水泥、粮食和钢材的合理调运，取得了较好的经济效益。运用规划论方法可以解决合理选址问题、车辆调度问题、货物配装问题、物流资源(人员或设备)指派问题等。

管理运筹学在供应链管理中的应用也十分典型。供应链管理的基本模型是：从供应商开始到制造商到批发商到顾客，通过这样一个网络，目标是怎样把顾客需要的产品以最低的成本在合适的时间送到顾客手上。供应链管理的问题分成三块：第一块是网络规划，对于一个制造企业来讲，你的制造厂设在哪里，你的物流中心设在哪里，你的零售商会在哪个地点，这是需要通过“合理选址”设计的；第二块称为仓库规划，你的仓库建成什么形式，你的库存怎样进行管理，要确定你的最低库存和最高库存到底应该是多少，这需要通过存储论的方法来计算；第三块称为运输规划，如在运输中是大车大批量运还是小车小批量运？是从一个点出发再返回，还是走一个环形的路线？送货和取货应该在两个网络中还是在一个网络中？等等。管理运筹学在供应链管理优化上的应用，主要解决产品和服务设计的问题以及工艺能力设计问题。比如，生产产品需要什么样的工艺，需要多大的工厂；工厂设在什么地方，配送仓库设在什么地方，厂区内如何布局，设备及工器具如何定置，如何通过合理的人力资源和工作设计建立一个良好的工作环境；在供应链管理中，哪些需要购买，哪些可以自己做，如何同供应商建立好关系以及库存管理、设备维护等。

通信手段和互联网的发展使管理运筹学的思想在订单交付中得到体现。例如，青岛海尔集团商流部通过在每一笔订单生产完成的第一时间，把产品出厂信息通过短信的方式传递给一线2000多名相关工贸公司的业务人员，进而由这些业务人员协助当地客户同步做好订单接收工作。这是海尔解决订单交付迟延、实现零库存至关重要的一环。采用短信之前，海尔从产品出厂到客户仓库所需的时间约为7天；而采用短信之后，这个过程压缩了一半，仅需要3～4天。这不仅意味着更少的库存成本和更快的资金周转速度，更意味着企业有着更为快速的订单反应速度；如果说前者对公司财务方面意义重大，后者在市场营销方面有时对企业就是生死存亡的影响了。

已故数学大师华罗庚曾在中国大力推行运筹学思想，其广为称道的一个例子是：在烧开水的同时，你也可以洗衣服，等水开了，衣服也洗好了；两件事同时做完，总时间最少。像烧开水和洗衣服这样能同时进行的事件称为并行事件；而另一类事件，如烧开水和洗澡，必须烧好了水之后才能用热水洗澡，不能同时进行，称为顺延事件。在管理运筹学思想中，并行事件越多，就能在同一时间内做更多的事情，效率就更高。

在海尔订单交付的过程中，也存在同样的逻辑：产品按订单生产出来，首先有一个在途的过程，产品要从工厂运到海尔各地的工贸公司。海尔的工贸公司相当于一般企业的销售公司，工贸公司的作用除了吸引客户向海尔提交订单，还包括向客户交付订单和替客户暂时保存订单产品，有一个过渡型仓库的作用。真正意义上的订单交付是从货到后才开始的，即客户得到货到通知后，要开始整理自己的仓库、货架，同时准备相关接收单据，完成货物交接。如果排除客户故意延迟接收订单的情况，这一过程往往需要2～3天。从运筹学来看，在途和交付是两个顺延的事件，这意味着订单产品只有到了工贸公司，海尔业务代表才可能通知客户开始接收这批订单。而客户为接收订单进行准备的2～3天时间里，该未交付的订单就作为海尔的库存呆在工贸公司的仓库里。海尔短信的作用就是把这两个订单处理方面的顺延事件变成并行事件。海尔的具体做法是：订单产品出厂时，由总部向工贸公司的相关业务员发出一个短信，告知货物在途，业务人员马上可以同时着手进行订单交付的前期准备工作；货物到达工贸公司后，由工贸公司立即通过局域网反馈给总部货物已到的信息，该信息再通过总部集中的短信平台以短信方式发送给业务员，由业务员立刻组织交货，避免货物在工贸公司的仓库中积压。

短信收发只是一个形式，背后是海尔以订单为中心的供应链管理系统。海尔的每一个订单都包含订单型号、客户、业务代表三方面的信息，在提交订单的时候通过商流部门的CRM网络进入生产运营的ERP平台，保证与生产系统一一对应的关系，生产完成后又自动由ERP系统在第一时间将信息释放到商流部门的短信平台中，发送给业务代表。海尔在这个过程中虽未使用运筹学的具体定量分析方法，但是运筹学统筹思想的运用显露无遗。

运筹学的研究应用已经给企业各部门带来了巨大的财富节约。由国际运筹学会联合会和美国运筹学会联合主办的Interfaces杂志主要用于刊登运筹学的应用成果，由国际运筹学会联合会每年在世界范围内评选出6篇最优秀的运筹学应用成果，授予弗兰茨·厄德曼(Franz Edelman)奖，并刊登在该杂志每年的首期上。

比如美国雪铁戈(Citgo)石油公司运用线性规划的方法针对炼油程序及产品供应、配送和销售的整体优化案例发表于Interfaces 17(1987，no.1)。Citgo在20世纪80年代中期曾是全美前150位最大的工业公司之一，由于财务亏损，1983年被Southland收购，1984年税前亏损创纪录达到5000万美元。Southland集团是711便利商店的大供应商，该便利商店每年零售汽油达20亿加仑。为挽回亏损，公司成立了一个由凯林满(Klingman)领导的OR任务小组，希望借助于运筹学的方法来分析优化业务流程，以提高公司的赢利。OR任务小组分析了石油行业的竞争环境对石油价格以及公司业务流程对成本的影响，确定了利润改善的领域：减少原油产品库存和原油库存、控制原油及原料采购、减少分摊在产品销售上的变动成本、降低石油精炼厂的成本等。通过对石油精炼厂的原油选择和采购、运营水平、产品组成部分的生产水平、原料选择和采购、单位周转时间的优化、加氢裂化装置改装等的经济分析，确定了LP系统和基础数据的质量。在此基础上，建立了LP(线性规划)模型：

min
Citgo各工厂炼油成本

成本约束

s.t.
  生产能力约束

库存约束

该模型共有15 000个决策变量，3000个约束条件。工作小组在对模型中的数据进行了一个月的调整对比后，将输出的优化方案应用到Citgo的各种业务流程中，运行第一年即减少库存11 650万美元，节省利息1400万美元；在协作、定价、购买决策上的改进至少增加了250万美元利润。1985年总利润增加7000万美元，而实施OR工作的总成本估计为2000万～3000万美元，与这个数字相比，Citgo在OR上投资的收益是巨大的。

综上所述，无论在国内或国外，管理运筹学的应用前景都是非常广阔的，取得的成效也是十分显著的，这也是管理运筹学发展越来越快的驱动因素之一。

管理运筹学课程是经济管理类专业的主干课程，也是所有专业基础课中难度较大的一门课程。该门课程对于经济管理类专业学生的培养不同于数学类专业，其主旨在于运用运筹学方法去分析和解决管理中的问题，而不是单纯学习运筹学理论本身。管理运筹学教学的目的就是要使学生掌握运筹学理论的基本思想方法，掌握各种定量模型及其求解方法，为今后运用运筹学理论解决实际管理问题打下坚实的基础。特别要注意，管理运筹学不同于纯数学课程，模型的求解并不代表问题的解决，还需要考虑许多因素，这就要求学生在学习过程中不拘泥于课本，不墨守成规，要充分发挥自己的想象力和主观能动性，独立思考，大胆探索，提出自己的新观点、新思路和新方法。培养学生解决实际问题的能力是管理运筹学课程设置的宗旨。

徐老师

第二章  线 性 规 划
线性规划问题是目标函数和约束条件均为线性的最优化问题。自从1947年丹捷格(Dantzig)提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛，已成为现代管理中经常采用的基本方法之一。线性规划是最优化问题中的重要领域之一，很多运筹学中的实际问题都可以用线性规划来表述。很多其他种类的最优化问题算法也都可以分拆成线性规划子问题，然后求解。
通过学习本章，应当了解线性规划的有关概念，掌握线性规划模型的建立及优化方法，会用计算机对大型线性规划模型问题进行求解和分析。本章的难点为单纯形计算方法。

第一节  线性规划问题的提出
线性规划是运筹学的一个重要分支。它的适用领域非常广泛，从工业、农业、商业、交通运输业、军事的计划和管理及决策到整个国民经济计划的最优方案的提出，都有它的用武之地，是现代管理科学的重要基础和手段之一。
线性规划研究的问题主要有以下两类。
(1)        给出一定量的人力、物力、财力等资源，如何统筹规划这些有限资源完成最大任务。
(2)        给定一项任务，如何运筹规划，合理安排，以最少资源来完成它。
线性规划要研究的两类问题中都有一个限制条件：第一类问题是给出一定量的人力、物力和财力等资源；第二类问题是给定一项任务。这种限制条件可以用一组线性方程组或线性不等式组来描述。限制条件所要达到的结果称为“目标”，第一类问题的目标是利用有限资源完成最大任务，第二类问题的目标是以最少资源完成给定任务。可以用一个线性函数来描述这种目标，称这个线性函数为目标函数。
由此可见，各类问题尽管限制条件与目标不相同，但规划的目的就是使这些资源发挥最大限度的作用，从而完成最多最大的任务。换句话说，也就是资源的最优利用问题。用数学形式表示的话，规划的目的就是在给定的限制条件(或称约束条件)下，求目标函数的极值问题(包括极小值和极大值)。
下面用一个例题来说明线性规划问题的特点。
例2-1  某工厂在计划期内安排生产Ⅰ，Ⅱ两种产品，已知生产单位产品所占用的设备A,B的台时，原材料的消耗如表2-1所示。工厂每生产一单位产品Ⅰ可获得利润2万元，每生产一单位产品Ⅱ可获得利润3万元，问：工厂应分别生产多少单位产品Ⅰ和产品Ⅱ才使工厂获利最多？
表2-1  原材料消耗
        I        II        资源总量
设备A/小时
设备B/小时
原材料/公斤        0
4
2        3
0
2        15
12
14

解：设计划期内生产单位产品Ⅰ和单位产品Ⅱ的件数为 和 。因为在计划期内设备A的可利用有效台时是15，所以在确定单位产品Ⅰ，Ⅱ的产量时可表示为

同理，因在计划期内设备B的限制，有不等式

因原材料的限制，有不等式

此外， ， 还应该是非负的数，即
，
该工厂的利润值为

综上所述，该工厂的计划安排问题可用以下数学模型表示：


由上例可看出线性规划问题有如下特点。
(1)        用一组未知数 表示某一方案，这组未知数的一组定值就代表一个具体方案，通常要求这些未知数取值是非负的。
(2)        存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表达。
(3)        有一个目标函数，按研究问题不同，要求其实现极大或极小值。
一般来讲，这类问题可用数学语言描述如下。
目标函数：                                 (2-1)
满足约束条件：

                 (2-2)
这就是线性规划的数学模型。式(2-1)称为目标函数，式(2-2)称为约束条件，其中，式 也称为非负条件。
为了书写方便，上述模型可以简写为


第二节  线性规划问题的数学模型
当用线性规划的方法对实际问题进行优化时，必须把这个实际问题用恰当的数学形式表达出来，这个表达的过程，就是建立数学模型的过程。数学模型的建立需要经验和技巧以及有关的专业知识，只有通过大量的实践，在建立模型时才能得心应手。初学时可从题目中所给出的限制条件和目标入手，由限制条件建立起线性方程组，由目标得到目标函数。
下面，结合若干个实际问题讨论数学模型的建立。
一、投资问题的数学模型
例2-2  已知某集团有1 000 000元的资金可供给投资，该集团有5个可选择的投资项目，其中各种资料如表2-2所示。
表2-2  投资方案
投资项目        风险/%        红利/%        增长/%        信用度
1
2
3
4
5        10
6
18
12
4         5
8
7
6
10        10
17
14
22
7        11
8
10
4
10

该集团的目标为：每年红利至少是80 000元，最低平均增长率为14%，最低平均信用度为6。该集团应如何安排投资，才能使投资风险最小？
解：设 表示第 个项目的投资额， =1,2,3,4,5，目标是投资风险最小化，因此目标函数为

约束条件分别如下。
各项投资总和为1 000 000元，即

所得红利最少为80 000元，即

增加额不低于140 000元，即

平均信用度不低于6，即

非负约束，即            ， =1，2，3，4，5
综上所述，该问题的数学模型可以表示为


二、配料问题的数学模型
例2-3  某厂要用三种原材料A，B，C混合调出三种不同规格的产品X，Y，Z。产品的规格要求、产品单价、每天能供应的原材料数量及原材料单价分别如表2-3和表2-4所示。该厂应如何安排生产，才能使得利润收入为最大？
表2-3  产品规格
产品名称        规格要求        单价/(元/公斤)
X

Y

Z        原材料A不少于50%
原材料B不超过25%
原材料A不少于25%
原材料B不超过50%
                  不限        50

35

25

表2-4  原材料供应数量和单价
原材料名称        每天最多供应量/公斤        单价/(元/公斤)
A
B
C        100
100
60        65
25
35

解：设 表示产品X中A的成分； 表示产品X中B的成分； 表示产品X中C的成分； 表示产品Y中A的成分； 表示产品Y中B的成分； 表示产品Y中C的成分； 表示产品Z中A的成分； 表示产品Z中B的成分； 表示产品Z中C的成分。依据条件有




目标函数为
                                  
约束条件为

配料问题在工业中常用到。例如铸造车间对熔炼出来的铁水有一定的质量要求，也就是要求化学成分有一定含量的百分比。已知各种炉料所含有的各种化学成分的数量，以及各种炉料的最大利用量及单价，利用配料问题的数学模型就能制订出价格最低而又符合一定质量要求的铁水的配料方案。

三、人力资源问题的数学模型
例2-4  某商场因为每天顾客的数量不同，所以每天需要的营业员人数也不同。经过统计分析，商场对营业员的需求量如表2-5所示。按照规定，营业员每周工作五天后，连续休息两天。问：应如何安排营业员的作息，既能满足工作需要，又使得雇佣的营业员人数最少？
表2-5  营业员需求量
工作日        需要营业员人数
星期一        300
星期二        300
星期三        350
星期四        400
星期五        480
星期六        600
星期日        550

解：设 为星期 开始工作的人数。问题的目标是要在满足工作需要的条件下，使一周内需要的营业员数量最少。由于每个营业员都工作五天，休息两天，因此只要计算出一周每天开始工作的人数，然后计算营业员的总数并使得营业员总数最少。
所以，目标函数可以表示为以下形式：

再按照每天所需要的营业员的人数写出约束条件。例如对于星期一，因为除了星期二和星期三开始工作的营业员(休息)，在其他时间开始工作的营业员都会在星期一继续工作，其余类推。所以可以得到以下约束：


四、合理下料问题的数学模型
合理下料问题是机械工业常遇到的问题。毛坯车间经常要在长度一定的条形材料或面积一定的板材上切割若干个具有一定形状、尺寸的毛坯。在一般情况下，材料不可能被完全利用，会有边角余料，造成浪费。因此，如何最大限度地减少边角余料，提高材料利用率，使得切割规定数量的毛坯所用材料最少就是合理下料问题所要研究的。
例2-5  某车间有一批长度为180cm的钢管(数量充分多)，为了制造零件的需要，要将其截成三种不同长度的管料：70cm、52cm、35cm。规定这三种管料的需要量分别不少于100根、150根和100根。问：应如何下料能使消耗的钢管数量最少？
解：为了完成规定的下料任务，有许多下料方法。
(1)        单一下料法：最简单。就是在每一根或每一张板材上只下一种规格的毛坯。其好处是可以按照一种固定不变的方式送料、下料，简单方便。但是由于材料规格尺寸与毛坯尺寸一般不成比例，所以采用单一下料法会产生很多甚至比较大的边角余料，因此材料利用率低。
(2)        简单套裁法：就是在一根或一张板材上先下尺寸规格大的零件，以剩下的边角余料下尺寸规格小的零件。该法的材料利用率虽然比单一下料法高一些，但往往由于事先对如何下料缺乏周密的考虑，所以材料利用率也不会太高。
一个高利用率的下料方案，必须是没有太多的边角余料，并且各种零件的生产数量都正好等于或略高于计划需要的数量。现在的问题是如何求得材料利用率高的下料方案。
下料方案是由一种或几种不同的下料方式配以一定的数量所组成。因此，只要求出材料的全部下料方式，就可找出下料问题的数学模型。
下面结合例题讲述。
找出全部下料方式的思想：假设切口宽度为零，从一根材料上能不能裁出若干个长度相同或不相同的零件，就完全取决于这些零件的总长度是否超过材料的长度。也就是说，如果从一根条材上下出若干个零件来。这些零件的总长度一定不超过条材的长度。有了这个简单的判断准则，就不难求出全部下料方式。
设在180cm长的钢管上能够下出U个70cm的零件、V个52cm的零件和W个35cm的零件，则U，V，W个零件必须符合
70U+52V+35W≤180
上式左方是这些零件的长度，右方是材料的长度。所以，要求出在180cm长的钢管上下出这三种零件的全部下料方式，就只要求适合U≥0、V≥0、W≥0的全部整数组[U、V、W]。
全部整数组可以采用试算法得到。可以从最大尺寸的零件下起，也就是先看U最多能够达到多少。显然U≤2，所以U可以取2,1,0三个数值。
当U=2时，140+52V+35W≤180。
于是V=0，W=1，余料为5，得第一个下料方式为
     U   V    W   余料/cm
2    0    1    5
当U=1时，70+52V+35W≤180。
于是V≤2，因此V可能取2,1,0三个数，这样可得三个下料方式，为
U   V    W   余料/cm
1    2    0     6
1    1    1    23
1    0    3     5
当U=0时，0+52V+35W≤180。
于是V=3，V取3,2,1,0四个数，这样可得四个下料方式，为
U   V    W   余料/cm
0    3    0    24
0    2    2     6
0    1    3    23
0    0    5     5
经过这样试算，可得到8种下料方式，如表2-6所示。
表2-6  下料方式
下料方式
零件尺寸        一    二     三   四     五     六      七     八        零件需要量
70        2     1      1     1      0     0       0      0        100
52        0     2      1     0      3     2       1      0        150
35        1     0      1     3      0     2       3      5        100
余料        5     6     23     5     24     6      23      5       

现在的问题是：在这8种下料方式中找出用料最省的下料方案。从表中可见，一、二、四、六、八这5种下料方式余料最少，但单一采用任一种均不能保证零件的需要量，所以必须同时采用多种下料方式，才能满足零件的需要量，这里零件需要量是限制条件。
设 分别表示这8种下料方式钢管消耗的总根数，则数学模型为



五、运输问题的数学模型
问题的提出：某类产品有若干个产地，已知每个生产地的产量；这类产品有若干个消费地，已知每个消费地的需要量。假设总的产量等于总的需要量。问题是如何编制一个最优的运输计划，使从产地到消费地的运输费用最小。
例2-6  某地区有3个矿山A1,A2,A3，生产同一种矿物。另外有4个这种矿物的消费地(铁厂)B1,B2,B3,B4。各矿山产量及铁厂的需要量和矿山将矿物运到铁厂的单位运价如表2-7所示。
表2-7  需求量和单位运价
铁厂
运价/元/t
矿山        B1        B2        B3        B4        产量/t
A1
A2
A3           1.5
7
   1.2         2
   0.8
   0.3          0.3
  1.4
2         3
2
   2.5        100
80
50
需要量/t        50        70        80        30       

问：应如何调运，才使总运费最省？
解：该题有两个限制条件：一个是产量，一个是需量。目标是总运费最省。
设 表示从第 个矿山运往第 个铁厂的矿物运量，这样得到以下两组线性方程组。
(1)        各矿山矿物的生产量与运出量的平衡方程为

(2)        各铁厂矿物的供应量与需要量的平衡方程为

(3)        矿物的运输量应非负，即

(4)        目标函数为

         

以上建立了5个在经济领域常见的实际问题的数学模型。其他一些类型，同学们可根据实际问题的特点，灵活运用所学知识去建立相应的数学模型。
第三节  两个变量问题的图解法
图解法简单直观，有助于我们从几何图形上了解线性规划问题求解的基本原理。
例2-7  以例2-1模型为例讲述图解法。


解：建立直角坐标系如图2-1所示， 为横轴， 为纵轴。在以 ， 为坐标轴的直角坐标系中，模型中的非负条件 就代表包括 轴和它右侧的半个平面，非负条件 代表包括 轴和它以上的半个平面。这两个条件同时存在就把 和 的解均限制在第Ⅰ象限了，所以寻找线性规划数学模型的解只在第Ⅰ象限进行即可。
同样道理，每一个约束条件都代表一个半平面。因为题目由5个不等式组成，所以满足全部约束条件的点集是这5个半平面的相交部分，即公共区域OABCD，如图2-1所示。

图2-1  唯一最优解
区域OABCD中的每一个点(包括边界点)都是这个线性规划问题的一个解(又称可行解)，因而区域OABCD是解集合(称它为可行域)。
现分析目标函数 。在坐标平面上，它可表示为以Z为参数的一族平行线 。位于同一直线上的点，具有相同的目标函数值，因而称它为“等值线”。当Z值由小变大时，直线 沿其法线方向向右上方移动。当移到B点时Z的取值最大，这就得到了问题的最优解。B的坐标为(2,5)，于是可计算出Z=19。
这说明该工厂的最优生产计划方案是：在计划期内生产产品Ⅰ2件，产品Ⅱ5件，可得最大利润19元。
由上例可得到图解法的一般做法如下。
(1)        建立直角坐标系。
(2)        找出所有约束条件交成的公共区域即可行域。
(3)        改变Z值，使等值线平行移动，当移动到某一点再移动就要离开可行域时，则该点使目标函数达到极值，该点坐标为最优解。
例2-8  若将例2-1模型的目标函数变为 ，求解线性规划。
解：目标函数以Z为参数的等值线与约束条件 的边界直线平行。当Z值由小变大时，等值线与线段BC重合，见图2-2。继续移动则得离开可行域，这表明线段BC上任意一点都使目标函数Z取得相同的最大值。于是，该线性规划问题有无限多个最优解。

图2-2  无限最优解
例2-9  例2-1模型中若约束条件变为


求解线性规划。
解：从图2-3中可以看到，可行域无界。

图2-3  无最优解
该题目标函数为 ，要求极大值。从图2-3中可以看出，因为可行域无界，目标函数Z→+∞无上界，因此无最优解。
例2-10  例2-1模型中若约束条件1变为 ，求解线性规划。
解：从图2-4中可以看出，同时满足5个不等式的点集不存在，所以没有可行解，当然没有最优解。

图2-4  无可行解
通过图解法可以看到，线性规划问题的所有可行解构成的可行域一般是凸多边形(有时可行域是无界的)。若存在最优解，则一定可在可行域的某顶点上得到：若在两个顶点上同时得到最优解，则这两顶点连线上的任一点都是最优解。若可行域无界，则可能发生最优解无界的情况，这时无最优解。
图解法虽然有直观、简便等优点，但是当变量较多时(三个以上)，即在高维的情况下它就无能为力了，但这种方法能使我们从几何直观上了解线性规划问题解的性质。
第四节  线性规划问题的标准形式
我们已经看到，线性规划问题可能有各种不同的形式。目标函数，有的要求实现最大化，有的要求实现最小化，约束条件可以是“≤”形式的不等式，也可以是“≥”形式的不等式，还可以是等式。这种多样性给讨论问题带来不方便，为了便于以后讨论，我们规定线性规划问题的标准形式如下。
目标函数为                                      (2-3)
满足于                                      (2-4)
其简缩形式为                                              (2-5)
                                  (2-6)
这里假定 。
有时，线性规划问题用向量和矩阵描述比较方便。
用向量描述可得               
                                            (2-7)
其中


向量 是其对应变量 的系数列向量。
用矩阵描述可得                                              (2-8)
                              (2-9)
其中
= ；0=
称A为约束方程组的系数矩阵(m&acute;n阶)，一般情况下m<n，m，n为正整数。
b为限定向量，一般情况下 。
C为价值向量。
X为未知数向量；为了方便，常将其列向量写成转置形式，如
X= =
实际问题的线性规划数学模型是各种各样的，需要把它们化成标准形式，并都借助于标准形式的求解方法进行求解。
下面讨论如何将模型化为标准形式的问题。
(1)        若要求目标函数实现最小化，即min Z=CX，此时将目标函数乘以(-1)，即可变为求最大值：min Z=max Z′=-CX
(2)        约束方程组为不等式，分两种情况。
若约束条件为“≤”形式的不等式，则可在“≤”号的左端加入一个非负变量x(称松弛变量)，把原“≤”形式的不等式变成等式。
若约束条件为“≥”形式的不等式，则可在“≥”号的左端减去一个非负变量(称剩余变量或松弛变量)，把“≥”号变为“=”号。下面举例说明。
例2-11  将例2-1的数学模型化为标准形式：




解：在各不等式中，分别加上一个松弛变量 , , ，使不等式化为等式，于是得标准形式为


所加松弛变量 , , 表示没有被利用的4种资源，由于它们未被利用，当然也没有转变为价值，所以在目标函数中，它们的系数应当为零，即 。
(3)        若存在无非负要求的变量，即变量 取正值或取负值都可以，为了满足标准形式对变量的非负要求，可令 = ，其中 ， 。由于 可能大于 ，也可能小于 ，故 可以为正也可以为负。
例2-12  将下述问题化为标准形式：


解：令 = - ，其中 ， ，则标准形式为      


(4)        若 ，则在约束条件两边同乘(-1)，使 。
第五节  线性规划问题解的概念和性质
在讨论线性规划问题的解法前，先来介绍一下线性规划问题解的概念。由本章第四节可知，一般线性规划问题的标准形式为
                                (2-10)


                     (2-11)
可行解：满足约束条件(2-11)的解 ，称为线性规划问题的可行解。所有可行解的集合称为可行域。
最优解：满足式(2-10)的可行解称为线性规划问题的最优解(即使目标函数达到最大值的可行解，叫最优解)。
基：设A是约束方程组的m&acute;n阶系数矩阵，其秩为m。B是矩阵A中m&acute;m阶非奇异子矩阵 ，则称B是线性规划的一个基。
这就是说，矩阵B是由m个线性独立的列向量组成。不失一般性，可设

称 为基向量( )，与基向量 相对应的变量 ( )为基变量。否则称为非基变量。
为了进一步讨论线性规划问题的解，现在来研究约束方程组(2-11)的求解问题(暂不考虑非负约束)。假设该方程组系数矩阵A的秩为m。因m<n，故它有无穷多个解。假设前m个变量的系数列向量是线性独立的，这时式(2-11)可写成
         (2-12)
方程组(2-12)的一个基是

设 是对应这个基的基变量，  。
现若令式(2-12)中的非基变量 ，并用高斯消去法，可求出一个解 ，称x为基本解。由此可见，有一个基就可以求出一个基本解。
基本可行解：满足非负条件的基本解，称为基本可行解。
可行基：对应于基本可行解的基，称为可行基。

第六节  单纯形法的基本原理
一、单纯形法的思路
在用图解法解两个变量的线性规划问题时，我们提出，如果线性规划有最优解存在的话，则一定可以在可行域(即凸多边形)的顶点上找到，只要沿着这些顶点去找就行了。这个方法可推广到多个变量的线性规划问题。由多个变量所组成的不等式组的可行域在n维空间内是一个凸多面体，与多边形一样，凸多面体的每一个顶点均是一个基本可行解。根据定理：线性规划问题目标函数一定可在其可行域的顶点上达到最大值。只需从可行域(凸多面体)的顶点去找，按照问题的标准形式，从可行域中一个基本可行解(一个顶点)开始，转换到另一个基本可行解(顶点)，并且使目标函数的值逐步增大；当目标函数达到最大值时，问题就得到了最优解。先举一个例子来说明。
例2-13  某制药厂生产甲、乙两种药品。生产1吨甲药品需要30公斤维生素和5个台班。生产1吨乙药品需要20公斤维生素和1个台班。该厂每周所能得到的维生素量为160公斤，每周设备最多能开15个台班。根据市场需求，甲种产品每周产量不应该超过4吨。已知该厂生产1吨甲、乙两种产品的利润分别为5万元及2万元。问：该厂应如何安排两种产品的产量才能使每周获得的利润最大？
解：设该厂每周安排生产甲种药品的产量为 吨，乙种药品的产量为 吨，则每周所能获得的利润总和为 万元。但是生产量的大小要受到维生素产量、设备台班和市场最大需求量的制约，即 ， 要满足以下约束条件：

综上所述可以建立如下模型：


化为标准形式得



首先从约束矩阵A中找出一个基矩阵。可以看出由 , , 向量构成一个三阶单位矩阵，是可逆矩阵。因此令

为基矩阵。相应地 , , 是基变量； , 是非基变量。
将基变量用非基变量表示，可得
                            (2-13)
将 , , 代入目标函数，得到目标函数的非基变量表示式为
                              (2-14)
若令非基变量 = =0，代入式(2-13)，得到一个基本可行解 ：

这个基本可行解显然不是最优解。因为从经济上讲 = =0表示该厂不安排生产，因此没有利润。从数学角度看，式(2-14)中非基变量 , 前的系数为正数。故若让非基变量 或 的取值从零增加，相应的目标函数Z也将随之增加，因此就有可能找到一个新的基本可行解，使目标函数数值更好。显然在式(2-14)中， 的系数比 前的系数大，即 每增加一个单位对Z值的贡献比 的大。故让 的取值从零变为一个正值。这表明 应从非基变量转为基变量，称为进基变量。因此必须从原有基变量 , , 中选一个离开转为非基变量，称为离基变量(或出基变量)。下面分析 应该取多大的正值及选哪个基变量作为离基变量。在式(2-13)中，让 由零值开始增加，则由式(2-15)
                              (2-15)
可知 , , 的值都要逐步减小。但为了满足非负条件，必须 , , 。故当 从零值开始增加直到使 , , 取值第一个减少到零时停止。这时 的取值既能满足非负条件，又使原有基变量中一个转为非基变量，即此时 的取值应为


此时 ， ，而 。这样就得到一个新的基本可行解 ，相应的基矩阵为 。基变量是 , , ，非基变量为 和 。对应的目标函数值 ，因此 是比 改善了的基本可行解。为了分析 是否为最优解，仍要用非基变量来表示基变量及目标函数。由式(2-13)可得
                         (2-16)
式(2-13)中 的位置在式(2-16)中由 来代替。为了进一步分析问题，找出规律，可以用消元法将式(2-16)中的 的系数列向量 化成式(2-13)中 的系数列向量 的形式，得到
                            (2-17)
将式(2-17)代入目标函数式(2-14)，得到用非基变量 和 表示目标函数值的表示式
                               (2-18)
在式(2-17)中令  即可得当前基变量的取值 ， ， 。在式(2-18)中令  即可得到当前基本可行解 的目标函数值 。
在式(2-18)中，非基变量 前的系数仍为正数，因此若让 作为进基变量，迭代到另一个新基本可行解 ，就有可能使目标函数值再增加，因此当前解 仍不是最优解。为了从 迭代到 ，选 作为进基变量，仍让 作非基变量。因此令式(2-17)中的 ，得到
                            (2-19)
当 取值从零开始增加时，显然 总可以满足可行性。因此取   ，则 ， ， ，即 作进基变量， 为离基变量，得到新的基本可行解 。为了进一步的分析，将式(2-17)写成用非基变量 , 表示 , , 的式子，即
                         (2-20)
再用高斯消去法将式(2-20)中 的系数化成单位列向量 ，得到
                          (2-21)
再将式(2-21)代入目标函数式(2-18)，得到用非基变量 , 表示目标函数的式子
                         (2-22)
在式(2-22)中，若非基变量 或 由零增加，只能使Z值下降，因此当前的基本可行解 就是最优解： 。最优值 。
通过上述例子，可以了解利用单纯形法求解线性规划问题的思路。
原题是二维的，即两个变量 , ；当加入松弛变量 , , 后，变换成高维。这时可以想象，满足所有约束条件的可行域是一个高维空间的凸多面体。这个凸多面体上的顶点就是基本可行解。以下将做出一般性叙述。
二、确定初始基本可行解
为了确定初始基本可行解，要首先找出初始可行基。由前述已知，可行基一定是约束条件

中的一个单位矩阵。因此，在解线性规划问题前，要先观察约束条件方程的系数矩阵中是否存在单位矩阵，如果存在，则作为一个基；如果不存在，就要分两种情况分别解决。
(1)        对约束条件是“≤”形式的不等式情况，可用化标准形式的方法，在每个约束条件的左端加上一个非负的松弛变量，经过整理，重新对 及 进行编号，则得到下列方程组：


显然得到一个单位(m&acute;n)矩阵为

将B作为可行基，将上述方程组移项得

令 ，则得一初始基本可行解为

(2)        对于约束是“≥”或“=”形式的不等式，若不存在单位矩阵，则采用人造基方法。即对“≥”的不等式减去一个非负的剩余变量，再加上一个非负的人工变量；对于“=”约束再加上一个非负的人工变量，总能得到一个单位矩阵。
三、最优性检验
得到一个基本可行解后，要检验它是否为最优解，如果是，则停止迭代，如果不是，则继续迭代。为此，需要建立一个判别准则。
一般情况下，经过迭代后，约束方程组变为

将其代入目标函数的表达式，得


令

于是

再令

则

式中， 为非基变量 的检验数。
(1)        最优解判别定理：若 为对应于基B的基本可行解，且对于一切 =m+1,m+2…,n，有 ，则 为最优解。
(2)        无有限最优解判别定理：若 为一个基本可行解。有一个非基变量的检验数 ，并且对于一切 =1,2,…,m，有 ，那么该线性规划问题没有有限最优解(也称无解)。
(3)        最优表中存在非基变量的检验数为零，则线性规划具有多重最优解。
四、基变换
得到一个基本可行解后，经检验如果不是最优解，则要寻找一个新的基本可行解。具体做法是从原可行基中换一个列向量，得到一个新的可行基，这就叫基变换。为了换基，要确定进基变量和离基变量。
(1)        确定进基变量。得到一个基本可行解，经检验，发现某些 时， 增加则目标函数值还可能增加。这时要将某个非基变量 换到基变量中去(称为进基变量)。若有两个以上的 ，为了使目标函数值增加得快，一般选 中的最大者，即max( )= ，则对应的 为进基变量。
(2)        确定离基变量。离基变量的确定依据q规则。
当确定 所对应的 为进基变量后，再求 与 对应的系数 的比值 ，选比值最小的 所对应的变量 为离基变量，即

对应的 为离基变量， 为主元素。

(3)        迭代(旋转运算)。确定了进基变量 和换出变量 后，要让它们的系数列向量对换位置，由此得到一个新基。利用矩阵的初等行变换将新基变为单位矩阵，即将主元素 变为1，主元素所在列的其他元素变为0。当非基变量为0时，就可得到新的基本可行解。
第七节  单 纯 形 表
根据第六节讨论的结果，可以利用单纯形法求解任何形式的线性规划问题。为了使计算过程紧凑，便于计算和检验，设计了一种计算表，称为单纯形表，如表2-8所示，其功能与增广矩阵相似。
表2-8  单纯形表
cj        c1        …        cm        cm+1        …        cn        &#61553;i
CB        XB        b        x1        …        xm        xm+1        …        xn       
c1
c2

cm        x1
x2

xm        b1
b2

bm        1
0

0        …
…

…        0
0

1        a1m+1
a2m+1

amm+1        …
…

…        a1n
a2n

amn        q1
q2

qm

0        …        0         
…         


表2-8中各列、各行的意义如下。
(1)         列中填入基变量，这里是 。
(2)         列中填入基变量的价格系数，这里是 , ,…, ，它们随基变量的改变而改变，并与基变量相对应。
(3)        b列中填入方程组右端的常数。
(4)         行表示各变量的价格系数。
(5)         行称为检验数行。对应各非基变量 的检验数为

对应基变量的检验数为
， =1,2,…,m
(6)        qi列的数字是在确定换入变量后，按 规则计算出来的。
表2-8称为初始单纯形表，以它为起点进行迭代，每迭代一次后就得到一个新的单纯形表。

单纯形表法的计算步骤如下。
第一步：找出初始可行基，确定初始基本可行解，建立初始单纯形表。
第二步：检查对应于非基变量的检验数 ，若所有的 ， ，则已得最优解，停止计算。否则，转入下一步。
第三步：在所有 中，若有一个 对应 的系数列向量 (即对i=1,2,…,m，均有 )，则此问题无解，停止计算，否则，转入下一步。
第四步：根据max ( )= ，确定xk为换入变量，根据q规则

确定 为换出变量，于是得到主元素 ，转入下一步。
第五步：在表中以 为主元素进行旋转运算，把 所对应的列向量

将 与 对换位置，则得到新的单纯形表。再以它为起点重复第二步，第三步……直到得到最优解为止。
例2-14  用例2-1来说明单纯形表法的计算步骤。


解：(1)根据例2-1线性规划问题的标准形式，取对应于松弛变量的单位矩阵为基， 为基变量，令非基变量 , ，可得一初始基本可行解为
=
将有关数字填入单纯形表的相应列中，得初始单纯形表，如表2-9所示。
表2-9中 行是表示目标函数中各变量的价值系数。在表的CB列中填入初始基变量的价值系数，它们都是0。检验数行各非基变量的检验数为


表2-9  初始单纯形表(1)
cj        2        3        0        0        0        qi
CB        XB        b        x1        x2        x3        x4        x5       
0
0
0        x3
x4
x5        15
12
14        0
4
2        [3]
0
2        1
0
0        0
1
0        0
0
1        5
—
7

2        3        0        0        0       

(2)        因为 ， 都大于零，且P1,P2的坐标有正分量存在，转入下一步。
(3)         ，因 ，所以 为换入变量

因 对应 那一行，所以 为换出变量。 对应行和 对应列交叉处[3]为主元素。
(4)        以[3]为主元素进行旋转运算，即对表2-9进行初等行变换，总能使P2变为 ，于是得表2-10。
表2-10  第一次迭代后的单纯形表
cj        2        3        0        0        0        qi
CB        XB        b        x1        x2        x3        x4        x5       
3
0
0        x2
x4
x5        5
12
4        0
4
[2]        1
0
0        1/3
0
-2/3        0
1
0        0
0
1        —
3
2

2        0        -1        0        0       

b列的数字表示 ， ， ，于是得到一个新的基本可行解为
=
(5)        检查表2-10中所有检验数 ，这时还有检验数 ，说明应将 作为换入变量，于是重复(2)，(3)，(4)的计算步骤，得到表2-11。
(6)        由于表2-11的最后一行中的所有检验数均小于或等于零。这表示目标函数已不可能再增大，于是得到最优解(b列数字)为
=
目标函数  = 。
表2-11  第二次迭代后的单纯形表
cj        2        3        0        0        0        qi
CB        XB        b        x1        x2        x3        x4        x5       
3
0
2        x2
x4
x1        5
4
2        0
0
1        1
0
0         1/3
4/3
-1/3        0
1
0         0
-2
  1/2        —
3
2

0        0        -1/3        0        -1       

例2-15  用单纯形表法计算下面的线性规划问题。


解：先化为标准型


填入单纯形表，如表2-12所示。
表2-12  初始单纯形表(2)
cj        2        3        0        0        qi
CB        XB        b        x1        x2        x3        x4       
0
0        x3
x4        1
4         3
2        -2
-1        1
0        0
1       

-1         1        0        0       

由于 ， 进基，而 ， ，没有比值，即当固定 时，当 趋于无穷，Z也趋于无穷，且满足约束条件，因而原问题具有无界解。
例2-16  用单纯形表法计算下面的线性规划问题。



解：先化为标准形，然后填入单纯形表如表2-13所示，进行迭代运算。
检验数全部非正，最优解为 = ，Z=20。非基变量 的检验数为零， 若增加，目标函数值不变，即当 进基时Z仍等于20。进基，出基继续迭代，得到另一最优解 = ，Z=20。它们的组合仍是最优解，所以原线性规划有多重最优解。
表2-13  单纯形迭代过程(1)
cj        2        3        0        0        0        qi
CB        XB        b        x1        x2        x3        x4        x5       
0
0
0        x3
x4
x5        4
10
2        -1
1
1        [2]
2
-1        1
0
0        0
1
0        0
0
1        2
5
—
sj        2        4        0        0        0       
3
0
0        x2
x4
x5        2
6
4        -1/2
[2]
1/2        1
0
0        1/2
-1
1/2        0
1
0        0
0
1        —
3
8
sj        4        0        -2        0        0       
3
2
0        x2
x1
x5        7/2
3
5/2        0
1
0        1
0
0        1/4
-1/2
3/4        1/4
1/2
-1/4        0
0
1        14
—
10/3
sj        0        0        0        -2        0       
3
2
0        x2
x1
x3        8/3
14/3
10/3        0
1
0        1
0
0        0
0
1        1/3
1/3
-1/3        -1/3
2/3
4/3       

0        0        0        -2        0       

补充有关检验数的表示方法：
本书是以max Z=CX；AX=b，X≥0为标准形式，并以检验数 ，Cj=1,2,…,n为最优解的判别准则。有的书以minZ=CX；AX=b，X≥0为标准形式，以检验数 ，j=1,2,…,n为最优判别准则，为了避免混淆，列出判别准则如表2-14所示。
表2-14  判别准则
标准型
规则        max Z=CX,AX=b，X≥0        min Z=CX,AX=b，X≥0
最优解判别        所有sj≤0        所有sj≥0
选进基变量        由max (sj>0)=sk确定xk为换入变量        由min (sj<0)=sk确定xk为换入变量
选出基变量         



第八节  单纯形法的进一步讨论
我们已经知道，要找出线性规划问题的初始基本可行解，就要先找出初始可行基。在约束条件方程 中，初始可行基一定要是一个m阶单位矩阵。对于“≤”形式的不等式，可用加松弛变量的方法得到。而对于“≥”或“=”形式的式子，就要采用人造基的方法，即减去一个非负的剩余变量再加上一个非负的人工变量，以得到m阶单位矩阵，对于“=”约束，只加一个非负的人工变量即可。
例2-17  将如下的约束条件化为标准形。


解：在约束条件中加入松弛变量、剩余变量和人工变量，得到

约束方程中 , , 的系数列向量构成三阶单位矩阵，可作为初始可行基，因基变量 ， 为人工变量，所以该基为人造基。令非基变量 , , , 为零，便可以得到一个初始基本可行解 为

因为人工变量是后加入到原约束方程组中的虚拟的变量，要求将它们从基变量中逐渐替换掉。若经过基的变换，基变量中不再包含有人工变量，则表示原问题有解。若经过基的变换，最后在基中还有某一个或几个人工变量，则意味原问题无可行解。下面介绍两种处理人工变量的方法。
一、大M法
我们希望人工变量对目标函数取值不受影响，因此只有在迭代过程中把人工变量从基变量中换出去，让它成为非基变量。为此假定人工变量在目标函数中的价值系数为M。M是一个很大的正数，并设人工变量为 。则目标函数实现最大化时 ，因此只要在基变量中存在人工变量，目标函数就不可能实现最大化。
同理，目标函数实现最小化时 ，只要在基变量中存在人工变量，目标函数就不可能实现最小化。
例2-18  用大M法求解例2-17。


解：用单纯形法求解如表2-15所示。因本例是求目标函数最小化，所以用所有 来判别目标函数是否实现了最小化。
表2-15  单纯形迭代过程(2)
sj        -3        1        1        0        0        M        M        qi
CB        XB        b        x1        x2        x3        x4        x5        x6        x7       
0
M
M        x4
x6
x7         11
3
1        1
-4
-2        -2
1
0        1
2
[1]        1
0
0        0
-1
0        0
1
0        0
0
1         11
1.5
1
sj        -3+6M        1-M        1-3M        0        M        0        0       
0
M
1        x4
x6
x3         10
1
1        3
0
-2        -2
[1]
0        0
0
1        1
0
0        0
-1
0        0
1
0        -1
-2
1        —
1
—
sj        -1        1-M        0        0        M        0        3M-1       
0
1
1        x4
x2
x3         12
1
1        [3]
0
-2        0
1
0        0
0
1        1
0
0        -2
-1
0        2
1
0         -5
-2
1        4
—
—
sj        -1        0        0        0        1        M-1        M+1       
-3
1
1        x1
x2
x3        4
1
9        1
0
0        0
1
0        0
0
1        1/3
0
2/3        -2/3
-1
-4/3        2/3
1
4/3        -5/3
-2
-7/3       
sj        0        0        0        1/3        1/3        M-1/3        M-2/3       

表2-15的最终计算表中所有 ，且基变量中无人工变量，故已得最优解，即
x =
Z=-3&#61620;4+1+9=-2

二、两阶段法
两阶段法是处理人工变量的另一种方法，这种方法是将加入人工变量后的线性规划问题分两段来求解。
第一阶段：要判断原线性规划问题是否存在基本可行解。办法是，先求解以下线性规划问题。


式中， 为人工变量。
用单纯形法对上述问题求解，若得到w=0，即所有的人工变量都变换为非基变量，这表示原问题已得到了一个基本可行解，转入第二阶段计算。若第一阶段的最终计算表出现w>0，这表示原问题无可行解，停止计算。
第二阶段：将第一阶段的最终计算表中的人工变量取消，并将第一阶段最终计算表中的目标函数行的数字换成原问题的目标函数的数字，继续求解，直到得到最优解。
各阶段的计算方法及步骤与以前讲的单纯形法完全相同。下面用例子说明两阶段法的计算。
例2-19  用两阶段法求解如下的线性规划问题。


解：先在上述问题的约束条件方程中加入人工变量，给出第一阶段的规划问题。
第一阶段：



这里 , 是人工变量。用单纯形法求解，如表2-16所示。因这里是求目标函数最小化，所以当所有的检验数 时，表示目标函数达到了最小值。
表2-16  单纯形迭代过程(3)
cj        0        0        0        0        0        1        1        qi
CB        XB        b        x1        x2        x3        x4        x5        x6        x7       
0
1
1        x4
x6
x7        11
3
1        1
-4
-2        -2
1
0        1
2
[1]        1
0
0        0
-1
0        0
1
0        0
0
1        11
3/2
1
sj        6        -1        -3        0        1        0        0       
0
1
0        x4
x6
x3        10
1
1        3
0
-2        -2
[1]
0        0
0
1        1
0
0        0
-1
0        0
1
0        -1
-2
1        —
1
—
sj        0        -1        0        0        1        0        3       
0
0
0        x4
x2
x3        12
1
1        3
0
-2        0
1
0        0
0
1        1
0
0        -2
-1
0        2
1
0        -5
-2
1       
sj        0        0        0        0        0        1        1       

第一阶段求得的结果是w=0， 。
因人工变量  ，即已从基变量中全部替换出。故原问题有解，转入第二阶段计算。
第二阶段：将第一阶段最终计算表中的人工变量 和 取消，并将 行的数字换成目标函数行的数字，其余数不变，继续求解，如表2-17所示。
表2-17中所有 ，已得最优解 ，min Z=-2。
以上讨论了用单纯形法求解线性规划问题的具体方法。实际应用时，可能会出现一些问题。以目标函数求极大为例，现说明如下。
(1)        非基变量的检验数为零。一般在最优单纯形式表中所有检验数 ，其中基变量的 ，非基变量的 ，但有时会出现非基变量的检验数 的情况。如果出现这种情况，说明原问题存在多个最优解，这种情况称线性规划具有任选最优解或多重最优解。反之，如果最优表中所有非基变量的检验数都为负数时，则不可能存在其他可行解使目标函数达到极大，即只有唯一最优解。

表2-17  单纯形迭代过程(4)
cj        -3        1        1        0        0        qi
CB        XB        b        x1        x2        x3        x4        x5       
0
1
1        x4
x2
x3        12
1
1        [3]
0
-2        0
1
0        0
0
1        1
0
0        -2
-1
0        4
—
—
sj        -1        0        0        0        1       
-3
1
1        x1
x2
x3        4
1
9        1
0
0        0
1
0        0
0
1        1/3
0
2/3        -2/3
-1
-4/3       
sj        0        0        0        1/3        2/3       

(2)        最小比值 相同。遇到这种情况，如果任选一个基变量出基，则进一步的迭代不一定会立即改进目标函数值，因而减低了单纯形法求解的效率，甚至可能导致循环。为避免这种情况，应按摄动原理处理。
(3)        检验数相同。选取哪一个非基变量进基一般是按检验数的大小来处理。如有一个以上的检验数 相同，选取哪一个非基变量进基就有几种可能了。遇到这种情况时，一般任选一个非基变量进基是不成问题的。选不同的非基变量进基的差别仅仅是迭代次数不同，这在事先是很难预测的，也没有必要多考虑，因为最终得到的结果是一样的。
(4)        最小比值规则失效。在迭代过程中，如果换入变量的系数列向量全部小于或等于0，则导致最小比值规则失效，这种情况表明线性规划问题无有限最优解。
第九节  线性规划问题的WinQSB求解
例2-20  某商店要制定某种商品第二季度的进货计划，已知该商店仓库容纳此种商品
的容量不能超过600件，3月底已存货200件，以后每月初进货一次。假定各月份此种商品买进售出的单价如表2-18所示，问：各月进货、售货各多少件才能使得利润最大(存货控制数学模型)？
表2-18  单价
月  份        买进单价/(元/件)        出售价格/(元/件)
4        17        18
5          16.5        18
6        17        19

(为了简单起见，只考虑进货时受到的仓库容量的限制、售货时受到进货量的限制这两个约束因素，对于货物存放在仓库内的消耗与保管费用不作考虑。)
解：设4、5、6月份的进货量分别为 , , 件；销售量分别为 , , 件。由于各月份的进货量要受到仓库容量的限制，所以有
4月份的进货约束为
，即
5月份的进货约束为
，即   
6月份的进货约束为
    ，即     
售货量还要受到存货量的限制，所以4月份的售货约束应满足
，即  
5月份的售货约束应满足
   ，即   
6月份的售货约束应满足
，即      
第二季度的利润目标函数为

约束条件为

解：运用WinQSB求解该线性规划模型，从“开始”菜单中，选择Linear and Integer Programming命令，求解线性规划问题。选择File｜New Problem命令，创建一个新问题，弹出如图2-5所示的对话框。在该对话框中，输入问题名称2，设置变量个数和约束条件个数，设置默认变量类型，选择目标函数类型为Maximization，然后单击OK按钮输入目标函数及约束系数、资源系数和价值系数如图2-6所示。
选择Edit｜Variable Names命令，修改变量X4,X5,X6为Y1,Y2,Y3，如图2-7所示。

                                 
    图2-5  定义问题                                                        图2-7  修改变量

图2-6  数据输入
输入完数据后，选择Solve and Analyze｜Solve the Problem命令，进行求解运算。得到如图2-8所示的求解结果。其中，Reduced Cost是检验数，Basis Status是基变量状态。

图2-8  求解结果
于是得到最优解为 =400， =600， =600， =600， =600， =600，max Z=6100。

习    题
1．用图解法求下列线性规划的最优解。
(1)                                      (2)         
(3)                                         (4)         
2．把下列线性规划化为标准形式。
(1)                                 (2)         
3．求出如下线性规划的所有基本解，并指出其中的基可行解和最优解。

4．求下列线性规划的解。
(1)                                         (2)         

(3)                                         (4)         
5．利用大M法或两阶段法求解下列线性规划。
(1)                                         (2)         
6．某公司计划在3年的计划期内，有4个建设项目可以投资。项目Ⅰ从第一年到第三年年初都可以投资，预计每年年初投资，年末可收回本利120%，每年又可以重新将所获本利纳入投资计划。项目Ⅱ需要在第一年年初投资，经过两年可收回本利150%，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不超过20万元。项目Ⅲ需要在第二年年初投资，经过两年可收回本利160%，但用于该项目的最大投资额不超过15万元。项目Ⅳ需要在第三年年初投资，年末可收回本利140%，但用于该项目的最大投资额不超过10万元。在这个计划期内，该公司第一年可供投资的金额有30万元。问：怎样的投资方案，才能使该公司在这个计划期内获得最大利润？
7．某饲养场饲养动物，每头动物每天需要700g蛋白质，30g矿物质，100g维生素。现有5种饲料可供选用，各种饲料每公斤营养成分含量及单价如表2-19所示。要求确定既满足动物生产的营养要求，又使费用最省的选择饲料的方案。
表2-19  营养成分和单价
饲  料        蛋白质/g        矿物质/g        维生素/g        价格/(元/公斤)
1         3         1          0.5        0.2
2         2          0.5          1.0        0.7
3         1          0.2          0.2        0.4
4         6        2        2        0.3
5        12          0.5          0.8        0.8

8．某医院每天各时间段至少需要配备护理人员的数量如表2-20所示。假定每人上班后连续工作8小时，试建立使总人数最少的计划安排模型。用适当的工具软件求解最优解。

表2-20  护理人员数
班  次        时  间        最少人数
1
2
3
4
5
6        6:00－10:00
10:00－14:00
14:00－18:00
18:00－22:00
22:00－2:00
2:00－6:00        80
90
80
70
40
30

9．某工场Ⅰ，Ⅱ，Ⅲ 3种产品在下一年各季度的合同预订数量如表2-21所示，该3种产品第一季度初无库存，要求在第四季度末每种产品的库存为150件。已知该厂每季度生产工时为15 000h，生产产品Ⅰ，Ⅱ，Ⅲ每件分别需要3h，4h，3h。因更换工艺设备，产品Ⅰ在第二季度无法生产。规定当产品不能按期交货时，产品Ⅰ，Ⅱ每件每迟交一个季度赔偿20元，产品Ⅲ赔偿15元。又知生产出来的产品不能在本季度交货，每件每季度的库存费用为5元。问：该如何安排生产，使总的赔偿和库存费用最少？
表2-21  合同预订数量
产  品        季  度
        1        2        3        4
Ⅰ        1500        1000        2000        1200
Ⅱ        1500        1500        1200        1500
Ⅲ        1500        2000        1500        2500

10．某制衣厂生产两种服装，现有100名熟练工人。已知一名熟练工人每小时生产10件服装Ⅰ或6件服装Ⅱ。根据销售部门消息，本周开始这两种服装的需求量将持续上升，如表2-22所示。该厂决定到第八周末需要培训出100名新工人，两班生产。已知一名工人一周工作40h，一名熟练工人每周最多可培训5名新工人，培训期间熟练工人和培训人员不参加生产。熟练工人每周工资400元，新工人在培训期间工资每周80元，培训合格后参加生产每周工资260元，生产效能同熟练工人。在培训期间，为了按期交货，工厂安排部分工人加班生产每周工作50h，工资每周600元。若所定的服装不能按期交货，每推迟交货一周的赔偿费为：服装Ⅰ每件10元，服装Ⅱ每件20元。问：工厂该如何安排生产，使各项费用总和最少？
表2-22  服装需求量
      周次
服装        1        2        3        4        5        6        7        8
Ⅰ        20        20        24        25        33        34        40        42
Ⅱ        12        14        17        33        22        25        25        25

chizp

此书编辑、排版结构破坏后看起来费劲

qxnhzy

休息休息