matlab求解指派问题最优解的函数

您所在的位置：网站首页 › matlab求解优化问题函数 › matlab求解指派问题最优解的函数

matlab求解指派问题最优解的函数

2023-09-12 08:42| 来源: 网络整理| 查看: 265

指派问题（基础）：

指派系数矩阵：

转化为线性规划问题：

找到目标函数：

增加约束条件：

matlab求解线性规划问题：

intlinprog：

指派问题的函数🌟 ：

使用实例：

指派问题延伸：

指派问题（基础）：

最基础的指派问题其简而言之就是

n个工人，n份工作，不同工人做不同工作各有不同的代价或效益，每个工人做一个工作，每个工作由一个人来做，求怎么分配工人代价最低或效益最高。

例如：

工人/工作ABC甲357乙134丙241

指派系数矩阵：

第 i 个人做第 j 个工作的代价为c_ij, 那么c_ij组成的矩阵就是指派系数矩阵

例如上述例子的指派矩阵就是. c =

$gif.latex?%5Cbegin%7Bbmatrix%7D%203%20%26%205%20%267%20%5C%5C%201%20%263%20%264%20%5C%5C%202%26%204%26%201%20%5Cend%7Bbmatrix%7D$

转化为线性规划问题：找到目标函数：

引入 0 - 1变量 $gif.latex?x_i_j$

1 表示第 i 个人去做第 j 个工作

那么目标函数（工作的成本或代价）即为

$gif.latex?z%3D%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%5Csum_%7Bj%3D1%7D%5E%7Bn%7Dc_i_jx_i_j$

增加约束条件：

由于每个人只做一个工作，每个工作只有一个人做，我们可以得到约束条件：

$gif.latex?%5Csum_%7Bi%3D1%7D%5E%7Bn%7Dx_i_j%3D1%28j%3D1%2C2%2C3%2C4...%29$

$gif.latex?%5Csum_%7Bj%3D1%7D%5E%7Bn%7Dx_i_j%3D1%28i%3D1%2C2%2C3%2C4...%29$

又因为 $gif.latex?x_i_j$ 是0-1变量，还有约束条件

$gif.latex?x_i_j%3D0%20%2C1$

在线性规划问题中，等价于

$gif.latex?%5Cbegin%7Bcases%7D%20%26%20%5Ctext%7B%20%7Dx_i_j%20%5Cgeq%200%20%5C%5C%20%26%20%5Ctext%7B%20%7Dx_i_j%20%5Cleq%201%5C%5C%20%26%20%5Ctext%7B%20%7D%20x_i_j%20%5Cend%7Bcases%7D$ 是整数

那么至此就构建好了线性规划模型。

matlab求解线性规划问题：

使用函数：intlinprog（）

intlinprog：

用于求解混合整数的线性规划问题，详细使用参见官方文档：

混合整数线性规划 (MILP) - MATLAB intlinprog- MathWorks 中国

指派问题的函数🌟 ：

先设置基本参数和输出量

function [x,fval] = AssignmentProblem(c，flag) %输入参数c为指派矩阵 %x输出指派问题的解 %fval输出最小成本/代价 %flag用于区分求最大效益还是最小成本,1表示求最小成本，-1表示求最大利益

目标函数对应向量：

c=c(:); %把矩阵转化为向量 c=flag*c; %求最大利益需要先取负

添加约束条件：

%构建等式条件 aeq=zeros(2*n,n^2); beq=ones(n*2,1); for i=1:n aeq(i,(i-1)*n+1:i*n)=1; aeq(i+n,i:n:n^2)=1; end

设置变量边界：

%变量边界 lb=zeros(n^2,1); ub=zeros(n^2,1);

求解：

[x,fval]=intlinprog(c,intcon,[],[],aeq,beq,lb,ub); fval=flag*fval; x=reshape(x,n,n); %把解得的x化为矩阵使用实例：

完整代码我上传资源

指派问题延伸：

即一个人可做多个工作，或一个工作可由多个人来做等

思路：

人多工作少：添加虚拟的人，代价为0人少工作多；添加虚拟工作，代价为0一人可做多个工作：将一个人分为等价的多个人某工作不能由某人做：将对应代价设置为无穷大……

【本文地址】

matlab求解指派问题最优解的函数

matlab求解指派问题最优解的函数

今日新闻

推荐新闻