07 运输问题数学模型

运输问题

勤务指挥系部队管理教研室教学内容教学内容运输问题的模型及其特点求解运输问题的表上作业法产销不平衡的运输问题运输问题

（一）运输问题的数学模型讲课提纲一、军事案例实际军事案例(油料运输规划)：某团野外驻训期间要从A1、A2两个联勤加油库调送油料到B1、B2、B3三个驻训地。各油库的储存量、各驻训地的需求量以及从各油库运往各驻训地的单位油料的运价如下表所示。问题：如何调运可使总运输费用最小？

驻地油库B1B2B3存储量A1646200A2655300需求量150150200

一、军事案例

minz=6x11+4x12+6x13+6x21+5x22+5x23

s.t.x11+x12+x13=200x21+x22+x23=300x11+

x21=150x12+x22=150x13+x23=200xij≥0(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+5x23

s.t.x11+x12+x13=200x21+x22+x23=300x11+

x21=150x12+x22=150x13+x23=200xij≥0(i=1,2；j=1,2,3）

驻地油库B1B2B3存储量A1646200A2655300需求量150150200

m个产地=2n个销地=3二、运输问题的一般数学模型决策变量：约束方程：系数矩阵：基变量（秩）：产销平衡运输问题与线性规划问题的联系：

m个产地=2n个销地=3m×n个m+n个，且全部为等式约束每一个列向量中只有两个元素是1，其余元素都是0m+n-1个讲课提纲三、产销不平衡的数学模型

驻地油库B1B2B3存储量A1646200→300A2655300需求量150150200600500

三、产销不平衡的数学模型

minz=6x11+4x12+6x13+6x21+5x22+5x23

s.t.x11+x12+x13

≤300x21+x22+x23

≤300x11+

x21=150x12+x22=150x13+x23=200xij≥0(i=1,2；j=1,2,3）产销不平衡：产大于销

驻地油库B1B2B3存储量A1646300A2655300需求量150150200三、产销不平衡的数学模型

minz=6x11+4x12+6x13+6x21+5x22+5x23

s.t.x11+x12+x13

≤300x21+x22+x23

≤300x11+

x21=150x12+x22=150x13+x23=200xij≥0(i=1,2；j=1,2,3）产销不平衡：产大于销

minz=6x11+4x12+6x13+6x21+5x22+5x23

s.t.x11+x12+x13

+a1=300x21+x22+x23

+a2=300x11+

x21=150x12+x22=150x13+x23=200xij≥0(i=1,2；j=1,2,3）,a1,a2≥0a1+a2=100三、产销不平衡的数学模型产销不平衡：产大于销【添加人工变量的物理意义】

minz=6x11+4x12+6x13+6x21+5x22+5x23

+0a1+0a2s.t.x11+x12+x13

+a1=300x21+x22+x23

+a2=300x11+

x21=150x12+x22=150x13+x23=200a1+a2=100xij≥0(i=1,2；j=1,2,3）,a1,a2≥0三、产销不平衡的数学模型产销不平衡：产大于销【添加人工变量的物理意义】

minz=6x11+4x12+6x13+6x21+5x22+5x23

+0x14+0x24s.t.x11+x12+x13

+x14=300x21+x22+x23

+x24=300x11+

x21=150x12+x22=150x13+x23=200x14+x24=100xij≥0(i=1,2；j=1,2,3,4）三、产销不平衡的数学模型产销不平衡：产大于销【添加人工变量的物理意义】

驻地油库B1B2B3B4存储量A16460300A26550300需求量150150200100600600

minz=6x11+4x12+6x13+6x21+5x22+5x23

+0x14+0x24s.t.x11+x12+x13

+x14=300x21+x22+x23

+x24=300x11+

x21=150x12+x22=150x13+x23=200x14+x24=100xij≥0(i=1,2；j=1,2,3,4）三、产销不平衡的数学模型等价转换添加一个假想的需求地B4，令其需求量为产量过剩值，即产量-销量。并令各油库到B4的运费单价为0。为什么是0？只能是0吗？产销不平衡：产大于销【添加人工变量的物理意义】

驻地油库B1B2B3B4存储量A16460300A26550300需求量150150200100600600三、产销不平衡的数学模型运费单价为只能是0吗?产销不平衡：产大于销【添加人工变量的物理意义】

minz=6x11+4x12+6x13+6x21+5x22+5x23

+0x14+0x24s.t.x11+x12+x13

+x14=300x21+x22+x23

+x24=300x11+

x21=150x12+x22=150x13+x23=200x14+x24=100xij≥0(i=1,2；j=1,2,3,4）

驻地油库B1B2B3B4存储量A16460300A26550300需求量150150200100600600三、产销不平衡的数学模型

minz=6x11+4x12+6x13+6x21+5x22+5x23

s.t.x11+x12+x13=200x21+x22+x23=300x11+

x21

≤

250x12+x22

≤

150x13+x23

≤200xij≥0(i=1,2；j=1,2,3）产销不平衡：销大于产

驻地油库B1B2B3存储量A1646200A2655300需求量250150200500600三、产销不平衡的数学模型产销不平衡：销大于产【添加人工变量的物理意义】

minz=6x11+4x12+6x13+6x21+5x22+5x23

+0a1+0a2+0a3s.t.x11+x12+x13=200x21+x22+x23=300x11+

x21

+a1=250x12+x22

+a2=150x13+x23

+a3=200a1+a2+a3=100xij≥0(i=1,2；j=1,2,3）,a1,a2≥0三、产销不平衡的数学模型产销不平衡：销大于产【添加人工变量的物理意义】

minz=6x11+4x12+6x13+6x21+5x22+5x23

+0x31+0x32+0x33s.t.x11+x12+x13=200x21+x22+x23=300x11+

x21

+x31=250x12+x22

+x32=150x13+x23

+x33=200x31+x32+x33=100xij≥0(i=1,2,3；j=1,2,3）三、产销不平衡的数学模型产销不平衡：销大于产【添加人工变量的物理意义】

minz=6x11+4x12+6x13+6x21+5x22+5x23

+0x31+0x32+0x33s.t.x11+x12+x13=200x21+x22+x23=300x11+

x21

+x31=250x12+x22

+x32=150x13+x23

+x33=200x31+x32+x33=100xij≥0(i=1,2,3；j=1,2,3）

驻地油库B1B2B3存储量A1646200A2655300A3000100需求量250150200600600三、产销不平衡的数学模型等价转换添加一个假想的产地A3，令其产量为需求过剩值，即销量-产量。并令A3到各驻地的运费单价为0。产销不平衡：销大于产【添加人工变量的物理意义】

驻地油库B1B2B3存储量A1646200A2655300A3000100需求量250150200600600三、产销不平衡的数学模型产量大于销量：建立一个假想的需求地，并令其需求量为原问题中总供应量与总需求量的差值，令各供应地到该需求地的运输单价为0，由此可把原问题转化成供求平衡的运输问题。产量小于销量：建立一个假想的供应地，并令其供应量为原问题中总需求量与总供应量的差值，令从该供应地到各需求地的运输单价为0，由此可把原问题转化成供求平衡的运输问题。经验总结：三、产销不平衡的数学模型由于供不应求，经总部统筹安排决定： B1供应量可减少0~300吨， B2必须全部满足， B3供应量不得少于1500吨。试求出总运费最低的调拨方案。试试这道题：

驻地油库B1B2B3存储量A11.801.701.554000A21.601.501.751500需求量30001000200055006000≥2700≥1500需要添加剩余变量！三、产销不平衡的数学模型试试这道题：

minz=1.8x11+1.7x12+1.55x13+1.6x21+1.5x22+1.75x23

s.t.x11+x12+x13=4000x21+x22+x23=1500x11+

x21

≥2700x11+

x21

≤3000x12+

x22=1000

x13+

x23

≥1500x13+

x23

≤2000xij≥0(i=1,2；j=1,2,3）x11+

x21

–s1=2700x13+

x23

–s2=1500标准化后，系数矩阵找不到单位阵，怎么办？三、产销不平衡的数学模型等价转换添加一个假想的产地，令其需求量为产量过剩值，即产量-销量。将驻地的需