北京理工大学：《运筹学》课程PPT教学课件（讲稿）第四章 运输问题

课 制作:北景狸工夫吴新泉奇 器因翻 数学术

运筹学课件 制作：北京理工大学 吴祈宗等

第四章运瑜问题 本章内容重点 运瑜问题与有关概念 运瑜问题的求解一表上作业法 运瑜问题应用—建模

2 第四章 运输问题 运输问题与有关概念 运输问题的求解—表上作业法 运输问题应用—建模 本章内容重点

1运输问题摸烈及有关概念 问题的提出 般的远瑜问题就是要解决把 某种产品从若干个产地调到考干个 销地,在每个产地的供应量与每个销 地的鼎求量已知,并知道各地之间的 运输单价的前提下,如何确定一个使 得总的运输费用最小的方案

3 1.运输问题模型及有关概念 问题的提出 一般的运输问题就是要解决把 某种产品从若干个产地调运到若干个 销地，在每个产地的供应量与每个销 地的需求量已知，并知道各地之间的 运输单价的前提下，如何确定一个使 得总的运输费用最小的方案

1运输问题摸烈及有关概念 例4.1:某公司从两个产地A1 A2将物品运往三个销地B1、B2、B3, 各产地的产量、各销地的销量和 各产地运往各销地每件物品的沄 费如下表所示,问:应如何调运 可使总沄输费用最小? B—66 B2 B 产量 45 65 200 a 2 300 销量 150 150 200

4 1.运输问题模型及有关概念 例4.1:某公司从两个产地A1、 A2将物品运往三个销地B1、B2、B3， 各产地的产量、各销地的销量和 各产地运往各销地每件物品的运 费如下表所示，问：应如何调运 可使总运输费用最小？

1运输问题摸烈及有关概念 解:产销平衡问题: 总产量三总销量 设x为从产地A运往销地B 的运输量,得到下列运输量表: Bi B2 B3产量 W 13 00 x23 300 销量 150 150 200

5 解： 产销平衡问题： 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj 的运输量，得到下列运输量表： 1.运输问题模型及有关概念

1运输问题摸烈及有关概念 Minf=6x1+4x2+6x13+6x1+5x2+5x3 s. t 12 13 200 x21+x2+x23=300 x1+x1=150 x1+xp=150 Xu X 23 200 >0(=1,2;六1,2,3)

6 Min f = 6x11+4x12+6x13+6x21+5x22+5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij≥0(i=1,2；j=1,2,3） 1.运输问题模型及有关概念

1运输问题模烈及有关概念 系数矩阵 10 0100 0010 000 1100 01010 0100

7 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 系数矩阵 1.运输问题模型及有关概念

运翁问题模型及有关概 模型系数矩阵特征 1.共有mn行,分别表示各 产地和销地:m1列。分别表示 各决策变量 2.每列只有两个1.其余 为0.分别表示只有一个产地和 个销地被使用

8 模型系数矩阵特征 1.共有m+n行，分别表示各 产地和销地；mn列，分别表示 各决策变量； 2.每列只有两个 1，其余 为 0，分别表示只有一个产地和 一个销地被使用。 1.运输问题模型及有关概念

运翁问题模型及有关概 般运输冋题的线性规灲模型及求解思路 般远输问题的提法 假设A1,A,…,A表示某物资的m个 产地;B1,B,…,B表示某物资的I个销地; S:表示产地A1的产量;表示销地B单 的 销量 表示把物资从产地A1运往销 B.的单位运价(表4-3) 如果 m dn 称该远输问题为产销平衡问题:否则。称 产销不平衡。首先讨论产销平衡问题

9 一般运输问题的线性规划模型及求解思路 一般运输问题的提法： 假设 A1 , A2 ,…,Am 表示某物资的m个 产地；B1,B2,…,Bn 表示某物资的n个销地； si表示产地 Ai 的产量；dj 表示销地 Bj 的 销量；cij 表示把物资从产地 Ai 运往销地 Bj 的单位运价（表4-3）。如果 s1 + s2 + … + sm = d1 + d2 + … + dn 则称该运输问题为产销平衡问题；否则，称 产销不平衡。首先讨论产销平衡问题。 1.运输问题模型及有关概念

运翁问题模型及有关概 表4-3运输问题数据表 销地 b, B 产量 产地 销量 设x;为从产地;运往销地B的运 输量,根据这个运输冋题的要求,可以建立 运输变量表(表4-4)

10 表4-3 运输问题数据表 1.运输问题模型及有关概念 销地 产地 B1 B2 … Bn 产量 A1 A2 ┇ Am c11 c12 … c1n c21 c22 … c2n ┇ ┇ ┇ ┇ cm1 cm2 … cmn s1 s2 ┇ sm 销量 d1 d2 … dn 设 xij 为从产地 Ai 运往销地 Bj 的运 输量，根据这个运输问题的要求，可以建立 运输变量表（表 4-4）