3-1运输问题模型与性质.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 运输问题变量表 ?3.1 运输问题模型与性质 一、运输问题的数学模型 1、 运输问题的一般提法： 某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？ 2、运输问题的数学模型 设xij为从产地Ai运往销地Bj的物资数量（i=1，…m；j=1，…n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足： 运输问题的数学模型 三、运输问题的求解方法 1、单纯形法（为什麽？） 2、表上作业法 由于问题的特殊形式而采用的更简洁、更方便的方法 可以证明：m+n个约束方程中的任意m+n-1个都是线性无关的。 定义3.1 凡是能排成 (3-4) 或 (3-5) 形式的变量集合称为一个闭回路,并称式中变量为该闭回路的顶点；其中 互不相同, 互不相同。 3. m+n-1个变量构成基变量的充要条件是它们不构成闭回路。 X11 X13 X21 X24 X33 ? B1 B2 B3 B4 A1 X12 X14 A2 X22 X23 A3 X31 X32 X34 例3-1 设m=3，n=4，决策变量xij表示从产地Ai到销地Bj的调运量，列表如下，给出闭回路 在表中的表示法——用折线连接起来的顶点变量。 练习3-1 请给出闭回路 和 在表中的表示法。 X11 X13 X21 X24 X33 ? B1 B2 B3 B4 A1 X12 X14 A2 X22 X23 A3 X31 X32 X34 练习3-2 下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？为什麽？ （