第4章 线性规划问题的应用及计算机求解ppt课件.ppt

《第4章 线性规划问题的应用及计算机求解ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章线性规划问题的应用及计算机求解§4.1人力资源管理的问题§4.2生产计划的问题§4.3套裁下料问题§4.4配料问题§4.5投资问题1§4.1人力资源管理的问题例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?2§4.1人力资源管理的问题解：设xi表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6约束条件：s.t.x1+x6≥60x1+x2≥70x2+x3≥

2、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人3§4.1人力资源管理的问题例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？4§4.1人力资源管理的问题解：设xi(i=1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。目标函数：

3、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人问：假如直接设xi为星期i开始上班的人数，结果一样么？5§4.2生产计划的问题例3某工厂拥有A、B、C三种类型的设备，生产甲、乙

4、、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：用线性规划制订使总利润最大的生产计划。每件产品占用的机时数（小时/件）产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.186§4.2生产计划的问题解：设变量xi为第i种产品的生产件数（i＝1，2，3，4），目标函数z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型：ma

5、xz=5.24x1+7.30x2+8.34x3+4.18x4s.t.1.5x1+1.0x2+2.4x3+1.0x4≤20001.0x1+5.0x2+1.0x3+3.5x4≤80001.5x1+3.0x2+3.5x3+1.0x4≤5000x1，x2，x3，x4≥0求解得：x1=294.12，x2=1500，x3=0，x4=58.82可获得最大利润z=12737.06元产品产品甲产品乙产品丙产品丁利润（元/件）5.247.308.344.18注意注意：最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当产品品种很多，设

6、备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果7§4.2生产计划的问题例4．某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？8§4.2生产计划的问题解：设x1，x2，x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4，x5分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。求xi

7、的利润：利润=售价-各成本之和单位产品甲全部自制的利润=23-(3+2+3)=15单位产品乙全部自制的利润=18-(5+1+2)=10单位产品丙的利润=16-(4+3+2)=7单位产品甲铸造外协，其余自制的利润=23-(5+2+3)=13单位产品乙铸造外协，其余自制的利润=18-(6+1+2)=9可得到单位产品xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。9§4.2生产计划的问题通过以上分析,可建立如下的数学模型:目标函