第五讲运输问题续.pptx

第五讲 ;表4-3 运输问题数据表;表4-4 运输问题变量表; m n Min f = ? ? cij xij （4-1） i=1 j=1 n s.t.? xij ≤ si i = 1,2,…,m （4-2） j=1 m ?xij ≤(=, ≥)dj j = 1,2,…,n （4-3） i=1 xij ≥ 0 (i=1,2,…,m;j=1,2,…,n)（4-4） ; m n Min f = ? ? cij xij i=1 j=1 n s.t. ? xij = si i = 1,2,…,m (4-5) j =1 m ? xij = dj j = 1,2,…,n (4-6) i =1 xij ≥ 0 (i=1,2,…,m;j=1,2,…,n) ;1.运输问题模型及有关概念;1.运输问题模型及有关概念; A的秩为 m + n -1， 基变量共有 m + n -1 个。 运输问题的 m + n -1 个变量构成基变量的充分必要条件是不含闭回路。 ;2.运输问题求解 —表上作业法 ;求检验数的方法: 闭回路法 位势法;表4-10 以非基变量 x22 为起始顶点的闭回路; 销地 产地 ;2.运输问题求解 —表上作业法; 2.位势法 位势：设对应基变量xij 的 m +n -1 个 ij ，存在ui ,vj 满足 ui+vj=cij ，i=1,2 … ,m ; j=1,2 … ,n . 称这些 ui , vj 为该基本可行解对应的位势。 注.由于有m + n 个变量（ ui , vj ）， m + n - 1 个方程（基变量个数）， 故有一个自由变量，位势不唯一。 利用位势求检验数：?ij = cij - ui - vj i = 1, … , m ; j = 1, … , n;前例，位势法求检验数： step 1 从任意基变量对应的 cij 开始,任取 ui 或 vj ，然后利用公式 cij = ui + vj 依次找出 m + n 个 ui , vj 从 c14 = 10 开始 step 2 计算非基变量的检验数 ?ij = cij - ui - vj ；填入圆圈内;; 当非基变量的检验数出现负值时，则表明当前的基本可行解不是最优解。在这种情况下，应该对基本可行解进行调整，即找到一个新的基本可行解使目标函数值下降，这一过程通常称为换基(或主元变换)过程。; （1）选负检验数中最小者 ?rk，那么 xrk 为主元，作为进基变量（上页图中 x24 ）; （2）以 xrk 为起点找一条闭回路，除 xrk 外其余顶点必须为基变量格（上页图中的回路）;; （3）为闭回路的每???个顶点标号， xrk 为 1，沿一个方向（顺时针或逆时针）依次给各顶点标号； （4）求? =Min{xij?xij对应闭回路上的偶数标号格}= xpq 那么确定 xpq为出基变量，?为调整量；; （5）对闭回路的各奇标号顶点调整为：xij + ?，对各偶标号顶点 调整为：xij - ?，特别 xpq - ? = 0， xpq变为非基变量。 重复(2)、(3)步，直到所有检验数均非负，得到最优解。;2.表上作业法;作业：; 四、产销不平衡问题的处理 在实际中遇到的运输问题常常不是产销平衡的，而是下列的一般运输问题模型 m n Min f = ? ? cij xij （4-1） i=1 j=1 n s.t.? xij ≤ si i = 1,2,…,m （4-2） j=1 m ?xij ≤(=, ≥)dj j = 1,2,…,n (4-3