企业网站建设与维护,十大进销存软件排名,怎么用2级目录做网站,企业网站设计经典案例目录
一、0-1型整数规划问题
1.1 案例
1.2 指派问题的标准形式
2.2 非标准形式的指派问题
二、指派问题的匈牙利解法
2.1 匈牙利解法的一般步骤
2.2 匈牙利解法的实例
2.3 代码实现 一、0-1型整数规划问题
1.1 案例
投资问题#xff1a; 有600万元投资5个项目…目录
一、0-1型整数规划问题
1.1 案例
1.2 指派问题的标准形式
2.2 非标准形式的指派问题
二、指派问题的匈牙利解法
2.1 匈牙利解法的一般步骤
2.2 匈牙利解法的实例
2.3 代码实现 一、0-1型整数规划问题
1.1 案例
投资问题 有600万元投资5个项目收益如表求利润最大的方案? 设置决策变量 模型 指派问题 甲乙丙丁四个人ABCD四项工作要求每人只能做一项工作每项工作只由一人完成问如何指派总时间最短? 设置决策变量 模型 约束条件 1.2 指派问题的标准形式
标准的指派问题 有n个人和n项工作已知第i个人做第j项工作的代价为cj(i,j1,…..,n),要求每项工作只能交与其中一人完成每个人只能完成其中一项工作问如何分配可使总代价最少? 指派问题标准求解形式
1 指派问题的系数矩阵 2决策变量的设置 3指派问题的解矩阵 指派问题的可行解中每行每列有且仅有一个1。 4标准模型 2.2 非标准形式的指派问题
1最大化指派问题
例如求利润只需找出最大元素令最大元素减去所有元素构建一个新的系数矩阵即可。 中最大元素为m令 。
2人数和工作数不等
人少工作多添加虚拟的 “人”代价都为0。
人多工作少添加虚拟的工作代价都为0。
3一个人可做多件工作 该人可化为几个相同的 “人”。
4某工作一定不能由某人做 该人做该工作的相应代价取足够大M。例如将某人做某工作代价设为负值。 二、指派问题的匈牙利解法 匈牙利法是一种求解指派问题的简便解法它利用了矩阵中0元素的定理。若从系数矩阵的一行(列)各元素中分别减去该行(列)的最小元素得到新矩阵。以新矩阵为系数矩阵求得的最优解和用原矩阵求得的最优解相同。 2.1 匈牙利解法的一般步骤
第一步变换指派问题的系数(也称效率)矩阵()为()使在()的各行各列中都出现0元素即
(1) 从矩阵()的每行元素都减去该行的最小元素。(2) 再从所得新系数矩阵的每列元素中减去该列的最小元素。 第二步进行试指派以寻求最优解。
在()中找尽可能多的独立0元素即行和列中只有这一个0元素若能找出n个独立0元素就以这n个独立0元素对应解矩阵()中的元素为1其余为0这就得到最优解。找独立0元素常用的步骤为
(1) 从只有一个0元素的行开始给这个0元素加圈记作然后划去所在列的其它0元素记作。这表示这列所代表的任务已指派完不必再考虑别人了。(2) 给只有一个0元素的列中的0元素加圈记作然后划去所在行的0元素记作。(3) 反复进行(1)(2)两步直到尽可能多的0元素都被圈出和划掉为止。(4) 若仍有没有划圈的0元素且同行(列)的0元素至少有两个则从剩有0元素最少的行(列)开始比较这行各0元素所在列中0元素的数目选择0元素少的那列的这个0元素加圈。然后划掉同行同列的其它0元素。可反复进行直到所有0元素都已圈出和划掉为止。(5) 若元素的数目m等于矩阵的阶数n那么这指派问题的最优解已得到。若mn,则转入下一步。 第三步作最少的直线覆盖所有0元素。
(1) 对没有的行打√号;(2) 对已打√号的行中所有含元素的列打√号。(3) 再对打有√号的列中含元素的行打√号。(4) 重复(2)(3)直到得不出新的打√号的行、列为止。(5) 对没有打√号的行画横线有打√号的列画纵线这就得到覆盖所有0元素的最少直线数 。 应等于m转第四步。若不相等说明试指派过程有误回到第二步(4)。 第四步变换矩阵()以增加0元素。
在没有被直线覆盖的所有元素中找出最小元素然后打√各行都减去这最小元素。打√各列都加上这最小元素以保证系数矩阵中不出现负元素。新系数矩阵的最优解和原问题仍相同。转回第二步直到找出最优解。 2.2 匈牙利解法的实例 甲乙丙丁四人要完成四项工作A、B、C、D每人只能完成一项工作要求完成总时间最短。 匈牙利解法 第一步减去最小值。 第二步加圈和划掉比较圈数是否等于矩阵的阶数。 等于则输出最优值 否则转到第三步重整矩阵。 2.3 代码实现
c[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5; 8 4 2 3 5;9 10 6 9 10];%系数矩阵cc(:); %把矩阵c转化为向量 azeros(10,25);for i1:5 % 实现循环运算
a(i,(i-1)*51:5*i)1;
a(5i,i:5:25)1;
end % 此循环把指派问题转换为线性规划问题bones(10,1); [x,y]linprog(c,[],[],a,b,zeros(25,1),ones(25,1));Xreshape(x,5,5)opty输出
