运筹学指派问题

发布 2022-09-15 10:04:28 阅读 8435

可以自己添加。

在现实生活中,有各种性质的指派问题。例如,有若干项工作需要分配给若干人(或部门~设备)去完成;有若干项合同需要若干个投标者来承包;有若干班级需要安排在不同的教师上课等等。诸如此类问题,他们的基本要求实在满足特定的指派要求的同时,是指派方案的中体效果最佳。

由于指派问题的多样性我们划分成标准的指派问题和一般的指派问题两大类。一般的指派问题需经过处理使其标准化,在用匈牙利解法求出最优方案。

例如:西南交通大学希望学院土木工程系将在全校举行首届测量大赛,个班自己组队一组四人分别为甲~乙~丙~丁四人。在测量工作当中有调整仪器,观测读数,记录数据,数据处理四项任务。

但是个人处理问题的能力以时间作为划分标准(如下表所示).但是记录数据不需要多大能力,于是记录数据的人就是在其他三项选完后剩下的工作。(完成各项工作没有错误存在)

分析: 由于规定每项任务只能有一个人来完成,即一人一事。 此问题为非标准的指派问题我们需要对其进行标准化,再用匈牙利法对其求最优指派方案。

指派问题的系数矩阵如下:

将其化成标准的指派问题矩阵:

用匈牙利法求解最优方案,矩阵的每行每列均减去他的最小数,使其每行每列至少有个0存在。得到如下矩阵。

找出一行或则一列只有一个0的所有行或列,并划上 .如上图。在没有的行打√ ,在打√的行找划去的0列打√,在打√的列找划的行打√.

一直划到不能再继续为止。再将剩下的元素减去他们中间最小的元素(此例是40)为了保证个元素不为负数因此在划去0的列加上此数字得到如下矩阵:

10 140 0 此时每行每一列都只有一个0这次是为此问题的最优方案,将划的位置用1代替,其余位置用0表示,0,1分别表示承担和不承担。即:

1 0 0 0 为此问题的最优解,即甲观测读数,丙数据处理,丁调整仪器,剩下一项数据记录由乙来完成。

运筹学试卷 物流运筹学

2012 2013学年第一学期。运筹学 试卷。试卷 自拟送卷人 唐文广打印 校对 唐文广。一 6分 已知线性规划模型。写出该问题的对偶问题。二 15分 用单纯形法求解下面线性规划问题 作1张表即可 三 10分 求解下面标准指派问题,其中效率矩阵为。四 15分 某项工程由a b i j k等11项工序...

生产与储存问题运筹学作业

3.5生产与储存问题 某工厂是生产某种电子仪器的专业厂家,该厂是以销量来确定产量的,1 6月份各个月的生产能力 合同销量 单台仪器平均生产费用如表 又知上年末积压库存103台该仪器没有售出。如果生产出的仪器当月不交货,则需要运到分厂库房储存,每台仪器需增加运输成本0.1万元,每台仪器每月的平均仓储费...

运筹学设备更新问题作业

作业 课堂作业 书本p183第6题 结论最小费用为40,最优路径是a c f。课后作业 1 某工厂使用一台设备,每年年初工厂都要作出决定,如果继续使用旧的,要付维修费 若购买一台新设备,要付购买费。试制定一个五年的更新计划,使总支出最少。已知设备在各年的购买费,及不同机器役龄时的残值与维修费,如下表...