第四章 运输问题Transportation Problems 数学模型及其解法1第一节 运输问题的数学模型一、问题的提出例 1 产销平衡表2二、运输问题的一般数学模型 有 m个产地生产 某 种物资，有 n个地区需要该类物资； 设 xij表示产地 Ai 运往销地 B j 的物资量，cij表示对应的单位运费，则我们有运输问题的数学模型如下： 令 a1, a2, , am表示各产地产量，b1, b2, , bn表示各销地的销量；一般满足产销平衡： ai=bj 3三、约束系数矩阵的特征1. 系数矩阵的形式在例 1中，运输问题的系数矩阵 A为：2. 系数矩阵的特征特征 1： 矩阵的行与平衡表行、列一一对应4一般情况下 ,运输问题的决策变量 xij的 系数列向量为 :特征 2： 矩阵的列向量只有两个元素为 15特征 3： r(A)=m + n 167四、闭回路1. 概念 例 21) 数字格 2) 空格 3) 闭回路闭回路： 以某空格为起点，用水平或垂直线向前划，当碰到某恰当的数字格后，转 900继续前进，直到回到起始空格为止。8 9 10
