人员指派问题

1、v1.0 可编辑可修改问题：要求每个施工点的 R公里内至少有一个料场。1. 确定设计变量和目标变量 设第 j 个料场的位置坐标为 （xi ,yj ） ，第 j 个料场向第 i 个施工点的材料运量为 wij 。第 j 个 料 场 到 第 i 个 施 工 点 的 吨 公 里 数 为 ： wijdij ， 其 中dij(xj ai)2 (yj bi )2 。设yij（i 1,2, m， j 1,2, n）表示第 j 个料场在第 i个施工点的 R公里内是 否选址，则 yij的取值为 0或 1。2确定目标函数的表达式mn总吨公里数为： zwij diji1 j 13 确定约束条件（ 1） 施工地点的需求

2、：nwij ri ， i 1,2, m j1（ 2） 各料场的最大容量：mwijqi ， j 1,2, ni1（ 3）对运量的自然要求：wij 0， i 1,2, m ， j 1,2, n4）每个施工点的v1.0 可编辑可修改R 公里内至少有一个料场：min d1 j R,j 1,2, nmin d mj R,即优化模型如下：mnzwij diji 1 j1nwij ri ,i 1,2, m j1mwijqi1i , j1,2,ns.twij 0,i1,2,m, j1,2, nmin d1 jR,j1,2,nmin d mjR,v1.0 可编辑可修改练习 1 指派问题关键词：题目：人员指派问题

3、最优化问题、 0-1 规划、 Lingo摘要对于成本最低问题，我们考虑到最优化模型，在使用最优化模型的过程中， 又出现在第 i 个人做或者不做第 j 项任务的问题，此时我们运用 0-1 规划问题， 如果第 i 个人做第 j 项任务，xij 1；如果第 i 个人不做第 j 项任务，此时令 xij 0 。 最后根据最优化模型的三步骤， 逐步确定设计变量和目标变量、 目标函数和约束 条件。最终利用 Lingo 软件，求出最优结果有：最小的总成本应为 32，并且得 到其中 x12 1，x23 1，x35 1，x44 1，x51 1，也就是说，由第 1 个人做第 2个项v1.0 可编辑可修改目；第 2个

4、人做第 3个项目；第 3个人做第 5 个项目；第 4个人做第 4个项目；第 5个人做 第 1 个项目。一、问题重述设有 n 项任务要分给 n 个人完成，每人完成一项。由于每个人的专长不同， 完成任务所需的成本也不同。若第 i 个人完成第 j 个问题的成本为 Cij ，见下 表。问题：如何分配这些工作任务，使总成本为最小。表：每个人员的成本工作人员12345112797928966637171214941514661054107109、问题分析对于此问题， 首先，它是一个线性最优化问题， 要求在满足约束条件的情况 下，使得成本达到最优。 对于有 n 项任务要分给 n 个人完成，并且每人必须且只

5、能完成一项，这里我们要应用 0-1规划问题，对于任务 j 来说，第i 个人要么做 这项任务，此时令 xij 1；要么不做这项任务，此时令 xij 0 。再考虑每个人的 工作成本，使得最后的成本最低，达到最优。v1.0 可编辑可修改三、符号说明Cij ：第 i 个人完成第 j 个项目的成本；xij ：第 i 个人做第 j 个项目；四、模型假设1. 假设除人员成本外无其他因素影响总成本。五、问题求解模型建立确定设计变量和目标变量利用最优化问题， 使得最后求解出的总成本最低， 其中， 要考虑题目中要求 n 个人对应 n 个项目，所以，要排除一个人对应多个项目和一个项目对应多个人 的情况。确定目标函数

6、的表达式n总成本为：Cij xiji1寻找约束条件（1）对于每一个项目只由有一个人完成：（2）对于每一个人只能完成一个项目：（1）对于第 i 个人完成第 j 个项目有，nxij 1 i 1,2, ,n. j1nxij 1 j 1,2, ,n. i1xij 0或1 i 1,2, ,n.j 1,2, ,n.v1.0 可编辑可修改即第i 个人要么做第 j 项任务，此时令 xij 1；要么不做第 j 项任务，此时令 xij 0我们对问题进行分析后，建立模型如下：minnCij xiji1nxij1j1i 1,2,n.s.t.nxij 1j 1,2,n.i1xij0或1i 1,2,n.j 1,2, ,n

7、其中 Cij 数值对应于下表工作人员12345112797928966637171214941514661054107109模型求解关于 0-1 整数规划问题， 我们利用 Lingo 程序对模型进行求解， 编程如下截 图一：v1.0 可编辑可修改图 1 Lingo 程序求解程序运行编写的 Lingo 程序，得到如下结果：Global optimal solution found.Objective value:Objective bound:Infeasibilities:Extended solver steps: 0Total solver iterations: 0VariableVal

8、ue Reduced Costv1.0 可编辑可修改C( 1, 1)C( 1, 2)C( 1, 3)C( 1, 4)C( 1, 5)C( 2, 1)C( 2, 2)C( 2, 3)C( 2, 4)C( 2, 5)C( 3, 1)C( 3, 2)C( 3, 3)C( 3, 4)C( 3, 5)C( 4, 1)C( 4, 2)C( 4, 3)C( 4, 4)v1.0 可编辑可修改C( 4, 5)C( 5, 1)C( 5, 2)C( 5, 3)C( 5, 4)C( 5, 5)X( 1, 1)X( 1, 2)X( 1, 3)X( 1, 4)X( 1, 5)X( 2, 1)X( 2, 2)X( 2, 3

9、)X( 2, 4)X( 2, 5)X( 3, 1)X( 3, 2)X( 3, 3)v1.0 可编辑可修改X( 3, 4)X( 3, 5)X( 4, 1)X( 4, 2)X( 4, 3)X( 4, 4)X( 4, 5)X( 5, 1)X( 5, 2)X( 5, 3)X( 5, 4)Dual PriceX( 5, 5)Row Slack or SurplusOBJ234510v1.0 可编辑可修改1178910111213141516171819202122232425v1.0 可编辑可修改2627282930313233343536我们从运行结果可以的到， 根据约束条件和 0-1 规划条件， 最

10、后得到最小的 总成本应为 32，并且得到其中 x12 1， x23 1， x35 1， x44 1， x51 1 ，也就是 说，由第 1个人做第 2个项目； 第 2个人做第 3个项目； 第 3个人做第 5个项目；第 4个人 做第 4 个项目；第 5个人做第 1个项目。这样就得到了最优解，即最低总成本32。六、模型的评价与推广优点：1. 此模型精确的求出了第几个人做第几个项目， 并且求出了精确的总成本最 低的最优解。2. 本模型为类似的公司提供了降低成本的方法，即根据不同人对不同业务12v1.0 可编辑可修改的工作成本，通过类似的方法对人员进行分工，从而使得成本最低。模型改进：1. 本优化模型只

11、考虑了如何使成本最低， 但是在实际生活中， 我们还应考虑 如何使得效益最高，而不是一味的降低成本。2 本题的模型是采用 0-1 混合型线性规划，在变量个数不是很大的情况下可 以用 Lingo 求出准确的最优解， 而且速度较快； 但是当情况很复杂变量很多、 有 些因素是难以甚至无法量化时，采本题的模型就很难进行求解与分析了。练习 213v1.0 可编辑可修改题目：平板车装车问题关键词 ：最优模型、 Lingo摘要本文应用求解最优化模型中的线性规划方法， 对两个平板车进行了装车问题 的分析，其中要考虑各个约束条件对目标函数的约束，通过优化模型求解过程， 分别确定了设计变量和目标变量、 目标函数和约

12、束条件。 最终求出符合题意的最 优化结果，得到 第一辆平板车装的包装箱为 C1规格的 8箱， C2规格的 1箱， C4 规格的 6 箱， C5规格的 3箱；第二辆平板车装的包装箱为 C2规格的 6 箱，C3规 格的 9 箱， C6规格的 3箱。第一辆平板车浪费的空间为1020 8 48.7 52 72 6 48.7 3 0.3 第二辆平板车浪费的空间为1020 61.3 9 52 6 52 3 0.3 ，所以最优化模型结果总浪费的空间为 .一、问题重述要把 7种规格的包装箱装到两辆铁路平板车上去， 箱子的宽高相同， 而厚度 和重量不同，下表给出它们的厚度、重量与数量每辆平板车有米长的地方装箱

13、（像面包片那样），载重 40 吨。由于货运限制， 对 c5 , c6 , c7 三种包装箱的装载有如下特殊要求：它们所占的空间（厚度）不 得超过厘米。试把包装箱装到平板车上，使浪费的空间最小。C1C2C3C4C5C6C7厚度 t（厘米）14v1.0 可编辑可修改重量 w（ 千 克）200030001000500400020001000数量 n8796648、问题分析问题是把包装箱装到平板车上， 使浪费的空间最小， 显然这是一个最优 化问题。 问题已知每辆平板车有米长的地方装箱， 要使浪费的空间最小， 从而可 将问题转化为装箱之后，使利用的空间最大。三、符号说明1、Cj (j=1,2,3,4,5

14、,6,7)分别表示 7 种不同规格的包装箱；2、xij (i=1,2;j=1,2,3.7)表示第 i 辆平板车放第 j 种规格包装箱的数量；3、 wj (j=1,2,3,4,5,6,7)表示第 j 种规格包装箱的重量；4、t j (j=1,2,3,4,5,6,7)表示第 j 种规格包装箱的厚度；5、n j (j=1,2,3,4,5,6,7)表示第 j 种规格包装箱的总数量；四、问题假设1、假设平板车上各包装箱之间的空隙忽略不计；2、假设平板车上只放一列的包装箱；3、假设两辆平板车的差异忽略不计；五、模型建立首先，确定决策变量与目标变量15v1.0 可编辑可修改由问题分析可知： 可以将问题转化为

15、把包装箱装到平板车上， 使利用的空间 最大，则目标变量就是平板车上利用的空间长度，记为 z. 决策变量为两辆平板 车上分别放的 7 种不同规格的包装箱的数量，记为 xij .从而进一步确定目标函数的表达式为：z=*x11+ x12 )+52*( x21 + x22 )+*( x13 + x23 )+72*( x14 + x24 )+*( x15 x25 )+52*( x16 +x26)+ 64*( x17 +x27 )最后，寻找约束条件 , 即设计变量所受的限制由问题已知每辆平板车有米长的地方装箱（像面包片那样） ，载重 40吨，即48.7 x1152 x1261.3 x1372 x1448.

16、7 x1552 x1664 x17 102048.7 x2152 x2261.3 x2372 x2448.7 x2552 x2664 x27 102077且 x1j wj 40, x2j wj 40 ;又由于货运限制，对 c5 , c6 , c7三种包装箱的 j1 j 1装载有如下特殊要 求 ：它们 所 占的空 间 （厚度） 不得超 过厘米，从 而有x11x218x12x227x13x2397种不同规格的包装箱的数量是已知的（见表格） ，因此， x14x246x15x256x16x264x17x27848.7 x15 x2552 x16x2664 x17 x27302.7 ;且有 xij 0

17、i 1,2; j 1,2 ,3 7从而，模型的约束条件为16v1.0 可编辑可修改48.7x1152 x1261.3x1372x1448.7x2152 x2261.3x2372x2477x1j1j w j40,j1x2jwj40x11x218x12x227x13x239648.7 x15 52 x16 64 x17 102048.7 x25 52 x26 64 x27 10206xij 0 i 1,2; j 1,2 ,3 748.7 x15 x2552 x16x2664 x17 x27302.7综上所述，我们建立如下数学模型：Max z=* ( x11 + x12 )+52*( x21 +x2

18、2 )+*( x13 +x23 )+72*( x14 +x24 )+*( x15 x25 )+52*( x16 +x26 )+ 64*( x17 +x27)48.7x1152 x1261.3 x1372 x1448.7x1552 x1664 x17102048.7x2152 x2261.3 x2372 x2448.7x2552 x2664 x27102077x1j w j40,x2 j wj40j1j1x11x218x12x227x13x239x14x246x15x256x16x264x17x278xij0i1,2; j1,2 ,3748.7x2552 x2664 x27302.748.7x1552 x1664 x17302.717v1.0 可