『无忧PPT』PPT免费下载,PPT素材,PPT背景PPT图片PPT模板PPT制作免费下载的门户网站Rss 2.0无忧PPT-PPT门户网站

PPT模板下载排行榜(New) 无忧PPT原创PPT模板 无忧PPT官方微博 精品PPT模板

运筹学-北京邮电大学-3PPT资源下载

::推荐PPT模板::
  • ::运筹学-北京邮电大学-3下载地址::
  • 下载地址1  
  • 上传作者:chinappt
  • 来源:运筹学-北京邮电大学|PowerPoint资源|免费下载|PPT模板|PPT资源|商务|PowerPoint工具|business|PPTresources
  • 运筹学-北京邮电大学-3简介
  • 运筹学-北京邮电大学-3

    第三章  运输问题 — 数学模型及其解法
           顺风而呼,声非加疾也,而闻者彰。假舆马者,非利足也,而致千里;假舟楫者,非能水也,而绝江河。君子生非异也,善假于物也。          荀子《劝学》
    3.1 运输问题的一般数学模型
    有m个产地生产某种物资,有n个地区需要该类物资
    令a1, a2, …, am表示各产地产量, b1, b2, …, bn表示各销地的销量,ai=bj 称为产销平衡
    设xij表示产地 i 运往销地 j 的物资量,wij表示对应的单位运费,则我们有运输问题的数学模型如下:
    3.2 运输问题的求解方法
    约束条件非常有规律,技术系数非 0 即 1
    基变量的个数远小于决策变量的个数
    采用表上作业法,称为位势法和踏石法
    运算中涉及两个表:运费表和产销平衡表(分配表)
        3.2.1 寻找初始可行解的方法
         1、西北角法
    从 x11开始分配,从西北向东南方向逐个分配
    xij 的分配公式
        例3.2.1 西北角法
        2、最低费用法
    采用最小费用优先分配的原则,看一步
        3、运费差额法
    采用最大差额费用(即利用每行或列中最小费用与次最小之间的差额中选最大)优先分配的原则,看两步
        3.2.2 利用位势法检验分配方案是否最优
    不采用单纯型法,如何获得xij的检验数
    找到原问题的基础可行解,保持互补松弛条件,求出对应对偶问题的解,若该对偶问题的解非可行,则原问题的解不是最优解;否则,达到最优解

        位势法的原理
    为满足互补松弛条件,原问题中xij被选为基变量,即xij0,则要求对偶问题中ui+vj=wij,即该行的松弛变量为0
    共有m+n1个基变量xij ,因此可得m+n1个等式 ui+vj=wij
    m+n1个等式只能解出 m+n1个 ui 和 vj ,而一共有m+n个 ui 和 vj ,但可令任一个ui 或 vj =0,从而解出其它 m+n1个的值;这就是位势法
    令 zij= ui + vj ,其相当原问题xij的机会费用
    若对所有非基变量有 zij  wij  0,即 ui + vj  wij,表明当前ui 和 vj 是对偶问题的可行解,由互补松弛定理可知当前m+n1个基变量xij 是最优解,否则
    从 zij  wij > 0 中找最大者,对应 xij 就是入变量
        3.2.3 踏石法
    1、找入变量
    从 zij  wij > 0 中找最大者,对应 xij 就是入变量
    2、以 xij 为起点,寻找由原基变量构成的闭合回路
    该回路只在每个拐角各有一个基变量,中间允许穿越某些基变量;因此,闭合回路中必有偶数个变量(包括 xij ),且回路中每行每列只有两个变量
    3、求入变量 xij 的最大值及新基变量的解
    从 xij出发,沿任一个方向对回路拐角上的基变量依此标“”和“+”,表示“”和“+” xij ,从而迭代后仍满足分配的平衡
    标有“”的变量中最小者就是出变量xij* ,对应 xij*的值就是所求入变量 xij 的最大值
    标有“”的变量减去 xij*,标有“+”的变量加上 xij*
    4、用位势法求新基变量的检验数
    若所有 zij  wij  0,则达到最优,算法停止;否则返回 1
        例3.2.1 踏石法,以最低费用法所得初始解开始
    3.3 运输问题迭代中的一些具体问题
         3.3.1 闭合回路的画法
    从入变量xij出发,遇到某个基变量则选一个方向拐角,若不能再遇到其它基变量,则返回上一拐角,换一个方向走,采用深探法
    闭合回路不一定是矩形
         3.3.2 产销不平衡
    供过于求,即 ai > bj ,增加一个虚收点Dn+1,bn+1= ai - bj , 令 wi,n+1=0, i=1,2,…,m
    供小于求,即 ai < bj ,增加一个虚发点Wm+1,am+1= bj - ai , 令 wm+1,j=0, j=1,2,…,n
         3.3.3 关于退化问题
    1、初始解退化。即所求初始基变量的个数少于 m+n1。必须补足基变量的个数,否则不能正常解出 m+n个 ui 和  vj
    所补基变量的值为 0 ,补充的原则:(1)尽量先选运费小的实变量;(2)补充后不能有某个基变量独占一行一列
         3.3.3 关于退化问题
    2、迭代过程中出现退化
    闭合回路中标有“”的基变量同时有多个达到最小
    变换后,有多个原基变量变为 0,选运费最大者为出变量,其余保留在新的基础解中
    退化较严重时,可能会出现多次迭代只有值为 0 的基变量在转移。此时,一要耐心,二要正确选择出变量

  • 最热经济下载

    没有任何图片PPT下载资源
     
    网友评论:(只显示最新10条。评论内容只代表网友观点,与本站立场无关!) 【发表评论
    PPT搜索