运输问题数学模型

运输问题 吴海佳勤务指挥系部队管理教研室 教学内容 教学内容 运输问题的模型及其特点求解运输问题的表上作业法产销不平衡的运输问题 运输问题 一 运输问题的数学模型 讲课提纲 一 军事案例 实际军事案例 油料运输规划 某团野外驻训期间要从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 xij 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 5x23s 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 m个产地 2n个销地 3 二 运输问题的一般数学模型 决策变量 约束方程 系数矩阵 基变量 秩 产销平衡运输问题与线性规划问题的联系 m个产地 2n个销地 3 m n个 m n个 且全部为等式约束 每一个列向量中只有两个元素是1 其余元素都是0 m n 1个 讲课提纲 三 产销不平衡的数学模型 三 产销不平衡的数学模型 minz 6x11 4x12 6x13 6x21 5x22 5x23s 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 产销不平衡 产大于销 三 产销不平衡的数学模型 minz 6x11 4x12 6x13 6x21 5x22 5x23s 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 产销不平衡 产大于销 三 产销不平衡的数学模型 产销不平衡 产大于销 添加人工变量的物理意义 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 xij 0 i 1 2 j 1 2 3 a1 a2 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 xij 0 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 xij 0 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 xij 0 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 x21 250 x12 x22 150 x13 x23 200 xij 0 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 xij 0 i 1 2 j 1 2 3 a1 a2 0 三 产销不平衡的数学模型 产销不平衡 销大于产 添加人工变量的物理意义 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 xij 0 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 xij 0 i 1 2 3 j 1 2 3 三 产销不平衡的数学模型 等价转换添加一个假想的产地A3 令其产量为需求过剩值 即销量 产量 并令A3到各驻地的运费单价为0 产销不平衡 销大于产 添加人工变量的物理意义 三 产销不平衡的数学模型 产量大于销量 建立一个假想的需求地 并令其需求量为原问题中总供应量与总需求量的差值 令各供应地到该需求地的运输单价为0 由此可把原问题转化成供求平衡的运输问题 产量小于销量 建立一个假想的供应地 并令其供应量为原问题中总需求量与总供应量的差值 令从该供应地到各需求地的运输单价为0 由此可把原问题转化成供求平衡的运输问题 经验总结 三 产销不平衡的数学模型 由于供不应求 经总部统筹安排决定 B1供应量可减少0 300吨 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 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技巧的物理意义 2700 1500 三 产销不平衡的数学模型 等价转换添加