运翁问题模型及有关概 运输问题是一种特殊的线性规划 问题。在求解时依然可以采用单纯形法 的思路,如图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.运输问题模型及有关概念