如题所述
第一部把非标准形式转化为标准形式！添加虚拟的工作5和6，其中被做的费用为零。
第二部再用其中的最大元素13减去每一个元素得到一个新的矩阵！
第三部再用匈牙利解法！每行减去最小元素，每一列减去个最小元素，再划出独立零元素，对没有圈零的行打勾，在打勾的行中对杠零的列打勾，在打勾的列中对圈零的行在打勾，如此反复。在对没被打勾的行划一横线，对打勾的列划一垂线。再找出未被直线覆盖的最小元素，先行减去这一最小元素，势必会出现负数，在对有负数的列加上这一附属的相反数即可。再重新圈独立零元素，如果零元素数量少于6个再重复这一过程一直到有6个独立零元素即可。
如果不会你先照抄吧。。。这答案应该不会错和你给的答案是一致的，第一人和第二人都没有工作。。。。。。。。记得给分啊。。。打出来不容易！！！！！！！
温馨提示：答案为网友推荐，仅供参考
第1个回答 2018-12-19
In[1]:= u = 4; z = 6; a = Array[# &, {u}]; b = Array[# &, {z}];
aa = {{3, 5, 4, 5}, { 6, 7, 6, 8}, {8, 9, 8, 10}, { 10, 10, 9,
11}, {12, 11, 10, 12}, {13, 12, 11, 13}};
zz = Map[Table[
ToExpression[StringJoin["z", ToString[#], ToString[i]]], {i, 1,
Length[a]}] &, Array[# &, {z}]];
zh = Map[Table[
ToExpression[StringJoin["z", ToString[i], ToString[#]]], {i, 1,
z}] &, Array[# &, {Length[a]}]];
bb = Map[aa[[#]].zz[[#]] &, b];
t = Maximize[
Flatten[{Total[bb],
Map[Total[zh[[#]]] == 1 &, Array[# &, {Length[a]}]],
Map[Total[zz[[#]]] <= 1 &, Array[# &, {z}]],
Map[{# >= 0, # <= 1} &, Flatten[zz]]}], Flatten[zz], Integers]
Out[6]= {43, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 0,
z34 -> 1, z41 -> 0, z42 -> 1, z43 -> 0, z44 -> 0, z51 -> 1,
z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 0, z63 -> 1,
z64 -> 0}}
算出来的结果和你的有点不一样，第1、2个人没有工作，第3个人做第4项工作，第4个人做第2项工作，第3个人做第1项工作，第6个人做第3项工作，总收益为43.工作分配有点不一样，但总收益是一样的。结果是有12组不同的解：
{{z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0, z22 -> 0,
z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 0, z34 -> 1,
z41 -> 0, z42 -> 0, z43 -> 1, z44 -> 0, z51 -> 0, z52 -> 1,
z53 -> 0, z54 -> 0, z61 -> 1, z62 -> 0, z63 -> 0,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 0,
z34 -> 1, z41 -> 0, z42 -> 0, z43 -> 1, z44 -> 0, z51 -> 1,
z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 1, z63 -> 0,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 0,
z34 -> 1, z41 -> 0, z42 -> 1, z43 -> 0, z44 -> 0, z51 -> 0,
z52 -> 0, z53 -> 1, z54 -> 0, z61 -> 1, z62 -> 0, z63 -> 0,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 0,
z34 -> 1, z41 -> 0, z42 -> 1, z43 -> 0, z44 -> 0, z51 -> 1,
z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 0, z63 -> 1,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 1,
z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 0, z44 -> 1, z51 -> 0,
z52 -> 1, z53 -> 0, z54 -> 0, z61 -> 1, z62 -> 0, z63 -> 0,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 1,
z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 0, z44 -> 1, z51 -> 1,
z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 1, z63 -> 0,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 1,
z34 -> 0, z41 -> 0, z42 -> 1, z43 -> 0, z44 -> 0, z51 -> 0,
z52 -> 0, z53 -> 0, z54 -> 1, z61 -> 1, z62 -> 0, z63 -> 0,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 1,
z34 -> 0, z41 -> 0, z42 -> 1, z43 -> 0, z44 -> 0, z51 -> 1,
z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 0, z63 -> 0,
z64 -> 1}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 1, z33 -> 0,
z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 0, z44 -> 1, z51 -> 0,
z52 -> 0, z53 -> 1, z54 -> 0, z61 -> 1, z62 -> 0, z63 -> 0,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 1, z33 -> 0,
z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 0, z44 -> 1, z51 -> 1,
z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 0, z63 -> 1,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 1, z33 -> 0,
z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 1, z44 -> 0, z51 -> 0,
z52 -> 0, z53 -> 0, z54 -> 1, z61 -> 1, z62 -> 0, z63 -> 0,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 1, z33 -> 0,
z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 1, z44 -> 0, z51 -> 1,
z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 0, z63 -> 0,
z64 -> 1}}
aa = {{3, 5, 4, 5}, { 6, 7, 6, 8}, {8, 9, 8, 10}, { 10, 10, 9,
11}, {12, 11, 10, 12}, {13, 12, 11, 13}};
zz = Map[Table[
ToExpression[StringJoin["z", ToString[#], ToString[i]]], {i, 1,
Length[a]}] &, Array[# &, {z}]];
zh = Map[Table[
ToExpression[StringJoin["z", ToString[i], ToString[#]]], {i, 1,
z}] &, Array[# &, {Length[a]}]];
bb = Map[aa[[#]].zz[[#]] &, b];
t = Maximize[
Flatten[{Total[bb],
Map[Total[zh[[#]]] == 1 &, Array[# &, {Length[a]}]],
Map[Total[zz[[#]]] <= 1 &, Array[# &, {z}]],
Map[{# >= 0, # <= 1} &, Flatten[zz]]}], Flatten[zz], Integers]
Out[6]= {43, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 0,
z34 -> 1, z41 -> 0, z42 -> 1, z43 -> 0, z44 -> 0, z51 -> 1,
z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 0, z63 -> 1,
z64 -> 0}}
算出来的结果和你的有点不一样，第1、2个人没有工作，第3个人做第4项工作，第4个人做第2项工作，第3个人做第1项工作，第6个人做第3项工作，总收益为43.工作分配有点不一样，但总收益是一样的。结果是有12组不同的解：
{{z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0, z22 -> 0,
z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 0, z34 -> 1,
z41 -> 0, z42 -> 0, z43 -> 1, z44 -> 0, z51 -> 0, z52 -> 1,
z53 -> 0, z54 -> 0, z61 -> 1, z62 -> 0, z63 -> 0,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 0,
z34 -> 1, z41 -> 0, z42 -> 0, z43 -> 1, z44 -> 0, z51 -> 1,
z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 1, z63 -> 0,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 0,
z34 -> 1, z41 -> 0, z42 -> 1, z43 -> 0, z44 -> 0, z51 -> 0,
z52 -> 0, z53 -> 1, z54 -> 0, z61 -> 1, z62 -> 0, z63 -> 0,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 0,
z34 -> 1, z41 -> 0, z42 -> 1, z43 -> 0, z44 -> 0, z51 -> 1,
z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 0, z63 -> 1,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 1,
z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 0, z44 -> 1, z51 -> 0,
z52 -> 1, z53 -> 0, z54 -> 0, z61 -> 1, z62 -> 0, z63 -> 0,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 1,
z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 0, z44 -> 1, z51 -> 1,
z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 1, z63 -> 0,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 1,
z34 -> 0, z41 -> 0, z42 -> 1, z43 -> 0, z44 -> 0, z51 -> 0,
z52 -> 0, z53 -> 0, z54 -> 1, z61 -> 1, z62 -> 0, z63 -> 0,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 0, z33 -> 1,
z34 -> 0, z41 -> 0, z42 -> 1, z43 -> 0, z44 -> 0, z51 -> 1,
z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 0, z63 -> 0,
z64 -> 1}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 1, z33 -> 0,
z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 0, z44 -> 1, z51 -> 0,
z52 -> 0, z53 -> 1, z54 -> 0, z61 -> 1, z62 -> 0, z63 -> 0,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 1, z33 -> 0,
z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 0, z44 -> 1, z51 -> 1,
z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 0, z63 -> 1,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 1, z33 -> 0,
z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 1, z44 -> 0, z51 -> 0,
z52 -> 0, z53 -> 0, z54 -> 1, z61 -> 1, z62 -> 0, z63 -> 0,
z64 -> 0}, {z11 -> 0, z12 -> 0, z13 -> 0, z14 -> 0, z21 -> 0,
z22 -> 0, z23 -> 0, z24 -> 0, z31 -> 0, z32 -> 1, z33 -> 0,
z34 -> 0, z41 -> 0, z42 -> 0, z43 -> 1, z44 -> 0, z51 -> 1,
z52 -> 0, z53 -> 0, z54 -> 0, z61 -> 0, z62 -> 0, z63 -> 0,
z64 -> 1}}
