《运筹学第3章：运输问题》由会员分享，可在线阅读，更多相关《运筹学第3章：运输问题（15页珍藏版）》请在金锄头文库上搜索。
1、幻灯片1管理与人文学院忻展 红1999, 4第三章运输问题一数学模型及其解法顺风而呼，声非加疾也，而闻者彰。假舆马者，非利足也，而致千里；假舟楫者,非能水也，而绝江河。君子生非异也，善假于物也。荀子劝学幻灯片23-1运输问题的一般数学模型 有m个产地生产某种物资,有“个地区需要该类物资 令al, “2, , am表示各产地产量,bl, b2, , bn表示各销地的销量,ai= bj称 为产销平衡 设罚表示产地i运往销地j的物资量,wij妬对应的単位运费,则我们有运输问题 的数学模型如下运输问题有m n个决策变量,m+n个约束条件。由于产销平衡条件，只有m+n - 1个相 互独立，因此，运输问题
2、的基变量只有m+n个幻灯片33.2运输问题的求解方法 约束条件非常有规律，技术系数非0即1 基变量的个数远小于决策变量的个数 采用表上作业法，称为位势法和踏石法 运算中涉及两个表：运费表和产销平衡表（分配表）销地 运费 产地:12n 12mWilW12W21W22.w2llWmn幻灯片43.2.1寻找初始可行解的方法1、西北角法 从X11开始分配，从西北向东南方向逐个分配X1J的分配公式12n 产量12兀11X21X12X22.xl力“ axa2 mIlX,2 x.f 销量bj方2 例 3.2.1销地 g费 产地1234产量12 3 20 11365910218 74151015销量bj331
3、2 12幻灯片5例3.2.1西北角法1234产量325X2210153312121234产量3219无3351015331212IAI.ioz H gxrHHH 2 J*锹09袒 LHU2 寸E幻灯片62、最低费用法 采用最小费用优先分配的原则，看一步f(x)=121,比 西北角法低84幻灯片73、运费差额法 采用最大差额费用(即利用每行或列中最小费用与次最小之间的差额中选最大)优先分 配的原则，看两步f(x)=98,比 最低费用法 又低了 23幻灯片83.2.2利用位势法检验分配方案是否最优 不采用单纯型法，如何获得X1J的检验数 找到原问题的基础可行解，保持互补松弛条件，求出对应对偶问题的
4、解，若该对偶问题 的解非可行，则原问题的解不是最优解；否则，达到最优解幻灯片9幻灯片10位势法的原理 为满足互补松地条件，原问题中刈被选为基变量，即XIJ 0,则要求对偶问题中 ui+vj=wij ,即该行的松弛变量为0 共有m+n 1个基变量xij ,因此可得m+u 1个等式ui+yj=wij m+n 1个等式只能解出m+n 1个ui和yj ,而一共有m+n个ui和vj ,但可令任一个ui或vj=0,从而解出其它m+n1个的值；这就是位势法 令zij=ui + vj ,其相当原问题xij的机会费用 若对所有非基变量有zij wij 0,即ui + yj wij,表明当前ui和vj是对偶问 题
5、的可行解，由互补松弛定理可知当前m+n 1个基变量刈 是最优解，否则 从zij wij 0中找最大者，对应xij就是入变量幻灯片113.2.3踏石法1 找入变量 从zij wij0中找最人者，对应xij就是入变量2、以xij为起点，寻找由原基变量构成的闭合回路 该回路只在每个拐角各有一个基变量，中间允许穿越某些基变量；因此，闭合回路 中必有偶数个变量（包括xij）,且回路中每行每列只有两个变量3、求入变量xij的最大值及新基变量的解 从xij出发，沿任一个方向对回路拐角上的基变量依此标“”和“+”，表示“”和“ + ” xij ,从而迭代后仍满足分配的平衡 标有“”的变量中最小者就是出变量xi
6、j* ,对应xij*的值就是所求入变量X1J的最大值 标有“”的变量减去xij*,标有“+”的变量加上X1J*4、用位势法求新基变量的检验数若所有zij wij 0,则达到最优，算法停止；否则返回1幻灯片12例3.2.1踏石法，以最低费用法所得初始解开始OBJ=121359sQ41OBJ=101352741答：最优解如上分配表，OEJ=98 幻灯片133.3运输问题迭代中的一些具体问题3.3.1闭合回路的画法 从入变量xij出发，遇到某个基变量则选一个方向拐角，若不能再遇到其它基变量, 则返回上一拐角，换一个方向走，采用深探法 闭合回路不一定是矩形3.3.2产销不平衡 供过于求，即aibj ,
7、增加一个虚收点Dn+1, bn+l=ai-bj,令wi,n+l=O. i=l,2,m 供小于求，即ai bj ,增加一个虚发点Wm+l, am+l= bj - ai,令wm+1 ,j=0, j= 1,2,小3.3.3关于退化问题 1、初始解退化。即所求初始基变量的个数少于m+n1。必须补足基变量的个数,否则不能正常解出m+n个ui和vj所补基变屋的值为0 ,补充的原则：（1）尽屋先选运费小的实变量：（2）补充后不能有某 个基变量独占一行一列幻灯片143.3.3关于退化问题 2、迭代过程中出现退化 闭合回路中标有“”的基变量同时有多个达到最小 变换后，有多个原基变量变为0,选运费最人者为出变量，其余保留在新的基础解 中退化较严重时，可能会出现多次迭代只有值为0的基变量在转移。此时，一要耐心， 二要正确选择出变量踏石法迭代中需注意的问题：1、错误地将分配表中基变量的解代入到运费表中2、不能正确画闭合回路3、初始解退化，未能补足基变量的个数。因此在位势法中多次令某个ui或勺为0；4、在位势法中只能令一个ui或vj为0：若不能求出全部ui和vj ,说明基变量未 选够数或未选对
