运输问题数学模型.ppt

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

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

2、示。问题：如何调运可使总运输费用最小？驻地地油油库B1B2B3存存储量量A1646200A2655300需求量需求量150150200一、军事案例一、军事案例 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个产地到第j个销地的单

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

5、 x11+x21=150 x12+x22=150 x13+x23=200 xij 0 (i=1,2；j=1,2,3）驻地地油油库B1B2B3存存储量量A1646200A2655300需求量需求量150150200m个产地个产地=2n个销地个销地=3二、运输问题的一般数学模型二、运输问题的一般数学模型决策变量：约束方程：系数矩阵：基变量（秩）：产销平衡运输问题与线性规划问题的联系产销平衡运输问题与线性规划问题的联系：m个产地个产地=2n个销地个销地=3mn个m+n个，且全部为等式约束等式约束每一个列向量中只有两个元素是两个元素是1，其余元素都是0m+n-1个讲课提纲讲课提纲军事事案例案例一般一般

6、模型模型产销不平不平总结三、产销不平衡的数学模型三、产销不平衡的数学模型 驻地地油油库B1B2B3存存储量量A1646200300A2655300需求量需求量150150200600500三三、产销不平衡的数学模型、产销不平衡的数学模型 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,2,3）产销不平衡：产大于销 驻地地油油库B1B2B3存存储量量A1646300A2655300需求量需求量15

7、0150200三三、产销不平衡的数学模型、产销不平衡的数学模型 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,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=

8、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+x23+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

9、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）三三、产销不平衡的数学模型、产销不平衡的数学模型产销不平衡产销不平衡：产大于销【添加人工变量的物理意义】驻地地油油库B1B2B3B4存存储量量A16460300A26550300需求量需求量150150200100600600 min z=6x11+4x12+6x13+6x21

10、+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）三三、产销不平衡的数学模型、产销不平衡的数学模型等价转换等价转换添加一个假想的需求地B4，令其需求量为产量过剩产量过剩值值，即产量-销量。并令各油库到B4的运费单价为0 0。为什么是为什么是0 0？只能是只能是0 0吗？吗？产销不平衡产销不平衡：产大于销【添加人工变量的物理意义】驻地地油油库B1B2B3B4存存储量量A

11、16460300A26550300需求量需求量150150200100600600三三、产销不平衡的数学模型、产销不平衡的数学模型运费单价为运费单价为只能只能是是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）驻地地油油库B1B2B3B4存存储量量A

12、16460300A26550300需求量需求量150150200100600600三三、产销不平衡的数学模型、产销不平衡的数学模型 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）产销不平衡：销大于产 驻地地油油库B1B2B3存存储量量A1646200A2655300需求量需求量250150200500600三三、产销不平衡的数学模型、产销不平衡的数学模型产销不平衡产销不平衡：销大于产【

13、添加人工变量的物理意义】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+6x21+5x22+5x23+0 x31+0 x32+0 x33 s.t.x11+x

14、12+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 x11+x21+x31=250 x12+x22+x32=150 x13+x23+x33

15、=200 x31+x32+x33 =100 xij 0 (i=1,2,3；j=1,2,3）驻地地油油库B1B2B3存存储量量A1646200A2655300A3000100需求量需求量250150200600600三三、产销不平衡的数学模型、产销不平衡的数学模型等价转换等价转换添加一个假想的产地A3，令其产量为需求需求过剩值过剩值，即销量-产量。并令A3到各驻地的运费单价为0 0。产销不平衡产销不平衡：销大于产【添加人工变量的物理意义】驻地地油油库B1B2B3存存储量量A1646200A2655300A3000100需求量需求量250150200600600三三、产销不平衡的数学模型、产销不平

16、衡的数学模型产量大于销量：产量大于销量：建立一个假想的需求地假想的需求地，并令其需求量需求量为原问题中总供应量总供应量与总需求量的差值与总需求量的差值，令各供应地到该需求地到该需求地的运输单价为运输单价为0 0，由此可把原问题转化成供求平衡的运输问题。产量小于销量：产量小于销量：建立一个假想的供应地假想的供应地，并令其供应量供应量为原问题中总需求量总需求量与总供应量的差值与总供应量的差值，令从该供应地到该供应地到各需求地的运输单价为运输单价为0 0，由此可把原问题转化成供求平衡的运输问题。经验总结：经验总结：三三、产销不平衡的数学模型、产销不平衡的数学模型由于供不应求，经总部统筹安排决定：B1

17、供应量可减少0300吨，B2必须全部满足，B3供应量不得少于1500吨。试求出总运费最低的调拨方案。试试这道题：试试这道题：驻地地油油库B1B2B3存存储量量A11.801.701.554000A21.601.501.751500需求量需求量300010002000550060002700270015001500需要添加剩余变量！需要添加剩余变量！三三、产销不平衡的数学模型、产销不平衡的数学模型试试这道题：试试这道题：min z=1.8x11+1.7x12+1.55x13+1.6x21+1.5x22+1.75x23 s.t.x11+x12+x13=4000 x21+x22+x23=1500 x

18、11+x21 2700 x11+x21 3000 x12+x22=1000 x13+x23 1500 x13+x23 2000 xij 0 (i=1,2；j=1,2,3）x11+x21 s1=2700 x13+x23 s2=1500标准化后，系数矩阵找不到单位阵，怎么办？标准化后，系数矩阵找不到单位阵，怎么办？三三、产销不平衡的数学模型、产销不平衡的数学模型等价转换等价转换添加一个假想的产地，令其需求量为产量过剩值产量过剩值，即产量-销量。将驻地的需求分为必须满足部分和非必须满足部分。令假想油库到必须满足部分的运费单价为M。令假想油库到非必须满足部分的运费单价为0。产销不平衡产销不平衡：【大M

19、技巧的物理意义】驻地地油油库B1B2B3存存储量量A11.801.701.554000A21.601.501.751500需求量需求量300010002000550060002700270015001500三三、产销不平衡的数学模型、产销不平衡的数学模型等价转换等价转换添加一个假想的产地，令其需求量为产量过剩值产量过剩值，即产量-销量。将驻地的需求分为必须满足部分和非必须满足部分。令假想油库到必须满足部分的运费单价为M。令假想油库到非必须满足部分的运费单价为0。产销不平衡产销不平衡：【大M技巧的物理意义】驻地地油油库B1B1B2B3B3存存储量量A11.801.801.701.551.5540

20、00A21.601.601.501.751.751500假想油假想油库M0MM0500需求量需求量27003001000150050060006000三三、产销不平衡的数学模型、产销不平衡的数学模型产销不平衡产销不平衡：【大M技巧的物理意义】驻地地油油库B1B1B2B3B3存存储量量A11.801.801.701.551.554000A21.601.601.501.751.751500假想油假想油库M0MM0500需求量需求量27003001000150050060006000 驻地地油油库B1B2B3存存储量量A11.801.701.554000A21.601.501.751500需求量需求量300010002000550060002700270015001500讲课提纲讲课提纲军事事案例案例一般一般模型模型产销不平不平总结实际的军事案例实际的军事案例油料运输问题；油料运输问题；运输问题的一般模型；运输问题的一般模型；产销不平衡的运输问题模型的转化；产销不平衡的运输问题模型的转化；总结总结下下节提要节提要下节提要：下节提要：运输问题的利器运输问题的利器之之表上作业法！表上作业法！如何求解如何求解 运输问题？运输问题？