图a与a网a络.ppt

经济与管理决策方法导论 重庆大学经济与工商管理学院iongzhongkai bearelm1 决策方法 之六 图与网络及其应用 村庄1 伊拉克战后建设 30个村庄要通电话 已知两两距离 如何用最少的电话线 破圈法与避圈法 村庄4 村庄3 村庄6 村庄2 村庄5 6 3 11 5 9 8 10 7 12 7 网络结构 Internet DNS 内网WWW服务器 外网WWW服务器 楼层交换机 防火墙 网管工作站 OA骨干交换机 楼层交换机 用户工作站 CISCO路由器 骨干交换机 PSTN 移动办公 DCN 其它部门 OA EMAIL主机 决策方法 之六 图与网络及其应用 V2 V5 V1 V4 V3 4 1 5 3 6 2 七个居民点选择其一建立工商银行使得所有点到工商银行的最大距离最小 七个居民点选择两个建立工商银行使得所有点到工商银行的最大距离最小 V7 V6 1 8 1 5 3 决策方法 之六 图与网络及其应用 七个居民点选择其一建立工商银行使得所有点到工商银行的最大距离最小 任意两点间最短路长度如下表 最后一列是每个点到各个点的最大距离如果V6居民点建立工商银行 到其他点最大距离为4 8 决策方法 之六 图与网络及其应用 七个居民点选择其二建立工商银行使得所有点到工商银行的最大距离最小 上面矩阵任意取两行 例如第2行与第5行 表示第2 七个居民点选择两个建立工商银行使得所有点到工商银行的最大距离最小 如果在第1居民点 第2居民点建立工商银行 上面矩阵取第1行与第2行 表示其他各个居民点到每个工商银行的距离 表示其他各个居民点到这两个工商银行的最小距离 表示其他各个居民点到这两个工商银行的最小距离最大者 决策方法 之六 图与网络及其应用 七个居民点选择其二建立工商银行使得所有点到工商银行的最大距离最小 上面矩阵任意取两行 例如第2行与第5行 表示第2 七个居民点选择两个建立工商银行使得所有点到工商银行的最大距离最小 如果在第2居民点 第5居民点建立工商银行 上面矩阵取第2行与第5行 表示其他各个居民点到每个工商银行的距离 表示其他各个居民点到这两个工商银行的最小距离 表示其他各个居民点到这两个工商银行的最小距离最大者 决策方法 之六 图与网络及其应用 七个居民点选择其二建立工商银行使得所有点到工商银行的最大距离最小 七个居民点选择两个建立工商银行使得所有点到工商银行的最大距离最小 同理 有21种建立工商银行的可能性 分别求出再比较得到解 6 3 3 决策方法 之六 图与网络及其应用 已知设备在各年初的价格 Ki和使用时的运行与维修费Ci如下表 某企业使用一台设备 每年初 企业领导要决定是购置新的还是继续使用旧 若购置新设备 就要支付一定的购置费用 若继续使用旧设备 就要支付一定的维护费用 问题是如何制定一个五年之内的设备更新计划 目标是总支付费用最少 因为时间太长这种设备会被淘汰 决策方法 之六 图与网络及其应用 如下例子看起来不是网络问题 我们可以化为网络来求解最短路解决设备更新问题 请给出五年设备更新计划 使总费用最少 1 把问题表示成最短路问题 画出网络图 2 求最优设备更新计划 决策方法 之六 图与网络及其应用 网络最短路解 1 设节点 代表计划期始点和终点 代表第2 3 4 5年开始 当J I时 每一个节点I有一条有向弧与节点J相连 这样可以得到有向网络图 2 最短路为 即在五年中 第一年和第三年初购买新设备为最优方案 最低