运筹学复习提纲2015

1、期末复习考试及评分标准考试及评分标准n考试成绩考试成绩 60分分n平时平时 40分分第第2 2章章线性规划的图解法线性规划的图解法 2.图解法的灵敏度分析图解法的灵敏度分析1.图解法图解法例例1. 某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位、产品才能使工厂获利最多？线性规划模型：线性规划模型： 目标函数：目标函数：Max z = 50 x1 + 100 x2 约束条件：约束条件：s.t. x1 + x2 300 2 x1 + x2 400 x2 250 x1 , x2 0例例1.目标函数：目标

2、函数： Max z = 50 x1 + 100 x2 约束条件：约束条件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E)得到最优解：得到最优解： x1 = 50， x2 = 250 最优目标值最优目标值 z = 275002图图 解解 法法 对于只有两个决对于只有两个决策变量的线性规划问策变量的线性规划问题，可以在平面直角题，可以在平面直角坐标系上作图表示线坐标系上作图表示线性规划问题的有关概性规划问题的有关概念，并求解。念，并求解。 下面通过例下面通过例1 1详细详细讲解其方法：讲解其方法：取各约束条件

3、的公共部分，如图2-1所示。x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图2-12图图 解解 法法x1x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2CBADE第第2 2章章线性规划的图解法线性规划的图解法 2.图解法的灵敏度分析图解法的灵敏度分析1.图解法图解法图解法的灵敏度分析图解法的灵敏度分析 Ci 假设产品假设产品的利润的利润100元不变，即元不变，即 c2 = 100，代到式（，代到式（*）并整理得并整理得 0 c1 100 假设产品假设产品的利润的利润 50 元不变，即元不变，即 c1 = 50 ，代到式（，代

4、到式（*）并整理得并整理得 50 c2 + 假若产品假若产品、的利润均改变，则可直接用式（的利润均改变，则可直接用式（*）来判）来判断。断。 假设产品假设产品、的利润分别为的利润分别为60元、元、55元，则元，则 - 2 - (60 / 55) - 1 那么，最优解为那么，最优解为 z = x1 + x2 和和 z = 2 x1 + x2 的交的交点点 x1 = 100，x2 = 200 。 当约束条件右边系数bj变化时，其线性规划的可行域也将变化，这样就可能引起最优解的变化。为了说明这方面的灵敏度分析，不妨假设例1中的设备台时数增加了10个台时，共有台时数310个，这样例1中的设备台时数的约

5、束条件就变为： x1+x2310, 增加了10个台时，扩大了可行域。二、二、 约束条件中右边系数约束条件中右边系数bj的灵敏度分析的灵敏度分析第三章第三章 线性规划问题的计算机求解线性规划问题的计算机求解1“管理运筹学”软件的操作方法2“管理运筹学”软件的输出信息分析例例1.目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E)1 1“管理运筹学管理运筹学”软件的操作方法软件的操作方法1.1.软件使用演示：（演示例软件使用演示：（演示例1 1）第

6、一步：点击第一步：点击“开始开始”-“-“程序程序”- “- “管理运筹学管理运筹学2.5”2.5”，弹出主窗口。，弹出主窗口。1 1“管理运筹学管理运筹学”软件的操作方法软件的操作方法第四步：点击第四步：点击“解决解决”按钮，得出计算结果。本题的运行结果界面如下。按钮，得出计算结果。本题的运行结果界面如下。2 2“管理运筹学管理运筹学”软件的输出信息分软件的输出信息分析析第五步：分析运行结果。 本题中目标函数的最优值是27500，x1=50, x2=250。 相差值表示相应的决策变量的目标系数需要改进的数量，使得决策变量为正值，当决策变量已为正数时，相差数为零。 松弛/剩余变量的数值表示还有

7、多少资源没有被使用。如果为零，则表示与之相对应的资源已经全部用上。 对偶价格表示其对应的资源每增加一个单位，将增加多少个单位的最优值。 目标函数系数范围表示最优解不变的情况下，目标函数的决策变量系数的变化范围。当前值是指当前的最优解中的系数取值。 常数项范围是指约束条件的右端常量。上限值和下限值是指当约束条件的右端常量在此范围内变化时，与其对应的约束条件的对偶价格不变。当前值是指现在的取值。 以上计算机输出的目标函数系数和约束条件右边值的灵敏度分析都是在其他系数值不变，只有一个系数变化的基础上得出的！ 2.当有多个系数变化时，需要进一步讨论。 百分之一百法则：对于所有变化的目标函数决策系数（约

8、束条件右边常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过100%时，最优解不变（对偶价格不变，最优解仍是原来几个线性方程的解）。 * 允许增加量 = 上限 - 现在值 c1 的允许增加量为 100 - 50 = 50 b1 的允许增加量为 325 - 300 = 25 * 允许减少量 = 现在值 - 下限 c2 的允许减少量为 100 - 50 = 50 b3 的允许减少量为 250 - 200 = 50 * 允许增加的百分比 = 增加量 / 允许增加量 * 允许减少的百分比 = 减少量 / 允许减少量 第四章第四章 线性规划在工商管理中的应用线性规划在工商管理中的应用 1 1

9、 人力资源分配的问题 2 2 生产计划的问题 3 3 套裁下料问题 4 4 配料问题 5 5 投资问题1 1人力资源分配的问题 例1某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?1 1人力资源分配的问题 解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 + x6 约束条件：s.t. x1 + x6 60 x1 + x2 70 x2 + x

10、3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 03 3套裁下料问题 例5某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？第七章第七章 运运 输输 问问 题题 1 1运运 输输 模模 型型 2 2运输问题的计算机求解运输问题的计算机求解 3 3运输问题的应用运输问题的应用 4 4* *运输问题的表上作业法运输问题的表上作业法生产问题生产问题 某机床厂定下一年合同分某机床厂定下一年合同分别于各季度末交货。已知别于各季度末交货。已知各季度生产

11、成本不同，允各季度生产成本不同，允许存货，存储费许存货，存储费0.12万元万元/台季，三、四季度可以加台季，三、四季度可以加班生产，加班生产能力班生产，加班生产能力8台台/季，加班费用季，加班费用3万元万元/台台 问如何安排生产使得总费问如何安排生产使得总费用最低？用最低？季度正常生产能力单位成本（万元）交货台数12343032202810.5510.81111.125301545建模：建模： 成本成本 交货交货生产生产 1 2 3 4 5（虚拟）（虚拟）产量产量1季度正常生产季度正常生产2季度正常生产季度正常生产3季度正常生产季度正常生产3季度加班生产季度加班生产4季度正常生产季度正常生产4

12、季度加班生产季度加班生产10.55 10.67 10.79 10.91 0 M 10.8 10.92 11.04 0 M M 11 11.12 0 M M 14 14.12 0 M M M 11.1 0 M M M 14.1 0 30 32 20 8 28 8 需求量需求量 25 30 15 45 11 1261264 4运输问题的表上作业法运输问题的表上作业法例10.喜庆食品公司有三个生产面包的分厂A1，A2，A3，有四个销售公司B1，B2，B3，B4，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表所示，在表中产量与销量的单位为吨，运价的单位为百元/吨。问该公司

13、应如何调运产品在满足各销点的需求量的前提下总运费最少？ 销地产地B1B2B3B4产量A13113107A219284A3741059销量3656 2 020第八章第八章 整数规划整数规划 3整数规划的应用整数规划的应用 4整数规划的分枝定界法整数规划的分枝定界法3 3整数规划的应用整数规划的应用 一、投资场所的选择一、投资场所的选择 例2、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定： 在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至

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

15、少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。 27 指派问题 有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少 工作工人ABCD甲15182124乙19232218丙26171619丁19212317 如果把工作时间看成创造的效益，那么又该如何指派，才能获得最大效益？ 如果再增加一项工作E，四人完成的时间分别是17,20,15,16分钟，那么又该如何指派使得所花时间最少？29第九章第九章 目标规划目标规划 1 1 目标规划概述目标规

16、划概述 2 2 目标规划图解法目标规划图解法 3 3 复杂情况下的目标规划复杂情况下的目标规划 4 4 加权目标规划加权目标规划 303 3复杂情况下的目标规划复杂情况下的目标规划例例7一工艺品厂商手工生产某两种工艺品A、B，已知生产一件产品A需要耗费人力2工时，生产一件产品B需要耗费人力3工时。A、B产品的单位利润分别为260元和125元。为了最大效率地利用人力资源，确定生产的首要任务是保证人员高负荷生产，要求每周总耗费人力资源不能低于600工时，但也不能超过680工时的极限；次要任务是要求每周的利润超过70000元；在前两个任务的前提下，为了保证库存需要，要求每周产品A和B的产量分别不低于

17、200和120件，因为B产品比A产品更重要，不妨假设B完成最低产量120件的重要性是A完成200件的重要性的2倍。 试求如何安排生产？313 3复杂情况下的目标规划复杂情况下的目标规划采用简化模式，最终得到目标线性规划如下： Min P1(d1+)+ P1(d2)+P2(d3-)+ P3(d4-)+ P3(2d5-) s.t. 2x1+3x2-d1+d1-=680 对应第1个目标 2x1+3x2-d2+d2-=600 对应第2个目标 250 x1+125x2-d3-+d3+70000 对应第3个目标 x1-d4+d4-=200 对应第4个目标 x2-d5+d5-=120 对应第5个目标 x1,

18、x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-0 第十一章图与网络模型第十一章图与网络模型1 1图与网络的基本概念图与网络的基本概念2 2最短路问题最短路问题3 3最小生成树问题最小生成树问题4 4最大流问题最大流问题5 5最小费用最大流问题最小费用最大流问题 例例1 求下图中求下图中v1到到v6的最短路的最短路v23527531512v1v6v5v3v4 例例2 设备更新问题。某公司使用一台设备，在每年年初，设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是否购买新的设备。如果购置新设备，就要支付公司就要决定是否购买新的设备。如果购置新设备，就

19、要支付一定的购置费，新设备的维修费用就低。如果继续使用旧设备，一定的购置费，新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。公司原来没有此设备。用最小。公司原来没有此设备。 已知：设备每年年初的价格表已知：设备每年年初的价格表 设备维修费如下表设备维修费如下表年份年份12345年初价格年初价格1111121213使用年数使用年数0-11-22-33-44-5每年维修每年维修费用费

20、用56811181v2v3v4v5v64686865505061456054例例6：如下图：如下图G，求最小生成树：，求最小生成树：一、最小费用最大流的数学模型一、最小费用最大流的数学模型 例例7 由于输油管道的长短不一，所以在例由于输油管道的长短不一，所以在例6中每段管道（中每段管道（ vi,vj ）除了有不同的流量限制）除了有不同的流量限制cij外，还有不同的单位流量的费用外，还有不同的单位流量的费用bij ，cij的单的单位为万加仑位为万加仑/小时，小时， bij的单位为百元的单位为百元/万加仑。如万加仑。如图。从采地图。从采地 v1向销地向销地 v7运送石油，怎样运送才运送石油，怎样运

21、送才能运送最多的石油并使得总的运送费用最小？求能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。出最大流量和最小费用。(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单服务台泊松到达、任意服务时间的排队模型单服务台泊松到达、任意服务时间的排队模型

22、6单服务台泊松到达、定长服务时间的排队模型单服务台泊松到达、定长服务时间的排队模型7多服务台泊松到达、任意的服务时间、损失制排队模型多服务台泊松到达、任意的服务时间、损失制排队模型8顾客来源有限制排队模型顾客来源有限制排队模型9单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型10多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型37损失制系统服务机构被占用时新到的顾客将离开服务机构被占用时新到的顾客将离开等待制系统先来先服务先来先服务(First Come First Serve, FCFS)后来先服务后来先服务(Last Come First Serve, LCFS)具有优先权的服务具有优先权的服务(Priority, PR)随机选择服务随机选择服务混合制