运输问题数学模型(课堂PPT).ppt

《运输问题数学模型(课堂PPT).ppt》由会员分享，可在线阅读，更多相关《运输问题数学模型(课堂PPT).ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运输问题运输问题吴海佳吴海佳勤务指挥系部队管理教研室勤务指挥系部队管理教研室教学内容教学内容教学内容教学内容运输问题运输问题的模型及其的模型及其特点特点求解求解运输问题的运输问题的表上作业法表上作业法产销产销不平衡的运输问题不平衡的运输问题运输问题运输问题（一）运输问题的数学模型（一）运输问题的数学模型讲课提纲讲课提纲一、军事案例一、军事案例实际军事案例实际军事案例(油料运输规划油料运输规划)：某团野外驻训期间要从A1、A2两个联勤加油库调送油料到B1、B2、B3三个驻训地。各油库的储存量、各驻训地的需求量以及从各油库运往各驻训地的单位油料的运价如下表所示。问题：如何调运可使总运输费用最小？驻

2、地驻地油库油库B B1 1B B2 2B B3 3存储量存储量A A1 16 64 46 6200200A A2 26 65 55 5300300需求量需求量150150150150200200一、军事案例一、军事案例 min z=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）数学模型数学模型：讲课提纲讲课提纲二、运输问题的一般数学模型二、运输问题的一般数学模型运输问题（一般提法）：运输问题（一般

3、提法）：把某种产品从若干个产地调拨到若干个销地；已知:每个产地的供应量、如何确定一个使得总的运输费用最小的方案。如果运输问题的总产量等于总销量，则称运输问题为产销平衡运输问题；反之，称产销不平衡运输问题。每个销地的需求量、各地之间的运输单价；什么是运输问题什么是运输问题：二、运输问题的一般数学模型二、运输问题的一般数学模型已知有m个个地点可以供应某种物资(通称产地产地，用i=1,m表示)，有n个个地点需要该种物资(通称销地销地，用j=1,n表示)；m个产地的可供量(通称产量产量)为a1,a2,am(可通写为ai)；n个销地的需求量(通称销量销量)b1,b2,bn(可通写为bj)；从第i个产地到

4、第j个销地的单位物资运价运价为cij。一般数学模型一般数学模型：二、运输问题的一般数学模型二、运输问题的一般数学模型设 xij 为从第i个产地调运给第j个销地的物资的单位数量单位数量，那么产销平衡的条件产销平衡的条件下下 ，得到一般运输问题的数学模型：产量约束产量约束销量约束销量约束目标：运费最小目标：运费最小一般数学模型一般数学模型：二、运输问题的一般数学模型二、运输问题的一般数学模型产销平衡运输问题与一般线性规划问题的联系产销平衡运输问题与一般线性规划问题的联系：min z=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200 x21+x22+

5、x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1,2；j=1,2,3）驻地驻地油库油库B B1 1B B2 2B B3 3存储量存储量A A1 16 64 46 6200200A A2 26 65 55 5300300需求量需求量150150150150200200m个产地个产地=2n个销地个销地=3二、运输问题的一般数学模型二、运输问题的一般数学模型决策变量：约束方程：系数矩阵：基变量（秩）：产销平衡运输问题与线性规划问题的联系产销平衡运输问题与线性规划问题的联系：m个产地个产地=2n个销地个销地=3mn个m+n个，且全部为等式约束

6、等式约束每一个列向量中只有两个元素是两个元素是1，其余元素都是0m+n-1个讲课提纲讲课提纲三、产销不平衡的数学模型三、产销不平衡的数学模型 驻地驻地油库油库B B1 1B B2 2B B3 3存储量存储量A A1 16 64 46 6200200300300A A2 26 65 55 5300300需求量需求量150150150150200200600600500500三、产销不平衡的数学模型三、产销不平衡的数学模型 min z=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13 300 x21+x22+x23 300 x11+x21=150 x12+

7、x22=150 x13+x23=200 xij 0 (i=1,2；j=1,2,3）产销不平衡：产大于销 驻地驻地油库油库B B1 1B B2 2B B3 3存储量存储量A A1 16 64 46 6300300A A2 26 65 55 5300300需求量需求量150150150150200200三、产销不平衡的数学模型三、产销不平衡的数学模型 min z=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13 300 x21+x22+x23 300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1,2；j=1,

8、2,3）产销不平衡产销不平衡：产大于销 min z=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13+a1=300 x21+x22+x23+a2=300 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1,2；j=1,2,3）,a1,a2 0a1+a2=100三、产销不平衡的数学模型三、产销不平衡的数学模型产销不平衡产销不平衡：产大于销【添加人工变量的物理意义】min z=6x11+4x12+6x13+6x21+5x22+5x23+0a1+0a2 s.t.x11+x12+x13+a1=300 x21+x22+x

9、23+a2=300 x11+x21=150 x12+x22=150 x13+x23=200 a1 +a2 =100 xij 0 (i=1,2；j=1,2,3）,a1,a2 0三、产销不平衡的数学模型三、产销不平衡的数学模型产销不平衡产销不平衡：产大于销【添加人工变量的物理意义】min z=6x11+4x12+6x13+6x21+5x22+5x23+0 x14+0 x24 s.t.x11+x12+x13+x14=300 x21+x22+x23+x24=300 x11+x21=150 x12+x22=150 x13+x23=200 x14 +x24 =100 xij 0 (i=1,2；j=1,2,

10、3,4）三、产销不平衡的数学模型三、产销不平衡的数学模型产销不平衡产销不平衡：产大于销【添加人工变量的物理意义】驻地驻地油库油库B B1 1B B2 2B B3 3B4存储量存储量A A1 16 64 46 60300300A A2 26 65 55 50300300需求量需求量150150150150200200100600600 min z=6x11+4x12+6x13+6x21+5x22+5x23+0 x14+0 x24 s.t.x11+x12+x13+x14=300 x21+x22+x23+x24=300 x11+x21=150 x12+x22=150 x13+x23=200 x14

11、+x24 =100 xij 0 (i=1,2；j=1,2,3,4）三、产销不平衡的数学模型三、产销不平衡的数学模型等价转换等价转换添加一个假想的需求地B4，令其需求量为产量过剩值产量过剩值，即产量-销量。并令各油库到B4的运费单价为0 0。为什么是为什么是0 0？只能是只能是0 0吗？吗？产销不平衡产销不平衡：产大于销【添加人工变量的物理意义】驻地驻地油库油库B B1 1B B2 2B B3 3B4存储量存储量A A1 16 64 46 60300300A A2 26 65 55 50300300需求量需求量150150150150200200100600600三、产销不平衡的数学模型三、产销

12、不平衡的数学模型运费单价为只能是运费单价为只能是0 0吗吗?产销不平衡产销不平衡：产大于销【添加人工变量的物理意义】min z=6x11+4x12+6x13+6x21+5x22+5x23+0 x14+0 x24 s.t.x11+x12+x13+x14=300 x21+x22+x23+x24=300 x11+x21=150 x12+x22=150 x13+x23=200 x14 +x24 =100 xij 0 (i=1,2；j=1,2,3,4）驻地驻地油库油库B B1 1B B2 2B B3 3B4存储量存储量A A1 16 64 46 60300300A A2 26 65 55 5030030

13、0需求量需求量150150150150200200100600600三、产销不平衡的数学模型三、产销不平衡的数学模型 min z=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21 250 x12+x22 150 x13+x23 200 xij 0 (i=1,2；j=1,2,3）产销不平衡：销大于产 驻地驻地油库油库B B1 1B B2 2B B3 3存储量存储量A A1 16 64 46 6200200A A2 26 65 55 5300300需求量需求量250250150150200200500

14、600三、产销不平衡的数学模型三、产销不平衡的数学模型产销不平衡产销不平衡：销大于产【添加人工变量的物理意义】min z=6x11+4x12+6x13+6x21+5x22+5x23+0a1+0a2+0a3 s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21+a1=250 x12+x22+a2=150 x13+x23+a3=200 a1 +a2+a3 =100 xij 0 (i=1,2；j=1,2,3）,a1,a2 0三、产销不平衡的数学模型三、产销不平衡的数学模型产销不平衡产销不平衡：销大于产【添加人工变量的物理意义】min z=6x11+4x12+6x13

15、+6x21+5x22+5x23+0 x31+0 x32+0 x33 s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21+x31=250 x12+x22+x32=150 x13+x23+x33=200 x31+x32+x33 =100 xij 0 (i=1,2,3；j=1,2,3）三、产销不平衡的数学模型三、产销不平衡的数学模型产销不平衡产销不平衡：销大于产【添加人工变量的物理意义】min z=6x11+4x12+6x13+6x21+5x22+5x23+0 x31+0 x32+0 x33 s.t.x11+x12+x13=200 x21+x22+x23=300

16、x11+x21+x31=250 x12+x22+x32=150 x13+x23+x33=200 x31+x32+x33 =100 xij 0 (i=1,2,3；j=1,2,3）驻地驻地油库油库B B1 1B B2 2B B3 3存储量存储量A A1 16 64 46 6200200A A2 26 65 55 5300300A3000100需求量需求量250250150150200200600600三、产销不平衡的数学模型三、产销不平衡的数学模型等价转换等价转换添加一个假想的产地A3，令其产量为需求需求过剩值过剩值，即销量-产量。并令A3到各驻地的运费单价为0 0。产销不平衡产销不平衡：销大于产

17、【添加人工变量的物理意义】驻地驻地油库油库B B1 1B B2 2B B3 3存储量存储量A A1 16 64 46 6200200A A2 26 65 55 5300300A3000100需求量需求量250250150150200200600600三、产销不平衡的数学模型三、产销不平衡的数学模型产量大于销量：产量大于销量：建立一个假想的需求地假想的需求地，并令其需求量需求量为原问题中总供应量与总需求量的差值总供应量与总需求量的差值，令各供应地到该需求地到该需求地的运输单价为运输单价为0 0，由此可把原问题转化成供求平衡的运输问题。产量小于销量：产量小于销量：建立一个假想的供应地假想的供应地，

18、并令其供应量供应量为原问题中总需求量与总供应量的差值总需求量与总供应量的差值，令从该供应该供应地到地到各需求地的运输单价为运输单价为0 0，由此可把原问题转化成供求平衡的运输问题。经验总结：经验总结：三、产销不平衡的数学模型三、产销不平衡的数学模型由于供不应求，经总部统筹安排决定：B1供应量可减少0300吨，B2必须全部满足，B3供应量不得少于1500吨。试求出总运费最低的调拨方案。试试这道题：试试这道题：驻地驻地油库油库B B1 1B B2 2B B3 3存储量存储量A A1 11.801.801.701.701.551.5540004000A A2 21.601.601.501.501.7

19、51.7515001500需求量需求量300030001000100020002000550060002700270015001500需要添加剩余变量！需要添加剩余变量！三、产销不平衡的数学模型三、产销不平衡的数学模型试试这道题：试试这道题：min z=1.8x11+1.7x12+1.55x13+1.6x21+1.5x22+1.75x23 s.t.x11+x12+x13=4000 x21+x22+x23=1500 x11+x21 2700 x11+x21 3000 x12+x22=1000 x13+x23 1500 x13+x23 2000 xij 0 (i=1,2；j=1,2,3）x11+x

20、21 s1=2700 x13+x23 s2=1500标准化后，系数矩阵找不到单位阵，怎么办？标准化后，系数矩阵找不到单位阵，怎么办？三、产销不平衡的数学模型三、产销不平衡的数学模型等价转换等价转换添加一个假想的产地，令其需求量为产量过剩值产量过剩值，即产量-销量。将驻地的需求分为必须满足部分和非必须满足部分。令假想油库到必须满足部分的运费单价为M。令假想油库到非必须满足部分的运费单价为0。产销不平衡产销不平衡：【大M技巧的物理意义】驻地驻地油库油库B B1 1B B2 2B B3 3存储量存储量A A1 11.801.801.701.701.551.5540004000A A2 21.601.

21、601.501.501.751.7515001500需求量需求量300030001000100020002000550060002700270015001500三、产销不平衡的数学模型三、产销不平衡的数学模型等价转换等价转换添加一个假想的产地，令其需求量为产量过剩值产量过剩值，即产量-销量。将驻地的需求分为必须满足部分和非必须满足部分。令假想油库到必须满足部分的运费单价为M。令假想油库到非必须满足部分的运费单价为0。产销不平衡产销不平衡：【大M技巧的物理意义】驻地驻地油库油库B B1 1B B1 1B B2 2B B3 3B B3 3存储量存储量A A1 11.801.801.801.801.

22、701.551.5540004000A A2 21.601.601.601.601.501.751.7515001500假想油库假想油库M0MM0500需求量需求量270027003001000150050060006000三、产销不平衡的数学模型三、产销不平衡的数学模型产销不平衡产销不平衡：【大M技巧的物理意义】驻地驻地油库油库B B1 1B B1 1B B2 2B B3 3B B3 3存储量存储量A A1 11.801.801.801.801.701.551.5540004000A A2 21.601.601.601.601.501.751.7515001500假想油库假想油库M0MM05

23、00需求量需求量270027003001000150050060006000 驻地驻地油库油库B B1 1B B2 2B B3 3存储量存储量A A1 11.801.801.701.701.551.5540004000A A2 21.601.601.501.501.751.7515001500需求量需求量300030001000100020002000550060002700270015001500讲课提纲讲课提纲实际的军事案例实际的军事案例油料运输问题；油料运输问题；运输问题的一般模型；运输问题的一般模型；产销不平衡的运输问题模型的转化；产销不平衡的运输问题模型的转化；总结总结下节提要下节提要下节提要：下节提要：运输问题的利器之表上作业法！运输问题的利器之表上作业法！如何求解如何求解 运输问题？运输问题？