线性规划模型专题培训课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,线性规划模型,2,泰山工厂生产状况,泰山工厂可以生,产两种产品出售，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：,目前生产现状：,不生产产品,A,，生产产品,B,每天,30,，获利,3600,产品,A,产品,B,资源限量,设 备,劳动力,原材料,9,4,3,4,5,10,360,200,300,利润,元,/kg,70,120,3,招聘总经理！,约翰：我应聘！,在现有资源状况下，我可以使利润达到,4280,！,方案是：生产,A,产品,20,，生产,B,产品,24,可行性：,9*20+4*24=276,360,4*20+5*24=200,3*20+10*24=300,4,怎么达到的？,约翰使用了运筹学中的线性规划模型,问题：如何安排生产计划，使得获利最多？,步骤：,1,、确定决策变量：设生产,A,产品,x,1,kg,B,产品,x,2,kg,2,、确定目标函数：,maxZ=70X,1,+120X,2,3,、确定约束条件：设备约束,9X,1,+4X,2,360,人力约束,4X,1,+5X,2,200,原材料约束,3X,1,+10X,2,300,非负性约束,X,1,0,X,2,0,5,线性规划图解法,由数学知识可知：,y=ax+b,是一条直线，同理：,Z=70 x,1,+120 x,2,x,2,=70/120 x,1,-Z/120,也是一条直线，以,Z,为参数的一族等值线。,9x,1,+4x,2,360,x,1,360/9-4/9x,2,是直线,x,1,=360/9-4/9x,2,下方的半平面。所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解。,6,例,1,图示,.,90 80 60 40 20,0 20 40 60 80 100,x,1,x,2,9,x,1,+4,x,2,360,4,x,1,+5,x,2,200,3,x,1,+10,x,2,300,A,B,C,D,E,F,G,H,I,Z=70,x,1,+120,x,2,7,最优解：,X,1,=20,x,2,=24,对应的生产方案：,生产,A,产品,20,生产,B,产品,24,获利：,70*20+120*24=4280,8,约翰就任泰山工厂总经理！,9,二、线性规划图解法,例,2.,某工厂在计划期内要安排,、,两种产品的生产，已知生产单位产品所需的设备台时及,A,、,B,两种原材料的消耗、资源的限制，如下表：,问题：工厂应分别生产多少单位,、,产品才能使工厂获利最多？,线性规划模型：,目标函数：,Max z=50 x,1,+100 x,2,约束条件：,s.t.x,1,+x,2,300,2 x,1,+x,2,400,x,2,250,x,1,x,2,0,10,例,1.,目标函数：,Max z=50 x,1,+100 x,2,约束条件：,s.t.,x,1,+x,2,300 (A),2 x,1,+x,2,400 (B),x,2,250 (C),x,1,0 (D),x,2,0 (E),得到最优解：,x,1,=50,，,x,2,=250,最优目标值,z =27500,图 解 法,对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。,下面通过例,1,详细讲解其方法：,11,线性规划图解法（续）,(1),分别取决策变量,X,1,X,2,为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例,1,的每个约束条件都代表一个半平面。,x,2,x,1,X,2,0,X,2,=0,x,2,x,1,X,1,0,X,1,=0,12,线性规划图解法（续）,（,2,）对每个不等式,(,约束条件,),，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。,100,200,300,100,200,300,x,1,+x,2,300,x,1,+x,2,=300,100,100,200,2x,1,+x,2,400,2x,1,+x,2,=400,300,200,300,400,13,线性规划图解法（续）,（,3,）把五个图合并成一个图，取各约束条件的公共部分，如图,2-1,所示。,100,100,x,2,250,x,2,=250,200,300,200,300,x,1,x,2,x,2,=0,x,1,=0,x,2,=250,x,1,+x,2,=300,2x,1,+x,2,=400,图,2-1,14,线性规划图解法（续）,（,4,）目标函数,z=50 x,1,+100 x,2,，当,z,取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到,B,点时，,z,在可行域内实现了最大化。,A,，,B,，,C,，,D,，,E,是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。,x,1,x,2,z=20000=50 x,1,+100 x,2,图,2-2,z=27500=50 x,1,+100 x,2,z=0=50 x,1,+100 x,2,z=10000=50 x,1,+100 x,2,C,B,A,D,E,15,线性规划图解法（续）,重要结论：,如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；,无穷多个最优解。若将例,1,中的目标函数变为,max z=50 x,1,+50 x,2,，则线段,BC,上的所有点都代表了最优解；,无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；,无可行解。若在例,1,的数学模型中再增加一个约束条件,4x,1,+3x,2,1200,，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。,16,线性规划图解法（续）,例,2,某公司由于生产需要，共需要,A,，,B,两种原料至少,350,吨（,A,，,B,两种材料有一定替代性），其中,A,原料至少购进,125,吨。但由于,A,，,B,两种原料的规格不同，各自所需的加工时间,也是不同的，加工每吨,A,原料需要,2,个小时，加工每吨,B,原料需,要,1,小时，而公司总共有,600,个加工小时。又知道每吨,A,原料的,价格为,2,万元，每吨,B,原料的价格为,3,万元，试问在满足生产需,要的前提下，在公司加工能力的范围内，如何购买,A,，,B,两种,原料，使得购进成本最低？,17,线性规划图解法（续）,解：目标函数：,Min f=2x,1,+3 x,2,约束条件：,s.t.x,1,+x,2,350,x,1,125,2 x,1,+x,2,600,x,1,x,2,0,采用图解法。如下图：得,Q,点坐标（,250,，,100,）为最优解。,100,200,300,400,500,600,100,200,300,400,600,500,x,1,=125,x,1,+x,2,=350,2x,1,+3x,2,=800,2x,1,+3x,2,=900,2x,1,+x,2,=600,2x,1,+3x,2,=1200,x,1,x,2,Q,18,三、线性规划一般形式,企业管理的重点内容之一就是在各种生产因素和产品的调配问题上。,一方面，在一固定阶段，企业管理者所能“投入”的生产因素：原料、人力、设备时间是由一定限量的。在一固定期间，任何一工厂的厂房、工场、机器、一切固定资本是不会变动的，再雄厚的资本，也还是有它的限度。再从流动资本来看，原料的来源和存量，各种技工的人数和时间，在一相当的短期中也是有一定的限度。,19,线性规划一般形式,另一方面，企业管理者“投入”生产因素时，一定有一完整的目标。在商言商，企业管理者的目标当然是求最高的利润和最低的成本。如何将受时间、空间、数量限制的“投入”生产因素调配“得当”，达到最佳的境界而获得最佳的“产出”量，因而获得最大的收益。,以上就是企业管理者须面对的一个问题的两个方面。企业管理者不仅要知道如何调配手头上有限的生产因素，同时要从不同的调配中，找出最佳的调配，来达到他的企业经营目标,最低成本、最高利润。,20,线性规划一般形式,事实上，用最低的代价去追求最高的收获，原是一种理性的要求，因此在任何理性活动中，都有一求“最佳”问题的存在。,21,例题,3,配方问题,养海狸鼠 饲料中营养要求：,V,A,每天至少,700,克，,V,B,每天至少,30,克，,V,C,每天刚好,200,克。现有五种饲料，搭配使用，饲料成分如下表：,饲料,Va,Vb,Vc,价格元,/KG,I,II,III,IV,V,3,2,1,6,18,1,0.5,0.2,2,0.5,0.5,1,0.2,2,0.8,2,7,4,9,5,营养要求,700,30,200,22,例题,3,建模,设抓取饲料,I,x,1,kg;,饲料,II,x,2,kg;,饲料,III,x,3,kg,目标函数：最省钱,m,inZ=2x,1,+7x,2,+4x,3,+9x,4,+5x,5,约束条件：,3x,2,+2x,2,+x,3,+6x,4,+18x,5,700,营养要求：,x,1,+0.5x,2,+0.2x,3,+2x,4,+0.5x,5,30,0.5x,1,+x,2,+0.2x,3,+2x,4,+0.8x,5,=200,用量要求：,x,1,50,x,2,60,x,3,50,x,4,70,x,5,40,非负性要求：,x,1,0,x,2,0,x,3,0,x,4,0,x,5,0,23,例题,4,：人员安排问题,医院护士,24,小时值班，每次值班,8,小时。不同时段需要的护士人数不等。据统计：,序号,时段,最少人数,安排人数,1,0610,60,X,1,2,1014,70,X,2,3,1418,60,X,3,4,1822,50,X,4,5,2202,20,X,5,6,0206,30,x,6,24,例题,4,建模,目标函数：,min Z=x,1,+x,2,+x,3,+x,4,+x,5,+x,6,约束条件：,x,1,+x,2,70,x,2,+x,3,60,x,3,+x,4,50,x,4,+x,5,20,x,5,+x,6,30,非负性约束：,x,j,0,j,=1,2,6,25,归纳：线性规划的一般模式,目标函数：,max(min)Z=c,1,x,1,+c,2,x,2,+c,3,x,3,+c,n,x,n,约束条件：,a,11,x,1,+a,12,x,2,+a,13,x,3,+a,1n,x,n,(=)b,1,a,21,x,1,+a,22,x,2,+a,23,x,3,+a,2n,x,n,(=)b,2,a,m1,x,1,+a,m2,x,2,+a,m3,x,3,+a,mn,x,n,(=)b,n,非负性约束：,x,1,0,x,2,0,x,n,0,26,四、线性规划的标准型,一般形式,目标函数：,Max,（,Min,）,z=c,1,x,1,+c,2,x,2,+c,n,x,n,约束条件：,s.t.,a,11,x,1,+,a,12,x,2,+,a,1n,x,n,（,=,）,b,1,a,21,x,1,+,a,22,x,2,+,a,2n,x,n,（,=,）,b,2,a,m1,x,1,+,a,m2,x,2,+,a,mn,x,n,（,=,）,b,m,x,1,，,x,2,，,，,x,n,0,标准形式,目标函数：,Max z =c,1,x,1,+c,2,x,2,+c,n,x,n,约束条件：,s.t.,a,11,x,1,+,a,12,x,2,+,a,1n,x,n,=b,1,a,21,x,1,+,a,22,x,2,+,a,2n,x,n,=b,2,a,m1,x,1,+,a,m2,x,2,+,a,mn,x,n,=b,m,x,1,，,x,2,，,，,x,n,0,，,b,i,0,27,线性规划的标准型,可以看出，线性规划的标准形式有如下四个特,点：,目标最大化；,约束为等式；,决策变量均非负；,右端项非负。,对于各种非标准形式的线性规划问题，我们总可,以通过以下变换，将其转化为标准形式,:,28,线性规划的标准型,1.,极小化目标函数的问题：,设目标函数为,Min,f,=,c,1,x,1,+,c,2,x,2,+,+,c,n,x,n,(,可以,),令,z,-f,，,则该极小化问题与下面的极大化问题有相同的最优解，,即,Max,z,=,-c,1,x,1,-c,2,x,2,-,-c,n,x,n,但必须注意，尽管以上两个问题的最优解相同，但它们,最优解的目标函数值却相差一个符号，即,Min,f,-Max,z,29,线性规划的标准型,2,、约束条件不是等式的问题,：,设约束条件为,a,i1,x,1,+,a,i2,x,2,+,+,a,in,x,n,b,i,可以引进一个新的变量,s,，使它等于约束右边与左,边之差,s,=,b,i,(,a,i1,x,1,+,a,i2,x,2,+,+,a,in,x,n,),显然，,s,也具有非负约束，即,s,0,，,这时新的约束条件成为,a,i1,x,1,+,a,i2,x,2,+,+,a,in,x,n,+,s,=,b,i,30,线性规划的标准型,当约束条件为,a,i1,x,1,+,a,i2,x,2,+,+,a,in,x,n,b,i,时，,类似地令,s,=(,a,i1,x,1,+,a,i2,x,2,+,+,a,in,x,n,)-,b,i,显然，,s,也具有非负约束，即,s,0,，这时新的约,束条件成为,a,i1,x,1,+,a,i2,x,2,+,+,a,in,x,n,-,s,=,b,i,31,线性规划的标准型,为了使,约束由不等式成为等式而引进的变量,s,当,不等式为“小于等于”时称为,“,松弛变量,”,；当不等式,为“大于等于”时称为,“,剩余变量,”,。如果原问题中有,若干个非等式,约束，则将其转化为标准形式时，必须,对各个约束引进不同的松弛变量。,3.,右端项有负值的问题：,在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如,b,i,40,选,X,2,从,0,，,X,1,=0,X,3,=30-2X,2,0,X,2,30,/,2,X,4,=60-2X,2,0,X,2,60,/,2,X,5,=24-2X,2,0,X,2,24,/,2,X,2,=min(,30,/,2,60,/,2,24,/,2,)=12,X,2,进基变量，,X,5,出基变量。,44,B,2,=(P,3,P,4,P,2,),Z=0+40X,1,+50X,2,X,3,+2X,2,=30-X,1,X,4,+2X,2,=60-3X,1,2X,2,=24-X,5,45,1,/,2,，,代入式，,Z=600 +40X,1,-25X,5,X,3,=6 -X,1,+X,5,X,4,=,36-3X,1,+X,5,X,2,=12 -,1,/,2,X,5,令,X,1,=X,5,=0 X,(2),=(0,12,6,36,0),T,Z,(2),=600,46,(2),判断,40,0,X,(2),不是,。,(3),选,X,1,从,0,，,X,5,=0,X,3,=6-X,1,0,X,4,=,36-3X,1,0,X,2,=12,0,X,1,=min(,6,/,1,36,/,3,1,)=6,X,1,进基，,X,3,出基。,47,B,3,=(P,1,P,4,P,2,),Z=840-40X,3,+15X,5,X,1,=6 -X,3,+X,5,X,4,=,18+3X,3,-2X,5,X,2,=12 -,1,/,2,X,5,令,X,3,=X,5,=0,X,(3),=(6,12,0,18,0),T,Z,(3),=840,48,(2),15,0,X,(3),不是,(3),选,X,5,从,0,，,X,3,=0,X,1,=6 +X,5,0,X,4,=,18 -2X,5,0,X,2,=12-,1,/,2,X,5,0,X,5,=min(,18,/,2,12,/,1/2,)=9,X,5,进基，,X,4,出基。,49,B,4,=(P,1,P,5,P,2,),Z=975-,35,/,2,X,3,-,15,/,2,X,4,X,1,=15+,1,/,2,X,3,-,1,/,2,X,4,X,5,=,9 +,3,/,2,X,3,-,1,/,2,X,4,X,2,=,15,/,2,-,3,/,4,X,3,+,1,/,4,X,4,令,X,3,=X,4,=0,X,(4),=(15,15,/,2,0,0,9),T,Z,(4),=975,50,0,(0,0),X,2,X,1,A,D,C,B,(0,12),(6,12),(15,7.5),51,maxZ=CX,当,LP,的数学模型为矩阵型,AX=b,时，,X,0,两个重要公式：,X,B,=B,-1,b-B,-1,NX,N,Z=C,B,B,-1,b+(C,N,-C,B,B,-1,N)X,N,当,X,N,=0,时，,B,-1,b,0,X=,Z=C,B,B,-1,b,52,当,LP,的数学模型为一般型时,两个重要公式形如：,53,1 00 a,1m+1,a,1n,0 10 a,2m+1,a,2n,0 01 a,mm+1,a,mn,设,A=,B=(P,1,P,2,P,m,)=I,54,当,X,j,=0,(j=m+1,n),时,55,1.5.2,单纯形法原理,56,此时，,B=(P,1,P,2,P,m,),对应的基本可行解为,(1),(1),57,定理,1,：对解,X,(1),，若检验数,j,(j=m+1,n,),全部,0,，,则,X,(1),为最优解。,定理,2,：对,X,(1),，若有某个非基变量,X,m+k,m+k,0,且相应的,P,m+k,=(,a,1m+k,a,mm+k,),T,0,，,则原问题无有限最优解。,58,定理,2,证明,X,i,=,b,i,-,a,ij,x,j,J=m+1,n,令非基变量,X,m+k,=,(,0,),X,(2),=(,b,1,-,a,1m+k,b,m,-,a,mm+k,0,0),T,AX,(2),=b X,(2),0,Z=Z,0,+,m+k,当,时,Z,59,例：,Z=30X,1,+20X,2,-X,1,+3X,2,+X,3,=10,-3X,1,+2X,2,+X,4,=15,初始基,B,1,=(P,3,P,4,),X,(1),=(0,0,10,15),T,Z,(1),=0,Z=0,30X,1,+20X,2,X,3,=10-(-X,1,+3X,2,),X,4,=15-(-3X,1,+2X,2,),60,选中,X,1,从,0,，,X,2,=0,X,3,=10-(-X,1,),0,X,4,=15-(-3X,1,),0,求,X,1,，,X,1,+,Z,+,61,换基迭代公式：,(1),、,决定换入变量：,max,j,=,m+k,，,则,X,m+k,为换入变量,j,0,(2),、,决定换出变量：,b,i,-,a,im+k,X,m+k,0,(i=1,2,m,),X,m+k,b,i,a,im+k,(a,im+k,0,),62,=,min,a,im+k,0 =,b,i,a,im+k,b,r,a,rm+k,则,X,r,为换出变量,。,63,定理,3,：经单纯形法得到的,X,(2),=(,b,1,-,a,1m+k,b,m,-,a,mm+k,0,0),T,是基本可行解，且,Z,(2),Z,(1),64,证明：设,X,r,=,X,m,X,m,=0,X,m+k,=,=,b,m,A,mm+k,(,0,),X,(1),中,P,1,P,m,线性无关，下证,P,1,P,m-1,P,m+k,线性无关。,若否，因为,P,1,P,m,线性无关,则,P,m+k,=,a,1m+k,P,1,+,a,mm+k,P,m,而,P,m+k,=,l,1,P,1,+,l,m-1,P,m-1,65,-,(,a,1m+k,-,l,1,),P,1,+(,a,m-1m+k,-,l,m-1,),P,m-1,+,a,m m+k,P,m,=,0,P,1,P,m,线性相关，矛盾。,X,(2),是基本解，且是可行解,66,单纯形法基本步骤,(1),、定初始基，初始基本可行解,(3),、,若有,k,0,，,P,k,全,0,，,停，,没有有限最优解；否则转,(4),(2),、对应于非基变量检验数,j,全,0,。,若是，停，得到最优解；,若否，转,(3),。,67,=,min,a,im+k,0 =,b,i,a,im+k,b,r,a,rm+k,定,X,r,为换出变量，,a,rm+k,为,主元。,由最小,比值法求：,max,j,=,m+k,X,m+k,换入变量,j,0,(4),、,68,转,(2),m+k,0,a,1m+k,0,a,rm+k,1,a,mm+k,0,初等行变换,P,m+k,=,(5),、以,a,rm+k,为中心，换基迭代,69,证明可用归纳法（略）,X,(1),X,(2),X,(3),X,X,X,在边界上,X,在内部,X,X,+(1-),X,(2),(0,1,),X,X,(1),+(1-),X,(3),X,(1),(1-,),X,(2),(1-),X,(3),X=,+,+,(0,1,),70,证明：,设,X,(1),X,(k),为可行域顶点，若,X,*,不是顶点，但,max Z=C,X,*,X,*,=,定理,2,：可行域有界，最优值必可在顶点得到,i,X,(i),k,i=1,i,=1,k,i=1,0,i,1,CX,*,=,i,C,X,(i),k,i=1,i,C,X,(m),k,i=1,=,C,X,(m),设,C,X,(m),Max(,C,X,(i),),1,i,k,71,Z,(1),=,C,i,b,i,i=1,m,Z,(2),=,C,i,(b,i,-,a,im+k,)+,C,m+k,i=1,m,=,C,i,b,i,-,+,C,m+k,i=1,m,C,i,a,im+k,i=1,m,=,C,i,b,i,+,C,m+k,-,C,i,a,im+k,i=1,m,i=1,m,Z,(2),-,Z,(1),=,(,C,m+k,-Z,m+k,),=,m+k,0,72,1.5.3,单纯形表,C,1,C,2,C,m,C,m+1,C,m+k,C,n,X,1,X,2,X,m,X,m+1,X,m+k,X,n,C,B,X,B,Z,0,0 0,0 ,m+1,m+k,n,C,1,X,1,b,1,1 0,0 a,1m+1,a,1m+k,a,1n,C,2,X,2,b,2,0 1,0 a,2m+1,a,2m+k,a,2n,C,r,X,r,b,r,0 0,0 a,rm+1,a,rm+k,a,rn,C,m,X,m,b,m,0 0,1 a,mm+1,a,mm+k,a,nn,73,40 50 0 0 0,X,1,X,2,X,3,X,4,X,5,C,B,X,B,0 40 50 0 0 0 ,0,X,3,30 1 2 1 0 0 15,0,X,4,60,3,2 0 1 0 30,0,X,5,24 0 (2)0 0 1 12,X,B,600 40 0 0 0 -25,0,X,3,6 (1)0 1 0 -1 6,0,X,4,36 3 0 0 1 -1 12,50,X,2,12 0 1 0 0 1/2,840 0 0 -40 0 15,40,X,1,6 1 0 1 0 -1,0,X,4,18 0 0 -3 1 2,50,X,2,12 0 1 0 0 1/2,74,X,B,975 0 0 -35/2 -15/2 0,40,X,1,15 1 0 -1/2 1/2 0,0,X,5,9 0 0 -3/2 1/2 1,50,X,2,15/2 0 1 3/4 -1/4 0,本问题的最优解,X=(15,15/2,0,0,9),T,Z=975,75,几点说明：,(1),、例,maxZ=,X,1,+2X,2,X,1,4,X,2,3,X,1,+2X,2,8,X,1,X,2,0,X,1,+X,3,=,4,X,2,+X,4,=,3,X,1,+2X,2,+X,5,=,8,X,1,X,5,0,76,1 2 0 0 0,X,1,X,2,X,3,X,4,X,5,C,B,X,B,0 1 2 0 0 0,0,X,3,4 1 0 1 0 0,0,X,4,3 0 (1)0 1 0,0,X,5,8 1 2 0 0 1,C,B,X,B,6 1 0 0 -2 0,0,X,3,4 1 0 1 0 0,2,X,2,3 0 1 0 1 0,0,X,5,2,(1)0 0 -2 1,(,接下表,),77,1 2 0 0 0,X,1,X,2,X,3,X,4,X,5,C,B,X,B,8 0 0 0 0 -1,0,X,3,2 0 0 1 (2)-1,2,X,2,3 0 1 0 1 0,1,X,1,2 1 0 0 -2 1,C,B,X,B,8 0 0 0 0 -1,0,X,4,1 0 0 1/2 1 -1/2,2,X,2,2 0 1 -1/2 0 1/2,1,X,1,4,1 0 1 0 0,78,X,(1),=,(2,3),Z,(1),=8,X,(2),=,(4,2),Z,(2),=8,无穷多解,全部解：,X,=+(1-),(0,1,),2 4,3 2,79,(2),、例：,求,minZ=,X,1,-X,2,+X,3,-3X,5,X,2,+X,3,-X,4,+2X,5,=,6,X,1,+2X,2,-2X,4,=,5,2X,2,+X,4,+3X,5,+X,6,=,8,X,1,X,6,0,80,1 -1 1 0 -3 0,X,1,X,2,X,3,X,4,X,5,X,6,C,B,X,B,11 0 -4 0 3 -5 0,1,X,3,6 0 1 1 -1 2 0,1,X,1,5 1 2 0 -2 0 0,0,X,6,8 0 2 0 1 3 1,C,B,X,B,-7/3 0 -2/3 0 14/3 0 5/3,1,X,3,2/3 0 -1/3 1 -5/3 0 -2/3,1,X,1,5 1 2 0 -2 0 0,-3,X,5,8/3,0 2/3 0 1/3 1 1/3,C,B,X,B,-4 1/3 0 0 4 0 5/3,1,X,3,3/2 1/6 0 1 -2 0 -2/3,-1,X,2,5/2 1/2 1 0 -1 0 0,-1,X,5,1 -2/3 0 0 1 1 1/3,81,判定定理,1,：基本可行解,X,，当全部,j,0,时，,X,为最优解。,判定定理,2,：对可行基,B,，当某,k,0,，且,P,k,=(,a,1k,a,mk,),T,0,，,则原问题无有限最优解。,换入变量：,max,j,=,j,=,m+k,X,m+k,j,0,则判定原问题无可行解。,98,两阶段法原理：,(1),、辅助问题的基本可行解,X,(0),为最优解，对应,最小值,=0,则,X,(0),的前,n,个分量是原问题的基本可行解。,99,设,X,(0),=(X,1,(0),X,n,(0),y,1,(0),y,n,(0),),T,使,a,ij,x,j,(0),+,y,i,(0),b,i,(i=1,2,n),n,j=1,=0,y,1,(0),=,=,y,n,(0),=0,a,ij,x,j,(0),b,i,(i=1,m),n,j=1,证明：,100,(2),、原问题有可行解时，辅助问题最优值,=0,。,证明：若原问题有可行解,X,(0),=(X,1,(0),X,n,(0),),T,使,a,ij,x,j,(0),b,i,(i=1,m),j=1,n,作,X,(1),=(X,1,(0),X,n,(0),0 0,),T,=,y,i,0,=0,i=1,m,必为辅助问题最优解,101,maxZ,=,-X,1,+2X,2,X,1,+X,2,2,-X,1,+X,2,1,X,2,3,X,1,X,2,0,例,2,：,102,第,(1),阶段：,minW,=,X,6,+X,7,X,1,+X,2,-X,3,+X,6,=,2,-X,1,+X,2,-X,4,+X,7,=,1,X,2,+X,5,=,3,X,1,X,7,0,103,0 0 0 0 0 1 1,X,1,X,2,X,3,X,4,X,5,X,6,X,7,C,B,X,B,3,0,-2,1 1 0,0 0,1,X,6,2 1 1 -1 0 0 1 0,1,X,7,1 -1,(1)0 -1 0 0 1,0 X,5,3 0 1 0 0 1 0 0,C,B,X,B,1,-2,0,1 -1 0,0 2,X,6,1 (2)0 -1 1 0 1 -1,X,2,1 -1,1 0 -1 0 0 1,X,5,2 1 0 0 1 1 0 -1,X,B,0,0,0,0 0 0,1 1,X,1,1/2 1 0 -1/2 1/2 0 1/2 -1/2,X,2,3/2 0,1 -1/2 -1/2 0 1/2 1/2,X,5,3/2 0 0 -1/2 1/2 1 -1/2 -1/2,104,-1 2 0 0 0,X,1,X,2,X,3,X,4,X,5,C,B,X,B,3/2 0 0 1/2 3/2 0,-1 X,1,1/2 1 0 -1/2 (1/2)0,2 X,2,3/2 0 1 -1/2 -1/2 0,0 X,5,3/2 0 0 1/2 1/2 1,X,B,4 -3 0 2 0 0,X,4,1 2 0 -1 1 0,X,2,2 1 1 -1 0 0,X,5,1 -1 0 (1)0 1,X,B,6,1 0 0 0 -2,X,4,2 1 0 0 1 1,X,2,3 0 1 0 0 1,X,3,1 -1 0 1 0 1,105,例,3,：,maxZ,=,2X,1,+X,2,5X,1,+10X,2,8,2X,1,+2X,2,1,X,1,，,X,2,0,106,第,(1),阶段：,minW,=,X,5,5X,1,+10X,2,-X,3,+X,5,=8,2X,1,+2X,2,+X,4,=,1,X,1,X,5,0,107,0 0 0 0 1,X,1,X,2,X,3,X,4,X,5,C,B,X,B,8 -5 -10 1 0 0,1 X,5,8 5 10 -1 0 1,0 X,4,1 2 (2)0 1 0,X,B,3 5 0 1 5 0,1 X,5,3 -5 0 -1 -5 1,0 X,2,1/2 1 1 0 1/2 0,108,X,2,X,1,O,109,第,1,阶段 最优基,B*min,=,*,(1),、,*,0,(2),、,*,=0,y,i,0(i=1,2,m,),B*,基变量无人工变量,B*,基变量含人工变量,y,r,单纯形表中，,y,r,+,a,rk,y,k,+,a,rj,x,j,=0 (,),k J,j J,J,：非基变量下标集合,110,1),a,rj,全,=,0,(,),式多余方程,2),a,rj,有,0,元，设为,a,rs,0,以,a,rs,为主元，换基迭代，最后得到,111,例,4,、求,maxZ,=,-4X,1,-3X,3,1/2X,1,+X,2,+1/2X,3,-2/3X,4,=,2,3/2X,1,+3/4X,3,=,3,3X,1,-6X,2,+4X,4,=,0,X,1,X,2,X,3,X,4,0,满足,112,0 0 0 0 1 1 1,X,1,X,2,X,3,X,4,y,1,y,2,y,3,C,B,X,B,5 -5 5 -5/4 -10/3 0 0 0,1 y,1,2 1/2 1 1/2 -2/3 1 0 0,1 y,2,3 3/2 0 3/4 0 0 1 0,1 y,3,0 3 6 0 4 0 0 1,C,B,X,B,5 0 -5 -4/5 10/3 0 0 5/3,1 y,1,2 0 2 1/2 -4/3 1 0 -1/6,1 y,2,3 0 3 3/4 2 0 1 -1/2,0 X,1,0 1 -2 0 4/3 0 0 1/3,第 一 阶 段,一,二,113,C,B,X,B,0 0 0 0 0 5/2 0 5/4,0 X,2,1 0 1 1/4 -2/3 1/2 0 -1/2,1 y,2,0 0 0 0 0 -3/2 1 -1/4,0 X,1,2 1 0 1/2 0 1 0 1/6,第一阶段,三,-4 0 -3 0,X,1,X,2,X,3,X,4,C,B,X,B,-8 0 0 -1 0,0 X,2,1 0 1 1/4 -2/3,-4 X,4,2 1 0 1/2 0,第二阶段,114,的特殊情况,:,第,1,阶段结束时,有人工变量在基中取,0,但,X,i,系数全为0,此方程为多余方程。,115,例,5,、求,minZ,=4,X,1,+3X,3,1/2X,1,+X,2,+1/2X,3,-2/3X,4,=2,3/2X,1,-1/2X,3,=,3,3X,1,-6X,2,+4X,4,=0,X,1,X,2,X,3,X,4,0,满足,116,0 0 0 0 1 1 1,X,1,X,2,X,3,X,4,y,1,y,2,y,3,C,B,X,B,5 -5 5 0 -10/3 0 0 0,1 y,1,2 1/2 1 1/2 -2/3 1 0 0,1 y,2,3 3/2 0 -1/2 0 0 1 0,1 y,3,0 3 6 0 4 0 0 1,C,B,X,B,5 0 -5 0 10/3 0 0 5/3,y,1,2 0 2 1/2 -4/3 1 0 -1/6,y,2,3 0 3 -1/2 -2 0 1 -1/2,X,1,-2 1 -2 0 4/3 0 0 1/3,第 一 阶 段,一,二,117,C,B,X,B,0 0 0 5/4 0 5/2 0 5/4,X,2,1 0 1 1/4 -2/3 1/2 0 -1/2,y,2,0 0 0 -5/4 0 -3/2 1 -1/4,X,1,2 1 0 1/2 0 1 0 1/6,C,B,X,B,0 0 0 0 0 1 1 1,X,2,1 0 1 0 -2/3 1/5 1/5 -2/15,X,3,0 0 0 1 0 1/5 -4/5 1/5,X,1,2 1 0 0 0 2/5 2/5 1/15,第 一 阶 段,三,四,118,-4 0 -3 0,X,1,X,2,X,3,X,4,C,B,X,B,-8 0 0 0 0,0 X,2,1 0 1 0 -2/3,-3 X,3,0 0 0 1 0,-4 X,1,2 1 0 0 0,第二阶段,的特殊情况，可将人工变量换出,119,单纯形法小结：,1),、标准型中有单位基。,2),、标准型中没有单位基，用大,M,法加人工变量，使之构成单位基。,求,maxZ,时，目标中,M,X,j,求,minZ,时，目标中,M,X,j,3),、判定最优解定理：,maxZ,问题，检验数,j,0,minZ,问题，检验数,j,0,120,4),、解的几种情况：,唯一解,无穷多解最优表中非基变量检验数有为,0,者。,无有限最优解,max,j,0,但,P,j,0,min,j,0,但,P,j,0,无可行解,最优表中人工变量在基中，且,0,。,建模有问题,5),、退化解问题,121,122,第三章 运筹学优化模型,大连海事大学,刘巍,123,第,3,节 对偶线性规划与影子价格,一、对偶问题,再谈招聘总经理,124,泰山工厂生产状况,泰山工厂可以生,产两种产品出售，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：,目前生产现状：,不生产产品,A,，生产产品,B,每天,30,，获利,3600,产品,A,产品,B,资源限量,设 备,劳动力,原材料,9,4,3,4,5,10,360,200,300,利润,元,/kg,70,120,125,招聘总经理！,约翰：我应聘！,在现有资源状况下，我可以使利润达到,4280,！,方案是：生产,A,产品,20,，生产,B,产品,24,可行性：,9*20+4*24=276,360,4*20+5*24=200,3*20+10*24=300,126,怎么达到的？,约翰使用了运筹学中的线性规划模型,问题：如何安排生产计划，使得获利最多？,步骤：,1,、确定决策变量：设生产,A,产品,x,1,kg,B,产品,x,2,kg,2,、确定目标函数：,maxZ=70X,1,+120X,2,3,、确定约束条件：设备约束,9X,1,+4X,2,360,人力约束,4X,1,+5X,2,200,原材料约束,3X,1,+10X,2,3