人员指派问题.docxVIP

问题：要求每个施工点的R公里内至少有一个料场。 1.确定设计变量和目标变量 设第个料场的位置坐标为，第个料场向第个施工点的材料运量为。 第个料场到第个施工点的吨公里数为：，其中。 设（，）表示第个料场在第个施工点的公里内是否选址，则的取值为0或1。 2．确定目标函数的表达式 总吨公里数为： 3确定约束条件 施工地点的需求： ， 各料场的最大容量： ， （3）对运量的自然要求： ，， （4）每个施工点的公里内至少有一个料场： 即优化模型如下： 练习1 指派问题 题目：人员指派问题 关键词：最优化问题、0-1规划、Lingo 摘要 对于成本最低问题，我们考虑到最优化模型，在使用最优化模型的过程中，又出现在第i个人做或者不做第j项任务的问题，此时我们运用0-1规划问题，如果第i个人做第j项任务，；如果第i个人不做第j项任务，此时令。最后根据最优化模型的三步骤，逐步确定设计变量和目标变量、目标函数和约束条件。最终利用Lingo软件，求出最优结果有：最小的总成本应为32，并且得到其中，，，，，也就是说，由第1个人做第2个项目；第2个人做第3个项目；第3个人做第5个项目；第4个人做第4个项目；第5个人做第1个项目。 一、问题重述 设有n项任务要分给n个人完成，每人完成一项。由于每个人的专长不同，完成任务所需的成本也不同。若第 i 个人完成第 j 个问题的成本为，见下表。问题：如何分配这些工作任务，使总成本为最小。 表：每个人员的成本 工作 人员 1 2 3 4 5 1 12 7 9 7 9 2 8 9 6 6 6 3 7 17 12 14 9 4 15 14 6 6 10 5 4 10 7 10 9 二、问题分析 对于此问题，首先，它是一个线性最优化问题，要求在满足约束条件的情况下，使得成本达到最优。对于有n项任务要分给n个人完成，并且每人必须且只能完成一项，这里我们要应用0-1规划问题，对于任务j来说，第i个人要么做这项任务，此时令；要么不做这项任务，此时令。再考虑每个人的工作成本，使得最后的成本最低，达到最优。 三、符号说明 ：第 i 个人完成第 j 个项目的成本； ：第 i 个人做第 j 个项目； 四、模型假设 1.假设除人员成本外无其他因素影响总成本。 五、问题求解 5.1模型建立 5.1.1确定设计变量和目标变量 利用最优化问题，使得最后求解出的总成本最低，其中，要考虑题目中要求n 个人对应n个项目，所以，要排除一个人对应多个项目和一个项目对应多个人的情况。 5.1.2确定目标函数的表达式 总成本为： 5.1.3寻找约束条件 （1）对于每一个项目只由有一个人完成： （2）对于每一个人只能完成一个项目： （1）对于第i个人完成第j个项目有， 即第i个人要么做第j项任务，此时令；要么不做第j项任务，此时令。 我们对问题进行分析后，建立模型如下： 其中数值对应于下表 工作 人员 1 2 3 4 5 1 12 7 9 7 9 2 8 9 6 6 6 3 7 17 12 14 9 4 15 14 6 6 10 5 4 10 7 10 9 5.2模型求解 关于0-1整数规划问题，我们利用Lingo程序对模型进行求解，编程如下截图一： 图1 Lingo程序求解程序 运行编写的Lingo程序，得到如下结果： Global optimal solution found. Objective value: 32.00000 Objective bound: 32.00000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost C( 1, 1) 12.00000 0.000000 C( 1, 2) 7.000000 0.000000 C( 1, 3) 9.000000 0.000000