[2018年必威体育精装版整理]05运输问题.pptVIP

3.1运输问题模型及有关概念 问题的提出 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。 3.1运输问题模型及有关概念 例1:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 3.1运输问题模型及有关概念 解： 产销平衡问题： 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列产销平衡表： 3.1运输问题模型及有关概念 3.1运输问题模型及有关概念 一般运输问题的提法： 单位运价表 3.1运输问题模型及有关概念 产销平衡表 3.1运输问题模型及有关概念 模型系数矩阵特征 1.共有m+n行，分别表示各产地和销地；m?n列，分别表示各决策变量（xij）； 2.每列只有两个 1，其余为 0，表示每个变量只有一个产地和一个销地被使用。 解：增加一个虚设的销地运输费用为0 总销量大于总产量的情况: 例4.3:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 解：增加一个虚设的产地运输费用为0 3.2 运输问题求解 —表上作业法 3.2 运输问题求解 —表上作业法 3.2 运输问题求解 —表上作业法 练习：某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3 、B4，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示，用最小元素法求初始运输方案。 练习：某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3 、B4，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示，试用伏格尔法求初始运输方案。 2.运输问题求解 —表上作业法 说明：： 按照上述方法所产生的一组变量的取值将满足下面条件： (1)所有的约束条件均得到满足； (2)所得的变量均为非负，且基变量的总数恰好为 m + n – 1 个； (3)当某个格添入运量后，如果其所在行的产量和所在列的销量都变为零，需要同时在运价表中划掉这一行和这一列，为了保证数字格仍然为m + n – 1 个，需要在同时划掉的这一行和这一列中的任意一个相应空格内补添一个0，这个补添0的格被当作数字格看待。 二、最优解的判别——位势法 * * * * 本章重点 第三章 运输问题 求解产销平衡运输问题的表上作业法  Min f = 6x11+4x12+6x13+6x21+5x22+5x23 s.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） 3.1运输问题模型及有关概念 x11 x12 x13 x21 x22 x23 A1 1 1 1 0 0 0 A2 0 0 0 1 1 1 B1 1 0 0 1 0 0 B2 0 1 0 0 1 0 B3 0 0 1 0 0 1 系数矩阵 销地 产地 B1 B2 … Bn 产量 A1 A2 ┇ Am c11 c12 … c1n c21 c22 … c2n ┇ ┇ ┇ ┇ cm1 cm2 … cmn a1 a2 ┇ am 销量 b1 b2