1-6运输问题.ppt

1 运输问题模型及有关概念 2 运输问题的求解----表上作业法 3 运输问题应用----建模 §1运输问题模型及有关概念 问题的提出 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。 §2 运输问题求解——表上作业法 二、基本可行解的最优性检验 三、求新的基本可行解 §3.3 运输问题应用—建模 在变量个数相等的情况下，表上作业法的计算 远比单纯形法简单。解决实际问题时，人们常常尽 可能把某些线性规划的问题化为运输问题的数学模 型。下面为几个典型的例子。 对于产大于销问题，可得到下列运输问题的模型： 例3.6 某公司从两个产地A1、A2将物品运往三个销 地B1、B2、B3，各产地的产量、各销地的销量和各 产地运往各销地每件物品的运费如下表所示，问 应如何调运可使总运输费用最小？ 123 114 25 36 53 需求 22 29 11 45 A2 12 15 13 78 A1 B3 B2 B1 产量 B3 B2 B1 销 产 解： 这里，总产量为 78 + 45 = 123 ；总销量为 53 +36 + 25 = 114 。产销不平衡，增加一个虚设 的销地，得到下表 123 9 25 36 52 需求 0 22 29 11 45 A2 0 12 15 13 78 A1 B4 B3 B2 B1 产量 B4 B3 B2 B1 销 产 计算过程如下： 123 9 25 36 52 需求 0 22 29 11 45 A2 0 12 15 13 78 A1 B4 B3 B2 B1 产量 B4 B3 B2 B1 销 产 0 10 14 2 11 12 15 36 0 9 1 11 11 45 25 7 A2 A1 0 22 29 11 0 12 15 13 B4 B3 B2 B1 10 12 ui -12 0 3 1 vj 16 12 2 2、销量大于产量的情况：可得到下列运输问题的 模型： 例3.7 某公司从两个产地A1、A2将物品运往三个 销地B1、B2、B3，各产地的产量、各销地的销量 和各产地运往各销地每件物品的运费如下表，问 ：应如何调运可使总运输费用最小？ 123 154 65 36 53 需求 22 29 11 45 A2 12 15 13 78 A1 B3 B2 B1 产量 B3 B2 B1 销 产 解: 这里，总产量小于总销量，产销不平衡，增加 一个虚设的产地，得到下表 154 65 36 53 需求 0 0 0 31 A3 22 29 11 45 A2 12 15 13 78 A1 B3 B2 B1 产量 B3 B2 B1 销 产 154 65 36 53 需求 0 0 0 31 A3 22 29 11 45 A2 12 15 13 78 A1 B3 B2 B1 产量 B3 B2 B1 销 产 12 15 11 0 11 1 0 31 2 10 14 15 5 11 45 65 8 0 0 0 A3 A2 A1 22 29 11 12 15 13 12 1 10 3 0 - 3 16 12 2 3 例3.8 有 A1、A2、A3 三个生产某种物资的产地， 五个地区 B1、B2、B3、B4、B5 对这种物资有需求。 现要将这种物资从三个产地运往五个需求地区， 各产地的产量、各需求地区的需要量和各产地运 往各地区每单位物资的运费如下表所，其中 B2 地 区的115个单位必须满足。问：应如何调运可使 运输费用最小？ 运输费用及产量、需求量表 280 300 70 30 60 115 25 需求 130 25 55 40 35 30 A3 100 30 30 15 40 20 A2 50 40 20 20 15 10 A1 产量 B5 B4 B3 B2 B1 销地 产地 解：由于产量小于需求量，因此设一虚设产地 A4 , 它的产量为需求量与产量的差 20，与这一项有关的 运输费用一般为零。因为B2 地区的115个单位必须 满足，即不能有物资从 A4 运往 B2 地区，于是取相 应的费用为M（M是一个充分大的正数），以保证 在求最小运输费用的前提下，该变量的值为零。 可以建立如下产销平衡的运输费用表 300 70 30 60 115 25 需求 20 0 0 0 M 0 A4 130 25 55 40 35 30 A3 100 30 30 15 40 20 A2 50 40 20 20 15 10 A1 产量 B5 B4 B3 B2 B1 销地 产地