物流运筹学完整版课件全套ppt教学教程最全整套电子讲义幻灯片(最新)

1、运筹学(Operations Research)第一章 导论1.运筹学的定义2.运筹学的特点和工作步骤3.运筹学和物流的关系4.物流中的运筹学问题5.运筹学的发展简史知识要点1.1运筹学概述 运筹学是用数学方法研究各种系统最优化问题的学科。其研究方法是应用数学语言来描述实际系统，建立相应的数学模型，并对模型进行研究和分析，据此求得模型的最优解；其目的是制定合理运用人力、物力和财力的最优方案，为决策者提供科学决策的依据；其研究对象是各种社会系统，可以使对新的系统进行优化设计，也可以是研究已有系统的最佳运营问题。因此，运筹学既是应用数学，也是科学管理，同时也是系统工程的基础之一。1.1.1运筹学的

2、概念和特点（1）运筹学的概念运筹学( Operations Research )是一门新兴的应用学科。由于它所研究的对象极其广泛，所以有着许多不同的定义。英国运筹学杂志认为：“运筹学是运用科学方法(特别是数学方法)来解决那些在工业、商业、政府和国防部门中有关人力、机器、物质、金钱等大型系统的指挥和管理方面出现的问题的科学，目的是帮助管理者科学地决定其策略和行动。”1.1.1运筹学的概念和特点美国运筹学会(1976年)的定义是:“运筹学是研究用科学方法来决定在资源不充分的情况下如何最好地设计人机系统，并使之最好地运行的一门学科。”这从侧面描写了运筹学的特点。联邦德国科学辞典（1978年)上的定义

3、是:“运筹学是从事决策模型的数学解法的一门科学。”从这些定义中我们可以着出，虽然说法不一，但其基本含义大致相同，都包含了以下三方面的内容： 1.1.1运筹学的概念和特点 从这些定义中我们可以着出，虽然说法不一，但其基本含义大致相同，都包含了以下三方面的内容： 既定的目标和条件； 科学的方法和技术； 最优的决策方案。1.1.1运筹学的概念和特点（2）运筹学的特点 运筹学属于应用数学范畴，具体地说，它是一门管理数学，是一种通过对系统进行科学的定量分析，从而发现问题、解决问题的系统方法论。与其他的自然科学不同，运筹学研究的对象是“事”，而不是“物”，它揭示的是“事”的内在规律性，研究的是如何把“事”

4、办得更好的方式方法。 由此，我们可以看出运筹学主要有以下三个特点: 1.1.1运筹学的概念和特点 1.系统的整体优化 所谓系统可以理解为是由相互关联、相互制约、相互作用的部分组成的具有某种特定功能的有机整体。 例如物流系统由很多子系统组成，包括采购、运输、仓储、配送、流通加工、信息处理等，各子系统工作的好坏直接影响企业经营管理的好坏。但各子系统的目标往往不一致，生产部门为提高劳动生产效率希望尽可能增大批量；销售部门为满足更多用户的需要，要求增加花色品种；财务部门希望减少积压，加速流动资金周转，降低成本。 1.1.1运筹学的概念和特点2.多学科的配合 一个企业的有效管理涉及很多方面，运筹学研究中

5、吸收了来自不同领域、具有不同经验和技能的专家。由于专家们来自不同的学科领域，具有不同的经历经验 ,因此增强了集体提出问题和解决问题的能力。这种多学科的协调配合在研究的初期、在分析和确定问题的主要方面、在选定和探索解决问题的途径时，显得尤其重要。3.模型方法的应用 运筹学的研究不同于其他学科的实验室方法，其研究往往不能搬到实验室，而是建立这个问题的数学模型和模拟模型。如果说辅助决策是运筹学应用的核心，那么建立模型就是运筹学方法的精髓。1.1.1运筹学的概念和特点（3）运筹学的工作步骤提出和形成问题：要弄清问题的目标，可能的约束，问题的可控变量以及有关参数，搜集有关资料。建立模型：把问题中可控变量

6、、参数和目标与约束之间的关系用一定的模型表来出来。求解：用各种手段(主要是数学方法，也可用其他方法)将模型求解。解可以是最优解、次优解、满意解。复杂模型的求解需用计算机，解的精度要求可由决策者提出。解的检验：首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题。1.1.1运筹学的概念和特点解的控制：通过控制解的变化过程决定对解是否要作一定的改变。解的实施：是指将解应用到实际中必须考虑到实施的问题。如向实际部门讲清楚解的用法，在实施中可能产生的问题和修改。以上过程应反复进行。1.1.2运筹学的发展简史 运筹学的思想由来已久，我国历史上在军事和科学技术方面对运筹思想的运用是世界闻名的。军事方

7、面；公元前6世纪春秋时期著名的孙子兵法、战国时期的“田忌赛马”农业运输方面；北魏时期科学家贾思勰的齐民要术、“一举而三役济”的“丁渭造宫”水利方面：四川都江堰工程。1.1.2运筹学的发展简史 运筹学是20世纪40年代开始形成的一门应用数学学科，起源于第二次世界大战期间英、美等国的军事运筹小组。在第二次世界大战初期，英美两国的军事部门迫切需要研究如何将非常有限的人力和物力分配到各项军事活动中，以达到最好的作战效果。 第二次世界大战结束后，那些从事作战研究的人员纷纷转入工业生产部门和商业部门。由于组织内部与日俱增的复杂性和专门化所产生的问题，使人们认识到这些问题本质上与作战中曾面临的问题极为相似，

8、只是具有不同的现实环境而己，运筹学于是进入工商企业和其他部门。1.1.2运筹学的发展简史 1950年，英国的伯明翰大学正式开设了运筹学课程，同年第一本运筹学杂志运筹学季刊(O.R.Quarterly)在英国创刊。1951年，美国的莫尔斯(P.M. Morse)和金博尔(G.E. Kimball)合著的运筹学方法正式出版；1952年，美国运筹协会成立，并于同年出版了运筹学杂志Journal of ORSA，所有这些标志着这门科学基本形成，随后这门学科的理论体系也在不断完善。 20世纪50年代后期，我国著名科学家钱学森、华罗庚、许国志等将运筹学引入中国，并结合我国的特点在国内推广应用，著名的“打麦

9、场的选址问题”和“中国邮递员问题”就是在那个时期提出的。1.1.2运筹学的发展简史 目前，国内运筹学的专门刊物或较多刊登运筹学理论和应用的刊物主要有：运筹学学报、运筹与管理、系统工程学报、系统工程理论与实践、系统工程理论方法应用、数量经济、技术经济研究、预测、系统工程和系统科学与数学等。 经过半个多世纪的发展，运筹学的内容日趋成熟，逐渐形成了其理论与方法的基本框架，可以简单地概括为两技术、五规划和五论。1.1.2运筹学的发展简史 (1)两技术。当遇到有多种备选方案或不确定的情况，可以用决策技术来选择最满意的战略；在很多时候，决策者都需要为工程制定计划，列出时间表，并对其进行管理，而工程往往是巨

10、大的，包含很多工种、部门与员工等这时网络计划技术可以帮助决策者完成工程时间表的制订与控制。(2)五规划。在一定约束条件下寻求某种目标最大或最小的方法就是规划方法要解决的问题，包括线性规划、整数规划、非线性规划、目标规划与动态规划。一个典型的应用就是企业在一定资源限制下寻求利润最大或成本最小。1.1.2运筹学的发展简史 (3)五论。在决策过程中，首先要考虑的就是竞争对手的情况，这就需要应用对策论方法；企业必须维持一定的原料或产品的库存量以满足需求，同时为控制成本又必须压低库存，这就是库存论要解决的问题：而图论是用图形来描述问题，图形是由一些点以及一些点之间的连线表示，可用于解决运输设计、信息系统

11、的设计以及工程时间表的设计；有时也需要解决各种服务系统在排队等待现象中的概率特性，这就需要排队论，而非常重要的产品、工程的可靠性问题就需要可靠性模型和决策论来解决。1.2运筹学与物流 物流起源于第二次世界大战期间的军事后勤，它与科学管理共同采用的一项主要工具就是运筹学方法，运筹学应用的典型案例大都是物流作业或管理。 物流运筹学是运用数学模型、统计方法与代数等数量研究方法与技术为物流决策提供支持的一门新兴学科，它要求以系统的观念来看待和解决物流系统中日趋复杂化和动态化的决策问题。根据问题的要求，通过数学的分析和运算，对各种广义资源的运用、筹划以及相关决策等问题做出综合性的、合理的优化安排，以便更

12、经济、更有效地发挥有限资源的效益。1.2.1物流中的运筹学问题 运筹学与物流系统的关系如下： 从两者产生的时间来看，都是在二时期为军事所重视并利用发展起来的，同时产生必然有他们的联系性。 从功能上来说，运筹学是用来解决最优资源配置，而物流系统的主要功能(目标)也正是追求一种快速、及时、节约、合理的物流服务，这一点正好不谋而合。 1.2.1物流中的运筹学问题 为此，两者从一开始到现在都密切地联系在一起，并互相渗透和交叉发展。虽然后来一段时间，物流发展相对滞后于运筹学，但随着全球经济的不断发展，物流系统中运筹学的运用不断扩大，运筹学的作用不断凸显。 运筹学的主要分支在物流管理中都得到广泛的应用。

13、（1）规划论 （2）排队论 （3）存储论 （4）决策分析理论 （5）对策论 （6）图论与网络分析1.2.1物流中的运筹学问题（1）规划论 规划论主要研究计划管理工作中有关安排和估计的问题。一般可以归纳为在满足既定的要求下，按某一衡量指标来寻求最优方案的问题。如果目标函数和约束条件的数学表达式都是线性的，则称为“线性规划”；否则称为“非线性规划”。如果所考虑的规划问题可按时间划为几个阶段求解，则称为“动态规划”。1.2.1物流中的运筹学问题 应用规划论的典型的例子如“运输问题”，即将已给定数量和单位运价的某种物资从供应站运送到消费站，要求在供销平衡的同时，定出流量与流向，使总运输成本最小。我国曾

14、运用线性规划进行水泥、粮食和钢材的合理调运，取得了较好的经济效益。运用规划论方法还可以解决“合理选址”问题、“车辆调度”问题、“货物配装”问题、“物流资源(人员或设备)指派”问题、“投资分配”问题等。1.2.1物流中的运筹学问题1.2.1物流中的运筹学问题（2）排队论 排队论主要研究具有随机性的拥挤现象，它起源于有关自动电话的研究。由于叫号次数的多少和通话时间的长短都是不确定的，对于多条电话线路，叫通的机会和线路空闲的机会都是随机的，因此服务质量和设备利用率之间存在矛盾。所有这类问题度可以形象地描述为顾客来到服务台前要求接待服务。如果服务台已被其他顾客占用，那么就要等待，就要排队。另一方面，服

15、务台也时而空闲，时而忙碌。排队论的主要内容之一，就是研究等待时间、排队长度等的概率分布。根据服务台是一台或是多台的情况，排队问题又分为单线或多线的排队问题。1.2.1物流中的运筹学问题 排队论在物流过程中具有广泛地应用，例如机场跑道设计和机场设施数量问题，如何才能既保证飞机起降的使用要求，又不浪费机场资源； 又如码头的泊位设计和装卸设备的购置问题，如何达到既能满足船舶到港的装卸要求，而又不浪费港口资源； 再如仓库保管员的聘用数量问题，售票处的窗口的开设数量问题，物流机械维修人员的聘用数量问题，如何达到既能保证仓储保管业务、售票业务和物流机械的正常运转，又不造成人力浪费，这些问题都可以运用排队论

16、方法加以解决。1.2.1物流中的运筹学问题（3）存储论 存储论又称库存论。在经营管理中，为了促进系统的有效运转，往往需要对零部件、器材以及其他物资保障条件维持合理的储备。存储论就是研究在什么时间、以多人数量、从什么来源保证这些储备，并使得为保存合理的库存量和补充采购所需的总费用最小的理论。1.2.1物流中的运筹学问题 存储论是研究物资储备的控制策略的理论。存储物资是为了协调供应(生产)和需求(消费)之间关系的一种措施。例如工厂商店就必须考虑原材料和商品的库存量，库存太少可能造成停产或脱销，库存太多则造成积压，这些都直接影响企业的效益，因此库存管理是现代企业生产管理中的一个重要环节。库存论的模型

17、与以下几个要素有关。需求方式，即库存物资的输出方式。补充方式，即物资的输入方式。有关生产、库存、订货、缺货的费用。存贮策略，这里可以控制的是输入方式，控制订货时间和订货数量，形成库存控制的策略。的运筹学问题1.2.1物流中的运筹学问题（4）决策分析理论 现实世界有限的资源和人们无限的需求这一矛盾导致了竞争，由于竞争才使决策成为必要，是竞争催生了决策理论。战争是人类竞争的最激烈的表现形式，因而对于决策的研究也最早、最多地出现于对战争活动的研究中，从中国古代的孙子兵法和田忌赛马的故事中都可以看到我们祖先对决策的研究。1.2.1物流中的运筹学问题 决策所要解决的问题是多种多样的，在现代物流管理系统中

18、，决策论通过对系统状态的性质、采取的策略及效果的度量进行综合研究，确定决策准则，并选择最优的决策方案。1.2.1物流中的运筹学问题 （5）对策论 对策论是一种定量分析方法，可以帮助我们寻找最佳的竞争策略，以便战胜对手或者减少损失。 例如在一个城市内有两个配送中心经营相同的业务，为了争夺市场份额，双方都有多个策略可供选择，可以运用对策论进行分析，寻找最佳策略。 例如，面对一次次的铁路大提速，公路运输公司要与铁路系统争夺客源，有多种策略可供选择，也可用对策论研究竞争方案等。1.2.1物流中的运筹学问题（6）图论与网络分析 图论是物流运筹学应用十分广泛的一个分支。现代物流管理中经常碰到运输网络的合理

19、布置与选择、生产一序间的合理衔接搭配问题，各种管道、线路的通过能力以及仓库、附属设施的布局等问题。图论中把一些研究对象用节点表示，对象之间的联系用连线(边)表示，点、边的集合构成图。如果给图中各边赋予某些具体的权数，并指定了起点和终点，则称这样的图为网络图。图论与网络分析正是通过对图与网络性质及优化的研究。从而解决设计与管理中的时间最少、距离最短、费用最省等实际问题。1.2.1物流中的运筹学问题1.2.2物流运筹学发展的探索 运筹学作为一门实践应用的科学，已被广泛应用于工业、农业、商业、交通运输业、民政事业、军事决策等组织，解决山多种因素影响的复杂大型问题。目前，在物流领域中的应用也相当普遍，

20、并且解决了许多实际问题，取得了很好的效果。 改革开放以来，运筹学的应用更为普遍，特别是在流通领域应用更为广泛。例如运用线性规划进行全国范围的粮食、钢材、水泥的合理调运等；许多企业的作业调配、工序安排、场地选择等，也使用了运筹学方法，取得了显著的效果。与此同时，还创造了简单易行的“图上作业法”和“表上作业法”。1.2.2物流运筹学发展的探索 从物流和运筹学的关系不难看出，两者将不断渗透和交叉，物流系统中运筹的作用也将不断凸显，物流实现“5S”和克服物流系统中的制约关系(如高质量服务与成本的制约等)就必须考虑如何才能更有效地提供高效高质量节约的物流服务，就必须要运用到运筹学来解决原材料到半成品到成

21、品到顾客的过程中所涉及的运筹方面(规划问题、排队问题、库存、质量控制、对策问题等)。 随着物流运筹的迅速发展，物流科学和运筹学将会相得益彰，更好的应用于社会发展过程中。本章小结 本章首先介绍了运筹学的概念和特点，然后介绍了运筹学的发展简史，物流与运筹学的关系以及物流在运筹学中的问题，具体包括规划论、排队论、存储论、决策论、对策论和质量控制理论在物流中的应用做了分析介绍，最后在对物流运筹学发展的探索做了展望。习题1.什么是运筹学?它的特点有哪些？2.物流和运筹学有怎样关系？3.物流中的运筹学问题有哪些？4.物流运筹学会有怎样的发展前景？举例说明。5.举例说明运筹学的原理和思想在物流系统中的应用。

22、第二章 线性规划第一节 线性规划问题概述线性规划（Linear Programming）主要研究在既定的目标和条件下，如何最大限度地发挥有限资源的作用，从而完成最多最大的任务。简单地讲，也就是资源的最优利用问题。傅里叶(Fourier)于1823年、普桑(Poussin)于1911年就曾提出过一些与线性规划有关的问题，但未引起重视。1939年，苏联学者康脱洛维奇(L. V. Kantorovich)发表了重要著作生产组织与计划中的数学方法，针对生产的组织、分配、上料等一系列问题，提出了一种极值问题。这种问题不能用数学分析的方法解决，是一类新问题，他还提出了解乘数法的新方法，可惜这个工作在当时未

23、引起足够的重视。直到五十年代末期，苏联才重视了他的工作。1941年，希区柯克(Hitchcock)提出了运输问题，1945年，斯蒂格勒(Stigler)提出了营养问题，1947年，库普曼斯(Koopmans)提出了经济问题，这些都是关于线性规划的问题。真正奠定线性规划完整的概念、理论和算法的，应当归功于丹捷格(G. B. Dantzig)。1947年，丹捷格提出了在一组线性方程或线性不等式约束下，求某一线性形式极小值问题的数学模型，1947年夏天，丹捷格又提出了求解一般线性规划问题的单纯形法，并且电子计算机为这个算法提供了可能，终于使线性规划建立起来了。一、线性规划问题的提出提高经济效益，有两

24、种途径：一是进行技术创新；二是提高管理水平，改进生产组织与计划，最合理地安排各类生产要素。【例1】某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表2-1所示。表2-1 生产资源 产品 每件产品所需资源资源资源限量设备2410台时原材料A5015kg原材料B0510kg该工厂每生产一件产品可获利2元，每生产一件产品可获利4元，问应如何安排计划使该工厂获利最多？ 解：该问题可用以下数学模型来描述，设x1、x2分别表示在计划期内产品、的产量。2x1+4x2105x1155x210若用z表示利润，z = 2x1+4x2。综上，该计划问题可用数学模型表示

25、为：目标函数 max z = 2x1+4x2满足约束条件 2x1+4x210 5x1 15 5x210 x1、x20【例2】假定一个成年人每天需要从食物中获取3000cal热量，55g蛋白质和800mg钙。如果市场上只有4种食品可选，它们每千克所含热量、营养构成以及市场价格见表2-2。问如何选择各种食品，才能满足成年人每天的营养需要，同时使购买食品的费用最小？表2-2 食品所含热量、营养构成以及市场价格序号食品名称热量/cal蛋白质/g钙/mg价格/元1猪肉100050400102鸡蛋8006020063大米9002030034白菜200105002 解：该问题是如何选择各种食品的数量，以期在

26、满足营养的前提下使购买食品的费用最小。令xj（j=1, 2, 3, 4）表示第j种食品每天的购买量；然后根据每天从食物中获得营养的要求，猪肉中含有热量1000，现购买量为x1，故从猪肉中获得的热量为1000 x1；类似地，从鸡蛋、大米和白菜中获得的热量分别为800 x2、900 x3和200 x4，这样从食品中获得的总热量为1000 x1+800 x2+900 x3+200 x4，它应超过成人一天中所需的热量要求3000，于是，得到约束1000 x1+800 x2+900 x3+200 x43000。 同理，蛋白质和钙要求的约束：50 x1+60 x2+20 x3+10 x455400 x1+

27、200 x2+300 x3+500 x4800 再者，还有一些变量本身的约束，xj（j=1, 2, 3, 4）只能取非负值，故有下列非负约束：x10，x20，x30，x40最后确定购买这些食品的费用，若用z表示购买食品的总费用，则有：z = 10 x1+6x2+3x3+2x4 根据问题的要求，旨在总的费用最小，这是该问题的目标，可以表示为：min z = 10 x1+6x2+3x3+2x4综上所述，得数学模型为：min z = 10 x1+6x2+3x3+2x41000 x1+800 x2+900 x3+200 x4300050 x1+60 x2+20 x3+10 x455400 x1+200

28、 x2+300 x3+500 x4800 xj0 （j=1, 2, 3, 4）二、 线性规划模型线性规划问题具有以下3个特征。（1）都有一组决策变量，x=(x1，x2，xn)，每一组决策变量代表一个行动方案，且决策变量都是非负的。（2）都有一个目标函数，且是决策变量的线性函数，根据要求可以是求max或min。（3）都有一组约束条件，且是决策变量的线性等式或不等式。一般来说，线性规划问题可以用数学语言描述为：max(min)z = c1x1+c2x2+cnxna11x1+a12x2+a1nxn(=, )b1a21x1+a22x2+a2nxn(=, )b2 am1x1+am2x2+amnxn(=,

29、 )bm x1，xn0 也可以缩写为：max(min)z= ，j=(1, 2, , m) j=(1, 2, , n)或者用矩阵形式表示：max(min)z = CXAX (=, ) bX 0式中 C=(c1, c2, , cn)价值系数； 决策变量； 系数矩阵； 常数项 三、 线性规划模型的标准型由前节可知，线性规划问题有各种不同的形式。目标函数有的要求max，有的要求min；约束条件可以是“”，也可以是“”形式的不等式，还可以是等式。决策变量一般是非负约束，但也允许在（-，）范围内取值，即无约束。将这种多种形式的数学模型统一变换为标准型。这里规定的标准型为：在标准型中规定各约束条件的右端项b

30、i0，否则等式两端乘以“-1”。用矩阵描述时为： max z = CX （2-3） AX = b X 0 实际碰到各种线性规划问题的数学模型都应变换为标准型后求解。（一）目标函数是求最小值若要求目标函数实现最小化，即min z = CX，这时只需将目标函数最小化变换为求目标函数最大化，即令z = -z，于是得到max z= -CX。这就同标准型的目标函数的形式一致了，而且新问题与原问题具有同样的可行域和最优解（若存在），只是最优值（若存在）相差一个符号而已。（二）约束方程为不等式这里有两种情况：一种是约束方程为不等式，则可在不等式的左端加入非负松弛变量，把原不等式变为等式，同时规定目标函数中相

31、应的价值系数为零，不改变原问题的最优解；另一种是约束方程为不等式，则可在不等式的左端减去一个非负剩余变量（也可称松弛变量），把不等式约束条件变为等式约束条件，同时规定目标函数中相应的价值系数为零。（三）不是非负的变量如果某个变量xj0，则令：可得如果某个变量xk 的符号不受限制，则称xk为自由变量，或者说无约束，则可以引进两个非负变量xk 和xk，令：【例3】将例1的数学模型化为标准型。解：例1的数学模型为：在各不等式中分别加上一个松弛变量x3，x4，x5，使不等式变为等式。这时得到标准型：所加松弛变量x3、x4、x5表示没有被利用的资源。当然也没有利润，在目标函数中其系数为零，即c3，c4，

32、c5=0。【例4】将下面线性规划问题化成标准型。 解：该线性规划共有三处不符合标准型要求：目标函数z求最小值；第一、二个约束条件为不等式；决策变量x10；x3无约束。为此，通过以下步骤将该模型标准化。（1）决策变量 。（2）第一个约束引入松弛变量x4，第二个约束引入剩余变量x5。（3）目标函数min变为max。由于在第三个约束中资源量为-6，也可以从实际意义考虑将第三个等式约束两边同乘以-1，按照上述步骤，该问题的标准形式为：注意求解所得最优值的相反数才是原问题的最优值。第二节 线性规划问题解法一、 线性规划问题解的类型设线性规划的标准型为：max z = CX (2-4) AX = b (2

33、-5) X 0 (2-6)其中A是mn矩阵，mn且秩r (A) = m，即A中至少有一个mm满秩子矩阵。 现说明线性规划标准形式下各种解的含义。可行解：满足约束条件(2-5)和(2-6)的X = (x1, x2, , xn)T，称为线性规划问题的可行解。可行域：全体可行解的集合称为线性规划的可行域，一般记作D=X|AX=b, X0。最优解：使目标函数达到最大值（或最小值）的可行解X* = (x1, x2, , xn)T称为线性规划的最优解。最优值：最优解的目标函数值称为线性规划的最优值。基：若A中mm子矩阵B满足r(B) = m，则称B是线性规划问题的一个基。也就是说，矩阵B是由A的m个线性无

34、关列向量所构成，不妨设为：称Pj (j=1, 2, , m)为基向量。基变量、非基变量：与基向量Pj (j=1, 2, , m)相对应的变量xj (j=1, 2, , m)为基变量，其他决策变量称为非基变量。基本解：记基变量为XB=(x1, x2, , xm)T，非基变量为XN=(xm+1, xm+2, , xn)T，称满足方程组BXB=b且XN=0的解为基本解。基本可行解：若基本解XB=B-1b0，则称该解为基本可行解，也称为基可行解，B为可行基。线性规划解之间的关系如图2-1所示。图2-1 解之间的关系非可行解基本解可行解基本可行解【例5】某线性规划的约束条件如下，求其基本解和基本可行解。

35、x1+3x2+x3=54x1-2x2+x4=2 x1, ,x40解：线性规划的系数矩阵： A的子矩阵：非奇异，因而B1是一个基，其中：x1，x2为基变量，x3，x4为非基变量。令x3 = x4 = 0，则x1 =8/7 , x2 = 9/7X(1) = (8/7, 9/7, 0, 0)T是基本解，因为满足非负条件，因此还是基本可行解。同理，A的子矩阵：非奇异，因而B2是一个基，其中：x2，x3为基变量，x1，x4为非基变量。令x1 = x4 = 0，则x2 = -1，x3 = 8得到一个关于基B2的基本解X(2) = (0, -1, 8, 0)T，但不满足非负条件，因此不是基本可行解。其余基本

36、解和基本可行解读者可按照以上方法求出。二、 线性规划的图解法对于只有两个变量的线性规划问题，可以直接使用图解法求解。图解法简单直观，有助于了解线性规划问题求解的基本原理。现对下例使用图解法。max z = 2x1 + 3x2x1 + 2x2 8 4x1 16 （2-7） 4x2 12x1，x2 0在以x1、x2为坐标轴的直角坐标系中，非负条件x1，x20是指第一象限。上例的每一个约束条件都代表一个半平面。如约束条件x1+2x28是代表以直线x1+2x2=8为边界的左下方的半平面，若同时满足x1，x20，x1+2x28，4x116和4x212的约束条件的点，必然落在由这三个半平面交成的区域内。由

37、上例的所有约束条件为半平面交成的区域见图2.2中的阴影部分。阴影区域中的每一个点（包括边界点）都是这个线性规划问题的解（称可行解），因而此区域是上例的线性规划问题的解集合，称它为可行域。图2-2 线性规划可行域再分析目标函数z = 2x1+ 3x2，在这坐标平面上，它可表示以z为参数、-2/3为斜率的一族平行线：x2 = -(2/3)x1 + z/3位于同一直线上的点，具有相同的目标函数值，因而称它为“等值线”。当z值由小变大时，直线x2 = -(2/3)x1 + z/3沿其法线方向向右上方移动。当移动到Q2点时，使z值在可行域边界上实现最大化（见图2.3），这就得到了上例的最优解Q2，Q2点

38、的坐标为（4, 2）。于是可计算出z = 14。图2-3 图解法上例中求解得到问题的最优解是唯一的，但对一般线性规划问题，求解结果还可能出现以下几种情况： （一）无穷多最优解（多重解）若将上例中的目标函数变为求max z = 2x1 + 4x2，则表示目标函数中以参数z的这族平行直线与约束条件x1+2x28的边界线平行。当z值由小变大时，将与线段Q2Q3重合（见图2-4）。线段Q2Q3上任意一点都使z取得相同的最大值，这个线性规划问题有无穷多最优解（多重解）。图2-4 无穷多最优解示图（二）无界解对下述线性规划问题max z = x1 + x2-2x1+x24 x1-x22 x1，x20用图解

39、法求解结果见图2-5。从图中可以看到，该问题可行域无界，目标函数值可以增大到无穷大。称这种情况为无界解或无最优解。 图2-5 无界解示图-2-22240 x1x2（三）无可行解。如果在方程2-7的数学模型中增加一个约束条件-2x1+x24，该问题的可行域为空集，即无可行解，也不存在最优解。当求解结果出现(2)、(3)两种情况时，一般说明线性规划问题的数学模型有错误。前者缺乏必要的约束条件，后者是有矛盾的约束条件，建模时应注意。从图解法中直观地见到，当线性规划问题的可行域非空时，它是有界或无界凸多边形。若线性规划问题存在最优解，它一定在可行域的某个顶点得到；若在两个顶点同时得到最优解，则它们连线

40、上的任意一点都是最优解，即有无穷多最优解。图解法虽然直观、简便，但当变量数多于三个以上时，它就无能为力了。所以在下一小节中要介绍一种代数法单纯形法。三、 线性规划的单纯形法 （一）单纯形法的基本思想 单纯形法的基本思想是：从线性规划的标准型出发，从可行域中某一个基本可行解（一个顶点）开始，然后按照一定的方法迭代到另一个基本可行解（顶点），并且使目标函数达到最大值时，就得到了最优解。【例6】用单纯形法求解以下线性规划问题。max z =2x1+4x2 x1 2 2x28 3x1+2x212 x1, x20 解：1.先转化为标准型。引入松弛变量x3，x4，x5，将上述问题转化为标准型如下：max

41、z = 2x1+4x2 x1 + x3 = 2 (2-8) 2x2 + x4 = 8 3x1 + 2x2 + x5 = 12 x1, , x5 02.找一个初始基本可行解X(0)。上述标准型的约束方程组的系数矩阵如下：很显然，含有3个线性无关的单位列向量所组成的子矩阵是非奇异的：B0是线性规划问题的一个基。而且由于约束方程组的右端常数是非负的，所以B0显然是一个可行基，x3，x4，x5是关于可行基B0的基变量，x1，x2是非基变量。为了求初始基本可行解，只需要在约束方程组中令非基变量x1 = x2 = 0，可得x3 = 2，x4 = 8，x5 = 12。于是得到初始基本可行解：X(0) = (

42、0, 0, 2, 8, 12)T 其对应的目标函数值：z0 = 20+40 =03.检验X(0)是否是最优解。由目标函数的表达式：z = 2x1+4x2可知，非基变量x1，x2前面的系数都为正数，也就是说如果把非基变量x1，x2中的任意一个变为基变量，而且满足非负条件，都可以使目标函数值增大。可见，X(0)不是最优解。4.第一次迭代。为使目标函数值较快地增加，一般选择正系数最大的非基变量作为入基变量。在这里，把x2作为入基变量，让其数值尽可能地增大，x1仍是非基变量。从原来的基变量x3，x4，x5中选择一个作为非基变量。但是x2的值不能无限制地增大，它要受到约束方程组的限制，由线性规划问题的约

43、束方程组得：x3 = 2-x1 x4 = 8-2x2 x5 = 12-3x1-2x2 将x1 = 0，x2 = 代入上面方程组，为了使目标函数值尽可能地得到改善，希望尽可能地增大，但必须保证x3，x4，x5保持非负，从而的值要满足：x3 = 2x4 = 8-2x2 0 x5 = 12-2x2 0即：x2 = = min8/2, 12/2= 4 相应地有：x3 = 2x4 = 0 x5 = 4 这表明，应该确定x4为出基变量。于是新的基变量为x2，x3，x5，非基变量为x1，x4。令非基变量为零，代入式(2-8)的约束方程组可得第一次迭代后的基本可行解X(1) = (0, 4, 2, 0, 4)

44、T其对应的目标函数值：z1 = 20+44 = 16 z1 z0，这表明第二种方案比第一种方案有明显改善。5.检验X(1)是否是最优解。为了回答这个问题，将式(2-8)的约束方程组改写为用非基变量x1，x4表示基变量x2，x3，x5的表达式。用高斯消去法得到：x3 = 2 - x1x2 = 4 -x4x5 = 4 3x1 +x4代入目标函数，得到用非基变量x1，x4表示的目标函数：z = 16 + 2x1 - 2x4非基变量x1前的系数是正数，也就说如果把非基变量x1转换成为基变量，而且取正值，目标函数值还会进一步增大。因此，X(1)不是最优解。6.第二次迭代。同样可以根据第一次迭代的方法，选

45、取非基变量x1，使它变为入基变量，并尽可能使它取最大的值，x4仍是非基变量。从原来的基变量x3，x2，x5中选择一个转化成为非基变量。但是x1的值不能无限制地增大，它要受到约束方程组的限制，由线性规划问题的约束方程组得：x3 = 2 - x1x2 = 4 -x4x5 = 4 3x1 +x4将x1 = ，x4 = 0代入上面方程组，为使目标函数值尽可能地得到改善，希望尽可能地增大，但必须保证x3，x2，x5保持非负，从而的值要满足：x3 = 2-x1 0 x2 = 4 0 x5 = 4-3x1 0即： x1 = = min2/1, 4/3=4/3相应地有：x3 = 2/3x2 = 4 x5 =

46、0这表明，应该确定x5为出基变量。于是新的基变量为x1，x2，x3，非基变量为x4，x5。令非基变量为零，代入式(2-8)的约束方程组可得第二次迭代后的基本可行解：X(2) = (4/3, 4, 2/3, 0, 0)T其对应的目标函数值：z2 = 24/3 + 44 = 56/3z2z1，这表明，第三种方案比第二种方案有改善。7.检验X(2)是否是最优解。同样可以用检验X(1)的方法来检验X(2)，将式(2-8)的约束方程组改写为用非基变量x4，x5表示基变量x1，x2，x3的表达式。用高斯消去法得到：代入目标函数，得到用非基变量x4，x5表示的目标函数：这时，目标函数中非基变量x4，x5前面

47、的系数都已小于零，也就是说目标函数值不能进一步增大了，目标函数已取得最大值，所以X(2)就是最优解。通过以上例子，可以归纳出单纯形法的计算步骤如下：1.建立实际问题的线性规划数学模型。2.把一般形式的线性规划问题转化为标准型。3.找出初始基本可行解。4.检验初始基本可行解是否是最优解。5.如果不是，进行迭代，求出新的基本可行解。6.重复步骤（4）和（5），直到求出最优解为止，或者判定无最优解。（二）一般线性规划问题的求解从以上内容可以看出，用单纯形法求解线性规划问题，关键是要找出初始基本可行解。有些标准型的线性规划问题的初始基本可行解比较容易得到，有些比较难。可把它们分成两种类型来分别讨论。给

48、出线性规划问题的标准型：第一种情况：设式(2-9)的系数矩阵A中含有m个线性无关的单位列向量，且bi 0（i =1, 2, , m）。为了不失一般性，假定m个线性无关的单位列向量在A中的前m个列，构成m阶单位矩阵。也就是说，可以把式(2-9)表示成：max z = c1x1 + c2x2 + + cnxnx1 + a1,m+1xm+1 + a1,m+2xm+2 + + a1nxn = b1 x2 + a2,m+1xm+1 + a2,m+2xm+2 + + a2nxn = b2 (2-10) xm + am,m+1xm+1 + am,m+2xm+2 + + amnxn = bmx1, x2, ,

49、 xn 0其中，bi0 (i=1, 2, , m)第二种情况：如果系数矩阵A中不存在单位矩阵，则可以采用人工变量法进行处理，把它转化成为第一种情况。人工变量法会在后面介绍。1.初始基本可行解的确定由于单位矩阵B0是问题式(2-10)的一个可行基，x1，x2，xm是关于可行基B0的基变量，xm+1，xm+2，xn是关于可行基B0的非基变量。因此，相应地可得到一个基本可行解：X(0) = (b1, b2, , bm, 0, , 0)T即为所要的初始基本可行解。也就是说，想要找出线性规划问题的初始基本可行解，可以从系数矩阵里寻找m个线性无关的单位列向量，但单位矩阵并不是显然存在的，也可分成两种情况来

50、分析。 第一种情况： 线性规划问题的系数矩阵A中本来就存在m个线性无关的单位列向量，则以此单位矩阵为初始基矩阵即可。【例7】给出线性规划问题：max z = 3x1 + 4x2 + 2x3 - 4x5x1 + 2x2 - 2x3 + 3x5 = 63x2 + x4 - 4x5 = 12 -x2 + 3x3 + 5x5 + x6 = 9x1, , x6 0系数矩阵： 含有3个线性无关的单位列向量P1，P4，P6，组成了一个单位矩阵：即为初始基矩阵。关于基B0的基变量为x1，x4，x6，非基变量为x2，x3，x5，初始基本可行解为：X(0) = (6, 0, 0, 12, 0, 9)T第二种情况：

51、线性规划问题的系数矩阵A中不存在m个线性无关的单位列向量，但所有约束条件都是“”形式的不等式，可以利用前面所讲的转化标准型的方法，在每个约束条件的左端加上一个非负的松弛变量，松弛变量的系数列向量所组成的矩阵就是一个单位矩阵，以此单位矩阵为初始基矩阵即可。【例8】给出线性规划问题：max z = 2x1+3x2x1 + x2 5x1 + 2x2 6x1 4 x2 2x1,x2 0引入松弛变量x3，x4，x5，x6，将上述线性规划问题转化为标准型：max z = 2x1 + 3x2x1 + x2 + x3 = 5x1 + 2x2 + x4 = 6x1 + x5 = 4 x2 + x6 = 2x1,

52、 , x6 0初始可行基为P3，P4，P5，P6所组成的单位矩阵，基变量为x3，x4，x5，x6，非基变量为x1，x2，相应的初始基本可行解为：X(0) = (0, 0, 5, 6, 4, 2)T线性规划问题化为标准型以后，如果系数矩阵中含有单位矩阵，则该标准型称为规范型。2.最优性检验需要一个判别的法则，以便判定初始基本可行解及以后的基本可行解是否是最优解，从而决定是否需要继续进行迭代。为了不失一般性，经某一次迭代并经过整理重新编号后，约束条件为： 令非基变量xj = 0，得基变量xi =bi (i=1, 2, , m)。可得基本可行解：X(0) = (b1，b2，bm，0, , 0)T由可

53、得：代入目标函数表达式中，可得：式(2-12)是用非基变量来表示目标函数的表达式，其中z0表示基本可行解X(0) = (b1, b2, , bm, 0, , 0)T所对应的目标函数值；j称为非基变量xj的检验数，因为基变量不会在(2-12)中出现，所以规定所有基变量的检验数为零。 定理2.1 最优性判别定理。若所有非基变量的检验数j0（j=m+1, , n），则基本可行解X(0) = (b1，b2，bm，0，0)T为最优解。证：因为j0，xj0 (j=m+1, ,n)，由式(2-12)知：而基本可行解X对应的目标函数值为z0，故X(0)为最优解。定理2.2 无有限最优解判别定理。若至少存在一个

54、k 0（m+1kn），并且对于所有的i = 1, 2, , m均有aik0，那么该线性规划问题没有有限最优解。证：构造一个新的可行解X：因为bi0，0，aik0，故0（i = 1, 2, , m），由此可见，对任意0，X都是可行解，其对应的目标函数值可由式(2-12)求得：z = z0 + k因为已知k 0，所以当+时，目标函数无最大值，也就是说，该线性规划问题无有限最优解。3.基变换若在最优性检验中，初始基本可行解既不是最优解，也不是属于无有限最优解的情况，这时需要找一个新的基本可行解。具体做法是在保证线性无关的基础上，用某个非基变量代替原可行解中的某个基变量，得到一个新的可行解，这就是基变

55、换。在这里，关键是如何选择适当的基变量和非基变量之间的变换，使目标函数值得到改善。如果某个非基变量在迭代后成为基变量，这个变量就称为入基变量。如果某个基变量在迭代后成为非基变量，这个变量就称为出基变量。在基变换中首先要确定入基变量，然后再确定出基变量。（1）入基变量的确定。从式(2-12)可以看到，如果某些j0，则xj的增大还可以增大目标函数值，则需要把非基变量xj作为入基变量。那么，如果有两个及以上j0，那么应该选哪个非基变量作为入基变量呢？为了使目标函数值尽可能快地增大，一般选j0中的大者，即：max(j|j0) = k则xk为入基变量。（2）出基变量的确定。假设迭代以后得到基本可行解，x

56、k是入基变量，基本可行解的n个分量为为了使x1，x2，xm中有一个基变量成为非基变量，取值为零，其余变量仍然保持非负，故的取值应满足以下法则。出基变量的确定法则：若： 则取xl为出基变量。 以上法则也称为法则。 （三）单纯形表 前面介绍了一般线性规划问题的求解方法单纯形法，为了便于计算和检验，人们设计了一种计算表，称为单纯形表，其功能与增广矩阵相似。 给出以x1，x2，xm为基变量的规范型：max z = c1x1 + c2x2 + + cnxnx1 + a1,m+1xm+1 + a1,m+2xm+2 + + a1nxn = b1 x2 + a2,m+1xm+1 + a2,m+2xm+2 +

57、+ a2nxn = b2 (2-13) xm + am,m+1xm+1 + am,m+2xm+2 + +amnxn = bmx1, x2, , xn 0 其中，bi 0 (i = 1, 2, , m)。 从规范型出发，可得到初始基本可行基：基本可行解为：X(0) = (b1, b2, , bm, 0, , 0)T为了检验所得到的基本可行解是不是最优解，需要从式(2-11)求出所有非基变量的检验数j (j = m+1, , n)，基本可行解的目标函数值是z0 = 将目标函数、约束方程的系数、目标函数值、检验数等列成表，见表2-3。表2-3中，各部分的含义如下： cj行填入式(2-13)目标函数中

58、变量xj的系数(j = 1, 2, , n)； XB列填入基变量；CB列填入基变量所对应的价值系数；b列填入约束方程组右端的常数；j行填入所有变量的检验数（其中基变量的检验数为零），及基本可行解对应的目标函数值z0。其中最大的一块矩形区域填入约束方程组的系数矩阵。i列的数字是在确定入基变量以后，按法则计算后填入，并利用这一列值来确定出基变量。【例9】给出线性规划问题：max z = 2x1 - 2x2 + x3x1 + x2 + x3 48x1 2x2 + x3 12x1 + 2x2 - x3 24x1，x2，x3 0 解：引入松弛变量x4，x5，x6，化为标准型max z = 2x1 - 2

59、x2 + x3x1 + x2 + x3 + x4 = 48x1 2x2 + x3 + x5 = 12x1 + 2x2 x3 + x6 = 24x1, , x6 0根据标准型建立初始单纯形表，见表2-4。 由表2-4可得初始基本可行解：X(0) = (0, 0, 0, 48, 12, 24)T其相对应的目标函数值为0。为了检验X(0)是否为最优解，从表中最后一行可以看到有两个非基变量x1和x3的检验数1 = 2和3 = 1均大于零，所以X(0)不是最优解。因为max 1，3 = max2, 1 = 2，所以取x1为入基变量，并把x1所在列称为“主元列”。利用法则来确定出基变量： 所以取x5为出基

60、变量，并把x5所在的行称为“主元行”。主元行与主元列交叉的数字称为“主元素”，即表中带有“（）”的数字。 在表中以主元素为旋转轴心进行旋转运算，即对增广矩阵进行初等行变换，总能使： 其他数字也作相应变动，并重新计算检验数，得第一次迭代后的单纯形表，见表2-5。由表2-5可得：X(1) = (12, 0, 0, 36, 0, 12)T 其相对应的目标函数值为24。 由于20，故X(1)还不是最优解，以x2为入基变量。 又 = min36/3, -, 12/4=3，故取x6为出基变量。 与第一次迭代方法相同，找到主元行、主元列、主元素以后，进行第二次迭代，得到单纯形表，见表2-6。 由表2-6可得