人员指派问题

问题：要求每个施工点的R公里内至少有一个料场。1.确定设计变量和目标变量设第j个料场的位置坐标为),(jiyx，第j个料场向第i个施工点的材料运量为ijw。第j个料场到第i个施工点的吨公里数为：ijijdw，其中22)()(ijijijbyaxd。设ijy（mi,2,1，nj,2,1）表示第j个料场在第i个施工点的R公里内是否选址，则ijy的取值为0或1。2．确定目标函数的表达式总吨公里数为：minjijijdwz113确定约束条件（1）施工地点的需求：injijrw1，mi,2,1（2）各料场的最大容量：imiijqw1，nj,2,1（3）对运量的自然要求：0ijw，mi,2,1，nj,2,1（4）每个施工点的R公里内至少有一个料场：,min,min1RdRdmjjnj,2,1即优化模型如下：minjijijdwz11,min,,2,1,min,2,1,,2,1,0,2,1,,2,1,.111RdnjRdnjmiwnjqwmirwtsmjjijimiijinjij练习1指派问题题目：人员指派问题关键词：最优化问题、0-1规划、Lingo摘要对于成本最低问题，我们考虑到最优化模型，在使用最优化模型的过程中，又出现在第i个人做或者不做第j项任务的问题，此时我们运用0-1规划问题，如果第i个人做第j项任务，1ijx；如果第i个人不做第j项任务，此时令0ijx。最后根据最优化模型的三步骤，逐步确定设计变量和目标变量、目标函数和约束条件。最终利用Lingo软件，求出最优结果有：最小的总成本应为32，并且得到其中112x，123x，135x，144x，151x，也就是说，由第1个人做第2个项目；第2个人做第3个项目；第3个人做第5个项目；第4个人做第4个项目；第5个人做第1个项目。一、问题重述设有n项任务要分给n个人完成，每人完成一项。由于每个人的专长不同，完成任务所需的成本也不同。若第i个人完成第j个问题的成本为ijC，见下表。问题：如何分配这些工作任务，使总成本为最小。表：每个人员的成本工作人员12345112797928966637171214941514661054107109二、问题分析对于此问题，首先，它是一个线性最优化问题，要求在满足约束条件的情况下，使得成本达到最优。对于有n项任务要分给n个人完成，并且每人必须且只能完成一项，这里我们要应用0-1规划问题，对于任务j来说，第i个人要么做这项任务，此时令1ijx；要么不做这项任务，此时令0ijx。再考虑每个人的工作成本，使得最后的成本最低，达到最优。三、符号说明ijC：第i个人完成第j个项目的成本；ijx：第i个人做第j个项目；四、模型假设1.假设除人员成本外无其他因素影响总成本。五、问题求解5.1模型建立5.1.1确定设计变量和目标变量利用最优化问题，使得最后求解出的总成本最低，其中，要考虑题目中要求n个人对应n个项目，所以，要排除一个人对应多个项目和一个项目对应多个人的情况。5.1.2确定目标函数的表达式总成本为：niijijxC15.1.3寻找约束条件（1）对于每一个项目只由有一个人完成：njijnix1.,,2,11（2）对于每一个人只能完成一个项目：niijnjx1.,,2,11（1）对于第i个人完成第j个项目有，.,,2,1.,,2,110njnixij或即第i个人要么做第j项任务，此时令1ijx；要么不做第j项任务，此时令0ijx。我们对问题进行分析后，建立模型如下：niijijxC1min.,,2,1.,,2,110.,,2,11.,,2,11..11njnixnjxnixtsijniijnjij或其中ijC数值对应于下表工作人员123451127979289666371712149415146610541071095.2模型求解关于0-1整数规划问题，我们利用Lingo程序对模型进行求解，编程如下截图一：图1Lingo程序求解程序运行编写的Lingo程序，得到如下结果：Globaloptimalsolutionfound.Objectivevalue:32.00000Objectivebound:32.00000Infeasibilities:0.000000Extendedsolversteps:0Totalsolveriterations:0VariableValueReducedCostC(1,1)12.000000.000000C(1,2)7.0000000.000000C(1,3)9.0000000.000000C(1,4)7.0000000.000000C(1,5)9.0000000.000000C(2,1)8.0000000.000000C(2,2)9.0000000.000000C(2,3)6.0000000.000000C(2,4)6.0000000.000000C(2,5)6.0000000.000000C(3,1)7.0000000.000000C(3,2)17.000000.000000C(3,3)12.000000.000000C(3,4)14.000000.000000C(3,5)9.0000000.000000C(4,1)15.000000.000000C(4,2)14.000000.000000C(4,3)6.0000000.000000C(4,4)6.0000000.000000C(4,5)10.000000.000000C(5,1)4.0000000.000000C(5,2)10.000000.000000C(5,3)7.0000000.000000C(5,4)10.000000.000000C(5,5)9.0000000.000000X(1,1)0.00000012.00000X(1,2)1.0000007.000000X(1,3)0.0000009.000000X(1,4)0.0000007.000000X(1,5)0.0000009.000000X(2,1)0.0000008.000000X(2,2)0.0000009.000000X(2,3)1.0000006.000000X(2,4)0.0000006.000000X(2,5)0.0000006.000000X(3,1)0.0000007.000000X(3,2)0.00000017.00000X(3,3)0.00000012.00000X(3,4)0.00000014.00000X(3,5)1.0000009.000000X(4,1)0.00000015.00000X(4,2)0.00000014.00000X(4,3)0.0000006.000000X(4,4)1.0000006.000000X(4,5)0.00000010.00000X(5,1)1.0000004.000000X(5,2)0.00000010.00000X(5,3)0.0000007.000000X(5,4)0.00000010.00000X(5,5)0.0000009.000000RowSlackorSurplusDualPriceOBJ32.00000-1.00000020.0000000.00000030.0000000.00000040.0000000.00000050.0000000.00000060.0000000.00000070.0000000.00000080.0000000.00000090.0000000.000000100.0000000.000000110.0000000.000000120.0000000.000000131.0000000.000000140.0000000.000000150.0000000.000000160.0000000.000000170.0000000.000000180.0000000.000000191.0000000.000000200.0000000.000000210.0000000.000000220.0000000.000000230.0000000.000000240.0000000.000000250.0000000.000000261.0000000.000000270.0000000.000000280.0000000.000000290.0000000.000000301.0000000.000000310.0000000.000000321.0000000.000000330.0000000.000000340.0000000.000000350.0000000.000000360.0000000.000000我们从运行结果可以的到，根据约束条件和0-1规划条件，最后得到最小的总成本应为32，并且得到其中112x，123x，135x，144x，151x，也就是说，由第1个人做第2个项目；第2个人做第3个项目；第3个人做第5个项目；第4个人做第4个项目；第5个人做第1个项目。这样就得到了最优解，即最低总成本32。六、模型的评价与推广优点：1.此模型精确的求出了第几个人做第几个项目，并且求出了精确的总成本最低的最优解。2.本模型为类似的公司提供了降低成本的方法，即根据不同人对不同业务的工作成本，通过类似的方法对人员进行分工，从而使得成本最低。模型改进：1.本优化模型只考虑了如何使成本最低，但是在实际生活中，我们还应考虑如何使得效益最高，而不是一味的降低成本。2本题的模型是采用0-1混合型线性规划，在变量个数不是很大的情况下可以用Lingo求出准确的最优解，而且速度较快；但是当情况很复杂变量很多、有些因素是难以甚至无法量化时，采本题的模型就很难进行求解与分析了。练习2题目：平板车装车问题关键词：最优模型、Lingo摘要本文应用求解最优化模型中的线性规划方法，对两个平板车进行了装车问题的分析，其中要考虑各个约束条件对目标函数的约束，通过优化模型求解过程，分别确定了设计变量和目标变量、目标函数和约束条件。最终求出符合题意的最优化结果，得到第一辆平板车装的包装箱为1C规格的8箱，2C规格的1箱，4C规格的6箱，5C规格的3箱；第二辆平板车装的包装箱为2C规格的6箱，3C规格的9箱，6C规格的3箱。第一辆平板车浪费的空间为3037486725274881020...第二辆平板车浪费的空间为3035265293611020..，所以最优化模型结果总浪费的空间为0.6cm.一、问题重述要把7种规格的包装箱装到两辆铁路平板车上去，箱子的宽高相同，而厚度和重量不同，下表给出它们的厚度、重量与数量。每辆平板车有10.2米长的地方装箱（像面包片那样），载重40吨。由于货运限制，对765c,c,c三种包装箱的装载有如下特殊要求：它们所占的空间（厚度）不得超过302.7厘米。试把包装箱装到平板车上，使浪费的空间最小。C1C2C3C4C5C6C7厚度t（厘米）48.752.061.372.048.752.064.0重量w(千克)200030001000500400020001000数量n8796648二、问题分析问题是把包装箱装到平板车上，使浪费的空间最小，显然这是一个最优化问题。问题已知每辆平板车有10.2米长的地方装箱，要使浪费的空间最小，从而可将问题转化为装箱之后，使利用的空间最大。三、符号说明1、jC(j=1,2,3,4,5,6,7)分别表示7种不同规格的包装箱；2、ijx(i=1,2;j=1,2,3...7)表示第i辆平板车放第j种规格包装箱的数量；3、jw(j=1,2,3,4,5,6,7)表示第j种规格包装箱的重量；4、jt(j=1,2,3,4,5,6,7)表示第j种规格包装箱的厚度；5、jn(j=1,2,3