第一讲绪论运筹1回顾

运筹学(OR)主讲：张润东管理学博士管理学院管理科学与工程系

张润东Tel-mail：rung_bj2008@163.com平时成绩＝出勤（30）+考试（70）第一讲

绪论及运筹1回顾

运筹学是高等学校经济管理类专业本科生所必修的一门专业基础课；是分析和解决经营管理领域最优化问题的一门方法论学科各高校《运筹学》开课情况：哈工大：管理学院十门平台课之一，本科60学时，考试100％试卷；硕士70％试卷＋30％案例。重大：本科64学时，硕士45学时，博士30学时。东北大学：本科72学时＋32学时案例分析南航：本科72学时《运筹学》教材《运筹学》

吴祈宗主编，机械工业出版社，北理工，韩润春参考书1、《运筹学》教材编写组，钱颂迪，胡运权清华大学出版社2、《管理科学基础》吴育华，杜纲主编，天津大学出版社多目标决策与综合评估技术吴育华教授主要研究方向博弈理论与风险分析12信息技术在现代管理中的应用3冲突分析与合作理论4经济增长的非参数方法测度5足球经济与足球管理6授课原则须以一桶水的内必容来讲授一杯水内容杯桶原则树干原则演戏原则力求讲清课程内容的树干及主要分支，而不刻意描述树叶内容自编自导自演教师学生知识杯桶原则必须以一桶水的内容来讲授一杯水内容树干原则力求讲清课程内容的树干及主要分支，而不刻意描述树叶内容演戏原则演员导演编剧自编、自导、自演，把每一堂课作为一艺术精品课

程

简

介

何谓“运筹学”？它的英文名称是OperationsResearch,直译为“运作研究”或者作战行动。就是研究在经营管理活动中如何行动，如何以尽可能小的代价，获取尽可能好的结果，即所谓“最优化”问题。课

程

简

介

中国学者把这门学科意译为“运筹学”，就是取自古语“运筹于帷幄之中，决胜于千里之外”，其意为运算筹划，出谋献策，以最佳策略取胜。这就极为恰当地概括了这门学科的精髓。什么是运筹学？多快好省！课

程

简

介

我们讲授这门课程的目的就是要使同学们系统地了解运筹学的基本概念、基本原理、研究方法及其应用，掌握运筹学整体优化的思想和定量分析的优化技术，并能正确应用各类模型分析和解决实际问题。这门课程共讲授40学时。考试要求平时成绩（30%）+期末考试（70%）课

程

简

介

根据这些学时和教材，作了如下安排：

第二章：线性规划与单纯形法重要分支，1947年提出问题解法-单纯形法，计算机技术的发展，可以处理成千上万的约束条件和决策变量，解决实际问题。生产结构的优化、产品组合。

第三章：线性规划的对偶理论与灵敏度分析线性规划的进一步发展，对偶可以用于解决决策变量多于约束条件的线性规划问题，当常数或者系数发生变化时的分析为灵敏度分析。课

程

简

介

第四章：运输问题

特殊的一类线性规划问题，系数矩阵具有特殊结构，表上作业法解决运输问题，是物资调运运费最小问题。以上是运筹学的基本组成部分，是教学的重点内容。

第五章：整数规划一个数学规划问题如果一部分或全部决策变量的值必须取整数，则这样的数学规划称为整数规划问题。一般简称整数规划（IntegerProgramming，简记为IP）。整数规划是近年来发展起来的规划论中的一个分支，它在许多领域中都有重要应用。课

程

简

介

第六章：动态规划解决多阶段决策过程的最优化问题的数学方法。Bellman提出动态规划方法，将多阶段决策问题转化为一系列相互联系的单阶段问题，逐个加以解决。适用于库存问题，资源分配问题，背包问题-商人负重上山。第七章：排队论随即服务系统理论，是研究拥挤等待现象的科学，在研究概率规律基础上，解决排队系统的最优化设计和最优控制问题。性态问题。介绍

课

程

简

介

第八章：图与网络分析图论运筹学一个重要的分支，应用广泛，物理学、控制论、交通运输、工程技术、计算机等领域，解决许多实际问题，交通、通讯网络的架设于分布。最短路问题（邮递员送信问题），网络最大流问题（车辆流、现金流）。介绍网络设计建设工程。管理学应用水平

制造〉建筑〉服务〉政府课

程

简

介

第九章：存储论存储是一个普遍经济现象，是为了解决供应与需求不协调而采取的措施。存储轮研究最合理最经济的存储问题。存储多少最为经济，多长时间补充，补充多少最合理。水库（发电与安全）。介绍几个典型的存储模型。

第十章：决策分析

管理就是用各种有限的资源以更高水平实现目标的决策过程。西蒙认为管理就是决策。决策分析有效应用于投资分析、产品开发、市场营销（广告策划）等，从定量的角度加以研究。从决策量化的内容角度研究确定性、不确定性和风险性决策。介绍。（1）军事：

运筹学作为科学名字出现在20世纪30年代末，当时英美对付德国的空袭，雷达作为防空系统的一部分，从技术上是可行的，但实际运用时不好用。为此，英美等国抽调各方面的专家参与各种战略战术的优化研究工作，获得了显著的成功，大大推进了胜利的进程。战后，从事这些活动的许多专家转到了民用部门。1、运筹学的历史来源：（2）管理：管理既具有科学性又具有艺术性。动作研究切削效率与车速、进刀量等因素的数学关系-优选法用于生产活动分析和计划统筹方法（3）经济：经济理论特别是数理经济学派对运筹学影响巨大。近30年来，经济数学和运筹学互相影响，相互促进，共同发展。运筹学在中国：50年代中期钱学森，许国志引入华罗庚推广优选法、统筹法中国邮递员问题、运输问题

1、规划论：线性规划（是由丹捷格在1947年发表的有关美国空军军事规划时文章中提出的，并提出了求解线性规划问题的单纯行法。单纯行法是运筹学发展史上最重大的进展之一）、非线性规划、整数规划、目标规划、动态规划

2、运筹学的学科体系

2、存储论：存储论中最优批量公式是在本世纪20年代提出的。3、排队论：先驱为丹麦工程师爱尔朗（Erlang）1917年在哥本哈根电话公司研究电话通信系统时，提出排队论的一些著名公式。4、图论与网络5、决策论6、对策论1、明确问题；2、将问题归类、使概念化；3、建立数学模型；4、求解数学模型；5、结果分析与模型检验（反馈）；6、实施（对现实问题的管理和控制）

3、运筹学分析的主要步骤真实系统问题归类模型建立模型求解结果分析与模型检验数据准备明确问题

实施1、明确问题：确定问题是什么？通过系统分析与研究来定义问题，解决什么问题？为此必须做出什么决策？最终要达到什么目标？有哪些不可控因素等。2、将问题归类、使概念化：将问题用哪类管理科学方法解决。方法对号入座。概念化是指将将方法中的要素和术语重新描述具体实际问题，为建立模型作准备。3、建立数学模型：是运筹学的关键步骤，用变量和数学关系形成数学模型。（1）构成要素：结果变量、决策变量和不可控变量。结果变量是一种相依变量，反映了系统达成目标的有效性。决策变量是可控的独立变量，描叙了决策问题中必须做出选择的要素。不可控变量是独立变量，描述了对决策有重要影响因素。（2）数学模型如下图：决策变量不可控变量结果变量数学关系式决策变量X1,X2（产品产量）线性规划模型举例数学关系式有两种：目标函数和约束条件生产结构优化（产品组合）问题，模型结构图如下：数学关系式MaxR目标函数X1+X2≤50约束条件不可控变量P1，P2和50（市场价格和需求）结果变量R=P1X1+P2X2总收入4、求解模型：求解的方法和解的性质各异。求解方法可以分为数值的和分析的。数值的是通过某种模式一步一步地搜寻并不断改进解的过程。如数学规划和动态规划等。分析的是由数学公式一步求出解。存贮轮。最优解和满意解5、结果分析和模型检验：与实际问题是否相符，灵敏度分析等。6、实施：对问题事先管理和控制1生产计划--线性规划以谋求最大的利润或最小的成本，使用运筹学方法从总体上确定适应要求的生产。贮存和劳动力安排等计划。此外还在生产作业计划日程表的编排，合理下料，配料问题。2市场营销

可把运筹学方法用于广告预算和媒介的选择，竞争性的定价、新产品的开发、销售计划的制定等方面。4、运筹学的企业应用

3人事管理可以用运筹学方法对人员的需求和获得情况进行预测，确定适合需要的人员编制。用指派问题对人员合理分配，用层次分析法等方法来确定一个人才评价体系。4财务和会计设计到预测、贷款、成本分析、定价、证券管理、现金管理，使用转变的运筹学方法为：统计分析、数学规划、决策分析等。5库存管理6运输问题等都有广泛的应用。1、科学性它是在科学方法论的指导下通过一系列规范化步骤进行。明确问题观察提出假设设计试验完成试验接受或者决绝假设5、运筹学研究的特点2、实践性运筹学以实际问题为分析对象，通过鉴别问题的性质、系统的目标以及系统内主要变量之间的关系，利用数学方法达到对系统进行最优化的目的。结果要能被实践检验，并被用来指导实际系统的运行。3、系统性运筹学用系统的观点来分析一个组织（或系统），它着眼于整个系统而不是一个局部，通过协调各组成部分之间的关系和利害冲突，使整个系统达到最优状态。

运筹学的应用案例朴素的运筹思想：都江堰水利工程战国时期（大约公元前250年）川西太守李冰父子主持修建。其目标是：利用岷江上游的水资源灌溉川西平原。追求的效益还有防洪与航运。其总体构思是系统思想的杰出运用。

都江堰由三大工程及120多项配套工程组成：

1.“鱼嘴”岷江分水工程：将岷江水有控制地引入内江。

2.“飞沙堰”分洪排沙工程：将泥沙排入外江。

3.“宝瓶口”引水工程：除沙后的江水引入水网干道。

它们巧妙结合，完整而严密，相得益彰。两千多年来，这项工程一直发挥着巨大的效益，是我国最成功的水利工程。三峡工程皇宫修复工程

“一沟三用”

北宋年间，丁谓负责修复火毁的开封皇宫。方案是：先将工程皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；修复工程完成后，实施大沟排水，并将原废墟物回填，修复成原来的大街。丁谓将取材、生产、运输及废墟物的处理用巧妙地解决了。田忌赛马

齐王要与大臣田忌赛马，双方各出上、中、下马各一匹，对局三次，每次胜负1000金。田忌在好友、著名的军事谋略家孙膑的指导下，以以下安排：齐王 上 中 下 田忌 下 上 中 最终净胜一局，赢得1000金。鲍德西（Bawdsey）雷达站的研究（1935年）

1935年，英国科学家R.Watson-Wart发明了雷达。丘吉尔命令在英国东海岸的Bawdsey建立了一个秘密雷达站。当时，德国已拥有一支强大的空军，起飞17分钟即到达英国本土。在如此短的时间内，如何预警和拦截成为一大难题。

1939年由曼彻斯特大学物理学家、英国战斗机司令部顾问、战后获得诺贝尔奖金的P.M.S.Blackett为首，组织了一个小组，代号“Blackett马戏团”。

Team：三名心理学家、两名数学家、两名应用数学家、一名天文物理学家、一名普通物理学家、一名海军军官、一名陆军军官、一名测量员。

研究的问题是：

1、设计将雷达信息传送到指挥系统和武器系统的最佳方式；

2、雷达与武器的最佳配置；

通过他们卓有成效的研究，获得巨大成功。“Blackett马戏团”在秘密报告中首次使用了“OperationalResearch”，即“运筹学”。大西洋反潜战（1942年）

1942年，美国大西洋舰队反潜战官员W.D.BAKER舰长请求成立反潜战运筹组，麻省理工学院的物理学家P.W.MORSE被请来担任计划与监督。1941-1942年，德国潜艇严密封锁了英吉利海峡，企图切断英国的“生命线”。海军几次反封锁，均不成功。

MORSE经过多方实地考察，最后提出了两条重要建议：

1、将反潜攻击由反潜潜艇投掷水雷，改为飞机投掷炸弹。起爆深度由100米左右改为25米左右。即当潜艇刚下潜时攻击效果最佳。(提高效率4-7倍)2、运送物资的船队及护航舰队编队，由小规模多批次，改为加大规模、减少批次，这样，损失率将减少。（25%下降到10%）

丘吉尔采纳了MORSE的建议，最终成功地打破封锁，并重创了德国潜艇。MORSE同时获得英国和美国的最高勋章。阿波罗登月计划（1958-1969年）

阿波罗登月计划的全部任务分别由地面、空间和登月三部分组成，是一项复杂庞大的工程项目，它不仅涉及到火箭技术、电力技术、冶金和化工等多种技术，为把人安全地送上月球，还需要了解宇宙空间的物理环境。

它耗资300亿美元，研制零件有几百万种，共有二万家企业参与，涉及42万人，历时11年之久，为完成这项工作，除了考虑每个部门之间的配合和协调工作外，还要估计各种未知因素可能带来的种种影响，就要求有一个总体规划部门运用一种科学的组织管理方法，综合考虑，统筹安排来解决。2007年10月24日18时05分嫦娥一号卫星中采用了大量新技术，能够实现自主控制、三位定向、自我故障诊断、多路加热器的自主控制、整星能源管理和分配、故障下的应急处理等多项功能。“嫦娥一号”卫星的配套软件达到了23类46套，其中控制卫星动作和姿态的GNC分系统占了9类20套。实现卫星自主化，完备的软件是核心。装有当今世界上运算能力最强的星载计算机，对月球轨道参数的计算提高到1秒种之内。在嫦娥一号卫星上，推进分系统配置了1台大推力的变轨发动机和12台小推力的推力器。12台推力器分成Ａ、Ｂ两分支，每分支6台互为备份。嫦娥一号卫星第3次变轨成功后，由24小时轨道转入48小时轨道，远地点高度由7万多公里提高到12万多公里。“嫦娥一号”卫星的设定了4个科学技术目标。第一，通过CCD相机与激光高度计获取月球表面三维立体影像，描绘月球地质与构造图；第二，通过γ／x射线谱仪分析月球表面的元素及矿物质的含量和分布；第三，通过微波探测仪测量月壤的厚度并评估月壤中氦－3资源；第四，通过高能粒子探测仪探测地－月球空间环境。日本绕月探测卫星“月亮女神”的功能和科学目标与“嫦娥一号”颇为相似，“辉夜姬”的卫星上搭载着14种探测装置，是嫦娥一号装置数两倍多，而且还是一颗主卫星和两颗子卫星的多星系统。长征三号甲火箭，地球同步转移轨道的运载能力为2．65吨，全箭起飞质量241吨；美国阿波罗登月计划所动用的巨无霸——土星5号运载火箭，月球轨道的运载能力为47吨，起飞质量达到了3000吨。我国数十家科研院所和高等学校参与了“嫦娥工程”，已产生4000多项创新。而探月工程取得的各项成果，渗流到国民经济的血管中，流入每个人的日常生活。

“阿波罗”计划其科研成果带动了美国20世纪60－70年代计算机、通信、测控、火箭、激光、材料和医疗等高新技术全面发展，把科技整体水平提高到了一个全新高度。每投入1美元，就会产生4至5美元的国民经济回报。国际上五大智囊团：兰德（RAND）公司（美国）国际应用系统分析研究所（美国）野村研究中心（日本）德国工业企业设备公司（德国）斯坦福咨询公司（美国）朝鲜战争中国是否出兵？美国政府出资要求兰德（RAND）公司做一项紧急研究，并将成果呈报美国总统。该项研究成果的结论极其明晰：中国将派军队入朝参战！与历史的实际完全一致。在其透彻的分析中，还包含了对毛泽东主席的性格及心理学分析，毛泽东性格刚强，面对挑战绝不退缩，因此，可以断定毛泽东会最终做出参战的重大决策。学习建议要求：学习运筹学要把重点放在分析、理解有关的概念、方法、思路。培养分析解题结果及经济评价的能力；培养理论联系实际能力及自学能力。一、线性规划问题

人力资源分配问题例1.11某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：班次时间所需人员16:00——10:0060210:00——14:0070314:00——18:0060418:00——22:0050522:00——2:002062:00——6:0030设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少?解：设xi表示第i班次时开始上班的司机和乘务人员人数。此问题最优解：x1＝50，x2＝20，x3＝50，x4＝0，x5＝20，x6＝10，一共需要司机和乘务员150人。2.生产计划问题

某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1和A2上完成，有B1、B2、B3三种设备可用于完成B工序。已知产品Ⅰ可在A、B任何一种设备上加工；产品Ⅱ可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品Ⅲ只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。设备产品设备有效台时设备加工费（单位小时）ⅠⅡⅢ27910000321B168124000250B247000783B37114000200原料费（每件）0.250.350.5售价（每件）1.252.002.8解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有：目标是利润最大化，即利润的计算公式如下：带入数据整理得到：因此该规划问题的模型为：3.套裁下料问题例：现有一批某种型号的圆钢长8米，需要截取2.5米长的毛坯100根，长1.3米的毛坯200根。问如何才能既满足需要，又能使总的用料最少？解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出4种下料方案以供套裁用。ⅠⅡⅢⅣ2.5m32101.3m0246料头0设按方案Ⅰ、Ⅱ、Ⅲ、Ⅳ下料的原材料根数分别为xj(j=1，2,3,4)，可列出下面的数学模型：例题1——配方问题养海狸鼠饲料中营养要求：VA每天至少700克，VB每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：

饲料VAVBVC价格元/kgIIIIIIIVV3216180.510.220.827495营养要求70030200建模

设抓取饲料Ix1kg;饲料IIx2kg;饲料IIIx3kg饲料IVx4kg饲料Vx5kg目标函数：Z=2x1+7x2+4x3+9x4+5x5最省钱minZ=2x1+7x2+4x3+9x4+5x5约束条件：3x1+2x2+x3+6x4+18x5

≥700营养要求：x1+0.5x2+0.2x3+2x4+0.5x5≥300.5x1+x2+0.2x3+2x4+0.8x5=200非负性要求：x1

≥0,x2≥0,x3≥0,x4≥0,x5≥0

完整的数学模型

minZ=2x1+7x2+4x3+9x4+5x53x1+2x2+x3+6x4+18x5

≥700

x1+0.5x2+0.2x3+2x4+0.5x5≥300.5x1+x2+0.2x3+2x4+0.8x5=200x1

≥0,x2≥0,x3≥0,x4≥0,x5≥0

一、线性规划问题1、掌握模型的数学形式和标准形式：目标函数：约束条件：线性规划的标准型

代数式maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2

…

…

…am1x1+am2x2+…+amnxn=bmxj

≥0j=1,2,…,n标准型的特征

w目标函数极大化w约束条件为等式w右端相为非负值w决策变量非负值MaxZ=X1+X25X2≤156X1+2X2

≤24X1+X2≤5X1≥0，X2≥0①②X1X2③1、唯一最优解2、无穷多最优解（例题）3、无界解4、无可行解

理解线性规划问题解的性质１、若线性规划的可行域存在，则可行域是一个凸集。2、若线性规划问题的最优解存在，则最优解或最优解之一一定是可行域的凸集的某个顶点。3、线性规划问题有最优解，一定存在一个基可行解是最优解。

基：设A是m×n阶约束系数矩阵（m≤n）,秩为m。则A中一定存在m个线性无关的列向量。称可逆矩阵B=（Pj1,Pj2,…,Pjm

）为线性规划（L）的一个基。基解：X=（x1,x2,…xm,0,…,0）T，称X为线性规划问题的基解基可行解：若基本解中XB=B-1b≥0，则称该解为基可行解，

可行基：对应于基可行解的基称为可行基。

非可行解可行解基解基可行解找出一个初始可行解是否最优转移到另一个目标函数（找更大的基本可行解）最优解是否循环直到找出为止，核心是：变量迭代结束4、掌握单纯性表解法：确定初始基可行解若LP的标准型为:MaxZ=c1x1+c2x2+cmxm+cm+1xm+1…+cnxn

A=该标准型称为规范式(以x1,…xm为基变量的规范式)单纯形初始表为:标准型最优性检验换入变量的确定换出变量的确定相同相持(max)(1).当有二个相等的最大数,任取一个(或取下标小的)(取调整量大的)(2).当i有二个相等的最小数,取下标小的一个.若出现循环,则回到该表换另一个最小数作为主行例1用单纯性法求解下列线性规划问题例1的标准型来说明上述计算步骤。

最优解

X*=X(3)=(4,2,0,0,4)T

目标函数的最大值z*=14

5用M法求解一般线性规划问题设线性规划问题的约束条件则分别给每一个约束方程加入人工变量xn+1,…,xn+m，得到假定人工变量在最大目标函数中的系数为(-M)(M为任意大的正数)人工变量经过基的变换将它们从基变量中逐个替换出来。基变量中不再含有非零的人工变量，这表示原问题有解。若在最终表中当所有cj-zj≤0，而在其中还有某个非零人工变量，这表示原问题无可行解。例3：用大M法求解下列问题maxZ=2x1-x2+x3x1+x2-2x3

≤84x1-x2+x3

≤22x1+3x2-x3≥

4x1…x3≥0，

maxZ=2x1-x2+x3+0x4+0x5+0x6-Mx7标准型x1+x2-2x3+x4

=84x1-x2+x3+x5=22x1+3x2-x3-x6

+x7=1x1…x7≥0惩罚项M是很大的正数cj2-11000-McBxBbx1x2x3x4x5x6x70x4811-210008/10X524-110100-Mx7423-100-114/3σj

2+2M-1+3M1-M00-M0√√cj2-11000-McBxBbx1x2x3x4x5x6x70x420/31/30-5/3101/3-1/3200X510/314/302/301-1/31/35/7-1x24/32/31-1/300-1/31/32σj

8/302/300-1/3-M+1/3√cj2-11000-McBxBbx1x2x3x4x5x6x70x445/700-12/71-1/145/14-5/142X15/7101/703/14-1/141/145-1x26/701-3/70-1/7-2/72/7σj

002/70-2/7-1/7-M+1/7√cj2-11000-McBxBbx1x2x3x4x5x6x70x415120015/2-1/21/21X3570103/2-1/21/2-1x2331001/2-1/21/2σj

-2000-10-MX*=（0，3，5，15，0，0，0）Z=-[1*5+（-1）*3]=-2，由于x6的检验数为零，所以存在无穷多个最优解

二、线性规划问题的对偶问题

1、对称形式下对偶问题的引出和意义原问题maxz=cTxAx

≤bx≥0对偶问题minω=bTyATy≥cy≥02、掌握对偶变换规则LP（DP）DP（LP）maxzA

右端项价值系数minwA'

价值系数右端项变量n个≥0≤0无约束n个≥≤=约束条件约束条件m个≤≥

=m个≥0≤0无约束变量例：求出下列线形规划问题的对偶问题maxZ=x1+4x2+3x32x1+3x2-5x3≤2①

3x1-x2+6x3≥1②x1+x2+x3=4③

x1≥0,x2≤0x3无约束minw=2y1+y2

+4y32y1+3y2

+y3≥13y1-y2

+y3≤

4-5y1+6y2

+y3=3y1≥0y2≤0y3无约束minZ=2x1+3x2-5x3+x4

x1+x2-3x3+x4

≥5①

2x1+2x3-x4≤4②

x2+x3+x4=6③

x1≤0,x2，x3≥0

x4无约束练习求其对偶问题Maxw=5y1+4y2

+6y3y1+2y2

y1

+y3-3y1+2y2

+y3y1-y2

+y3≥2≤

3≤

-5=1y1≥0y2≤0y3无约束

3掌握对偶问题的基本性质(1)对称性

对偶问题的对偶是原问题

;(2)弱对偶性若X是原问题的可行解，Y是对偶问题的可行解。则存在CX≤Yb;(3)无界性

若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解;(4)

对偶定理若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。(4)可行解是最优解时的性质

设是原问题的可行解，是对偶问题的可行解，当时，是最优解。(6)原问题检验数与对偶问题解的关系

设原问题是maxz=CX;AX+XS=b;X,XS≥0它的对偶问题是minω=Yb;YA-YS=C;Y,YS≥0则原问题单纯形表的检验数行对应其对偶问题的一个基解。

规划问题的对偶问题的最优解y*i

称为第i个约束条件的影子价格，代表若P的某个约束条件的右端项常数bi增加一个单位时，所引起的目标函数最优值Z*

的改变量。

5了解影子价格的概念影子价格可以分析两类问题

1、增加最大的影子价格的约束条件的资源量

2、资源的市场价格和影子价格的关系，低于-企业应该买进该资源用于扩大生产；高于-则企业的决策者应该将已有资源买掉。

ci

,bj发生变化——对线性规划的影响

6了解灵敏度分析的基本意义

三、运输问题及其数学模型

问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。回本章目录

下面分两种情况来讨论：（1）。即运输问题的总产量等于其总销量，这样的运输问题称为产销平衡的运输问题。（2）。即运输问题的总产量不等于总销量，这样的运输问题称为产销不平衡的运输问题。若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，数学模型为：其中，ai和bj满足：

(3-2)称为产销平衡条件。

该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1以外，其余的都为零。即产量大于销量

对于产大于销问题，可得到下列运输问题的模型：

可增加一个假想的销地，其销量为：某个产地Ai运到这个假想销地Bn+1的物资量xi,n+1，实际上就意味着将这些物资在原产地贮存，其相应的运价，

转化为产销平衡的问题，其数学模型为：

产量小于销量

可增加一个假想的产地，其产量为：因此由假想产地运往某个销地的物资数量，实际上就意味着销地缺少这些物资供应的量，其相应的运费为。上述不平衡问题就转化为平衡的问题，

表上作业法:1.确定初始调运方案的最小元素法；2.检验数的意义、计算方法和格式；3.方案调整的方法；4.把不平衡运输问题转化为标准模型的方法。

确定初始基本可行解的方法：最小元素法，西北角法

解的最优性检验闭回路法和位势法闭回路法

在运输问题中，每个空格对应一个非基变量。因此，我们需要求出每个空格的检验数。当所有的检验数都大于或等于零时该调运方案就是最优方案。

如果对闭回路的方向不加区别，对每一个非基变量（空格）可以找到而且只能找到唯一的一个由基变量（数字格）组成的闭回路。闭合回路法的空格检验数代表：向空格调运单位货物与原运输方案相比引起的运费的变化。检验数的经济意义为空格增运1单位引起总费用的变化数

例1

某公司经销甲产品。它下设三个加工厂。每日的产量分别是：A1为7吨，A2为4吨，A3为9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为3吨，B2为6吨，B3为5吨，B4为6吨。已知从各工厂到各销售点的单位产品的运价为表3-3所示。问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。

解

先作出这问题的产销平衡表和单位运价表，见表3-3，表3-4

表3-3单位运价表

表3-4产销平衡表

这方案的总运费为860元。

850元四动态规划1、理解动态规划的基本概念

状态的选择应使其具有“无后效性”，即过程的历史只能通过当前的状态去影响它未来的发展。或者说过程未来的进程只与当前的状态有关，而与过程的历史无关。状态变量，常用sk表示在第k阶段的某一阶段，Sk表示第k阶段的状态变量集合。方程:状态转移方程概念:阶段变量k﹑状态变量sk﹑决策变量uk;指标:

动态规划本质上是多阶段决策过程;

效益指标函数形式:

和、积无后效性可递推解多阶段决策过程问题，求出

最优策略，即最优决策序列f1(s1)

最优轨线，即执行最优策略时的状态序列

最优目标函数值从k到终点最优策略子策略的最优目标函数值动态规划最优化原理：

“无论过去状态及决策如何，对于面前决策所形成的状态而言，余下的诸决策必构成最优策略。”一个最优策略的子策略是最优的。2、理解动态规划基本方程

例

今有1000台机床，要投放到A、B两个生产部门，计划连续使用5年。已知对A部门投入ua台机器时的年收益是g(ua)=8ua元，机器完好率a=0.7；相应地，B部门为h(ub)=5ub，b=0.9。试建立5年间总收益最大的年度机器分配方案。 解：阶段变量k表示年度

n=5sk：第k年度开始时拥有的完好的机床台数。uk：第k年度开始时对A部门投放的机床数则第k阶段B部门投放的机床数目标函数状态转移方程

基本方程

fk(sk)：由第k年的sk出发，采用最优分配方案到第5个年度结束这段时间内产品的产量。k=5时，k=4时，k=4时，k=3时，k=3时，k=2时，k=2时，k=1时，k=1时，

例2投资问题

现有资金5百万元，可对三个项目进行投资，投资额均为整数（单位为百万元），其中2号项目的投资不得超过3百万元，1号和3号项目的投资均不得超过4百万元，3号项目至少要投资1百万元。每个项目投资5年后，预计可获得的收益见下表，问如何投资可望获得最大的收益。

01234103610122051012---30481115投资额u收益wk项目k

[解]sk——对1,…,(k-1)项目投资后剩余的金额(状态变量)，投资第k个项目前的资金数uk——对k项目的投资额wk(sk,uk)——对k项目投资uk后的收益wk(uk)

fk(sk)——应用剩余资金sk对k,(k+1),…,n项目投资可获得的最大收益状态转移方程为sk+1=sk-uk

为了获得最大收益，必须将5百万元资金全部用于投资，可得下面的递归方程：

f4(s4)=0fk(sk)=max{wk(sk,uk)+fk+1(sk+1)}k=3,2,1当k=3时uk=skf3(1)=4f3(2)=8f3(3)=11f3(4)=15sk+1=sk-uk1号和3号项目的投资均不得超过4百万元，3号项目至少要投资1百万元。

当k=2时,有(注意：项目3至少投资1百万元)s212345D2(sk){0}{0,1}{0,1,2}{0,1,2,3}{1,2,3}

其中2号项目的投资不得超过3百万元，1号和3号项目的投资均不得超过4百万元00

f2(1)=w2(1,0)+f3(1)=4f2(2)=maxw2(2,1)+f3(1)w2(2,0)+f3(2)=max5+40+8=9f2(3)=maxw2(3,2)+f3(1)w2(3,1)+f3(2)w2(3,0)+f3(3)=max10+45+80+11=14f2(4)=maxw2(4,3)+f3(1)w2(4,2)+f3(2)w2(4,1)+f3(3)w2(4,0)+f3(4)=max12+410+85+110+15=18f2(5)=maxw2(5,3)+f3(2)w2(5,2)+f3(3)w2(5,1)+f3(4)=max12+810+115+15=21当k=1时，有s1=5D1(s1)={0,1,2,3,4}f1(5)=maxw1(5,4)+f2(1)w1(5,3)+f2(2)w1(5,2)+f2(3)w1(5,1)+f2(4)w1(5,0)+f2(5)=max12+410+96+143+180+21=21应用顺序跟踪，可知，最优方案有两个：方案Ⅰ——u1*=0,u2*=2,u3*=3方案Ⅱ——u1*=1,u2*=2,u3*=2最大收益为21百万元。五图论与网络分析

图的基本概念

网络分析最小支撑树问题最短路径问题网络最大流问题§1图的基本概念由点和边组成，记作G=(V，E)，其中V=(v1，v2，……，vn)为结点的集合，E=(e1，e2，……，em)为边的集合。点表示研究对象边表示表示研究对象之间的特定关系1.图

定理1所有顶点度数之和等于所有边数的2倍。定理2

在任一图中，奇点的个数必为偶数。

定理：有向图中，所有顶点的入次之和等于所有顶点的出次之和。§2最小支撑树问题本节主要内容：树支撑树最小支撑树

[例]今有煤气站A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。3.5ABCDEFGHIJKS2222225452634531树无圈连通图(A)(B)(C)例判断下面图形哪个是树：一、树的概念与性质树中次为1的点称为树叶，次大于1的点称为分支点。1、设图G=（V，E）是一个树，P（G）≥2，那么图G中至少有两个悬挂点。2、树任删去一边则不连通，故树是使图保持连通且具有最少边数的一种图形。树的性质：一、树的概念与性质v1v2v3v4v5v6

树

的性质：（3）树必连通，但无回路（圈）。（4）图是树的冲要条件是：图不含圈（或者是连通图），有且仅有p-1条边。（5）树中任意两个顶点之间，恰有且仅有一条链（初等链）。（6）n个顶点的树必有n-1条边。（7）树无回路（圈），但不相邻的两个点之间加一条边，恰得到一个回路（圈）。问题：求网络的支撑树，使其权和最小。二、最小支撑树问题55.5v1v2v3v4v53.57.5423算法1（避圈法）：把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1条边为止（n为结点数）。[例]

求上例中的最小支撑树解：3v12v4v545v23.5v3算法2（破圈法）：

在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。55.5v1v2v3v4v53.57.5423§3最短路径问题最短路问题是在一个网络（赋权有向图）中寻找从起点到某个节点之间一条最短的路线。现欲求出υ1至υ6距离最短的路径。最短路问题的Dijstra解法（权为整数）

1.标号意义给点vi标上号的意义：表示起点v1到点vi

的最短路已找到第一个标号表示v1至vi点最短路的路长第二个标号表示v1至vi的最短路中vi之前节点为2.算法基本步骤如下：(1)首先对起点v1标号,即计算v1至v1的最短路，最短路长为零，标号(2)考虑网络中所有这样的弧代表标号点的集合2.算法基本步骤如下：(3)若非空，计算

其中wij为弧(vi,vj)之长度，一未标号顶点vjk(4)对顶点vjk标号，其中

表示v1至vjk最短路已求出，vjk

点由未标号点变成已标号点，重复(2)练习：用标号法解题v5v1v3v6v4v2v7255233575711[0，v1][2，v1][3，v1]其中2=min{0+2,0+5,0+3}其中3=min{0+3，0+5，2+2，2+7}[4，v2][7，v3][8，v5][13，v6]最短距为13；最短路为v1-v2-v3-v5-v6-v7。V3

5V5V24541V612455V4V1V8238V77(0,V1)(1,V1)(2,V1)(6,V2)(5,V2)(9,V4)(7,V4)(12,V6/V7)关键线路：1.V1--V2--V4--V6--V82.V1--V2--V4—V7--V8最短路长：124、最大流问题maxv=v（f）容量约束平衡约束s.t.v2Vsv3v4v5Vt81041755311635312213362可行流6、增广链可行流中fij＝cij

的弧叫做饱和弧；fij＜cij的弧叫做非饱和弧；fij＞0的弧叫做非零流弧；fij＝0的弧叫做零流弧。

若为网络中从vs到vt的一条链，给定向为从vs到vt，上的弧凡与方向相同的称为前向弧，凡与方向相反的称为后向弧，其集合分别用和表示。f

是一个可行流，如果满足：

则称为从vs到vt

的关于f的一条增广链。即中的每一条弧都是非饱和弧即中的每一条弧都是非零流弧13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)是一个增广链显然图中增广链不止一条最大流判定定理：

可行流f*是最大流的充分必要条件是当且仅当不存在从vs到vt

的关于f*的增广链。

7、截集和截集的截量

容量网络D=（V，A，C），vs为始点，vt为终点。如果把V分成两个非空集合

使则所有始点属于S，而终点属于的弧的集合，称为分离vs和vt由S决定的截集。截集中所有弧的容量之和，称为这个截集的截量，记为13(5)9(3)4(1)5(3)6(3)5(2)5(2)5(0)4(2)4(1)9(5)10(1)设，则截集为容量为248.流量与截量的关系任一可行流的流量都不会超过任一截集的截量（∵v(f)=f(V1,V2)-f(V2,V1)≤f(V1,V2)≤C(V1,V2)）v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）最大流最小截定理：网络的最大流量等于最小截量。求最大流方法——标号法理论依据：最大流最小截定理

不存在关于f的增广链

判断：可行流f是最大流：思路：从始点开始标号，寻找是否存在增广链。给vj标号为[θj,vi]，其中θj为调整量，vi为前一节点。网络最大流问题的标号解法步骤：

（1）确定初始可行流（观察法和零流法）

（2）对已知可行流用标号法寻找增值链

（3）沿可增值链调整成更大的可行流

（4）重复标号过程，直至标号终止，确定最大流一.标号步骤：检查所有已标号点与没标号点的关联弧流出弧和流入弧三.标号终止，说明不存在可增价值链，当前即为流为最大流，并得最小截集(4)给终点标上号，说明存在可增值链,反向追踪找出，转二.

例用标号法求下面网络的最大流。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）••••••第一次标号可得两条可增值链如图1.用标号法求可增价值链按调整量大的增值链调整，这里按第二条增值链调整，调后进行第二次标号如图。Vs-V1-V2-V4-Vt，调量=1v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）•••••（5，2）（1，0）（1，0）（2，2）××Vs-V1-V2-V3-Vt，调量=12.调整新流，重复标号，直至标号终止在所得的可增值链上调整流量，=1，调后进行第二次标号如图。第二次标号未进行到底，得最大流如图，最大流量v=5，同时得最小截v4v2vsv1vtv3（2，2）（3，3）（4，3）（3，0）（5，3）••••••（5，2）（1，0）（1，0）（2，2）习题课练习：过纽约ALBANY的北-南高速公路，路况通过能力如下图所示，图中弧上数字单位：千辆/小时。求（1）该路网能承受的北-南向最大流量；（2）若要扩充通过能力，应在那一组路段上扩充，说明原因。2143562366241331进入Albany（北）离开Albany（南）(1)选取一个可行流123546（进入Albany(北)离开Albany(南)2(2)4(1)3(0)1(1)6(5)3(3)2(2)3(3)6(2)1(1)V1—V4—V2—V5—V6，可扩充量为1，调整成新流，继续标号,用标号法得可扩充链123546（进入Albany(北)离开Albany(南)2(2)4(2)3(1)1(1)6(5)3(3)2(2)3(3)6(3)1(0)标号终止，当前流为最大流，最大流量为8截集为：1-2,4-5，4-6，3-6应该在截集弧上扩大流量第11章网络计划网络计划关键路线法（CPM）（criticalpathmethod）工程工期的概率分析—项目评审技术（PERT）（programevaluation＆

reviewtechnique）压缩工期问题工程工序费用分析

学习目的及要求：1、掌握绘制网络图的规律和方法，对一些简单的实际问题，通过对问题的分析，会绘制网络图。2、熟练掌握网络图中各种参数的计算，并会求关键路线；3、掌握最优方案的调整方法。六决策分析第1节决策的分类和过程第2节确定型的决策第3节不确定型的决策第4节风险决策第5节灵敏度分析第6节效用理论在决策中的应用按决策环境分类：确定型：自然环境因素完全确定。不确定型：自然环境因素完全不确定，发生的概率无法确定，主观意向决策。风险型：自然环境因素不是完全确定，发生的概率已知。决策问题的要素构成：(1)决策者，他的任务是进行决策。决策者可以是个人、委员会或某个组织。一般指领导者或领导集体。(2)可供选择的方案(替代方案)、行动或策略。参谋人员提供选择方案。研究对象的属性（客观度量、主观选定）目的和目标。(3)准则是衡量选择方案，包括目的、目标、属性、正确性的标准，在决策时有单一准则和多准则。(4)事件是指不为决策者所控制的客观存在的将发生的状态，即为自然状态。(5)每一事件的发生将会产生某种结果，如获得收益或损失。(6)决策者的价值观，如决策者对货币额或不同风险程度的主观价值观念。确定型的决策第3节不确定型的决策不确定型的决策是指决策者对环境情况一无所知，自然状态（事件）是不确定的。决策者根据自己的主观倾向进行决策，由决策者的主观态度不同可分为四种准则：悲观主义准则乐观主义准则等可能性准则最小机会准则3.1悲观主义(maxmin)决策准则

悲观主义决策准则亦称保守主义决策准则。当决策者面临着各事件的发生概率不清时，决策者考虑可能由于决策错误而造成重大经济损失。由于自己的经济实力比较脆弱，他在处理问题时就较谨慎。他分析各种最坏的可能结果，从中选择最好者，以它对应的策略为决策策略，用符号表示为maxmin决策准则。3.1悲观主义(maxmin)决策准则

在收益矩阵中先从各策略所对应的可能发生的“策略—事件”对的结果中选出最小值，将它们列于表的最右列。再从此列的数值中选出最大者，以它对应的策略为决策者应选的决策策略。3.2乐观主义(maxmax)决策准则持乐观主义(maxmax)决策准则的决策者对待风险的态度与悲观主义者不同，当他面临情况不明的策略问题时，他绝不放弃任何一个可获得最好结果的机会，以争取好中之好的乐观态度来选择他的决策策略。3.2乐观主义(maxmax)决策准则

决策者在分析收益矩阵各策略的“策略—事件”对的结果中选出最大者，记在表的最右列。再从该列数值中选择最大者，以它对应的策略为决策策略。3.3等可能性(Laplace)准则等可能性(Laplace)准则是19世纪数学家Laplace提出的。他认为：当一个人面临着某事件集合，在没有什么确切理由来说明这一事件比那一事件有更多发生机会时，只能认为各事件发生的机会是均等的。即每一事件发生的概率都是1/事件数。3.3等可能性(Laplace)准则

决策者计算各策略的收益期望值，然后在所有这些期望值中选择最大者，以它对应的策略为决策策略，见表15-5。然后按下式决定决策策略。3.4最小机会损失准则最小机会损失决策准则亦称