线性规划在管理中的应用

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,1,3,4,5,2,线性规划在管理中的应用,线性规划问题的建模过程,1.,理解要解决的问题，了解解题的目标和条件；,2.,定义决策变量（,x,1,，,x,2,，,，,x,n,），每一组值表示一个方案；,3.,用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；,4.,用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件。,人力资源分配的问题（,1,）,例,1,某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：,设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员,?,人力资源分配的问题（,1,）,解：设,x,i,表示第,i,班次时开始上班的司机和乘务人员数，这样我们建立如下的数学模型：,目标函数：,min,x,1,+,x,2,+,x,3,+,x,4,+,x,5,+,x,6,约束条件：,s.t.,x,1,+,x,6,60,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,1,x,2,x,3,x,4,x,5,x,6,0,最优解：,x,1,=50,，,x,2,=20,，,x,3,=50,，,x,4,=0,，,x,5,=20,，,x,6,=10,，共,150,人。,人力资源分配的问题（,2,）,例,2,一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作,5,天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？,人力资源分配的问题（,2,）,解：,设,x,i,(,i,=1,2,7),表示星期一至日开始休息的人数，这样我们建立如下的数学模型。,目标函数：,min,x,1,+,x,2,+,x,3,+,x,4,+,x,5,+,x,6,+,x,7,约束条件：,s.t.,x,1,+,x,2,+,x,3,+,x,4,+,x,5,28,x,2,+,x,3,+,x,4,+,x,5,+,x,6,15,x,3,+,x,4,+,x,5,+,x,6,+,x,7,24,x,4,+,x,5,+,x,6,+,x,7,+,x,1,25,x,5,+,x,6,+,x,7,+,x,1,+,x,2,19,x,6,+,x,7,+,x,1,+,x,2,+,x,3,31,x,7,+,x,1,+,x,2,+,x,3,+,x,4,28,x,1,x,2,x,3,x,4,x,5,x,6,x,7,0,最优解：,x,1,=12,，,x,2,=0,，,x,3,=11,，,x,4,=5,，,x,5,=0,，,x,6,=8,，,x,7,=0,，共,36,人。,生产计划的问题（,1,）,例,3,某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？,生产计划的问题（,1,）,解：设,x,1,x,2,x,3,分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，,x,4,x,5,分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。,求,x,i,的利润：利润,=,售价,-,各成本之和,产品甲全部自制的利润,23-(3+2+3)=15,产品甲铸造外协、其余自制的利润,23-(5+2+3)=13,产品乙全部自制的利润,18-(5+1+2)=10,产品乙铸造外协、其余自制的利润,18-(6+1+2)=9,产品丙的利润,16-(4+3+2)=7,可得到,x,i,（,i,=1,2,3,4,5,）的利润分别为,15,、,10,、,7,、,13,、,9,元。,生产计划的问题（,1,）,通过以上分析,可建立如下的线性规划模型,:,目标函数：,max 15,x,1,+10,x,2,+7,x,3,+13,x,4,+9,x,5,约束条件：,5,x,1,+10,x,2,+7,x,3,8000,6,x,1,+4,x,2,+8,x,3,+6,x,4,+4,x,5,12000,3,x,1,+2,x,2,+2,x,3,+3,x,4,+2,x,5,10000,x,1,x,2,x,3,x,4,x,5,0,最优解：,x,1,=1600,，,x,2,=,x,3,=,x,4,=0,，,x,5,=600,生产计划的问题（,2,）,例,4,永久机械厂生产,、,、,三种产品，均要经过,A,、,B,两道工序加工。设有两种规格的设备,A1,、,A2,能完成,A,工序；有三种规格的设备,B1,、,B2,、,B3,能完成,B,工序。,可在,A,、,B,的任何规格的设备上加工；,可在任意规格的,A,设备上加工，但对,B,工序，只能在,B1,设备上加工；,只能在,A2,与,B2,设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？,生产计划的问题（,2,）,解：设,x,ijk,表示第,i,种产品，在第,j,种工序上的第,k,种设备上加工的数量。,约束条件为：,s.t.5,x,111,+10,x,211,6000,（设备,A,1,）,7,x,112,+9,x,212,+12,x,312,10000,（设备,A,2,）,6,x,121,+8,x,221,4000,（设备,B,1,）,4,x,122,+11,x,322,7000,（设备,B,2,）,7,x,123,4000,（设备,B,3,）,x,111,+,x,112,=,x,121,+,x,122,+,x,123,（,产品在,A,、,B,工序加工的数量相等）,x,211,+,x,212,=,x,221,（,产品在,A,、,B,工序加工的数量相等）,x,312,=,x,322,（,产品在,A,、,B,工序加工的数量相等）,x,ijk,0,i,=1,2,3;,j,=1,2;,k,=1,2,3,生产计划的问题（,2,）,目标函数为计算利润最大化，利润的计算公式为：,利润,=,（销售单价,-,原料单价）*产品件数,之和,-,（每台时的 设备费用*设备实际使用的总台时数）之和。,这样得到目标函数：,max (1.25 0.25)(,x,111,+,x,112,)+(2 0.35),x,221,+(2.8 0.5),x,312,300/6000(5,x,111,+10,x,211,)321/10000(7,x,112,+9,x,212,+12,x,312,)250/4000(6,x,121,+8,x,221,)783/7000(4,x,122,+11,x,322,)200/4000(7,x,123,),经整理可得：,max 0.75,x,111,+0.7753,x,112,+1.15,x,211,+1.3611,x,212,+1.9148,x,312,0.375,x,121,0.5,x,221,0.4475,x,122,1.2304,x,322,0.35,x,123,解得：,x,111,=1200,，,x,112,=230.049,，,x,211,=0,，,x,212,=500,，,x,312,=324.138,，,x,121,=0,，,x,221,=500,，,x,122,=858.6206,，,x,322,=324.138,，,x,123,=571.4286,生产计划的问题（,2,）,另解：设,y,ijk,表示在第,j,种设备上完成工序,A,、在第,k,种设备上完成工序,B,的第,i,种产品的数量。,目标函数为：,max (1.25 0.25)(,y,111,+,y,112,+,y,113,+,y,121,+,y,122,+,y,123,)+(2 0.35)(,y,211,+,y,221,)+(2.8 0.5),y,322,300/6000 5(,y,111,+,y,112,+,y,113,)+10,y,211,321/10000 7(,y,121,+,y,122,+,y,123,)+9,y,221,+12,y,322,250/4000 6(,y,111,+,y,121,)+8(,y,211,+,y,221,)783/7000 4(,y,112,+,y,122,)+11,y,322,200/4000 7(,y,113,+,y,123,),约束条件为：,s.t.5(,y,111,+,y,112,+,y,113,)+10,y,211,6000,（设备,A,1,）,7(,y,121,+,y,122,+,y,123,)+9,y,221,+12,y,322,10000,（设备,A,2,）,6(,y,111,+,y,121,)+8(,y,211,+,y,221,)4000,（设备,B,1,）,4(,y,112,+,y,122,)+11,y,322,7000,（设备,B,2,）,7(,y,113,+,y,123,)4000,（设备,B,3,）,y,ijk,0,i,=1,2,3;,j,=1,2;,k,=1,2,3,套裁下料问题,例,5,某工厂要做,100,套钢架，每套用长为,2.9m,，,2.1m,，,1.5m,的圆钢各一根。已知原料每根长,7.4m,，问：应如何下料，可使所用原料最省？,解：共可设计下列,5,种下料方案，见下表,设,x,1,x,2,x,3,x,4,x,5,分别为上面,5,种方案下料的原材料根数。,套裁下料问题,最优解：,x,1,=30,，,x,2,=10,，,x,3,=0,，,x,4,=50,，,x,5,=0,约束条件中，用“,=”,还是“,”？,目标函数：,min,x,1,+,x,2,+,x,3,+,x,4,+,x,5,约束条件：,s.t.,x,1,+2,x,2,+,x,4,100,2,x,3,+2,x,4,+,x,5,100,3,x,1,+,x,2,+2,x,3,+3,x,5,100,x,1,x,2,x,3,x,4,x,5,0,配料问题（,1,）,例,6,某工厂要用三种原料,1,、,2,、,3,混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？,解：设,x,ij,表示第,i,种（甲、乙、丙）产品中原料,j,的含量。,目标函数：利润最大，利润,=,收入,原料支出,约束条件：规格要求,4,个；供应量限制,3,个。,配料问题（,1,）,目标函数：,max 50(,x,11,+,x,12,+,x,13,)+35(,x,21,+,x,22,+,x,23,),+25(,x,31,+,x,32,+,x,33,),65(,x,11,+,x,21,+,x,31,)25(,x,12,+,x,22,+,x,32,)35(,x,13,+,x,23,+,x,33,),=15,x,11,+25,x,12,+15,x,13,30,x,21,+10,x,22,40,x,31,10,x,33,约束条件：,从第,1,个表中有：,x,11,0.5(,x,11,+,x,12,+,x,13,),x,12,0.25(,x,11,+,x,12,+,x,13,),x,21,0.25(,x,21,+,x,22,+,x,23,),x,22,0.5(,x,21,+,x,22,+,x,23,),从第,2,个表中有：,x,11,+,x,21,+,x,31,100,x,12,+,x,22,+,x,32,100,x,13,+,x,23,+,x,33,60,配料问题（,1,）,线性规划模型为：,目标函数：,max,z,=15,x,11,+25,x,12,+15,x,13,30,x