指派和网络最优化问题学生学习教案

1、会计学1指派和网络指派和网络(wnglu)最优化问题学生最优化问题学生第一页，共29页。例例1：A公司分别从公司分别从3个客户（个客户（c1，c2，c3）那里得到了市场调研的项目）那里得到了市场调研的项目，目前有，目前有3个项目经理（个项目经理（m1，m2，m3）可以）可以(ky)承担这些项目，完成承担这些项目，完成每个项目所需的时间与这每个项目所需的时间与这3位项目经理的经验和能力有关，管理层估算了位项目经理的经验和能力有关，管理层估算了每位经理完成各项目的可能时间（单位：天），见下表。如果每个客户每位经理完成各项目的可能时间（单位：天），见下表。如果每个客户项目分配一名项目经理，每名项目经

2、理可以项目分配一名项目经理，每名项目经理可以(ky)得到一个客户项目，管得到一个客户项目，管理层需要知道如何分配项目给各经理，可以理层需要知道如何分配项目给各经理，可以(ky)使项目尽快完成（所用使项目尽快完成（所用时间最短）？时间最短）？预计项目完成时间项目经理项目经理客户客户c1c2c3m110159m29185m36143第2页/共29页第二页，共29页。预计项目完成时间项目经理项目经理客户客户c1c2c3m1x11x12x13m2x21x22x23m3x31x32x33第3页/共29页第三页，共29页。、 、第4页/共29页第四页，共29页。第5页/共29页第五页，共29页。例例2：某

3、公司购买了：某公司购买了3种不同的设备，但是种不同的设备，但是(dnsh)车间里却有车间里却有5个不同的地点可以安装。每一个可以安装的新设备的地点处个不同的地点可以安装。每一个可以安装的新设备的地点处理物料的小时成本列于下表中，公司寻求总物料处理成本最理物料的小时成本列于下表中，公司寻求总物料处理成本最小的安装方案。其中设备小的安装方案。其中设备2不能安装在地点不能安装在地点2。Cost($/hour)Location 1Location 2Location 3Location 4Location 5Machine 11316121415Machine 215-132016Machine 34

4、71067第6页/共29页第六页，共29页。Cost($/hour)Location 1Location 2Location 3Location 4Location 5Machine 1x11x12x13x14x15Machine 2x21x22x23x24x25Machine 3x31x32x33x34x35第7页/共29页第七页，共29页。第8页/共29页第八页，共29页。第9页/共29页第九页，共29页。第10页/共29页第十页，共29页。点连 线 （ 边 或 弧 ）基 本 概 念权 （ 赋 权 图 ）网 络 图最 小 费 用 流 问 题最 大 流 问 题网 络 最 优 化 问 题主 要

5、 类 型最 短 路 问 题最 小 支 撑 树 问 题货 郎 担 问 题 和 中 国 邮 路 问 题节 点 （ 供 应 点 、 转 运 点 、 需 求 点 ）净 流 量建 模 和 求 解数 学 模 型电 子 表 格 模 型第11页/共29页第十一页，共29页。第12页/共29页第十二页，共29页。v1v3v5v2v4v68736548521对于该网络图，可以提出许多极值(j zh)问题 第13页/共29页第十三页，共29页。v1v3v5v2v4v68736548521第14页/共29页第十四页，共29页。v1v3v5v2v4v68736548521第15页/共29页第十五页，共29页。v1v3v

6、5v2v4v68736548521第16页/共29页第十六页，共29页。第17页/共29页第十七页，共29页。第18页/共29页第十八页，共29页。（5050，400400）（5050，200200）（5050，400400）（5050，300300）F1F1F2F2DCDCW2W2W1W18080707060609090（无限制，（无限制，700700）（无限制，（无限制，900900）第19页/共29页第十九页，共29页。第20页/共29页第二十页，共29页。第21页/共29页第二十一页，共29页。第22页/共29页第二十二页，共29页。第23页/共29页第二十三页，共29页。111122

7、22Min z = 700300200 400900400FWFDCDCWFDCFWDCWffffff第24页/共29页第二十四页，共29页。1111222211122212121112221Min z = 700300200 400900400 = 80+ = 70 () 0s.t. = 60 90,FWFDCDC WFDCFWDC WFWFDCFDCFWDC WDC WFDCFDCFWDC WDC WFWFDCfffffffffffffffffff21211112222, , 50,0FDCDC WDC WFWFDCDC WFDCFWDC Wfffffffff第25页/共29页第二十五页，共