[發明專利]一種原材料下料排樣的求解方法

有效

• 申請號: 202211346050.6
• 申請日: 2022-10-31
• 公開（公告）號: CN115455341B
• 公開（公告）日: 2023-02-07
• 發明（設計）人: 梁橋康;肖海華;秦海;鄒坤霖
• 申請（專利權）人: 湖南大學
• 主分類號: G06F17/11
• 分類號: G06F17/11;G06Q10/04
• 代理公司: 長沙市護航專利代理事務所(特殊普通合伙) 43220
• 代理人: 莫曉齊

1.一種原材料下料排樣的求解方法，其特征在于：包括如下步驟：

步驟S1、確定原材料的長度、每種下料工件的數量、每種下料工件的尺寸大??；

步驟S2、依據原材料的長度、每種下料工件的數量、每種下料工件的尺寸大小建立原始數學模型，對原始數學模型矩陣化得到簡化后的數學模型；

步驟S3、建立初始單位矩陣，引入常量參數，利用初始單位矩陣和常量參數對簡化后的數學模型進行初等行變化，得到新數學模型；

步驟S4、借助Gurobi優化器對新數學模型進行求解，得到新數學模型的初始可行解，初始可行解包括下料排樣方案和決策變量，決策變量指不同排樣方案對應的變量，即對應每一種排樣方案所使用原材料的數量；

步驟S5、利用CG算法在初始可行解的基礎上繼續進行求解，得到最優松弛解,最優松弛解是指最優決策變量，若最優松弛解全為非負整數，則將最優決策變量求和的值與步驟S4中決策變量求和的值進行比較，選擇求和最小的一方所產生的決策變量作為最終的決策變量，其所對應的下料排樣方案為最終的原材料下料排樣方案，若最優松弛解不全為非負整數，則進入步驟S6；

步驟S6、借助啟發式算法對步驟S5獲得的最優松弛解進行取整，得到非負整數解，將最優決策變量求和的值與步驟S4中決策變量求和的值進行比較，選擇求和最小的一方所產生的決策變量作為最終的決策變量，其所對應的下料排樣方案為最終的原材料下料排樣方案；

所述步驟S2中的原始數學模型為：

第一目標函數：

第一約束條件：

，，，，（1）

其中，表示決策變量，具體表示第j種切割模式下所使用的原材料的數量；表示第j種切割模式中第i種待下料的產品的數量；表示第i種待下料的工件所需要的總數量；表示所需第i種待下料的工件的尺寸大?。籐代表原材料的長度；表示非負整數；

所述步驟S2中簡化后的數學模型具體為：

第二目標函數：

第二約束條件：

，，，

（2）

其中, 表示一個1行n列的矩陣；解向量矩陣表示是一個n行1列的矩陣，該矩陣的元素是決策變量，它的值被約束為大于或等于零且為整數；A表示排樣方案的矩陣，是一個m行n列的矩陣，，當求解完成所有的切割模式后，由產生的切割模式組成矩陣A中所有的列，每一列代表一種切割模式，在迭代開始前，它是一個m行m列的單位矩陣；表示一個m行1列的列向量需求矩陣，該矩陣的元素值表示不同尺寸工件的需求數量，m表示所需求工件種類的數量；表示一個m行1列的矩陣，該矩陣是一個列向量變量的列矩陣，其中的元素值為非負整數，代表當前需要被求解的一種切割模式，用作為的索引，表示所有可能的切割模式集，表示當前迭代需要被求解的一種切割模式，其中元素表示在切割模式中，第i種工件的數量，；表示一個1行m列的行向量矩陣，該矩陣的元素代表m個不同工件的尺寸大?。槐硎驹谇懈钅Ｊ街?，不同工件的尺寸乘以各自對應不同工件數量的乘積之和要小于等于原材料的長度；中的0 表示一個元素全為0的m行1列的列向量矩陣,其中，矩陣中所有的變量值被約束為大于或等于零，且必須小于或等于各類工件對應的需求數量，其值；

所述步驟S3中的新數學模型具體為：

假設決策變量的數量為m個，不同工件種類的數量為m個，每迭代一次，生成一個新列，也代表生成一種新的切割模式，當迭代求解生成第k種切割模式時，對應的第三目標函數和第三約束條件可寫成如下：

第三目標函數：

第三約束條件：，

，

，

，and，，

，，

，（3）

在（3）式中，表示在當前迭代中，將切割模式對應的決策變量固定為一個常量參數，該常量參數等于前一次迭代求解得到的第k列對應決策變量的值；表示求解切割模式時，通過將列向量矩陣的第k個元素強制為0獲得；同理，表示求解切割模式時，通過將矩陣的第k行的元素強制為0元素獲得；表示列向量變量矩陣參與矩陣初等變化之后的矩陣表達式；表示決策變量矩陣中除第k列對應的決策變量為固定值外，其余決策變量全部被約束為大于或等于零；表示未知列向量變量矩陣參與矩陣A進行初等行變化之后，矩陣A中第k行第k列元素的表達式，其值等于1，其中是一個1行m列矩陣，可通過將矩陣的第k行構建的行向量矩陣；目標函數中是一個元素全為1的1行m列矩陣。