学做网站论坛课程,湘潭做网站价格找磐石网络一流,wordpress seo教程网,做房产中介需要有内部网站吗问题描述
有 N N N个任务#xff0c;需要 N N N个人去完成#xff0c;每个人完成不同工作的效率不同#xff08;或者资源、收益等等#xff09;#xff0c;需要怎么分配使得整体的效率最高#xff08;成本最低等等#xff09;呢#xff1f;这就是经典的指派问题啦需要 N N N个人去完成每个人完成不同工作的效率不同或者资源、收益等等需要怎么分配使得整体的效率最高成本最低等等呢这就是经典的指派问题啦
数学建模
我们首先做以下定义 I I I: 人的集合 J J J: 任务的集合 c i j c_{ij} cij: 把任务 j j j分配给 i i i的成本 x i j x_{ij} xij: 是否把任务 j j j分配给 i i i0-1变量 m i n ∑ i ∈ I ∑ j ∈ J x i j c i j s . t ∑ i ∈ I x i j 1 , ∀ j ∈ J ∑ j ∈ J x i j 1 , ∀ i ∈ I min \sum_{i \in I} \sum_{j \in J}x_{ij}c_{ij} \\ s.t \sum_{i \in I}x_{ij}1, \forall j\in J\\ \sum_{j \in J}x_{ij}1, \forall i\in I\\ mini∈I∑j∈J∑xijcijs.ti∈I∑xij1,∀j∈Jj∈J∑xij1,∀i∈I
目标函数表示最小化成本第一行约束表示每个任务只能分配给一个人第二行约束表示每个人只能被分配一个任务。
整数最优解特性 即使把变量 x e x_{e} xe松弛成 0 ≤ x e ≤ 1 0 \leq x_e \leq1 0≤xe≤1原问题变成线性规划该问题仍然存在整数最优解。 模型求解
方式一将模型直接扔给求解器Gurobi、Cplex等求解就可以啦如果对求解运筹模型时如何选择求解器有疑问的小伙伴可以参考我的文章如何选择合适的求解器 后面再补充python实现的代码(todo)
方式二对算法求解速度有更高要求的可以通过匈牙利算法、Ford-Fulkerson算法FFA等求解。
