管理科学1.ppt

管理运筹学管理科学 Operations Research Management science,教学日历,概述 线性规划模型及求解 线性规划模型的应用 运输问题 指派问题 排队问题,第一讲 管理科学概述,管理科学发展简史 管理科学的含义 管理科学研究程序 管理科学实例,1.1 管理科学发展简史,“二战”以前的科学管理 “二战”以后的管理科学 军事运筹学 运筹学管理科学的诞生,1.1.1 二战以前的科学管理,1850年，“三化”（单一化、标准化和专业化） 1911年，泰勒的科学管理管理 1913年，福特的“流水线生产管理” ,1.1.2 “二战”以后的管理科学,今天，人们所说的“管理科学”产生于20世纪40、50年代，称之为现代管理科学。 现代管理科学的思想与二战以前的管理科学思想应该说同属一个思想体系，但前者决不是后者的简单延伸，而是在思维方式、技术手段方面带有许许多多质的变化。 从数量角度研究和分析管理活动中存在的各种各样问题。 是一门决策性质的科学。“管理就是决策”，管理科学的基本任务就是，在一定的资源约束条件下，对可能存在的各种方案进行选择，以确定出最好的行动方案。 广泛使用各门学科中的科学方法和技术，尤其是数学、统计学、系统科学、控制论、决策科学等学科的方法。 以计算机为辅助手段，进行各项管理活动。,1.1.3 “军事运筹学”,1938年英国最早出现了军事运筹学，命名为“Operational Research”,1942年，美国从事这方面工作的科学家命其名为“Operations Research”这个名字一直延用至今。 英国雷达站与防空作战系统的协调 深水炸弹爆炸深度 巧妙避开德军潜艇 诺曼底登陆战役,深水炸弹爆炸深度,二战期间英军船队在大西洋里航行时经常受到德军潜艇的攻击。为此，英国空军经常派出轰炸机对德军潜艇实施火力打击，但轰炸效果总是不理想，对潜艇几乎构不成威胁。英军请来一些数学家专门研究这一问题，结果发现，潜艇从发现英军飞机开始下潜到深水炸弹爆炸时止，只下潜了7.6米，而英军飞机投下的炸弹却已下沉到21米处爆炸，从而导致毁伤效果低下。经过科学论证，英军果断调整了深水炸弹的引信，爆炸深度从水下21米减为水下9.1米，结果轰炸效果较过去提高了4倍。德军还误以为英军发明了新式炸弹。,巧妙避开德军潜艇,1943年以前，在大西洋上英美运输船队常常受到德国潜艇的袭击，当时，英美两国海军实力有限，一时间，德军的潜艇战搞得盟军焦头烂额。为此，一位美国海军将领专门去请教了几位数学家。数学家们运用概率分析后发现，舰队与敌潜艇相遇是一个随机事件。从数学角度来看这一问题，它具有一定的规律：一定数量的船编次越多与敌人相遇的概率就越大。美国海军接受了数学家的建议，命令舰队在指定海域集合，再集体通过危险海域，然后各自驶向预定港口。结果盟军舰队遭袭被击沉的概率下降，大大减少了损失。,1.1.4 运筹学管理科学的诞生,以数学（计算机）作为工具，通过定量分析进行决策的方法在二战中取得重大的收获，二战结束后，OR的研究和应用从军事领域迅速扩展到社会和经济领域，理论体系不断的发展和完善。 1950年，英伯明翰大学开设运筹学课程； 1951年，美专家出版运筹学方法专著； 运筹学研究期刊杂志的创刊以及出版； 电子计算机的应用；,1.2 管理科学的含义,从字面上看，管理科学包含二个方面的意思，即管理和科学，或者确切一点说，就是管理的科学。 到目前为止，人们对管理科学及作用已有了明确的认识，但对如何定义管理科学却仍然众说纷纭。 所谓管理科学是指，对与定量因素有关的管理问题通过使用科学的手段和方法（尤其是数学学科方法）进行科学决策的一门科学。 研究如何使用以定量为主的分析方法和技术来获得科学的决策。,模型,模型是对现实问题的一种描述和表述，数学模型（定量模型）则是现实问题的要素以及要素之间数量关系的数学表达。是定量分析的基础。 模型的精度：根据模型预测的值与实际值的接近程度,1.3 管理科学的研究程序,1、识别和定义问题 2、搜集数据资料 3、建立分析模型（一般是数学模型） 4、建立对模型进行求解的计算机程序 5、测试和修正模型 6、应用模型分析问题并提出管理建议 7、帮助实施决策方案,1.4 管理科学例子1,某工厂拥有有3个车间生产门、窗两种产品。每件产品在生产中需要占有的车间加工时数以及每件产品可以获得的利润以及3个车间每周可供加工时数如下表所示：,求使得总利润最大的生产计划。,1.确定决策变量：设门、窗2种产品每周的产量分别为x1，x2,2.确定限制条件： 车间1时间限制： 1x1+0x24 车间2时间限制： 0x1+2x212 车间3时间限制： 3x1+2x218 决策变量限制： x1, x20,3.确定决策目标：设总利润为z ，即： Max z =300x1+500x2,目标函数,约束条件,变量非负约束,张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。,1.4 管理科学例子2,设：,max z=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+ 83x31+90x32+74x33+65x34+93x41+61x42+83x43+75x44 s.t. x11+x12+x13+x14=1 (1) x21+x22+x23+x24=1 (2) x31+x32+x33+x34=1 (3) x41+x42+x43+x44=1 (4) x11+x21+x31+x41=1 (5) x12+x22+x32+x42=1 (6) x13+x23+x33+x43=1 (7) x14+x24+x34+x44=1 (8) xij=0,1,最优解为：x14=1，x23=1，x32=1，x41=1，max z=336 即张老师教化学，王老师教语文，李老师教数学，赵老师教语文。,四门课的总分可以达到336分。,第二讲 线性规划模型,线性规划问题 线性规划模型 线性规划的图解法,线性规划问题,生产计划问题产品组合优化问题 配料问题 背包问题 运输问题 指派问题,1. 生产计划问题1（Production Planning）,某工厂拥有原料A、B以及生产设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,求使得总利润最大的生产计划。,1.确定决策变量：设甲乙丙三种产品的产量分别为x1，x2，x3,2.确定限制条件： 台时限制： 1x1+2x2+3x33000 原料A 限制： 6x1+5x2+4x34000 原料B 限制： 0x1+7x2+8x32500 决策变量限制： x1, x2, x30,3.确定决策目标：设总利润为z ，即： Max z =500x1+800x2+1000x3,设三种产品的产量分别为x1，x2，x3，总利润为z，线性规划模型为：,max z=500x1+800x2+1000x3 s.t. 1x1+2x2+3x33000 6x1+5x2+4x34000 0x1+7x2+8x32500 x1, x2, x30,目标函数,约束条件,变量非负约束,这个问题的最优解为：x1=458.3件，x2=0单位，x3=312.5单位 最大利润为：z=541666.7元。 问题：三个约束条件可以改为等式吗？,1. 生产计划问题2（Production Planning）,某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,求使得总利润最大的生产计划。,设四种产品的产量分别为x1，x2，x3，x4，总利润为z，线性规划模型为：,max z=5.24x1+7.30x2+8.34x3+4.18x4 s.t. 1.5x1+1.0x2+2.4x3+1.0x42000 1.0x1+5.0x2+1.0x3+3.5x48000 1.5x1+3.0x2+3.5x3+1.0x45000 x1, x2, x3, x40,目标函数,约束条件,变量非负约束,这个问题的最优解为：x1=294.12件，x2=1500件，x3=0，x4=58.82件 最大利润为：z=12737.06元。 问题：三个约束条件可以改为等式吗？,2. 配料问题（Material Blending）,某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（）如下表：,要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。,min z=115x1+97x2+82x3+76x4 s.t. 0.0321x1+0.0453x2+0.0219x3+0.0176x43.20 Cr的含量下限约束 0.0204x1+0.0112x2+0.0357x3+0.0433x42.10 Mn的含量下限约束 0.0582x1+0.0306x2+0.0427x3+0.0273x44.30 Ni的含量下限约束 x1+x2+x3+x4=100 物料平衡约束 x1, x2, x3, x40,设四种原料分别选取x1，x2，x3，x4公斤，总成本为z。,这个问题的最优解为：x1=26.58, x2=31.57, x3=41.84，x4=0（公斤）, 最低成本为z=9549.87元。 问题：如果某一种成分的含量既有下限，又有上限怎么办？,3. 背包问题（Knapsack Problem）,一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：,求背包中装入每种物品各多少件，使背包中物品总价值最高。,设三种物品的件数各为x1，x2，x3件，总价值为z。 max z=17x1+72x2+35x3 s.t. 10x1+41x2+20x350 x1，x2，x30 x1，x2，x3为整数 这是一个整数规划问题（Integer Programming）。这个问题的最优解为： x1=1件，x2=0件，x3=2件，最高价值z=87元,4. 运输问题（Transportation）,某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：,求总运费最低的运输方案。,35吨,25吨,10吨,30吨,20吨,设从两个供应地到三个需求地的运量（吨）如下表：,min z=2x11+3x12+5x13+4x21+7x22+8x23 s.t. x11+x12+x13 =35 供应地A1 x21+x22+x23 =25 供应地A2 x11 +x21 =10 需求地B1 x12 +x22 =30 需求地B2 x13 +x23 =20 需求地B3 x11, x12, x13, x21, x22, x230,这个问题的最优解表示如下：,最小总运费为：z=330+55+410+815=275元,30吨,5吨,10吨,15吨,5. 指派问题（Assignment Problem）,有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个人完成j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。 设：,张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。,设：,max z=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+ 83x31+90x32+74x33+65x34+93x41+61x42+83x43+75x44 s.t. x11+x12+x13+x14=1 (1) x21+x22+x23+x24=1 (2) x31+x32+x33+x34=1 (3) x41+x42+x43+x44=1 (4) x11+x21+x31+x41=1 (5) x12+x22+x32+x42=1 (6) x13+x23+x33+x43=1 (7) x14+x24+x34+x44=1 (8) xij=0,1,最优解为：x14=1，x23=1，x32=1，x41=1，max z=336 即张老师教化学，王老师教语文，李老师教数学，赵老师教语文。,四门课的总分可以达到336分。,线性规划模型,min(max) z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn (, )b1 a21x1+a22x2+a2nxn (, )b2 am1x1+am2x2+amnxn (, )bm x1, x2, , xn 0 (, Free),线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：,线性规划的标准形式,目标函数为极小(大)化，约束条件全部为等号约束，所有变量全部是非负的，这样的线性规划模型称为标准形式 Min(max) z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0,线性规划模型用矩阵和向量表示,Min(max) z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0,线性规划模型用矩阵和向量表示（续）,因此，线性规划模型可以写成如下矩阵和向量的形式,线性规划模型总结,线性规划模型的结构 目标函数 ：max，min 约束条件：,=, 变量符号：0, 0, Free 线性规划的标准形式 目标函数： Min(max) 约束条件 ：= 变量符号 ：0,线性规划问题的标准化,极大化目标函数转化为极小化 小于等于约束条件转化为等号约束 大于等于约束条件转化为等号约束 变量没有符号限制（Free）的标准化 变量小于等于0的标准化,max z=2x1-3x2+x3 令 z=-z，z=-2x1+3x2-x3 新的目标函数 min z=-2x1+3x2-x3 取得极小化的最优解时，这个最优解同时使原目标函数值取得最大化的最优解。但两个问题最优解的目标函数值相差一个负号。,极大化目标函数问题转化为极小化目标函数,例如，对于以下两个线性规划问题,max z=2x1+3x2 s.t. x1+x23 x21 (A) x1, x20,min z=-2x1-3x2 s.t. x1+x23 x21 (B) x1, x20,它们的最优解都是x1=2, x2=1，但(A)的最大化的目标函数值为max z=7，(B)的最小化的目标函数值为min z=-7,2x1+3x2-4x35 引进松弛变量(Slack variable) x4=5-(2x1+3x2-4x3)，把松弛变量x4加在约束条件左边，就可以将小于等于约束变为等式。 2x1+3x2-4x3+x4=5 由此可以知道，松弛变量x40。如果有一个以上小于等于约束，要对于每一个约束引进不同的松弛变量。例如： 2x1+3x2-4x35 3x1-2x2+5x38 在两个约束中分别引进松弛变量x4，x50 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 +x5=8,小于等于约束条件转化为等号约束,将不等式约束变为等式约束。例如： 2x1+3x2-4x35 3x1-2x2+5x38 在两个约束的左边分别减去松弛变量x4，x50 2x1+3x2-4x3-x4 =5 3x1-2x2+5x3 -x5=8,大于等于约束条件转化为等号约束,没有符号限制的变量，用两个非负变量之差表示。例如： max z=x1+2x2-3x3 s.t. 2x1+3x2-4x35 3x1-2x2+5x38 x10, x2:free, x30 先将目标函数转化为极小化，并在约束中引进松弛变量，把不等式约束变为等式。 Min z=-x1-2x2+3x3 s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10, x2:free, x3, x4, x50,变量没有符号限制(Free)的标准化,Min z=-x1-2x2+3x3 s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3-x5=8 x10, x2:free, x3, x4, x50 然后，令x2=x2-x2”，其中x2,x2”0。代入模型，消去x2 Min z=-x1-2(x2-x”2)+3x3 s.t. 2x1+3(x2-x”2)-4x3+x4 =5 3x1-2(x2-x”2)+5x3 -x5=8 x1, x2, x”2, x3, x4,x50 整理，得到标准形式： Min z=-x1-2x2+x”2+3x3 s.t. 2x1+3x2-3x”2-4x3+x4 =5 3x1-2x2+2x”2+5x3 -x5=8 x1, x2, x”2, x3, x4,x50,max z=x1+2x2-3x3 s.t. 2x1+3x2-4x35 3x1-2x2+5x38 x10, x20, x30 min z=-x1-2x2+3x3 s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x10, x20, x3, x4, x50 令 x2=-x2，x20, 代入模型 min z=-x1+2x2+3x3 s.t. 2x1-3x2-4x3+x4 =5 3x1+2x2+5x3 -x5=8 x10, x20, x3, x4, x50,变量小于等于0的的标准化,max z=x1+ 3x2 s.t. x1 + x210 -2x1+ 2x212 x1 7 x1 0, x2 : free,max z=x1+ 2x2 s.t. x1 - x21 x1+ 2x24 x1 3 x1 0, x20,min z=x1 - 3x2 s.t. 2x1 - x24 x1+ x2 3 x2 5 x1 4 x1 , x2 : free,min z=x1 + 3x2 s.t. x1 + 2x2 4 2x1+ x2 4 x1 : free, x2 0,简单线性规划问题的图解法,某小家电制造企业提出两种新型的小家电D3210与H4211，两种产品均要经过5道工序，两件产品在生产中各工序的时间、每件产品可以获得的利润以及5道工序可利用的时数如下表所示：,求使得总利润最大的生产计划。,设两种产品的产量分别为x1，x2，总利润为z，线性规划模型为：,max z=70x1+110x2 s.t. 1.0x1+1.2x240 0.7x1+0.8x234 0.5x1+0.5x227 0.2x1+0.3x215 1.5x1+1.4x254 x1, x20,目标函数,约束条件,变量非负约束,线性规划的图解,max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域,目标函数等值线,最优解,z=6,z=3,z=9,z=12,问题：1、线性规划的最优解是否可能位于可行域的内部？ 2、线性规划的最优解是否可能位于可行域的边界上？,可行域的性质,线性规划的可行域是凸集 线性规划如果有最优解，最优解至少在可行域的一个极点上,凸集,凸集,不是凸集,线性规划可行域和最优解的几种情况,1、可行域封闭 唯一最优解,2、可行域封闭 多个最优解,3、可行域开放 唯一最优解,4、可行域开放 多个最优解,5、可行域开放 目标函数无界,6、无可行解,图解法习题,max z=x1+ 3x2 s.t. x1 + x210 -2x1+ 2x212 x1 7 x1 0, x20,max z=x1+ 2x2 s.t. x1 - x21 x1+ 2x24 x1 3 x1 0, x20,min z=x1 - 3x2 s.t. 2x1 - x24 x1+ x2 3 x2 5 x1 4 x1 0, x20,min z=x1 + 3x2 s.t. x1 + 2x2 4 2x1+ x2 4 x1 0, x20,解的可行性和松弛变量符号的关系,max z=2x1+3x2 s.t. x1+x24 (1) -x1+x21 (2) x1, x20,max z=2x1+3x2 s.t. x1+x2+x3 =4 -x1+x2 -x4=1 x1, x2,x3,x40,引进松 弛变量,A(1,2.5)满足所有约束条件，x3=0.5, x4=0.5 B(2,1)满足(1)，不满足(2)，x3=1, x4=-2 C(1.5,3)不满足(1),满足(2)，x3=-0.5, x4=0.5 D(3,2)不满足(1)和(2)，x3=-1, x4=-2 结论：如果一个解满足一个约束条件，相应的松弛变量大于等于0。如果一个解不满足一个约束条件，相应的松弛变量小于0。,x3=0,x4=0,max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0,max z=x1+2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40,x1=0, x2=0 x3=3, x4=1,x1=0, x4=0 x2=1, x3=2,x2=0, x3=0 x1=3, x4=1,x3=0, x4=0 x1=2, x2=1,x1=0, x3=0 x2=3, x4=-2,x2=0,x1=0,O,A,B,C,D,线性规划的基本概念基、基础解、基础可行解、极点,标准化的线性规划问题，有n个变量，m个约束。 令其中n-m个变量等于零，如果剩下的m个变量的系数矩阵的行列式不等于0，这