Java指派问题_[原创]Matlab指派问题模型代码

指派问题的基本内容

一般来说指派问题解决的是如何将任务分配到人，使得任务完成的效益最大化(成本型效益则求最小值，利润型效益则求最大值)。上述问题一个 0 - 1 整数规划问题。

问题围绕着任务和人展开，即存在着 m 个任务，以及 n 个人。每个人处理每个任务都会有对应的效益，将所有人的情况写在一起，就组成了一个 m*n 的效益矩阵。

当 m = n 时，即此时，任务数和人数相等，那么每个人都会处理一项任务，存在如下约束：

对于任务来说，每个任务必须分配一个人；

对于人来说，每个人必须分配一个任务。

类似的，当 m

对于任务来说，每个任务必须分配一个人；

对于人来说，每个人可能会被分配到一个任务，也可能没有分配到任务。

当 m > n 时，任务数大于人数，则存在如下约束：

对于任务来说，每个任务必须分配一个人；

对于人来说，每个人可能会被分配到一个或者多个任务，但最多不超过任务总数。

模型调用形式

[x,min_fval,exitflag] = myTaskArrange2(f)

调用说明：

输入变量为一个 m*n 的效益矩阵，其中 m 行为 m 个任务， n 列为 n 个人。

输出变量 x 为与效益矩阵同型的 0-1 矩阵，1表示被安排，0表示不被安排；min_fval 为最优目标值；exitflag 为退出标识符，一般等于 1 表示解收敛。

模型代码

function [x,min_fval,exitflag] = myTaskArrange2(f)

%% 程序功能说明

%求解不平衡任务指派问题

%====输入参数====

%f m行n列的效益矩阵，m个任务，n个人，

%====输出参数====

%x 目标函数取最小值时的自变量值

%min_fval 目标函数的最小值

% exitflag 退出标识符

%程序编写时间：2019年09月

%% 程序主体

[m,n] = size(f); % 获取效益矩阵中任务的个数和人的个数

% 按行拉成一列向量

f = f&＃39;;

F = f(:);

% 构造等式约束(每一行加起来等于1，即每个任务必须分配一人)

Aeq = cell(m,m);

Aeq(:) = {zeros(1,n)};

Aeq(eye(m,m)==1) = {ones(1,n)};

Aeq = cell2mat(Aeq);

Beq = ones(m,1);

% 取整变量地址

intcon = 1:m*n;

% 变量取值范围(大于0小于1)

LB = zeros(m*n,1);

UB = ones(m*n,1);

if m == n % 如果任务数等于人数

% 构造等式约束(每个人一定会被安排)

Aeq2 = repmat(eye(n,n),1,m);

Beq2 = ones(n,1);

Aeq = [Aeq;Aeq2];

Beq = [Beq;Beq2];

% 整数规划求解

[x,min_fval, exitflag] = intlinprog(F,intcon,[],[],Aeq,Beq,LB,UB);

elseif m

% 构造不等式约束(每一列加起来大于0小于1，即每个人可能被安排也可能不被安排一个任务)

A = repmat(eye(n,n),1,m);

B = ones(n,1);

% 利用整数规划函数求解

[x,min_fval, exitflag] = intlinprog(F,intcon,A,B,Aeq,Beq,LB,UB);

elseif m > n % 如果任务数大于人数

% 构造不等式约束(每一列加起来大于1小于m，即每个人可能被安排一个或者多个任务，最多不超过任务数m)

A = repmat(eye(n,n),1,m);

B = ones(n,1)*m;

% 利用整数规划函数求解

[x,min_fval, exitflag] = intlinprog(F,intcon,A,B,Aeq,Beq,LB,UB);

end

%% 将结果还原成效益矩阵对应形式

x = reshape(x,n,m)&＃39;;

测试算例

为了验证本模型的效果，提供如下测试算例，进行验证：

% 4项任务，4个人完成 最优解：8

f1 = [6,1,3,8;

6,3,5,2;

1,1,1,4;

7,2,5,2];

% 4项任务，5个人完成 最优解：127.8

f2 = [37.7,32.9,38.8,37,35.4;

43.4,33.1,42.2,34.7,41.8;

33.3,28.5,38.9,30.4,33.6;

29.2,26.4,29.6,28.5,31.1];

% 5项任务，3个人完成 最优解：116

f3 = [25,39,34;

29,38,27;

31,26,28;

4,20,40;

37,18,32];

[x,min_fval,exitflag] = myTaskArrange2(f1) % 修改输入测试效果

Matlab 整数线性规划问题模型代码

整数线性规划问题的基本内容 整数线性规划解决的是自变量在一定的线性约束条件下,使得线性目标函数求得最大值或者最小值的问题.其中自变量只能取整数.特别地,当自变量只能取0或者1时,称之为 0-1 整数规 ...

Matlab 非线性规划问题模型代码

非线性规划问题的基本内容 非线性规划解决的是自变量在一定的非线性约束或线性约束组合条件下,使得非线性目标函数求得最大值或者最小值的问题. 当目标函数为最小值时,上述问题可以写成如下形式: \[ \mi ...

Matlab 线性规划问题模型代码

线性规划问题的基本内容 线性规划解决的是自变量在一定的线性约束条件下,使得线性目标函数求得最大值或者最小值的问题. \[ \min z=\sum_{j=1}^{n} f_{j} x_{j} \] \[ ...

Matlab 图论最短路问题模型代码

最短路问题的基本内容 最短路问题研究的是,在一个点与点之间连接形成的网络图中,对应路径赋予一定的权重(可以理解为两点之间的距离),计算任意两点之间如何和走,路径最短的问题.在这里的距离可以理解成各种两 ...

球体的双目视觉定位(matlab，附代码)

球体的双目视觉定位(matlab,附代码) 标签(空格分隔): 机器视觉 引言 双目视觉定位是我们的一个课程设计,最近刚做完,拿出来与大家分享一下,实验的目的是在拍摄的照片中识别球体,并求出该球体到相 ...

[原创]IBM BLM模型思维导图

[原创]IBM BLM模型思维导图 IBM业务领先模型 http://wenku.baidu.com/view/1d1d247af242336c1eb95e3b.html?from=search

k-means算法MATLAB和opencv代码

上一篇博客写了k-means聚类算法和改进的k-means算法.这篇博客就贴出相应的MATLAB和C++代码. 下面是MATLAB代码,实现用k-means进行切割: %%%%%%%%%%%%%%%% ...

多路复用I/O模型poll() 模型 代码实现

多路复用I/O模型poll() 模型 代码实现 poll()机制和select()机制是相似的,都是对多个描述符进行轮询的方式. 不同的是poll()没有描述符数目的限制. 是通过struct pol ...

Windows Socket五种I/O模型——代码全攻略(转)

Winsock 的I/O操作: 1. 两种I/O模式 阻塞模式:执行I/O操作完成前会一直进行等待,不会将控制权交给程序.套接字 默认为阻塞模式.可以通过多线程技术进行处理. 非阻塞模式:执行I/O操 ...

随机推荐

Android Studio添加aar

1.把aar复制到项目中的 libs 里面 2.在module 里面的build.gradle 的根目录添加 repositories{ flatDir { dirs &＃39;libs&＃39; } } 3.在mo ...

Word2013创建目录

1.写好文档内容后,将光标移到标题行,点击“开始”里的“样式”->“创建样式”,为该标题创建一个新的样式,同时点击“修改”,在打开的窗口中选择左下方的“格式”,进行标题格式的调整.依次可设定子标 ...

mongodb命令使用大全(常用命令)

数据库常用命令 1.Help查看命令提示 help db.help(); db.yourColl.help(); db.youColl.find().help(); rs.help(); 2.切换/创 ...

[BZOJ3875][AHOI2014]骑士游戏(松弛操作)

题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=3875 分析: 类似于spfa求最短路,设d[i]表示完全消灭i号怪物的最小花费,我们对 ...

Python 之 lambda 函数

Python 支持一种单行匿名函数,这种函数称为 lambda,它最初借鉴自 Lisp. >>> add = lambda x, y: x +y >>> add(3 ...

jsapi支付，提示redirect_uri 参数错误

检查授权目录(微信支付——配置中心) appid MCHID KEYS 配置参数是否正确 appsecrect 配置是否正确(开发者中心) 如果是使用测试链接,需要同时指定测试授权目录,测试账号,并且 ...

MyeclipseJRE版本设置

1.首先添加JDK版本 Window——Preferences——Java——Install JREs——Add——Stand VM——浏览JDK安装版本完成即可(一定是JDK中JRE的安装目录如:D ...

PYTHON-函数的定义与调用，返回值，和参数-练习

# day10函数的定义调用和参数作业# 1.写函数,用户传入修改的文件名.与要修改的内容,执行函数,完成批量修改操作# def modify_file(filename,old,new):# imp ...

Origin绘制双Y轴图的方法

1.已有数据绘图如下,其中网络流量的单位是M Bytes/s,与另外两组数据的单位(时间)不同,现在要为其添加右侧Y轴. 2.首先选中该图像,找到工具条,点击第三个按钮“Add Right-Y Lay ...