operational|Assignment Problem（任务分配问题）详解运筹学|research

Assignment Problem（任务分配问题）

定义：任务分配问题，一般的定义都是以n个机器， n 个任务，每个机器mim i上安排仅且一个任务tjt j ，每个任务只能被安排一次，且每个任务在每个机器上都有一个价值aija i j , 问怎样安排使得总的价值最大？
定义2：我更偏爱于师父-徒弟来阐释，即：有n 个师父， n 个徒弟，每个徒弟只能选者一个师父学习, 每个师父只能带一个徒弟; 每个师父有自己的技能, 每个徒弟有自己学习的天分, 当徒弟 j 在师父 i 门下学习, 产生效益为aija i j , 问如何安排使得总效益最大？

数据格式定义：

mim i : 第 i 个师父, i= 1,2,3,?,n1 , 2 , 3 , ? , n
tjt j : 第 j 个徒弟, j= 1,2,3,?,n1 , 2 , 3 , ? , n
xijx i j : 第j 个徒弟是否在第i 个师父门下学习: 1, 是; 2 不是.
aija i j : 第j 个徒弟在第i 个师父门下学习产生的效益.

数学模型

【operational|Assignment Problem（任务分配问题）详解】f.o.max∑ni=1∑nj=1aij?xij∑ i = 1 n ∑ j = 1 n a i j ? x i j(0)
s.t.∑ni=1xij=1?j=1,2,3,?,n∑ i = 1 n x i j = 1 ? j = 1 , 2 , 3 , ? , n(1)
∑nj=1xij=1?i=1,2,3,?,n∑ j = 1 n x i j = 1 ? i = 1 , 2 , 3 , ? , n(2)
xij∈{0,1}?i=1,2,3,?,n; x i j ∈ { 0 , 1 } ? i = 1 , 2 , 3 , ? , n ;
j=1,2,3,?,nj = 1 , 2 , 3 , ? , n(3)
式0 为目标函数, 即最大化总效益；
式1 表示一个师父只能带一个徒弟；
式2 表示一个徒弟只能跟一个师父学习；
式3 表示师父-徒弟分配是原子操作，要么分配要么不分配。

编程：代入solver中解决即可