清华大学运筹学综合习题解析.ppt

例1maxz=3x1+x2+3x3s.t.2x1+x2+x32x1+2x2+3x352x1+2x2+x36xi0,i=1,2,3解标准化后，写出单纯形表,XBbx1x2x3x4x5x6x422111001x551230105/2x6622100130313000,x222111002x51-301-2101/2x62-20-1-201-2102-100,XBbx1x2x3x4x5x6x215103-101/5x31-301-210-x63-500-411-7003-20,x11/511/503/5-1/50 x38/503/50-1/52/50 x64011-101-27/50-7/50-6/5-3/50,最优解为(1/5,0,8/5,0,0,4)Tmax=27/5,例2.max=3x1+2x1+x3-x4s.t.3x1+2x2+x3=15,5x1+x2+2x3=20 x1+2x2+x3+x4=10 x1,x2,x3,x40,解引入人工变量把原问题变成下列形式max=3x1+2x1+x3-x4-M(x5+x6)s.t.3x1+2x2+x3+x5=155x1+x2+2x3+x6=20,最优解为(5/2,5/2,5/2,0,0,0)T,max=15,原问题的解为(5/2,5/2,5/2,0)T,max=15.,例3max=2x1+x2+3x3+x4s.t.x1+x2+x3+x452x1-x2+3x3=-4x1-x3+x41x10,x2,x4无约束,x30,min=5y1+4y2-y3s.t.y1-2y2-y32y1+y2=1y1+3y2-y33y1+y3=1,其对偶问题为,y10，y2无约束，y30,2020/6/5,5,令,设原问题为,为原问题的一最优解,则,为对偶问题,的一最优解,2020/6/5,6,例4MaxZ=40X1+50X2,X1+2X2303X1+2X2602X224X1,X20,s.t,y1y2y3,MinW=30y1+60y2+24y3,y1+3y2+0y3402y1+2y2+2y350y1,y2,y30,s.t,MaxW=-30y1-60y2-24y3,y1+3y2+0y3y4=402y1+2y2+2y3y5=50y1,y2,y3,y4,y50,s.t,2020/6/5,7,MaxW=-30y1-60y2-24y3+0(y4+y5)-M(y6+y7),y1+3y2+0y3y4+y6=402y1+2y2+2y3y5+y7=50y1,y2,y3,y4,y50,s.t,2020/6/5,8,2020/6/5,9,例5、MaxZ=40X1+50X2,X1+2X2303X1+2X2602X224X1,X20,s.t,X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1X50,s.t,2020/6/5,10,例6.求解下列线性规划问题max=x1+2x2+3x3+4x4s.t.x1+2x2+2x3+3x4202x1+x2+3x3+2x420 xj0,j=1,2,3,4,解其对偶问题为min=20y1+20y2s.t.y1+2y212y1+y222y1+3y233y1+2y24y1,y20,(1.2,0.2),1,2,1,2,.,.,y1,y2,用图解法得最优解y1=1.2,y2=0.2,根据松紧定理，原问题的最优解必满足XS=0及YSX=0,及(y3,y4,y5,y6)=0,x5(y1,y2)x6=0,x1x2x3x4,将y1=1.2,y2=0.2代入对偶问题的约束条件，得y30,y40,所以x1=x2=0,又因y10,y20。所以x5=x6=0，即原问题为等式约束,x1=x2=0 x1+2x2+2x3+3x4=202x1+x2+3x3+2x4=20,即x1=x2=0，x3=4,x4=4原问题的最优解为(0,0,4,4)T,例7.max=x1+4x2+3x3s.t.2x1+2x2+x34x1+2x2+2x36xj0,对偶问题为min=4y1+6y2s.t.2y1+y212y1+2y24,y1+2y23y1,y20,初始单纯形表为422110612201014300,对偶问题的基本解为y1=0,y2=0，ys1=-1，ys2=-4，ys3=-3,其最终表为,13/2101-1/2210111-102001-1,由原问题的最终表可知，y1=1,y2=1(最优解)，ys1=2,2020/6/5,17,例8用单纯形法来求解目标规划Minf=P1（d1+d2+)+P2d3+P3d4-+P4（d1-+2d2-)s.t.x1+d1-d1+=9x2+d2-d2+=84x1+6x2+d3-d3+=6012x1+18x2+d4-d4+=252x1,x2,di-,di+0,i=1,2,3,4.,2020/6/5,18,解:首先处理初始基本可行解对应的各级检验数。,2020/6/5,19,（1）k=1，在初始单纯形表中基变量为（d1-,d2-,d3-,d4-)T=（9，8，60，252)T；（2）因为P1与P2优先级的检验数均已经为非负，所以这个单纯形表对P1与P2优先级是最优单纯形表；（3）下面考虑P3优先级，第二列的检验数为-18，此为进基变量，计算相应的比值bi/aij写在列。通过比较，得到d2-对应的比值最小，于是取a22（标为*号）为主元进行矩阵行变换得到新的单纯形表；,2020/6/5,20,（4）下面继续考虑P3优先级，第一列的检验数为-12，此为进基变量，计算相应的比值bi/aij，得到d3-对应的比值最小，于是取a31（标为*号）为转轴元进行矩阵行变换得到新的单纯形表；,2020/6/5,21,（5）当前的单纯形表各优先级的检验数均满足了上述条件,故为最优单纯形表。我们得到最优解x1=3，x2=8。,例9某公司生产A,B两种塑料布，这两种产品每小时的产量均为1000米(宽度为2米)，该公司每天采用两班制生产，每周最大工作时间为80小时。按预测，A,B两种塑料布每周市场的最大销售量分别为70,000米和45,000米，A种塑料布每米的利润为2.5元，B种塑料布每米的利润是1.5元。试确定公司每周A,B两种塑料布的生产量x1和x2(单位:千米)，公司的目标是：,P1:避免每周80小时生产能力的过少利用；,P2:加班时间限制在10小时以内；,P3:A,B两种塑料布的每周产量分别达到70,000米和45,000米，但不得超出。其权系数依它们每米的利润为准；,P4:尽量减少加班。,解这个问题的目标规划模型。,1.每周可利用的工作时间约束,x1+x2+d1-d1+=80,2.每周可利用的加班时间约束,d1+d11-d11+=10,3.每周塑料布产量约束,x1+d2=70,x2+d3=45,权系数为2.5:1.5=5:3,目标规划模型如下：,min=P1d1+P2d11+P3(5d2+3d3)+P4d1+,s.t.x1+x2+d1-d1+=80,x1+d2=70,x2+d3=45,d1+d11d11+=10,x1,x2,di,di+0(i=1,2,3,11),解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。,初始表,最终表,例10用分支定界法求解整数规划问题（单纯形法）,x1=13/4x2=5/2Z(0)=59/414.75选x2进行分枝，即增加两个约束，2x23有下式：,分别在(LP1)和(LP2)中引入松弛变量x5和x6，将新加约束条件加入上表计算。即x2+x5=2,x2+x6=3得下表:,x1=7/2,x2=2Z(1)=14.5继续分枝，加入约束3x14,LP1,LP2,x1=5/2,x2=3Z(2)=13.5Z(2)Z(1)先不考虑分枝,接(LP1)继续分枝，加入约束4x13，有下式：,分别引入松弛变量x7和x8，然后进行计算。,x1=3,x2=2Z(3)=13找到整数解，问题已探明，停止计算。,LP3,x1=4x2=1Z(4)=14找到整数解，问题已探明，停止计算。,LP4,树形图如下：,LP1x1=7/2,x2=2Z(1)29/2=14.5,LPx1=13/4,x2=5/2Z(0)59/4=14.75,LP2x1=5/2,x2=3Z(2)27/2=13.5,LP3x1=3,x2=2Z(3)13,LP4x1=4,x2=1Z(4)14,x22,x23,x13,x14,#,#,#,例11：用割平面法求解数规划问题,初始表,最优表,在松弛问题最优解中，x1,x2均为非整数解，由上表有：,将系数和常数都分解成整数和非负真分数之和,以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得：,引入松弛变量s1后得到下式，将此约束条件加到上表中，继续求解。,得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解：X=(0,4),Z=4,或X=(2,2),Z=4。,例12,11,5,7,6,4,戊,6,9,6,3,7,丁,8,6,4,5,8,丙,9,11,7,12,9,乙,11,8,9,5,7,甲,E,D,C,B,A,费工作用人员,-1,-2,l=m=4n=5,l=m=4n=5,此问题有多个最优解,Z=28,例13用逆推解法求解问题,用逆推解法，从后先前依次有,利用微分法易知：,已知s1=c，可得各阶段的最优决策和最优值。即,例14分配投资问题,某公司有资金10万元，若投资于项目k（k=1，2，3）的投资额为xk时，其收益分别为g1（x1）=4x1，g2（x2）=9x2，g3（x3）=2x32，问应该如何分配投资数额才能使总收益最大？该问题表面上看与时间无明显关系，其静态模型：,Maxz=4x1+9x2+2x32x1+x2+x3=10 xi0（i=1，2，3）,建立动态规划模型与求解,建立DP模型与求解阶段k=1，2，3，分别表示项目1，2，3状态变量sk：第k段初拥有的资金总量（分配给第k至第3个项目的资金数量）决策变量xk：第k段的投资量（分配给第k个项目的资金数量），决策集合Dk（sk）=xk0xksk,4、状态转移方程sk+1=sk-xk,5、阶段指标值（函数）：vk（sk，xk）=gk（xk）所以指标函数为：6、fk（sk）：第k段初拥有的资金总量为sk时，第k至第3段按最优投资策略所获得的第k至第3段的总收益。,g1（x1）=4x1g2（x2）=9x2g3（x3）=2x32,7.建立动态规划基本方程：（逆序递推方程）,8.逆序递推求解动态规划基本方程k=3,f3*（s3）=2s32x3*=s3,可以证明极大值只可能在端点取得，即：1、s29/2时，f2（0）f2（s2），此时x2*=s2f2（s2）=9s22、s29/2时，f2（0）f2（s2），此时x2*=0f2（0）=2s22,k=1第一种情况,当f2（s2）=9s2，f1（10）=Max4x1+f2(s2)=Max4x1+9s2,0x110,=Max4x1+9(s1x1)=Max9s15x1=9s1，x1*=0,但此时s2=s1x1=10-09/2与s29/2矛盾，故舍去。,0x110,k=1第二种情况,同样可以证明极大值只可能在端点取得，比较两个端点：x1=0时，f1（10）=200，x1=10时，f1（10）=40所以x1*=0,10、顺序确定最优策略。,最优投资方案为全部资金投资于第3个项目，可获最大收益200万元。,vs,vt,v1,v3,v2,v4,(3,3),(4,2),(5,1),(2,2),(1,1),(1,1),(5,3),(3,1),(3,1),(cij,fij),截集为：（Vs，V2）,(V1,V3)。割容量为：3+2=5,截集为：（V2，V4）,(V1,V3)。割容量为：4+2=6,截集为：（V4，Vt）,(V1,V3)。割容量为：5+2=7,网络最大流的流量=容量最小的割容量,例15:求图所示网络中的最小费用最大流，弧旁的权是（bij,cij）。,算法：取f(0)=0，一般若在第k-1步得到最小费用流f(k-1)，则构造赋权有向图W(f(k-1)，在W(f(k-1)中，寻求从vs到vt的最短路。若不存在最短路(即最短路权是+)，则f(k-1)就是最小费用最大流；若存在最短路，则在原网络D中得到相应的增广链，在增广链上对f(k-1)进行调整。,4,vs,vt,v1,v2,v3,4,1,2,3,1,6,2,vs,vt,v1,v2,v3,按最短路根据弧的容量调整运量得流量图下图.,W(f(0),0,0,0,0,vs,vt,v1,v2,v3,(a),(b),f(1),v(f(1)=5,1,-2,3,1,6,2,vs,vt,v1,v2,v3,-1,-1,W(f(1),(c),作相应赋权有向图并求出最短路,以0流f(0)=0为初始流构造赋权有向图并算得最短路如右,0,0,0,5,5,5,(4,10),(1,8),(2,5),(3,10),(1,7),(6,2),(2,4),(bij,cij),（运价，容量）,1,4,0,5,5,0,5,0,0,vs,vt,v1,v2,v3,(b),f(1),v(f(1)=5,1,3,1,6,2,vs,vt,v1,v2,v3,-1,W(f(1),(c),作相应赋权有向图并求出最短路,0,5,5,0,5,0,0,vs,vt,v1,v2,v3,(d),4,3,-1,6,2,vs,vt,v1,v2,v3,-1,W(f(2),(e),-4,沿最短路调整,得左下图,作相应赋权有向图并求出最短路,bij,若fij0,+,若fij=0,wij=,wji=,-1,2,7,-2,-2,1,2,5,5,0,7,0,0,vs,vt,v1,vs,v2,v3,(d),4,3,-1,6,2,vs,vt,v1,v2,v3,-1,W(f(2),(e),-4,作相应赋权有向图并求出最短路,4,-2,3,-1,6,2,vs,vt,v2,v3,-1,W(f(3),(g),-4,-2,-3,2,5,5,0,7,0,0,vs,vt,v1,v2,v3,(f),f(3),v(f(3)=10,作相应赋权有向图并求出最短路,沿最短路调整流量,bij,若fij0,+,若fij=0,wij=,wji=,8,3,3,-2,2,8,5,3,7,0,3,vt,v1,vs,v2,v3,(h),f(4),v(f(4)=11,4,-2,3,-1,6,2,vs,vt,v2,v3,-1,W(f(3),(g),-4,-2,-3,2,8,5,3,7