运筹学讲义 §5.2初始基本可行解 本节来介绍求(TP)的一个初始基本可行解的两种方法:西北角法和最小元素法 如§5.1所言,运输问题的求解过程并不象一般线性规划问题一样借助于单纯形表,而是借助于 运输表来实现:但其算法在理论基础、基本思想、算法步骤(包括初始基本可行解的选取、最优性的 验证、转轴)等各方面都和单纯形法是一致的 供需平衡型运输问题的运输表: ∑b C2 3, b1 b2 运输表实际上是运输问题的单纯形表 西北角法 基本思想:优先安排运输表中的西北角处的格子(即编号小的格子)对应的发点与收点之间的运 输业务. 使用条件:已知d 北 水 步骤 1.令西北角格子tm对应的变量xp的值为xm=mman,b}.将x四填入格子lp中,并圈起 2.令 ba:=ba 当ap=0时,删去第P行,并在格子lm(≠qj=12,…,m)内画x运 筹 学 讲 义 1 §5.2 初始基本可行解 本节来介绍求 (TP) 的一个初始基本可行解的两种方法：西北角法和最小元素法. 如§5.1 所言，运输问题的求解过程并不象一般线性规划问题一样借助于单纯形表，而是借助于 运输表来实现；但其算法在理论基础、基本思想、算法步骤（包括初始基本可行解的选取、最优性的 验证、转轴）等各方面都和单纯形法是一致的. 供需平衡型运输问题的运输表：   = = = n j j m i ai b 1 1 运输表实际上是运输问题的单纯形表. 一.西北角法 基本思想：优先安排运输表中的西北角处的格子（即编号小的格子）对应的发点与收点之间的运 输业务. 使用条件：已知 d . 步骤： 1.令西北角格子 pq t 对应的变量 pq x 的值为 min{ , } pq ap bq x = .将 pq x 填入格子 pq t 中，并圈起. 2.令 p p pq a := a − x ， q q pq b : = b − x . 当 a p = 0 时，删去第 p 行，并在格子 t ( j q, j 1,2, ,n) pj  =  内画  ；