100分求一个成品布优化开剪算法

求一个成品布优化开剪算法,
比如说我有200M的布,布宽1.5M,布上有许多疵点,每个疵点我们给它定一个评分,
等级标准是
一等品  100平方米的评分和<=20
二等品  100平方米的评分和<=25
三等品  100平方米的评分和>25现在我要将给定的200M布剪为大小不等的几段,小于20M的计为二等品,大于120M的要继续开剪.要求使开剪后的布的一等品率最高,
请各位高手给个算法思路,非常感谢!!!

解决方案 »

  1.   

    问题的确比较含糊。
    该问题简化一下：
    有指定矩形（M 200*N 1.5）的原料，其上随机分布着许多疵点。
    求最优的一维分割
    约束：
    必须小于120M一等品  100平方米(66.7m)的评分和 <=20
    二等品  100平方米(66.7m)的评分和 <=25
    三等品  100平方米(66.7m)的评分和 >25小于20M的计为二等品，瑕疵<=25约束条件有如下问题：
    分割小于100平方米的怎么评价等级？
    等级的分级不是给定面积对应的瑕疵数量。应该是单位长度（面积）对应的瑕疵的数量。
    这样的约束是没有办法使用计算机求解的，因为条件不严密。
      

  2.   

    to hapland :
    定等条件等价于下面这个:
    一等品  每平方米评分和  <=20/100 
    二等品  每平方米评分和  <=25/100 
    三等品  每平方米评分和  >25/100 每个疵点都有字典表对应一个评分值,
    可以根据疵点的代码从数据库中检索到相应的评分.
    小于20M布是不能记为一等品的,
    意思就是说小于20M的布就算布面评分再小,最好的等级也只能是二等品.不知这样解释有没有清楚了???
      

  3.   

    呵呵，楼主是Esquel.IT 的吗？我认为：可以使用加权序列，序列中保存每个疵点的级别和上个疵点到这个疵点的长度。然后的主要疵点作为开剪分界,递归向两边运算,每检测一个疵点后,检查是否等级变化,持续到三等品,再将该点作为开剪分界.并依次计算使用每个主要疵点的开剪方案的结果。仅供参考.
      

  4.   

    呵呵,我们经理曾经是Esquel.IT的,哈哈
      

  5.   

    呵呵，我是Esquel.IT 出来的。
      

  6.   

    首先 一个问题的解决需要经历两个阶段：物理模型 和 数学模型
    物理模型是用通用的术语把问题说清楚
    数学模型是用数学的语言把问题说清楚
    一般有了数学模型，在问题不是很复杂的情况下，
      目前的计算机水平都可以求得解答
    本问题的模型存在三个主要难点：
    1、物理模型的描述：包括瑕疵的描述，分割的描述，评价的描述
    （这个事情究竟是怎么做的，直接解法就是模仿人的做法，求解）
    2、求解模型的建立
    3、分割方案的优选：什么样的分割方案才是较优的。（这个属于数学模型）本问题的数学描述可能不是很复杂，但是解法可能有点复杂我个人基本理解这个问题，但是要建立物理模型还是有点困难
    （因为这样的问题从来没有遇到过，我可不是Esquel.IT的，哈哈）近来很忙，没有时间静心来想。见谅。
      

  7.   

    to neweipeng :
    ‘要求使开剪后的布的一等品率最高’是指‘一等品的面积/布总面积'最大to hapland:
     想法太帅了,老外的优化开裁原理就是模仿人的操作,
    但最可惜的就是没有相关的资料,所以只能自已找路子.
    我认为老外可以,我们一样可以,不但可以,而且会更好.
    现在公司的做法是只按长度开剪,然后定等,没有一点优化,所以才要开发一个算法.最近在查运筹学方面的材料,希望能打开局面.to yourlin :
    有疑问请提出来,我可以解释,呵呵
    to all:
    感谢各位的支持!!
      

  8.   

    哈哈，这个wanglj2007的出现频率比我还低。
    这个问题可能还涉及 图论 的知识。
    运筹学中的内容可能还不足以处理。关于这个问题的参数，我要提问：
    是将瑕疵控制在开剪的位置（将瑕疵分成两半），还是保留完整的瑕疵。
    或者进一步的，瑕疵是有大小的，还是抽象为一个点。带来数学处理上的问题：
    瑕疵如果被剪开，评分如何计算？所以大家说该问题的物理模型不清楚。------------------------
    所以让你参考图论是因为，
        布可以认为是连续的空间，
        瑕疵将该连续的空间，分割为离散的部分，即由连续空间变成了离散的空间。
        
        我们要求的是这些离散空间的组合 或者 某种分割       ——这个就是分割方案（开剪方案）
        使其某种属性（瑕疵评分，其实与面积这样的属性没有性质上的差异），达到最优。
        
        可以认为是离散空间上的优化问题。直接解法是人的解法，人有时靠的是知觉，不是科学，计算机学不会。
    计算机的直接解法就是穷举（遍历），
        由于是离散空间求解，
    因此，
        解（开剪方案）的总数是有限的。数量再大也是有限的。
        因此建立 评价方法 后，用量化方法 回答 解答甲 好 还是 解答乙 好？这样的问题。
    就可以直接使用穷举（遍历）求解。
      

  9.   

    to   hapland: 瑕疵如果被剪开，评分如何计算？ 
    答:疵点分为两种:一种是点状的,此类疵点可以看为一个点,没有长度;
    一种是长度型的,此类疵点剪开后,评分按比例算,
    即:100cm的疵点,评分为10分,剪为两个,40cm和60cm,
    则40cm的评分为40cm/100cm*10分=4分
      60cm的评分为60cm/100cm*10分=6分我在数据库记录了疵点的开始位置,长度,评分等一系列的信息本来只是感觉这个问题不简单,但没想到如此复杂,越想越复杂,头都大了...关于<<图论>> 可不可以介绍本书让我参考下下,非常感谢!!
      

  10.   

    感谢各位的大力相助,尤其是hapland,
    呵呵.
    CSDN通知我结帖了...给分...
      

  11.   

    CSDN什么意思，这样能够深入讨论问题的帖子很少的，
    结贴对于论坛有什么好处。
    下周还要出差，等我有时间了，继续想。只要我们这些低等兵种使劲想，一定可以想出来的。