运翁问题模型及有关概 运输问题是一种特殊的线性规划冋题, 在求解时依然可以采用单纯形法的思路, 如图4-1所示 由于输规划系数矩阵的特殊性,如果 直接使用线性规判单纯形法求解讣算 则无法利用这些有利条件。人们在分析 运瑜规捌系数矩阵特征的基础上建立了 针对运输问题的表上作业法。 下面主要讨论基本可行解、检验数以及 基的转换等冋题。 续下页
16 运输问题是一种特殊的线性规划问题， 在求解时依然可以采用单纯形法的思路， 如图4-1所示。 由于运输规划系数矩阵的特殊性，如果 直接使用线性规划单纯形法求解计算， 则无法利用这些有利条件。人们在分析 运输规划系数矩阵特征的基础上建立了 针对运输问题的表上作业法。 下面主要讨论基本可行解、检验数以及 基的转换等问题。 续下页 1.运输问题模型及有关概念
运输问题模型及有关概 是 基本可行解 是否最优解 结束 换基 图4-1运输问题的求解思路返回
17 1.运输问题模型及有关概念 基本可行解 是否最优解 结束 换基 是 否 图4-1 运输问题的求解思路 返回
运翁问题模型及有关概 运输问题求解的有关概念 考慮产销平衡问题。由于我们关心的 量均在表43与表4-4中,因此考虑把表43 与表44合成一个表,如下表45 表4-5运输问题求解作业数据表 (下页)
18 运输问题求解的有关概念 考虑产销平衡问题，由于我们关心的 量均在表4-3与表4-4中，因此考虑把表4-3 与表4-4合成一个表, 如下表4-5 表4-5 运输问题求解作业数据表 (下页） 1.运输问题模型及有关概念
运输问题模型及有关概 销地 B1 B B 产量 产地 A n 11 21 22 A 销量 b
19 1.运输问题模型及有关概念 销地 产地 B1 B2 … Bn 产量 A1 c11 x11 c12 x12 … c1n x1n a1 A2 c21 x21 c22 x22 … c2n x2n a2 ┇ ┇ ┇ ┇ ┇ Am cm1 xm1 cm2 xm2 … cmn xmn am 销量 b1 b2 … bn
运翁问题模型及有关概 运瑜问题基变量的 特点 运输问题的基变量共有m+n-1 个,A的秩为m+n-1。 运输问题的m+n-1个变量构成基 变量的充分必要条件是不含闭回路。 重要概念:闭回路、闭回路的顶点
20 运输问题的基变量共有 m + n -1 个，A的秩为 m + n -1。 运输问题的 m + n -1 个变量构成基 变量的充分必要条件是不含闭回路。 重要概念: 闭回路、闭回路的顶点 运输问题基变量的 特点 1.运输问题模型及有关概念