运输问题数学模型

运输问题,吴海佳勤务指挥系部队管理教研室,教学内容,教学内容,运输问题的模型及其特点求解运输问题的表上作业法产销不平衡的运输问题,运输问题（一）运输问题的数学模型,讲课提纲,一、军事案例,实际军事案例(油料运输规划)：某团野外驻训期间要从A1、A2两个联勤加油库调送油料到B1、B2、B3三个驻训地。各油库的储存量、各驻训地的需求量以及从各油库运往各驻训地的单位油料的运价如下表所示。问题：如何调运可使总运输费用最小？,一、军事案例,minz=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij0(i=1,2；j=1,2,3）,数学模型：,讲课提纲,二、运输问题的一般数学模型,运输问题（一般提法）：把某种产品从若干个产地调拨到若干个销地；已知:每个产地的供应量、如何确定一个使得总的运输费用最小的方案。,如果运输问题的总产量等于总销量，则称运输问题为产销平衡运输问题；反之，称产销不平衡运输问题。,每个销地的需求量、,各地之间的运输单价；,什么是运输问题：,二、运输问题的一般数学模型,已知有m个地点可以供应某种物资(通称产地，用i=1,m表示)，有n个地点需要该种物资(通称销地，用j=1,n表示)；m个产地的可供量(通称产量)为a1,a2,am(可通写为ai)；n个销地的需求量(通称销量)b1,b2,bn(可通写为bj)；从第i个产地到第j个销地的单位物资运价为cij。,一般数学模型：,二、运输问题的一般数学模型,设xij为从第i个产地调运给第j个销地的物资的单位数量，那么产销平衡的条件下，得到一般运输问题的数学模型：,产量约束,销量约束,目标：运费最小,一般数学模型：,二、运输问题的一般数学模型,产销平衡运输问题与一般线性规划问题的联系：,minz=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij0(i=1,2；j=1,2,3）,m个产地=2n个销地=3,二、运输问题的一般数学模型,决策变量：约束方程：系数矩阵：基变量（秩）：,产销平衡运输问题与线性规划问题的联系：,m个产地=2n个销地=3,mn个,m+n个，且全部为等式约束,每一个列向量中只有两个元素是1，其余元素都是0,m+n-1个,讲课提纲,三、产销不平衡的数学模型,三、产销不平衡的数学模型,minz=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13300 x21+x22+x23300 x11+x21=150 x12+x22=150 x13+x23=200 xij0(i=1,2；j=1,2,3）,产销不平衡：产大于销,三、产销不平衡的数学模型,minz=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13300 x21+x22+x23300 x11+x21=150 x12+x22=150 x13+x23=200 xij0(i=1,2；j=1,2,3）,产销不平衡：产大于销,三、产销不平衡的数学模型,产销不平衡：产大于销【添加人工变量的物理意义】,minz=6x11+4x12+6x13+6x21+5x22+5x23+0a1+0a2s.t.x11+x12+x13+a1=300 x21+x22+x23+a2=300 x11+x21=150 x12+x22=150 x13+x23=200a1+a2=100 xij0(i=1,2；j=1,2,3）,a1,a20,三、产销不平衡的数学模型,产销不平衡：产大于销【添加人工变量的物理意义】,minz=6x11+4x12+6x13+6x21+5x22+5x23+0 x14+0 x24s.t.x11+x12+x13+x14=300 x21+x22+x23+x24=300 x11+x21=150 x12+x22=150 x13+x23=200 x14+x24=100 xij0(i=1,2；j=1,2,3,4）,三、产销不平衡的数学模型,产销不平衡：产大于销【添加人工变量的物理意义】,minz=6x11+4x12+6x13+6x21+5x22+5x23+0 x14+0 x24s.t.x11+x12+x13+x14=300 x21+x22+x23+x24=300 x11+x21=150 x12+x22=150 x13+x23=200 x14+x24=100 xij0(i=1,2；j=1,2,3,4）,三、产销不平衡的数学模型,等价转换添加一个假想的需求地B4，令其需求量为产量过剩值，即产量-销量。并令各油库到B4的运费单价为0。,产销不平衡：产大于销【添加人工变量的物理意义】,三、产销不平衡的数学模型,运费单价为只能是0吗?,产销不平衡：产大于销【添加人工变量的物理意义】,minz=6x11+4x12+6x13+6x21+5x22+5x23+0 x14+0 x24s.t.x11+x12+x13+x14=300 x21+x22+x23+x24=300 x11+x21=150 x12+x22=150 x13+x23=200 x14+x24=100 xij0(i=1,2；j=1,2,3,4）,三、产销不平衡的数学模型,minz=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21250 x12+x22150 x13+x23200 xij0(i=1,2；j=1,2,3）,产销不平衡：销大于产,三、产销不平衡的数学模型,产销不平衡：销大于产【添加人工变量的物理意义】,minz=6x11+4x12+6x13+6x21+5x22+5x23+0a1+0a2+0a3s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21+a1=250 x12+x22+a2=150 x13+x23+a3=200a1+a2+a3=100 xij0(i=1,2；j=1,2,3）,a1,a20,三、产销不平衡的数学模型,产销不平衡：销大于产【添加人工变量的物理意义】,minz=6x11+4x12+6x13+6x21+5x22+5x23+0 x31+0 x32+0 x33s.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 xij0(i=1,2,3；j=1,2,3）,三、产销不平衡的数学模型,产销不平衡：销大于产【添加人工变量的物理意义】,minz=6x11+4x12+6x13+6x21+5x22+5x23+0 x31+0 x32+0 x33s.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 xij0(i=1,2,3；j=1,2,3）,三、产销不平衡的数学模型,等价转换添加一个假想的产地A3，令其产量为需求过剩值，即销量-产量。并令A3到各驻地的运费单价为0。,产销不平衡：销大于产【添加人工变量的物理意义】,三、产销不平衡的数学模型,产量大于销量：建立一个假想的需求地，并令其需求量为原问题中总供应量与总需求量的差值，令各供应地到该需求地的运输单价为0，由此可把原问题转化成供求平衡的运输问题。,产量小于销量：建立一个假想的供应地，并令其供应量为原问题中总需求量与总供应量的差值，令从该供应地到各需求地的运输单价为0，由此可把原问题转化成供求平衡的运输问题。,经验总结：,三、产销不平衡的数学模型,由于供不应求，经总部统筹安排决定：B1供应量可减少0300吨，B2必须全部满足，B3供应量不得少于1500吨。试求出总运费最低的调拨方案。,试试这道题：,2700,1500,需要添加剩余变量！,三、产销不平衡的数学模型,试试这道题：,minz=1.8x11+1.7x12+1.55x13+1.6x21+1.5x22+1.75x23s.t.x11+x12+x13=4000 x21+x22+x23=1500 x11+x212700 x11+x213000 x12+x22=1000 x13+x231500 x13+x232000 xij0(i=1,2；j=1,2,3）,x11+x21s1=2700,x13+x23s2=1500,标准化后，系数矩阵找不到单位阵，怎么办？,三、产销不平衡的数学模型,等价转换添加一个假想的产地，令其需求量为产量过剩值，即产量-销量。将驻地的需求分为必须满足部分和非必须满足部分。令假想油库到必须满足部分的运费单价为M。令假想油库到非必须满足部分的运费单价为0。,产销不平衡：【大M技巧的物理意义】,2700,1500,三、产销不平衡的数学模型,等价转换添加一个假想的