运筹学学习(自制笔记)第3章 运输问题VIP免费

第 3 章 运输问题3.1 标准运输问题及模型3.1.1 标准运输问题：某种物资有 m 个产地 Ai（i=1,2,…,m）,产量分别为 ai，另有 n 个销地 Bj（j=1,2,…,n），销量（需求量）分别为bj，现在需要把这种物资从各个产地运送到各个销地，已知从 Ai到Bj的单位运价(或运距)为 cij，假定产量总数等于销量总数，即,问就如何组织调运，才能使总运费（或总运输量）最省?3.1.2 标准运输问题的有关信息表单位运价 销地或运距产地B1B2…Bn产量A1c11c 12…c 1na1A2c 21c 22…c 2na2………………Amc m1c m2…c mnamb1b2…bn3.1.3 标准运输问题的数学模型 设 xij 为从产地 Ai 运到销地 Bj 的物资数量（i=1,2,…,m；j=1,2,…,n），由于从 Ai运出的物资总量等于 Ai的产量，运到的物资总量等于的销量，得模型如下： minZ= s.t. 且有 即满足产销平衡条件，故此模型描述的是产销平衡运输问题。3.1.4 标准运输问题的特点⑴ 平衡条件下的运输问题必有最优解此问题是一个有 m×n 个变量，m+n 个等型约束条件的线性规划最小 化 问 题 ， 由 于 目 标 函 数 不 可 能 为 负 ， 故 有 下 界 存 在 ， 而是问题的一组可行解，因此一定有最优解。既是线性规划问题，无疑可用单纯形法求解，但其数学模型自身结构有其特殊性，可以利用更简便的表上作业法求解。⑵ 标准运输问题约束方程组的系数矩阵运输问题是一个具有 m×n 个变量，m+n 个等型约束条件的线性规划问题，问题的约束方程组的系数矩阵 A 是一个只有 0 和 1 两个数值的稀疏矩阵，对应的列只有第 i 行和第 m+j 行为 1，其余各行皆为 0。⑶ 标准运输问题的基变量总数为 m+n-1。可以证明系数矩阵 A 和增广矩阵 A′的秩为 m+n-1。增广矩阵 A′的前 m 行相加之和减后 n 行相加之和等于 0，说明m+n 个行向量线性相关，A′和 A 的秩都小于 m+n；另外，可以在 A′中找出一个行列式的值不为 0 的 m+n-1 阶方阵 D(取第二行至第 n 行的前 n 列及所在的列，其中 i=2，3，…m,得到一个副对角线上为两单位矩阵，上方为零矩阵的矩阵，显然，此矩阵满秩)，所以,A′和 A 的秩为 m+n-1。 ⑷m+n-1 个变量构成基变量的充要条件是它们不构成回路。 运输模型中能排列成｛｝的变量组称为一个闭回路，其中 i1,i2,…is互不相同，j1,j2,…js也互不相同，出现在组中的变量称为回路的顶点。 由于所对应的列向量仅有第 i 行和 m...