运筹学教程第4章课件.ppt

第四章 运输问题 运输问题与有关概念 运输问题的求解—表上作业法 运输问题应用—建模 1.运输问题模型及有关概念 问题的提出 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。 1.运输问题模型及有关概念 例4.1:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 1.运输问题模型及有关概念 解： 产销平衡问题： 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表： 1.运输问题模型及有关概念 1.运输问题模型及有关概念 模型系数矩阵特征 1.共有m+n行，分别表示各产地和销地；m?n列，分别表示各决策变量； 2.每列只有两个 1，其余为 0，分别表示只有一个产地和一个销地被使用。 1.运输问题模型及有关概念 一般运输问题的线性规划模型及求解思路 一般运输问题的提法： 假设 A1, A2,…,Am 表示某物资的m个产地；B1,B2,…,Bn 表示某物资的n个销地；si表示产地 Ai 的产量；dj 表示销地 Bj 的销量；cij 表示把物资从产地 Ai 运往销地 Bj 的单位运价（表4-3）。如果 s1 + s2 + … + sm = d1 + d2 + … + dn 则称该运输问题为产销平衡问题；否则，称产销不平衡。首先讨论产销平衡问题。 1.运输问题模型及有关概念 表4-3 运输问题数据表 1.运输问题模型及有关概念 表4-4 运输问题变量表 1.运输问题模型及有关概念 在产销平衡问题中，仔细观察式（4-2）、 （4-3）分别变为（4-5）、（4-6），约束条件成 为等式。 在实际问题建模时，还会出现如下一 些变化： （1）有时目标函数求最大，如求利润最 大或营业额最大等； （2）当某些运输线路上的能力有限制时， 模型中可直接加入（等式或不等式） 约束； 1.运输问题模型及有关概念 (3)产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，这相当于在式（4-2）每一式中加上 1 个松弛变量，共 m 个；当产量大于销量时可加入一个虚设的销地去消化多余的物资，这相当于在式（4-3）每一式中加上 1 个松弛变量，共 n 个。 1.运输问题模型及有关概念 运输问题是一种特殊的线性规划问题，在求解时依然可以采用单纯形法的思路，如图4-1所示。由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。在这里需要讨论基本可行解、检验数以及基的转换等问题。 1.运输问题模型及有关概念 1.运输问题模型及有关概念 运输问题求解的有关概念 考虑产销平衡问题，由于我们关心的量均在表4-3与表4-4中，因此考虑把表4-3与表4-4合成一个表, 如下表4-5? 表4-5 运输问题求解作业数据表 (下页） 1.运输问题模型及有关概念 1.运输问题模型及有关概念 运输问题的基变量共有 m + n -1 个，A的秩为 m + n -1。 运输问题的 m + n -1 个变量构成基变量的充分必要条件是不含闭回路。 重要概念: 闭回路、闭回路的顶点 1.运输问题模型及有关概念 定义4.1 在表4-5的决策变量格中，凡是能够排列成下列形式的 xab ,xac ,xdc ,xde ,…,xst ,xsb (4-7) 或 xab ,xcb ,xcd ,xed ,…,xst ,xat (4-8) 其中，a,d,…,s 各不相同；b,c,…,t 各不相同，我们称之为变量集合的一个闭回路，并将式（4-7）、式（4-8）中的变量称为这个闭回路的顶点。 1.运输问题模型及有关概念 例如，x13, x16, x36, x34, x24, x23 ； x23, x53, x55, x45, x41, x21 ； x11, x14, x34, x31等都是闭回路。 若把闭回路的各变量格看作节点， 在表中可以画出如下形式的闭回路： 1.运