03运筹学运输规划.ppt

习题 表上作业法解决下列运输问题： 表上作业法 ⑵ 退化解： ※ 表格中一般要有(m+n-1)个数字格。但有时在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格作为基变量。一般可在划去的行和列的任意空格处加一个0即可。 ※ 利用进基变量的闭回路对解进行调整时，标有负号的最小运量（超过2个最小值）作为调整量θ，选择任意一个最小运量对应的基变量作为出基变量，并打上“×”以示作为非基变量。 表上作业法 销地 产地 B1 B2 B3 B4 产量 A1 16 A2 10 A3 22 销量 8 14 12 14 12 4 11 4 8 3 10 2 9 5 11 6 (0) (2) (9) (2) (1) (12) 8 12 4 2 8 14 如下例中σ11检验数是 0，经过调整，可得到另一个最优解。 表上作业法 销地 产地 B1 B2 B3 B4 产量 A1 7 A2 4 A3 9 销量 3 6 5 6 20 11 4 4 3 1 3 7 7 8 2 10 6 × 3 × 4 1 6 × 0 6 × × × 在x12、x22、x33、x34中任选一个变量作为基变量，例如选x34 例：用最小元素法求初始可行解 运输问题的应用 求极大值问题 目标函数求利润最大或营业额最大等问题。 运输问题的应用 求解方法： 将极大化问题转化为极小化问题。设极大化问题的运价表为C ，用一个较大的数M（M≥max{cij}）去减每一个cij得到矩阵C′，其中C′=（M－cij）≥0,将C′作为极小化问题的运价表，用表上用业法求出最优解。 运输问题的应用 例3.3 下列矩阵C是Ai（I=1，2，3）到Bj的吨公里利润,运输部门如何安排运输方案使总利润最大. 销地 产地 B1 B2 B3 产量 A1 2 5 8 9 A2 9 10 7 10 A3 6 5 4 12 销量 8 14 9 运输问题的应用 销地 产地 B1 B2 B3 产量 A1 2 5 8 9 A2 9 10 7 10 A3 6 5 4 12 销量 8 14 9 得到新的最小化运输问题，用表上作业法求解即可。 运输问题的应用 产销不平衡的运输问题 当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。 当产大于销时，即： 数学模型为： 运输问题的应用 由于总产量大于总销量，必有部分产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地Bn+1， bn+1作为一个虚设销地Bn+1的销量(即库存量)。各产地Ai到Bn+1的运价为零，即Ci,n+1=0,（i=1，…，m）。则平衡问题的数学模型为： 具体求解时,只在运价表右端增加一列Bn+1，运价为零,销量为bn+1即可 运输问题的应用 当销大于产时，即： 数学模型为： 由于总销量大于总产量,故一定有些需求地不完全满足,这时虚设一个产地Am+1，产量为： 运输问题的应用 销大于产化为平衡问题的数学模型为 ： 具体计算时，在运价表的下方增加一行Am+1，运价为零。产量为am+1即可。 运输问题的数学模型，包含有m×n个变量，（m＋n）个约束条件。由于∑ai＝ ∑bj，所以系数矩阵中线性独立的列向量的最大个数为m+n-1个，即运输问题的解中基变量的个数一般为m+n-1。 * 前一种按最小元素法求得，总运费是Z1=10×8+5×2+15×1=105，后一种方案考虑到C11与C21之间的差额是8－2=6，如果不先调运x21，到后来就有可能x11≠0，这样会使总运费增加较大，从而先调运x21，再是x22，其次是x12这时总运费Z2=10×5+15×2+5×1=85Z1。 * 当一个运输问题的产地和销地数量很多时，用位势法计算检验数比较简单。 Chapter3 运输规划( Transportation Problem ) 运输规划问题的数学模型 表上作业法 运输问题的应用 本章主要内容： 运输规划问题的数学模型 例3.1 某公司从两个产地A1、A2将物品运往三个销地B1, B2, B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ B1 B2 B3 产量 A1 6 4 6 200 A2 6 5 5 300 销量 150 150 200 运输规划问题的数学模型 解：产销平衡问题：总产量 = 总销量＝500 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表： B1 B2 B3 产量 A1 x11 x1