精华内容
下载资源
问答
  • 可以用分支定界法求解出一维下料问题。有利于解决NP问题。
  • 针对一维下料优化问题,根据企业的实际生产情况,考虑能够满足和不满足生产两种情况,建立一个新的优化模型,并使用蜂群遗传算法求解方案。用各零件长度的一个排列作为一个染色体,每个零件的长度作为染色体的一个...
  • 基于改进文化算法一维下料问题,吴迪,张剑飞,一维优化下料问题是工程应用中普遍存在的一种组合优化问题,属于NP完备问题。针对一维下料问题,本文将混沌算法,博弈论和遗传算�
  • 中国知网收费材料,很有用,采用伪C编写的代码说明,很明了
  • 根据目前对优化下料问题新特性的研究,指出优化下料问题呈现多目标和复杂约束状态,建立了以原料消耗最少和不同交货期的惩罚最小为目标函数的优化下料问题的数学模型。利用多目标智能优化算法求解模型,并结合算例...
  • 部分主要讲cutting stock问题的定义,以及如何用列生成算法解决cutting stock问题。 . cutting stock问题的定义 问题描述:有批钢管数量为 N,长度都为 L;假设m个顾客,来钢厂订单,每位顾客需要长度为...

    最近在调研大规模的cutting stock问题,发现了分支定价(price and bound) 方法。但是网上关于分支定价(price and bound)的资料很少,对自己的学习过程做个记录,希望能帮助到有需要的小伙伴。

    第一部分主要讲cutting stock问题的定义,以及如何用列生成算法解决cutting stock问题。

    一. cutting stock问题的定义

    问题描述:有一批钢管数量为 N,长度都为 L;假设m个顾客,来钢厂下订单,每位顾客需要长度为 Li的钢管 Di根。

    优化目标: 如何切割钢管使得既能满足客户的需求又使得的消耗的钢管数量最少?

    整数规划模型如下

    二. 列生成算法

    列生成算法的主要流程如下:

    step1:给出模型的初始解,其解代表可行列

    step2: 求解主问题(RMP)并获取乘子π

    step3: 求解子问题 ,并计算检验数,如果小于0,向限制主问题中添加一列求解,返回step2

    step4: 若检验数大于等于零,停止算法,输出最优解

    初始原问题时一个集合覆盖模型,一开始列出所有的列是不现实的,因此我们一开始只能从有限列出发,不断添加列,直到包含有限列的模型(限制主问题)与原问题模型具有相同的线性最优解;为了使用列生成,必须将原问题松弛为线性模型,因为列生成只能对线性模型使用。

    python代码如下:

    import gurobipy as grb
    from gurobipy import GRB
    import numpy as np
    
    # column就是pattern
    def master_problem(column, vtype, demand_number_array):
        m = grb.Model()
        x = m.addMVar(shape=column.shape[1], lb=0, vtype=vtype)
        m.addConstr(lhs=column @ x >= demand_number_array)
        m.setObjective(x.sum(), GRB.MINIMIZE)
        m.optimize()
    
        if vtype == GRB.CONTINUOUS:
            return np.array(m.getAttr('Pi', m.getConstrs()))
        else:
            return m.objVal, np.array(m.getAttr('X'))
    
    # 将主问题松弛成线性问题
    def restricted_lp_master_problem(column,demand_number_array):
        return master_problem(column, GRB.CONTINUOUS,demand_number_array)
    
    # 找到所有的cut pattern后,求解整数优化主问题。
    def restricted_ip_master_problem(column,demand_number_array):
        return master_problem(column, GRB.INTEGER,demand_number_array)
    
    # 子問題求解,寻找pattern
    def knapsack_subproblem(kk,demand_width_array,demand_number_array,roll_width):
        m = grb.Model()
        x = m.addMVar(shape=kk.shape[0], lb=0, vtype=GRB.INTEGER)  # 整数规划
        m.addConstr(lhs=demand_width_array @ x <= roll_width)
        m.setObjective(1 - kk @ x, GRB.MINIMIZE)
        m.optimize()
    
        flag_new_column = m.objVal < 0   # 判别数
        if flag_new_column:
            new_column = m.getAttr('X')  # 子问题求解,找到新的列
        else:
            new_column = None
        return flag_new_column, new_column
    
    def test(roll_width,demand_width_array,demand_number_array):
        # 初始定义最简单的pattern
        initial_cut_pattern = np.diag(np.floor(roll_width / demand_width_array))
        flag_new_cut_pattern = True
        new_cut_pattern = None
        cut_pattern = initial_cut_pattern  # 最近的pattern
        while flag_new_cut_pattern:
            if new_cut_pattern:
                cut_pattern = np.column_stack((cut_pattern, new_cut_pattern))    # 最新的pattern。按列合并
            kk = restricted_lp_master_problem(cut_pattern, demand_number_array)  # 将主问题松弛成线性问题
            flag_new_cut_pattern, new_cut_pattern = knapsack_subproblem(kk, demand_width_array, demand_number_array, roll_width)
        # 找到所有的cut pattern后,求解整数优化主问题。
        minimal_stock, optimal_number = restricted_ip_master_problem(cut_pattern, demand_number_array)
        print(f'demand_width_array: {demand_width_array}')
        print(f'demand_number_array: {demand_number_array}')
        print('result:')
        print(f'minimal_stock: {minimal_stock}')
    
    # 生成测试数据
    def generate_data(roll_width,customer_num):
        roll_width = np.array(roll_width)
        demand_width_array = np.random.randint(1, 3, size=(customer_num))
        demand_number_array = np.random.randint(50, 200, size=(customer_num))
        return roll_width, demand_width_array, demand_number_array
    
    # print(generate_data(120,100))
    roll_width, demand_width_array, demand_number_array = generate_data(roll_width=120,customer_num=2)
    test(roll_width, demand_width_array, demand_number_array)

     

    展开全文
  • 维下料问题是说,在固定宽度的板材上切割下一些要求大小的目标物,使得消耗的板材长度最小。对于这个问题,可以把他抽象为这样的数学模型:每个目标物设置个id号,这样组id号就构成了个切割顺序。显然,在...
     最近做了这方面的事情。把自己的一些经验跟大家分享一下。
    遗传算法是一种优化算法,所以可以应用在很多地方。尤其是对于比较复杂或者难于求出精确解的问题,该方法给出了比较好的解决方案。
    二维下料问题是说,在固定宽度的板材上切割下一些要求大小的目标物,使得消耗的板材长度最小。
    对于这个问题,可以把他抽象为这样的数学模型:每一个目标物设置一个id号,这样一组id号就构成了一个切割顺序。显然,在这样的模型下,切割顺序和切割方式对于最终的结果有比较大的影响。
    略去切割方式,本文在一种切割方式下,集中对切割顺序作一个小小的分析。
    我选择的切割方法是:将进入的目标物从下到上,从左到右地在板材上找空闲位置,找到后将板材上的该区域标记;重复上述过程直到没有目标物进入为止。
    在上述切割方式下,我的目标转化为找到一个合适的序列使得切割后使用的板材长度尽可能地小。
    对于这个序列,我使用了遗传算法。遗传算法控制参数很多,尤其是初始种群的选取对于该算法有较大影响。我选择了从大到小排列目标物,然后象挤牙膏那样生成一组新的序列。用这样的序列进行进化。基本上对于较小数目的目标物,很快能给出次优序列。从本人实验的结果看,优化率((直接切割所需长度-优化后所需长度)/直接切割所需长度)平均为11%,有时甚至高达28%。可见,优化和不优化还是有很大差别的。
    最近就做了遗传算法这方面的一点事情。希望对您能有用。
    展开全文
  • 研究一维单一原料下料问题,将最优化模型和EPFF算法相结合,建立了混合型模型,即先采用EPFF算法得到下料方式阵,再将其代入线性规划模型中,加上了加工时间以及最大加工能力的限制;最后确定了满足要求的实用下料...
  • 针对一维下料问题,提出了减少废料、减少下料设置时间和减少可回收余料的三目标优化模型,用改进的非支配排序进化算法求出问题的Pareto最优解集,运用逼近理想解方法从解集中选出一个满意解作为下料方案,各优化目标...
  • 利用部分温度的有效导热系数,采用遗传算法对纤维隔热材料的辐射衰减系数进行了优化。利用其余温度的有效导热系数验证了优化后的传热模型的正确性。最后采用优化后的数值模型对再入过程进行了模拟,通过计算得出...
  • 1d切断算法

    2018-09-27 13:03:42
    针对一维下料优化问题,提出了一种基于启发式多级序列线性优化思想的新算法,即 将下料优化问题转化为多级序列线性优化问题求解.每级求解时,在当前可行的下料方式中选择最优的一种进行下料,不断重复此操作,直到所有...
  • 首先针对给定的集装箱空间,计算出沿高度方向的水平层的最优分布,即一维下料问题;再通过优化计算,求出水平层内货物的最优排列,将问题转化为二维裁剪问题。通过与文,献报道算例的比较,表明该算法通过简单的计算过程就...
  • 18 基于鱼群算法的函数寻优算法(王辉) 人工鱼群算法是李晓磊等人于2002年提出的类基于动物行为的群体智能优化算法.该算 法是通过模拟鱼类的觅食、聚群、追尾等行为在搜索域中进行寻优,是集群体智能思想的个...
  • 该吸收器是由截断的金字塔型单元结构构成的一维光栅,其吸收机制是磁激元共振效应和法布里-珀罗谐振腔共振效应。运用有限元算法分析该吸收器的结构参数、工作波长及入射角度对其吸收性能的影响。结果表明:在优化的...
  • 关于矩形排样问题()

    千次阅读 多人点赞 2015-05-04 11:34:01
    最近看到几个比较有意思的软件:极致下料、Cutlogic 2D、新易优化板材切割等软件,都围绕个共同的话题,即板材切割,主要是针对二的。对于上述软件,下载安装测试了一下,极致下料还算可以吧。让我好奇的是整个...

    最近看到几个比较有意思的软件:极致下料、Cutlogic 2D、新易优化板材切割等软件,都围绕一个共同的话题,即板材切割,主要是针对二维的。对于上述软件,下载安装测试了一下,极致下料还算可以吧。让我好奇的是整个软件的实现算法,如果是暴力枚举的话不可能分分钟就返回一个还算可以接受的结果。目测用了一些智能搜索算法,像遗传算法、蚁群算法、模拟退火算法等等。好奇心的驱动,自己也研究了一些矩形排样的文章。准备写一个基于遗传算法的矩形排样系统。当然,仅仅是Demo版本的。好的,下面进入正题,说说关于矩形排样问题。
    在传统工业中,钢板、圆木、玻璃、服装等的切割问题都属于排料问题,排料是组合优化问题的一类典型问题。板材排料可分为两种情况:规则形状和不规则形状。排料问题的实质就是研究零件如何在板材上组合排放使得利用率最高,即排样问题。在实际情况下,考虑到成本,还要考虑“一刀切”的问题。“一刀切”即与激光切割相对应,激光切割成本太高,“一刀切”的成本比较低。“一刀切”的概念下面的图一目了然。
    这里写图片描述
    显然,左图可用“一刀切”,右图不可以“一刀切”。
    该问题的难点主要在于:
    - 如何量化“一刀切”,如何有效地排样,排样是个难点;
    - 考虑到利用率的问题,还要考虑余料的可用性;
    很明显,下料排样问题已经属于NP完全问题,此外还要尽量做到在满足利用率尽可能高的情况下,剩下的原材料板材中,可用余料的最大化。

    未完,待续,后面会给出相应的思路以及编码实现。

    展开全文
  • 采用动态规划算法生成最优单毛坯条带,通过一维背包算法确定条带在级中的排样方式和级在段中的最优排样方式,选择最优的两个段组成排样方式.对传统文献中的43道大规模基准测题进行计算,有38道测题达到最优,剩余5...
  • 基于自顶向的设计理念,提出种结构框架模型的概念,通过EXCEL表进行框架模型全尺寸驱动,并在此基础上实现三数模的生成;同时,利用有限元分析软件的二次开发技术,引入基于参数策略的改进粒子群算法,编写...
  • 《大数据:互联网大规模数据挖掘与分布式处理》源自作者在斯坦福大学教授多年的“Web挖掘”课程材料,主要关注大数据环境数据挖掘的实际算法。书中分析了海量数据集数据挖掘常用的算法,介绍了目前Web应用的许多...
  • 《大数据:互联网大规模数据挖掘与分布式处理》源自作者在斯坦福大学教授多年的“Web挖掘”课程材料,主要关注大数据环境数据挖掘的实际算法。书中分析了海量数据集数据挖掘常用的算法,介绍了目前Web应用的许多...
  • 原始微积分-源码

    2021-02-23 04:45:33
    一维非线性材料 二等分-一阶收敛。 糟糕的方法,需要特定的功能和范围设置才能正常工作 割线-收敛阶在1到2(〜1.5)之间。 一点也不差,特别是如果我们不想使用衍生工具。 牛顿-二阶收敛(并非总是如此!)。 通常...
  • 是进入CST工作室套装的通道 包含前后处理、优化器、材料库四大部分 完成三建模,CAD/EDA/CAE接口,支 持各子软件间的协同,结果后处理和导出 CST 印制板工作室™ —— CST PCB STUDIO™ 专业板级电磁兼容仿真...
  • 炉衬的传热(包括钢包侧壁和包底)分别采用圆柱坐标和直角坐标一维非稳态导 热微分方程及其初始条件和第三类边界条件来描述,以有限差分方法求解。然后,根据 整体热平衡,推导出 LF 钢水温度预报模型,预报...
  • B题:使用下料问题 C题:售后服务数据的运用 D题:研究生录取问题 美赛论文 2017年特等奖论文 2016年特等奖论文 2015年特等奖论文 2014年特等奖论文 2013年特等奖论文 2012年特等奖论文 2011年特等奖论文 2010...
  • MARC开发模式实例

    2012-01-17 14:30:31
    MSC.Marc/Link-Pro提供的另种数据传输方式,是在 MENTAT的环境从 Pro/Engineer 的数据库中直接提取Part或Assembly数据。  MSC.Marc/Link-C  MSC.Marc/Link-C是CATIA系统向高级有限元分析系统的扩展。MSC.Marc/...
  • 光电技术论文集103篇

    2010-09-17 18:50:43
    55. 梳状一维位置敏感探测器(PSD)的研制—————————————————236 56. 基于声音的跟踪摄像初步研究——————————————————————241 57. 基于瞳孔检测的注视点跟踪系统————...

空空如也

空空如也

1 2
收藏数 37
精华内容 14
关键字:

一维下料优化算法