运筹学全套课件

2024/4/10运筹学

2/22第一章绪论运筹学的产生与发展运筹学的分支运筹学在工商管理中的应用关于运筹学的学习3/22题解Operations汉语翻译工作、操作、行动、手术、运算OperationsResearch日本——运用学港台——作业研究中国大陆——运筹学OperationalResearch原来名称，意为军事行动研究英国称为OperationalResearch美国称为OperationResearch4/221.运筹学的产生与发展运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。运筹学产生于第二次世界大战，主要用于解决如何在与德军的对抗中最大限度地杀伤敌人、减少损失。与作战问题相关如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等5/221.运筹学的产生与发展战后二战以后，在经济、管理领域和机关学校及科研单位继续研究，并得到了快速的发展，形成了许多分支，丹捷格提出的求解线性规划问题的单纯形法是运筹学发展史上最重大的进展之一。而计算机的应用极大地推进了运筹学的普及与应用。1952年，Morse和Kimball出版《运筹学方法》1948年英国首先成立运筹学会1952年美国成立运筹学会1959年成立国际运筹学联合会(IFORS)我国于1982年加入IFORS，并于1999年8月组织了第15届大会MIT（1948）：首开“运筹学”课。6/22运筹学的定义为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法——Morse和Kimball运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测，比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策——英国运筹学会Churchman定义：运筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决方法。运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理——中国百科全书现代运筹学涵盖了一切领域的管理与优化问题，称为ManagementScience7/222.运筹学的分支运筹学不仅在军事上，而且在生产、决策、运输、存储等经济管理领域有着广泛的应用。由此产生了许多不同的分支数学规划：线性规划、非线性规划、整数规划、动态规划、目标规划等图论与网路理论随机服务理论：排队论存储理论决策理论对策论系统仿真：随机模拟技术、系统动力学可靠性理论金融工程……8/22决策、定量分析与管理运筹学决策过程（解决问题的过程）（1）认清问题。（2）找出一些可供选择的方案。（3）确定目标或评估方案的标准。（4）评估各个方案：解的检验、灵敏性分析等。（5）选出一个最优的方案：决策。（6）执行此方案：回到实践中。（7）进行后评估：考察问题是否得到圆满解决。（1）（2）（3）形成问题。（4）（5）分析问题：定性分析与定量分析，构成决策。9/223运筹学在工商管理中的应用生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等，追求利润最大化和成本最小化。库存管理：多种物资库存量的管理，某些设备的库存方式、库存量等的确定。运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。10/223运筹学在工商管理中的应用市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等。此外，还有设备维修、更新，项目选择、评价，工程优化设计与管理等。11/223运筹学在工商管理中的应用由国际运筹与管理科学协会（INFORMS）及其下属的管理科学实践学会（CollegeforthePracticeoftheManagementSciences）主持评定的弗兰茨·厄德曼（FranzEdelman）奖久负盛名，该奖是为奖励运筹学在管理中的应用的卓越成就设立的，该奖每年评选一次，在对大量富有竞争力的入围者进行认真的评审后，一般有六位优胜者获奖。这些获奖项目的文章都会在第二年发表在著名刊物Interface新年第一期上。12/22部分获奖应用列表组织应用效果联合航空公司在满足乘客需求的前提下，以最低成本进行订票及机场工作班次安排每年节约成本600万美元Citgo石油公司优化炼油程序及产品供应、配送和营销每年节约成本7000万美元AT＆T优化商业用户的电话销售中心选址每年节约成本4.06亿美元，销售额大幅增加13/22荷玛特发展公司优化商业区和办公楼销售程序每年节约成本4000万美元标准品牌公司控制成品库存（制定最优再订购点和订购量确保安全库存）每年节约成本380万美元施乐公司通过战略调整，缩短维修机器的反应时间和改进维修人员的生产率每生产效率提高50%以上宝洁公司重新设计北美生产和分销系统以降低成本并加快了市场进入速度每年节约成本2亿美元法国国家铁路公司制定最优铁路时刻表并调整铁路日运营量年节约成本1500万美元，年收入大幅增加Delta航空公司优化配置上千个国内航线航班来实现利润最大化每年节约成本1亿美元IBM重组全球供应链，保持最小库存的同时满足客户需求第一年节约成本7.5亿美元14/22运筹学方法使用情况(美1983)15/22运筹学方法在我国使用情况(随机抽样)16/22运筹学的推广应用前景据美劳工局1992年统计预测:

运筹学应用分析人员需求从1990年到2005年的增长百分比预测为73%,增长速度排到各项职业的前三位.结论:运筹学在国内或国外的推广前景是非常广阔的工商企业对运筹学应用和需求是很大的在工商企业推广运筹学方面有大量的工作要做线性规划数学模型1、线性规划模型的概念2、线性规划模型的图解法3、线性规划模型问题的灵敏度分析4、线性规划模型的计算机求解线性规划数学模型所以分别设其变量为xl，x2本决策问题的关键因素是产品I和产品Ⅱ的产量引例：某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：产品Ⅰ产品Ⅱ资源限制设备11300台时原料A21400千克原料B01250千克单位产品获利50元100元线性规划数学模型用xl和x2以函数形式表达工厂所要求的最大利润的目标:单位产品I和Ⅱ的利润maxz=50xl＋100x2，线性规划数学模型再以xl和

x2的不等式关系来表示问题中相应资源的限制条件：台时数的限制：xl+x2≤300原材料A的限量：2xl+x2≤400原材料B的限量：x2≤250线性规划数学模型线性规划数学（表述）模型线性规划数学模型线性规划数学模型maxz＝50xl+100x2满足条件：xl＋

x2≤3002xl+x2≤400

x2≤250

xl≥0，

x2≥0线性规划数学模型的表述形式线性规划数学模型线性规划数学模型线性规划数学模型的基本要素（1）决策变量：用符号来表示可控制的因素，如xj。（2）目标函数：Maxz

或Minf，用来计算和实现决策问题的目标。（3）约束条件：s.t.(subjectto)满足于（一个等式或不等式组），一般是问题的资源限制条件。线性规划数学模型线性规划数学模型线性规划数学模型的特点（1）所有的决策变量

xj都只能取非负值（3）约束条件关系符右端都是不含xj的常量，称为常数项。一般是决策问题的资源限制量，所以常数项也都只能取非负值。（2）目标函数、约束条件关系符左端的关系式都是决策变量

xj的线性函数。线性规划数学模型线性规划数学模型一般线性规划问题的建模过程

（1）理解要解决的问题（2）定义决策变量（3）确定线性目标函数（4）确定约束条件（决策分析中的自然状态）线性规划数学模型线性规划数学模型一个最小化决策问题的建模实例

例2.2

某生产基地每天需从A、B两仓库中提取原材料用于生产，需要提取的原材料有：原材料甲不少于240件，原材料乙不少于80公斤，原材料丙不少于120吨。已知每辆车从A仓库每天能运回甲4件、乙2公斤、丙6吨，运费为每车200元；从B仓库每天能运回甲7件、乙2公斤、丙2吨，运费为每车160元。为满足生产需要，基地每天应发往A、B两仓库多少辆车，并使总的运费为最低。线性规划数学模型线性规划数学模型一个最小化决策问题的建模实例

将上述问题的描述整理成一个表格：

原料甲

(件)

原料乙

(公斤)原料丙

(吨)

运费

(元)仓库A（/车）426200仓库B（/车）722160最少需求量24080120线性规划数学模型线性规划数学模型一个最小化决策问题的建模实例

一、确定决策变量

分别设xl、

x2为该基地每天发往A、B两仓库的货车数量线性规划数学模型线性规划数学模型一个最小化决策问题的建模实例

二、确定目标函数

本问题的目标是使每天总的运费为最低。而每天的总运费为：

Z=200xl+160x2

所以本决策问题的目标函数为：minZ=200xl+160x2

线性规划数学模型线性规划数学模型一个最小化决策问题的建模实例

三、确定约束条件

原料甲

4xl+7x2

≥240

原料乙

2xl+2x2

≥80

原料丙

6xl+2x2

≥120

车辆不能为负

xl、

x2

≥0外在约束简单约束线性规划数学模型线性规划数学模型一个最小化决策问题的建模实例

得线性规划数学模型S.T.

4xl+7x2

≥2402xl+2x2

≥80

6xl+2x2

≥120

xl、

x2

≥0minz=200xl+160x2

线性规划数学模型线性规划数学模型线性规划数学模型的一般形式

max(min)z=clxl+c2x2+…+cnxns.t.al1xl+a12x2+…+a1nxn≤（=，≥）b1a21xl+a22x2+…+a2nxn≤（=，≥）b2………am1xl+am2x2+…+amnxn≤（=，≥）bmxl，x2，…，

xn≥0资源限制

外部环境

内部条件

数学模型的特征，是由问题的自然关系构成的线性规划数学模型线性规划数学模型cj是目标函数的变量系数，也称作价值系数

aij是约束条件的变量系数，也称作资源配置系数

bi是常数项，也称作资源限制量线性规划数学模型中的关键参数：线性规划数学模型的一般形式

线性规划数学模型两个变量（二维）线性规划问题的图解法多个变量（高维）线性规划问题的单纯形法计算机软件求解线性规划数学模型的求解方法

用于解释基本概念仅作为工具用来求解数学模型线性规划数学模型线性规划数学模型的图解法

特征：只包含两个决策变量的线性规划问题优点：简单、直观地显现线性规划问题的基本概念方法：在以x1，x2为坐标轴的直角坐标系里，图上任意一点的坐标代表了决策变量

x1，

x2的一组值，也就代表了一个具体的决策方案。线性规划数学模型用图解法求解例2.1图解法0100200300400x1400300200100x2x2=2502xl+x2=400xl+x2=300同时满足：2x1+x2

400x1+x2

300

x2

250x1

0x2

0的区域——可行域可行域线性规划数学模型图解法线性规划问题的可行域0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)O(0,0)线性规划数学模型图解法线性规划问题的可行域

对于不同的线性规划问题，可行域的几何形状可千变万化，但几何结构都是凸集。线性规划数学模型图解法在可行域中寻找最优解0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)z=0=50x1+100x2线性规划数学模型图解法在可行域中寻找最优解0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)z=10000=50x1+100x2线性规划数学模型图解法在可行域中寻找最优解0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)z=20000=50x1+100x2线性规划数学模型图解法在可行域中寻找最优解0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)z=30000=50x1+100x2线性规划数学模型图解法在可行域中寻找最优解0100200300400x1400300200100x2可行域A(0,250)B(50,250)C(100,200)D(200,0)z=27500=50x1+100x2线性规划数学模型图解法在可行域中找到的最优解B点的坐标为(50，250)，因此最佳决策为x1=50，

x2=250，此时z=27500。最优生产计划方案是生产产品I50单位，生产产品Ⅱ250单位，可得最大利润27500元。线性规划数学模型线性规划数学模型的可能解线性规划数学模型可能的解1、在线性规划问题的解集合中，若约束条件能构成一个封闭的可行域，则可行域的任意点都是该问题的一个可行解，这些可行解中必有最优解。

若最优解是可行域中一个点，则这个解是线性规划的唯一最优解。唯一最优解都必落在可行域的顶点上，可行域的所有顶点称为基本可行解；

线性规划数学模型可能的解

2、若可行域的某一个特殊的边与目标函数平行，则最优解就有可能是这条边上的所有点，所以是无穷多点，而每一个点都是线性规划问题的解，此时线性规划问题就有无穷多解（或最优解不唯一）。线性规划数学模型可能的解

3、对于目标为求最大化的线性规划问题，若约束条件不能构成封闭（或有限）区域的可行域，如沿目标函数值增大的方向无限扩散而没有边界。这时的可行域是无界的，线性规划问题就有无界解。（图2-3）线性规划数学模型可能的解

4、若可行域为空集，或约束条件虽构成封闭区域，但是两个及两个以上的互不相连的区域，那么这些区域中的点都不能同时满足所有的约束要求，因此都不是可行域，则线性规划问题没有可行域，即无可行解（或无解）。线性规划数学模型剩余资源的松弛量线性规划数学模型松弛量

在线性规划的解中，约束条件的实际值与常数项（资源限制量）不一定相等。设备台时：1×50+1×250=300(kg

)300原料A：2×50+1×250=350(kg)400原料B∶0×50+1×250＝250(kg)250

在线性规划中，一个“≤”约束条件中没使用的资源或能力被称之为该约束条件的松弛量。实际值限制量松弛量0500线性规划数学模型松弛变量

设代表松弛量的变量s为松弛变量则：约束条件实际值+松弛变量=资源限制量

在例2.1中引入三个松弛变量sl、s2、s3后，线性规划数学模型描述为：S.T.x1+x2+sl＝3002x1+x2+s2＝400x2+s3＝250x1，x2，sl，s2，s3≥0maxz＝50x1+100x2+0sl+0s2+0s3引入新变量改变了约束关系形式sl＝0s2＝50s3＝0线性规划数学模型

最小化线性规划问题的图解法例2.3

图解目标函数最小化的线性规划问题。minf=11x1+8x2S.T.10x1+2x2≥203x1+3x2≥184x1+9x2≥36

x1，x2≥0线性规划数学模型可行域及基本可行解图解法●●●●B(1,5)x28642x12468A(0,10)C(3.6,2.4)D(9,0)可行域：以x1=0、AB、BC、CD和x2=0形成的半发散区域

基本可行解：

A、B、C、D点为基本可行解。离原点较远的基本可行解为初始基本可行解。

f=11x1+8x2

线性规划数学模型可行域及基本可行解图解法●●●●B(1,5)x28642x12468A(0,10)C(3.6,2.4)D(9,0)f=11x1+8x2

线性规划数学模型可行域及基本可行解图解法●●●●B(1,5)x28642x12468A(0,10)C(3.6,2.4)D(9,0)当目标函数值直线左移至B点时获得问题的最优解：

x1=1,x2=5。最优值：minf=11x1+8x2=51线性规划数学模型多于资源最低限的剩余量线性规划数学模型剩余量

“≥”约束条件中超过资源或能力最低限量的部分称之为剩余量。把例2.2中x1=1，

x2＝5代入约束条件：10×1+2×5=20

=203×1+3×5=18

=184×1+9×5=49

>36剩余量0013实际值最低限线性规划数学模型剩余变量

设代表剩余量的变量s为剩余变量则：约束条件实际值-剩余变量=资源限制量

在例2.3中引入三个松弛变量sl、s2、s3后，线性规划数学模型描述为：S.T.引入新变量

minz＝11x1+8x2+0sl+0s2+0s3；10x1+

2x2-sl＝20，

3x1+3x2-s2＝18，

4x1+9x2-s3＝36，x1，x2，sl，s2，s3≥0改变了约束关系形式sl＝0s2＝0s3＝13线性规划数学模型线性规划数学模型的标准形式maxz=clxl+c2x2+…+cnxn；

S.T.al1xl+a12x2+…+a1nxn=b1a21xl+a22x2+…+a2nxn=b2………am1xl+am2x2+…+amnxn=bmxl，x2，…，

xn≥0线性规划数学模型标准形式线性规划数学模型标准形式的特征1、所有约束条件都是“=”关系

2、决策变量的取值区间0≤xj≤+∞

3、常数项bi都为大于或等于0的数

4、目标函数求最大化（也可求最小化，最大化和最小化可以转换）。线性规划数学模型线性规划问题的灵敏度分析

研究线性规划模型中的系数cj,aij,bi在微小范围内变化时对最优解所产生的影响。线性规划数学模型灵敏度分析目标函数中变量系数cj的取值范围分析cj代表广义的产品价值，称之为价值系统，价值或价格是经营的环境。

cj的灵敏度分析是研究经营环境的变化对最优解的影响。

cj的改变只是改变目标函数直线的斜率，不会改变可行域的形状。线性规划数学模型Cj的灵敏度分析x10100200300x2300200100直线S3(原料A约束)直线z(目标函数)直线S1(原料B约束)直线S2(设备约束)ABDC例2.1的目标函数系数变化线性规划数学模型Cj的灵敏度分析例2.1的目标函数系数变化当时，B仍然是其最优解。－1≤≤0假设单位产品Ⅱ的利润为100元不变，即c2＝100，则有－1≤≤00≤cl≤100假设单位产品I的利润为50元不变，即cl=50，得：－1≤≤050≤c2≤＋∞线性规划数学模型Cj的灵敏度分析例2.1的目标函数系数变化

即当产品I的利润为50元，而产品Ⅱ的利润只要大于等于50元时，顶点B仍为其最优解。最低限当前值最高限C1050100C250100不限

整理如下表：线性规划数学模型灵敏度分析目标函数中变量系数bi的取值范围分析

常数项bi代表的是提供给企业经营的资源限制量。

bi的灵敏度分析是研究资源的变化对最优解的影响。

bi的改变是可行域某一边的平行移动，这种改变极有可能导致最优解和最优值的改变。线性规划数学模型灵敏度分析例2.1中bi的取值范围分析●BC直线Z(目标函数)100200300x2200100300x10ODA原问题中的可行域是OABCD，最优解是B（50，250），最优值是27500。线性规划数学模型灵敏度分析例2.1中bi的取值范围分析

假设例1中的设备台时数增加到310个台时，则例1中的设备台时数的约束条件变为：

xl+x2≤310线性规划数学模型灵敏度分析例2.1中bi的取值范围分析B’●BC直线Z(目标函数)C’100200300x2200100300x10ODA线性规划数学模型灵敏度分析例2.1中bi的取值范围分析B’点的坐标为xl=60,x2=250，获得的最大利润为28000（元）。

则每增加一个设备台时会使企业多获利（28000-27500）/10=50

或每减少一个设备台时会使企业少获利（28000-27500）/10=50线性规划数学模型灵敏度分析对偶价格

在约束条件中的常数项增加一个单位而使最优目标函数值得到改进的数量称之为这个约束条件的对偶价格。例2.1中bi的取值范围分析线性规划数学模型灵敏度分析对偶价格

在例2.1中设备台时约束条件的对偶价格是50。例2.1中bi的取值范围分析线性规划数学模型灵敏度分析对偶价格若原料A增加10kg由约束条件为：2xl+x2≤410100200300x2●BC直线Z(目标函数)C’D’200100300x10ODA最优解仍为B点，对偶价格是0例2.1中bi的取值范围分析线性规划数学模型灵敏度分析对偶价格的进一步解释1、如果对偶价格大于零，则其最优目标函数值得到改进，即求最大化时，常数项的增（减）使最优目标函数值变得更大（更小）；求最小化时，常数项的增（减）使最优目标函数值变得更小（更大）。

线性规划数学模型灵敏度分析对偶价格的进一步解释2、如果对偶价格小于零，则其最优目标函数值变坏，即求最大化时，常数项的增（减）使最优目标函数值变得更小（更大）；求最小化时，常数项的增（减）使最优目标函数值变得更大（更小）。

线性规划数学模型灵敏度分析对偶价格的进一步解释3、如果对偶价格等于零，则常数项的增（减）不会使其最优目标函数值改变。线性规划数学模型灵敏度分析对偶价格的进一步解释4、若约束条件的松驰量或剩余量不为0，则对偶价格必等于零。线性规划数学模型灵敏度分析对偶价格的应用1、资源的价值衡量对偶价格高于该资源的市场价格，表明该资源在本组织有获利能力。就应该购入该资源；对偶价格等于该资源的市场价格，表明该资源在本组织无获利能力；对偶价格低于该资源的市场价格，表明该资源在本组织处于负利状态。在整体利益得到保障的前提下，就可以卖掉该资源。否则用该资源生产的产品越多，企业亏损得越多。线性规划数学模型灵敏度分析对偶价格的应用2、每种资源都有对偶价格不同大小的定量值，因此这个值也就定量地反映资源在企业内部的紧缺程度。

线性规划数学模型灵敏度分析对偶价格的应用3、用数字来确定了企业经营活动中的瓶颈环节（处于木桶中的最短板，其对偶价格才不为0），并且定量地分析了瓶颈环节的紧张程度，以及改进这些瓶颈环节后可给企业带来的收益。

线性规划数学模型灵敏度分析对偶价格的应用4、可更准确地了解各种资源在企业的真实价值(客观地核算成本，体现在与会计核算的不同，会计核算时是按“行规”进行分摊，有人为因素）对偶价格又客观地考虑了资源的机会成本)。线性规划数学模型灵敏度分析

与最优解相关约束条件的常数项改变

bi的取值范围分析可行域结构改变最优解和最优值改变可行域形状改变常数项改变超范围

对偶价格改变关注这个关键的范围值线性规划数学模型灵敏度分析例3.1的图解例2.1中bi的取值范围分析0100200300400x1400300200100x2可行域ACxl+x2=300=b1x2=250=b32xl+x2=400=b2最优解目标函数OBD线性规划数学模型灵敏度分析常数项b1由300减小到260使可行域形状改变，而结构不变，所以对偶价格就不变。例2.1中bi的取值范围分析目标函数最优解0100200300400x1400300200100x2x2=250=b32xl+x2=400=b2DBOCAxl+x2=260=b1可行域线性规划数学模型灵敏度分析常数项继续减小，到可行域结构开始改变时的常数项值，就是这个约束条件常数项的下限值。即本例常数项b1的下限为250。例2.1中bi的取值范围分析400300200100x2最优解0100200300400x1x2=250=b32xl+x2=400=b2DOCA目标函数xl+x2=250=b1B可行域线性规划数学模型灵敏度分析常数项增大，到可行域结构开始改变时的常数项值，就是这个约束条件常数项的上限值。即本例常数项b1的上限为325。例2.1中bi的取值范围分析0100200300400x1400300200100x2可行域Axl+x2=325=b1x2=250=b32xl+x2=400=b2最优解目标函数OBC线性规划数学模型灵敏度分析用同样的方法可得下表：例2.1中bi的取值范围分析最下限当前值最高限b1250300325b2350400不限b3200250300线性规划数学模型灵敏度分析资源配置系数矩阵的变化改变了可行域各边界线段的斜率，即完全且不规则地改变了可行域的形状。资源配置系数矩阵的变化对最优解的影响太繁杂，也不具有共性，可视为完全改变了原有的数学模型，另外求解。约束条件中资源配置系数aij的灵敏度分析线性规划数学模型灵敏度分析

“参数”

---被研究的线性规划数学模型的目标函数变量系数cj或约束条件中的常数项bi。允许增加量---某“参数”在上限范围内的最大增加量（最高限-当前值）。允许减少量

---某“参数”在下限范围内的最大减少量（当前值-最低限）。多个“参数”同时变化的百分之一百法则线性规划数学模型灵敏度分析某类“参数”同时变化的的百分之一百法则：对于所有变化的某一类中的多个“参数”，当其所有实际增加量与允许增加量的百分比和所有实际减少量与允许减少量的百分比之和不超过百分之一百时，最优解（或对偶价格）不变。即：多个“参数”同时变化的百分之一百法则线性规划数学模型灵敏度分析例2.1中，原来每件产品I和产品Ⅱ的利润分别为50和100元，现在每件产品I和产品Ⅱ的利润分别变为70和80元，对其进行灵敏度分析。多个“参数”同时变化的百分之一百法则x1的系数cl的允许增加量为：100－50＝50x2的系数c2的允许减少量也为：100－50＝50百分一百法则：（70-50）/50+（100-80）/50=80%最优解不变，最优值为23500线性规划数学模型灵敏度分析例2.1中，原来每件产品I和产品Ⅱ的利润分别为50和100元，现在每件产品I和产品Ⅱ的利润分别变为70和70元，对其进行灵敏度分析。多个“参数”同时变化的百分之一百法则x1的系数cl的允许增加量为：100－50＝50x2的系数c2的允许减少量也为：100－50＝50百分一百法则：（70-50）/50+（100-70）/50=100%最优解不变，最优值为21000线性规划数学模型灵敏度分析例2.1中，原来每件产品I和产品Ⅱ的利润分别为50和100元，现在每件产品I和产品Ⅱ的利润分别变为70和69元，对其进行灵敏度分析。多个“参数”同时变化的百分之一百法则x1的系数cl的允许增加量为：100－50＝50x2的系数c2的允许减少量也为：100－50＝50百分一百法则：（70-50）/50+（100-69）/50=102%此时最解由B点变为C点，即x1＝100，x2＝200最优值为20800线性规划数学模型灵敏度分析例2.1中，设备台时数从300台时增加为315台时（上限325），而原料A从400kg减少到390kg（下限350），原料B从250kg减少到240kg（下限200）可得：多个“参数”同时变化的百分之一百法则百分一百法则：15/25+10/50+10/50=100%没有超过100%，所以三个约束条件的对偶价格：50，0，50，都不变。但最优值变为：27750

线性规划数学模型灵敏度分析例2.1中，设备台时数从300台时增加为316台时（上限325），而原料A从400kg减少到390kg（下限350），原料B从250kg减少到240kg（下限200）可得：多个“参数”同时变化的百分之一百法则百分一百法则：16/25+10/50+10/50=104%超过了100%

对偶价格分别由原来的50，0，50改变为0，25，75线性规划数学模型灵敏度分析1、当允许增(减)量为无穷大时，则对于任一个对应参数的增(减)量，其允许增(减)的百分比都看成零。这时灵敏度的分析结果就只取决于其它参数的变化。百分之一百法则的四个特点：线性规划数学模型灵敏度分析2、百分之一百法则是判断最优解或对偶价格是否发生变化的充分条件，但不是必要条件。也就是说，当其允许增(减)的百分比之和不超过(小于)100%时，其最优解或对偶价格不变；但是当其允许增(减)的百分比之和超过(大于)100%时，我们并不知道其最优解或对偶价格是否发生变化。

百分之一百法则的四个特点：线性规划数学模型灵敏度分析3、百分之一百法则不包括同步增加或同步减小的情况。百分之一百法则的四个特点：线性规划数学模型灵敏度分析4、百分之一百法则不能应用于目标函数决策变量系数和约束条件中常数项同时变化的情况，在这种情况下，只有重新求解。百分之一百法则的四个特点：线性规划数学模型灵敏度分析

所谓目标函数变量系数的相差值，是指最优解中为0的变量，在其它变量系数保持不变的情况下，使最优解中该变量的值不为0时，相应目标函数变量系数由现有值再改变的量。目标函数中变量系数cj的相差值分析

线性规划数学模型灵敏度分析将本讲的例2.1中,原料B的限制量改变为300kg，其它条件都不变（如下表）,重新决策。目标函数中变量系数cj的相差值分析

产品资源III资源限制设备11300台时原料A21400kg原料B01300kg线性规划数学模型灵敏度分析目标函数中变量系数cj的相差值分析

maxz＝50xl+100x2；

S.T.xl＋

x2≤3002xl+x2≤400

x2≤300

xl≥0，

x2≥0线性规划数学模型：线性规划数学模型灵敏度分析目标函数中变量系数cj的相差值分析

0100200300400x1400300200100x2可行域ACxl+x2=300=b1x2=3002xl+x2=400=b2最优解目标函数OB最优解：

x1=0x2=300线性规划数学模型灵敏度分析目标函数中变量系数cj的相差值分析

由于x1=0，所以在可行域和x2的系数都不变的前提下，要改变当前的解（xl=0,x2=300），只有增加变量xl的系数c1的值，使目标函数直线与xl＋x2=300斜率一样时，才能使得xl真正等于或大于0。即：或得：相差值=50106/27§1人力资源分配的问题

设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：107/27§1人力资源分配的问题

解：设xi

表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6

约束条件：s.t.x1+x6≥60

x1+x2≥70

x2+x3≥60

x3+x4≥50

x4+x5≥20

x5+x6≥30

x1,x2,x3,x4,x5,x6≥0108/27§1人力资源分配的问题例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？109/27§1人力资源分配的问题解：设xi(i=1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6+x7约束条件：s.t.x1+x2+x3+x4+x5≥28x2+x3+x4+x5+x6≥15x3+x4+x5+x6+x7≥24x4+x5+x6+x7+x1≥25x5+x6+x7+x1+x2≥19x6+x7+x1+x2+x3≥31x7+x1+x2+x3+x4≥28x1,x2,x3,x4,x5,x6,x7≥0110/27§2生产计划的问题(课后复习作业)例3．某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？111/27§2生产计划的问题

解：设x1,x2,x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5

分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。求xi的利润：利润=售价-各成本之和产品甲全部自制的利润=23-(3+2+3)=15

产品甲铸造外协，其余自制的利润=23-(5+2+3)=13

产品乙全部自制的利润=18-(5+1+2)=10

产品乙铸造外协，其余自制的利润=18-(6+1+2)=9

产品丙的利润=16-(4+3+2)=7

可得到xi

（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。112/27§2生产计划的问题通过以上分析,可建立如下的数学模型:目标函数：Max15x1+10x2+7x3+13x4+9x5

约束条件：5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0113/27§2生产计划的问题例4．永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过A、B两道工序加工。设有两种规格的设备A1、A2能完成A工序；有三种规格的设备B1、B2、B3能完成B工序。Ⅰ可在A、B的任何规格的设备上加工；Ⅱ可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；Ⅲ只能在A2与B2设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？114/27§2生产计划的问题解：设xijk

表示第i种产品，在第j种工序上的第k种设备上加工的数量。建立如下的数学模型:s.t.5x111+10x211≤6000（设备A1

）

7x112+9x212+12x312≤10000（设备A2

）

6x121+8x221≤4000（设备B1

）

4x122+11x322≤7000（设备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,3115/27§2生产计划的问题目标函数为计算利润最大化，利润的计算公式为：利润=[（销售单价-原料单价）*产品件数]之和-（每台时的设备费用*设备实际使用的总台时数）之和。这样得到目标函数：

Max(1.25-0.25)(x111+x112)+(2-0.35)x221+(2.80-0.5)x312

–

300/6000(5x111+10x211)-321/10000(7x112+9x212+12x312)-250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123).经整理可得：

Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123116/27§3套裁下料问题例5．某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？117/27§3套裁下料问题解：共可设计下列8种下料方案，见下表

设x1～x8分别为上面8种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6+x7+x8

约束条件：s.t.x1+2x2+x4

+x6≥1002x3+2x4+x5+x6+3x7≥1003x1+x2+2x3+3x5+x6+4x8≥100x1,x2,x3,x4,x5,x6,x7,x8≥0118/27计算得出最优下料方案

x1=30;x2=10；

x3=0；

x4=50；

x5=0；x6=x7=x8=0即：按方案1下料30根；按方案2下料10根；按方案4下料50根。只需90根原材料就可制造出100套钢架。注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。§3套裁下料问题119/27§4配料问题

例6．某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？120/27§4配料问题

解：设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个。121/27§4配料问题利润=总收入-总成本=甲乙丙三种产品的销售单价*产品数量-甲乙丙使用的原料单价*原料数量，故有目标函数Max50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

约束条件：从第1个表中有：

x11≥0.5(x11+x12+x13)x12≤0.25(x11+x12+x13)x21≥0.25(x21+x22+x23)x22≤0.5(x21+x22+x23)122/27§4配料问题

从第2个表中，生产甲乙丙的原材料不能超过原材料的供应限额，故有

(x11+x21+x31)≤100(x12+x22+x32)≤100(x13+x23+x33)≤60

通过整理，得到以下模型：123/27§4配料问题目标函数：Maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

约束条件：

s.t.0.5x11-0.5x12-0.5x13≥0（原材料1不少于50%）

-0.25x11+0.75x12-0.25x13≤0（原材料2不超过25%）

0.75x21-0.25x22-0.25x23≥0（原材料1不少于25%）

-0.5x21+0.5x22-0.5x23≤0（原材料2不超过50%）

x11+x21+x31≤100(供应量限制）

x12+x22+x32≤100(供应量限制）

x13+x23+x33≤60(供应量限制）

xij≥0,i=1,2,3;j=1,2,3124/27§4配料问题（略）

标准汽油辛烷数蒸汽压力(g/cm2)库存量(L)1107.57.11×10-2380000293.011.38×10-2265200387.05.69×10-24081004108.028.45×10-2130100例7.汽油混合问题。一种汽油的特性可用两种指标描述，用“辛烷数”来定量描述其点火特性，用“蒸汽压力”来定量描述其挥发性。某炼油厂有1、2、3、4种标准汽油，其特性和库存量列于表4-6中，将这四种标准汽油混合，可得到标号为1，2的两种飞机汽油，这两种汽油的性能指标及产量需求列于表4-7中。问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号汽油满足需求，并使得1号汽油产量最高？飞机汽油辛烷数蒸汽压力(g/cm2)产量需求1不小于91不大于9.96×10-2越多越好2不小于100不大于9.96×10-2不少于250000表4-6表4-7125/27§4配料问题

解：设xij为飞机汽油i中所用标准汽油j的数量(L)。目标函数为飞机汽油1的总产量：库存量约束为：产量约束为飞机汽油2的产量：由物理中的分压定律，可得有关蒸汽压力的约束条件：同样可得有关辛烷数的约束条件为：126/27§4配料问题综上所述，得该问题的数学模型为：127/27§4配料问题

由管理运筹学软件求解得：128/27§5投资问题

例8．某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。据测定每万元每次投资的风险指数如下表：问：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？129/27§5投资问题

解：1）确定决策变量：连续投资问题设xij(i=1～5，j=1～4)表示第i年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量：

Ax11

x21

x31

x41

x51

Bx12

x22

x32

x42Cx33

Dx24130/272）约束条件：第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是x11+x12=200；第二年：B次年末才可收回投资，故第二年年初有资金1.1x11，于是x21+x22+x24=1.1x11；第三年：年初有资金1.1x21+1.25x12，于是x31+x32+x33=1.1x21+1.25x12；第四年：年初有资金1.1x31+1.25x22，于是x41+x42=1.1x31+1.25x22；第五年：年初有资金1.1x41+1.25x32，于是x51=1.1x41+1.25x32；

B、C、D的投资限制：xi2≤30(i=1、2、3、4)，x33≤80，x24≤1003）目标函数及模型：a)Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200

x21+x22+x24=1.1x11；

x31+x32+x33=1.1x21+1.25x12；

x41+x42=1.1x31+1.25x22；

x51=1.1x41+1.25x32；

xi2≤30(i=1、2、3、4)，x33≤80，x24≤100

xij≥0(i=1、2、3、4、5；j=1、2、3、4）§5投资问题解：因为顾客到达间隔时间T服从负指数分布，所以T的