运 筹 学
（Operations Research）
华南理工大学工商管理学院
工业工程系
《运筹学》
Operations Research
运筹帷幄，
决胜千里
史记《张良传》
*
课程目标
运筹学是管理科学的主要组成部分，运筹学模型和方法是管理学科数量分析的重要方法。
了解运筹学、管理科学在现代化管理中的重要地位，运筹学在管理中的应用范围。
掌握运筹学分析的技巧，建立起实践观点、系统观点和优化观点。
将管理中出现的问题归结为抽象的数学模型，应用数学等科学方法建立模型，借助电子计算机求解模型，为管理决策提供支持。
运 筹 学
在英国称为 Operational Research；
在美国称为 Operations Research；
在港台译为 “运作研究”或“作业研究”；
在中国大陆译为 “运筹学”。
英文缩写为 .
绪 论
§1 运筹学的发展简史
§2 运筹学的定义与特点
§3 运筹学的主要内容
§4 运筹学研究的基本方法
§5 运筹学的广泛应用及发展趋势
§6 学习运筹学的重要性
§1 运筹学的发展简史
一般说来，运筹学起源于第二次世界大战，但在这之前已有许多蕴含运筹学思想和方法的书籍和论文出现，例如：
1939年前苏联学者康托洛维奇(Л.в.Канторович)出版了《生产组织与计划中的数学方法》一书（属于运筹学中的规划论），对列宁格勒胶合板厂的计划任务建立了一个线性规划的模型，并提出了“解乘数法”的求解方法，为数学与管理科学的结合做了开创性的工作；
在商业方面，列温逊在20世纪30年代已用运筹思想分析商业广告、顾客心理；
冯·诺意曼( Neumann)等所著《对策论和经济行为》一书（运筹学中的对策论的创始作）成书前所发表的一系列论文在1928年就开始刊出；
存储论的最优批量公式是在20世纪20年代初被提出的；
1917年，排队论的先驱者丹麦工程师埃尔朗()在哥本哈根电话公司研究电话通信系统时，提出了排队论的一些著名公式；
1915年哈里斯()推导出经济订货批量公式；
1914年兰彻斯特(Lanchester)提出军事运筹学的战斗方程；
1736年欧拉(E Euler)解决了著名的哥尼斯堡七桥问题。
因此运筹学的起源还能追溯得更早。但
是，限于生产力发展水平，这些思想方
法只是停留在自发地和零星地应用于个
别问题上，还没有形成一种系统的科学
方法。
一、运筹学的产生
运筹学这个名词的正式使用是在1938年，当时英国为解决空袭的早期预警，做好反侵略战争准备，积极进行“雷达”的研究。但随着雷达性能的改善和配置数量的增多，出现了来自不同雷达站的信息以及雷达站同整个防空作战系统的协调配合问题。
1938年7月。波得塞(Bawdsey)雷达站的负责人罗伊()提出立即进行整个防空作战系统运行的研究，并用“operational research”一词作为这方面研究的描述，这就是.(运筹学)这个名词的起源。
1940年9月英国成立了由物理学家布莱克特()领导的第一个运筹学小组。后来发展到每一个英军指挥部都成立运筹学小组。
1942年美国和加拿大也都相继成立运筹学小组，这些小组在确定扩建舰队规模、开展反潜艇战的侦察和组织有效的对敌轰炸等方面作了大量研究，为取得反法西斯战争的胜利及运筹学有关分支的建立作出了贡献。
这些研究，由于综合地运用了科学方法和技术，纠正了人们一些直观想象的错误，解决了当时战争中提出的一些新问题，从而引起人们对运筹研究的重视。据统计，战时同盟国参加(军事)运筹研究的科学工作者超过了700人。
二、运筹学在中国
1． 朴素的运筹学思想在我国古代文献中
就有不少记载，例如：
田忌赛马——田忌赛马的典故是说一次齐王和田忌赛马，规定双方各出上、中、下三个等级的马各一匹。如果按同等级的马比赛，齐王可获全胜，但田忌采取的策略是以下马对齐王的上马，以上马对齐王的中马，以中马对齐王的下马，结果田忌反以二比一获胜。
丁渭主持皇宫的修复
——丁渭修皇宫的故事发生在北宋时代，皇宫因火焚毁，由丁渭主持修复工作。他让人在宫前大街取土烧砖，挖成大沟后灌水成渠，利用水渠运来各种建筑材料，工程完毕后再以废砖乱瓦等填沟修复大街，做到减少和方便运输，加快了工程进度。
2．运筹学在中国
中文译名“运筹学”则是出自《史记》卷八的“高祖本记”中刘邦的一句话：“夫运筹于帷幄之中，决胜于千里之外，吾不如子房”。借用了其中的“运筹”二字，将. 正式译作运筹学，说明运筹学不只是数学。还含有运用筹划，以策略取胜等意义，比较恰当地反映了这门学科的性质和内涵。
在20世纪50年代中期，钱学森、许国志等教授全面介绍运筹学，并结合我国的特点在国内推广应用。
我国第一个运筹学小组于1956年在中国科学院力学研究所成立，1958年建立了运筹学研究室。1960年在山东济南召开全国应用运筹学的经验交流和推广会议，1962年和1978年先后在北京和成都召开了全国运筹学专业学术会议，1980年4月成立中国运筹学学会。
除中国运筹学学会外，中国系统工程学学会以及与国民经济各部门有关的专业学会，也都把运筹学应用作为重要的研究领域。
我国各高等院校，特别是各经济管理类专业中已普遍把运筹学作为一门专业的主干课程列入教学计划之中。
1957年，我国在建筑业和纺织业中首先应用运筹学。
从1958年开始在交通运输、工业、农业、水利建设、邮电等方面陆续得到推广应用。比如，粮食部门为解决粮食的合理调运问题，提出了“图上作业法”，我国的运筹学工作者从理论上证明了它的科学性；在解决邮递员合理投递路线时，管梅谷教授提出了国外称之为“中国邮路问题”的解法。
从20世纪60年代起，运筹学在钢铁和石油部门开始得到了比较全面、深入的应用。
1970年在全国大部分省、市和部门推广优选法；70年代中期，最优化方法在工程设计界受到了广泛的重视、并在许多方面取得成果；排队论开始应用于矿山、港口、电信及计算机设计等方面；图论用于线路布置、计算机设计、化学物品的存放等。
70年代后期，存储论在应用汽车工业等方面获得成功。近年来，运筹学已趋向研究和解决规模更大、更复杂的问题，并与系统工程紧密结合。
综观运筹学在国内外发展的历史，我们可以看出，运筹学的发展是来自于物理学家、经济学家、数学家、其他专业的学者、军官和各行业的实际工作者的共同努力。
§2 运筹学的定义与特点
一、运筹学的定义
运筹学是一门新兴的学科，至今还没有公认统一且确切的定义。
英国运筹学会给运筹学下的定义是：“运筹学是运用科学方法（特别是数学方法）来解决那些在工业、商业、政府部门、国防部门中有关人力、机器、物资、金钱等大型系统的指挥和管理方面所出现的问题，其目的是帮助管理者科学地决定其策略和行动”。
运筹学作为一门定量决策科学，利用数学、计算机科学以及其它科学的新成就，研究各种系统尤其是经济管理系统中运行的数量化规律，合理使用与统筹安排人力、物力、财务等资源，为决策者提供有依据的最优方案，以实现最有效的管理并获得满意的经济效益和社会效果。
运筹学的本质是“事理科学”。它揭示了事的内在联系，研究如何把事办好。
从运筹学的定义和特点我们可以看出：
运筹学的研究对象：是“事”。例如，各种有组织的系统（主要是经济组织系统）的经营管理问题；
运筹学所研究的系统是在一定时空条件下存在，为人所能控制和操纵，有两个以上行动方案可供抉择而需要人们作决策的系统；
运筹学研究的问题是能用数量表示与系统各项活动有关而带有运用、筹划、使用、安排、控制和规划等方面的问题；
运筹学的任务就是在现有条件下，根据问题的要求，对有关活动中的错综复杂的数量进行分析研究，并归纳为一定的模型，然后运用有关原理和方法求得解决问题的最优途径和方案，以求实现预期目的。
二、运筹学的特点
运筹学的目的在于解决实际问题，它所使用的全部假设和数学模型无非都是解决实际问题的工具，有助于各种经济活动和管理问题的解决，最终能向决策者提供建设性方案并能收到实效。因此，它的应用并不受行业和部门的限制，已被广泛应用于工商企业、军事部门、服务行业和经济管理部门中。就其理论与应用意义上归纳，运筹学具有如下一些主要特点：
*
1．强调系统整体最优
运筹学针对研究的实际问题，从系统的观点出发，以整体最优为目标，研究各组成部分的功能及其相互间的影响关系， 解决各组成部门之间的利害冲突，求出使所研究问题达到最佳效果的解，并寻找一个最好的行动方案付诸实施。
2．多学科的交叉和综合
运筹学研究和解决问题的优势是应用各学科交叉的方法，具有综合性，运筹学从一开始就是由不同学科专长、多方面专家经过共同协作集体努力而获得成功的。现在，由于研究对象的复杂性和多因素性，决定了运筹学内容的跨学科性、交叉渗透性和综合性。
3． 模型方法的应用
在各门学科的研究中广泛应用实验的方法，但运筹学研究的系统往往不能搬到实验室来，代替的方法是建立这个问题的数学和模拟的模型。应当指出，制定决策是运筹学应用的核心，而建立模型则是运筹学方法的精髓。学习运筹学要掌握的最重要技巧就是提高对运筹学数学模型的表达、运算和分析的能力。
4．具有连续性
运筹学研究和解决问题的效果具有连续性。一方面，用运筹学方法获得的解或最优方案，不可能在同一时间内将所有相关的问题都全部解决；另一方面，一旦发现有新的情况或问题时，必须对原有模型进行修正或者需要输入新的数据，以调整原来的解或方案。因此，只有通过连续研究才能获得新的更好的效果。
5．着重实际应用
在运筹学学术界，有许多人强调运筹学 的实用性和对研究结果的“执行”，把“执行”看作运筹工作中的一个重要组成部分，有的运筹学教科书中，在讲述从理论上求得最优解之后，还要讲述根据实际情况对所得解进行进一步的考察，讲述对所得最优解如何进行灵敏度分析等。
6．电子计算机是不可缺少的工具
近50年来，随着电子计算机的发展，使许多运筹学方法得以实现和发展，没有电子计算机，运筹学只是一种理论科学，不会像今天这样成为广泛应用、不断发展的应用学科。在解决实际问题时，应用计算机既可避免在利用模型进行求解时大量重复计算的劳动，又可利用它对某些实际问题进行仿真模拟，达到解决问题的目的，因此，电子计算机是运筹学研究不可缺少的工具。
§3 运筹学的主要内容
运筹学发展到现在虽然只有六十年左右的历史，但是内容丰富，涉及面广，应用范围大，已形成了一个相当庞大的学科。
运筹学按所解决问题性质的差别，将实际的问题归结为不同类型的数学模型。这些不同类型的数学模型构成了运筹学的各个分支。它的主要内容一般应包含以下几个方面。
一、线性规划 (Linear Programming)
线性规划是运筹学的最主要分支之一。
线性规划是研究在线性不等式或等式的约束条件下，使得某一个线性目标取得最大（或最小）的问题。由于线性规划模型比较简单，理论与计算方法比较成熟，因而，线性规划在交通、工业、农业、军事、经济、管理等方面有很多成功应用的实例。
线性规划建模相对简单，有通用算法和计算机软件，是运筹学中应用最为广泛的一个分支。用线性规划求解的典型问题有运输问题、生产计划问题、下料问题、混合配料问题等。有些规划问题的目标函数是非线性的，但往往可以采用分段线性化等手法，转化为线性规划问题。
二、整数规划 (Integer Programming)
由于在实际问题中某些变量的取值只能为整数（例如，机器的台数，完成工作的人数等），因此，在线性规划的模型中有一部分或全部变量要求是整数，这就构成了（线性）整数规划问题。在整数规划的解法当中，最具有代表性的是割平面法和分支定界法。这两类方法的共同特点是把一个整数规划问题的求解，转化为多次线性规划的求解。
三、非线性规划 (Nonlinear Programming)
如果线性规划模型中目标函数或约束条件不全是线性的，我们就称这类问题为非线性规划问题。
非线性规划的发展是与寇恩-塔凯尔（,）于1951年发表的非线性规划基本定理分不开的。
由于大多数工程物理量的表达式是非线性的，因此非线性规划在各类工程的优化设计中得到较多应用，是优化设计的有力工具。
四、动态规划 (Dynamic Programming)
动态规划是贝尔曼()等人在1951年，根据一类多阶段决策问题的特性，提出了解决这类问题的著名的“最优化原理”，随后又应用这一原理解决了很多实际问题，从而创建了解决多阶段决策问题的一种新方法——动态规划。
有些经营管理活动由一系列相互关连的阶段组成，在每个阶段依次进行决策，而且上一阶段的输出状态就是下一阶段的输入状态，各阶段决策之间互相关连，因而构成一个多阶段的决策过程。
动态规划研究多阶段决策过程的总体优化，即从系统总体出发，要求各阶段决策所构成的决策序列使目标函数值达到最优。
动态规划在工程技术、经济、管理、军事等有关部门都有着广泛的应用。
五、多目标规划 (Multiobjective Programming)
由于客观情况比较复杂，有时判断一个方案的优劣难以用一个目标来权衡，即需用一个以上的目标来衡量，而这些目标之间又往往不是那么协调（甚至是彼此完全对立的）。多目标规划是研究具有多个目标的规划问题的理论与方法的一个新分支。多目标规划应用广泛，近十年这一分支的研究十分活跃。
六、图与网络分析
(Graph Theory and Network Analysis)
生产管理中经常碰到工序间的合理衔接搭配问题，设计中经常碰到研究各种管道、线路的通过能力，以及仓库、附属设施的布局等问题。运筹学中把一些研究的对象用节点表示，对象之间的联系用连线（边）表示，用点、边的集合构成图。
网络分析主要是研究解决生产组织、计划管理中诸如最短路径问题、最小连接问题、最小费用流问题、以及最优分派问题等。
网络分析还包括利用网络图形来描述一项工程中各项作业的进度和结构关系，以便对工程进度进行优化控制。
图是网络分析的基础，根据研究的具体网络对象（如铁路网、电力网、通信网等），赋予图中各边某个具体的参数，如时间、流量、费用、距离等，规定图中各节点代表具体网络中任何一种流动的起点、中转点或终点，然后利用图论方法来研究各类网络结构和流量的优化分析。
七、存贮论 (Inventory Theory)
人们在生产和消费过程中，都必须储备一定数量的原材料、半成品或商品。存储少了会因停工待料或失去销售机会而遭受损失，存储多了又会造成资金积压、原材料及商品的损耗。因此，如何确定合理的存储量、购货批量和购货周期至关重要，这便是存储论要解决的问题。
存贮论是研究在各种不同情况下的库存问题，形成数学模型，选择合理的存贮策略，以使相应问题中考虑的各项费用的总和为最小。
存贮策略是研究在不同需求、供货及到达方式等情况下，确定在什么时间点及一次提出多大批量的订货，使用于订购、贮存和可能发生短缺的费用的总和为最少。
八、排队论
(Queuing Theory, or Waiting Line)
排队现象在日常生活中屡见不鲜，如机器等待修理，船舶等待装卸，顾客等待服务等．它们有一个共同的问题，就是等待时间长了，会影响生产任务的完成，或者顾客会自动离去而影响经济效益；如果增加修理工、装卸码头和服务台，固然能解决等待时间过长的问题，但又会蒙受修理工、码头和服务台空闲的损失．这类问题的妥善解决是排队论的任务。
排队论的开创性工作是1915年丹麦数学家埃尔朗()在研究自动电话系统中通话线路与电话用户呼叫的数量关系问题时，建立了呼叫生灭模型，推导出了后来被人们命名的埃尔朗公式，它极为成功地解决了这一问题。
排队论有时也被称为随机服务系统，它是研究在顾客不同输入、各类服务时间的分布、不同服务员数及不同排队规则情况下，排队系统的工作性能和状态，为设计新的排队系统及改进现有系统的性能提供数量依据。
排队论在城市管理、计算机研制、卫星通讯、水库调度、生产管理等方面都得到了广泛应用。
九、对策论 (Game Theory)
1928年冯·诺意曼( Neumann)等人由于经济问题的启发，研究了一类具有某种特性的博弈问题，这是对策论的最早期的工作。
对策论用于研究具有对抗局势的模型。在这类模型中，参与对抗的各方称为局中人，对策论是为局中人在这种高度不确定和充满竞争的环境中．提供一套完整的、定量化和程序化的选择策略的理论和方法。
战国时代“齐王与田忌赛马”的故事便是对策论的一个绝妙的例子。
对策论已应用于商品、消费者、生产者之间的供求平衡分析、利益集团间的协商和谈判，以及军事上各种作战模型的研究等。由于它处理问题的方法有着明显的特色，所以越来越受到人们的注意。
十、决策论 (Decision Theory)
决策问题是普遍存在的，凡属“举棋不定”的事情都必须做出决策。人们之所以举棋不定，是因为人们在着手实现某个预期目标时，面前出现了多种情况，又有多种行动方案可供选择。决策者如何从中选择一个最优方案，才能达到他的预期目标，这是决策论的研究任务。
决策过程一般是指：形成决策问题，包括提出方案，确定目标及效果的度量；确定各方案对应的结局及出现的概率；确定决策者对不同结局的效用值；综合评价，决定方案的取舍。
决策论是对整个决策过程中涉及方案目标选取、度量、概率值确定、效用值计算，一直到最优方案和策略选取的有关科学理论。
十一、其它 (Others)
运筹学的研究领域和应用领域在不断的扩大，而且运筹学与其它有关学科（例如，系统工程，系统分析，管理学等）有其相同之处，因此，运筹学应包括哪些分支并不是很严格的。现将国内、外一些文献中出现的与运筹学有关的内容罗列如下：
模拟；
可靠性；
质量控制；
模型论；
可行性研究；
统筹方法；
投入产出分析。
§4 运筹学研究的基本方法
一、运筹学模型
模型通常是指为特定目的建立的，反映某种客观存在的特征和特性的一种结构。运筹学研究的模型主要为抽象模型——数学模型。数学模型的基本特点是用一些数学关系（数学方程、逻辑关系等）来描述被研究对象的实际关系（技术关系、物理关系、外部关系）。
二、运筹学分析的主要步骤
任何一门学科从研究范畴上都大致可分为以下四个方面：
1、观察现象并从中提出问题；
2、对于问题进行理论或模型的建立；
3、将理论与观察相结合，并从结果得到预测：
4、将这些预测同新的观察相比较，并加以证实。
运筹学也不例外，围绕着模型的建立、修正与实施，对上述四个方面的研究可划分为以下六个步骤：
1、分析和表述问题
任何决策问题进行定量分析前，先必须认真地进行定性分析。
一是要确定决策目标，明确主要应决策什么，选取上述决策时的有效性度量，以及在对方案比较时这些度量的权衡；
二是要辨认哪些是决策中的关键因素，在选取这些关键因素时存在哪些资源或环境的限制。
三是要同有关人员进一步讨论，明确有关研究问题的过去与未来，问题的边界、环境以及包含这个问题在内的更大系统的有关情况，以便在对问题的表述中明确，要不要把整个问题分成若干较小的子问题。
在上述分析基础上，可以列出表述问题的
各种基本要素，包括哪些是可控的决策变
量，哪些是不可控的变量，确定限制变量
取值的各种工艺技术条件，以及确定优化
和对方案改进的目标。
2、建立模型
运筹学研究和解决问题的核心是正确建立和使用模型。
1）模型的概念
模型是对现实世界的事物、现象、过程和系统的简化描述，或其部分属性的模仿，是对实际问题的抽象概括和严格的逻辑表达。
模型表达了问题中可控的决策变量、不可控变量、工艺技术条件及目标有效度量之间的相互关系。从而能够更简明的揭示出问题的本质。
2）模型的功能
一是使问题的描述高度规范化，掌握其本质规律。如在管理中，对人力、设备、材料、资金的利用安排都可以归纳为所谓资源的分配利用问题，可建立起一个统一的规划模型，而对规划模型的研究代替了对一个个具体问题的分析研究。
二是建立模型后，可以通过输入各种数据资料，分析各种因素同系统整体目标之间的因果关系，从而确立一套逻辑的分析问题的程序方法。
三是通过模型可以进行试验，用以分析和预测所研究事物或系统的特征及性质，尤其在研究工业系统、军事系统、政府或社会系统的最优管理或运行的问题时十分必要，因为这样可以避免由于真实对象的干扰而导致不测的风险。
四是利用模型可以根据过去和现在的信息进行预测，并可用来培训教育人才。
五是利用模型可以在相对短的时间内获得所研究问题的结果。特别对一个复杂问题的研究，利用模型，使研究者不必真的实现计划即可改变其参数，从而不必等待一段较长的时间就可以得到问题的答案。
3）模型的基本形式
模型有三种基本形式：形象模型、模拟模型及符号或数学模型，目前用得最多的是符号或数学模型。数学模型是将现实系统或问题中的有关参数的因素及其相互关系归纳成一个或一组数学表达式，并可以用一定的分析和计算方法进行求 解，以实现反映现实系统变化规律的主要目标。
4）模型的建立
一般建模时应尽可能选择建立数学模型。但有时问题中的各种关系难于用数学语言描绘，或问题中包含的随机因素较多，也可以建立起一个模拟的模型，即将问题的因素、目标及运行时的关系用逻辑框图的形式表示出来。
尽量建立系统的模型。建立模型时既要尽可能包含系统的各种信息资料，又要抓住本质的因素。
模型的正确建立是运筹学研究中的关键一步，对模型的研制是一项艺术，它是将实际问题、经验、科学方法三者有机结合的创造性的工作。
3、求解模型和优化方案
即用数学方法或其它工具对模型求解，例如经典法、迭代法或模拟法等。根据问题的要求，可分别求出最优解、次最优解或满意解；依据对解的精度的要求及算法上实现的可能性，又可区分为精确解和近似解等。
4、检验并评价模型。
回溯的方法。即将历史的资料输入模型，研究得到的解与历史实际的符合程度。以判断模型是否正确。当发现有较大误差时，要将实际问题同模型重新对比，检查实际问题中的重要因素在模型中是否已考虑，检查模型中各公式的表达是否前后一致。
当输入发生微小变化时，检验输出变化的相对大小是否合适。
当模型中各参数取极值时，检验问题的解，还要检查模型是否容易求解，并在规定时间内算出所需的结果等等，以便发现问题，进行修正。
灵敏度分析法、参数规划法、相关分析法等，都是对模型结构和一些基本参数进行评价，以检验它们是否准确无误。
5、建立对解的有效控制
任何模型都有一定的适用范围，模型的解是否有效，首先要注意模型是否继续有效。并依据灵敏度分析的方法，确定最优解保持稳定时的参数变化范围。一旦外界条件参数变比超出这个范围时，及时对模型和导出的解进行修正。
6、方案的实施
方案实施是很关键的一步，但也是很困难的一步。只有实施方案后，研究成果才能有收获。这一步要求明确：方案由谁实施，什么时间实施，如何实施，要求估计实施过程可能遇到的阻力，并为此制订相应的克服困难的措施。
应当说明，以上虽然将运筹学解决问题的过程划分为六个独立的阶段，但在实际应用中，很少能够将它们截然分开并加以区分，各个阶段之间经常是相互影响和彼此重迭，有时要经过多次反复。
最后需要指出，随着运筹学应用逐渐向
复杂的系统和社会系统渗透，而这些系
统又往往存在着大量的不确定因素。因
此，运筹学仅仅依靠数学模型作定量分
析已很难处理好系统的优化问题。难怪
其研究方法已开始出现将定量分析、定
性分析及计算机模拟等相结合的综合优
化分析方法的发展趋势。
§5 运筹学的广泛应用及发展趋势
一、运筹学的广泛应用
近几十年来，运筹学模型已广泛应用于许多领域，深入到国民经济的多个方面，诸如生产计划管理、市场预测与分析、资源分配与管理、工程优化设计、运输调度管理、库存管理、企业管理、区域规划与城市管理、计算机与管理信息系统等。
运筹学方法使用情况(美1983)（%）
*
运筹学方法在中国使用情况(随机抽样)（%）
§6 学习运筹学的重要性
今日，运筹学不仅在理学、工学（称为工程数学）领域，在人文、社会科学领域亦得到广泛运用。尤其是经济学、社会学、管理学、政治学（如选举、民意测验、政治体制等的数学分析）、法学（如法经济学，即用经济学的定量分析方法研究法学问题）等。
从管理学看，管理经济学、生产与运作管理、财务管理等的基本工具就是运筹学。
社会工学，即运用运筹学的思想和分析工具，分析研究诸多社会问题。如都市规划问题，儿童教育问题等等。
第一章 线性规划
§ 线性规划的概念和模型
线性规划问题的导出
线性规划概念和模型
线性规划的标准型
线性规划的标准化
线性规划问题的导出
例1、生产计划问题
A, B各生产多少, 可获最大利润?
. x1 + 2x2 30
3x1 + 2x2 60
2x2 24
x1，x2 0
max Z= 40x1 +50x2
解:设产品A, B产量分别为变量x1 ， x2
例2 营养配餐
求：最低成本的原料混合方案
解：设每单位添加剂中原料i的用量为xi(i =1,2,3,4)
minZ= 2x1 + 5x2 +6x3+8x4
. 4x1 + 6x2 + x3+2x4 12
x1 + x2 +7x3+5x4 14
2x2 + x3+3x4 8
xi 0 (i =1,…,4)
线性规划概念
定义：
对于求取一组变量xj(j=1,2,…..,n)，使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。
线性规划模型的特点
决策变量：向量(x1… xn)T 决策人要考虑和控制的因素非负
约束条件：线性等式或不等式
目标函数：Z=ƒ(x1 … xn) 线性式，求Z极大或极小
*
一般式
Max(min)Z=C1X1+ C2X2+…+CnXn
*
隐含的假定
比例性：决策变量变化引起目标的改变量与决策变量改变量成正比
可加性：每个决策变量对目标和约束的影响独立于其它变量
连续性：每个决策变量取连续值
确定性：线性规划中的参数aij , bi , ci为确定值
(1)设立决策变量；
(2)明确约束条件并用决策变量的线性等式或不等式表示；
(3)用决策变量的线性函数表示目标，并确定是求极大（Max）还是极小（Min）；
(4)根据决策变量的物理性质研究变量是否有非负性。
★ 实际问题化为线性规化
问题的方法
人力资源分配的问题
某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：
设司机和乘务人员分别在各时间段一开始时上班，并连续工作8h，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?
解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。
目标函数：Min x1 + x2 + x3 + x4 + x5 + x6
约束条件：. x1 + x6 ≥ 60
x1 + x2 ≥ 70
x2 + x3 ≥ 60
x3 + x4 ≥ 50
x4 + x5 ≥ 20
x5 + x6 ≥ 30
x1,x2,x3,x4,x5,x6 ≥ 0
套裁下料问题
某工厂要做100套钢架，每套用长为 m, , 的圆钢各一根。已知原料每根长 m，问：应如何下料，可使所用原料最省？
解:考虑下列各种下料方案（按一种逻辑顺序给出）
把各种下料方案按剩余料头从小到大顺序列出
假设 x1,x2,x3,x4,x5 分别为上面前 5 种方案下料的原材料根数。我们建立如下的数学模型。
目标函数：
Min x1 + x2 + x3 + x4 + x5
约束条件：
. x1 + 2x2 + x4 ≥ 100
2x3 + 2x4 + x5 ≥ 100
3x1 + x2 + 2x3+ 3x5 ≥ 100
x1,x2,x3,x4,x5 ≥ 0
明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配 三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？
生产计划的问题
解：设 x1 ,x2 ,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4, x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。
求 xi 的利润:利润 = 售价 - 各成本之和可得到 xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。
这样我们建立如下数学模型：
目标函数: Max 15x1+10x2+7x3+13x4+9x5
约束条件：
. 5x1+10x2+7x3 ≤ 8000
6x1+4x2+8x3+6x4+4x5 ≤12000
3x1+2x2+2x3+3x4+2x5 ≤ 10000
x1,x2,x3,x4,x5 ≥ 0
永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过 A、B 两道工序加工。假设有两种规格的设备A1、A2能完成 A 工序；有三种规格的设备B1、 B2 、B3能完成 B 工序。Ⅰ可在 A、B 的任何规格的设备上加工；Ⅱ 可在任意规格的A设备上加工，但对B工序,只能在B1设备上加工；Ⅲ 只能在A2与B2设备上加工；数据如下表。问：为使该厂获得最大利润，应如何制定产品加工方案？
解：设 xijk 表示第 i 种产品，在第 j 种工序上的第 k 种设备上加工的数量. 利润 = [（销售单价 - 原料单价）× 产品件数]之和 - （每台时的设备费用×设备实际使用的总台时数）之和。
这样我们建立如下的数学模型:
Max ++++
.
5x111+10x211≤6000 （ 设备 A1 ）
7x112+9x212+12x312≤10000（ 设备 A2 ）
6x121+ 8x221≤ 4000 ( 设备 B1 ）
4x122+11x322≤700 ( 设备 B2 ）
7x123 ≤ 4000 （ 设备 B3 ）
x111+ x112- x121- x122- x123 = 0
(Ⅰ产品在A、B工序加工的数量相等）
x211+ x212- x221 = 0
(Ⅱ产品在A、B工序加工的数量相等）
x312 - x322 = 0
(Ⅲ产品在A、B工序加工的数量相等）
xijk≥0, i=1,2,3; j=1,2; k=1,2,3
某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？
配料问题
解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑：
对于甲： x11，x12，x13；
对于乙： x21，x22，x23；
对于丙： x31，x32，x33；
对于原料1： x11，x21，x31；
对于原料2： x12，x22，x32；
对于原料3： x13，x23，x33；
目标函数：
利润最大，利润 = 收入 - 原料支出
约束条件：规格要求 4 个；
供应量限制 3 个。
Max
z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33
. x11- x12 - x13 ≥ 0
（原材料1不少于50%）
-x11+3x12 -x13 ≤ 0
（原材料2不超过25%）
3x21-x22 -x23 ≥ 0
（原材料1不少于25%）
-x21+x22-x23 ≤ 0
（原材料2不超过50%）
x11+x21+x31≤ 100 (供应量限制）
x12+x22+x32≤ 100 (供应量限制）
x13+x23+x33≤ 60 (供应量限制）
xij≥0 ,i = 1,2,3; j = 1,2,3
投资问题
某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：
1、项目A ：从第一年到第五年每年年初都可投资，当年末能收回本利110%；
2、项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；
3、项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；
4、项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。
据测定每万元每次投资的风险指数如下表：
a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？
b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？
问：
*
解：1）确定决策变量：连续投资问题
设 xij ( i = 1—5，j = 1、2、3、4)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下决策变量：
A x11 x21 x31 x41 x51
B x12 x22 x32 x42
C x33
D x24
*
2）约束条件：
第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是：
x11+ x12 = 200
第二年：B 次年末才可收回投资故第二年年初的资金为，于是：
x21 + x22+ x24 =
第三年：年初的资金为+，于是 ：
x31 + x32+ x33 = +
第四年：年初的资金为+，于是：
x41 + x42 = +
第五年：年初的资金为+，于是：
x51 = +
B、C、D的投资限制：
xi2 ≤ 30 ( i=1，2，3，4 )，
x33 ≤ 80，x24 ≤ 100
a)
Max z=+++
+ x12 = 200
x21 + x22+ x24 =
x31 + x32+ x33 = +
x41 + x42 = +
x51 = +
xi2 ≤ 30 ( i =1、2、3、4 )，
x33 ≤ 80，x24 ≤ 100
xij≥0(i=1,2,3,4,5；j=1,2,3,4）
3）目标函数及模型：
b)
Min f = （x11+x21+x31+x41+x51)+ 3(x12+x22+x32+x42)+4x33+
. x11+ x12 ≤ 200
x21 + x22+ x24 ≤
x31 + x32+ x33 ≤ +
x41 + x42 ≤ +
x51 ≤ +
xi2 ≤ 30 ( i =1、2、3、4 )，
x33 ≤ 80，x24 ≤ 100
+ + + ≥ 330
xij≥0(i=1,2,3,4,5；j = 1,2,3,4）
运输问题
设xij为i 仓库运到 j工厂的产品数量(i ＝1，2，3， j ＝1，2，3)
Min Z= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33
.
练习：连续投资10万元，现有如下4种投资途经
A：从第1年 到第4年每年初要投资，次年末回收本利
B：第3年初投资，到第5年末回收，最大投资4万元
C：第2年初投资，到第5年末回收，最大投资3万元
D：每年初投资，每年末回收。
求最优投资方案，使得5年末总资本最大
[分析] 首先确定决策变量
其中 Xik( i =1,2,…,5; k =A,B,C,D)为第i年初投k项目的资金数
Max Z= + x2C++
在企业管理的具体应用
市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)
生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”)
库存管理(合理物资库存量，停车场大小，设备容量)
运输问题
财政、会计(预算，贷款，成本分析，投资，证券管理)
人事(人员分配，人才评价，工资和奖金的确定)
设备管理(维修计划，设备更新)
城市管理(供水，污水管理，服务系统设计、运用)
见“线性规划建模习题.doc”
案例练习
要解决的问题的目标可以用数值指标反映
对于要实现的目标有多种方案可选择
有影响决策的若干约束条件
线性规划模型的要求
§ 线性规划的标准型
(一)、标准型
其中 bi 0 (i=1,2,…,m)
(四)、一般形式转化为标准型
(1)、约束条件
(2)、变量
(3)、目标函数
(1)、约束条件
例1 Max Z=40X1+ 50X2
引入松弛变量
例1 max Z=40X1+ 50X2+0·X3 +0·X4+0·X5
例2 Min Z=2X1+ 5X2+6X3 +8X4
引入剩余变量
(2)、自由变量的处理
1、
令X1= X1'- X1 "
2、
-6+6 X1+6 10+6
令X1' = X1 +6
0 X1' 16
(3)、目标函数的处理
例：将 Min Z = -X1+2X2 -3X3
化为标准型
解：① 令X3 =X4 - X5
② 加松弛变量X6
③ 加剩余变量X7
④ 令Z'= -Z
Max Z'= X1 -2X2 +3X4 -3X5
将 Min Z = -X1+2X2 -3X3
X1+X2 +X3 7
X1 -X2 +X3 2
-4<X2<-1
X10
化为标准型
练习
§ 图解法
定义1：满足约束(1)、(2)的X=(X1 … Xn)T称为LP问题的可行解，全部可行解的集合称为可行域。
定义2：满足(3)的可行解称为LP问题的最优解。
线性规划的图解法(解的几何表示)对于只有两个变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。图解法求解线性规划问题的步骤如下：
(1)分别取决策变量x1 ,x2 为坐标向量建立直角坐标系。
*
（2）对每个约束（包括非负约束）条件，先取其等式在坐标系中作出直线，通过判断确定不等式所决定的半平面。各约束半平面交出来的区域(存在或不存在），若存在，其中的点表示的解称为此线性规划的可行解。这些符合约束限制的点集合，称为可行集或可行域。然后进行（3）。否则该线性规划问题无可行解。
*
（3）任意给定目标函数一个值作一条目标函数的等值线，并确定该等值线平移后值增加的方向，平移此目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置(有时交于无穷远处，此时称无有限最优解）。若有交点时，此目标函数等值线与可行域的交点即最优解（一个或多个），此目标函数的值即最优值。
*
图解法举例
例1、家具厂生产计划问题
A, B各生产多少, 可获最大利润?
建立模型
先确定决策变量，设A，B分别生产X1 ，X2
Max Z=40X1+ 50X2
.
解：(1)、确定可行域
X1 0 X1 =0 (横)
X2 0 X2=0 (纵)
X1+2X2 30
X1+2X2 =30
(0,15) (30,0)
3X1+2X2 =60
(0,30) (20,0)
2X2 =24
X1
(2)、求最优解
解：X* = (15,)
Zmax =975
C
几何概念
代数概念
约束直线
满足一个等式约束的解
约束半平面
满足一个不等式约束的解
约束半平面的交集：凸多边形
满足一组不等式约束的解
约束直线的交点
基本解
可行域的极点
基本可行解
目标函数等值线：一组平行线
目标函数值等于一个常数的解
Max Z=40X1+ 80X2
1.用图解法求解下面线性规划模型
见文件“2.线性规划解法练习.doc”
0
X(1)=(6,12)
X(2)=(15,)
X= X(1)+(1-) X(2)
(0 1)
求解
最优解：BC线段
B点 C点
无穷多解
无界
无有限最优解
X1
无解
无可行解
0
图解法总结
§ 单纯形法
引例
0
(0,0)
X2
X1
图解法表示
利用求解线性规划问题基本可行解（极点）的方法来求解较大规模的问题是不可行的。单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。
由上节的讨论可知，对于线性规划的一个基，当非基变量确定以后，基变量和目标函数的值也随之确定。因此，一个基本可行解向另一个基本可行解的移动，以及移动时基变量和目标函数值的变化，可以分别由基变量和目标函数用非基变量的表达式来表示。同时，当可行解从可行域的一个极点沿着可行域的边界移动到一个相邻的极点的过程中，所有非基变量中只有一个变量的值从0开始增加，而其他非基变量的值都保持0不变。
初始基本可行解
是否最优解或
无限最优解?
结束
沿边界找新
的基本可行解
N
Y
单纯形法的基本过程
单纯形法的基本步骤可描述如下：
（1）寻找一个初始的可行基和相应基本可行解（极点），确定基变量、非基变量以及基变量、非基变量（全部等于0）和目标函数的值，并将目标函数和基变量分别用非基变量表示；
（2）在用非基变量表示的目标函数表达式（2-12）中，我们称非基变量xj的系数（或其负值）为检验数记为 j 。若 j > 0，那么相应的非基变量xj，它的值从当前值0开始增加时，目标函数值随之增加。这个选定的非基变量xj称为“进基变量”，转（3）。如果任何一个非基变量的值增加都不能使目标函数值增加，即所有 j 非正，则当前的基本可行解就是最优解，计算结束；
（3）在用非基变量表示的基变量的表达式（2-11）中，观察进基变量增加时各基变量变化情况，确定基变量的值在进基变量增加过程中首先减少到0的变量xr ，满足，
=minb’i /a’ij a’ij > 0 = b’r /a’rj
这个基变量xr称为“出基变量”。当进基变量的值增加到 时，出基变量xr的值降为0时，可行解就移动到了相邻的基本可行解（极点），转（4）。
如果进基变量的值增加时，所有基变量的值都不减少，即所有a’ij 非正，则表示可行域是不封闭的，且目标函数值随进基变量的增加可以无限增加，此时，不存在有限最优解，计算结束；
（4）将进基变量作为新的基变量，出基变量作为新的非基变量，确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重复（1）。
当LP的数学模型为一般型时
*
单纯形法基本步骤
(1)、选定初始基，初始基本可行解
(3)、若有k >0，Pk全 0，停，
没有有限最优解； 否则转(4)
(2)、对应于非基变量检验数j 全 0。
若是，停，得到最优解；
若否，转(3)。
*
定Xr为出基变量，ar,m+k为主元。
由最小θ比值法求：
转(2)
(5)、以ar,m+k为中心，换基迭代
max Z = CX……(1)
: AX=b……(2)
X≥0……(3)
用B-1乘以(2)两边得: B-1AX=B-1b……(4)
用CB乘以(4)两边得: CB B-1AX= CB B-1b……(5)
(1)+(5)得: Z = ( C -CB B-1A) X+CB B-1b……(6)
(4)与(6)的系数组成的表格叫单纯形表:
单纯形表
B-1b B-1A
CBB-1b C-CBB-1A
单纯形表
C c1,c2,…,cn
CB XB B-1b x1,x2,…,xn
CB XB B-1b B-1A
λj CBB-1b C-CBB-1A
将基变量移到前面的单纯形表
C CB , CN
CB XB B-1b XB , XN θ
I , B-1N
λj Z 值 0 ,CN-CBB-1N
检验数→“盲人爬山的棍”
检验数λ＝C-CBB-1A
检验数λj＝Cj-CBB-1Pj , j=1,2,…,n
检验数的意义:
1.目标求max Z时, 当C-CBB-1A ≤0, Z=CBB-1b最大.
2.目标求min Z时, 当C-CBB-1A ≥ 0, Z=CBB-1b最小.
案例 生产计划问题
胜利家具厂生产桌子和椅子两种家具。桌子售价50元／个，椅子售价30元／个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？
决策变量：
X1=生产桌子数量; X2=生产椅子数量.
2. 目标函数是什么?
Z=每月的销售收入,
则Max Z=50 X1 +30 X2
3. 满足什么?约束条件是什么?
木工工时为120小时: 4X1+3X2≤120
油漆工工时为50小时: 2X1+1X2 ≤50
生产数量: X1≥0; X2 ≥0
模型为:求X1 ,X2
Max Z=50 X1 +30 X2
.: 4X1+3X2≤120
2X1+1X2 ≤50
X1≥0; X2 ≥0
一般型
max Z =50X1+30X2
: 4X1+3X2 ≤120
2X1+X2 ≤50
X1 ≥0 , X2 ≥0
化为标准型:
max Z =50X1+30X2
: 4X1+3X2+X3 =120
2X1+X2 +X4 =50
Xj ≥0 , j=1,2,3,4
C 50 30 0 0 比值
CB XB B-1b X1 X2 X3 X4
0
0 X3
X4 120
50 4 3 1 0
(2) 1 0 1 120/4=30
50/2=25
λj 0 50 30 0 0
C 50 30 0 0 比值
CB XB B-1b X1 X2 X3 X4
0
0 X3
X4 120
50 4 3 1 0
2 1 0 1 120/4=30
50/2=25
λj 0 50 30 0 0
0
50 X3
X1 20
25 0 1 1 -2
1 ½ 0 1/2 20/1=20
25/1/2=50
λj 1250 0 5 0 -25
∵λj≤0 , ∴得最优解：X1=15 , X2=20 .最优值：Max Z=1350 .
C 50 30 0 0 比值
CB XB B-1b X1 X2 X3 X4
0
0 X3
X4 120
50 4 3 1 0
2 1 0 1 120/4=30
50/2=25
λj 0 50 30 0 0
0
50 X3
X1 20
25 0 1 1 -2
1 ½ 0 1/2 20/1=20
25/1/2=50
λj 1250 0 5 0 -25
30
50 X2
X1 20
15 0 1 1 -2
1 0 -1/2 3/2
λj 1350 0 0 -5 -15
∵λj≤0 , ∴得最优解：X1=15 , X2=20 .最优值：MaxZ=1350 .
C 50 30 0 0 比值
CB XB B-1b X1 X2 X3 X4
0
0 X3
X4 120
50 4 3 1 0
2 1 0 1 120/4=30
50/2=25
λj 0 50 30 0 0
0
50 X3
X1 20
25 0 1 1 -2
1 ½ 0 1/2 20/1=20
25/1/2=50
λj 1250 0 5 0 -25
30
50 X2
X1 20
15 0 1 1 -2
1 0 -1/2 3/2
λj 1350 0 0 -5 -15
0 0 … 0
单纯形表的重要特征
(1) 基变量的目标行系数均为 0 ；
(2) 非基变量的目标行系数可用以检验现行解的优化性；
(3) 基变量的列向量必然是单位矩阵中的某一个列向量；
(4) 表中的目标方程和约束方程都是由非基变量构成的。
*
单纯形法的几点补充说明：
(1)、例1 max Z=X1 +2X2
表 1
表 2
(接下表)
表 3
表 4
该线性规划问题有无穷多解！
10 12 0 0 0
XB B-1b X1 X2 X3 X4 X5 θi
X3 6 3 (4) 1 0 0 3/2
X4 2 4 1 0 1 0 2/1
X5 3 3 2 0 0 1 3/2
λj 0 10 12 0 0 0
表 1
X1 X2 X3 X4 X5
XB B-1b 10 12 0 0 0 θi
X2 3/2 3/4 1 1/4 0 0 2
X4 1/2 13/4 0 -1/4 1 0 2/13
X5 0 (3/2) 0 -1/2 0 1 0
λj 18 1 0 -3 0 0
表 2
X1 X2 X3 X4 X5
XB B-1b 10 12 0 0 0 θi
X2 3/2 0 1 1/2 0 -1/2
X4 1/2 0 0 5/6 1 -13/6
X1 0 1 0 -1/3 0 2/3
λj 18 0 0 -8/3 0 -2/3 θi
表 3
退化解：在使用单纯形表确定出基变量时，如果有两个以上的基变量具有相同的最小比值θ，那么在下一个单纯形表中会出现一个或几个基变量取值为零、而目标值不变的情形，这样得到的新解被称为退化解。
原因：模型的构造不合理，其中包含了至少一个以上的冗余约束条件。
X *=(0, 3/2, 0, 1/2, 0)T
Zmax=18
*
换基迭代
(P1 P2 P3) (P4 P2 P3) (P4 P5 P3) (P6 P5 P3) (P6 P7 P3) (P1 P7 P3) (P1 P2 P3)
例3：
λj
表 1
λj
λj
目标函数值有无变化？是否有最优解？
表 2
没有最优解，本问题无界。
对偶问题
对偶理论
互补松弛定理
灵敏度分析
第二章 对偶规划
对偶问题的提出?
胜利家具厂生产桌子和椅子两种家具。桌子售价50元／个，椅子售价30元／个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？
如出卖资源收入多少?
利用资源的生产计划。
家具厂管理者的目标追求销售收入最大。
例题：胜利家具厂生产问题的求解
模型为: 求X1 ,X2 Max Z=50 X1 +30 X2
: 4X1+3X2≤120
2X1+1X2 ≤50
X1≥0; X2 ≥0
2. 家具厂不生产，出卖资源。
对于一个企业家，有意租用家具厂的资源。
他的目标是什么？
对偶问题的提出?
模型为: 求Y1,Y2 (Y1=木工单价;Y2=油漆工单价)
min W=120Y1+50Y2
: 4Y1+2Y2 ≥50
3Y1+1Y2 ≥30
Y 1≥ 0; Y2 ≥0
企业家的目标追求所付的租金最少！
对偶问题
Min W=120Y1+50Y2
: 4Y1+2Y2 ≥50
3Y1+1Y2 ≥30
Y 1≥ 0; Y2 ≥0
原问题
Max Z=50 X1 +30 X2
: 4X1+3X2≤120
2X1+1X2 ≤50
X1≥0; X2 ≥0
对偶问题的定义
对称形式的对偶问题
对偶问题的定义（矩阵）
对称形式的对偶问题
对偶问题的定义
对偶问题的特点
若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然
原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵
极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。
一般线性规划问题的对偶问题
对偶问题 (D)
原问题(P)
对偶问题对应表
原问题（对偶问题） 对偶问题（原问题）
目标函数maxZ 目标函数minZ
约束条件： m个
第i个约束类型为“≤”
第i个约束类型为“≥”
第i个约束类型为“＝” 变量数： m个
第i个变量≥0
第i个变量≤0
第i个变量是自由变量
变量数：n个
第j个变量≥0
第j个变量≤0
第j个变量是自由变量 约束条件：n个
第j个约束类型为“≥”
第j个约束类型为“≤”
第j个约束类型为“＝”
标准型对偶问题
如何将原问题转化为对偶问题?
例: 原问题 max Z =2X1+4X2-3X3
: X1-X2+X3 ≤10
-X1+4X2-3X3= -5
3X1+2X2-5X3≥8
X1≥0, X2≤0
写出对偶问题。
对比
原问题(P)
max Z=2X1+4X2-3X3
: X1-X2+X3 ≤10
-X1+4X2-3X3= -5
3X1+2X2-5X3≥8
X1≥0, X2≤0
对偶问题 (D)
练习、写出如下线性规划问题的对偶问题
对偶问题
Ｐ与Ｄ的标准型
(Ｐ)
(D)
线性规划的对偶理论
1. 对偶问题的对偶就是原问题.
2. 设X与Y分别是(P)与(D)的可行解, 则cX≤Yb.
3. (P)有最优解的充要条件是(D)有最优解.
4. (P)无界,则(D)不可行.
5. (D)无界,则(P)不可行.
∵ AX ≤b, X≥0 ①
∴ YAX≤Yb ②
∵ YA≥C, Y≥0 ③
∴ YAX≥CX ④
可得，CX ≤ YAX ≤ Yb
6. 若X＊,Y＊分别是(P)与(D)的可行解, 则它们分别为(P)与(D)的最优解的充要条件是: CX＊=Y＊b.
则可知：
（P）的对偶解为： Y＝CBB-1
对偶最优解-----CBB-1
Y= (Y1，Y2 )＝ (5，15 )
对偶解的经济意义
经济解释：
由(1)的经济解释可知，yi的大小与系统内资源对目标的贡献有关，是资源的一种估价，称为影子价格。
yi的准确经济意义与建模有关。
案例 某企业生产A,B两种产品.A产品需消耗2个单位的原料和1小时人工; B产品需消耗3个单位的原料和2小时人工. A产品售价23元,B产品售价40元.该企业每天可用于生产的原料为25个单位和15小时人工.每单位原料的采购成本为5元,每小时人工的工资为10元.问该企业如何组织生产才能使销售利润最大.
设A生产X1, B生产X2, Z为销售利润, 则
max Z = 23X1+40X2-5(2X1+3X2)-10(X1+2X2)
max Z = 3X1+5X2
: 2X1+3X2≤25
X1+2X2≤15
Xj≥0, j=1,2.
最优解:X=(5, 5)T, Z=40, 对偶解Y=(1,1).
隐性处理成本.
模型一：不反映成本数据
目标函数如何得出？
模型二 反映成本数据
设A生产X1, B生产X2, 原料的用量为X3, 人工的用量为X4, Z为销售利润, 则
max Z =23X1+40X2-5X3-10X4
: 2X1+3X2=X3
X1+2X2=X4
X3≤25
X4≤15
Xj≥0, j=1,2,3,4
最优解:X=(5,5,25,15)T, Z=40, 对偶解Y=(6,11,1,1).
显性处理成本.
模型一的对偶问题?
. 2y1+y2 3
3y1 +2y25
y1, y2 0
min W = 25y1+15y2
对偶解 Y= (1, 1)
模型二的对偶问题
. 2y1+y2 23
3y1 +2y2 40
- y1 +y3 - 5
- y2 +y4 -10
y1, y2 , y3 , y4 0
min W = 25y3+15y4
对偶解 Y= (6, 11, 1, 1)
情况① 模型中，目标函数系数Ci 表示利润时， yi 不是真正的影子价格，只表示资源bi 增加1单位时，企业目标增加的净利润。
情况② 模型中，目标函数系数Ci 表示成本时， yi 是真正的影子价格。
（3）应用：企业策略
模型一
1.如果某资源的对偶解>0,表示该资源在系统内有获利能力,应买入该资源.
2.如果某资源的对偶解<0,表示该资源在系统内无获利能力,应卖出该资源.
模型二
1.如果某资源的影子价格高于市场价格,表示该资源在系统内有获利能力,应买入该资源.
2.如果某资源的影子价格低于市场价格,表示该资源在系统内无获利能力,应卖出该资源.
对偶最优解的经济含义――影子价格
代表着当第i个右端常数增加一个单位时，最优目标函数值的相应增量。
其含义是在目前已给定的情况下，最优目标值随资源数量变化的变化率；
其经济含义是为约束条件所付出的代价。
当B是原问题的最优基时，Y=CBB-1就是影子价格向量。
影子价格-----CBB-1
１. 是对偶最优解.
２. 是资源的单位改变量引起的
目标函数值的改变量.
３. 是最优价格.
４. 是动态价格.
５. 是边际价格.
检验数λ＝C-CBB-1A解释
1. 数学解释:
Z = CBB-1b+(C-CBB-1A)X
= CBB-1b+(CN-CBB-1N)XN
非基变量的单位改变量引起目标函数Z的改变量.
2. 检验数经济解释:
λj＝ Cj-CBB-1Pj ＝ Cj-YPj
=产品J的价格 - 影子价格×产品J对各种资源的消耗系数
=产品J对目标函数Z的边际贡献.
灵敏度分析
1 ．优化性分析
2 ．可行性分析
3 ．优化性—可行性综合分析
A（原材料消耗系数）代表企业的技术状况；
b（资源供应量）代表企业的资源状况；
C（价值系数）代表企业产品的市场状况；
在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定。
其中A，b，C各代表什么？
为什么要做灵敏度分析？
在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。
更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。
敏感性分析
C(价格系数)变化的分析:
b(资源量)变化的分析: 最优条件B-1b≥0.
同时变化两个以上参数
(1)、参数A，b，C在什么范围内变动，对当前方案无影响？
(2)、参数A，b，C中的一个(几个)变动，对当前方案影响？
应用计算机求解 LP问题
常见的应用软件
Excel规划求解的举例
Excel规划求解的案例
胜利家具厂生产桌子和椅子两种家具。桌子售价50元／个，椅子售价30元／个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？
设决策变量X1 ,X2分别表示生产桌子和椅子的数量，则可建立如下线性规划模型
Max Z=50 X1 +30 X2
: 4X1+3X2≤120
2X1+1X2 ≤50
X1≥0; X2 ≥0
Excel操作步骤
1、工具——加载宏——规划求解
2、建立Excel表
3、工具——规划求解
4、选项卡选择线性模型和假定非负
5、保存方案选择运行结果、敏感性分析、极限值。
Excel案例
Excel输出报告分析
1、运行结果报告
终值为最优值
Excel输出报告分析
2、敏感性报告
递减成本：为检验数，表示决策变量对目标的边际效益
阴影价格：为对偶解，也称影子价格，表示资源（约束右端项）对目标的边际效益。
允许的增量或减量：为保证当前最优方案为最优，假定别的参数不变，一个参数可以变化的量。
家具厂案例最优方案报告
从运行结果报告可知，最优生产计划为桌子15张，椅子20张，此时销售收入最大为1350元，而且木工工时和油漆工工时都已用完。
从敏感性分析报告可知：桌子和椅子对销售收入的边际效应为0。而如果每增加一个油漆工工时，将增加15元的销售收入，每增加一木个工工时，将增加5元的销售收入，
在别的参数不变的情况下，桌子的售价在(50-10,50+10)=(40,60)内变动时，最优生产计划不变。
在别的参数不变的情况下，椅子的售价在(30-5,30+)=(25,)内变动时，最优生产计划不变。
在别的参数不变的情况下，油漆工总工时在(50-10,50+10)=(40,60)内变动时，对偶价格不变。
问：在别的参数不变的情况下，木工总工时的可变化范围。
如果已知桌子的售价为52元，椅子的售价为27元，问当前的最优生产计划桌子15张，椅子20张是否还是最优方案。
100%法则
1、目标函数系数的100％法则
对所有变化的目标函数系数，计算其占允许增加量和允许减少量的百分比之和。如果和没有达到100％，最优解就不会改变。
2、约束条件右端值的100％法则
对所有变化的右端值，计算其占允许增加量和允许减少量的百分比之和。如果和没有达到100％，对偶价格就不会改变。
如果已知桌子的售价为52元，椅子的售价为27元，问当前的最优生产计划桌子15张，椅子20张是否还是最优方案。
解：利用目标函数系数的100％法则,
2/10+3/5=80%
则可知最优方案不变。
如果已知油漆工总工时为53小时，木工总工时为110小时，问当前的油漆工以及木工在系统中的估值是否发生变化，此时对系统资源有什么改善建议？
LINDO（Linear Interactive and Discrete Optimizer）－美国Lindo System Inc.
LINDO是一种专门用于求解数学规划问题的软件包。由于LINDO执行速度快，易于方便地输入、求解和分析数学规划问题，因此在教学、科研和工业界得到广泛应用。
LINDO主要用于求解线性规划、非线性规划、二次规划和整数规划等问题。一般用于求解线性规划，整数规划问题。
LINDO 6 .1 学生版可求解多达300个变量和150个约束的规划问题。其正式版（标准版）则可求解的变量和约束在10^4量级以上。
LINDO的运行界面
输入模型
求解
点击求解按钮即可
结果
LinDo求解 LP问题的使用说明
线性规划案例
求解动态看板
Update Interval 更新间隔
输入模型
!注释内容，可用中文
!目标函数：最大-max,最小-min,大小写不分
max 3 x1+5 x2+4 x3
!约束，以subject to开始
subject to
2 x1+3 x2<=1500
2 x2+4 x3<=800
3 x1+2 x2 +5 x3<=2000
end
int X1 ！ X1取0-1整数值
Gin X2 ！ X2取任意正整数值
Int 3 ！3个决策变量全取0-1整数值
注意事项
变量以字母开头，下标写在后面，系数与边量之间加空格
不等号为:<= ( <),>=( >) , =, <=与 <等同
变量非负约束可省略
结束时以end标示
输出结果1
LP OPTIMUM FOUND AT STEP 3
OBJECTIVE FUNCTION VALUE
1)
VARIABLE VALUE REDUCED COST
X1
X2
X3
ROW SLACK OR SURPLUS DUAL PRICES
2)
3)
4)
检验数
对偶解
最优目标函数值
输出结果2-灵敏度分析
RANGES IN WHICH THE BASIS IS UNCHANGED:
OBJ COEFFICIENT RANGES
VARIABLE CURRENT ALLOWABLE ALLOWABLE
COEF INCREASE DECREASE
X1
X2
X3
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE
RHS INCREASE DECREASE
2
3
4
见“3.线性规划软件求解习题.doc”
案例练习
案例报告
以小组为单位，以生产或生活实践问题为背景建立线性规划或整数规划模型，并用Excel求解。
报告内容：
选题意义及背景、
构建的模型、
最优方案、
原系统资源配置情况（是否合理，瓶颈在哪，如何改善？）、
最优方案适用性分析（提出的最优解决方案在市场与环境变化多大时，仍然适用。）
第三章 运输模型与分配问题
一、运输问题
二、分配问题
一、运输问题
运输问题的提法:某物资有M个产地Ai, 产量分别是ai (I=1,2,…,m), 有N个销地Bj(j=1,2,…,n). 销量分别是bj (j=1,2,…,n). 若从Ai运到Bj的单位运价为cij (I=1,2,…,m; j=1,2,…,n), 又假设产销平衡, 即
问如何安排运输可使总运费最小?
运输表格
x11
x12
x1n
x21
x22
x2n
xm1
xm2
xmn
销地
单价 产 地
B1
B2
…
Bn
产量
A1 c11 c12 … c1n a1
A2 c21 c22 … c2n a2
… … … … … …
Am cm1 cm2 … cmn am
销量 b1 b2 … bn
如何建立运输问题的LP模型
Xij:从Ai到Bj的运量. Z:总运输费用.
变量？约束方程？
约束方程组的系数矩阵？矩阵的秩？
运输问题的解法
线性规划问题：单纯形法
最小费用流问题：
增加一个总发点Vs和一个总收点Vt 。
表上作业法
运输问题举例
例： 三个工厂B1、B2、B3，它们需要同一种原料，数量分别为72吨、102吨、41吨，另外有三座原料仓库A1、A2、A3可以供应上述原料56吨、82吨、77吨，由于工厂和仓库位置不同，单位运价也不同，具体数据如表。应如何安排运输方案，才能使总运费最小？
min Z = 4X11 ＋ 8X12 ＋ 8X13 + 16X21 ＋ 24X22 ＋ 16X23 + 9X31 ＋ 16X32 ＋ 24X33
.
X11 ＋ X12 ＋ X13 ≤ 56 （供应量约束1）
X21 ＋ X22 ＋ X23 ≤ 82 （供应量约束2）
X31 ＋ X32 ＋ X33 ≤ 77 （供应量约束3）
X11 ＋X21 ＋ X31 ≥ 72 （需求量约束1）
X12 ＋X22 ＋ X32 ≥ 102 （需求量约束2）
X13 ＋X23 ＋ X33 ≥ 41 （需求量约束3）
Xij ≥ 0 （ i, j =1,2,3）
多起点、多终点运输的LP模型
Xij:从Ai到Bj的运量. Z:总运输费用.
单纯形法计算过程
单纯形法计算的求解结果
∴最优方案：从A1运56吨到B2；从A2运41吨到B2；从A2运41吨到B3；从A3运72吨到B1；从A3运5吨到B2。
最小总运费 = 56×8+41×24+41×16+72×8+5×16=2744
运输问题的表上作业法步骤
1.列出产销平衡表；
2.建立初始可行方案(初始基本可行解).
用西北角法；或者 最小元素法.
3.用闭回路法计算检验数并判断（位势法）
4.用闭回路法调整达到最优.
表上作业法的产销平衡表
西北角法步骤
1.从西北角的格(元素)出发填运量=min{此格对应剩余产量与销量},同时用一条直线划去满足的一行或一列.(只划一条线,若需同时划两条线,则应在此行或此列其它格补0,此0当填运量的格看待.)
2.在未划线的格重复1.
3.填最后的格的运量时,要同时划一行和一列两条线.这样保证填运量的格的个数是:m+n-1个.也即基变量的格的个数是: m+n-1个.
56
0
16
16
0
66
66
0
36
36
0
41
41
最小元素法步骤
1.从最小元素的格(元素)出发填运量=min{此格对应剩余产量与销量},同时用一条直线划去满足的一行或一列.(只划一条线,若需同时划两条线,则应在此行或此列其它格补0,此0当填运量的格看待.)
2.在末划线的格重复1.
3.填最后的格的运量时,要同时划一行和一列两条线.这样保证填运量的格的个数是:m+n-1个.也即基变量的格的个数是: m+n-1个.
56
0
16
16
0
61
41
41
0
61
0
41
41
0
0
用闭回路法计算
非基变量的检验数与调整
1.闭回路的概念：从任一非基变量格(未填运量的格)出发,可水平或垂直地走,遇到基变量格(填运量的格)可转(也可跳过)900走,最后转回到起点的非基变量格.则转弯的格形成唯一的一条闭回路.
2.闭回路的特点：
1)第一个格是非基变量格,其他各格都是基变量格.
2)每个格都是转弯的格,每个格都是900的顶点格.
3)一行或一列有闭回路的格一定是双数个.
x12对应的闭回路是:x12,x32,x31,x11. x13对应的闭回路是:x13,x11,x31,x32,x22,x23. x21对应的闭回路是:x21,x22,x32,x31. x33对应的闭回路是:x33,x32,x22,x23.
56
16
41
61
41
检验数的概念
检验数的概念：
闭回路中单数格的单价取+
闭回路中双数格的单价取-
它们的代数和就是此非基变量格的检验数。
检验数λ12=8-16+8-4= -4;
检验数λ13=8-4+8-16+24-16= 4;
检验数λ21=16-24+16-8= 0;
检验数λ33=24-16+24-16=16.
56
16
41
61
41
最优判别与调整
1.最优判别准则:当所有检验数都大于或等于0时,方案最优.
2.调整:
1) 取检验数中负数最小的闭回路调整.
2) 调整量θ= min{闭回路中双数格的运量}.
3)调整方法:闭回路中单数格的运量+ θ,闭回路中双数格的运量- θ,其他格运量不变.
检验数λ12=-4,最小,调整.调整量θ= min{闭回路中双数格的运量} = min{61,56}=56.
调整后方案如下:
56
72
41
5
41
调整λ12 =-4的闭回路后,两个方案的总运费比较
1. 原方案的总运费=4*56+8*16+16*61+24*41+16*41=2968;
2. 调整后的方案的总运费
= 8θ+4(56- θ)+8(16+θ)+16(61- θ)+24*41+16*41
= θ(8-4+8-16)+2968= -4 θ+2968
3. 因为θ是调整量, 大于０; 故调整后的方案的总运费比原方案的总运费小.
检验数的经济意义
1. 检验数是正数,则沿此闭回路调整方案,总运费会增加.为什么?
2 检验数是负数,则沿此闭回路调整方案,总运费会减少.
3. 检验数是0,则沿此闭回路调整方案,总运费不变.
计算结果
检验数λ11=4-8+16-8=4;
检验数λ13=8-16+24-8=8;
检验数λ21=16-24+16-8=0;
检验数λ33=24-16+24-16=16.
∵ λij≥0, ∴最优方案是:从A1运56吨到B2；从A2运41吨到B2；从A2运41吨到B3；从A3运72吨到B1；从A3运5吨到B2。
最小总运费=56×8+41×24+41×16+72×8+5×16=2744.
56
0
16
16
0
61
41
41
0
61
0
41
41
0
0
完整计算过程:
检验数λ12=8-16+8-4= -4;
检验数λ13=8-4+8-16+24-16= 4;
检验数λ21=16-24+16-8= 0;
检验数λ33=24-16+24-16=16.
56
16
41
61
41
检验数λ12=-4,最小,调整.调整量θ=min{闭回路中双数格的运量}= min{61,56}=56.调整后方案如下:
56
72
41
5
41
计算结果
检验数λ11=4-8+16-8=4;
检验数λ13=8-16+24-8=8;
检验数λ21=16-24+16-8=0;
检验数λ33=24-16+24-16=16.
∵ λij≥0, ∴最优方案是:从A1运56到B2,从A2运41到B2,从A2运41到B3,从A3运72到B1,从A3运5到B2.最小总运费=56×8+41×24+41×16+72×8+5×16=2744.
产销不平衡的运输问题
1.总产量>总销量，如何处理？
2.总产量<总销量，如何处理？
产销不平衡的运输问题
1.总产量>总销量: 虚拟一个销地(或称哑元，增添一列),销量=总产量-总销量.单位运费为0. 即可化为平衡的运输问题.
2.总产量<总销量: 虚拟一个产地(或称哑元，增添一行),产量=总销量-总产量.单位运费为0. 即可化为平衡的运输问题.
产销不平衡的运输问题
(1) 供应量小于需求量
虚构一产地(哑元)
(2) 供应量小于需求量
虚构一销地(哑元)
二、分配问题
设有m个不同工件需进行某种加工，现有n台不同机器可以承担此加工任务，但由于每台机器的性能不同，加工不同工件所需的费用和效率都不一样。于是产生了应该将哪一个工件分配给哪一台机器加工所需的总费用最小的问题。
匈牙利算法：
步骤1
将每行的元素减去行中的最小元素；如果某列中没有出现0元素，再将该列元素减去列中的最小元素。
步骤2
进行试分配：从0元素最少的行或列开始，选择一个0，然后划去同行和同列的其它0。如此反复进行，直到所有0元素都被选择或划去为止。若所选0元素的数目等于矩阵的阶，则分配问题的最优解已经得到，终止算法；否则，转入下一步。
步骤3
用最少的直线覆盖所有的0元素：先对没有被选元素的行作一标记，再对已标记的行中所有含0元素的列作一标记，然后对有标记的列中含0元素的行作一标记，如此反复进行，直至找不到可标记的行或列为止。最后划去没有标记的行和有标记的列，即为覆盖所有0元素的最少直线数。
步骤4
将没有被直线覆盖的元素减去其中的最小元素，并将各直线交点上的元素加上该最小元素。然后返回步骤2。
例：求解以下分配问题
步骤1 行作业与列作业：保证每行每列都有0存在。
1 4 6 3
9 7 10 9
4 5 11 7
8 7 8 5
0 3 2 2
2 0 0 2
0 1 4 3
3 2 0 0
步骤2 试分配：由于第一行中只有唯一的0，必须选择，故淘汰第三行第一列处的0，因为同一列中不能选两个0。但第三行只有一个0，它被淘汰后则无0可选。类似地，第三列和第四列中也只能选出一个0。故试分配不成功。
0 3 2 2
2 0 0 2
0 1 4 3
3 2 0 0
步骤3 用最少的直线划去所有0元素：因为第三行没有被选元素，将第三行作一标记。由于此行中第一列含有0元素，再将第一列作一标记。此列中第一行有0，又将第一行作一标记。最后划去没有标记的第2、4行和有标记的第1列。
0 3 2 2 √
2 0 0 2
0 1 4 3 √
3 2 0 0
√
步骤4
将剩余元素减去其中的最小元素1，并将各直线交点上的元素加上1。然后返回步骤2。
0 2 1 1
3 0 0 2
0 0 3 2
4 2 0 0
步骤5
再行试分配：可得问题的最优解x11 = x23 = x32 = x44 = 1，C = 21。
0 2 1 1
3 0 0 2
0 0 3 2
4 2 0 0
第四章 整数规划
整数规划是数学规划的一个重要的分支，在实践中有着广泛的应用背景，例如指派问题、背包问题、旅行推销商问题都是整数规划问题。整数规划是在线性规划基础上把决策变量取值限制为正整数值。其求解难度远大于一般线性规划。
本章任务：了解分支定界法和割平面法的基本思路；掌握整数规划在实际问题中的应用(建模能力)。
整数规划的几个概念
要求所有 xj 的解为整数，称为纯整数规划
要求部分 xj 的解为整数，称为混合整数规划
整数变量只能取0或1，称为0-1整数规划
对应没有整数解要求的线性规划称之为松弛问题
整数规划的解是可数个的，最优解不一定发生在极点
整数规划的最优解不会优于其松弛问题的最优解
整数规划的解法
图解法
穷举法
分枝定界法
割平面法
一、 穷举法
如果线性规划松弛问题的可行域为有界的，则整数规划可行域中解的数量是有限的，从而在理论上，这样的问题可以通过穷举法来求解。
2100个整数解，用最现代化的计算机也要算上几亿年。
穷举法是无法用来求解实际问题。
四舍五入的方法也是行不通的。为什么？
若该整数规划问题有100个0－1整数变量，那么整数解有多少个？
二、 分枝定界法的基本思路
(B)为(A)的线性规划松弛问题。
(C)
(D)
每次分两枝, 每枝多一个约束条件
分枝定界法的步骤
思路: 暂不考虑整数条件,用单纯形法求解,得整数解,停;不是整数解,分枝。
分枝: 每次分两枝, 每枝多一个约束条件， （每个节点代表一个子问题）.
停止分枝条件: 1. 子问题无可行解. 2. 子问题得整数解. 3. 子问题的目标值比下界差.
定界: (max Z )1. 初始整数规划的松弛问题的最优值是上界. 2. 子问题的整数解的最优值是一个下界.
分枝问题解可能出现的情况
表分枝问题解可能出现的情况
情况 2, 4, 5 找到最优解
情况 3 在缩减的域上继续分枝定界法
情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后续分枝的整数解进行比较，结论如情况 4。
分枝定界法优点：
(1)、任何模型均可用；
(2)、思路简单、灵活；
(3)、效率高，速度快；
(4)、常作为商业软件的算法。
三、 割平面法
思路：暂不考虑整数条件,用单纯形法求解,得整数解,停;不是整数解,则取一个不是整数的分量构造割平面。
割平面构造法：设Xi=bi不是整数。对应最终单纯形表的行(方程)是：bi=ai1X1+ai2X2+…+ainXn。
1.将常数和全部系数化为一个正的纯小数加上一个整数。例：=-6; =+4 。
从方程的右边看,由于系数是整数,并且变量也是整数,故右边=整数。左边=右边=整数。但左边除第一项是正的纯小数外,其他项都是一个负的纯小数与一个非负整数变量的积,故得方程左边的整数最大是0,从而得割平面如下：
3.在不等式左边加上一个非负的整数变量Xn+1得割平面方程如下：
4.将割平面方程作为新约束加入最终表,用对偶单纯形法继续求解。重复以上步骤,直到求出最优解为止。
(1)、适于中小型问题，也可解混合整数规 划问题。
(2)、收敛较慢，舍入误差大。
(3)、割平面取法不唯一。
割平面法小结：
四、 整数规划应用举例：
决策问题与0－1决策变量
0－1变量可称为二进制变量、决策变量或逻
辑变量。下面可用如下约束条件来表示决策
中的一些问题：
1、用0－1 变量表示某方案可行或不可行
3. 从N个方案中最多选中k个，则可表示如
下约束:
2、用0－1 变量表示从N个方案中选中一个
方案，则可表示如下约束：
5、方案i与方案j是否选中是同时的:
4、只有方案j选中时，方案i才可能被选中:
如何表示？
6、矛盾约束，可用如下决策变量y表示:
f(x)-5≥0与f(x) ≤0
→-f(x)+5≤M(1-y)与f(x) ≤My
其中 M为足够大的正数。
7、多个条件:fi(x) ≤0, i=1,2,…,n.中选一个
如何表示？
fi(x) ≤M(1-yi) I=1,2,…,n.
y1+y2+…+yn=1
8、逻辑关系约束：
若f(x)无限制, 则g(x) ≤0;
若f(x)<0不成立, 则g(x)无限制.
如何表示？
→f(x) ≥-M(1-y), g(x) ≤My，y为0－1变量。
整数规划应用举例
例1 华美公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益：该公司只有600万元资金可用于投资，由于技术上的原因，投资受到以下约束：
1.在项目1、2和3中必须（只）有一项被选中；
2.项目3和4只能选中一项；（必须选一项）
3.项目5被选中的前提是项目1必须被选中。
如何在上述条件下选择一个最好的投资方案，使投资收益最大。
表 项目投资收益表
Xj=1表项目j选中, Xj=0表项目j未选中. j=1,2,3,4,5.约束条件如何表示？
建立模型
解: Xj=1表项目j选中, Xj=0表项目j未选中. j=1,2,3,4,5.
Z表示总收益. 则模型如下:
Max Z =150X1+210X2+60X3+80X4+180X5
: 210X1+300X2+100X3+130X4+260X5 ≤ 600
X1+X2+X3=1
X3+X4=1
X5 ≤ X1
Xj=0或1; j =1,2,3,4,5.
固定费用问题
例3 红光服装厂可生产三种服装：西服、衬衫和羽绒服。生产不同种类的服装要使用不同的设备，红光服装厂可从专业租赁公司租用这些设备。设备租金和其他经济参数见下表：假定市场需求不成问题，服装厂每月可用工人工时为2000小时，该厂如何安排生产可使每月的利润最大？
表 产品经济参数
解:
1. 目标函数是什么?……
每月的利润最大. 用Ｚ=每月的利润, 则Ｚ=收入-租金-生产成本。
2. 决策变量是什么?…… 如何安排生产?……租用与不租用设备?与租用后生产多少?
3.满足什么? 约束条件是什么?
１) 人工工时只有２０００小时.
２) 设备工时约束. (注意: 租用设备与用设 备生产的关系)
Yj=租用第j种设备; Xj=第Ｉ种产品生产量。
模型如下:
Max Z=400X1+40X2+300X3-280X1-30X2-200X3-5000Y1-
2000Y2-3000Y3
. 5X1+X2+4X3 ≤2000
3X1 ≤300Y1
≤300y2
2X3 ≤300Y3
Xj ≥0, 且为整数, j=1,2,3.
Yj=0或1 , j=1,2,3
练习：集合覆盖和布点问题
解决某市消防站的布点问题。该城市共有6个区，每个都可以建消防站。市政府希望建设的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间见下表：请帮助该市制定一个最节省的计划。
表 消防车在各区行驶距离表
解: Xj=1表地区设消防站, Xj=0表地区不设消防站.
Z=消防站总数, 则模型如下:
Min Z=X1+X2+X3+X4+X5+X6
. X1+X2≥1
X1+X2+X6≥1
X3+X4≥1
X3+X4+X5 ≥1
X4+X5+X6 ≥1
X2+X5+X6 ≥1
Xj=0或1；j =1,2,3,4,5,6.
建立模型
第五章 图与网络模型
图与网络的基本概念
最小树问题
最短路问题
最大流问题
最小费用流问题
指派问题解法(匈牙利法)
图论 Graph Theory
图与网络模型
用图表示上述问题，你能否从A地出发连续走过每座桥一次回到A地吗?
哥尼斯堡七桥问题 (Königsberg Bridge Problem)
欧拉Euler (1707-1783) 图论的创始人，于1736年证明了哥尼斯堡城七桥问题是不行的.
匈牙利数学家Konig 1936年，发表第一本图论专著
《有限图与无限图的理论》
很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联
一、图的基本概念
1.图G=(V,E),V是顶点集,E是边集.
一般用 G(V,E) 表示,
节点: 物理实体、事物、概念一般用vi表
示,
边: 节点间的连线，表示关系一般用eij
表示
图与网路
图 (Graph)
节点和边的集合
一般用 G(V,E) 表示
点集 V={v1,v2,…, vn}
边集E={eij }
节点 (Vertex)
物理实体、事物、概念
一般用 vi 表示
边 (Edge)
节点间的连线，表示有关系
一般用 eij 表示
网络 (Network)
边上具有表示连接强度的权值，如 wij
又称加权图(Weighted graph)
2.有限图与无限图,（看V,E是否有限集合）.
3.边的数目m(G)，节点的数目n(G);
4.顶点的相邻，边的相邻，顶点的关联边；
图中可以只有点，而没有边；而有边必有点
若节点vi, vj 之间有一条边 eij，则称 vi, vj 是 eij 的端点(end vertex)，而 eij 是节点 vi, vj 的关联边(incident edge)
同一条边的两个端点称为相邻(adjacent)节点，具有共同端点的边称为相邻边
一条边的两个端点相同，称此边为环(自回路)；具有两个共同端点的多条边称为多重边(parallel edges)
既没有环也没有多重边的图称为简单图(simple graph)
在无向图中，与节点相关联边的数目，称为该节点的“次” (degree)，记为 d ；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even)；图中都是偶点的图称为偶图(even graph)
无向图与有向图
边都没有方向的图称为无向图，
在无向图中 eij=eji，或 (vi, vj)=(vj, vi)
当边都有方向时，称为有向图，用G(V,A)表示
在有向图中，有向边又称为弧，用 aij表示，i, j 的顺序是不能颠倒的，图中弧的方向用箭头标识
图中既有边又有弧，称为混合图
有向图中，由节点指向外的弧的数目称为正次数（或出度），记为 d+，指向该节点的弧的数目称为负次数（或入度），记为 d–。则在有向图中，出度之和=入度之和；
次数为 0 的点称为孤立点(isolated vertex) ，次数为 1 的点称为悬挂点(pendant vertex)
定理 ：图G中,顶点的总次数=边数×2.
定理 ： 图G中,次为奇数的顶点是偶数个.
8.完全图:每对顶点都有边的无向简单图.
9.二部图（偶图）:V=X∪Y, Ǿ=X∩Y,E的元素一端在X,另一端在Y.记G=(X,Y,E)
10.子图：设有两个图 G1(V1, E1), G2(V2, E2), 若V2 V1, E2 E1， 则 G2 是 G1 的子图
生成子图(子图的顶点集=G的顶点集).
11. 图的同构
11. 图的同构
给定图G1和G2，如果存在点函数f和边函数g，使得 ，并且如果 ，则有 ，那么G1和G2被称为同构图。
网络的基本概念(二)
1.网络=赋权图 .有向网络与无向网络.
2.链:点边序列.链长，简单链(无重复边),初等链(无重复边和无重复点).
3.圈:起终点相同的链.简单圈(无重复边),初等圈(无重复边和无重复点).道路,回路(有方向且方向一致).
4.连通图:G中任意两点间至少有一条链相连.不连通图，任何一个不连通图都可以分成若干个连通子图，每一个连通子图称为原图的一个分图。用k(G)表示图G的分图个数。
三、 图的矩阵表示
2
3
4
1
2
1
3
2
权矩阵
距离矩阵
图1
图的矩阵表示方法有：权矩阵、邻接矩阵、可达矩阵等。
一、权矩阵
2
3
4
1
2
1
3
2
邻接矩阵
图1
二、邻接矩阵
无向图的邻接矩阵是对称的。
通过邻接矩阵我们可以得到图的很多重要性质：
1、行和等于出次，列和等于入次；
2、路径问题。
通过邻接矩阵我们可以算出图中任一点与其它点之间是否有路可通，若有的话走几步到达该点。当邻接矩阵A的k次幂中i行j列
为1，则表示vi经过k-1个点
到达vj。
2
3
4
1
2
1
3
2
可达矩阵
图1
二、可达矩阵M
欧拉图
什么是欧拉道路，欧拉回路，欧拉图？
欧拉道路(存在一条道路，经过每边一次且仅一次) ，欧拉回路(存在一条回路，过每边一次且仅一次)，欧拉图(有欧拉回路的图).
定理 ：连通图G中有欧拉回路，当且仅当G中无奇点.
推论：连通图G中有欧拉道路，当且仅当G中恰有两个奇点.（例:七桥问题、一笔划问题）
定理 ：连通有向图G是欧拉图，当且仅当每个顶点的出次=入次.
奇点数为4，不能从A地出发连续走过每座桥一次回到A地。假设C,D点无连线，是否可以呢？
哥尼斯堡七桥问题 (Königsberg Bridge Problem)
中国邮路问题
1.问题描述: 一个邮递员,每天从邮电局出发，走遍所有他负责的街道，回到邮电局，问他如何走路程最短?由我国管梅谷教授于1962年提出
等价于寻找欧拉回路！
2.数学描述: 连通图G，每边有非负权，求一条回路过每边至少一次，而且满足总权最小.
3.定理 已知图G*=G+E1无奇点，则增加的重复边之和为最小的充要条件:
1)每条边最多重复一次；
2)对图中每个初等圈，重复边的长度和≤圈长的一半.
奇偶点图上作业法
求解下图所示网络的中国邮路问题。
第一步，确定初始可行方案
是否有奇点？
四个奇点v2 ，v4 ， v6 ， v8
如何构造欧拉回路？
增加重复边，奇点两两配对v2 -v4 ， v6 - v8
重复边的总长为51。
第二步，调整可行方案，使重复边最多为一次
去掉多余的重复边
重复边的总长为21。
第三步，每个初等圈是否满足定理 ，直至满足为止。
发现圈{v1 ， v2 ， v5 ， v4 }的总长度为24，而重复边的长为14，大于该圈总长度的一半。则调整
再检查每个初等圈是否满足定理 ， 再次调整。
如右图，得到最优方案。
二、树图与最小生成树
一般研究无向图
树图：倒置的树，根(root)在上，树叶(leaf)在下
多级辐射制的电信网络、管理的指标体系、组织结构、家谱、分类学等都是典型的树图
最小树问题
定义：树:连通而且不含圈的无向图。
下列说法等价：无圈且边数=N-1；连通且边数=N-1；无圈,但加一条边得唯一的一个圈；连通但舍去一条边不连通；任意两点有唯一的链相连.
生成树:若图G的生成子图是一棵树，则称该树为图G的生成树，或简称图G的树.
图G有生成树的充要条件为G是连通图；
生成树不唯一
生成树的权：一个生成树所有树枝上权的总和；
最小生成树：具有最小权的生成树称为最小生成树，或简称最小树
最小生成树的求法（两种方法）:
一、Kruskal 算法（避圈法）:
首先将图G的边按权从小到大顺序排列,每次从排列中选一条边与已选边比较,构成圈,不选此边;不构成圈,选此边.直到选够N-1条边为止.
首先将图G的边按权从小到大顺序排列,
9个点，则需选8条边。
二、破圈法原理
方法原理
如果网络图中无圈并且m=n-1，则已经是树；
如果网络图中有圈，则截去该圈中权数最大的边；这样，并不影响网络图的连通性，且能使边数减少一个；
经过一定次数的截边，网络图中将再也没有圈，成为无圈图；
如果此时的网络满足m=n-1，则已经是树；
由于每次截去的边在圈中具有最大的权数，因此获得的树也是最短的树。
方法步骤
①在网络图中寻找一个圈，若已经无圈则转③。
②在圈中选取权数最大的边，从网络图中截去该边，对新的网络，转①。
③若m=n-1，则已找到最短树，否则网络图不连通，无最短树。
最短路问题
最短路问题是图论中的一个基本问题。
它在通讯网络设计、石油管线铺设、公路交通规划等实际问题中有着广泛的应用。
一、Dijkstra算法
1.问题提法:图G中任意两点vs,vt求出连接此两点的总权最小的路.
2.思路:用最短路不断向外扩张(标号).
3.标号法(Dijkstra算法):
1)给vs标P标号,P(vs)=0,其他各点标T标号,T(vi)=+∞.
2)若vi点为刚得到P标号的点,考虑这样的点vj:(vi,vj)是图的边,而且vj为T标号.对vj的T标号更改为T(vj)=min[T(vj),P(vj)+lij].
3)比较全部具有T标号的点,把最小者改为P标号,设vk为T标号最小者,则
P(vk)=
若全部点均为P标号则停.否则用vk代vi转2).
Dijkstra最短路算法举例
例 求v1 点到 v8点的最短路。
=0
解: Dijkstra最短路算法计算过程
（1）首先给v1标P标号，P(v1)=0，其余点给T标号。
=+
=4
=4
=+
=6
=6
解:
由T(vj)=min[T(vj)，P(vj)+lij]， (v1 ,v2 )， (v1 ,v3 )边属于E，且v2 ,v3为T标号，
T(v2)=min[T(v2)，P(v1)+l12]=min[+，0+4]=4 T(v3)=min[T(v3)，P(v1)+l13]=min[+，0+6]=4
v1
v3
v2
v5
v4
v7
v6
v8
=0
===4
=
=6
=6
4
6
5
4
4
7
9
7
5
6
5
4
1
解:
v1
v3
v2
v5
v4
v7
v6
v8
P=0
P=4
P=6
P=8
P=9
P=13
P=14
P=15
4
6
5
4
4
7
9
7
5
6
5
4
1
路长P( v8 )=15，最短路：v1 —v2 — v5 — v7 — v8
解:
Dijkstra最短路算法的适应范围
永久标记Pj 表示 vs 到 vj 的最短路，因此 要求 dij0；当dij ≤ 0，是否适用？
请举例说明？
实际最短路线v1 到 v3到 v2
而不是v1 到 v2
P( v3)=2
P( v2)=1
Dijkstra最短路算法的特点和适应范围
一种隐阶段的动态规划方法
每次迭代只有一个节点获得永久标记，若有两个或两个以上节点的临时标记同时最小，可任选一个永久标记；总是从一个新的永久标记开始新一轮的临时标记
永久标记Pj 表示 vs 到 vj 的最短路，因此 要求 dij0，第 k 次迭代得到的永久标记，其最短路中最多有 k 条边，因此最多有n1 次迭代
可以应用于简单有向图和混合图，在临时标记时，所谓相邻必须表明 vs是箭头指向的节点；若第 n1 次迭代后仍有节点的标记为 ，则到该节点无有向路径
如果只求 vs 到 vt 的最短路，则当 vt 得到永久标记算法就结束了；但算法复杂度是一样的
应用 Dijkstra 算法 n1 次 ，可以求所有点间的最短路
vs 到所有点的最短路也是一棵生成树，但不是最小生成树
二、Bellman算法
一.功能:
１.求指定点到网络任意点的最短路.
２.边是负数也可以.
二.思路. 方法:
１.思路:从v1到vj的最短路必然从v1直接到vj或是从v1到vi , 再从vi到vj, 从v1到vi必然是最短路, 有
２.方法:
*
例 用Bellman算法求如下图中V1到各点的最短路。
v1
v2
v4
v6
v8
v5
v7
v3
2
5
-3
-2
4
6
7
-3
4
2
4
-1
3
解：由图知，
初始条件
＝min{ 0+0, 2+ , 5+ , －3+ , , , , ,}
＝0
＝min{ 0+2, 2+ 0, 5+ , －3+ , , , , ,}
＝2
j
i lij
V1 v2 v3 v4 v5 v6 v7 v8
V1
v2
V3
V4
V5
V6
V7
v8 0 2
0 5
-2
0
4 -3
0
7
4
0
-3
3
6
0
2
0
-1
4
0 0
2
5
-3 0
2
0
-3
6
11 0
2
0
-3
6
6
15 0
2
0
-3
3
6
14
10 0
2
0
-3
3
6
9
10 0
2
0
-3
3
6
9
10
最短路程与最短路线
最短路程:
最后的一列的元素 就是v1到vj的最短路长.
最短路：逆向法求出.
例:V1到V7最短路程是9.
最短路线是: 从-1+10=9与14比较取9,所以经V8,从4+6=10,所以经V6,从6+0=6,所以经V3,从-2+2=0,所以经V2。
V1到V7的最短路线是:V1到V2到V3到V6到V8到V7。
设备更新问题
例 某公司每年年初需决定某种设备是购置新的，还是使用旧的。若购置新设备，就要支付购置费用；若继续使用旧的，则需支付维修费用。现欲制定五年内的设备使用计划，使总的支付费用最小。已知该设备在未来各年年初的价格为：
使用不同时间的设备所需要的维修费用为：
【分析】可供选择的设备更新方案有很多。例如，每年购置一台新设备，则购置费用为： 11+11+12+12+13 = 59 万元，而每年支付的维修费用为 5 万元，五年合计为 25 万元，因此五年总支出为84 万元。又如，若在第一、三、五年各购置一台，则设备购置费为 11+12+13 = 36 万元，维修费为5+6+5+6+5 = 27 万元，五年总支出为 63 万元。
设备更新问题
图中用点vi 代表“第 i 年年初购置一台新设备”这种状态， ( 加设一点v 6 ，可以理解为第五年年底) ，从 vi 到vi +1 ,…,v6 各画一条弧，弧(vi ,vj) 表示在第 i 年年初购置的设备一直使用到第 j 年年初 ( 即第j -1 年年底) 。
每条弧的权可按已知资料计算出来。例如， (v1 ,v4) 是第一年年初购置一台新设备 ( 支付购置费 11) ，一直使用到第三年年底( 支付维修费 5+6+8 = 19) ，故(v1 ,v4) 上的权为 30 。
设备更新问题
这样一来，制定一个最优的设备更新计划的问题就等于寻求从 v 1 到 v 6 的最短路的问题。
在多数情形下，最短路不一定是唯一的。本例中的最短路有两条： {v1, v3, v6} 和 {{v1, v4, v6} 即有两个最优方案：一个方案是在第一年、第三年各购置一台新设备；另一个方案是在第一年、第四年各购置一台新设备，五年的总支付均为 53 万元。
最短路问题3
1.问题提法:图G中任意两点的最短路.
2.思路:dij=min(dij,dik+dkj),每一个点都迭代一次.
算法:
1)输入权矩阵D(0)=D=(dij)n×n,dij=
lij为vi到vj的距离.
2)计算D(k)=(dij(k))n×n (k=1,2,…,n)
其中dij(k)=min[dij(k-1),dik(k-1)+dkj(k-1)]
3)D(n)=(dij(n))n×n中的元素dij(n)就是vi到vj的最短路长.
例 求下图中任意两点间的最短路.
求任意V1到V5间的最短路.
最短路程与最短路线
最短路程:最后矩阵中的元素dij(n)就是vi到vj的最短路长.
最短路线：逆向法求出.
例：V1到V5最短路程是6，6是从第3步的1+5与7选6， 1是V1到V3，5是V3到V5。5是从第2步的2+3与8选5， 3是V3到V2 ，2是V2到V5。所以V1到V5经V3, V3到V5经V2，得V3到V5的最短路线是：V1到V3到V2到V5。
设v1,v2,v3,v4, v5５个地区的甘蔗产量分别是8,5,6,4,1千吨, 现规划在５个地区之一建一糖厂,建在哪个点使总运输量最少?
*
最大流问题
一、引言
许多系统包含了流量问题，例如公路系统中有车辆流，控制系统中有信息流，供水系统中有水流，金融系统中有现金流，城市给排水系统的水流问题等等。
50年代，Ford等建立“网络流理论”，提出了Ford – Fulkerson 算法，有效地解决了最大流问题。
举例：最大流问题
例如，输油管道网的总运输量最大。
二、网络流基本概念
定义 设一个赋权有向图G =（V,E）,在V中指定一个发点vs和一个收点vt,其他的点叫做中间点。对于G中的每一个弧（vi,vj）∈E,都有一个权 cij 叫做弧的容量。我们把这样的图G叫做一个容量网络系统，记做G =（V，E，C）。
网络G上的流，是指定义在弧集合E上的一个函数f={f(vi,vj)}={fij} f(vi,vj)=fij叫做在弧(vi,vj)上的流量。
v3
v2
v1
v4
vs
（2）
（3）
（2）
（5）
（3）
（3）
（6）
（1）
（1）
（2）
fij
如上网络上的一个流（运输方案）
每一个弧上的流量fij就是运输量
例如fs1=5,fs2=3,f13=2等等
vt
网络系统上流的特点：
(1)发点的总流出量和收点的总流入量
必相等；
(2)每一个中间点的流入量与流出量相
等；
(3)每一个弧上的流量不能超过它的最
大通过能力（即容量）。
定义 网络上的一个流f 叫做可行流，如果f满足以下条件
（1）容量条件：对于每一个弧（vi,vj）∈E,有 0 fij cij .
（2）平衡条件：
对于发点vs，有∑fsj-∑fjs=v(f)
对于收点vt，有∑ftj-∑fjt=-v(f)
对于中间点，有∑fij-∑fji=0
其中发点的总流量（或收点的总流量）v(f)叫做这个可行流的流量。
任意一个网络上的可行流总是存在的。例如零流v(f)=0,就是满足以上条件的可行流。
网络系统中最大流问题就是在给定的网络上寻求一个可行流f,其流量v(f)达到最大值。
设流f={fij}是网络G上的一个可行流。我们把G中fij=cij的弧叫做饱和弧，fij<cij的弧叫做非饱和弧，fij>0的弧为非零流弧，fij=0的弧叫做零流弧。
设μ是网络G中连接发点νs和收点
vt的一条链。定义链的方向是从vs到
vt，于是链μ上的弧被分为两类：一
是弧的方向与链的方向相同，叫做前
向弧，前向弧的集合记做μ+。二是弧
的方向与链的方向相反，叫做后向
弧，后向弧的集合记做μ-。
在下图中，(v4,v3)是饱和弧，其他的弧是非饱和弧，并且都是非零流弧。
v3
v2
v1
v4
vs
（17,2）
（3,3）
（5,2）
（10,5）
（8,3）
（6,3）
（11,6）
（4,1）
（5,1）
（3,2）
fij
如图，在链（vs,v1,v2,v3,v4,vt)中，
μ+={(vs,v1),(v1,v2),(v2,v3),(v4,vt)},
μ-={(v4,v3)}.
vt
定义 可增广链，如果链μ满足以下条件：
1．在弧(vi,vj)∈μ+上，有0<=fij<cij,即μ+中的每一条弧是非饱和弧。
2．在弧(vi,vj)∈μ-上，有0<fij<=cij,即μ-中的每一条弧是非零流弧。
例如在上图中，链μ=（vs,v1,v2,v3,v4,vt）就是一条可增广链。
再如：
设图G=(V，A，C)，点集S,TV,S∩T=ф中。将起点在S，终点在T 的所有弧作成集合，记做（S，T）。
定义 设一个网络G=(V,E,C)。如果点集V被剖分为两个非空集合V1和V1，发点vs∈V1,收点vt∈V1,那么将弧集（V1,V1）叫做是分离vs和vt的截集。
设一个截集（V1, V1）.将截集（V1,V1）中所有的弧的容量的和叫做截集的截量，记做s(V1,V1),亦即s(V1,V1)=∑cij (vi,vj)∈(V1,V1)
vs
v2
v4
v3
vt
2
4
5
3
3
5
6
下面的事实是显然的：一个网络G中，任何一个可行流f的流量v(f)都小于或等于这个网络中任何一个截集(V1,V1)的截量。并且，如果网络上的一个可行流f*和网络中的一个截集（V1*,V1*），满足条件v*(f*)=c(V1*,V1*),那么f*一定是G上的最大流，而（V1*,V1*）一定是G的所有的截集中截量最小的一个（即最小截集）。
流量与割的容量的关系
定理 可行流流量小于或等于截的容量.
定理 任何一个网络G中，从vs到vt的最大流的流量等于分离vs，vt的最小截的容量.
推论：网络中的一个可行流f*是最大流的充分必要条件是，不存在关于f*的增广链。
以上推论实际上提供了一个寻求网络系统最
大流的方法：如果网络G中有一个可行流f，只
要判断网络是否存在关于可行流f的增广链 。
如果没有增广链，那么f一定是最大流。如有增
广链，那么可以不断改进和增大可行流f的流
量，最终可以得到网络中的一个最大流。
三．标号法
从网络中的一个可行流f出发（如果G中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。
用给顶点标号的方法来定义V1*.在标号过程中，有标号的顶点是V1*中的点，没有标号的点不是V1*中的点。如果vt有了标号，表示存在一条关于f的增广链。如果标号过程无法进行下去，并且vt未被标号，则表示不存在关于f的增广链。这样，就得到了网络中的一个最大流和最小截集。
1． 标号过程
在标号过程中，网络中的点或者是标号点（分为已检查和未检查两种）。或者是未标号点。每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的。以便找出增广链。第二个标号是为了用来确定增广链上的调整量θ。
标号过程开始，先给vs标号（0，+∞）。这时，vs是标号未检查的点，其他都是未标号点。一般地，取一个标号未检查点vi，对一切未标号点vj：
1）如果在弧（vi,vj）上，fij<cij,那么给vj标号（vi,l(vj)）.其中l(vj)=min[l(vi),cij-fij].这时，vj成为标号未检查的点。
2）如果在弧（vj,vi）上，fij>0,那么给vj标号（-vi, l(vj)）.其中l(vj)=min[l(vi), fji].这时，vj成为标号未检查点。
于是vi成为标号已检查的点。重复以上步骤，如果所有的标号都已经检查过，而标号过程无法进行下去，则标号法结束。这时的可行流就是最大流。但是，如果vt被标上号，表示得到一条增广链μ，转入下一步调整过程。
2.调整过程
首先按照vt和其他的点的第一个标号，反向追踪，找出增广链μ。例如，令vt的第一个标号是vk，则弧（vk,vt）在μ上。再看vk的第一个标号，若是vi，则弧(vi,vk)都在μ上。依次类推，直到vs为止。这时，所找出的弧就成为网络G的一条增广链μ。取调整量θ= l(vt),即vt的第二个标号
fij+θ，当(vi,vj)∈μ+
令f’ij= fij-θ，当(vi,vj)∈μ-
其他不变
再去掉所有的标号，对新的可行流f’={f’ij},重新进行标号过程，直到找到网络G的最大流为止。
举例: 最大流算法
v3
vs
v1
v2
vt
(-v1,1)
(3,2)
(3,2)
(5,4)
(4,4)
(4,2)
(Cij,fij)
举例
v3
vs
v1
v2
vt
(0, ∞)
(+vs,1)
(+v1,1)
(-v1,1)
(+v2,1)
(3,2)
(3,2)
(5,4)
(4,4)
(4,2)
(Cij,fij)
举例
v3
vs
v1
v2
vt
(0, ∞)
(+vs,1)
(+v1,1)
(-v1,1)
(+v2,1)
(3,2)
(3,2)
(5,4)
(4,4)
(4,2)
vs
v3
v1
v2
vt
(5,4)
(4,4)
(Cij,fij)
调整过程
(Cij,fij)
例
v3
vs
v1
v2
vt
v5
v4
v6
如图(a)表示一个网络及初始可行流 ,每条边上的有序数表示(Cij,fij)。求网络的最大流。
(3,2)
(4,2)
(5,4)
(3,3)
(2,2)
(2,2)
(3,0)
(4,2)
(5,2)
(5,5)
(3,3)
求解过程
v3
vs
v1
v2
vt
v5
v4
v6
(+vs,2)
(+v1,1)
(-v5,2)
(+v4,2)
(3,2)
(4,2)
(5,4)
(3,3)
(2,2)
(2,2)
(3,0)
(4,2)
(5,2)
(5,5)
(0, ∞)
(+vs,1)
(+v2,2)
(+v1,2)
图(b) 标号过程
(3,3)
v3
vs
v1
v2
vt
v5
v4
v6
(+vs,2)
(+v1,1)
(-v5,2)
(+v4,2)
(3,2)
(4,4)
(5,4)
(3,3)
(2,2)
(2,2)
(3,2)
(4,4)
(5,4)
(5,5)
(0, ∞)
(+vs,1)
(+v2,2)
(+v1,2)
(3,1)
图(c) 调整中的可增广链及调整后的可行流
最小割集容量＝？
标号算法的推广
（1）可以用来解决多收点多发点网络的最大流问题，只要添加两个虚拟的新点作为发点和收点，并令其到发点或收点的容量为无穷大即可。
（2）可以推广到无向网络的最大流问题，把每条边用两条方向相反的边代替，而且容量不变(两条都容量一样)。
最大匹配问题
背景原型：
N个人分配做M项工作，由于每人能力、特长不同，因此每人各能胜任其中某几项工作，假设每项工作只需一人做，每人只做一项工作，如何分配使尽量多的人有工作？
定义1.二部图G=(X,Y,E),M是E的子集,且两边无公共点,则M是G的一个匹配.
定义2.若M的边数最大,则M是最大匹配.
算法:归于最大流算法（增加发点和收点）.
最大分配问题：属于最大流问题，可用最大流标号算法解决 ；
例 5个人(X)分配做4项工作(Y)，每人只做一项工作，如何使尽量多的人就业？
X1
X2
X3
X4
X5
Y1
Y2
Y3
Y4
最大匹配问题
X1
X2
X3
X4
X5
Y1
Y2
Y3
Y4
一个最大匹配如图（红线）
最小费用流问题
在实际的网络系统中，当涉及到有关流的问题的时候，我们往往不仅仅考虑的是流量，还经常要考虑费用的问题。比如一个铁路系统的运输网络流，即要考虑网络流的货运量最大，又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。
一般提法
已知容量网络G=(V,E,C),每条边(vi,vj)除了已给出容量Cij外,还给出了单位流量的费用dij(≥0),记G=(V,E,C,d).求G的一个可行流f={fij),使得流量W(f)=v,且总费用d(f)= 最小.
思路
先找一个流量的W(f(0))<v的最小费用流f(0),然后寻找从vs到vt的可增广链μ,并使它的费用最小,沿此链调整流f(0),使流量增加,重复此步骤,直到流量达到v为止.
在一个网络G中，当沿可行流f的一条增广链μ，以调整量θ=1改进f，得到的新可行流f’的流量，有v(f’)=v(f)+1，而此时总费用d(f’)比d(f)增加了
d(f’)-d(f)=∑dij(f’ij-fij)-∑dij(fij-f’ij)=∑dij-∑dij
μ+ μ- μ+ μ-
将∑dij-∑dij叫做这条增广链的费用。
定理 如果可行流在流量为v(f)的所有可行流中的费用最小，并且是关于f的所有增广链中的费用最小的增广链。那么沿增广链μ调整可行流f，得到的新可行流f’，也是流量为v(f’)的所有可行流中的最小费用流。
依次类推，当f’是最大流时，就是所要求的最小费用最大流。
显然，零流f={0}是流量为0的最小费用流。一般地，寻求最小费用流，总可以从零流f={0}开始。下面的问题是：如果已知f是流量为v(f)的最小费用流，那么就要去寻找关于f的最小费用增广链。
对此，重新构造一个赋权有向图费用网络L(f)，其顶点是原网络G的顶点，而将G中的每一条弧(vi,vj)变成两个相反方向的弧（vi,vj）和(vj,vi)，并且定义L(f)中弧的权wij为：
费用网络L(f)的构造
1).顶点与原网络一样,每条边用两条相反的有向边代替；.2).边及边的权定义如下:
①当边(vi,vj) ∈E,令各边的权lij
②当边(vj,vi)为原G中的边(vi,vj)反向边,令各边的权lij
的意义？
权lij = 的边可去掉！
这样，在网络G中寻找关于f的最小费用增广链就等于价于在L(f)中寻求从vs到vt的最短路。
算法开始，取零流f(0) ={0}.一般地，如果在第K-1步得到最小费用流f(K-1),则构造图L（f(K-1)）。在图L（f(K-1)）中，寻求从vs到vt的最短路。如果不存在最短路，则f(K-1)就是最小费用最大流。如果存在最短路，则在原网络G中得到相对应（一一对应）的增广链μ0
在增广链μ上对f(K-1)进行调整，取调整量θ=min{min((cij-f(k-1)ij),min(f(k-1)ij)}.
μ+ μ-
令
f(k-1)ij +θ，在μ+上
f(k)ij = f(k-1)ij -θ，在μ-上
其他的不变。
得到一个新的可行流f(k)，在对f(k)重复以上的步骤，直到G中找不到相对应的增广链时为止。
例 求流量V为10的最小费用流，边上括号内为(Cij,dij).
解: 取零流为初始可行流，即f(0)={0}
从Vs到Vt的可增广链μ最大流算法进行调整。
最短路:Vs到V2到V1到Vt；
θ=min{8,5,7}
相应边为：（ Vs , V2 ）, （ V2 , V1 ）, （ V1 , Vt ）
解: 有f(k-1)，流量为W(f(k-1)) < 10
从Vs到Vt的可增广链μ最大流算法进行调整。
最短路:Vs到V1到Vt；
θ= min {10,7-5}
构造长度（费用）网络L(f)，求从Vs到Vt的最短路。
相应边为：（ Vs , V1 ）, （ V1 , Vt ）
解:
左：长度（费用）网络L(f)的构造，求从vs到vt的最短路。
右：从vs到vt的可增广链μ最大流算法进行调整。
是否最大流？
-4
4
-2
-3
-1
6
-2
3
-1
2
W(f(1))=11
最小费用最大流d(f(1))=8×1＋3×4＋5×2＋3×3 ＋ 1×6＋7×1＋3×3＝60
用Bellman算法求初最短路为12，最短路径为 Vs到V1到V3到Vt
θ=min{8,2,1}
最优匹配问题(指派问题)
最大匹配问题：属于最大流问题，可用最大流标号算法解决 ；
最优匹配问题 ？
N个人分配做M项工作，每人只做一项工作，由于每人能力、特长不同，因此每人干每项工作的工时也不同，问如何指派使工作总工时最小？
最大匹配问题
X1
X2
X3
X4
X5
Y1
Y2
Y3
Y4
5个人(X)分配做4项工作(Y)，每人只做一项工作，如何使尽量多的人就业？
最大匹配问题
X1
X2
X3
X4
X5
Y1
Y2
Y3
Y4
一个最大匹配如图（红线）
最优分配问题
定义 覆盖
最小点覆盖
定理 （ Konig 定理）
最小点覆盖
定义：图G=(V,E)，点集C V，若G中每条边至少有一个端点在C中，称C为G的一个点（对边的）覆盖。
使点数达到最少的点集C称为G的最小点覆盖。
定理 （ Konig 定理）
二部图G=(X,Y,E)，M为最大匹配，C为最小点覆盖，则有|M||C|。
举例：下图的最小点覆盖？
X1
X2
X3
X4
X5
Y1
Y2
Y3
Y4
{X1, X5, Y1, Y2}是最小点覆盖
最优分配问题的解法 (匈牙利法)
1. 给二部图每个点标号.
2. 作矩阵B:
3. 对B中的0元素求最小点覆盖:
直到求出n个不同行不同列的0元素.
4. 修改标号. 首先决定调整量，把各点标号改为新标号，转2。
介绍：指派问题解法(匈牙利法)
1. 各行(列)减去各行(列)的最小元素.
2. 试求最优方案:
从0元素最少的行起圈0,用◎表示.划去同行同列其它0,用Ǿ表示.若圈了N个◎,则得最优方案;否则,转3.
3. 求最少数直线覆盖0元素:
1).没有◎的行记×, 2).记×的行有0元素的列记√, 3).记√的列有◎的行记×,反复1),2),3),直到不能记为止, 4).记√的列划线,没有记×的行划线.
4. 找出没有直线复盖的元素中最小元素θ,没有直线复盖的元素- θ,直线交叉的元素+ θ,其它元素不动.转2.
例 哪个工人操作哪台机器可使总工时最小?
机器
工时
工人 y1 y2 y3 y4
X1
X2
X3
X4 2
15
13
4 10
4
14
7 3
14
16
13 7
8
11
9
解: 初始标号
作矩阵B1 ，然后求最小点覆盖:
最小点覆盖:Xa＝{X2, X3},Yb＝{Y1}
0
11
2
0
8
0
3
3 1
10
5
9 5
4
0
5
2
15
13
4 10
4
14
7 3
14
16
13 7
8
11
9
修改标号
作矩阵B2 ，然后求最小点覆盖:
求调整量，
Wij ＝ W13 ＝ 3； l(xi) ＝ 2， l(yi) ＝0
＝ min [Wij －l(xi) － l(yi)]
＝3-2-0=1
0
12
3
0 7
0
3
2 0
10
5
8 4
4
0
4
2
15
13
4 10
4
14
7 3
14
16
13 7
8
11
9
最小点覆盖:Xa＝{X2, X3},Yb＝{Y1, Y3}
作矩阵B2 ，然后求最小点覆盖:
0
12
3
◎ 7
◎
3
2 ◎
10
5
8 4
4
◎
4
0
12
3
0 7
0
3
2 0
10
5
8 4
4
0
4
最优方案:工人X1操作机器Y3,工人X2操作机器Y2,工人X3操作机器Y4,工人X4操作机器Y1.
最小总工时=3+4+11+4=22.
全体标号和＝？
全体标号和＝ 3+4+11+5+(-1) + 0+ 0+ 0 =22
最小点覆盖:Xa＝{X2, X3},Yb＝{Y1, Y3}
2
15
13
4 10
4
14
7 3
14
16
13 7
8
11
9
解: 初始标号
作矩阵B1 ，然后求最小点覆盖:
修改标号
作矩阵B2 ，然后求最小点覆盖:
0
11
2
0
8
0
3
3 1
10
5
9 5
4
0
5
0
12
3
◎ 7
◎
3
2 ◎
10
5
8 4
4
◎
4
2
15
13
4 10
4
14
7 3
14
16
13 7
8
11
9
2
15
13
4 10
4
14
7 3
14
16
13 7
8
11
9
最优方案:工人X1操作机器Y3,工人X2操作机器Y2,工人X3操作机器Y4,工人X4操作机器Y1.
最小总工时=3+4+11+4=22.
（接上页）
全体标号和＝？
最小点覆盖:Xa＝{X2, X3},Yb＝{Y1, Y3}
0
12
3
◎ 7
◎
3
2 ◎
10
5
8 4
4
◎
4
0
12
3
◎ 7
◎
3
2 ◎
10
5
8 4
4
◎
4
2
15
13
4 10
4
14
7 3
14
16
13 7
8
11
9
举例
设有一个4人小组,接到上级的4项任务,如何安排人与任务,使消耗的总时间最少?他们的效率如下
任务1 任务2 任务3 任务4
甲 4 6 6 7
乙 1 6 7 3
丙 2 5 4 2
丁 3 2 1 4
解:
×
×
√
答:甲做任务2 ;乙做任务1 ;丙做任务4;丁做任务3.最少总时间=6+1+2+1=10.
货郎担问题
(旅行推销员问题，Traveling Salesman Problem)
货郎担问题：设v1, v2,...,vn 为 n 个已知城市，城市之间的旅程也是已知的，货郎从 v1出发，走遍所有城市一次且仅一次又回到出发点，应如何选择行走路线并使总旅程最短。
典型的应用：
乡邮员的投递路线
邮递员开邮箱取信的路线问题
邮车到各支局的转趟问题
货郎担问题
货郎担问题 （选择一条路线，经过每个城市一次且仅一次，然后回到起点）
即要构成哈密尔顿回路。
（完全图：每一对顶点间都有边相连的无向简单图）
中国邮路问题（选择一条路线，经过所有街道至少一次，然后回到起点）
实际的货郎担问题
(加工零件的排序问题)
有N种零件要在一部机床上加工，从加工完零件i转到加工零件j需要准备时间tij，希望安排一个加工顺序，使总的准备时间最少.
例 5个城市的货郎担问题。
5个零件要在同一机床上加工，从I零件转到J零件的准备时间如表，如何安排加工顺序使总的准备时间最少?
V1 V2 V3 V4 V5
V1 ∞ 1 7 4 3
V2 2 ∞ 6 3 4
V3 1 6 ∞ 2 1
V4 1 5 4 ∞ 6
V5 7 5 4 5 ∞
从
到
解:第一步 最优分配的算法（匈牙利法）求解
∞ 0 6 3 2
0 ∞ 4 1 2
0 5 ∞ 1 0
0 4 3 ∞ 5
3 1 0 1 ∞
∞ ◎ 6 3 2
0 ∞ 4 ◎ 2
1 5 ∞ 1 ◎
◎ 3 2 ∞ 4
3 1 ◎ 1 ∞
V1→V2→V4→V1, V3→V5→V3，总路程=1+3+1+1+4=10
第二步 总路程=10作为下界.
第一枝：去掉d35=1,改为d35=∞； 第二枝：保留d35=1,令 d53=∞,去掉D的第三行与第五列,即不许V3到其他点,也不许其他点到V5。分别求解：
作矩阵B1 ，然后求最小点覆盖:
作矩阵B2 ，然后求最小点覆盖:
子问题的最优解: V1→V2→V5→V3→V4→V1.
总路程=1+4+4+2+1=12。是一个上界(可行解).
∞ 0 6 3
0 ∞ 4 1
0 4 3 ∞
2 0 ∞ 0
∞ ◎ 3 3
◎ ∞ 1 1
0 4 ◎ ∞
2 0 ∞ ◎
子问题的最优解:V1→V2→V1, V3→V5→V4 →V3.
总路程=1+2+1+5+4=13。是否继续分枝？
该问题的最优解: V1→V2→V5→V3→V4→V1.
总路程=1+4+4+2+1=12.
子问题的最优解:V1→V2→V1, V3→V5→V4 →V3.
总路程=1+2+1+5+4=13. 是否继续分枝？
总路程大于上界12(不是最优解) ，不用再分枝.
Management scientist 软件操作
1、最短路
2、最小支撑树
3、最大流量
转换为线性规划问题
第六章 网络计划技术
(1)、又名：统筹方法，是一种科学的组织管理技术。
(2)、应用：工业、农业、政府、科研、军事中的项目计划与管理。
例：
阿波罗载人登月计划
海陆空联合作战计划
美国北极星导弹研制系统（缩短1年半）
横道图 (甘特图)
甘特图Gantt Charts
甘特图 (Gantt charts)是一种用来展示及监督项目进度的工具，于1917年首创。
甘特图 为图形表示法:
横轴代表时间，纵轴代表各个活动，活动的完成时间以长条表示.
最早时间的甘特图，长条开始于某活动的最早开始进行的时间.
*
举例1：蓝天电脑公司产品项目
蓝天电脑公司制造个人计算机
品牌SKY Computers需要设计、制造
对其产品进行营销活动
三个主要的工作:
制造新计算机
训练员工与销售员代表.
广告营销
如何显示各活动间的先后顺序关系？
*
活动 叙述 A 设计原型(Prototype model)
B 材料购买
制造活动 C 原型制造 D 设计修正
E 第一次生产
F 员工训练
培训活动 G 员工对产品原型的建议
H 销售人员训练
广告活动 I 生产前广告活动 J 生产后广告活动
蓝天电脑公司活动内容
*
蓝天电脑公司活动前后关系表
(Precedence Relationships Chart)
*
蓝天电脑公司产品项目甘特图
*
甘特图- 控制项目进度
甘特图可以用来监控各个活动的进度
做法是：在已完成的部份就其所占的比例在长条上画上阴影
管理者检查此图就可以了解项目是否按时间完成，及时控制项目进度。
例如，135天后的项目进度情况
*
A
90
B
15
F
25
I
30
C
5
G
14
D
20
E
21
H
28
J
45
135
控制项目进度：例如135天后的项目进度
阴影部份长条代表进行
135天后完成的工作
*
甘特图的优缺点
优点
容易制作
可决定最早完成时间
提供一个能符合项目的最早开始与完成时间的活动安排
缺点
甘特图只提供一个可能会提前的活动安排
无法辨识项目进度是否落后
未显示活动的先后顺序关系，由甘特图无法明显看出某活动的延迟如何影响另一活动的开始时间.
*
统筹方法（网络计划技术）
基本思想：
从需要管理的任务的总进度着眼，以任务中各项工作所需要的工时为时间因素，按照工作的先后顺序和相互关系作出网络图，以反映任务全貌，实现管理过程的模型化。然后进行时间参数计算，找出计划中的关键工作和关键路线，对任务的各个工作所需的人、财、物通过改善网络计划作出合理安排，得到最优方案并付诸实施。还可对各种评价指标进行定量化分析。
例 : 某新产品投产前全部准备工作。注:紧前工序是指必须在它们完工之后本工序才能开工的那些工序。类似地，紧后工序被定义为只有在本工序完工之后才能开工的那些工序。
E
A
C
D
B
I
J
H
L
F
G
K
10
2
5
1
8
2
3
2
3
6
4
新产品开发项目的网络图
8
统筹方法（网络计划技术）
1.网络图的绘制.
2.网络图的时间参数的计算.
3.网络图的优化.
1) 工期最短的时间优化(平行与交叉工作,
时差的利用).
2) 资源的合理分配.
3) 最低成本日程.
网络图的绘制
i
j
i
事项不占用时间，工作则占用时间。
但虚工作( i , j )不占用时间.
i
j
网络图的构成
网络图画法
(一)、结构
事项：(1, 2)
(二)、画法注意事项：
(1)、一个总起点事项,一个总终点事项 。从左→右
Х
(2)、两事项间不允许有两道或两道以上的工作
Х
(3)、不允许回路
Х
(4)、虚工作的运用（6方面）
② 正确表达工作的前行、后续关系(连结、隔离)
① 解决画法中问题
表达平行作业：一道工作分为几道工作同时进行。
表达交叉作业：两件或两件以上的工作交叉进行。
⑤ 减少交叉，布局合理、美观
⑥ 图的分细与合并
① 解决画法中问题
② 正确表达工作的前行、后续关系(连结、隔离)
例1、现有a, b, c, d四项工作, c在 a, b完工后开始， d在 b完工后开始。绘制网络图。
Х
√
例2、已知A,B,C,D,E关系如下，试画出网络图。
*
例2 网络图如下：
③ 表达平行作业：一道工作分为
几道工作同时进行。
表达交叉作业：两件或两件以上的工作
交叉进行。
⑤ 减少交叉，布局合理、美观
图的分细与合并
举例：
例3 练习：三工序两段交叉
a:挖沟，b:下管，c:回填土
a=a1 +a2 b=b1 +b2 c=c1 +c2
(三)、画图基本步骤
(1)、任务分解，工作明细表。
(2)、绘制网络图。
(3)、工序、事项编号
例如，(i , j)工序 必需满足 i < j
举例: 某新产品投产前全部准备工作。注:紧前工序是指必须在它们完工之后本工序才能开工的那些工序。类似地，紧后工序被定义为只有在本工序完工之后才能开工的那些工序。
1.任务分解。
2.绘制网络图。
E
8
3.节点编号。
什么是关键路线？
1.网络图中需时最长的路叫关键路线.
2.关键路线用双线或粗线画出.
3.关键路线上的工作叫关键工作.
网络图的计算
事项的时间1
1.事项的最早时间:tE( j )
第j个事项的最早可能开始的时间.
tE( i )=与事项 j 相邻的各紧前事项的最早时间
tE(n)=总最早完工期.
事项的时间2
2.事项的最迟时间:tL( i )
在不影响总工期条件下，此事项的最迟必须完成时间.
tL( j )=与事项 i 相邻的各紧后事项的最迟时间.
3.某新产品投产的事项时间计算。
事项的最迟时间: tL ( i )
事项的最早时间:tE( j )
3.某新产品投产的事项时间计算。
事项的最迟时间: tL ( i )
事项的最早时间:tE( j )
工作的时间参数1
工作的最早可能开工时间tES(i,j)与工作的最早可能完工时间tEF(i,j)
工作的时间参数2
工作的最迟必须开工时间tLS(i,j)与工作的最迟必须完工时间tLF(i,j)
总时差R(i,j)与单时差r(i,j)
总时差R(i,j)不影响总工期;
R(i,j)= tLS(i,j)－tES(i,j)
总时差＝0，表示关键工作。
单时差r(i,j)不影响紧后工作的最早可能开工时间.
r(i,j)= tES(j,k)－tEF(i,j)
= tES(j,k)－tES(i,j)-t(i,j)
关键路线(CPM)
确定关键路线的计算方法包括前向分析与后向分析两个程序。
1.图上计算法
例: 某高尔夫球场地下喷水系统的安装工程可分解为12道工序，每道工序所需时间及先后关系如下。
工序代号 工序内容 作业时间(天) 紧前工序
A 勘测球场，成本预算 10 —
B 制订施工计划 8 A
C 向银行贷款 5 A
D 订购烁石 3 B, C
E 除草，开沟 24 B, C
F 用烁石铺平沟底 8 D, E
G 订购管道及接头配件 20 B, C
H 安装管道和接头 10 G
I 将总水管延伸至喷水系统 5 H
J 安装喷水系统 20 F, H
K 平整填沟 10 I, J
L 将喷头与总水管接通 3 I, J
图中节点符号的左半边填写节点的编号，右上方填写紧后作业的最早开始时间ES，而右下方填写紧前作业的最迟完工时间LF。
(1) 前向分析：现工序的最早开工时间等于紧前工序的最早开工时间加上作业时间。如有多个紧前工序存在，选择计算结果中的最大值作为现工序的最早开工时间。
(2) 后向分析：现工序的最迟完工时间等于紧后工序的最迟完工时间减去作业时间。如有多个紧后工序存在，选择计算结果中的最小值作为现工序的最迟完工时间。
(3) 关键路线：机动时间为0的工序被称为关键工序，由关键工序所组成的路线称为关键路线。本例中的关键工序为：A, B, E, F, J, K，其关键路线如下图红色路线所示。
活动前后关系表
练习：根据如下表画出网络图，并计算关键路线
*
在研究与开发项目中，每项任务的完成时间不象工程作业那样规范和标准化，故常常要对任务的完成时间进行估计。常用的估计方法是对每项任务给出三个可能的完成时间，即乐观时间OT，悲观时间PT和最可能时间MT。理论上，该时间分布服从统计学上的 分布，其参数估计的近似计算公式为：
不确定型网络图的时间参数估计
整项工程的完成时间与时间方差可以表示为
根据 与 可算出不同的项目完成时间的概率。
例 下表为高尔夫球场喷水系统安装工程的作业时间提供了更接近实际的日期估计
工序代号 工序内容 OT MT PT te
A 勘测球场，成本预算 8 10 15
B 制订施工计划 4 8 9
C 向银行贷款 4 5 9
D 订购烁石 2 3 5
E 除草，开沟 21 24 30
F 用烁石铺平沟底 4 8 13
G 订购管道及接头配件 18 20 25
H 安装管道和接头 6 10 12
I 将总水管延伸至喷水系统 4 5 6
J 安装喷水系统 17 20 25
K 平整填沟 7 10 15
L 将喷头与总水管接通 2 3 5
所得关键路线的预期长度和时间方差如下表所示：
工序代号 te ES EF LS LF ST CPM
A 0 0 0 √
C 20
B 0 √
D
E 0 √
G
F 0 √
H
I
J 0 √
K 0 √
L
∑(关键路线)
其结论为：该项工程的完工时间是一个以为均值，以为方差的正态分布。
根据 与 可算出不同的项目完成时间的概率。
按预计周期天完成该项目的概率为50%。如果要在75天之内完工，则可将正态变量T标准化，即：
从正态分布表中查得：
网络计划的优化
优化目标：
(1)、工期优化
(2)、工期－成本优化
(3)、资源优化
网络计划的优化方法
1.工期最短的时间优化
① 把串联工作改为平行与交叉工作；
② 时差的利用；
2.有限资源的合理分配；
3.最低成本日程。
有限资源合理分配的原则
1.保证关键工作的资源需求；
2.利用非关键工作的时差错开各工作的使用资源的时间；
3.条件允许,可适当延长时差大的工时,或切断某些非关键工作,以减少资源日需求量。
例：人力资源的合理分配(有限资源下使工期最短问题）。有一个项目，共有7项工作组成。
带日程的网络图及资源动态曲线，如上左图所示。人力需求很不均匀，最多为20人/日，最少为1人/日，这种安排即使在人力资源充足时也是很不经济的。
具体方法：按资源的日需求量所划分的时间段逐步从始点向终点调整。如上右图所示。
右图所示，人力日需求量已满足不超过10人的限制，总工期未受影响。
最低成本日程
直接费用：人力,资源,设备….，与工作时间常假定为线性反比关系.
间接费用：管理费,办公费…，与工作时间常假定为正比关系.
① 直接成本、 间接成本以及总成本的关系
总成本
( i, j )直接成本
举例：最低成本日程的计算
１
2
5
4
6
3
24
30
22
26
24
18
18
直接费用与工时的关系如后表。已知工期每缩短一天，间接费用可省百元。问如何优化工期与成本？
网络图如下：
直接费用与工时的关系表
工作 正常工时 特急工时 成本斜率Cij
时间
(天) 费用
(百元) 时间 费用
1 2
1 3
2 4
3 4
3 5
4 6
5 6 24
30
22
26
24
18
18 50
90
40
100
80
54
64 16
18
18
24
20
18
10 70
102
48
103
90
54
68
1
2
----
最低成本日程的计算过程
１
2
5
4
6
3
24
30
22
26
24
18
18
T=74
关键路线如图。
总直接费用=478百元; 总间接费用=180百元；总费用658百元。如何优化工期与成本？
解:网络图绘制如下：
最低成本日程的计算步骤
1）从关键工作中选出缩短工时所需直接费用最少的方案，并确定该方案可能缩短的天数；
2）通过工作的新工时，重新计算网络计划的关键路线及关键工作。
3）计算由于缩短工时所增加的直接费用。
不断重复上述步骤，直到工期不能再缩短为止。
解:
１
2
5
4
6
3
24
20
22
26
24
18
18
总直接费用=478+10*1=488百元;
间接费用=180-10*=147百元;
总工期64天，总费用635百元，节省23百元.
先缩短１３关键工作的工时: 分析最多缩12天,但考虑到关键路线已转移, 故缩短10天即可. 网络图如下:两条关键路线.
总工期T=64
１)同时缩１３和１２；费用=1+=.
２)同时缩１３和２ ４；费用=1+2=3
３)同时缩３４和１２；费用=+=4.
４)同时缩３４和２４；费用=+2=
５)缩短４ ６；费用.
从费用最小考虑应取２)。
二.现有缩短工时的方案有多少种？
最多缩二天, 网络图如下: 两条关键路线.
１
2
5
4
6
3
24
18
20
26
24
18
18
总直接费用=488+2*3=494百元;
总间接费用=147-2*=百元;
总工期62天，总费用百元，节省百元.
总工期T=62
三. 现有缩短工时的方案有多少种？
１).同时缩１３和１２.费用=
２).同时缩１３和２ ４.费用=
３).同时缩３４和１２.费用=+=4
４)同时缩３４和２４.费用=+2=
５).缩短４ ６.费用.
从费用最小考虑，应取方案４)。
最多缩二天，网络图如下:三条关键路线.
总工期T=60
总直接费用＝ 494+2* ＝ 501百元;
总间接费用＝－2*＝百元；
总工期60天，总费用百元， 增加费用百元。
最低成本日程的计算过程
最低成本日程计算的小结
一. 此时由于工序13; 3 4; 4 6不能缩短工时, 其他工序缩短工时已无意义， 总工期不能再缩短；
二. 从成本最优考虑，应取62天的方案，总费用百元；
三. 单从工期最快考虑，应取60天的方案，总费用百元。
§ 网络计划的实施控制
(1)、执行单位的及时报告
(2)、计划管理部门对报告进行加工分析
(3)、对网络计划及时调整
监控计划的实施
(收集执行情况)
方法计划的再研究
完整的网络计划技术的程序框图
PERT/CPM的作用
1.项目需要多长时间完成.
2.如何安排每项活动的开始时间和完成时间.
3.为了按计划完成整个项目，哪些活动是重要的，需要按时完成.
4.不重要的活动在不影响总工期的情况下，最多可以延误多长时间？
第七章 排队论
特征:
有请求服务的人或物，我们统称它们为“顾客”。
有为顾客服务的人或物，我们叫它们为“服务员”或“服务台”。服务系统是由顾客和服务员组成的。
顾客在随机的时刻，一个（批）一个（批）地来到服务系统。每位顾客需要的服务时间不一定是确定的。服务过程的随机性造成某个阶段顾客排队长，而某些时候服务员又闲聊无事。
研究内容:
性态问题。研究各种排队系统的概率规律性。主要是研究队长分布，等待时间分布和忙期分布等，包括瞬态和稳态两种情形。
最优化问题。最优化又分静态最优和动态最优，前者指最优设计；后者指现有排队系统的最优运营。
排队系统的统计推断，即判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行分析研究。
*
第一节 排 队 系 统
排队系统：是由从顾客到达、排队等待、接受服务一直到最后离开的整个服务过程构成的。
排队等待
顾客到达
接受服务
顾客离开
图 排队系统
*
一、顾客到达
顾客到达的五项内容：
*
顾客到达的五项内容
1、顾客群类型（不同需求类型）
分为许多亚顾客群。例如，医院病人中有的是来体检的，有的是事先预约的，有的是看急诊的。
亚顾客群体的存在，将会影响到排队规则和排队结构。例如，急诊病人比预约病人优先得到治疗，预约病人比普通挂号病人优先得到治疗。
*
2、顾客源总量
有限总量：是指到服务系统接受服务的顾客数量比较少，每一位顾客的到来和离去都会影响到队列的长度，影响到下一次要求服务的概率。
例如：咨询公司、律师事务所、美容店的顾客人数
无限总量：是指到服务系统接受服务的顾客数量非常多，顾客人数的少量增减不会对顾客到达时间的概率分布产生显著影响。
例如，高速公路收费服务
*
3、顾客群规模
含义：是指一起来消费的同一组顾客的数量。一般服从一定的概率分布。
对顾客群规模的预测，将会关系到服务系统服务能力的配置和调整。
例如，餐馆的餐桌配置应当依据顾客群规模的预测。
*
4、耐心程度
在接受服务前一直在等待的顾客被称做耐心顾客。
有些顾客尽管有所抱怨或有一些不耐烦的举动，只要他能够一直等到接受服务，我们从事实上可以认定他为耐心顾客。
不够耐心的顾客分为两类：
望而却步者
中途离队者
与耐心程度有关的因素：
队列长度以及需要等待的时间长度
顾客等待的服务的重要性
等待环境以及企业对顾客的关照
顾客的个性
*
5、顾客到达时间的分布
最常见的，也是研究最多的，是顾客相继到达的时间间隔服从负指数分布，相当于单位时间内到达顾客数（或叫顾客到达率）服从泊松分布（Poisson）。
负指数分布是具有连续型的概率密度函数；
泊松分布是一种离散型的概率函数。
*
负指数分布
公式中，
λ= 一定间隔时间内的平均到达率或单位时间内的平均到达人数；
t = 到达间隔时间；
e = 自然对数的底数（…）；
那么，到达间隔时间的平均值=1/λ；方差= 1/λ2。
此函数表明，随机变量“顾客到达间隔时间”服从参数为1/λ（即到达间隔时间的平均值）的负指数分布。
负指数分布的累加分布函数为：
F（t）=1-e-λt t≥0
累加分布函数给出了到达间隔时间小于等于t的概率。
*
例题
Λ是到达间隔时间平均值的倒数，如果间隔时间均值是分钟， Λ等于1/=（即平均每小时达到25个人）。代入指数分布：
F（t）= t≥0
如果有一个病人已经到达，在未来5分钟内在来一病人的概率是：
F（5）=（5） =
即在未来5分钟内在来一病人的概率是%。
*
1
t
f(t)
t
(a)概率密度函数
(b)累加分布函数
图1 负指数分布
*
泊松分布
公式中，λ= 一定间隔时间的平均到达率或到达人数
t= 观察的时间段的个数（通常取t=1）；
n= 到达次数（0，1，2，3，…）；
e= 自然对数的底数（…）；
那么，平均值 = λt；方差 =λt。
也就是说，随机变量“顾客到达率”或“顾客到达人数”服从参数为λt（当t取1时，该参数为λ，即平均顾客到达人数）的泊松分布。
*
例题
泊松分布给出了t时间内有n位顾客到达的概率.
例如某超市顾客平均到达率为每分钟3个客人（=3）
那么1分钟内到达5个顾客的概率是多少？
*
二、排队规则
排队规则：也就是优先服务规则，它决定了顾客队列中哪些顾客将优先获得服务。
排队规则的制定：它可能是由服务系统明确规定的，也可能是出于行规或人们普遍接受的社会观念。
作用：它将会对服务系统的运作产生重要影响，包括：顾客获得服务的次序、队列秩序、顾客情绪、顾客对服务系统的评价、顾客平均等待时间、服务系统的效率、服务设施的利用率等。
*
*
三、排队结构
排队结构：排队结构类型也称为排队类型或队列类型，它是由如下三个关键指标决定的：
队列数量：顾客队列的数量。
服务台数量：平行作业的服务台数量。
服务阶段数量：服务阶段数量代表了服务工作的步骤，即顾客必须经过几个步骤后才能结束服务任务。
*
常见5种排队结构基本类型
*
常见5种排队结构基本类型
*
常见5种排队结构基本类型
服务台2
服务台3
*
三、排队结构
2、排队结构类型的特点
队列数量对排队类型特点的影响
单队列：较公平，先来者先服务，顾客不必担心排错队
多队列：感觉比较短、比较快，离服务员距离近；当发现自己选择对了队伍，比先来者先获得服务，那么他会获得一种幸运的感觉。
*
服务台数量对排队类型特点的影响
服务台数量不仅影响服务的效率，而且还会影响根据顾客多少而关闭或开启服务台数量的灵活性。
服务阶段数量对排队类型特点的影响
多服务阶段带来的影响在服务线中得到了充分的体现，一个关键问题就是如何保持服务线的平衡运作。
*
第二节 排 队 模 型
*
一、排队系统的标记及分类方法
1957年，英国数学家Kendall提出了一种对排队系统进行标识和分类的方法：A/B/C
A=相继到达的间隔时间的分布；B=服务时间的分布；C=平行服务台的数目。
A和B是两个统计变量，可能存在不同的分布类型。我们使用下面的符号代表不同类型的分布：
M：表示负指数分布；D：定长分布；Ek：k阶爱尔郎分布（Erlang）；G：表示具有均值和方差的一般随机分布，如正态分布、均匀分布或其他经验分布。
如果服务台数目C是1，那么C用1表示；如果服务台数目可以被认定为无穷多，那么C用∞表示；如果服务台数目是多个，那么C用c表示。
例如：M/M/1表示：顾客到达率（或到达数）服从泊松分布，服务时间服从负指数分布，具有单一服务台。
*
排队模型
到达率服从泊松分布
标准型（无
限排队）
有限排队
服务时间服从
指数分布
服务时间服从
一般分布
服务时间服从
指数分布
单服务台的
M/G/1模型
自助服务
M/G/ ∞模型
单服务台的
M/M/1模型）
多服务台的
M/M/c模型
多服务台的
M/M/c模型
单服务台的
M/M/1模型
*
二、衡量排队系统运行效率的工作指标
运行指标
数量指标
平均队长Ls
平均排队长Lq
平均逗留时间Ts
和平均等待时间Tq
平均到达率λ
平均服务率μ
服务强度ρ
系统状态P
有效到达率λe
忙期
*
二、衡量排队系统运行效率的工作指标
平均队长Ls和平均排队长Lq
平均队长Ls是指排队系统中的平均顾客数（包括正接受服务的顾客数和正排队的顾客数）；
平均排队长Lq则是指排队系统中正排队等待的平均顾客数。
*
平均逗留时间Ts和平均等待时间Tq
平均逗留时间Ts是指顾客从进入服务系统一直到离开服务系统的全部时间的平均值（包括排队等待时间和接受服务的时间）；
平均等待时间Tq是指顾客在系统中排队等待时间均值。
备注：以上两对共四个指标对顾客和管理者而言都是非常重要的运行指标。这四个指标的值越小，就说明系统的队列越短，顾客等候时间越短，进而说明系统的运行性能越好。为了计算上述运行指标，还需要用到下面五个常用的数量指标。
*
平均到达率λ
λ是指单位时间内到达服务系统的平均顾客数。
1/λ为相邻两个顾客到达服务系统的间隔时间。
例如，λ=20人/小时，即平均每小时到达20个顾客；那么，相邻两个顾客的平均间隔时间为1/λ=1/20（小时）=3分钟，即平均每3分钟到达1位。
*
平均服务率μ
μ是指单位时间内服务系统服务的顾客数量，也就是单位时间内服务系统输出的顾客数量。
同理，1/μ表示系统服务每个顾客的平均服务时间。
服务强度ρ
服务强度ρ=λ/μ，反映了单个服务台在单位时间内（用于为顾客提供服务）的平均服务时间。
服务强度ρ既反映了服务台（或服务员）的有效利用率，也反映了服务台（或服务员）的繁忙程度。
*
系统状态P
Pn是指系统中的顾客数恰好为n的概率。
P0为系统中的顾客数为0（即系统所有服务台全都空闲）的概率。
有效到达率λe
λe是指单位时间内进入服务系统的平均顾客人数。
这个指标是专门针对有限等待空间排队系统而言的。
备注：实际上，后面这五个指标也在一定程度上能够说明服务系统的运行状况和效率。
M/M/1/∞/∞模型
M/M/1/∞/∞，又称为标准的M/M/1模型，是符合下列条件的排队系统：
输入过程：顾客源是无限的，顾客单个到来，相互独立，顾客相继到达的间隔时间服从参数为λ的负指数分布。
排队规则：单队，且队长没有限制，先到先服务。
服务机构：单服务台，各顾客的服务时间是相互独立的，服从相同的负指数分布。
系统的状态概率：
n≥0
（ρ<1）
这就是标准M/M/1模型的系统状态为n的概率。P0是系统空闲的概率；故服务台忙期的概率P忙为：
即系统忙期的概率P忙就是系统的负荷率（服务强度）P。
由概率论的性质知：
系统的主要运行指标
系统中的平均顾客：
在队列中等待的平均顾客数：
系统中顾客逗留时间的平均值：
在系统中顾客的平均等待时间：
它们之间的关系如下：
例：某市铁路车票预售所，设有一个售票窗口，在一天的服务时间内，平均每小时到达15人，服从泊松分布：一个顾客的平均售票时间为3min，服从负指数分布。现在计算这个排队系统的有关运行指标。
解：这是一个标准M/M/1系统。由题意知：
平均到达率：=15人/h
平均服务率：=20人/h
服务强度：
1）平均队列Ls：
2）平均队列长Lq：
3）顾客平均逗留时间Ws：
4）顾客平均等待时间Wq：
5）顾客不排队的概率P0：
6）顾客不得不排队的概率P=
7）顾客到达后必须等待K个以上顾客的概率：
例如：若k=3，则：
对于本排队模型，求这个概率有更简明公式：
所以，对于P（n>3）有：
系统的繁忙（Busy）与空闲（Idle）
（1）系统处在空闲状态的概率：
系统处在繁忙状态即系统处于忙期的概率：
（2）在繁忙状态条件下
队列中顾客平均数
顾客平均等待时间：
忙期（Pmry Period）：指服务台由空闲状态因顾客到来而开始忙碌到再度空闲为止的时间长度。
和闲期（Idle Period）：闲期指由原有的顾客都被服务完了的时刻开始到下一个顾客到来为止的时间长度。
各忙期的平均长度为：
一个忙期所服务的顾客平均数为：
二、M/M/1/∞/N模型
由于系统中排队等待的顾客数最多为N-1，在某一时刻一顾客到达时，如果系统中已有N个顾客，那么该顾客就被拒绝进行系统。
N=1时，为损失制系统；N→∞时，为等待制系统，即M/M/1/∞/∞情形；1<N<∞时，为混合制系统。这里讨论后一种情形，即N为有限数的情形。
1．系统的状态概率：
ρ≠1
n≤N
2．系统的主要运行指标
ρ≠1（系统中的平均顾客数）
（在队列中等待的平均顾客数）
（3）单位时间内损失顾客的平均数λ·PN，因为损失率为PN。
（4）有效到达率λe，因为平均到达率λ是指系统中顾客数不以N（即系统有空）时的平均到达率，当系统已满即n=N，则到达率为0，故要求出有效到达到λe。
（顾客逗留时间的期望值）
（顾客等待时间的期望值）
它们之间的关系：
例：单人理发馆有六个椅子接待人们排队等待理发，当6个椅子都坐满时，后来到的顾客不进店就离开。顾客平均到达率3人/小时，理发需时平均15分钟。则N=7为系统中最大的顾客数，λ=3人/小时，μ=4人/小时
解：（1）求某顾客一到达就能理发的概率。
这种情形相当于理发馆内没有顾客，所求概率：
（2）求需要等待的顾客数的期望值。
Lq=Ls-(1-P0)=-()=
（3）求有效到达率
λe=μ（1-P0）=4×（）=人/小时
（4）求一顾客在理发馆内逗留的期望时间
Ws=Ls/λe=
（5）在可能到来的顾客中有百分之几不等待离开？
这就是求系统中有7个顾客的概率：
这也是理发馆的损失率。
第八章 决策论
1、目标(objectives)：
目标可以是定量的，如收益、成本、时间、距离、市场占有率等；也可以是定性的，如舒适性、满意性、可持续性等。
2、方案(alternatives)：
指决策者为实现目标可能采取的手段、措施、或可能具有的机会等，它是决策的前提。
3、自然状态(states of nature)：
每种方案的有效性取决于某些未来的环境条件，它们是决策者无法控制的可能发生的情形。如未来的法令法规会影响到汽车燃料的效率，从而影响消费者对汽车燃料的选择。
4、后果(decision outcomes)：
指每一种方案在不同状态下的实施成效，它是目标实现情况的具体标志。
将方案、自然状态和后果等要素归纳在一张表中，便得到下面的决策表，也称为决策矩阵
状态
方案 s1 s2 ┅ sn
a1 c11 c12 ┅ c1n
a2 c21 c22 ┅ c2n
┆ ┆ ┆ ┆ ┆
am cm1 cm2 ┅ cmn
例 某公司拟建新厂，有三种规模可供选择，分别记为小型、中型和大型。每种规模的效益被估计为：小厂在低需求水平时可赢利25万元，一般需求水平时赢利4万元，高需求水平时不赚不赔；中厂在低需求水平时将损失5万元，一般需求水平时可赢利35万元，高需求水平时赢利6万元；大厂在低需求水平时将损失10万元，一般需求水平时可赢利8万元，高需求水平时赢利40万元。本问题中的目标是要选择一个适当的新厂规模以使公司的收益达到最大；可能的行动方案为建小厂、建中厂或建大厂，分别记为a1, a2, a3；自然状态为未来的需求水平，即低需求、一般需求和高需求，分别记为s1, s2, s3；每种方案与状态结合对应的收益或损失便是决策的结果。
状态
方案 S1 S2 S3
A1 25 4 0
A2 －5 35 6
A3 －10 8 40
一、不定型决策分析
1、乐观准则(最大最大法则)
结论：该公司应选择行动方案a3，即建大厂的方案，
可能获得的最大收益为40万元。
状态
方案 s1 s2 s3
a1 25 4 0 25 40
a2 －5 35 6 35
a3 －10 8 40 40
2、悲观准则(最大最小法则)
结论：该公司应选择行动方案a1，即建小厂的方案，
以保证在最不利的情况下也能够维持平衡，不至于
出现亏损。
状态
方案 s1 s2 s3
a1 25 4 0 0 0
a2 －5 35 6 －5
a3 －10 8 40 －10
3、乐观系数准则(赫威兹准则)
结论：该公司应选择行动方案a2，可能获得的
加权平均收益为11万元。
乐观系数用α 表示，0≤α≤1。赫威兹值的
计算公式可表示如下：
状态
方案 s1 s2 s3 H(ai)
α= H(a*)
α=
a1 25 4 0 25 0 10 11
a2 －5 35 6 35 －5 11
a3 －10 8 40 40 －10 10
4、等概率准则
等概率准则的基本思想是：既然不定型决策对
各种状态的发生概率一无所知，就应该对它们
“一视同仁”，即假定各状态发生的概率彼此相等，
这也是“不充分推理”的必然结果。一般地，对于
给定的收益矩阵C = [cij]，如果
则ak 为等概率准则下的最优方案。
结论：该公司应选择行动方案a3，即建大厂的方案，
可能获得的平均收益为38/3万元。
状态
方案 s1 s2 s3 E (ai )
a1 25 4 0 29/3 38/3
a2 －5 35 6 36/3
a3 －10 8 40 38/3
5、机会损失准则(最小机会损失)
当决策者选定决策方案后，往往会因为舍优取劣而后悔，这种后悔实际上是一种机会损失。所选方案的收益值与最优方案的收益值差别越大，后悔的程度就越严重。
结论：该公司应选择行动方案a2(建中厂)，
可能遭受的最大机会损失为34万元。
状态
方案 s1 s2 s3
a1 25
0 4
31 0
40 40 34
a2 －5
30 35
0 6
34 34
a3 －10
35 8
27 40
0 35
二、风险型决策分析
决策树中的方块代表决策结点，从它引出的每一条直线代表一个方案，称为方案枝。在每一方案枝的末端有一个圆圈，叫做状态结点。由状态结点引出的每条直线代表一个自然状态及其发生的概率，故称为概率枝。概率枝的末端标明每一方案在相应状态下的损益值或效用值，作为决策分析的依据
例 在上面讨论的建厂问题中，如果我们知道未来的产品需求状态为低需求水平的概率为；一般需求水平的概率为；高需求水平的概率为。则其决策矩阵为：
状态(概率)
方案 S1( p1= ) S2 ( p2= ) S3 ( p3= )
a1 25 4 0
a2 －5 35 6
a3 －10 8 40
1、期望损益准则
结论：该公司应选择行动方案a2(建中厂)，其
期望收益为万元。
状态(概率) 方案 S1(p1= ) S2 (p2= ) S3 (p3= ) E(ai )
a1 25 4 0
a2 －5 35 6
a3 －10 8 40
2、期望效用准则
由于在某些情况下，货币的期望值不能完全反映
决策者心目中的真正价值，因而有必要改用效用准则
作为决策的基础。为此，我们首先要确定决策者的效
用曲线。
例 在建厂问题中，令u(-10) = 0, u(40) = 1，并采用标准测定技术对决策者提问，从而绘制出下面的效用曲线。
从效用曲线上可求得以下各损益值的效用值：
u(-5)=，u(0)=，u(4)=，u(6)=，
u(8)=，u(25)=，u(35)=。
状态
方案 S1(p1= ) S2 (p2= ) S3 (p3= ) E(ui )
a1 25
4
0
a2 －5
35
6
a3 －10
0 8
40
1
三、序贯型决策分析
例 某虫害防治计划有三种方案可供选择，分别记为a1, a2, a3。第一种方案是一次性措施，可保证100%有效，但需耗资10万元，且由于对环境造成的污染，需另外支付5万元环境治理费；第二种方案分两阶段进行，在第一阶段中只有一种措施，记为a21，所需成本为3万元，但并不能完全根治虫害，实验资料和历史数据表明，害虫大量残留的概率为40%，少量残留的概率为60%，故还需进行第二阶段的防治，有两种不同的防治措施，第一种措施记为 ，可保证100%有效，但成本较高，需耗资10万元。第二种措施记为 ，成本为3万元，其防治效果取决于第一阶段害虫的残留量。
如果第一阶段只有少量害虫残留，则第二阶段防治成功的概率为70%，不成功的概率为30%。如果第一阶段有大量害虫残留，则则第二阶段防治成功的概率只有20%，而不成功的概率高达80%。另一方面，如果第二阶段对虫害防治成功，则农作物的损失可控制在4万元以内，但如果防治不成功，则农作物的损失会增加至12万元。第三种方案也是一次性防治措施，成本为7万元，成功与失败的概率各为50%。如果成功，农作物的损失可降低为万元，否则，农作物损失将高达20万元。试确定成本最低的虫害防治方案。其决策树及相关数据如下图所示。
关于期望值的计算结果表明，该虫害防治计划应采用第二种防治方案为宜。其中，第二阶段的防治方案需视第一阶段的防治后果而定。如果经第一阶段防治后，只有少量病虫害残留，则实施方案 ，否则，实施方案 。总期望成本为万元。
三、贝叶斯决策分析
1、贝叶斯公式与后验概率
例 某工厂的某种产品可由两条自动化生产线中的任意一条生产，其产品不合格率分别为s1=10% 和s2=20%。历史资料表明，这两条生产线被用于生产该产品的概率分布为p(s1)=和p(s2)=。将产品送往有关商店时的包装为每1000件一箱，为了保证货品质量，厂方可以在发运前对产品开箱检验，每件产品的检验费用为元。当然，厂方也可以不加检验直接送货，但根据协议，若商店发现不合格产品时，厂方不仅要同意更换，且需每件赔偿损失费元。问该厂决策者从纯费用的角度考虑应否逐件检验其产品？
方案a1为检验每一个产品，方案a2为不检验任何产品，。
若采用期望值准则进行决策
结论：方案a2为最优方案。
状态(概率)方案 s1 =
( p1 = ) s2 =
( p2 = )
a1 150 150
a2 100 200
由上面可知决策依赖于p1=和p2=。
存在某一概率p(s1)，使得两种方案的期望收益相等，即
解得p(s1)=。此概率被称为“无差异概率”。
为了提高决策的正确性，厂方决定在发货前先从每箱中抽取1件样品进行检验，然后视抽样检验的结果如何再分析行动方案应怎样选择。
设x表示抽样检验的结果为合格， 表示不合格。抽样检验为决策提供了一种补充信息，容易算出
p(x|s1) = ， p( |s1) =
p(x|s2) = ， p( |s2) =
决策者可利用抽样检验提供的补充信息对先验概率作出修正，所得概率称为后验概率。即
利用后验概率重新计算行动方案a1和a2的期望亏损值，其结果为：
结论：经比较可知，如抽检样品为合格，则坚持原有决策，即选择行动方案a2，对产品不作检验而直接送往商店；如抽检样品不合格，则应改变决策而选择行动方案a1，即检验全部产品后再送往商店。
在一般情况下，设风险型决策问题的自然状态有n种不同情形，记为s1, s2, …, sn。用p(sj) 表示自然状态sj发生的先验概率，并用x表示抽样检验或市场调查在状态sj下取得的结果，其条件概率记为p(x|sj)。利用补充信息对先验概率进行修正的计算公式为：
该计算公式便是贝叶斯(Bayes)公式，p(sj|x)称为后验概率，以后验概率为基础进行的决策分析被称为贝叶斯决策分析。
2、信息的价值
例 某投资公司正在考虑新一轮的投资计划，有两种投资方案可供选择，分别记为a1和a2。投资效益取决于未来的宏观经济形势是萧条还是繁荣，分别记为s1和s2。状态的先验概率、决策后果及期望收益总结在下面的决策表中
如果决策者能确知未来发生的状态是什么，则总的期望收益为550+45 = 595万元，该收益被称为“确定状态下的期望值”(EVC)。
状态(概率)
方案 s1 = 萧条
(p1 = ) s2 = 繁荣
(p2 = ) E(ai )
a1 －500 1000 325
a2 100 400 265
先验决策的最大期望收益为325万元。因此，缺乏精确信息的后果是导致了595－325 = 270万元的机会损失。这一损失被称为“完全信息的价值”(EVPI )，表示为：
EVPI = EVC － EVP*
EVP*是先验决策的最大期望值
a1和a2的期望机会损失分别为270万元和330万元。这里270=595－325，330=595－265。一般而言，存在着以下关系：
EVP + EOL = EVC 和 EVPI = EOL*
确定状态下的期望值等于风险状态下的期望值与期望机会损失之和，而完全信息的价值等于最小的期望机会损失。
状态(概率)方案 s1 = 萧条
( p1 = ) s2 = 繁荣
( p2 = ) EOL(ai )
a1 －500
600 1000
0 270
a2 100
0 400
600 330
为了进一步说明样本信息的价值，假定该投资公司拟就未来的宏观经济形势咨询某经济研究所，咨询费用为10万元。以往的研究资料表明，研究所对经济形势的判断也并非完全一致。具体地说，当实际经济形势为萧条时判断失误的比率为14%，而当实际经济形势为繁荣时判断失误的比率为6%。如果用x表示该所对形势的判断为萧条，用 表示判断为繁荣，那么以上的判断结果可以写成条件概率的形式，即
p(x | s1) = ， p( | s1) =
p(x | s2) = ， p( | s2) =
容易算出概率
p(s1, x) = ， p(s1, ) =
p(s2, x) = ， p(s2, ) =
和边际概率
p(x) = ， p( ) =
将以上概率代入贝叶斯公式可得后验概率为：
p(s1 | x) = p(s1, x)/ p(x) = = ，
p(s2 | x) = p(s2, x)/ p(x) = = ；
和
p(s1 | ) = p(s1, )/ p( ) = = ，
p(s2 | ) = p(s2, )/ p( ) = = 。
设a3表示咨询的行动方案，a4表示不咨询的行动方案，则根据后验概率进行的贝叶斯决策可用以下决策树表示。
本例的最优决策为先选择行动方案a3，即向某经济研究所咨询，如该所对未来经济形势的判断为萧条，则选用方案a2，否则选用方案a1，期望收益为万元。这里，以先验概率为基础的期望收益为325万元，故“样本信息的期望价值”(EVSI) 为：
EVSI = |EVS*－EVP*| = －325 = 万元
式中EVS*为后验决策的最佳期望值，EVP*为具有先验决策的最佳期望值。
由样本信息产生的期望净利(expected net gain from sampling - ENGS) 为
ENGS = EVSI－CS = －10 = 万元
式中CS表示抽样成本。与最大样本净利相对应的样本容量被称为最佳样本容量。为了检查样本信息是否充分，特定义样本信息价值与完全信息价值之比为有效比，即
可见该经济研究所提供的判断结果是相当有效的。
投资公司案例
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
