在运送货物时.ppt

、 销地 产地 1 2 n 产量 销地 产地 1 2 n 1 2 m A1 A2 am 1 2 n C11 C12 C1n C21 C22 C2n Cm1 Cm2 Cnm 销量 B1 B2 Bn 如果用Xij表示从第i个产地运到第j个销地的物品的单位数量,使总运费最 小，用线性数规划表示 出发地和目的地在同一地点 一个邮递员负责某一地区的信件投递，他每天要从邮局出发，走遍该地区所有街道再回邮局，如何安排使路程最短。 ——中国邮递员问题 图： 图是有点集V={Vi}和V中元素的无序对的一个集合E={ek}所构成的二元组。 V中元素Vi叫做顶点 , E中的元素ek叫做边。 两个点u、v属于V，如果边(u、v)属于E，则称u、v两点相邻，u、v称为边（u、v）的端点。 对于的任一条边（Vi、、Vj）属于E，如果边（Vi、、Vj）端点无序，则它是无向边，图为无向图，如果边的端点有序，此时图为有向图。图中若点或边有某种数量指标（权），则图称之为网络。 以点V为端点的边数叫做点V的次，次为奇数的点称为奇点，次为偶数的点为偶点，任何图中次为奇数的顶点必为偶数个。 2 5 7 6 11 4 8 V0 V 1 V3 V5 V4 V2 连通图 图中某些点与边的交替序列可以排成（V0、e1、V1、e2、V2、……VK—1、eK、VK）的形式，且eK=(VK—1、VK)，则称这个点边序列为一条链，链中V0与VK是同一个点时，称为圈，圈中既无重复点也无重复边者称为初等圈。 一个图中任意两点间至少有一条链相连，则称此图为连通图： 树 连通且不含圈的无向图称为树，若图的子图是一棵树，则称该树为图的支撑树，图中属于支撑树的边称为树枝，不在支撑树上的边称为弦，一棵支撑树所有树枝上权的总和，称为这个树的权，具有最小权的支撑树，称为最小支撑树，简称最小树。 最小树的算法 每步从未选的边中，选取边e,使它与未选边不够成圈，且e是未选边中的最小权边，直到选够n-1条边为止 S A C B D E T 2 4 2 5 7 5 1 1 3 4 7 5 S A C B D E T 2 4 2 5 7 5 1 1 3 4 7 5 S A C B D E T 2 4 5 7 5 1 1 3 4 7 5 S A C B D E T 2 4 5 7 5 1 1 3 4 7 5 S A C B D E T 2 4 2 5 7 5 1 1 3 4 7 5 S A C B D E T 2 4 2 5 7 5 1 1 3 4 7 5 中国邮递员问题算法——奇偶点图上作业法 2 4 3 4 4 9 5 5 4 4 6 V1 V7 V4 V5 V9 V8 V2 V3 V6 达到最优的充分必要条件是： 1、每条边最多重复一次（达到图中无奇点）。 2、图中每个初等圈重复边的长度和不超过圈长的一半。 3 第一步：检查图中是否有奇点，如有，奇点个数必为偶数，可两两配对 2 4 3 4 4 9 5 5 4 4 6 V1 V7 V4 V5 V9 V8 V2 V3 V6 3 第二步：检查图中每个初等圈是否满足第2个条件，如不满足，重复调整 2 4 3 4 4 9 5 5 4 4 6 V1 V7 V4 V5 V9 V8 V2 V3 V6 2 4 3 4 4 9 5 5 4 4 6 V1 V7 V4 V5 V9 V8 V2 V3 V6 3 自营运输之弊 （1）需要自筹资金来购买和更新车辆； （2）由于有些成本隐藏在一般性支出项（工资和薪金部分）下，难以确切地评估自营运输的成本； （3）车辆的使用效率通常较低； （4）不论是否使用车辆，都发生费用； （5）由于难以获得回程货物，更容易出现不平衡载货，甚至回空问题。 自营运输成本 1、持有成本：车辆、车库设施、车辆保险、办证费用、 资金利息、折旧 2、运输者成本：与司机有关的成本、包括工资、与健康有关的成本，保险费用，途中膳食费用 3、车辆运费成本 麦当劳的冷链物流 “麦当劳不仅仅是一家餐厅。”麦当劳创始人雷·克洛克曾是一位奶昔机推销商。54岁开始了经营麦当劳的传奇事业。50年后的今天，麦当劳已经在全球120多个国家拥有29000多家餐厅，居全球知名品牌的前十位。在这个群体力量的成功故事中，物流伴随“我就喜欢”的火热节奏行遍全球，在麦当劳品牌的成长中扮演了一个不可或缺的角色。 1990年，中国的第一家麦