- 1、本文档共112页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第三章 运筹学运输问题
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 求检验数:λ
您可能关注的文档
最近下载
- 智慧牧场繁育系统设计方案.docx
- 教师近3年任教学科学生学业水平和综合素质.docx VIP
- 特种设备安全风险辨识标准查找方法清单汇编.docx VIP
- 4.11.1《探问人生目标》课件人教统编版道德与法治七年级上册2024新教材.pptx
- 小学四年级上册数学练习题大全.pdf VIP
- 小学四年级上册数学练习题大全.docx VIP
- 面粉厂企业安全生产风险分级管控和隐患排查治理双体系方案资料(2022-2023版).pdf VIP
- 高中数学5.1.2导数的概念及其几何意义课件.ppt
- 2020-2024年高考语文试题分类汇编(全国)文学类文本阅读(小说)(学生卷).pdf VIP
- 特种设备安全风险辨识清单——电梯.pdf VIP
文档评论(0)