线性规划在管理中的应用

13452线性规划在管理中的应用线性规划问题的建模过程•1.理解要解决的问题，了解解题的目标和条件；•2.定义决策变量（x1，x2，…，xn），每一组值表示一个方案；•3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；•4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件。人力资源分配的问题（1）•例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?班次时间所需人数16：00——10：0060210：00——14：0070314：00——18：0060418：00——22：0050522：00——2：002062：00——6：0030人力资源分配的问题（1）解：设xi表示第i班次时开始上班的司机和乘务人员数，这样我们建立如下的数学模型：目标函数：minx1+x2+x3+x4+x5+x6约束条件：s.t.x1+x6≥60x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1,x2,x3,x4,x5,x6≥0最优解：x1=50，x2=20，x3=50，x4=0，x5=20，x6=10，共150人。人力资源分配的问题（2）•例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？时间所需售货员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六28人力资源分配的问题（2）解：设xi(i=1,2,…,7)表示星期一至日开始休息的人数，这样我们建立如下的数学模型。目标函数：minx1+x2+x3+x4+x5+x6+x7约束条件：s.t.x1+x2+x3+x4+x5≥28x2+x3+x4+x5+x6≥15x3+x4+x5+x6+x7≥24x4+x5+x6+x7+x1≥25x5+x6+x7+x1+x2≥19x6+x7+x1+x2+x3≥31x7+x1+x2+x3+x4≥28x1,x2,x3,x4,x5,x6,x7≥0最优解：x1=12，x2=0，x3=11，x4=5，x5=0，x6=8，x7=0，共36人。生产计划的问题（1）•例3．某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？甲乙丙资源限制铸造工时(小时/件)51078000机加工工时(小时/件)64812000装配工时(小时/件)32210000自产铸件成本(元/件)354外协铸件成本(元/件)56--机加工成本(元/件)213装配成本(元/件)322产品售价(元/件)231816生产计划的问题（1）解：设x1,x2,x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。求xi的利润：利润=售价-各成本之和产品甲全部自制的利润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可得到xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。甲乙丙自产铸件成本(元/件)354外协铸件成本(元/件)56--机加工成本(元/件)213装配成本(元/件)322产品售价(元/件)231816生产计划的问题（1）通过以上分析,可建立如下的线性规划模型:目标函数：max15x1+10x2+7x3+13x4+9x5约束条件：5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0最优解：x1=1600，x2=x3=x4=0，x5=600生产计划的问题（2）•例4．永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过A、B两道工序加工。设有两种规格的设备A1、A2能完成A工序；有三种规格的设备B1、B2、B3能完成B工序。Ⅰ可在A、B的任何规格的设备上加工；Ⅱ可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；Ⅲ只能在A2与B2设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？产品单件工时设备ⅠⅡⅢ设备的有效台时满负荷时的设备费用A15106000300A2791210000321B1684000250B24117000783B374000200原料（元/件）0.250.350.50售价（元/件）1.252.002.80生产计划的问题（2）解：设xijk表示第i种产品，在第j种工序上的第k种设备上加工的数量。约束条件为：s.t.5x111+10x211≤6000（设备A1）7x112+9x212+12x312≤10000（设备A2）6x121+8x221≤4000（设备B1）4x122+11x322≤7000（设备B2）7x123≤4000（设备B3）x111+x112=x121+x122+x123（Ⅰ产品在A、B工序加工的数量相等）x211+x212=x221（Ⅱ产品在A、B工序加工的数量相等）x312=x322（Ⅲ产品在A、B工序加工的数量相等）xijk≥0,i=1,2,3;j=1,2;k=1,2,3生产计划的问题（2）目标函数为计算利润最大化，利润的计算公式为：利润=[（销售单价-原料单价）*产品件数]之和-（每台时的设备费用*设备实际使用的总台时数）之和。这样得到目标函数：max(1.25–0.25)(x111+x112)+(2–0.35)x221+(2.8–0.5)x312–300/6000(5x111+10x211)–321/10000(7x112+9x212+12x312)–250/4000(6x121+8x221)–783/7000(4x122+11x322)–200/4000(7x123)经整理可得：max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312–0.375x121–0.5x221–0.4475x122–1.2304x322–0.35x123解得：x111=1200，x112=230.049，x211=0，x212=500，x312=324.138，x121=0，x221=500，x122=858.6206，x322=324.138，x123=571.4286生产计划的问题（2）•另解：设yijk表示在第j种设备上完成工序A、在第k种设备上完成工序B的第i种产品的数量。•目标函数为：max(1.25–0.25)(y111+y112+y113+y121+y122+y123)+(2–0.35)(y211+y221)+(2.8–0.5)y322–300/6000[5(y111+y112+y113)+10y211]–321/10000[7(y121+y122+y123)+9y221+12y322]–250/4000[6(y111+y121)+8(y211+y221)]–783/7000[4(y112+y122)+11y322]–200/4000[7(y113+y123)]•约束条件为：s.t.5(y111+y112+y113)+10y211≤6000（设备A1）7(y121+y122+y123)+9y221+12y322≤10000（设备A2）6(y111+y121)+8(y211+y221)≤4000（设备B1）4(y112+y122)+11y322≤7000（设备B2）7(y113+y123)≤4000（设备B3）yijk≥0,i=1,2,3;j=1,2;k=1,2,3套裁下料问题•例5．某工厂要做100套钢架，每套用长为2.9m，2.1m，1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？解：共可设计下列5种下料方案，见下表方案1方案2方案3方案4方案52.9m120102.1m002211.5m31203合计7.47.37.27.16.6剩余料头00.10.20.30.8设x1,x2,x3,x4,x5分别为上面5种方案下料的原材料根数。套裁下料问题•最优解：x1=30，x2=10，x3=0，x4=50，x5=0•约束条件中，用“=”还是“≥”？目标函数：minx1+x2+x3+x4+x5约束条件：s.t.x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0配料问题（1）•例6．某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？产品名称规格要求单价（元/kg）甲原材料1不少于50%，原材料2不超过25%50乙原材料1不少于25%，原材料2不超过50%35丙不限25原材料名称每天最多供应量单价（元/kg）11006521002536035解：设xij表示第i种（甲、乙、丙）产品中原料j的含量。目标函数：利润最大，利润=收入–原料支出约束条件：规格要求4个；供应量限制3个。配料问题（1）目标函数：max50(x11+x12+x13)+35(x21+x22+x23)+25(x31+x32+x33)–65(x11+x21+x31)–25(x12+x22+x32)–35(x13+x23+x33)=–15x11+25x12+15x13–30x21+10x22–40x31–10x33约束条件：从第1个表中有：x11≥0.5(x11+x12+x13)x12≤0.25(x11+x12+x13)x21≥0.25(x21+x22+x23)x22≤0.5(x21+x22+x23)从第2个表中有：x11+x21+x31≤100x12+x22+x32≤100x13+x23+x33≤60配料问题（1）•线性规划模型为：目标函数：maxz=–15x11+25x12+15x13–30x21+10x22–40x31–10x33约束条件：s.t.0.5x11–0.5x12–0.5x13≥0（原材料1不少于50%）–0.25x11+0.75x12–0.25x13≤0（原材料2不超过25%）0.75x21–0.25x22–0.25x23≥0（原材料1不少于25%）–0.5x21+0.5x22–0.5x23≤0（原材料2不超过50%）x11+x21+x31≤100(供应量限制）x12+x22+x32≤100(供应量限制）x13+x23+x33≤60(供应量限制）xij≥0，i=1,2,3；j=1,2,3解得：x11=100，x21=50，x31=50配料问题（2）•例7.汽油混合问题。一种汽油的特性可用两种指标描述，用“辛烷数”来定量描述其点火特性，用“蒸汽压力”来定量描述其挥发性。某炼油厂有1、2、3、4种标准汽油，其特性和库存量列于下表中，将这四种标准汽油混合，可得到标号为1，2的两种飞机汽油，这两种汽油的性能指标及产量需求也列于下表中。问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号汽油满足需求，并使得1号汽油产量最高？标准汽油辛烷数蒸汽压力(g/cm2)库存量(L)1107.57.11×10-2380000293.011.38×10-2265200387.05.69×10-24081004108.028.45×10-2130100飞机汽油辛烷数蒸汽压力(g/cm2)产量需求1不小于91不大于9.96×