运筹学复习提纲2015

期末复习考试及评分标准考试成绩＝60分平时＝40分内容概要第2章线性规划的图解法

2.图解法的灵敏度分析1.图解法例1.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？线性规划模型：目标函数：Maxz=50x1+100x2

约束条件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0例1.目标函数：

Maxz=50x1+100x2约束条件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：

x1=50，x2=250

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

对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：取各约束条件的公共部分，如图2-1所示。x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-1§2图解法x1x2图2-2z=27500=50x1+100x2z=0=50x1+100x2CBADE内容概要第2章线性规划的图解法

2.图解法的灵敏度分析1.图解法图解法的灵敏度分析Ci假设产品Ⅱ的利润100元不变，即c2=100，代到式（*）并整理得

0c1

100假设产品Ⅰ的利润50元不变，即c1=50，代到式（*）并整理得

50c2

+假若产品Ⅰ、Ⅱ的利润均改变，则可直接用式（*）来判断。假设产品Ⅰ、Ⅱ的利润分别为60元、55元，则

-2-(60/55)

-1

那么，最优解为

z=x1+x2

和

z=2x1+x2

的交点x1=100，x2=200。

当约束条件右边系数bj变化时，其线性规划的可行域也将变化，这样就可能引起最优解的变化。为了说明这方面的灵敏度分析，不妨假设例1中的设备台时数增加了10个台时，共有台时数310个，这样例1中的设备台时数的约束条件就变为：

x1+x2≤310,

增加了10个台时，扩大了可行域。二、约束条件中右边系数bj的灵敏度分析第三章线性规划问题的计算机求解§1“管理运筹学”软件的操作方法§2“管理运筹学”软件的输出信息分析例1.目标函数：

Maxz=50x1+100x2约束条件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)§1

“管理运筹学”软件的操作方法1.软件使用演示：（演示例1）第一步：点击“开始”->“程序”->“管理运筹学2.5”，弹出主窗口。§1

“管理运筹学”软件的操作方法第四步：点击“解决”按钮，得出计算结果。本题的运行结果界面如下。§2

“管理运筹学”软件的输出信息分析第五步：分析运行结果。本题中目标函数的最优值是27500，x1=50,x2=250。相差值表示相应的决策变量的目标系数需要改进的数量，使得决策变量为正值，当决策变量已为正数时，相差数为零。松弛/剩余变量的数值表示还有多少资源没有被使用。如果为零，则表示与之相对应的资源已经全部用上。对偶价格表示其对应的资源每增加一个单位，将增加多少个单位的最优值。目标函数系数范围表示最优解不变的情况下，目标函数的决策变量系数的变化范围。当前值是指当前的最优解中的系数取值。常数项范围是指约束条件的右端常量。上限值和下限值是指当约束条件的右端常量在此范围内变化时，与其对应的约束条件的对偶价格不变。当前值是指现在的取值。

以上计算机输出的目标函数系数和约束条件右边值的灵敏度分析都是在其他系数值不变，只有一个系数变化的基础上得出的！

2.当有多个系数变化时，需要进一步讨论。百分之一百法则：对于所有变化的目标函数决策系数（约束条件右边常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过100%时，最优解不变（对偶价格不变，最优解仍是原来几个线性方程的解）。*允许增加量=上限-现在值

c1的允许增加量为100-50=50

b1的允许增加量为325-300=25*允许减少量=现在值-下限

c2的允许减少量为100-50=50

b3的允许减少量为250-200=50*允许增加的百分比=增加量/允许增加量*允许减少的百分比=减少量/允许减少量第四章线性规划在工商管理中的应用§1人力资源分配的问题§2生产计划的问题§3套裁下料问题§4配料问题§5投资问题§1

人力资源分配的问题

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

设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?§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≥0§3

套裁下料问题

例5．某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？第七章运输问题§1运输模型§2运输问题的计算机求解§3运输问题的应用§4*运输问题的表上作业法生产问题某机床厂定下一年合同分别于各季度末交货。已知各季度生产成本不同，允许存货，存储费0.12万元/台季，三、四季度可以加班生产，加班生产能力8台/季，加班费用3万元/台问如何安排生产使得总费用最低？季度正常生产能力单位成本（万元）交货台数12343032202810.5510.81111.125301545建模：

成本交货生产

12345（虚拟）产量1季度正常生产2季度正常生产3季度正常生产3季度加班生产4季度正常生产4季度加班生产10.5510.6710.7910.910M10.810.9211.040MM1111.120MM1414.120MMM11.10MMM14.103032208288

需求量2530154511126126§4运输问题的表上作业法例10.喜庆食品公司有三个生产面包的分厂A1，A2，A3，有四个销售公司B1，B2，B3，B4，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元/吨。问该公司应如何调运产品在满足各销点的需求量的前提下总运费最少？

销地产地B1B2B3B4产量A13113107A219284A3741059销量36562020第八章整数规划§3整数规划的应用

§4整数规划的分枝定界法§3整数规划的应用

一、投资场所的选择例2、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置Aj(j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区由A1

，A2

，A3三个点至多选择两个；在西区由A4

，A5两个点中至少选一个；在南区由A6

，A7两个点中至少选一个；在北区由A8

，A9

，A10

三个点中至少选两个。

Aj

各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示(单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?二、固定成本问题例7．高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。

27指派问题

有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少如果把工作时间看成创造的效益，那么又该如何指派，才能获得最大效益？如果再增加一项工作E，四人完成的时间分别是17,20,15,16分钟，那么又该如何指派使得所花时间最少？29第九章目标规划§1目标规划概述§2目标规划图解法§3复杂情况下的目标规划§4加权目标规划

30§3复杂情况下的目标规划例7．一工艺品厂商手工生产某两种工艺品A、B，已知生产一件产品A需要耗费人力2工时，生产一件产品B需要耗费人力3工时。A、B产品的单位利润分别为260元和125元。为了最大效率地利用人力资源，确定生产的首要任务是保证人员高负荷生产，要求每周总耗费人力资源不能低于600工时，但也不能超过680工时的极限；次要任务是要求每周的利润超过70000元；在前两个任务的前提下，为了保证库存需要，要求每周产品A和B的产量分别不低于200和120件，因为B产品比A产品更重要，不妨假设B完成最低产量120件的重要性是A完成200件的重要性的2倍。试求如何安排生产？31§3复杂情况下的目标规划采用简化模式，最终得到目标线性规划如下：

MinP1(d1+)+P1(d2－)+P2(d3-)+P3(d4-)+P3(2d5-)s.t.

2x1+3x2-d1++d1-=680对应第1个目标

2x1+3x2-d2++d2-=600对应第2个目标

250x1+125x2-d3-+d3+＝70000对应第3个目标

x1-d4++d4-=200对应第4个目标

x2-d5++d5-=120对应第5个目标

x1,x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-≥0

第十一章图与网络模型§1图与网络的基本概念§2最短路问题§3最小生成树问题§4最大流问题§5最小费用最大流问题

例1求下图中v1到v6的最短路v23527531512v1v6v5v3v4

例2设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是否购买新的设备。如果购置新设备，就要支付一定的购置费，新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。公司原来没有此设备。已知：设备每年年初的价格表设备维修费如下表年份12345年初价格1111121213使用年数0-11-22-33-44-5每年维修费用568111864686865505061456054例6：如下图G，求最小生成树：一、最小费用最大流的数学模型例7由于输油管道的长短不一，所以在例6中每段管道（vi,vj）除了有不同的流量限制cij外，还有不同的单位流量的费用bij，cij的单位为万加仑/小时，bij的单位为百元/万加仑。如图。从采地v1向销地v7运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)第十四章排队论§1引言§2单服务台泊松到达、负指数服务时间的排队模型§3多服务台泊松到达、负指数服务时间的排队模型§4排队系统的经济分析§5单服务台泊松到达、任意服务时间的排队模型§6单服务台泊松到达、定长服务时间的排队模型§7多服务台泊松到达、任意的服务时间、损失制排队模型§8顾客来源有限制排队模型§9单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型§10多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型37损失制系统服务机构被占用时新到的顾客将离开等待制系统先来先服务(FirstComeFirstServe,FCFS)后来先服务(LastComeFirstServe,LCFS)具有优先权的服务(Priority,PR)随机选择服务混合制系统损失制与等待制的混合排队及排队规则：M/M/1/∞/∞单位时间顾客平均到达数，单位平均服务顾客数(<)数量指标公式:1.系统中无顾客的概率