第6讲生产与服务管理中的优化问题(二).ppt

*,*,新余学院 建模组,优 化 建 模,上一页,下一页,Xinyu University MCM,优化建模,第,6,讲,:,生产与服务管理中的,优化问题,(,二,),面试顺序与消防车调度,飞行计划问题,机票的销售策略,4/18/2026,例,有,4,名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段,4,名同学的顺序是一样的）。由于,4,名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：分钟）。这,4,名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨,8,：,00,，请问他们最早何时能离开公司？,一,面试顺序与消防车调度问题,秘书初试,主管复试,经理面试,同学甲,13,15,20,同学乙,10,20,18,同学丙,20,10,10,同学丁,8,10,15,4/18/2026,建立模型,实际上，这个问题就是要安排,4,名同学的面试顺序，使完成全部面试所花费的时间最少。,记,t,ij,为第,i,名同学参加第,j,阶段面试需要的时间,(,已知,),，令,x,ij,表示第,i,名同学参加第,j,阶段面试的开始时刻,(,不妨记早上,8,：,00,面试开始为,0,时刻,)(,i,=1,2,3,4,；,j,=1,2,3),，,T,为完成全部面试所花费的最少时间。,优化目标为,4/18/2026,a.,时间先后次序约束,(,每人只有参加完前一个阶段的面试后才能进入下一个阶段,),：,x,ij,+,t,ij,x,i,，,j+,1,(,i,=1,2,3,4,；,j,=1,2),b.,每个阶段,j,同一时间只能面试,1,名同学：用,0-1,变量,y,ik,表示第,i,名同学是否排在第,k,名同学前面,(0,表示是，,1,表示否,),，则,x,ij,+,t,ij,x,kj,Ty,ik,(,i,k,=1,2,3,4;,j,=1,2,3;,ik,),x,kj,+,t,kj,x,ij,T,(1,y,ik,)(,i,k,=1,2,3,4;,j,=1,2,3;,ik,),约束条件：,4/18/2026,可以将非线性的优化目标改写为如下线性优化目标：,Min,T,s.t.,T,x,13,+,t,13,T,x,23,+,t,23,T,x,33,+,t,33,T,x,43,+,t,43,4/18/2026,Min,T,s.t.,x,ij,+,t,ij,x,i,j+,1,(,i,=1,2,3,4,；,j,=1,2),x,ij,+,t,ij,x,kj,Ty,ik,(,i,k,=1,2,3,4;,j,=1,2,3;,ik,),x,kj,+,t,kj,x,ij,T,(1,y,ik,)(,i,k,=1,2,3,4;,j,=1,2,3;,i=max(PXS(i,j)|j#EQ#size(stage):x(i,j)+t(i,j),;,!,只有参加完前一个阶段的面试后才能进入下一个阶段,;,for(PXS(i,j)|j#LT#size(stage):ORDERx(i,j)+t(i,j)x(i,j+1);,!,同一时间只能面试,1,名同学,;,for(Stage(j):,for(PXP(i,k):SORT1x(i,j)+t(i,j)-x(k,j)MAXT*Y(i,k);,for(PXP(i,k):SORT2x(k,j)+t(k,j)-x(i,j)MAXT*(1-Y(i,k);,);,for(PXP:bin(y);,End,4/18/2026,求解这个模型，得到的结果与前面的完全相同。,可以很清楚地看到，使用,LINGO,建模语言的集合和属性概念，得到的模型具有非常好的结构性，反映了相应的优化模型的本质，目标、决策变量、约束一清二楚，容易阅读和理解，而且还可以让数据与程序完全分离，这种优越性是,LINDO,软件无法与之相比的。,4/18/2026,消防车调度问题,例,5.6,某市消防中心同时接到了三处火警报告。根据当前的火势，三处火警地点分别需要,2,辆、,2,辆和,3,辆消防车前往灭火。三处火警地点的损失将依赖于消防车到达的及时程度：记,t,ij,为第,j,辆消防车到达火警地点,i,的时间,(,分钟,),，则三处火警地点的损失分别为,:,6,t,11,+4,t,12,，,7,t,21,+3,t,22,，,9,t,31,+8,t,32,+5,t,33,。,目前可供消防中心调度的消防车正好有,7,辆，分别属于三个消防站,(,可用消防车数量分别为,3,辆、,2,辆、,2,辆,),。消防车从三个消防站到三个火警地点所需要的时间如表,5-6,所示。该公司应如何调度消防车，才能使总损失最小？,4/18/2026,如果三处火警地点的损失分别为,:,4,t,11,+6,t,12,，,3,t,21,+7,t,22,，,5,t,31,+8,t,32,+9,t,33,，,调度方案是否需要改变？,消防站到三个火警地点所需要的时间,时间,(,分钟,),火警地点,1,火警地点,2,火警地点,3,消防站,1,6,7,9,消防站,2,5,8,11,消防站,3,6,9,10,4/18/2026,问题分析,本题考虑的是为每个火警地点分配消防车的问题，初步看来与线性规划中经典的运输问题有些类似。本题的问题可以看成是指派问题和运输问题的一种变形，我们下面首先把它变成一个运输问题建模求解。,决策变量,为了用运输问题建模求解，很自然地把,3,个消防站看成供应点。如果直接把,3,个火警地点看成需求点，我们却不能很方便地描述消防车到达的先后次序，因此难以确定损失的大小。下面我们把,7,辆车的需求分别看成,7,个需求点,(,分别对应于到达时间,t,11,t,12,t,21,t,22,t,31,t,32,t,33,),。用,x,i j,表示消防站,i,是否向第,j,个需求点派车,(1,表示派车，,0,表示不派车,),，则共有,21,个,0-1,变量。,4/18/2026,决策目标,题目中给出的损失函数都是消防车到达时间的线性函数，所以由所给数据进行简单的计算可知，如果消防站,1,向第,6,个需求点派车,(,即消防站,1,向火警地点,3,派车但该消防车是到达火警地点,3,的第二辆车,),，则由此引起的损失为,8*9=72,。同理计算，可以得到损失矩阵,(,元素分别记为,c,i,j,),。,c,i,j,火警地点,1,火警地点,2,火警地点,3,j,=1,j,=2,j,=3,j,=4,j,=5,j,=6,j,=7,消防站,i,=1,36,24,49,21,81,72,45,消防站,i,=2,30,20,56,24,99,88,55,消防站,i,=3,36,24,63,27,90,80,50,4/18/2026,于是，使总损失最小的决策目标为,约束条件,约束条件有两类：一类是消防站拥有的消防车的数量限制，另一类是各需求点对消防车的需求量限制。,消防站拥有的消防车的数量限制可以表示为,x,11,+,x,12,+,x,13,+,x,14,+,x,15,+,x,16,+,x,17,=3,x,21,+,x,22,+,x,23,+,x,24,+,x,25,+,x,26,+,x,27,=2,x,31,+,x,32,+,x,33,+,x,34,+,x,35,+,x,36,+,x,37,=2,各需求点对消防车的需求量限制可以表示为,4/18/2026,求解得到如下结果：,OBJECTIVE FUNCTION VALUE 1)329.0000,VARIABLE VALUE REDUCED COST,X11 0.000000 10.000000,X12 0.000000 8.000000,X13 1.000000 0.000000,X14 0.000000 2.000000,X15 1.000000 0.000000,X16 1.000000 0.000000,X17 0.000000 3.000000,X21 1.000000 0.000000,X22 1.000000 0.000000,X23 0.000000 3.000000,X24 0.000000 1.000000,X25 0.000000 14.000000,X26 0.000000 12.000000,X27 0.000000 9.000000,输入,LINDO,：,4/18/2026,VARIABLE VALUE REDUCED COST,X31 0.000000 2.000000,X32 0.000000 0.000000,X33 0.000000 6.000000,X34 1.000000 0.000000,X35 0.000000 1.000000,X36 0.000000 0.000000,X37 1.000000 0.000000,也就是说，消防站,1,应向火警地点,2,派,1,辆车，向火警地点,3,派,2,辆车；消防站,2,应向火警地点,1,派,2,辆车；消防站,3,应向火警地点,2,、,3,各派,1,辆车。最小总损失为,329,。,4/18/2026,讨论,1),这个问题本质上仍然和经典的运输问题类似，可以把每辆车到达火场看作需求点，消防站可作供应点。在上面模型中，我们虽然假设,x,ij,为,0-1,变量，但求解时是采用线性规划求解的，也就是说没有加上,x,ij,为,0-1,变量或整数变量的限制条件，但求解得到的结果中,x,ij,正好是,0-1,变量。这一结果不是偶然的，而是运输问题特有的一种性质。,4/18/2026,2),在上面模型中，我们没有考虑消防车到达各火警地点的先后次序约束，但得到的结果正好满足所有的先后次序约束。这一结果却并不总是必然的，而只是巧合。,如对例题后半部分的情形，结果就不是这样了。显然，此时只需要修改损失矩阵,(,元素仍然分别记为,c,ij,),c,i,j,火警地点,1,火警地点,2,火警地点,3,j,=1,j,=2,j,=3,j,=4,j,=5,j,=6,j,=7,消防站,i,=1,24,36,21,49,45,72,81,消防站,i,=2,20,30,24,56,55,88,99,消防站,i,=3,24,36,27,63,50,80,90,4/18/2026,此时将重新构成的线性规划模型输入,LINDO,求解,可以得到新的最优解,:,x,14,=,x,16,=,x,17,=,x,21,=,x,22,=,x,33,=,x,35,=1,其他变量为,0(,最小总损失仍为,329),。实际上,损失矩阵中只是,1,、,2,列交换了位置，,3,、,4,列交换了位置，,5,、,7,列交换了位置，因此不用重新求解就可以直接看出以上新的最优解。,但是，以上新的最优解却是不符合实际情况的。例如，,x,14,=,x,33,=1,表明火警地点,2,的第一辆消防车来自消防站,3,，第二辆消防车来自消防站,1,，但这是不合理的，因为火警地点,2,与消防站,3,有,9,分钟的距离，大于与消防站,1,的,7,分钟的距离。分配给火警地点,3,的消防车也有类似的不合理问题。,4/18/2026,为了解决这一问题，我们必须考虑消防车到达各火警地点的先后次序约束，也就是说必须在简单的运输问题模型中增加一些新的约束，以保证以上的不合理问题不再出现。,首先考虑火警地点,2,。由于消防站,1,的消防车到达所需时间,(7,分钟,),小于消防站,2,的消防车到达所需时间,(8,分钟,),，并都小于消防站,3,的消防车到达所需时间,(9,分钟,),，因此火警地点,2,的第,2,辆消防车如果来自消防站,1,，则火警地点,2,的第,1,辆消防车也一定来自消防站,1,；火警地点,2,的第,2,辆消防车如果来自消防站,2,，则火警地点,2,的第,1,辆消防车一定来自消防站,1,或,2,。因此，必须增加以下约束：,x,14,x,13,x,24,x,13,+,x,23,4/18/2026,x,16,x,15,x,17,x,16,x,36,x,15,+,x,35,2,x,37,x,15,+,x,16,+,x,35,+,x,36,同理，对火警地点,1,，必须增加以下约束：,x,22,x,21,对火警地点,3,，必须增加以下约束：,4/18/2026,此时将重新构成的线性规划模型输入,LINDO,软件如下：,!,消防车调度,Min 36x12+24x11+49x14+21x13+81x17+72x16+45x15,+30 x22+20 x21+56x24+24x23+99x27+88x26+55x25,+36x32+24x31+63x34+27x33+90 x37+80 x36+50 x35,SUBJECT TO x11+x12+x13+x14+x15+x16+x17=3,x21+x22+x23+x24+x25+x26+x27=2,x31+x32+x33+x34+x35+x36+x37=2,x11+x21+x31=1,x12+x22+x32=1,x13+x23+x33=1,x14+x24+x34=1,x15+x25+x35=1,x16+x26+x36=1,x17+x27+x37=1,4/18/2026,X22-X21=0,X14-X13=0,X24-X23-X13=0,X16-X15=0,X17-X16=0,X36-X15-X35=0,2X37-X15-X16-X35-X36=0,END,!INT 21,4/18/2026,求解，可以得到新的解为：,OBJECTIVE FUNCTION VALUE 1)32.6667,VARIABLE VALUE REDUCED COST,X12 0.000000 9.333333,X11 0.000000 7.333333,X14 1.000000 0.000000,X13 1.000000 0.000000,X17 0.333333 0.000000,X16 0.333333 0.000000,X15 0.333333 0.000000,X22 1.000000 0.000000,X21 1.000000 0.000000,X24 0.000000 2.333333,X23 0.000000 1.000000,4/18/2026,VARIABLE VALUE REDUCED COST,X27 0.000000 13.000000,X26 0.000000 12.000000,X25 0.000000 9.000000,X32 0.000000 2.000000,X31 0.000000 0.000000,X34 0.000000 5.333333,X33 0.000000 0.000000,X37 0.666667 0.000000,X36 0.666667 0.000000,X35 0.666667 0.000000,4/18/2026,但是我们发现此时的解中,x,ij,并不都是,01,变量或整数变量，因此还是不符合题意。这是因为此时的模型已经不再是“标准”的运输模型，所以得到的解不一定自然地为正数解的缘故。所以我们还必须显式地加上,x,ij,为,01,变量的约束。,加上,x,ij,为,0-1,变量的约束后求解可以得到：,x,13,=,x,14,=,x,15,=,x,21,=,x,22,=,x,36,=,x,37,=1,，,其他变量为,0(,最小总损失仍为,335),。也就是说，消防站,1,应向火警地点,2,派,2,辆车，向火警地点,3,派,1,辆车；消防站,2,应向火警地点,1,派,2,辆车；消防站,3,应向火警地点,3,派,2,辆车。经过检验可以发现，此时的派车方案是合理的。,4/18/2026,例,这个问题是以第二次世界大战中的一个实际问题为背景，经过简化而提出来的。在甲乙双方的一场战争中，一部分甲方部队被乙方部队包围长达,4,个月。,由于乙方封锁了所有水陆交通通道，被包围的甲方部队只能依靠空中交通维持供给。运送,4,个月的供给分别需要,2,3,3,4,次飞行，每次飞行编队由,50,架飞机组成,(,每架飞机需要,3,名飞行员,),，可以运送,10,万吨物资。每架飞机每个月只能飞行一次，每名飞行员每个月也只能飞行一次。在执行完运输任务后的返回途中有,20%,的飞机会被乙方部队击落，相应的飞行员也因此牺牲或失踪。,二,飞行计划问题,4/18/2026,在第,1,个月开始时，甲方拥有,110,架飞机和,330,名熟练的飞行员。在每个月开始时，甲方可以招聘新飞行员和购买新飞机。新飞机必须经过一个月的检查后才可以投入使用，新飞行员必须在熟练飞行员的指导下经过一个月的训练才能投入飞行。每名熟练飞行员可以作为教练每个月指导,20,名飞行员,(,包括他自己在内,),进行训练。每名飞行员在完成一个月的飞行任务后，必须有一个月的带薪假期，假期结束后才能再投入飞行。已知各项费用,(,单位略去,),如下表所示，请你为甲方安排一个飞行计划。,4/18/2026,如果每名熟练飞行员可以作为教练每个月指导不超过,20,名飞行员,(,包括他自己在内,),进行训练，模型和结果有哪些改变？,第,1,个月,第,2,个月,第,3,个月,第,4,个月,新飞机价格,200.0,195.0,190.0,185.0,闲置的熟练飞行员报酬,7.0,6.9,6.8,6.7,教练和新飞行员报酬,(,包括培训费用,),10.0,9.9,9.8,9.7,执行飞行任务的熟练飞行员报酬,9.0,8.9,9.8,9.7,休假期间的熟练飞行员报酬,5.0,4.9,4.8,4.7,4/18/2026,问题分析,这个问题看起来很复杂，但只要理解了这个例子中所描述的事实，其实建立优化模型并不困难。首先可以看出，执行飞行任务以及执行飞行任务后休假的熟练飞行员数量是常数，所以这部分费用,(,报酬,),是固定的，在优化目标中可以不考虑。,决策变量,设,4,个月开始时甲方新购买的飞机数量分别为,x,1,x,2,x,3,x,4,架,闲置的飞机数量分别为,y,1,y,2,y,3,y,4,架。,4,个月中,飞行员中教练和新飞行员数量分别为,u,1,u,2,u,3,u,4,人,闲置的的熟练飞行员数量分别为,v,1,v,2,v,3,v,4,人。,4/18/2026,目标函数,优化目标是,:,Min 200,x,1,+195,x,2,+190,x,3,+185,x,4,+10,u,1,+9.9,u,2,+9.8,u,3,+9.7,u,4,+7,v,1,+6.9,v,2,+6.8,v,3,+6.7,v,4,约束条件,需要考虑的约束包括：,1,）,飞机数量限制,：,4,个月中执行飞行任务的飞机分别为,100,150,150,200,架，但只有,80,120,120,160,架能够返回供下个月使用。,第,1,个月：,100+,y,1,=110,第,2,个月：,150+,y,2,=80+,y,1,+,x,1,第,3,个月：,150+,y,3,=120+,y,2,+,x,2,第,4,个月：,200+,y,4,=120+,y,3,+,x,3,4/18/2026,2,）,飞行员数量限制,：,4,个月中执行飞行任务的熟练飞行员分别为,300,450,450,600,人，但只有,240,360,，,360,480,人能够返回,(,下个月一定休假,),。,第,1,个月：,300+0.05,u,1,+,v,1,=330,第,2,个月：,450,+0.05,u,2,+,v,2,=,u,1,+,v,1,第,3,个月：,450+0.05,u,3,+,v,3,=,u,2,+,v,2,+240,第,4,个月：,600+0.05,u,4,+,v,4,=,u,3,+,v,3,+360,最后，自然要求,x,1,x,2,x,3,x,4,y,1,y,2,y,3,y,4,u,1,u,2,u,3,u,4,v,1,v,2,v,3,v,4,0,且为整数。,4/18/2026,于是，这个优化模型很容易输入,LINDO,：,MIN 200 x1+195x2+190 x3+185x4+10u1+9.9u2,+9.8u3+9.7u4+7v1+6.9v2+6.8v3+6.7v4,s.t.y1=10,y1+x1-y2=70,y2+x2-y3=30,y3+x3-y4=80,0.05 u1+v1=30,u1+v1-0.05 u2-v2=450,u2+v2-0.05 u3-v3=210,u3+v3-0.05 u4-v4=240,end,GIN 16,4/18/2026,用,LINDO,求解得到：,OBJECTIVE FUNCTION VALUE 1)42324.40,VARIABLE VALUE REDUCED COST,X1 60.000000 200.000000,X2 30.000000 195.000000,X3 80.000000 190.000000,X4 0.0000000 185.000000,U1 460.00000 10.000000,U2 220.00000 9.900000,U3 240.00000 9.800000,U4 0.0000000 9.700000,V1 7.0000000 7.000000,V2 6.0000000 6.900000,V3 4.0000000 6.800000,V4 4.0000000 6.700000,4/18/2026,VARIABLE VALUE REDUCED COST,Y1 10.000000 0.000000,Y2 0.000000 0.000000,Y3 0.000000 0.000000,Y4 0.000000 0.000000,即最优解为,x,1,=60,x,2,=30,x,3,=80,x,4,=0,y,1,=10,y,2,=,y,3,=,y,4,=0,u,1,=460,u,2,=220,u,3,=240,u,4,=0,v,1,=7,v,2,=6,v,3,=4,v,4,=4;,目标函数值为,42324.40,。,4/18/2026,问题讨论,如果每名熟练飞行员可以作为教练每个月指导不超过,20,名飞行员,(,包括他自己在内,),进行训练，则应将教练与新飞行员分开：,设,4,个月飞行员中教练为,u,1,u,2,u,3,u,4,人，新飞行员数量分别为,w,1,w,2,w,3,w,4,人。其它符号不变。飞行员的数量限制约束为,第,1,个月：,300+,u,1,+,v,1,=330,第,2,个月：,450+,u,2,+,v,2,=,u,1,+,v,1,+,w,1,，,w,1,20,u,1,第,3,个月：,450+,u,3,+,v,3,=,u,2,+,v,2,+240+,w,2,，,w,2,20,u,2,第,4,个月：,600+,u,4,+,v,4,=,u,3,+,v,3,+360+,w,3,，,w,3,20,u,3,4/18/2026,优化模型作相应修改，输入,LINDO,如下：,MIN 200 x1+195x2+190 x3+185x4+10u1+9.9u2+9.8u3+9.7u4,+7v1+6.9v2+6.8v3+6.7v4+10w1+9.9w2+9.8w3+9.7w4,s.t.,y1=10,y1+x1-y2=70,y2+x2-y3=30,y3+x3-y4=80,u1+v1=30,u1+v1+w1-u2-v2=450,u2+v2+w2-u3-v3=210,u3+v3+w3-u4-v4=240,w1-20u1=0,w2-20u2=0,w3-20u3=0,end,gin 20,4/18/2026,用,LINDO,求解得到：,OBJECTIVE FUNCTION VALUE 1)42185.80,VARIABLE VALUE REDUCED COST,X1 60.000000 200.000000,X2 30.000000 195.000000,X3 80.000000 190.000000,X4 0.000000 185.000000,U1 22.000000 10.000000,U2 11.000000 9.900000,U3 12.000000 9.800000,U4 0.000000 9.700000,V1 8.000000 7.000000,V2 0.000000 6.900000,V3 0.000000 6.800000,V4 0.000000 6.700000,4/18/2026,VARIABLE VALUE REDUCED COST,W1 431.000000 10.000000,W2 211.000000 9.900000,W3 228.000000 9.800000,W4 0.000000 9.700000,Y1 10.000000 0.000000,Y2 0.000000 0.000000,Y3 0.000000 0.000000,Y4 0.000000 0.000000,即最优解为,u,1,=22,u,2,=11,u,3,=12,u,4,=0,v,1,=8,v,2,=,v,3,=,v,4,=0,w,1,=431,w,2,=211,w,3,=228,w,4,=0(,x,1,x,4,y,1,y,4,不变,),；目标函数值为,42185.80,。,4/18/2026,航班,AH,、,HB,、,HC,可搭乘旅客的最大数量分别为,120,、,100,、,110,人,三 机票的销售策略,机票分配问题,出发地,-,目的地,头等舱需求（人）,头等舱价格（元）,经济舱需求（人）,经济舱价格（元）,AH,33,190,56,90,AB,（经,H,转机）,24,244,43,193,AC,（经,H,转机）,12,261,67,199,HB,44,140,69,80,HC,16,186,17,103,每条航线上分别分配多少,头等舱和经济舱的机票？,问,题,目标,使销售收入最大化,4/18/2026,5,个起终点航线,AH,、,AB,、,AC,、,HB,、,HC,，,依次编号为,i,（,i,=1,，,2,，,5,）,模型建立,相应的头等舱需求记为,a,i,，价格记为,p,i,相应的经济舱需求记为,b,i,，价格记为,q,i,三个航班,AH,、,HB,、,HC,的顾客容量分别是,c,1,=120,，,c,2,=100,，,c,3,=110,决策,变量,x,i,（起终点航线,i,上销售的头等舱机票数）,y,i,（销售的经济舱机票数）,4/18/2026,目标,收入最大,约束,x,1,+,x,2,+,x,3,+,y,1,+,y,2,+,y,3,c,1,x,2,+x,4,+y,2,+y,4,c,2,x,3,+x,5,+y,3,+y,5,c,3,容量限制,需求限制,0,x,i,a,i,0,y,i,b,i,线性规划模型,(LP),头等舱：,33,、,10,、,12,、,44,、,16,经济舱：,0,、,0,、,65,、,46,、,17,总销售收入：,39344,（元）,4/18/2026,谢谢!,4/18/2026,