运输问题数学模型.ppt

前言前两章讨论了一般线性规划问题的求解方法。但在实际工作中，往往碰到一些特殊的线性规划问题，它们的约束方程的系数具有特殊的结构，这样就有可能找到比单纯形法更为简单的求解方法。本章所讨论的运输问题就属于这样一类问题。

第一节运输问题及其数学模型运输问题是一类特殊的线性规划问题，本节介绍运输问题的数学模型及其约束方程组的系数矩阵结构的特殊性。

典型背景——物资运输调度问题一般提法为：设某种物品有:m个产地：产量：n个销地：销量：从产地到销地的单位运价是。求总运费最小的调度方案。

决策变量表示由到的物品数量。销地产地销量产量

产销平衡问题——总产量=总销量即产销不平衡问题——总产量=总销量

产销平衡问题的数学模型产量约束销量约束具有m×n个变量，m＋n个等式约束条件的线型规划，可以用单纯形法求解

mn运输问题数学模型的特点1、约束条件系数矩阵的元素等于0或1；2、约束条件系数矩阵每一列只有两个1，其余为0；每个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次。

im+j

对产销平衡问题约束条件〔不包括非负约束〕均为等式；产量之和=销量之和；约束条件的独立方程最多有m+n-1个。〔约束条件中，前m行相加之和减去后n行相加之和结果是零向量，说明m＋n个行向量线型相关。可以证明，m＋n个约束方程中的任意m＋n－1个方程都是线型无关的。非零变量的个数不大于独立的约束方程的个数，从而在运输表上填有数字的格子数不大于m+n-1个。〕