Min f =cyxi"is.tx=dj = l...., n"i- 1....m=SiX1Xi ≥ 0,i = 1....m,ji = 1,...,nZs,=2d,说明：当时，称其为产销平衡的运输问题i=lj=l否则产销不平衡。2025/4/5
2025/4/5 7 j n x i m x s i m st x d j n Min f c x i j i n j i j j m i i j m i n j i j i j 1,., 0, 1,. , 1,. . 1,., 1 1 1 1 = = = = = = = = = = = 说明：当 时，称其为产销平衡的运输问题， 否则产销不平衡。 = = = n j j m i si d 1 1
说明：从上述模型可以看出：（1）这是一个线性规划的模型；（2）变量有m×n个；（3）约束条件有m+n个；（4）系数矩阵非常稀疏；系数矩阵的秩一般为（m+n-1)而非m+n若直接用单纯形法求解，显然单纯形表比较庞大，于是在单纯形法的基础上创建了表上作业法求解运输问题这一特殊的线性规划问题2025/4/5
2025/4/5 8 说明：从上述模型可以看出： （1）这是一个线性规划的模型； （2）变量有m×n个； （3）约束条件有 m+n 个； （4）系数矩阵非常稀疏；系数矩阵的秩一般为（m+n-1), 而非m+n 。 若直接用单纯形法求解，显然单纯形表比较庞大，于是在 单纯形法的基础上创建了表上作业法求解运输问题这一特 殊的线性规划问题
82运输问题的表上作业法从第一节的运输问题的数学模型可知，运输问题实际上也属于线性规划，但由于运输问题的特殊性（变量个数较多系数矩阵的特点），如果用单纯形表格方法送代，计算量很大。今天介绍的“表上作业法”，是针对运输问题的特殊求解方法，实质还是单纯形法，但减少了计算量。表上作业法适用于求解产销平衡的运输问题。（产销不平衡的问题可转化为平衡问题）2025/4/5
2025/4/5 9 从第一节的运输问题的数学模型可知，运输问题实际上 也属于线性规划，但由于运输问题的特殊性（变量个数较多， 系数矩阵的特点），如果用单纯形表格方法迭代，计算量很 大。今天介绍的 “表上作业法” ，是针对运输问题的特殊求解 方法，实质还是单纯形法，但减少了计算量。 表上作业法适用于求解产销平衡的运输问题。（产销不平 衡的问题可转化为平衡问题） §2 运输问题的表上作业法
表上作业法一般步骤1、找出初始基本可行解；2、检查各非基变量的检验数，是否达到最优性条件，若达到，则得最优解；否则转第三步；3、确定出基变量、进基变量，用闭回路方法进行调整，得到新的基可行解；4、重复第二、第三步，直至得到最优解。销地产量B1B2B3B4运费单价(吨）产地A1311310792A2184A37410593656销量 (吨）2025/4/510
2025/4/5 10 表上作业法一般步骤： 1、找出初始基本可行解； 2、检查各非基变量的检验数，是否达到最优性条件，若达到，则得最优 解；否则 转第三步； 3、确定出基变量、进基变量，用闭回路方法进行调整，得到新的基可 行解； 4、重复第二、第三步，直至得到最优解。 销地 运费单价 产地 B1 B2 B3 B4 产量 （吨） A1 3 11 3 10 7 A2 1 9 2 8 4 A3 7 4 10 5 9 销量（吨） 3 6 5 6
确定初始基本可行解：对于有m个产地n个销地的产销平衡问题，有m个关于产量的约束方程和n个关于销量的约束方程。表面上，共有m+n个约束方程。但由于产销平衡，其模型最多只有m+n-1个独立的约束方程，所以运输问题实际上有m+n-1个基变量。在mxn的产销平衡表上给出m+n-1个数字格，其相对应的调运量的值即为基变量的值。那么在该例中，应有3+4-1=6个基变量。2025/4/511
2025/4/5 11 一、确定初始基本可行解： 对于有m个产地n个销地的产销平衡问题，有m个关于产量 的约束方程和n个关于销量的约束方程。表面上，共有m+n个 约束方程。 但由于产销平衡，其模型最多只有m+n-1个独立的约束方 程，所以运输问题实际上有m+n-1个基变量。在m×n的产销 平衡表上给出m+n-1个数字格，其相对应的调运量的值即为 基变量的值。 那么在该例中，应有 3+4-1=6个基变量