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

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

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

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

    第四章   整数规划
       整数规划的难度远大于一般线性规划
    4.1 整数规划简介
    要求所有 xj 的解为整数,称为纯整数规划
    要求部分 xj 的解为整数,称为混合整数规划
    对应没有整数解要求的线性规划称之为松弛问题
    整数规划的解是可数个的,最优解不一定发生在极点
    整数规划的最优解不会优于其松弛问题的最优解
    4.2 整数规划的分枝定解法
        4.2.1 思路与解题步骤
    只解松弛问题
    1、在全部可行性域上解松弛问题
    若松弛问题最优解为整数解,则其也是整数规划的最优解
    2、分枝过程
    若松弛问题最优解中某个 xk=bk 不是整数,令  bk  为 bk 的整数部分
    构造两个新的约束条件 xk  bk  和 xk  bk +1,分别加于原松弛问题,形成两个新的整数规划
    3、求解分枝的松弛问题 — 定界过程
    设两个分枝的松弛问题分别为问题 1 和问题 2 ,它们的最优解有如下情况
    表4.2.1 分枝问题解可能出现的情况
        4.2.2  分枝定界法举例
        例4.1.1
        表4.2.3 分枝问题的松弛解
    4.6 任务分配问题
    例4.6.1  有四个熟练工人,他们都是多面手,有四项任务要他们完成。若规定每人必须完成且只完成一项任务,而每人完成每项任务的工时耗费如表4.6.1,问如何分配任务使完成四项任务的总工时耗费最少?
        任务分配问题的数学模型
    模型中:xij 为第 i 个工人分配去做第 j 项任务;
                    aij 为第 i 个工人为完成第 j 项任务时的工时消耗;
                    {aij}mm 称为效率矩阵
        4.6.1 清华算法
    定理 1  如果从效率矩阵{aij}mm中每行元素分别减去一个常数 ui,从每列元素分别减去一个常数 vj ,所得新的效率矩阵{bij}mm的任务分配问题的最优解等价于原问题的最优解。
         证明:略
    定理 2  若方阵中一部分元素为零,一部分元素非零,则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。
         证明:略
         清华算法的基本思路:
    根据定理 1 变换效率矩阵,使矩阵中有足够多的零。若矩阵中存在 m 个不同行不同列的零,就找到了最优解
    若覆盖变换后的效率矩阵零元素的直线少于m 条,就尚未找到最优解,设法进一步变换矩阵,增加新的零
        清华算法的步骤:例4.6.1
    第一步:变换效率矩阵,使每行每列至少有一个零
    行变换:找出每行最小元素,从该行各元素中减去之
    列变换:找出每列最小元素,从该列各元素中减去之
        清华算法的步骤:例4.6.1
    2、逐列检查,若该列只有一个未标记的零,对其加( )标记,将( )标记元素同行同列上其它的零打上*标记。若该列有二个以上未标记的零,暂不标记,转下一列检查,直到所有列检查完;
        清华算法的步骤:例4.6.1
        清华算法的步骤:例4.6.1
        清华算法的步骤:例4.6.1
         4.6.2 关于清华算法的适用条件
    要求所有aij 0
    若某些 aij <0 ,则利用定理 1 进行变换,使所有 bij  0
    目标函数为min型
    对于max型目标函数,将效率矩阵中所有 aij 反号,则等效于求min型问题;再利用定理 1 进行变换,使所有 bij  0,则可采用清华算法
    线性规划有关的英文词汇
    Operational/operations research   运筹学
    Linear programming  线性规划      Feasible domain  可行域
    Convex set  凸集       Basic feasible solutions  基础可行解
    Simplex algorithm  单纯型法       Pivot  主元      Pivoting  主元变换
    Revised, dual simplex algorithm  修正、对偶单纯型法
    Relative cost  相对成本(机会成本)       Shadow price   影子价格
    Slack, Surplus, Artificial variable  松弛,剩余,人工变量
    Unbounded, Infeasible, Degenerate solution  无界解, 无可行解, 退化解
    Duality  对偶性        Primal, dual problem  原问题,对偶问题
    Complementary slackness  互补松弛    Sensitivity analysis  灵敏度分析
    Ttransportation problem  运输问题
    Assignment problem  任务分配(指派) 问题
    Bipartite matching  两部图匹配        Hungarian method  匈牙利算法

  • 最热经济下载

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