logo资料库

运筹学运输问题小论文.docx

发布时间：2022-06-03 发布人：admin 分类：说明书 资料大小：0.06M 资料格式：docx 举报 版权申诉
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
资料共9页，剩余部分请下载后查看
    运输问题 摘要：运输问题（transportation problem）一般是研究把某种商品从若干个产 地运至若干个销地而使总运费最小的一类问题。然而从更广义上讲，运输问题是 具有一定模型特征的线性规划问题。它不仅可以用来求解商品的调运问题，还可 以解决诸多非商品调运问题。运输问题是一种特殊的线性规划问题，由于其技术 系数矩阵具有特殊的结构，这就有可能找到比一般单纯形法更简便高效的求解方 法，这正是单独研究运输问题的目的所在。 引言：运输一般分为运输和配送。关于运输和配送的区分，有许多不同的观点， 可以这样来说，所有物品的移动都是运输，而配送则专指短距离、小批量的运输。 因此，可以说运输是指整体，配送则是指其中的一部分，而且配送的侧重点在于 一个“配”字，它的主要意义也体现在“配"字上；而”送”是为最终实现资源 配置的“配”而服务的。 运输功能要素。包括供应及销售物流中的车、船、飞机等方式的运输，生 产物流中的管道、传送带等方式的运输。 运输是指把人、财、物由一个地方转移到另外一个地方的过程。运输又被 认为是国民经济的根本． 运输的主要工具有自行车.板车.三轮车.摩托车.汽车.火车.飞机.轮船.宇 宙飞船.火箭.等等 运输按服务对象不同分为客运和货运 公共运输,泛指所有收费提供交通服务的运输方式。 轿车托运:(轿车运输)是指将汽车做为商品出厂后,通过大型汽车运输工具, 到达指定地方的运输方式 运输运价的构成 发到基价，运行基价构成，货物运输杂费 零担货物年车运价=每吨运价×计费重量 整车货物每吨运价=发到基价+运行基价×运价里程 集装箱货物每箱运价=发到基价+运行基价×运价里程 运输问题的数学模型 某公司经营某种产品，该公司下设 A、B、C 三个生产厂，甲、乙、丙、丁四 个销售点。公司每天把三个工厂生产的产品分别运往四个销售点，由于各工厂到 各销售点的路程不同，所以单位产品的运费也就不同案。各工厂每日的产量、各 销售点每日的销量，以及从各工厂到各销售点单位产品的运价如表 4-1 所示。问 该公司应如何调运产品，在满足各销售点需要的前提下，使总运费最小。
    表 4-1 A B C 销量（ jb ） 甲 3 1 7 3 乙 11 9 4 6 丙 3 2 10 5 产量( ia ) 7 4 9 丁 10 8 5 6 设 ijx 代表从第i 个产地到第 j 个销地的运输量（ i  ;3,2,1 j  4,3,2,1 ），用 ijc 代表从第 i 个产地到第 j 个销地的运价，于是可构造如下数学模型： min   3 4  i 1  j 1  c ij x ij x ij  a i ( i  ;3,2,1 运出的商品总量等于其 产量） x ij  b j （ ;4,3,2,1j  运来的商品总量等于其 产量）  0 4  j 1  3  1 i  x ij           通过该引例的数学模型，我们可以得出运输问题是一种特殊的线性规划问题 的结论，其特殊性就在于技术系数矩阵是由“1”和“0”两个元素构成的。 将该引例的数学模型做一般性推广，即可得到有 m 个产地、n 个销地的运输 问题的一般模型。注意:在此仅限于探讨总产量等于总销量的产销平衡运输问题， 而产销不平衡运输问题在本章的后续内容中探讨。 min   n m  i 1  j 1  c ij x ij x ij  a i ( i  ,...,2,1 ; m 运出的商品总量等于其 产量） x ij  b j （ ,...,3,2,1j  ; n 运来的商品总量等于其 产量）  0 n 1 j  m         1 i   x ij    供应约束确保从任何一个产地运出的商品等于其产量，需求约束保证运至任 何一个销地的商品等于其需求。除非负约束外，运输问题约束条件的个数是产地 与销地的数量和，即 nm  ；而决策变量个数是二者的积，即 nm* 。由于在这 nm  个约束条件中，隐含着一个总产量等于总销量的关系式，所以相互独立的约束条 件的个数是 个。 1 nm
    运输问题的求解： 运输问题的求解采用表上作业法，该方法是单纯形法求解运输问题的一种特定形 式，其实质是单纯形法。既然表上作业法是一种特定形式的单纯形法，它自然与 单纯形法有着完全相同的解题步骤，所不同的只是完成各步采用的具体形式。表 上作业法的基本步骤可参照单纯形法归纳如下： 1. 找出初始基可行解：即要在 nm* 阶产销平衡表上给出“ 1 nm ”个数字（基 变量）； 2. 求各非基变量（空格）的检验数，判断当前的基可行解是否是最优解，如已 得到最优解，则停止计算，否则转到下一步； 3. 确定入基变量，若  min | ＜  ij ij  0  lk ，那么选取 lkx 为入基变量； 4. 确定出基变量，找出入基变量的闭合回路，在闭合回路上最大限度地增加 基变量的值，那么闭合回路上首先减少为“0”的基变量即为出基变量； 5. 在表上用闭合回路法调整运输方案； 6. 重复 2、3、4、5 步骤，直到得到最优解。 确定初始基可行解 与一般的线性规划不同，产销平衡的运输问题一定具有可行解（同时也一定存在 最优解），这一点是显然的。确定初始基可行解的方法有很多，下面是最小元素 法。 最小元素法 最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定 产销关系，依此类推，一直到给出基本方案为止。下面就用例 4-1 说明最小元素 法的应用。 第一步：从表 4-1 中找出最小运价“1”，这表示先将 B 生产的产品供应给 甲。由于 B 每天生产 4 个单位产品，甲每天需求 3 个单位产品，即 B 每天生产的 产品除满足甲的全部需求外，还可多余 1 个单位产品。在（B，甲）的交叉格处 填上“3”，形成表 4-2；将运价表的甲列运价划去得表 4-3，划去甲列表明甲的 需求已经得到满足。
    表 4-2 A B C 销量（ jb ） 表 4-3 A B C 甲 乙 丙 丁 产量( ia ) 3 3 甲 3 1 7 6 5 6 乙 11 9 4 丙 3 2 10 7 4 9 丁 10 8 5 第二步：在表 4-3 的未被划掉的元素中再找出最小运价“2”，最小运价所 确定的供应关系为（B，丙），即将 B 余下的 1 个单位产品供应给丙，表 4-2 转 换成表 4-4。划去 B 行的运价，划去 B 行表明 B 所生产的产品已全部运出，表 4-3 转换成表 4-5。 表 4-4 A B C 销量（ jb ） 甲 乙 丙 丁 产量( ia ) 3 3 6 1 5 6 7 4 9 第三步：在表 4-5 中再找出最小运价“3”，这样一步步地进行下去，直到 单位运价表上的所有元素均被划去为止。最后在产销平衡表上得到一个调运方 案，见表 4-6。这一方案的总运费为 86 个单位。
    表 4-5 A B C 表 4-6 A B C 销量（ jb ） 甲 3 1 7 甲 3 3 3 乙 11 9 4 乙 11 6 6 丙 3 2 10 丁 10 8 5 丙 丁 产量( ia ) 4 1 5 3 3 6 7 4 9 最小元素法各步在运价表中划掉的行或列是需求得到满足的列或产品被调 空的行。一般情况下，每填入一个数相应地划掉一行或一列，这样最终将得到一 个具有“m+n-1”个数字格（基变量）的初始基可行解。然而，问题并非总是如 此，有时也会出现这样的情况：在供需关系格（i,j）处填入一数字，刚好使第 i 个产地的产品调空，同时也使第 j 个销地的需求得到满足。按照前述的处理方 法，此时需要在运价表上相应地划去第 i 行和第 j 列。填入一数字同时划去了一 行和一列，如果不加入任何补救措施的话，那么最终必然无法得到一个具“m+n-1” 个数字格（基变量）的初始基可行解。为了使在产销平衡表上有“m+n-1”个数 字格，这时需要在第 i 行或第 j 列此前未被划掉的任意一个空格上填一个“0”。 填“0”格虽然所反映的运输量同空格没有什么不同；但它所对应的变量却是基 变量，而空格所对应的变量是非基变量。 表 4-7 A B C 销量（ jb ） 甲 3 1 7 3 乙 11 9 4 6 丙 3 2 10 5 产量( ia ) 10 4 12 丁 10 8 5 6
    将表 4-1 的各工厂的产量做适当调整（调整结果见表 4-7），就会出现此类 特殊情况。第一步在（B，甲）处填入“3”，划去甲列运价；第二步在（B，丙） 处填入“1”，划去 B 行运价，此二步的结果见表 4-8 和表 4-9。 表 4-8 A B C 销量（ jb ） 表 4-9 A B C 销量（ jb ） 表 4-10 A B C 销量（ jb ） 甲 乙 丙 丁 产量( ia ) 3 3 甲 3 1 7 3 甲 3 3 6 乙 11 9 4 6 乙 0 6 4 4 12 产量( ia ) 4 4 12 6 丁 10 8 5 6 1 5 丙 3 2 10 5 丙 丁 产量( ia ) 4 1 5 4 4 12 6
    表 4-11 A B C 销量（ jb ） 甲 3 1 7 3 乙 11 9 4 6 丙 3 2 10 5 产量( ia ) 4 4 12 丁 10 8 5 6 表 4-9 中剩下的最小元素为“3”，其对应产地 A 的产量是 4，销地丙的剩 余需要量也是 4，在格（A，丙）中填入“4”，需同时划去 A 行和丙列。在填入 “4”之前 A 行和丙列中除了（A，丙）之外，还有（A，乙）、（A，丁）和（C， 丙）三个空格未被划去；因此，可以在（A，乙）、（A，丁）和（C，丙）任选 一格填加一个“0”，不妨选择（A，乙），结果可见表 4-10 和表 4-11。注意这 个“0”是不能填入（A，甲）或（B，丙）的，因为在填入“4”之前它们已经被 划去了。
    实例分析： 有三个化肥厂供应四个地区的化肥需求，假定等量化肥在这些地区的使用效 果相同。各肥厂年产量、各地区年需要量及从各化肥厂到各地区运送单位化肥的 单位运价如表 3-8 所示，试求出总的运费最节省的化肥调拨方案。 表 3-8（单位：万吨） 地区 1 地区 2 地区 3 地区 4 产量 化肥厂 A 化肥厂 B 化肥厂 C 年需要量 最低要求 最高要求 16 14 19 30 50 13 13 20 70 70 50 60 50 22 19 23 0 30 17 15 M 10 不限 160 0-70-30- 这是一个产销不平衡的运输问题，总产量为 160 万吨，四个地区的最低需求 为 110 万吨，最高需求为无限。根据现有产量，除满足地区 1、地区 2 和地区 3  ）万吨，这样 的最低需求外，地区 4 每年最多能分配到 60（ 其不限的最高需求可等价认为是 60 万吨。按最高需求分析，总需求为 210 万吨， 大于总产量 160 万吨，将此问题定义为销大于产的运输问题。为了求得平衡，在 产销平衡表中增加一个假想的化肥厂 D，令其年产量为 50（ 各地区的需要量包含最低和最高两部分：如地区 1，其中 30 万吨是最低需求， 故这部分需求不能由假想的化肥厂 D 来供给，因此相应的运价定义为任意大正数 M；而另一部分 20 万吨满足与否都是可以的，因此可以由假想化肥厂 D 来供给， 按前面讲的，令相应运价为“0”。凡是需求分两种情况的地区，实际上可按照 两个地区来看待，这样可以将表 4-38 所示的运输问题转换为表 39 所示的运输问 题。 ）万吨。 210  160 60  50 表 3-9（单位：万吨） 地区 1 地区 1 地区 2 地区 3 地区 4 地区 4 产量 化肥厂 A 化肥厂 B 化肥厂 C 化肥厂 D 年需要量 16 14 19 M 30 16 14 19 0 20 13 13 20 M 70 22 19 23 0 30 17 15 M M 10 17 15 M 0 50 50 60 50 50
    分享到：
    赞 收藏

    相关推荐

    资料库

    大数据

    共收录841份资料，累计11个分类，关注成员有19位，主要包括：Matlab,统计分析,数据挖掘,Hbase,Hive,flink,kafka,spark,Storm,算法与数据结构,Hadoop

    热门标签

    Matlab 统计分析 数据挖掘 Hbase Hive flink kafka spark Storm 算法与数据结构 Hadoop

    最新资料