管理运筹学（第五版）全套课件

管理运筹学北京理工大学韩伯棠教授管理运筹学第一章绪论北京理工大学韩伯棠教授第一章绪论

运筹学（OperationalResearch）运筹学直译为“运作研究”，是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。运筹学管理运筹学管理科学第一章绪论

运筹学的产生和发展我国古代有很多关于运筹学思想方法的典故。齐王赛马丁渭修皇宫沈括运军粮第一章绪论

运筹学的产生和发展

运筹学作为一门新兴的学科是在第二次世界大战期间才出现的。

第一章绪论

运筹学的产生和发展有效保护从美国到英国的商船补给运输线；有效对付德国空军对英伦三岛的大轰炸；

英美成立了“运作研究”（OperationResearch）小组，解决了许多复杂的战略和战术问题。第一章绪论

运筹学的产生和发展

二战以后，运筹学的发展：

1、运筹学方法论快速发展。其里程碑是:1947年由丹捷格（GeorgeDantzig）提出的求解线性规划问题的单纯形法。第一章绪论

运筹学的产生和发展

2、电子计算机技术迅猛发展和广泛应用，使应用运筹学方法解决实际问题可行。决策、定量分析与管理运筹学运筹学的分支运筹学在工商管理中的应用学习管理运筹学必须使用相应的计算机软件，必须注重学以致用的原则本章内容1234§1决策、定量分析与管理运筹学决策过程（解决问题的过程）（1）认清问题。（2）找出一些可供选择的方案。（3）确定目标或评估方案的标准。（4）评估各个方案：解的检验、灵敏性分析等。（5）选出一个最优的方案：决策。（6）执行此方案：回到实践中。（7）进行后评估：考察问题是否得到圆满解决。形成问题分析问题：定性分析与定量分析，构成决策决策、定量分析与管理运筹学运筹学的分支运筹学在工商管理中的应用学习管理运筹学必须使用相应的计算机软件，必须注重学以致用的原则本章内容1234§2运筹学的分支线性规划整数线性规划动态规划图与网络模型存储论排队论排序与统筹方法决策分析对策论预测目标规划此外，还有非线性规划、多目标规划、随机规划、模糊规划等。决策、定量分析与管理运筹学运筹学的分支运筹学在工商管理中的应用学习管理运筹学必须使用相应的计算机软件，必须注重学以致用的原则本章内容1234§3运筹学在工商管理中的应用生产计划库存管理运输问题人事管理市场营销财务和会计……§3运筹学在工商管理中的应用

我国1957年开始成功应用运筹学于工商管理。运输部门“图上作业法”管梅谷“中国邮路问题”华罗庚推广优选法和统筹法§3运筹学在工商管理中的应用

国际运筹与管理科学协会（INFORMS）及其下属的管理科学实践学会（CollegeforthePracticeoftheManagementSciences）颁发弗兰茨·厄德曼（FranzEdelman）奖。奖励运筹学在管理中的应用，该奖每年一次，有六位获奖。§3运筹学在工商管理中的应用自1972年至2017年，FranzEdelman奖项入围项目获利累计超过2570亿美元。组织应用效果卡尔森酒店集团CRHG需求管理和价格优化收入2-4%年增长率，增加1600万美元惠普商业转型中的决策分析2002-2012年电子商务业务翻3番戴尔Dell价值链渠道转型系统解决方案和服务占收入1/3和利润的50%§3运筹学在工商管理中的应用组织应用效果配对捐赠联盟优化匹配拯救了220个生命美国能源局水力发电量优化根据风电和太阳能电源数量调整水力发电量澳大利亚国家宽带网络优化光纤网络设计节约3.75亿美元，模块设计工期从145天变为16天宝钢集团优化算法和决策支持系统（DSSs）产生7681万美元效益，提升16.8%的运营能力，CO2排放量每年下降58.5万吨决策、定量分析与管理运筹学运筹学的分支运筹学在工商管理中的应用学习管理运筹学必须使用相应的计算机软件，必须注重学以致用的原则本章内容1234§4学习管理运筹学必须使用相应的计算机软件，必须注重学以致用的原则一位刚刚毕业的MBA学员，针对公司的设备分销工作，建立了一个存储模型，为公司节省成本35.15万元。§4学习管理运筹学必须使用相应的计算机软件，必须注重学以致用的原则第一，对运筹学的理解停留在理论而非应用层面；

第二，认为运筹学方法太复杂繁琐，不易用，忽视了计算机在运筹学的应用。他的主管经理也学过运筹学却不应用，为什么？值得关注的是：责任在谁？在老师，在教学。§4学习管理运筹学必须使用相应的计算机软件，必须注重学以致用的原则这给我们管理运筹学教学的启示：务必把管理运筹学的教学重点放在应用上，学以致用，充分应用计算机的运筹学软件解决实际问题。§4学习管理运筹学必须使用相应的计算机软件，必须注重学以致用的原则例：有人要从北京去乌鲁木齐。

在一百多年以前，我们应该告诉他如何选购马匹、马车，挑选马夫和保镖如何配备粮草、银两、衣物如何根据天气、地理条件和社会诸因素来确定行车路线和行程

教学务必紧密跟踪现代科技发展。§4学习管理运筹学必须使用相应的计算机软件，必须注重学以致用的原则

但是现在，我们只需要告诉他如何去北京机场，提前多少时间如何订机票着陆后如何领取行李出机场后如何到达目的地没有必要攻读空气动力学、喷气发动机设计和制造、飞行器驾驶手册等。§4学习管理运筹学必须使用相应的计算机软件，必须注重学以致用的原则与管理运筹学相关的最重要的现代科技:计算机技术信息技术软件技术§4学习管理运筹学必须使用相应的计算机软件，必须注重学以致用的原则

《管理运筹学》教材附有运筹学教学软件。谢谢！管理运筹学第二章线性规划图解法北京理工大学韩伯棠教授第二章线性规划的图解法

线性规划是运筹学一个重要分支管理上的典型应用：典型线性规划应用应用场景合理利用线材问题用料最少配料问题获利最大投资问题投资回报最大的方案产品生产计划合理利用人力、物力、财力等使获利最大劳动力安排用最少的劳动力满足需要运输问题总运费最少第二章线性规划的图解法线性规划的组成：

线性规划的组成1目标函数：MIN/MAX2约束条件：限制条件3决策变量：可控因素线性规划问题的提出线性规划的图解法图解法的灵敏度分析本章内容123§1线性规划问题的提出例1.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的限制，如下表所示。问：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？资源产品Ⅰ产品Ⅱ资源限制设备11300台时原料A21400kg原料B01250kg单位产品获利（元）50100

§1线性规划问题的提出问：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？约束条件：

资源产品Ⅰ产品Ⅱ资源限制设备11300台时原料A21400kg原料B01250kg单位产品获利（元）50100

§1线性规划问题的提出建模过程步骤建立线性规划模型1在什么条件下追求什么目标2定义决策变量表，每组代表一个方案

3用决策变量的线性函数形式写出目标函数4必须遵循的约束条件§1线性规划问题的提出

问题的提出图解法图解法的灵敏度分析本章内容123§2图解法两个决策变量的线性问题，可以用图解法求解。

§2图解法每个约束条件都代表一个半平面。

§2图解法

每个约束条件都代表一个半平面。§2图解法把五个限制条件对应的五个半平面合并成一个图，各约束条件的公共部分即为可行域。§2图解法

得到最优解：B:𝒙𝟏=50,𝒙𝟐=250

最优目标值z=27500§2图解法

重要结论

解的情况场景有最优解一定有一个可行域的顶点，对应一个最优点无穷多个最优解若将例一中的目标函数变为z=50x1+50x2，则线段BC上的所有点都代表最优解无可行解可行域为空域，不存在满足约束条件的解无界解可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小§2图解法

重要结论——无界解（无最优解的情况）目标函数：maxz=

x1

+

x2

约束条件：x1

-x2≤1 -3

x1

+2x2≤6

x1

≥0，x2≥0该问题可行域无界，目标函数值无穷大，无界解，即无最优解。§2图解法例2某公司生产某产品，共需A,B两种原料至少350吨（A，B有一定替代性）限制条件具体如下：求目标函数最小化的线性规划问题试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？

资源需求加工时间

（小时/吨）成本

（万元/吨）A≥125吨22B无限制13总资源需求（A+B）需求≥350吨

时间限制（小时）600

§2图解法

得B点坐标（250，100）为最优解建立模型：问题的提出图解法图解法的灵敏度分析本章内容123§3图解法的灵敏度分析

§3图解法的灵敏度分析

§3图解法的灵敏度分析

非标准形式的线性规划问题，通过变换转化为标准形式。标准形式的线性规划的四大特点

线性规划标准形式的四个特点1目标最大化2约束为等式3决策变量均非负4右端项非负§3图解法的灵敏度分析

极小化目标函数的标准化问题

注意：以上两个问题的最优解相同，但最优值相差一个负号，即minf=−maxz§3图解法的灵敏度分析

约束条件不是等式的标准化问题

引入一个非负变量s，令其等于等式左右两边的差值

§3图解法的灵敏度分析

§3图解法的灵敏度分析

§3图解法的灵敏度分析

通过标准化得：§3图解法的灵敏度分析

*变量无符号限制的标准化问题

§3图解法的灵敏度分析

考虑例1的情况，目标函数

z=50x1+100x2

斜线在右图两条红线之间,-1≤（-𝑐1/𝑐2）≤0

最优解不变，仍为B.§3图解法的灵敏度分析

等值线斜率在-1≤（-𝑐1/𝑐2）≤0范围内则最优值不变。

§3图解法的灵敏度分析

§3图解法的灵敏度分析

§3图解法的灵敏度分析在一定范围内，当约束条件中常数项增加1个单位时，（1）对偶价格大于0，则其最优目标函数值得到改善，求Max则函数值增大，求min则函数值变小；（2）对偶价格小于0，则其最优目标函数值受到影响（变坏），求Max则函数值变小，求min则函数值增大；（3）对偶价格等于0，则其最优目标函数值不变。对偶价格谢谢！管理运筹学第三章线性规划问题的计算机求解北京理工大学韩伯棠教授第三章线性规划问题的计算机求解随书软件为“管理运筹学”3.5

版（Windows版），是“管理运筹学”3.0版（Windows版）的升级版。它包括15个子模块。“管理运筹学”软件的操作方法“管理运筹学”软件的输出分析本章内容12§1“管理运筹学”软件的操作方法第一步：双击“管理运筹学v3.5”在桌面上的快捷方式下面演示如何用“管理运筹学”软件包来解决第二章例一的线性规划问题§1“管理运筹学”软件的操作方法

§1“管理运筹学”软件的操作方法第二步：在主菜单中选择线性规划模型§1“管理运筹学”软件的操作方法第三步：在点击“新建”按钮以后，输入变量个数，约束条件个数，目标函数选择max(min)，点击确定§1“管理运筹学”软件的操作方法第四步：输入约束条件个数，目标函数及约束条件各系数和b值，并选择好变量的正负号§1“管理运筹学”软件的操作方法第五步：点击解决§1“管理运筹学”软件的操作方法第六步：点击开始§1“管理运筹学”软件的操作方法第七步：点击下一步§1“管理运筹学”软件的操作方法第八步：点击下一步§1“管理运筹学”软件的操作方法第九步：关闭计算过程“管理运筹学”软件的输出分析“管理运筹学”软件的操作方法本章内容21§2“管理运筹学”软件的输出信息分析分析软件输出的信息

解释变量相差值：

为了使决策变量为正值，相应的决策变量的目标系数需要改进的数量约束松弛（剩余变量）：资源剩余量（超过量）。如果为零,表示与之相对应的资源正好全部用完。对偶价格：对应的资源每增加一个单位，最优值将变化多少个单位目标函数系数范围最优解不变的情况下，目标函数的决策变量系数的变化范围

当前值：当前的目标函数的系数取值§2“管理运筹学”软件的输出信息分析分析软件输出的信息灵敏度分析都是在只有一个系数变化的基础上得出的

解释常数项范围上限值和下限值：当约束条件的右端常量在此范围内变化时，与其对应的约束条件的对偶价格不变

当前值：约束条件的右端常量现在的取值。§2“管理运筹学”软件的输出信息分析百分之一百法则：对于所有变化的目标函数决策变量系数（约束条件右端常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过100%时，最优解不变（对偶价格不变）当有多个系数变化，怎样进行灵敏度分析？§2“管理运筹学”软件的输出信息分析

目标函数系数的百分之一百法则

约束条件中常数项的百分之一百法则§2“管理运筹学”软件的输出信息分析在使用百分之一百法则进行灵敏度分析时，要注意以下几方面注意事项

1当允许增加量（允许减少量）为无穷大时，

则对任意增加量（减少量），其允许增加（减少）百分比均看作零2百分之一百法则是充分条件，但非必要条件；也就是说超过100%最优解或对偶价格并不一定变化。3百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化的情况。

这种情况下，只能重新求解§2“管理运筹学”软件的输出信息分析用“管理运筹学”软件来分析第二章的例2

当购进原料A250t，原料B100t时购进成本最低为800万元。§2“管理运筹学”软件的输出信息分析

解释松弛/剩余变量约束条件2的值为125，表示对原料A多了125，即对A的剩余变量值为125，原料A用了250。对偶价格约束条件1的对偶价格为-4，表示如果采购量再增加1吨，那么总的成本要增加4万元。由800万元增加到804万元。约束条件3的对偶价格为1万元，即如果把加工时数从600小时增加到601小时，则总成本将得到改进，由800万元减少到799万元常数项范围约束条件1：

常数项在300到475范围内变化，且其他约束条件不变时，约束条件1的对偶价格不变，仍为-4

约束条件2：

常数项在负无穷到250范围内变化，且其他约束条件的常数项不变时，约束条件2的对偶价格不变，仍为0

约束条件3：

常数项在475到700范围内变化，且其他约束条件的常数项不变时，约束条件3的对偶价格不变，仍为1。§2“管理运筹学”软件的输出信息分析影子价格：当约束条件中的常数项增加一个单位时，最优目标函数值增加的数量影子价格与对偶价格条件影子价格与对偶价格的关系求目标函数max当约束条件中的常数项增加一个单位时，目标函数值增加的量就为改进的数量，此时影子价格即为对偶价格求目标函数min在求目标函数最小值时，改进的数量即减少的数量，此时影子价格为负的对偶价格§2“管理运筹学”软件的输出信息分析

管理运筹学”软件可以解决含有100个变量50个约束方程的线性规划问题。如果想要解决更大的线性规划问题，可以使用由芝加哥大学的

L.E.Schrage

开发的LINDO计算机软件包的PC机版本

LINDO/PC。注意：谢谢！管理运筹学第四章线性规划在工商

管理中的应用北京理工大学韩伯棠教授第四章线性规划在工商管理中的应用在对线性规划的求解及灵敏度分析的基本概念、基本原理有所了解之后，我们来研究线性规划在工商管理中的应用，解决工商管理中的实际问题。

人力资源分配的问题生产计划的问题套裁下料问题配料问题本章内容1234投资问题5人力资源分配的问题生产计划的问题套裁下料问题配料问题本章内容1234投资问题5

例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：

§1人力资源分配的问题设司机和乘务人员分别在各时间段开始时上班，并连续工作八小时，问该公交线路应怎样安排司机和乘务人员，既能满足工作需要，又使配备司机和乘务人员的人数最少?班次时间所需人数16:00--10:0060210:00--14:0070314:00--18:0060418:00--22:0050522:00--2:002062:00--6:0030

x1+x6≥60（班次1所需人数）

§1人力资源分配的问题设xi

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

x1+x2≥70

x2+x3≥60

x3+x4≥50x4+x5≥20

x5+x6≥30

x1,x2,x3,x4,x5,x6≥0解：目标函数：约束条件：§1人力资源分配的问题

例2．百货商场对售货员的需求如下表。要求售货员每周工作五天，连续休息两天。问：应该如何安排售货员，满足工作需要，同时使配备的售货员人数最少？时间所需售货员人数星期一15星期二24星期三25星期四19星期五31星期六28星期日28§1人力资源分配的问题解：设xi(i=1,2,…,7)表示星期i开始休息的人数,建立如下的数学模型：目标函数：约束条件：Minx1+x2+x3+x4+x5+x6+x7

x2+x3+x4+x5+x6≥15（星期一所需售货员人数）x3+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≥28x1,x2,x3,x4,x5,x6,x7≥0§1人力资源分配的问题实际中，服务行业企业一周内对人力资源的需求往往像例2所描述的方式变化，而每天各时间段的需求又像例1所描述的那样变化。我们只要用例1的方法，分别求出周一、周二······周六、周日每天的人员需求，再用例2的方法，即可求出该公司的最小编制。

注意：人力资源分配的问题生产计划的问题套裁下料问题配料问题本章内容134投资问题52§2生产计划的问题例3．公司面临外包协作、自行生产的问题。甲、乙、丙产品都需要经过铸造、机加工和装配三道工序。铸造工序中甲、乙可外包，亦可自产，丙必须自产，其余工序必须本厂完成。

问：为获取最大利润，三种产品各生产多少件？甲、乙的铸件有多少由本公司铸造？有多少由外包协作？甲乙丙资源限制每件铸造工时/小时51078000每件机械加工工时/小时64812000每件装配工时/小时32210000自行生产铸件每件成本/元354外包协作铸件每件成本/元56--机械加工每件成本/元213装配每件成本/元322每件产品售价/元231816§2生产计划的问题

设x1,x2,x3分别为三道工序都由本公司加工的甲、乙、

丙三种产品的件数，x4

,x5

分别为由外协铸造再由本公

司加工和装配的甲、乙两种产品的件数。

解：可得到xi(i=1,2,3,4,5)的利润分别为15、10、7、13、9元。求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；§2生产计划的问题通过以上分析,可建立如下的数学模型:目标函数：约束条件：Max15x1+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§2生产计划的问题例4．机械厂生产Ⅰ、Ⅱ、Ⅲ产品，均要经过A、B两道工序。两种规格的设备A1、A2能完成A工序；三种规格的设备B1、B2、B3能完成B工序。Ⅰ可在A、B的任何规格的设备上加工；Ⅱ可在任意规格的A上加工，B工序只能在B1上加工；Ⅲ只能在A2与B2上加工。问：为获得最大利润，应如何制定最优的产品加工方案？设备产品单件工时设备的有效台时满负荷时的设备费用IIIIII2791210000321B1684000250B24117000783B374000200原料（元/件）0.250.350.50售价（元/件）1.252.002.80§2生产计划的问题解：设xijk表示产品i在工序j（工序A用1表示，工序B用2表示）的设备k上加工的数量，建立如下的数学模型: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工序加工

的数量相等）s.t.x312-x322=0（Ⅲ产品在A、B工序加工

的数量相等）xijk≥0,i=1,2,3;j=1,2;k=1,2,3§2生产计划的问题利润=[（销售单价-原料单价）*产品件数]之和-（每台时的设

备费用*设备实际使用的总台时数）之和.目标函数为计算利润最大化，利润的计算公式为：目标函数：整理得：Max(1.25-0.25)(x111+x112)+(2-0.35)(x211+x212)+(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.4474x122-1.2304x322-0.35x123§2生产计划的问题合并同类项，自行完成；移项问题；变量下标的转换问题；

把变量设定中两维和三维下标将为一维；

例：xijk：x111x1x112x2。。。

需要注意的问题：人力资源分配的问题生产计划的问题套裁下料问题配料问题本章内容1234投资问题5§3套裁下料问题104

解：列出所有可能下料方案：例5．工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？方案1方案2方案3方案4方案5方案6方案7方案82.9m120101002.1m002211301.5m31203104合计/m7.47.37.27.16.66.56.36料头/m00.10.20.30.80.91.11.4§3套裁下料问题设按上述方案下料的原材料根数分别为x1,x2,x3,x4,x5,x6,x7,x8建立如下的数学模型：目标函数：约束条件：Minx1+x2+x3+x4+x5+x6+x7+x8

x1+2x2+x4+x6≥100（2.9m圆钢）2x3+2x4+x5+x6+3x7≥1003x1+x2+2x3+3x5+x6+4x8≥100x1,x2,x3,x4,x5,x6,x7,x8≥0§3套裁下料问题用“管理运筹学”软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。

即x1=30;x2=10；x3=0；x4=50；x5=x6=x7=x8=0；只需90根原材料就可制造出100套钢架。注意：建立此类型数学模型时，约束条件用大于等于号优于用等于号。§3套裁下料问题

面裁问题如何解决？

体裁问题又如何解决？§3套裁下料问题零件1x1：2件

零件2x2：2件

零件3x3：3件

零件4x4：1件

零件5x5：3件

零件6x6：2件

零件7x7：2件

零件8x8：1件

人力资源分配的问题生产计划的问题套裁下料问题配料问题本章内容1234投资问题5§4配料问题例6．工厂要用三种原料1、2、3混合调配出不同规格的产品甲、乙、丙。问：该厂应如何安排生产，使利润最大？产品名称规格要求单价（元/kg）甲原材料1不少于50%，原材料2不超过25%50乙原材料1不少于25%，原材料2不超过50%35丙不限25原材料名称每天最多供应量单价（元/kg）11006521002536035§4配料问题解：设xij

表示第i种（我们分别用1,2,3表示产品甲、乙、丙）产品中原料j的含量。建立数学模型时，要考虑：甲产品的数量为：x11+x12+x13；乙产品的数量为：x21+x22+x23；丙产品的数量为：x31+x32+x33；原料1的总需求量为：x11+x21+x31；原料2的总需求量为：x12+x22+x32；原料3的总需求量为：x13+x23+x33；目标函数：利润最大，利润=收入-原料支出约束条件：规格要求4个；供应量限制3个。§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)（甲含原材料1的比例）x12≤0.25(x11+x12+x13)x21≥0.25(x21+x22+x23)x22≤0.5(x21+x22+x23)§4配料问题

从第2个表中，

生产甲乙丙的原材料不能超过原材料的供应限额，故有：(x11+x21+x31)≤100（原材料1的供应限额）(x12+x22+x32)≤100(x13+x23+x33)≤60§4配料问题通过整理，得到以下模型：目标函数：约束条件：Maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

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,3§4配料问题例7.汽油混合问题。汽油的特性用“辛烷数”描述点火特性，用“蒸汽压力”描述挥发性。炼油厂有1、2、3、4种标准汽油，性能与库存信息如表1.将这四种混合，可得到标号为1，2的两种飞机汽油，性能指标如表2。问：如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号汽油满足需求，并使得1号汽油产量最高？标准汽油辛烷数蒸汽压力(g/cm2)库存量(L)1107.57.11×10-2380000293.011.38×10-2265200387.05.69×10-24081004108.028.45×10-2130100飞机汽油辛烷数蒸汽压力(g/cm2)产量需求1不小于91不大于9.96×10-2越多越好2不小于100不大于9.96×10-2不少于250000表1§4配料问题表2§4配料问题库存量和产量约束为：解：设xij为飞机汽油i中所用标准汽油j的数量(L)。目标函数为飞机汽油1的总产量越多越好由物理中的分压定律，可得有关蒸汽压力的约束条件：

辛烷数的约束条件为：§4配料问题辛烷数和蒸汽压力的约束条件为：§4配料问题

综上所述，得该问题的数学模型为：§4配料问题

由管理运筹学软件求解得：人力资源分配的问题生产计划的问题套裁下料问题配料问题本章内容1234投资问题5§5投资问题

例8．现有资金200万元，今后五年内考虑给以下的项目投资。项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元。问：a）应如何确定这些项目的每年投资额，使得第五年

年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年

年末拥有资金的本利在330万元的基础上使得其

投资总的风险系数为最小？据测定每万元每次投资的风险指数如表：§5投资问题项目风险指数（次/万元）A1B3C4D5.5§5投资问题

设xij

表示第i年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量：

Ax11

x21

x31

x41

x51

Bx12

x22

x32

x42

C

x33

D

x24解：1）确定决策变量：连续投资问题2）约束条件：第一年：A项目当年末可收回投资，故第一年年初应把全部资金投出去，于是x11+x12=200；第二年：B项目次年末才可收回投资，故第二年年初有资金1.1x11，于是x21+x22+x24=1.1x11；B、C、D的投资限制：xi2≤30(i=1、2、3、4)x33≤80x24≤100

第四年：同上分析，年初有资金1.1x31+1.25x22，于是x41+x42=1.1x31+1.25x22；§5投资问题第五年：同上分析，年初有资金1.1x41+1.25x32，于是x51=1.1x41+1.25x32；第三年：第三年年初的资金是从项目A第二年投资和项目B第一年投资所回收的本息总和1.1x21+1.25x12，于是x31+x32+x33=1.1x21+1.25x12；§5投资问题b)所设变量与问题a相同，目标函数为风险最小，有

Minf=x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24

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）3）目标函数及模型：§5投资问题Minf=(x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24s.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

1.1x51+1.25x42+1.4x33+1.55x24≥330

xij≥0(i=1、2、3、4、5；j=1、2、3、4）即在问题a的约束条件中加上“第五年末拥有资金本利在330万元”的条件，得模型：谢谢！管理运筹学第五章单纯形法北京理工大学韩伯棠教授130单纯形法的基本思路和原理单纯形法的表格形式求目标函数值最小的线性规划问题的单纯形表解法几种特殊情况本章内容1234131单纯形法的基本思路和原理单纯形法的表格形式求目标函数值最小的线性规划问题的单纯形表解法几种特殊情况本章内容1234132§1单纯形法的基本思路和原理单纯形法的基本思路：

是否选取可行域某顶点(更优顶点)是否为最优解输出最优解终止是否无最优解是否133§1单纯形法的基本思路和原理一、找出一个初始基本可行解下面通过第二章例1的求解来介绍单纯形法。在加上松弛变量之后得到此线性规划的标准形式。 目标函数：max50x1+100x2 约束条件：x1+x2+s1=300，

2x1+x2+s2=400， x2+s3=250， xi≥0（i=1,2），sj≥0（j=1,2,3）。

134§1单纯形法的基本思路和原理该线性规划问题约束方程的系数矩阵为：

其中

pj为系数矩阵A第j列的向量.A的秩为3,方程组变量个数大于A的秩，从方程组的无数组解中找一个初始可行解。

135§1单纯形法的基本思路和原理基Am×n

是约束条件系数矩阵，秩为m。若Bm×m

是A的子阵，且可逆，称B为一个基。如何找初始基本可行解？基本概念

基向量基B中的一列即称为一个基向量。非基向量在A中除了基B之外的一列称之为基B的非基向量。基变量与基向量

pi

相应的变量xi

叫基变量，基变量有m个。非基变量与非基向量

pj

相应的变量xj叫非基变量，非基变量有n‒m个。136§1单纯形法的基本思路和原理

此例题找到A的一个基B3（可逆子阵）：令非基变量x1=0,s2=0,约束方程变为基变量的方程。若在约束方程组系数矩阵中找到一个基，令其非基变量为零，再求解该m元线性方程组可得到唯一解，该解称之为线性规划的基本解。

137§1单纯形法的基本思路和原理基变量的约束方程:

x2+s1=300， x2

=400， x2+s3=250，

求解得到此线性规划的一个基本解：

x1=0，x2=400，s1=−100，s2=0，s3=−150138§1单纯形法的基本思路和原理

由于该基本解中

s1=−100，s3=−150,不满足决策变量非负的约束条件，不是可行解。满足非负条件的基本解叫做基本可行解，并把这样的基叫做可行基。

139§1单纯形法的基本思路和原理一般来说判断一个基是否是可行基，只有在求出其基本解以后。能否在求解之前，找到一个可行基呢？也就是能否找到的一个基保证在求解之后得到的解一定是基本可行解呢？

140§1单纯形法的基本思路和原理

由于线性规划的标准型中要求bj

≥0，若能找到一个基是单位矩阵（各列向量顺序无关重要），例如：

所得基本解一定是基本可行解，解中的各个变量或等于某个bj

或等于零。

141本例中找到了一个基是单位矩阵：

令其非基变量x1=x2=0，得初始基本可行解：

x1=0，x2=0，s1=300，s2=400，s3=250§1单纯形法的基本思路和原理第一次找到的可行基为单位矩阵（各列可以乱序），称之为初始可行基，相应的基本可行解叫初始基本可行解。注：若找不到单位矩阵（各列可以乱序）的基作为初始可行基，需要构造初始可行基。1421．最优性检验的依据——检验数

σj二、最优性检验

判断已求得的基本可行解是否是最优解。§1单纯形法的基本思路和原理基变量&非基变量目标函数非基变量目标函数约束等式中，非基变量移到右边，用非基变量表示基变量则目标函数中变量系数即为其检验数，把xi的检验数记为

σi。所有基变量检验数为0。143§1单纯形法的基本思路和原理例题中找到一个初始可行基：

目标函数为50x1+100x2，由于初始可行解中x1，x2

为非基变量，所以此目标函数已经用非基变量表示了，无需代换出基变量。各检验数为：

σ1=50，σ2=100，σ3=0，σ4=0，σ5=0144§1单纯形法的基本思路和原理2．最优解判别定理求最大目标函数的问题中，若某个基本可行解所有检验数

σj≤0，则该解是最优解。通俗地解释最优解判别定理，设用非基变量表示的目标函数如下所示：

注：对于求目标函数最小值的情况，只需把σj≤0改为σj≥0。145§1单纯形法的基本思路和原理当所有的

xj

≥0，且σj≤0，此时

实际上目标函数：基变量均≥0，只有检验数都为0，才有σsxs=0;非基变量的检验数均

≤0，只有非基变量都为0，才有σtxt=0

。此时目标函数才能取最大值z0。146§1单纯形法的基本思路和原理

三、基变换例题中

σ1，σ2>0，即该基本可行解不是最优解，需进行基变换。

具体做法：更换可行基中的一个列向量，得到新的可行基，求出新的基本可行解使目标函数值更优。为了换基要确定换入变量---入基变量与换出变量---出基变量。147§1单纯形法的基本思路和原理1．入基变量的确定

当某σj＞0，非基变量xj

变为基变量，不取0值可使目标函数值增大，故选基检验数大于0的非基变量换到基变量中。

max

σj

，其中σj＞0，对应的非基变量为入基变量基变量

若有两个以上σj＞0，为使目标函数更大，一般选σj

较大者的非基变量为入基变量。例题中σ2=100是最大的非负检验数，故选x2

为入基变量。

148§1单纯形法的基本思路和原理2．出基变量的确定

确定入基变量后，需在原来的基变量

s1，s2，s3

中选一个出基变量。若

s3

作为出基变量，则新的基变量为

x2，s1，s2

，非基变量

x1=s3=0，方程组变为：

x2

+s1=300，

x2+s2=400，

x2=250.得基本解：x1=0，x2=250，s1=50，s2=150，s3=0。此解满足非负条件，是基本可行解。149§1单纯形法的基本思路和原理

如何在求解以前来确定出基变量，使得求出的解是可行解？150§1单纯形法的基本思路和原理

确定出基变量的方法如下：把已确定的入基变量在各约束方程中的正系数除其所在约束方程中的常数项，把最小比值所在的约束方程中的原基变量确定为出基变量。在下一步迭代的矩阵变换中可以确保新得到的

bj

值都≥0。minbi/aij，其中aij

>0，对应的基变量为出基变量基变量151§1单纯形法的基本思路和原理

在本例题中约束方程为

x1+x2+s1=300, 2x1+x2+s2=400,

x2+s3=250.在第二步中已经知道

x2

为入基变量，把各约束方程中

x2

的为正的系数除对应的常量，得152§1单纯形法的基本思路和原理

令非基变量为零，得 x2+s1=300，

x2+s2=400，

x2=250.求解得到新的基本可行解

x1=0，x2=250，s1=50，s2=150，s3=0.

此时最小，从而对应原基变量中

s3

为出基变量，变换为

x2，s1，s2

为基变量，x1，s3

为非基变量。

153§1单纯形法的基本思路和原理

这时目标函数值为

50x1+100x2=50×0+100×250=25000显然比初始基本可行解x1=0，x2=0，s1=300，s2=400，s3=250

时的目标函数值为0要好得多。

下面再重新检验其解的最优性，若不是最优解还要继续进行基变换，直至找到最优解，或者能够判断出线性规划无最优解为止。154单纯形法的基本思路和原理单纯形法的表格形式求目标函数值最小的线性规划问题的单纯形表解法几种特殊情况本章内容1234155§2单纯形法的表格形式

可行基为m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前m列是单位矩阵）：约束条件：

以下用

xi(i=1,2,…,m)表示基变量，用

xj

(j=m+1,m+2,…,n)表示非基变量。在讲解单纯形法的表格形式之前，先从一般数学模型里推导出检验数

σj

的表达式。156§2单纯形法的表格形式

把第

i个约束方程移项，就可用非基变量来表示基变量

xi，

把以上的表达式代入目标函数，有157§2单纯形法的表格形式

最终有表达式：

其中：158§2单纯形法的表格形式

已假设

x1,x2,…xm

是基变量，即第

i行约束方程的基变量正好是

xi，迭代后，若第

i行约束方程的基变量变为

xBi，相应的目标函数系数变为

cBi，系数列向量为p′j(j=1,2,,n)则

zj

=(cB1,...,cBm

)p′j

=(cB)p′j,其中，(cB)是基变量目标函数依次组成的有序行向量。159§2单纯形法的表格形式

以下用单纯形表格来求解第二章的例1。

max50x1+100x2+0∙s1+0∙s2+0∙s3约束条件：

x1+x2+s1=300，2x1+x2+s2=400，

x2+s3=250，

x1,x2,s1,s2,s3≥0.

单纯形法的表格形式是把用单纯形法求出的基本可行解、检验最优性、迭代等步骤都用表格的方式表现。其计算的方法基本使用矩阵的行的初等变换。

160§2单纯形法的表格形式

把上面的数据填入如表所示的单纯形表格。迭代次数基变量cBx1x2s1s2s3b比值50100000bi/aij0111003002101040001001250zjσj=cj-zjstep1---寻找基变量：在上表中有一个

m×m的单位矩阵，对应的基变量为s1,s2,s3；s1s2s3000step2---计算zj

值：在

zj

行中填入第

j列与

cB

列中对应的元素相乘相加所得的值；00000step3---计算

σ

j

值：在σj

=cj

−zj

行中填入

cj−

zj

所得的值；50100000step4---计算目标函数z：b列乘以

cB

列；初始基本可行解为s1=300，s2=400，s3=250，x1=0，x2=0；z=0step5---确定入基变量：由于

σ2>σ1>0，因此确定

x2

为入基变量；step6---确定出基变量：计算bi/aij，由于250/1最小，因此确定

s3

为出基变量；300/1400/1250/1step7---标出主元：出基变量所在行，入基变量所在列的交汇处为主元，这里是a32，在表中画圈以示区别；161§2单纯形法的表格形式

以下进行第一次迭代，迭代次数基变量cBx1x2s1s2s3b比值50100000bi/aij101001250zjσj=cj-zjs1s2x2001000100001002500050/1150/2----5000-1000通过矩阵的行初等变换新的基可行解1 010-150210104002001-115011100300162§2单纯形法的表格形式

以下进行第二次迭代，迭代次数基变量cBx1x2s1s2s3b比值50100000bi/aij2zjσj=cj-zjx1s2x250010050100500502750000-50-500通过矩阵的行初等变换新的基可行解1 010-15000-211502001-115001001250最优解为：x1=50,x2=250,s1=0,s2=50,s3=0目标函数最优值：z=2750000-50-500163单纯形法的基本思路和原理单纯形法的表格形式求目标函数值最小的线性规划问题的单纯形表解法几种特殊情况本章内容1234164§3求目标函数值最小的线性规划问题的单纯形表解法

目标函数：minf=2x1+3x2.

约束条件：

x1+x2−s1=350,

x1−s2=125, 2x1+x2+s3=600,

x1,x2,s1,s2,s3≥0.一、大M法 以第二章例2讲解如何用单纯形表的方法求解目标函数值最小的

约束条件：

x1+x2≥350,

x1≥125, 2x1+x2≤600,

x1,x2≥0.

加入松弛变量和剩余变量变为标准型，得到新的约束条件

165§3求目标函数值最小的线性规划问题的单纯形表解法

目标函数：minf=2x1+3x2.

约束条件：

x1+x2

−

s1=350,

x1

−

s2=125, 2x1+x2+s3=600,

x1,x2,s1,s2,s3≥0.首先为了使单纯形表解法统一，把所有求目标函数最小值化成最大值的问题，把目标函数乘以-1。目标函数：maxz=－2x1－3x2×(-1)观察此时约束方程组的系数矩阵：无单位矩阵（或列是乱序的单位矩阵）166 约束条件：

x1+x2−s1=350,

x1−s2=125, 2x1+x2+s3=600,

x1,x2,s1,s2,s3≥0.§3求目标函数值最小的线性规划问题的单纯形表解法没有单位矩阵，则需构造，实质是构造初始可行基得到初始可行解，把人工变量“强行”地加到原来的约束方程中去目标函数：

maxz=－2x1－3x2a1a2167 约束条件：

x1+x2－s1+

a1

=350，

x1－s2+

a2=125， 2x1+x2+s3=600，

x1，x2，s1，s2，s3，a1，a2≥0.§3求目标函数值最小的线性规划问题的