《线性规划理论与模型应用.ppt》由会员分享，可在线阅读，更多相关《线性规划理论与模型应用.ppt（21页珍藏版）》请在金锄头文库上搜索。
1、线性规划理论与模型应用北京工业大学应用数理学院北京工业大学应用数理学院束金龙束金龙 闻人凯闻人凯科学出版社科学出版社第五章 运筹模型应用主要内容5.1 排队模型排队模型5.2 选址问题选址问题5.3 对策论对策论5.4 统筹方法统筹方法5.1 排队模型排队模型排队问题和线性规划问题同属于运筹模型，排队模型是一个等排队问题和线性规划问题同属于运筹模型，排队模型是一个等待服务或等待处理的对象序列，如病人到医院门诊部看病、待服务或等待处理的对象序列，如病人到医院门诊部看病、客户到银行储蓄所办理存取等业务、在一个机床上加工几客户到银行储蓄所办理存取等业务、在一个机床上加工几个不同的部件等均是排队模型。
2、个不同的部件等均是排队模型。一一. .在一台机器上加工在一台机器上加工n种零件种零件在工厂生产中，往往要求零件在各道工序的滞留时间或平在工厂生产中，往往要求零件在各道工序的滞留时间或平均滞留时间达到最小。各零件以不同的次序进行加工，其均滞留时间达到最小。各零件以不同的次序进行加工，其滞留时间将相差很远，因此在生产之前应考虑加工次序。滞留时间将相差很远，因此在生产之前应考虑加工次序。零件的滞留时间零件的滞留时间= =等待加工时间等待加工时间+ +加工时间；加工时间；平均滞留时间平均滞留时间( (Mt)=)=各零件的滞留时间的总和各零件的滞留时间的总和/ /零件个数；零件个数；排排队队模模型型例例
3、5.1 车间有一台机床，计划加工车间有一台机床，计划加工6个零件，每个零件加个零件，每个零件加工完毕后立刻送到下一道工序加工，但尚未加工的工完毕后立刻送到下一道工序加工，但尚未加工的零件必须等待正在加工的零件，待其加工完毕后才零件必须等待正在加工的零件，待其加工完毕后才可以加工，各零件有关数据如下：可以加工，各零件有关数据如下：解：首先按自然顺序加工滞留时间和加工时间如下表所示解：首先按自然顺序加工滞留时间和加工时间如下表所示排排队队模模型型总滞留时间总滞留时间= =60+100+120+230+285+315=1110(分分)平均平均滞留时间滞留时间Mt= =1110/6=185(分分)对于
4、一般情况，若有对于一般情况，若有n个零件，各个零件加工时间分别为个零件，各个零件加工时间分别为J1, J2, Jn，则则Mt = J1+(J1+J2)+(J1+J2+Jn)/n = nJ1+(n-1) J2+2Jn-1+Jn/n显然可以证明，当显然可以证明，当J1J2 Jn时时Mt将达到最小，从而对将达到最小，从而对于此类问题的求解方法是首先对加工时间于此类问题的求解方法是首先对加工时间J1, J2, Jn进行排序，使其满足进行排序，使其满足J1J2 Jn，然后进行加工，然后进行加工，即依次加工所需时间少的零件。即依次加工所需时间少的零件。例例5.1的正确加工次序为：的正确加工次序为：3、6、
5、2、5、1、4，所需时间，所需时间 Mt =6*20+5*30+4*40+3*55+2*60+110/6=825/6=137.5相对于自然次序，平均滞留时间相对于自然次序，平均滞留时间(185)少少47.5分。分。排排队队模模型型例例5.2 设某机床必须完成设某机床必须完成5种零件的加工，有关数据如下种零件的加工，有关数据如下表，问应如何表，问应如何安排加工次序，使平均安排加工次序，使平均平均滞留时间平均滞留时间最少。最少。解：首先注意到各种零件加工前要有准备时间，因此同一解：首先注意到各种零件加工前要有准备时间，因此同一种零件要有准备时间，应放在一起加工，因此某个零种零件要有准备时间，应放在
6、一起加工，因此某个零件实际的总耗工时为件实际的总耗工时为零件零件i总耗工时总耗工时= =零件零件i件数件数* *每件加工时间每件加工时间+ +准备时间准备时间各零件总耗时为各零件总耗时为195，26，132，215，65；工序应为工序应为2，5，3，1，4，平均耗时为，平均耗时为 Mt =5*26+4*65+3*132+2*195+215/5=278.2分。分。排排队队模模型型二二. .在二台机器上加工在二台机器上加工n种零件种零件有时要求一批零件必须依次在两台机器上加工，而有时要求一批零件必须依次在两台机器上加工，而且在两台机器上的加工次序必须相同，即每个零件且在两台机器上的加工次序必须相同
7、，即每个零件必须先在第必须先在第1 1台机器上加工然后再在第台机器上加工然后再在第2 2台机器上加台机器上加工。工。例例5.3 设有设有5个零件，按工艺要求每个零件必须先在车床个零件，按工艺要求每个零件必须先在车床上切割然后再在钻床上打孔，其加工耗时如下表，上切割然后再在钻床上打孔，其加工耗时如下表，应如何安排工序，效率最高。应如何安排工序，效率最高。排排队队模模型型先看按先看按A、B、C、D、E顺序加工，用条形图表示如下顺序加工，用条形图表示如下显然如此顺序加工总耗时显然如此顺序加工总耗时9小时。从图中可看出小时。从图中可看出M1的结余的结余时间一定大于时间一定大于E在在M2的时间，当然希望
8、在的时间，当然希望在M2上耗时最短上耗时最短的零件放在最后；另一方面要使的零件放在最后；另一方面要使M2尽快进行工作状态，尽快进行工作状态，在在M1上耗时最短的零件应尽可能放在前边。上耗时最短的零件应尽可能放在前边。排序原则：求排序原则：求M1和和M2上耗时最小者：上耗时最小者：在在M1上，尽可能放在前边；上，尽可能放在前边；在在M2上，尽可能放在后边。上，尽可能放在后边。排排队队模模型型解：解：1) 寻找加工顺序寻找加工顺序首先画如下加工顺序表首先画如下加工顺序表在加工时间表中找耗时最小者，零件在加工时间表中找耗时最小者，零件B是是0.25，属于，属于M2，因此零件因此零件B放在最后加工；在
9、余下的放在最后加工；在余下的零件中找耗时最小零件中找耗时最小者，零件者，零件D是是0.5，属于，属于M1，零件零件D放在前边加工；再找放在前边加工；再找到的是到的是零件零件A是是0.5，属于，属于M2，放在后边加工；再找到的放在后边加工；再找到的是是零件零件C是是1.00，属于，属于M2，零件，零件C放在后边加工；最后加放在后边加工；最后加入入E，加工顺序表如下：加工顺序表如下：总耗时为总耗时为7.25+0.25=7.5，显然此值是最小值。，显然此值是最小值。排排队队模模型型2) 加工起讫时间表加工起讫时间表通常需要建立如下加工起讫时间表通常需要建立如下加工起讫时间表全部零件的加工时间是全部零
10、件的加工时间是7.5小时小时M1的的等待时间等待时间=7.5-7.25=0.25小时小时M2的等待时间的等待时间=2.5小时小时排排队队模模型型三三. .在在m台机器上加工台机器上加工n种零件种零件考虑一批零件必须依次在考虑一批零件必须依次在m台机器上加工时的情况，台机器上加工时的情况，设设tij为第为第i个零件在第个零件在第j台机器上加工的耗时，再设台机器上加工的耗时，再设xij为第为第i个零件在第个零件在第j台机器上加工开始时刻，则有台机器上加工开始时刻，则有(1)第第i个零件必须在第个零件必须在第j- -1台机器上加工结束后才可在第台机器上加工结束后才可在第j台机器上加工，即台机器上加工
11、，即 xi,j-1 + + ti,j-1 xij ( (i=1,2,n, j=2,3,m) )(2) 任意两个不同的零件任意两个不同的零件I、i在在第第j台机器上加工必须有一台机器上加工必须有一个先后，即个先后，即 xij + + tij xIj ( (iI) )(3) 目标函数各零件必须尽早在所有机器上完成，也就是目标函数各零件必须尽早在所有机器上完成，也就是尽早在尽早在第第m台机器台机器上完成上完成，即，即z=maxx1m + + t1m ，x2m + + t2m ，xnm + + tnm 尽可能小，也就是尽可能小，也就是 min z。排排队队模模型型此时的数学模型为此时的数学模型为min
12、maxx1m + + t1m ，x2m + + t2m ，xnm + + tnm s.t. s.t. xi,j-1 + + ti,j-1 xij ( (i=1,2,n, j=2,3,m) )xij + + tij xIj ( (iI) ) ( (i,I=1,2,n, j=2,3,m) )xij 0 ( (i=1,2,n, j=2,3,m) )此问题求解是非常困难的。此问题求解是非常困难的。排排队队模模型型四四. .在三台机器上加工在三台机器上加工n种零件种零件考虑考虑n种零件必须依次在种零件必须依次在3台机器上加工时的情况，台机器上加工时的情况，当满足以下当满足以下2个条件之一时，问题可转化为
13、个条件之一时，问题可转化为2台机器台机器的问题。的问题。(1) 在在M1最小加工时间不小于在最小加工时间不小于在M2上最大加工时间，即上最大加工时间，即 minti1 maxti2 ( (i=1,2,n) )(2) 在在M3最小加工时间不小于在最小加工时间不小于在M2上最大加工时间，即上最大加工时间，即 minti3 maxti2 ( (i=1,2,n) )具体实现方法是：将第具体实现方法是：将第i个零件在个零件在M1，M2上的加工时间相上的加工时间相加看作第加看作第i个零件在新机器个零件在新机器N1上的加工时间；在上的加工时间；在M2，M3上的加工时间相加看作第上的加工时间相加看作第i个零件
14、在新机器个零件在新机器N2上的上的加工时间加工时间，如此就转化为两台机器的问题。如此就转化为两台机器的问题。排排队队模模型型例例5.6 设有设有5个零件必须依次在个零件必须依次在3台机器上加工，各零件有台机器上加工，各零件有关数据如下，是确定最佳加工次序。关数据如下，是确定最佳加工次序。解：显然解：显然 minti3=5 maxti2，转化为转化为2台机器问题台机器问题 排排队队模模型型2台机器问题的最佳加工次序台机器问题的最佳加工次序为为BEACD全部零件的加工时间是全部零件的加工时间是42小时小时M1的的等待时间等待时间=42-29=13小时小时M2的等待时间的等待时间=15+(42-32
15、)=25小时小时M3的等待时间的等待时间=5小时小时5.2 选址问题选址问题日常生活中存在大量最优选址问题，比如销售点的选址、消防日常生活中存在大量最优选址问题，比如销售点的选址、消防站的选址、急救站的选址等等。这些问题可描述为：有一站的选址、急救站的选址等等。这些问题可描述为：有一些服务对象，建立一些服务点为这些对象服务，服务点建些服务对象，建立一些服务点为这些对象服务，服务点建在何处最为便利就是所谓的最优选址问题。在何处最为便利就是所谓的最优选址问题。一.一.交通图上的选址问题交通图上的选址问题二.二.1. 1. 两点间的选址问题两点间的选址问题三.三.例例5.7 设某物资有设某物资有A、
16、B两个产地，相距两个产地，相距30公里，公里，A地产量地产量200吨，吨，B地产量地产量100吨，要求在连接吨，要求在连接AB的的公路上公路上(包括包括A、B两地两地)选择地点，建立一个加工厂，问建在何处总运费选择地点，建立一个加工厂，问建在何处总运费最小？最小？四四.解：以解：以A地为地为数轴原点，数轴原点，AB连线为数轴，设运费为连线为数轴，设运费为k元元/公里，加工厂建在公里，加工厂建在x处，则总运费为处，则总运费为选选址址问问题题S(x) = 200kx+100k(30-x)= 3000k+100kx显然显然x = 0时时S(x)取取最小值，即最小值，即S(0)=3000k，所以加工厂
17、建所以加工厂建在在A地。此种情况下，最优选址遵守地。此种情况下，最优选址遵守“小往大靠小往大靠”原则，与原则，与运价、距离无关。运价、距离无关。2. 树形图上的树形图上的选址问题选址问题将两点间的选址问题推广到将两点间的选址问题推广到树形图上。树形图上。例例5.8 设某物资有设某物资有7个产地，分个产地，分布图所示，要求在交通图上选布图所示，要求在交通图上选择一地建立加工厂，加工各地择一地建立加工厂，加工各地所运物资，问建在何处运价最所运物资，问建在何处运价最省？省？选选址址问问题题将此问题简化为两点选址问题，按将此问题简化为两点选址问题，按“小往大靠小往大靠”原则选原则选址。址。(1)将将3
18、、4之间的连线断开，将断开后的两部分看作两之间的连线断开，将断开后的两部分看作两点，点， 1、2、3的和是的和是400， 4、5 、6 、7的和是的和是430，按按“小往大靠小往大靠”原则选址应该原则选址应该4、5 、6 、7部分；部分；(2)将图重新在将图重新在4、5之间的连线断开，将断开后的两部之间的连线断开，将断开后的两部分看作两点，分看作两点， 1、2、3、4、6的和是的和是650， 5 、7的的和是和是180，按，按“小往大靠小往大靠”原则选址应该原则选址应该4所在的部所在的部分；分；(3)至此只有至此只有4、6两点，两点，重新在重新在4、6之间的连之间的连线断开，显然最后选线断开，
19、显然最后选在地点在地点4为最优选址。为最优选址。选选址址问问题题3. 中心选址问题中心选址问题例例5.9 现准备在现准备在v1,v7这七个这七个居民点居民点(如图如图)设立一个售票处，设立一个售票处，如何选址可使大家购票总距离如何选址可使大家购票总距离最小？最小？解：首先求出任意两个居民点之间的最短路数据表，标解：首先求出任意两个居民点之间的最短路数据表，标出任意一个居民点至其他居民点的最远距离出任意一个居民点至其他居民点的最远距离l(vi)和和总距离总距离L(vi) 。选选址址问问题题从表中可以看出，选择各居民点至从表中可以看出，选择各居民点至第第6居民点居民点的距离的距离之和最小而且最远距离也是最小的。之和最小而且最远距离也是最小的。排排队队模模型型作业作业P199 1、2、3，5、6、7
