2022研究生数学建模B题思路

        子问题1：排样优化问题。要求建立混合整数规划模型，在满足生产订单需求和相关约束条件下，尽可能减少板材用量。

约束:

        1.在相同栈(stack）里的产品项( item）的宽度（或长度）应该相同

        2.最终切割生成的产品项是完整的，非拼接而成。

        本子问题要求编程，以数据集A为输入，输出结果要求见第五部分。

求解思路：

        首先观察并分析数据(A1-A4,A5删掉不考虑，官方已通知)，每个excel表中材料相同，目标为给出板材的切割方案。

        根据第3条假定，排样方式为精确排样且切割段数不超过三，子问题中还要求相同栈里产品宽度或高度相同，所以很容易想到将数据中具有相同长度或宽度的部件进行合并，排列成更大的部件组合作为一一个栈，比如这三个部件：

        他们宽度相同，将其组合成224*1153的一个大块部件作为一个栈，然后这个栈再加上一些冗余，比如224*1160，注意得保持宽度不变，之后再合并类似的不同栈组成更大的条带，以满足条带的长度恰好是板材的长或宽，不同条带再一次组合直到匹配原材料的长宽。总共组合三次，每次都可以加上适当冗余，最后能精确匹配原材料版的长宽。这样的划分可符合题目要求。对于三阶段约束排样算法，有精确算法(如线性规划，动态规划，整数规划和分支定界法等)和启发式算法(遗传算法，模拟退火算法等)两种，可根据实际数据量大小进行选择。
        然后如何鉴定这切分的优秀程度呢?可用有效利用率表示，利用率即为所有部件面积和除以所用的所有原料面积和，越高越好。

        首先确定极限利用率，即理论最少需要多少板材，如A1中所有部件面积和为284万平方米,需要83.54块2440*1220的原材料板,即至少需要84块版﹐那么极限利用率为99.45%,因此划分后利用率越接近99.45越好(理论不可能超过)，当然这个，上限还能再降低，比如A1数据中有2418*58的部件，由于原材料版最长边为2440且没有小于22的部件可用，因此这种部件放入版中必然会有22*58的面积损失,如果考虑这种情况还可以进一步降低上界。最底层的算法是几何算法，可以采用左底策略等放置部件，通过不同策略选择最优的元件放置到矩形中。
        随机化方法和智能优化算法，则要处理排放矩形的顺序，可以使用各种规则，比如面积大小排序，周长，宽度，高度，综合等等，然后还要组织选择搜索策略。往往需要快速找到一个局部范围内的较优解，然后慢慢搜索到更好的全局解。
        以遗传算法为例:
        首先将长或宽相同的部件进行分组，遗传算法以整数编码(编码方式不唯一-，比如:每个部件有组号和组内序号，正数表示横放，负数表示竖放等等)，解码时根据整数排列顺序组合相邻的部件为更大的部件，然后将不同部件拼合，计算出利用率等。

        子问题2：订单组批问题。要求建立混合整数规划模型，对数据集B中全部的订单进行组批，然后对每个批次进行独立排样，在满足订单需求和相关约束条件下，使得板材原片的用量尽可能少。
在满足子问题1约束的基础上进一步要求:

1)每份订单当且仅当出现在一个批次中;
2)每个批次中的相同材质的产品项(item）才能使用同一块板材原片进行排样;

3)为保证加工环节快速流转，每个批次产品项(item）总数不能超过限定值;

4)因工厂产能限制，每个批次产品项(item）的面积总和不能超过限定值;本子题要求编程，以数据集B为输入，输出结果要求见第五部分。

子问题2思路:

        子问题2的数据量达到109218条，我们需要做的是根据题目要求完成组批，组批需要满足以下限制:
        单个批次产品项(item)总数上限max_ itemn__num = 1000
        单个批次产品项(item)的面积总和上限max__ item_ area = 250(m2)根据产品项数量粗略估计，至少需要110个批次。
        我们要寻找需遵循的组批原则。题目背景中提到:组批批次太小，材料利用率低，生产效率低;如果组批批次太大，材料利用率会提高，但订单交货期得不到保证，订单分拣难度提高，生产效率降低。
        假定我们已有一种组批策略，需要建立一个可以量化组批合理性的模型，可以使用批次内批次内产品项数/单批次产品项总数上限和批次内产品面积/单个批次产品项面积总和上限这两个指标进行评价。
        那么组批策略如何产生呢，可以建立整数规划模型，在数据处理的基础上(将 item按照相同材质、大小--致的汇总)使用启发式算法，如遗传算法等进行求解。
        可以尝试多种组批策略，分别计算所用板材原片的数量，选取最小的作为最优解。