1运输问题棋烈及有类概A 问题的提出 般的运输问题就是要解决把 某种产品从若干个产地调运到若干个 销地,在每个产地的供应量与每个销 地的需求量己知,并知道各地之间的 远输单价的前提下,如何确定一个使 得总的运输费用最小的方案
3 1.运输问题模型及有关概念 问题的提出 一般的运输问题就是要解决把 某种产品从若干个产地调运到若干个 销地,在每个产地的供应量与每个销 地的需求量已知,并知道各地之间的 运输单价的前提下,如何确定一个使 得总的运输费用最小的方案
1运输问题棋烈及有类概A 例4.1:某公司从两个产地A、 A2将物品运往三个销地B、B2、B3, 各产地的产量、各销地的销量和 各产地远往个销地每件物品的运 费如下表所示 应如何调远 可使总运输费用最小? B B2 B 产量 6 4 6 200 6 5 5 300 销量 150 150 200
4 1.运输问题模型及有关概念 例4.1:某公司从两个产地A1、 A2将物品运往三个销地B1、B2、B3, 各产地的产量、各销地的销量和 各产地运往个销地每件物品的运 费如下表所示,问:应如何调运 可使总运输费用最小?
1运输问题棋烈及有类概A 解:产销平衡问题 总产量三总销量 设x1为从产地A运往销地B 的远瑜量。得到下列远输量表: Bl B B3 里 x11 x12 13 200 x21 300 销量150 150 200
5 解: 产销平衡问题: 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj 的运输量,得到下列运输量表: 1.运输问题模型及有关概念
1运输问题棋烈及有类概A Minf=6x1+4x26+6x1+5x2+5x2 S.t.x1t+x12+x13=200 x21+x2+x23=300 150 X12+X22 150 13 23 200 x1≥>0(i1,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运输问题棋及有类概戏 系数矩阵 1100 0100 0010 000 1100 0 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运输问题模型及有关概A 模型系数矩阵特征 1.共有n行,分别表示各 产地和销地;m列,分别表示各 变量 2.每列只有两个1.其余 为0.分别表示只有一个产地和 个销地被使用
8 模型系数矩阵特征 1.共有m+n行,分别表示各 产地和销地;m列,分别表示各 变量; 2.每列只有两个 1,其余 为 0,分别表示只有一个产地和 一个销地被使用。 1.运输问题模型及有关概念
1运输问题模型及有关概A 一般运输问题的线性规灲模型及求解思路 一般运输问题的提法 假设A1,A2,…,A表示某物资的m个 产地;B1,B,…,B表示某物资的n个销地; S:表示产地A的产量;d表示销地B的 销量;C;表示把物资为从产地A运往销 地B;的单位运价(表4-3)。如果S1+S d,+d++d.,则称该 运输问题为产销平衡问题:否则,称产销 不平衡。下面,首先讨论产销平衡问题
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.运输问题模型及有关概念