数学建模(四)整数规划 |
您所在的位置:网站首页 › 指派问题求最小值例题 › 数学建模(四)整数规划 |
目录 一、0-1型整数规划问题 1.1 案例 1.2 指派问题的标准形式 2.2 非标准形式的指派问题 二、指派问题的匈牙利解法 2.1 匈牙利解法的一般步骤 2.2 匈牙利解法的实例 2.3 代码实现 一、0-1型整数规划问题 1.1 案例投资问题: 有600万元投资5个项目,收益如表,求利润最大的方案? 设置决策变量: 模型: 指派问题: 甲乙丙丁四个人,ABCD四项工作,要求每人只能做一项工作,每项工作只由一人完成,问如何指派总时间最短? 设置决策变量: 模型: 约束条件: 标准的指派问题: 有n个人和n项工作,已知第i个人做第j项工作的代价为cj(i,j=1,…..,n),要求每项工作只能交与其中一人完成,每个人只能完成其中一项工作,问如何分配可使总代价最少? 指派问题标准求解形式: (1) 指派问题的系数矩阵 (2)决策变量的设置 (3)指派问题的解矩阵 指派问题的可行解中,每行每列有且仅有一个1。 (4)标准模型 (1)最大化指派问题 例如:求利润,只需找出最大元素,令最大元素减去所有元素,构建一个新的系数矩阵即可。
(2)人数和工作数不等 人少工作多:添加虚拟的 “人”,代价都为0。 人多工作少:添加虚拟的工作,代价都为0。 (3)一个人可做多件工作 该人可化为几个相同的 “人”。 (4)某工作一定不能由某人做 该人做该工作的相应代价取足够大M。例如,将某人做某工作代价设为负值。 二、指派问题的匈牙利解法匈牙利法是一种求解指派问题的简便解法,它利用了矩阵中0元素的定理。若从系数矩阵的一行(列)各元素中分别减去该行(列)的最小元素,得到新矩阵。以新矩阵为系数矩阵求得的最优解和用原矩阵求得的最优解相同。 2.1 匈牙利解法的一般步骤第一步:变换指派问题的系数(也称效率)矩阵( 第二步:进行试指派,以寻求最优解。 在( ![]() ![]() |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |