运筹学复习.ppt

《运筹学复习.ppt》由会员分享，可在线阅读，更多相关《运筹学复习.ppt（115页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学复习运筹学复习第一章 线性规划模型和单纯形法q线性规划问题一般模型目标函数：max，min约束条件：,=,变量符号：0,unr,0q线性规划的标准形式目标函数：min约束条件：=变量符号：0qq 非标准形式转化为标准形式非标准形式转化为标准形式 极大化目标函数转化为极小化：极大化目标函数转化为极小化：目标函数系数变号目标函数系数变号 约束条件是不等式转化为等式：约束条件是不等式转化为等式：“”“”约束约束 加上松弛变量加上松弛变量 “”“”约束约束 减去松弛变量减去松弛变量 变量没有符号限制转化为变量非负：变量没有符号限制转化为变量非负：没有符号限制的变量用两个非负变量的差表示没有符号限

2、制的变量用两个非负变量的差表示例如例如:max z=3x1+4x2-2x3+5x4:max z=3x1+4x2-2x3+5x4s.ts.t 4x1-x2+2x3-x4=4 4x1-x2+2x3-x4=4 x1+x2+3x3-x414 x1+x2+3x3-x414 -2x1+3x2-x3+2x43 -2x1+3x2-x3+2x43x10,x22,x30,x4:unrx10,x22,x30,x4:unr线性规划的图解画约束直线确定满足约束条件的半平面所有半平面的交集凸多边形线性规划的可行域画两条目标函数等值线确定目标函数优化的方向平行移动目标函数等值线得到线性规划的最优解qq线性规划问题的概念线性

3、规划问题的概念基：设标准形式的基：设标准形式的LPLP问题的约束方程组的秩为问题的约束方程组的秩为MM，BB是系数矩是系数矩阵阵AA中的中的MM阶满秩子矩阵，则称阶满秩子矩阵，则称BB是该是该LPLP问题的一个基。问题的一个基。基变量：基变量：BB中的每一个列向量成为基向量，对应的变量为基变中的每一个列向量成为基向量，对应的变量为基变量，共有量，共有MM个。个。非基变量：非基变量：BB以外的列向量称为非基向量，对应变量成为非基以外的列向量称为非基向量，对应变量成为非基变量，共有变量，共有N-MN-M个。个。基础解：对应基基础解：对应基BB，令所有的非基变量为零，求解约束方程组令所有的非基变量为

4、零，求解约束方程组AX=bAX=b，可惟一得出基变量的一组值，这样得到的可惟一得出基变量的一组值，这样得到的NN个变个变量的一组解成为一个量的一组解成为一个“基础解基础解”。基础可行解：如果一个基础解中的所有变量都大于或等于基础可行解：如果一个基础解中的所有变量都大于或等于00，则，则称这个基础解为称这个基础解为“基础可行解基础可行解”。退化解：基解中的非零分量的个数小于退化解：基解中的非零分量的个数小于MM个时，即某个基变量个时，即某个基变量为零时，此时为退化解。为零时，此时为退化解。qq线性规划的基本定理线性规划的基本定理 线性规划的基础可行解就是可行域的极点。线性规划的基础可行解就是可行

5、域的极点。线性规划的基本概念线性规划的基本概念min z=x1+2x2s.t.x1+x2 4(1)-x1+x22(2)x2 5(3)x1,x2 0OABCDEFG41234123x1x2x3=0 x4=0 x2=0 x1=0 x5=0引进松弛变量x3,x4,x5min z=x1+2x2s.t.x1+x2+x3 =4 -x1+x2 -x4=2 x2 +x5=5 x1,x2 x3,x4,x50基础解O A B C D E F GBEF四边形B E F G基础可行解可行域目标函数等值线.最优解B5GqA不是可行解，是由于变量（）0。qC不是可行解，是由于变量（）0，则xn+i=0如果xn+i0，则w

6、i=0边际利润大于0的资源，在最优生产计划条件下没有剩余wm+jxj=0如果wm+j0，则xj=0如果xj0，则wm+j=0最优生产计划条件下有剩余的资源，其边际利润等于0差额成本大于0（机会成本大于利润）的产品，不安排生产安排生产的产品，差额成本等于0（机会成本等于利润）q灵敏度分析 主要分析当所给问题数据改变时，原有解的可行性和最有优性有何变化。v目标函数中系数的变化v约束条件右端常数的变化v约束条件左端系数的变化v引入新的变量v引入新的约束 利用对偶单纯形法求解Min z=4x1+6x2+18x3S.t x1+3x3 3 x2+2x3 5 x1,x2,x3 0第三章 运输问题q 运输问题

7、的模型q运输问题的表格表示q 运输表中一个基必须具备的特点1、一个基应占表中的m+n-1格2、构成基的同行同列格子不能构成闭回路3、一个基在表中所占的格子应包括表的每行和每列q初始基可行解的求法v西北角法v最小元素法q最优解的获得123411291114120271513823031065418012585110210运输问题运输问题12341129111412027151382303106541801258511021012510508535018003030075357507500用最小元素法得到一个初始基础可行解12341129111412027151382303106541801258

8、511021012585180303575-7求非基变量x11的检验数12341129111412027151382303106541801258511021012585180303575-7-8求非基变量x14的检验数12341129111412027151382303106541801258511021012585180303575-7-8-4求非基变量x22的检验数12341129111412027151382303106541801258511021012585180303575-7-8-6-7求非基变量x31的检验数1234112911141202715138230310654180

9、1258511021012585180303575-7-8-4-7+1求非基变量x32的检验数12341129111412027151382303106541801258511021012585180303575-7-8-4-7+1+4求非基变量x33的检验数12341129111412027151382303106541801258511021012585180303575-7-8-6-7+1+4x33=75进基，x23=0离基，x24=30+75=105，x34=180-75=105确定进基变量和离基变量1234112911141202715138230105310654180751258

10、51102101258510535-3求非基变量x11的检验数123411291114120271513823010531065418075125851102101258510535-3-4求非基变量x14的检验数123411291114120271513823010531065418075125851102101258510535-3-4-8求非基变量x22的检验数123411291114120271513823010531065418075125851102101258510535-6-4-4-8求非基变量x23的检验数12341129111412027151382301053106541

11、8075125851102101258510535-5-4-4-7-8求非基变量x31的检验数123411291114120271513823010531065418075125851102101258510535-5-4-4-7-3-8得到最优解：x12=85,x13=35,x21=125,x24=105,x33=75,x34=105 min z=3660求非基变量x32的检验数q不平衡运输问题v发大于收，则虚设收地，运价为零v发小于收，则虚设发地，运价为零q灵敏度分析v基变量的运价调整v非基变量的运价调整物流配送案例腾飞电子仪器厂在大连和广州有两个分厂生产同一种仪器。大连分厂每月生产400

12、台广州分厂每月生产600台。该公司在上海和天津有两个物流配送服务网点，负责对南京、济南、南昌、青岛四个城市的仪器进行配送供应。另外，因为大连距离青岛较近，公司同意大连分厂向青岛直接供货。这些城市间的每台仪器的运输费用标在两个城市间的弧上，单位为百元。公司应该如何调运仪器可使总运输费用最低?广州600南昌350天津南京200济南150大连400青岛300上海2446362561433多工厂模型一家公司有A和B两个工厂,每个工厂生产两种同样的产品,一种是普通的,每件利润10元;一种是精制的,每件利润15元.两厂采用相同的加工工艺:研磨和抛光.A厂每周的研磨能力为80小时,抛光能力为60小时;B厂每

13、周的研磨能力为60小时,抛光能力为75小时.两厂生产各类单位产品所需的研磨和抛光工时(以小时计)如表所示.另外,每类每件产品都消耗4公斤的原材料,该公司每周可获得原材料120公斤.问:应该如何制定生产计划?工厂AB产品普通精制普通精制研磨4253抛光2556分析 先假定每周分配原料给A厂75公斤,B厂45公斤.设x1为A厂的普通产品产量;x2为A厂的精制产品产量;x3为B厂的普通产品产量;x4为B厂的精制产品产量.A厂模型:Maxz=10 x1+15x2S.t 4x1+4x2 75(原料A)4x1+2x2 80(研磨A)2x1+5x2 60(抛光A)X1,x2 0最优解:(11.25,7.5,

14、利润225)剩余20小时的研磨时间B厂模型:Maxz=10 x3+15x4S.t 4x3+4x4 45(原料B)5x3+3x4 60(研磨B)5x3+6x4 75(抛光B)X3,x4 0最优解:(11.25,3.75,利润168.5)剩余26.25小时的研磨时间和7.5小时的抛光工时.假设建立一个公司模型,让模型去确定原材料的分配:Max z=10 x1+15x2+10 x3+15x4S.t 4x1+4x2+4x3+4x4 120 4x1+2x2 80 2x1+5x2 60 5x3+3x4 60 5x3+6x4 75 x1,x2,x3,x4 0最优解:X1=9.17,x2=8.33,x4=12

15、.5,z=404.15多周期动态生产计划问题考虑某厂配套生产产品问题.今年头四个月收到的订单数量分别为3000,4500,3500和5000件.该厂正常生产每月可生产产品3000件,利用加班还可生产1500件.正常生产成本为每件5000元,加班生产还要追加1500元的成本,库存成本为每件每月200元.问该厂如何组织生产才能使生产成本最低?第五章 目标规划q概念v偏差变量：实际值与目标值之间差距的变量表示，通常以di+di-表示，分别为正、负偏差变量，且有di+0、di-0，di+di-=0 v优先因子：描述问题中目标重要性程度的差别，一般用pi表示，通常i值越小，代表的优先程度越高。v目标约束

16、：用来描述允许对给定目标值有一定偏离程度的限制条件。q目标规划模型的特点1、引进正负偏差变量 2、模型中必须有目标约束 3、目标函数为偏差变量的表达式 4、以优先级因子描述目标的重要性程度q目标规划的解法 单纯形法：按单纯形法求解一搬目标规划问题的满意解。求解时需按优先级的顺序进行逐步优化。v各目标具有相同等级的目标规划v各目标具有不同优先等级的目标规划v各目标具有赋权优先等级的目标规划 第六章 整数规划q整数规划的基本概念v变量的取值为整数的LP问题为整数规划问题。q 整数规划的一般模型q整数规划的解法v 割平面法（纯整数规划）v 分支定界法人力资源安排 某超市物流配送中心，星期六有4个装卸

17、工人当班要分别指派他们去完成4项不同的装卸工作每人做各项工作所取得的利润如下表所示应如何合理地指派这4人的工作，才能使配送中心获得的利润最大。任务人员ABCD甲66697275乙70747386丙77686770丁78727468v点与（有向）边 每一条边和两个节点关联，一条边可以用两个节点的标号表示（i，j）jiv路径（Path）前后相继并且方向相同的边序列 P=(1,2),(2,3),(3,4)42314231v网络由点和边组成第七章 网络规划q 图的基本概念v连通图 任意两个节点之间至少有一条链的图称为连通图24351v圈(Cycle)起点和终点重合的链称为圈 =(1,2),(2,4),

18、(3,4),(1,3)圈中各条边方向不一定相同4231v树(Tree)无圈的连通图称为树 树中只与一条边关联的节点称为悬挂节点v 回路（Circuit）起点和终点重合的路径称为回路 =(1,2),(2,4),(4,1)回路中各条边方向相同4231v 链（Chain）前后相继并且方向不一定相同的边序列称为链 C=(1,2),(3,2),(3,4)4231q 树的性质v任何树至少有一个悬挂节点243512435124351v如果树的节点个数为m，则边的个数为m-1v树中任意两个节点之间只有唯一的一条链v在树的任意两个不相邻的节点之间增加一条边，则形成唯一的圈q 最小支撑树v由网络的所有节点（m个）

19、和网络的m-1条边组成的树称为网络的支撑树，构成支撑树的各边赋权之和最小的为最小支撑树。4231423142314231423142314231q 最小支撑树的算法vKruskal算法vPrim算法q最短路问题 vD氏算法q最短链问题q网络上的最大流问题q最小割集1254367最大流问题最大流问题36112743847125uij求从1到7的最大流125436736112743847125uij检查每一条边不饱和的方向，用 表示x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 =min12,26,67=min3,6,12=3 =min13,35,5

20、7=min11,4,5=4125436736112743847125uij寻找从1到7的不饱和链，用 表示，求出每一条不饱和链的间隙 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0=3=6=12=11=4=5125436736112743847125uij增加不饱和链的流量检查每一条边不饱和的方向，用 表示x=3x=3x=4x=0 x=0 x=0 x=0 x=0 x=3x=4x=4x=0f=7f=7寻找从1到7的不饱和链，用 表示，求出每一条不饱和链的间隙 125436736112743847125uijx=3x=3x=4x=0 x=0 x=0

21、x=0 x=0 x=3x=4x=4x=0=7f=7f=7=min13,34,46,67=min7,3,4,8=3=3=4=9125436736112743847125uij增加不饱和链的流量检查每一条边不饱和的方向，用 表示x=3x=3x=7x=0 x=0 x=3x=3x=0 x=6x=4x=4x=0f=10f=10寻找从1到7的不饱和链，用 表示，求出每一条不饱和链的间隙 125436736112743847125uijx=3x=3x=7x=0 x=0 x=3x=3x=0 x=6x=4x=4x=0f=10f=10 =min13,32,26,67=min4,2,3,6=2=4=2=3=6增加不

22、饱和链的流量检查每一条边不饱和的方向，用 表示125436736112743847125uijx=3x=5x=9x=2x=0 x=3x=3x=0 x=8x=4x=4x=0f=12f=12寻找从1到7的不饱和链125436736112743847125uijx=3x=5x=9x=2x=0 x=3x=3x=0 x=8x=4x=4x=0f=12f=12已不存在从1到7的不饱和链。获得最大流，f=12X=1,3，X=2,4,5,6,7最小割集为(1,2),(3,2),(3,4),(3,5)，用 表示最小割集的容量为u12+u32+u34+u35=3+2+3+4=12123456782639584761

23、04117126最短路径问题最短路径问题求1到8的最短路径12345678263958476104117126w1=0X=1min0+2,0+6,0+3=min2,6,3=2，w2=212345678263958476104117126w1=0X=1,2min2+9,2+5,2+4,0+6,0+3=min11,7,6,6,3=3，w4=3w2=212345678263958476104117126w1=0w2=2X=1,2,4min2+9,2+5,2+4,0+6,3+7,3+6,3+10=min11,7,6,6,10,9,13=5，w3=6w4=312345678263958476104117

24、126w1=0w2=2X=1,2,3,4min2+9,2+5,6+8,3+6,3+10=min11,7,14,9,13=7，w6=7w4=3w3=612345678263958476104117126w1=0w2=2X=1,2,3,4,6min2+9,7+4,7+11,3+10=min11,11,18,13=11，w5=11w4=3w3=6w6=712345678263958476104117126w1=0w2=2X=1,2,3,4,5,6min11+12,7+7,7+11,3+10=min23,14,18,13=13，w7=13w4=3w3=6w6=7w5=11123456782639584

25、76104117126w1=0w2=2X=1,2,3,4,6,7min11+12,7+7,13+6=min23,14,19=14，w8=14w4=3w3=6w6=7w5=11w7=1312345678263958476104117126w1=0w2=2X=1,2,3,4,6,7,8min11+12,7+7,13+6=min23,14,19=14，w8=14w4=3w3=6w6=7w5=11w7=13w8=1412345678263958476104117126w1=0w2=2w4=3w3=6w6=7w5=11w7=13w8=14从1到8的最短路径为14，最短路径为12 6 8从1到其他节点的最

26、短路径如上图红线所示，其中到3和5的最短路径有两条。2511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短路径问题求从A到E的最短路径2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5251121410610413111239658105

27、2C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f

28、4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=82511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=142511214106104131112396581052C1C3D1A

29、B1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B22511214106104131112396581052C1C3D

30、1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优

31、决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1 （C1，D1）D12511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1 （C1，D1）D1 （D1，E）E从A到E的最短路径为19，路线为AB 2C1 D1 E 资源分配问题 4台设备，分配给A、B、C三个工厂，每个工

32、厂分配到不同数量的设备所能产生的效益（万吨）如下表所示。求设备的最优分配方案，使总效益最大。设备台数产生的效益（万吨）工厂A工厂B工厂C0000115129228282734042474505553动态规划模型工厂A工厂B工厂C k=1k=2k=3k=4状态变量xk：尚未分配的设备台数x2x3x4决策变量dk：每个工厂分配的设备台数d1d2d3x2=x1-d1阶段kx1x3=x2-d2x4=x3-d3决策允许集合Dk(xk)：分配台数dk的范围0d1 x10d2 x20d3 x3状态转移方程Dk(xk)：状态如何随上一状态以及决策变化阶段指标Vk(xk,dk)：每个工厂分配设备产生的效益v1(

33、x1,d1)v2(x2,d2)v3(x3,d3)最优指标函数fk(xk)fk(xk)=maxvk(xk,dk)+fk+1(xk+1)终端条件fn(xn)f4(x4)=0 x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*00000+0=00010100+0=0911099+0=9*20200+0=02721199+0=9202727+0=27*30300+0=04731299+0=9212727+0=27304747+0=47*40400+0=05341399+0=9222727+0=27314747+0=47405353+0=53*x3f3(x3)d3*

34、000191227234734534f3(x3)f4(x4)x4f4(x4)0010203040 x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*00000+0=00010100+9=9121101212+0=12*20200+27=27282111212+9=21202828+0=28*30300+47=47*470121212+27=39212828+9=37304242+0=4240400+53=53591131212+47=59*222828+27=55314242+9=51405555+0=55x3f3(x3)d3*00019122723473

35、4534f3(x3)x2f2(x2)d2*0001121228234704591f2(x2)f4(x4)=0 x1D1(x1)x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)d1*40400+59=59621131515+47=62*222828+28=56314040+12=52405050+0=50 x1f1(x1)d1*4621x2f2(x2)d2*0001121228234704591x3f3(x3)d3*000191227234734534最优解为：x1=4,d1*=1x2=x1-d1=3,d2*=0 x3=x2-d2=3,d3*=3x4=x3-d3=0即工厂A分配

36、1台，工厂B不分配，工厂C分配3台，最大效益为62万吨，设备没有剩余。背包问题一艘货轮载重量为1000吨，装载以下三种货物：货物A货物B货物C重量（吨/件）240320430价值（万元/件）354663单位重量价值0.1460.1440.147每种货物各装载多少件，使一船货物价值最高。x1240吨x2320吨x31000吨0件 1000吨0件 1000吨1件680吨2件360吨3件40吨1件760吨0件760吨1件440吨2件120吨2件520吨0件520吨1件200吨3件280吨0件280吨4件40吨0件40吨x1x2x310004040280120520200760280100036044

37、05206807601000排序排序列举各阶段可能的状态x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*4004000+0=000120012000+0=000200020000+0=000280028000+0=000360036000+0=000440044000+0=06311106363+0=63*520052000+0=06311906363+0=63*680068000+0=063112506363+0=63*760076000+0=063113306363+0=63*10000100000+0=0126215706363+0=6321401

38、26126+0=126*x3f3(x3)d3*40001200020000280003600044063152063168063176063110001262f3(x3)f4(x4)0 x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*4004000+0=000280028000+0=000520052000+63=63*63012004646+0=46760076000+63=63109114404646+63=109*21209292+0=9210000100000+126=126138316804646+63=10823609292+0=923401

39、38138+0=138*x2f2(x2)d2*400028000520630760109110001383f2(x2)x3f3(x3)d3*40001200020000280003600044063152063168063176063110001262x1D1(x1)x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)d1*10000100000+138=138144117603535+109=144*25207070+63=1333280105105+0=105440140140+0=140*最优解为：x1=1000，d1*=1，x2=x1-240d1*=760，d2*=1x3=x2-320d2*=440，d3*=1，x4=x3-430d3*=10f1(x1)=f1(1000)=144即货物A、B、C各装1件，最大价值为144万元。货轮装载量还剩余10吨。x2f2(x2)d2*400028000520630760109110001383x1f1(x1)d1*10001441