运筹学-怎样把事情做到最好

运筹学

——怎样把事情做到最好绪论1.1题解Operations汉语翻译工作、操作、行动、手术、运算OperationsResearch日本——运用学港台——作业研究中国大陆——运筹学OperationalResearch原来名称，意为军事行动研究——历史渊源绪论1.2运筹学的历史早期运筹思想：田忌赛马丁渭修宫沈括运粮Erlang1917排队论Harris1920存储论

绪论1.3运筹学的历史军事运筹学阶段德军空袭防空系统Blackett运输船编队空袭逃避深水炸弹轰炸机编队绪论1.3运筹学的历史管理运筹学阶段战后人员三分:军队、大学、企业大学：课程、专业、硕士、博士企业：美国钢铁联合公司英国国家煤炭局运筹学在中国：50年代中期引入华罗庚推广优选法、统筹法中国邮递员问题、运输问题

1.4定性与定量两者都是常用的决策方法定性是根底，定量是工具，定量为定性效劳。定性有主观性，定量有科学性，管理科学的开展，定量越来越多。但定量不可替代定量。1.5运筹学的模型模型：真实事物的模仿，主要因素、相互关系、系统结构。形象模型：如地球仪、沙盘、风洞模拟模型：建港口，模拟船只到达。学生模拟企业管理系统运行。数学模型：用符号或数学工具描述现实系统。V=F〔xi,yj,uk)G(xi,yj,uk)≥01.6运筹学的学科体系规划论：线性规划、非线性规划|、整数规划、目标规划、动态规划图论与网络存储论排队论决策论对策论QMforWindows的常用工具人事(工作分配问题)整数规划〔当线形规划结果不为整数时,而需要是整数时用当约束条件中,有选择和不选择的问题是用一般的线性问题运输问题1.7运筹学的工作步骤确定问题搜集数据建立模型检验模型求解模型结果分析结果实施1.8运筹学与计算机计算机为运筹学提供解题工具。本书有现成的程序可以利用要学会解题的思路与方法，建立模型很重要。第二章线性规划与单纯形法引例:一元优化问题2.1LP的根本概念2.1.1LP的数学模型例题1——生产方案问题产品A产品B资源限量劳动力设备原材料9434510360200300利润元/KG70120例题1建模问题：如何安排生产方案，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：人力约束9X1+4X2≤360设备约束4X1+5X2≤200原材料约束3X1+10X2≤300非负性约束X1≥0X2≥0选择变量个数QM\linerprogramming数据输入分析结果影子价格

例(排产问题):某公司生产两种产品，具体的情况见表所示。问如何安排生产，使生产获得的利润最大？III资源设备台时128原料A4016原料B0412单位产品利润23解：设产品I、II分别生产X1、X2个Obj：MaxX=2X1+3X2S．T．X1+2X2≤84X1≤164X2≤12X1，X2≥0解得：X1=4，X2=2，Z=14专业软件求解结果产品1生产4件，产品2生产2件，总利润为14EXCEL输入界面例题2——配方问题养海狸鼠饲料中营养要求：Va每天至少700克，Vb每天至少30克，Vc每天刚好30克。现有五种饲料，搭配使用，饲料成分如下表：饲料VaVbVc价格元/KGIIIIIIIVV32161810.50.220.50.510.220.827495营养要求70030200例题2建模设抓取饲料Ix1kg;饲料IIx2kg;饲料IIIx3kg……目标函数：最省钱minZ=2x1+7x2+4x3+9x4+5x5约束条件：3x2+2x2+x3+6x4+18x5≥700营养要求：x1+0.5x2+0.2x3+2x4+0.5x5≥300.5x1+x2+0.2x3+2x4+0.8x5=200用量要求：x1

≤50,x2≤60,x3≤50,x4≤70,x5≤4非负性要求：x1

≥0,x2≥0,x3≥0,x4≥0,x5≥0例2(排班问题)：某公司日常工作统计，每昼夜至少需要的人数见表所示。最少需要配备的人数是多少？序号时间段所需人数方案16:00~14:007070x1214:00~22:006060x2322:00~6:003030x3例题3：人员安排问题模型：设不同的时间段的排班人数分别为X1、X2、X3Obj：MinZ=X1+X2+X3S．T．X1≥70X2≥60X3≥30X1、X2、X3≥0医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：

序号时段最少人数安排人数106—1060X1210—1470X2314—1860X3418—2250X4522—0220X5602—0630x6例题3建模目标函数：minZ=x1+x2+x3+x4+x5+x6约束条件：x1+x2

≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30非负性约束：xj

≥0,j=1,2,…6该公司进一步分析还可以知道，每个时段的人数分别是序号时间段所需人数方案具体的方案1方案0具体的方案216~1060X1604060210~1470X2103010314~1860X3503050418~2250X40200522~220X52003062~630X610300医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：

序号时段最少人数安排人数106—0860X1208—10X2310—1270X3412—14X4514—1660X5616—18X6718—2050X7820—22X8922—2420X91024—02X101102—04X111202—0630x12目标函数：minZ=x1+x2+x3+x4+x5+x6约束条件：x10+x11+x12+x1≥70x11+x12+x1+x2≥70x12+x1+x2+x3≥70x1+x2+x3+x4≥70x2+x3+x4+x5≥70x3+x4+x5+x6≥70x4+x5+x6+x7≥70x5+x6+x7+x8≥70x6+x7+x8+x9≥60x7+x8+x9+x10≥50x8+x9+x10+x11≥20x9+x10+x11+x12≥30非负性约束：xj≥0,j=1,2,…12该公司进一步分析还可以知道，每个时段的人数分别是序号时间段所需人数方案具体的方案1方案0具体的方案216~1060X1604060210~1470X2103010314~1860X3503050418~2250X40200522~220X52003062~630X610300如果我们进一步来分析，例如某快餐店从上午11点到晚上10点需要的人数不一样，该公司全日制工人2人，每天工作8小时，其余为兼职人员，每天工作4小时，每小时4元钱。一个全日制工人每天从11点开始上班，工作4小时，休息1小时，然后再干4小时。一个全日制工人从下午1点上班，休息1小时，再干4小时。现在分析，要多少兼职工人。时间需要的总人数全日制1全日制2需要兼职方案11~12918X112~1918X21~29117X32~33111X43~4312X54~53111X65~6615X76~7121110X87~8121110X98~9716X109~10716X11设不同的时间段上班的人数分别为X1，X2，X3，X4，X5，X6，X7，X7，X9，X10，X11Obj：MinZ=X1+X2+X3+X4+X5+X6+x7+x8+x9+x10+x11S．T．X1≥8X1+X2≥8X1+X2+X3≥7X1+X2+X3+X4≥1X2+X3+X4+X5≥2X3+X4+X5+X6≥1X4+X5+X6+X7≥5X5+X6+X7+X8≥10X6+X7+X8+X9≥10X7+X8+X9+X10≥6X8+X9+X10+X11≥6X1，X2，X3，X4，X5，X6，X7，X8，X9，X10，X11≥0线性规划图解法由中学知识可知：Y=Ax+b是一条直线，同理：Z=70x1+120x2→x2=70/120x1-Z/120也是一条直线，以Z为参数的等值线。9x1+4x2

≤360→x1≤360/9-4/9x2

是直线x1=360/9-4/9x2下方的半平面线形的图解化区域是要封闭的,解在交点上3x1+10x2=3004x1+5x2=2009x1+4x2=360概念概念：1、可行解：满足所有约束条件的解。2、可行域：所有约束条件的交集，即各半平面的公共局部，也就是满足所有约束条件的解的集合，称为可行域。3、基解：约束条件的交点称为基解〔直观〕4、基可行解：基解当中的可行解。5、凸集：集合内任意两点的连线上的点均属于这个集合。如：实心球、三角形结论可行域是个凸集可行域有有限个顶点最优值在可行域的顶点上到达无穷多解的情形无界解情形无解情形线性规划的标准型代数式maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2………am1x1+am2x2+…+amnxn=bmxj

≥0j=1,2,…,n线性规划的标准型和式：maxZ=∑cjxj

∑aijxj=bii=1,2,…,mxj≥0

j=1,2,…,n线性规划的标准型向量式：maxZ=CX

∑pjxj=bi

i=1,2,…,m

xj≥0j=1,2,…,nC=(c1,c2,c3,…,cn)

X=(X1,X2,X3,…,Xn)T线性规划的标准型矩阵式：maxZ=CXAX=bX≥0b=(b1,b2,…,bm)T

a11

a12….a1nA=a21

a22…a2n………

am1

am2…amn非标准型转化举例之二minZ=x1+2x2-3x3maxZ’=x’1-2x2+3(x’3-x〞3)x1+x2+x3≤9-x’1+x2+x’3-x〞3+x4=9-x1-2x2+x3≥2x’1-2x2+x’3-x〞3-x5=23x1+x2-3x3=5-3x’1+x2-3(x’3-x〞3)=5x1≤0x2≥0x3无约束x’1≥0x2≥0x’3≥0x〞3≥0x4≥0x5≥0非标准型转化举例之二minZ=x1+2x2-3x3maxZ’=x’1-2x2+3(x’3-x〞3)x1+x2+x3≤9-x’1+x2+x’3-x〞3+x4=9-x1-2x2+x3≥2x’1-2x2+x’3-x〞3-x5=23x1+x2-3x3=5-3x’1+x2-3(x’3-x〞3)=5x1≤0x2≥0x3无约束x’1≥0x2≥0x’3≥0x〞3≥0x4≥0x5≥0例5(混合配方问题)：一家化工厂将四种原料A、B、C、D混合调配出三种产品，三种产品的销售价格分别为每公斤9元、8.5元和8元，各种原料A、B、C、D的供给量分别是1000、1000，750和800公斤；单价分别是每公斤5元、6元、4元和4.5元。该厂应如何安排生产才能使获得的利润最大？产品规格要求最小需求(公斤)最大需求(公斤)1含A不少于25%，C不多于20%100025002含A不少于50%，D不多于25%100不限3含A和B各不少于25%，不含C不限不限应用举例之二

标准型的特征目标函数极大化约束条件为等式决策变量非负应用举例之三例15.阶段投资问题兹有100万元闲钱，投资方向有四：

第四年第一年第二年第三年A工程110%B工程135%C工程125%D工程104%第五年各年投资什么工程，使第五年末资本总额为最大？目标函数极小化转为极大化：应用举例之三项目123455年末AX1AX2AX3AX4ABX2BCX3CDX1DX2DX3DX4DX5D拥有的资金1001.04X1D1.04X2D+1.1X1A1.04X3D+1.1X2A1.04X4D+1.1X3A1.04X5D+1.1X4A+1.35X2B+1.25X3C例1：(排产问题)某厂生产Ⅰ、Ⅱ、Ⅲ，每种产品要经过A、B两道工序加工，A工序可以在A1、A2设备上完成；B工序可以在B1、B2、B3上完成。产品Ⅰ可在A、B任何设备上加工；Ⅱ产品可在任何A上完成，但是只能在B1上完成B工序；Ⅲ产品只能在A2上完成A工序、B2上完成B工序，各种生产参数见表所示。如何规划，使该厂利润最大。设备产品设备有效台时满负荷时设备费用(元)ⅠⅡⅢA1A2B1B2B351079126841176000100004000700040006006425001566400原料费(元/件)单价(元/件)0.50.71.02.54.05.6例4(一维下料问题)：某厂有一批长度为7.4m的钢管原材料(数量充分多)，今为制造零件要将它们截成长度为2.9m，2.1m，1.5m的管料，需要量都是200根，问应如何下料，使用的原材料最少？方案123456782.9120101002.1002211301.531203104合计7.47.37.27.16.66.56.36料头00.10.20.30.80.91.11.4解：设每种方案下料根数为X1，X2，X3，X4，X5，X6，X7，X8Obj：MinZ=X1+X2+X3+X4+X5+X6+X7+X8S．T．X1+2x2+x4+x6=2002x3+2x4+x5+x6+3x7=2003x1+x2+2x3+3x5+x6+4x8=200x1=60;x2=20;x4=100二维下料问题：平面下料问题三维下料问题：运输装配问题第三章对偶问题与灵敏度分析要求：了解LP对偶问题的实际背景了解对偶问题的建立规那么与根本性质掌握对偶最优解的计算及其经济解释掌握LP的灵敏度分析理解计算机输出的影子价格与灵敏度分析的内容3.1对偶问题3.1.1对偶问题的提出回忆例题1：现在A、B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？产品A产品B资源限制劳动力设备原材料9434510360200300单位利润70120对偶模型设每个工时收费Y1元，设备台时费用Y2元，原材料附加费Y3元。出租收入不低于生产收入：9y1+4y2+3y3≥704y1+5y2+10y3≥120目标：ω=360y1+200y2+300y3出租收入越多越好？至少不低于某数原问题与对偶问题之比较原问题：对偶问题：maxZ=70X1+120X2minω=360y1+200y2+300y3

9X1+4X2≤3609y1+4y2+3y3

≥70

4X1+5X2

≤200(3.1)4y1+5y2+10y3

≥120(3.2)3X1+10X2

≤300y1≥0,

y2≥0,

y3≥0X1≥0X2≥0对偶规那么原问题一般模型：对偶问题一般模型：maxZ=CXminω=YbAX

≤bYA≥CX≥0Y≥0对偶规那么原问题有m个约束条件，对偶问题有m个变量原问题有n个变量，对偶问题有n个约束条件原问题的价值系数对应对偶问题的右端项原问题的右端项对应对偶问题的价值系数原问题的技术系数矩阵转置后为对偶问题系数矩阵原问题的约束条件与对偶问题方向相反原问题与对偶问题优化方向相反对偶规那么原问题对偶问题目标函数maxmin目标函数约束条件≤≥变量≥≤=无约束变量符号≥≥约束条件≤≤无约束=对偶规那么简捷记法原问题标准那么对偶问题标准原问题不标准那么对偶问题不标准例题2maxω=7y1+4y2-2y3minZ=3x1+2x2-6x3+x52y1+y2-y3≤32x1+x2-4x3+x4+3x5≥7y1+3y3≤2x1+2x3-x4≤4-4y1+2y2≤-6-x1+3x2-x4+x5=-2y1-y2-y3≥0x1,x2，x3≥0;x4≤0;x5无限制3y1+y3=1y1≥0,y2≤0,y3无约束线性规划习题例8(综合应用例)：某工厂采用研磨和钻孔两种加工工艺生产五种产品，P1、P2、P3、P4、P5。扣除本钱后，每单位产品可获得的利润以及加工过程需要消耗的资源见下表P1P2P3P4P5利润550600350400200研磨1220——2515钻孔10816————人工2020202020产品P2的最低需求和最高需求分别为10个和100个单位，产品P4的最低需求和最高需求分别为20和150个单位，其余产品的产量无限制。该厂有九台磨床和六台钻床，每周工作6天，每天两班，每班8小时。另用24名工人进行装配，每人每天一斑。为了获取最大的总利润，试求一周内每种产品各应生产多少？进一步答复下面的问题(1)这家工厂还有资源剩余吗？如果有的话，是哪种资源？有多少？分析：9台磨床，每周提供的机时9×6×8×2=864台时6台钻床，每周提供的机时6×6×8×2=576台时24名工人，每周提供的人工24×6×8×1=1152小时；Obj:MaxZ=550x1+600x2+350x3+400x4+200x5s.t.12x1+20x2+25x4+15x5≤86410x1+8x2+16x3≤57620x1+20x2+20x3+20x4+20x5≤1152x2≥10x2≤100x4≥20x4≤150x1,x2,x3,x4,x5≥0线性规划习题例8(综合应用例)：某工厂采用研磨和钻孔两种加工工艺生产五种产品，P1、P2、P3、P4、P5。扣除本钱后，每单位产品可获得的利润以及加工过程需要消耗的资源见下表P1P2P3P4P5利润550600350400200研磨1220——2515钻孔10816————人工2020202020产品P2的最低需求和最高需求分别为10个和100个单位，产品P4的最低需求和最高需求分别为20和150个单位，其余产品的产量无限制。该厂有九台磨床和六台钻床，每周工作6天，每天两班，每班8小时。另用24名工人进行装配，每人每天一斑。为了获取最大的总利润，试求一周内每种产品各应生产多少？进一步答复下面的问题(1)这家工厂还有资源剩余吗？如果有的话，是哪种资源？有多少？分析：9台磨床，每周提供的机时9×6×8×2=864台时6台钻床，每周提供的机时6×6×8×2=576台时24名工人，每周提供的人工24×6×8×1=1152小时；Obj:MaxZ=550x1+600x2+350x3+400x4+200x5s.t.12x1+20x2+25x4+15x5≤86410x1+8x2+16x3≤57620x1+20x2+20x3+20x4+20x5≤1152x2≥10x2≤100x4≥20x4≤150x1,x2,x3,x4,x5≥0QM的分析结果当影子价格为0时,说明资源有剩余.增加资源对目标可能没有影响数字为正时,增加这个约束的资源,会带来目标值的相应变化负值表示?QM的分析结果当影子价格为0时,说明资源有剩余.增加资源对目标可能没有影响数字为正时,增加这个约束的资源,会带来目标值的相应变化负值表示?第四章运输问题本章要求：掌握运输问题的数学模型掌握运输问题的求解方法化产销不平衡问题为平衡问题学会用计算机求解

4.1运输问题的数学模型运输问题一般表述为：某企业有m个产地〔生产厂〕Ai，其产量分别为ai,i=1,2,…m,n个销地〔销售商〕Bj，其销售量分别为bj,j=1,2,…n,从Ai到Bj的每单位物资的运费为Cij.要求拟定总运费最小的调运方案。运输表.

销地产地B1B2…Bn产量A1C11C12…C1na1A2C21C22…C2na2………………AnCm1Cm2…Cmnam销量b1b2…bn运输问题的数学模型设从Ai到Bj的运输量为xij,〔假定产销平衡〕那么总运费：minZ=∑∑Cijxij产量约束：∑xij=aii=1,2,…m,销量约束：∑xij=bjj=1,2,…n,非负性约束：xij≥0例(产量销量平衡的问题)：有三个产地A1、A2、A3、四个销售地B1、B2、B3、B4，由不同的产地到不同的销售地的运输价格见表所示。试求如何调运使总体的运输本钱最低？B1B2B3B4产量A1A2A3873214751924964销量3245(2)根本的产销平衡模型设Xij表示由I地运到j地的量Obj：MinZ=8X11+7X12+3X13+2x14+4X21+7X22+5X23+1X24+2X31+4X32+9X33+6X34S．T．X11+X12+X13+X14=1X21+X22+X23+X24=9X31+X32+X33+X34=4(产量)X11+X21+X31=3X12+X22+X32=2(需求)X13+X23+X33=4X14+X24+X34=5专业软件求解结果总本钱=1×3+1×4+3×5+5×1+2×2+2×4=39例(产量大于销量的问题)：有两个产地A1、A2；两个销售地B1、B2。由不同的产地到不同的销售地的运输价格见表所示。试求如何调运使总体的运输本钱最低？B1B2产量A1A2871479销量32(3)产大于销的模型解：加多一个需求地配成平衡式B1B2B3产量A1A287014709销量325专业软件求解结果总本钱=3×4+2×7=26Destination3的运输量实际是不用运输的，也就是就地库存量。例(产量小于销量的问题)：有两个产地A1、A2，两个销售地B1、B2。由不同的产地到不同的销售地的运输价格见表所示。试求如何调运使总体的运输本钱最低？B1B2产量A1A2872473销量19(4)销大于产的模型解：加多一个假想的生产地地配成平衡式B1B2产量A1A2A3873472MM5销量19专业软件求解结果总本钱=3×7+1×4+1×7=32Destination2的三行由于是由假想生产地供给的，实际上是供给不了的。例(产量销量不平衡的问题综合问题)：设三个煤矿供给四个地区。各个煤矿的产量、各地区的需求量以及从各个煤矿运送煤炭到各个地区的单价见表所示。试求出将产量分配完又使总的运费最低的煤炭调运方案。甲乙丙丁产量(万吨)A1613221750B1413191560C192023M50最低需求(万吨)3070010最高需求(万吨)507030不限转变成产量——销量平衡的问题甲甲’乙丙丁丁’产量(万吨)A16161322171750B14141319151560C19192023MM50DM0M0M050需求量(万吨)302070301050专业软件求解结果总本钱=50×13+20×13+10×15+30×15+0×14+20×13+10×15+30×15+30×19+20×19+30×0+20×0=2460Destination1、2是甲地，共获得50；Destination3的第一、二行的和是乙地获得的70；Destination4第四行是假想地供货，实际没有供，因此丙地为零；Destination6中第四行是由假想地供货，不能记入实际供货，因此Destination5、6是丁地情况，合计为40。(5)中间转运模型:在情况(2)的例子中添加假设干中间转运站产地转运站销地A1A2A3T1T2B1B2B3B4产地A1023∞48732A2304254751A3∞40332496转运站T1∞23072513T2354803224销地B18∞22309810B2774∞∞7096B33596310607B4326348970从A1直运B1运价为8,假设从A1先到T2,再到B1,运价为4+3=7.处理：所有产地、转运站、销地都可以看成产地，又可以看成销地。对各个转运站假设一个统一的转运量t,t=max(产量总和，需求量总和)，各个产地的产量为“各地产量+t〞,各个销地的销量为“各地销量+t〞.在该例中产量总和等于销量总和,等于14，所以t=14。所以各个产地的产量分别为：15，23，18；销地的需求量分别为：17、16、18、19转运站：14那么：运输表的结果为：销地产量A1A2A3T1T2B1B2B3B4产地A1023∞4873215A230425475123A3∞4033249618T1∞2307251314T235480322414B18∞2230981014B2774∞∞709614B3359631060714B432634897014销量141414141417161819例(就地储存问题)：在下面的运输问题中，假设产地i有一个单位的物质未运出，那么将发生储存费用。假定产地1、2、3的单位物质储存费用分别为5、3、4。又假定产地2的物质至少运出35个单位，产地3的物质至少运出28个单位，试求此运输问题的最优调运方案。产地B1B2B3产量123130235440336230运输量302525(6)特殊要求安排的模型产地B1B2B3B4产量123153022’354M352”3543533’362M283”36242运输量30252520例1：某机床厂在年初签定了生产一批同型号机床的合同。合同要求该厂分别于当年四个季度末交货。四个季度正常生产的能力与单位本钱，以及按合同应当交货的台数见表所示。在第三季度和第四季度可以安排加班生产，加班生产能力为每季度8台，但生产本钱比正常高出3万元，另外如果生产出来的机床当季度不交货，那么每台每季度需要支付0.12万元的储存保养费。作出一个完成交货合同并使全年生产费用最小的生产方案。季度正常生产能力/台单位成本/万元交货台数/台加班生产能力/台13010.552523210.83032011.015842811.0458(8)可以转化为运输问题的模型12345产量第一季度(正常)10.5510.6710.7910.91030第二季度(正常)M10.810.9211.04032第三季度(正常)MM1111.12020第三季度(加班)MM1414.1208第四季度(正常)MMM11.1028第四季度(加班)MMM14.108第一季度(正常)2530154511请自己分析排产结果问题举例某集装箱运输公司，箱型标准体积24m3，重量13T,现有两种货物可以装运，甲货物体积5m3、重量2T、每件利润2000元；乙货物体积4m3、重量5T、每件利润1000元，如何装运获利最多？maxZ=2000x1+1000x25x1+4x2≤242x1+5x2

≤13x1.x2

≥0且为整数解此LP问题，得：X1=4.8，X2=0显然不是可行解整数规划图解法x2x11234567231BA图解法的启示A〔4.8，0〕点是LP问题的可行解，不是IP问题的可行解，B〔4，1〕才是IP的最优解纯整数规划的可行解就是可行域中的整数点非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不阻碍整数规划问题的优化IP问题的最优解不优于LP问题的最优解6.2分枝定界法思路：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解例1.maxZ=2000x1+1000x25x1+4x2≤242x1+5x2

≤13x1.x2

≥0且为整数解：先不考虑整数要求，解相应的LP问题，得：x1=4.8x2=0Z=9600不是可行解Z=9600是IP问题的上界，记为：Z=9600分枝定界法〔续〕X1=4.8不符合要求，切掉4—5之间的可行域，可行域变成两块，即原有约束条件再分别附加约束条件x1

≤4和x1≥5原问题分解为两个maxZ=2000x1+1000x2maxZ=2000x1+1000x25x1+4x2≤245x1+4x2≤242x1+5x2

≤13(IP1)2x1+5x2

≤13(IP2)x1

≤4x1≥5x1.x2

≥0且为整数x1.x2

≥0且为整数分枝定界法〔续〕不考虑整数要求，解相应LP问题。解IP1得：x1=4,x2=1z=9000解IP2得：无可行解此时可以断定IP问题的下界为9000，记为Z=9000٭由于目前的分枝末梢最大值是9000，故IP问题的上界便是9000。由于Z=Z，此时已得IP问题的最优解，即x1=4,x2=1,Z=90006.30—1规划问题某些特殊问题，只做是非选择，故变量设置简化为0或1，1代表选择，0代表不选择。例4.600万元投资5个工程，求利润最大的方案？项目投资额项目收益约束条件210160

中选1项300210

之中选1项15060选必先选13080260180求解0—1规划的隐枚举法例4解：0当工程未被选中1当工程被选中maxZ=160x1+210x2+60x3+80x4+180x5210x1+300x2+150x3+130x4+260x5≤600X1+x2+x3=1X3+x4=1x5≤x1Xj=0或1j=1，2,…,5增加过滤条件：160x1+210x2+60x3+80x4+180x5≥240建模：设xj=X5-X1≤0的方式处理QM的分析Module\mixedintegerprogram参数输入QM的分析结果1的方案是可选择的用隐枚举法解例4：(x1,x2,x3,x4,x5〕Z值（1，0，0，1，0）240（1，1，1，1，1）X（1，1，1，1，0）X（1，1，1，0，1）X（1，1，1，0，0）X（1，1，0，1，1）X（1，1，0，1，0）X（1，1，0，0，1）X（1，1，0，0，0）

X（1，0，1，1，1）X（1，0，1，1，0）X（1，0，0，1，1）

420………..例2〔本钱最低〕：有四个人分别做四件不同的事，各自的效率不一样，具体情况见表所示。如何分配工作，使整体的效率最高？ABCD甲917167乙1271416丙8171417丁791196.4指派问题设Xij表示i人做j事,丙下岗甲—D乙—B丁—C戊—AObj：MinZ=9X11+17X12+16X13+7x14+12X21+7X22+14X23+16X24+8X31+17X32+14X33+17X34+7X41+9X42+11X43+9X44S．T．X11+X12+X13+X14=1X21+X22+X23+X24=1X31+X32+X33+X34=1(一个人做一件事)X41+X42+X43+X44=1X11+X21+X31+X41=1X12+X22+X32+X42=1(一件事一个人做)X13+X23+X33+X43=1X14+X24+X34+X44=1这是个特殊的运输问题，每个产地的产量为1，每个需求地的需求量也为1专业软件求解结果总本钱=1×7+1×7+1×8+1×11=33六、指派问题例1〔本钱最低〕：有五个人分别做四件不同的事，各自的效率不一样，具体情况见表所示,为每个人完成需要的工作时间。如何分配工作，使整体的效率最高？ABCDE甲9171670乙12714160丙81714170丁791190戊36890

设Xij表示i人做j事，丙下岗甲—D乙—B丁—C戊—AObj：MinZ=9X11+17X12+16X13+7x14+12X21+7X22+14X23+16X24+8X31+17X32+14X33+17X34+7X41+9X42+11X43+9X44S．T．X11+X12+X13+X14=1X21+X22+X23+X24=1X31+X32+X33+X34=1(一个人做一件事)X41+X42+X43+X44=1X11+X21+X31+X41=1X12+X22+X32+X42=1(一件事一个人做)X13+X23+X33+X43=1X14+X24+X34+X44=1此局部使用linerprogram去做用的分析，用assignment是不要这样分析的QM的分析QM\module\assignment数据可以在excel或word里复制进去QM的分析结果这个人是没有工作的这些人工作工序名称ABCDEFGHI紧前工序——ABBC、DC、DE、FG工序时间4667597481246357A4C6B6D7G7F9E5I8H404622282013案例2：工程的工期是多少，工程经理主要控制哪些工作？ABCDEFGHI0510152025有搭接情况的网络参数计算设计110建造230安装与调试320FS5SS150101545305001015453050

有搭接情况的网络参数计算A130B220C310FF5SF150301535203003015352030有搭接情况的网络参数计算

(练习)设计110建造240安装与调试320FS5SS15网络图绘制案例讨论

—某软件系统开发网络图绘制(学生练习)序号工作名称紧前工作1问题界定—2研究现有系统13确定用户需求14逻辑系统设计35实体系统设计26系统开发4,57系统测试68转换数据库4,59系统转换7,8网络图绘制案例讨论(续)假设上述工作关系中，存在如下搭接关系：“3.确定用户需求〞工作开始4天之后，“4.逻辑系统设计〞工作才可以开始。“7.系统测试〞工作完成6天之后“9.系统转换〞工作才可以完成。在网络图中如何表示上述信息呢？时间参数计算(练习)A3E8C7F6D4B2G5

代号时间例如：有搭接情况的网络参数计算(练习)A3E8C7F6D4B2G5

代号时间例如：SS4FS8FF3策略市场乐观悲观等可能折中(0.3)010203040000000000010-105050505050-1038820-2040100100100100-20641630-303090150150150-30782440-402080140200200-408032不确定性决策:某工厂是按批生产产品并按批出售，每件产品的本钱为30元，批发价格为35元。假设每月生产的产品当月销售不完，那么每件损失1元，生产批量是10件，最大的月生产能力为40件。这时决策者应如何决策？策略市场损失01020304000501001502002001010050100150150202010050100100303020100505040403020100402．最小时机损失准那么策略市场期望值0102030