第三章 运筹学运输问题.ppt

5.4 指派问题assignment problem 5.4 指派问题assignment problem 5.4 指派问题assignment problem 5.4 指派问题assignment problem 第六步:回到第三步,反复进行,一直到找到了最优分配方案. 5.4 指派问题assignment problem 本题的最优解 最优分配方案为:让A1承建B3,A2承建B2,A3承建B1,A4承建B4,A5承建B5.这样安排能使总的建造费用最少,为7+9+6+6+6=34(万) 5.4 指派问题assignment problem 三、非标准形式的指派问题 5.4 指派问题assignment problem 求引例的最优分配方案 【解】 则 求此问题的最小值．求解过程如下 最优分配方案是：甲分配到B岗位；乙分配到A岗位；丙分配到D岗位；丁分配到C岗位；总成绩为357 工作 人员 A B C D 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 79 90 丁 86 90 80 88 5.4 指派问题assignment problem 5.4 指派问题assignment problem 5.4 指派问题assignment problem 5.4 指派问题assignment problem 5.4 指派问题assignment problem 练习1：某汽车公司拟将四种新产品配置到四个工厂生产，四个工厂的单位产品成本（元/件）如下表所示．求最优生产配置方案． 产品1 产品2 产品3 产品4 工厂1 58 69 180 260 工厂2 75 50 150 230 工厂3 65 70 170 250 工厂4 82 55 200 280 解：问题求最小值。 第一步：找出效率矩阵每行的最小元素，并分别从每行中减去最小元素，有 第二步：找出矩阵每列的最小元素，再分别从每列中减去，有 得到两个最优解 有两个最优方案 第一种方案：第一个工厂加工产品1，第二工厂加工产品3，第三个工厂加工产品4，第四个工厂加工产品2； 第二种方案：第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2； 单件产品总成本 Z＝58＋150＋250＋55＝513 练习2：某商业集团计划在市内四个点投资四个专业超市，考虑的商品有电器、服装、食品、家俱及计算机等5个类别．通过评估，家具超市不能放在第3个点，计算机超市不能放在第4个点，不同类别的商品投资到各点的年利润（万元）预测值见下表．该商业集团如何作出投资决策使年利润最大。 表5-31 地点 商品 1 2 3 4 电器 120 300 360 400 服装 80 350 420 260 食品 150 160 380 300 家具 90 200 － 180 计算机 220 260 270 － 解 这是求最大值、人数与任务数不相等、不可接受的配置的一个综合指派问题，分别对表5-36进行转换． （1）令c43=c54=0 （2）转换成求最小值问题，令M＝420，，得到效率表（机会损失表） （3）虚拟一个地点5 表5-32 地点 商品 1 2 3 4 5 电器 300 120 60 20 0 服装 340 70 0 160 0 食品 270 260 40 120 0 家俱 330 220 420 240 0 计算机 200 160 150 420 0 Z=1350 转换后得到下表．用匈牙利法求解得到最优解 最优投资方案：地点1投资建设计算机超市，地点2投资建设服装超市，地点3投资建设食品超市，地点4投资建设电器超市，年利润总额预测值为1350万元 方程ui+vj=Cij有m+n-1个方程， 有m+n未知变量ui及vj，有一个自由变量，一般地令u1=0就可得到ui及vi的一组解，再由式λi j =Cij－(ui+vi)得到非基变量的检验数，称ui、vi为运输问题关于基变量组的对偶解，或称势（ui为行位势vi为列位势）。不同的基变量组或自由变量的取值不同，得到不同 的位势，ui及vi有无穷多组解，但对同一组基变量来说，所求得的检验数是唯一的，并与闭回路法求得的检验数相同，这种求检验数的方法称为位势法。 用最小元素法求初始方案得 λ11=8,λ12=4,λ21=2,λ23=2全部非负,得到最优运输方案X,最大利润Z=8×9+10×10+6×8+5×4=240 第二种方法:所有非基变量的检验数λij≤0时最优.求初始运输方案可采用最大元素法.如上例,用最大元素得到 的初始运输方案: 8 14 9 求检验数:λ