1、工業中截斷切割的優化設計一摘要本文討論了加工業中 截斷切割的優化排序策略我們對于不同的切割方式總數用窮舉法得到720 種所可行解及其費用并對于原問題建立了決策并對所給出的算法進行了分析和檢驗1. 當e=0時我歸納出解決問題的最優法則, 從而提出了將面間距統一成判斷權重來作為排序準則的算法,同時證明了e = 0 的情況下根據這種最優準則能夠實現題目所要求的優化目標2.對于e ¹ 0 時我們提出了實用準則最后我結合實際問題 將本問題進行了拓展討論了當最終產品(成品)在毛坯(待加工長方體)中位置不預定時應如何實施加工方案以達到節省費用和節約資源的目的,使我們的方案適用于更為廣闊的領域二問題

2、的重述、在工業生產中，常需要采取將物理一分為二的截斷切割方式從一塊長方體材料中切出一個小長方體，其加工費用取決于水平切割和垂直切割的截面面積，以及調整刀具時的額外費用。對本題所給出的問題我們首先面臨的對加工次序的排序策略然后我們考慮當毛坯和產品位置不預定的時候如何采取策略以達到我們的優化目的問題：1> 需考慮的不同切割方式的總數。2> 給出上述問題的數學模型和求解方法。3> 試對某部門用的如下準則做出評價，每次選擇一個加工費用最少的切割面進行切割。4> 對于 e=0 的情況有無簡明的優化準則。5> 用以下實例驗證你的方法：待加工長方體和成品長方體的長，寬，高分別為

3、10，14.5,19 和3,2,4,兩者左側面，正面，底面之間的距離分別為6,7,5(單位為厘米，垂直切割費用為每平方厘米1 元，r 和e 的數據有4 組：1) r=1,e=0;2) r=1.5,e=0;3) r=8,e=0;4) r=1.5, 2 £ e £15 ;三 模型的假設和符號說明1 切割刀具為兩個一個水平放置一個為垂直放置2 目標長方體所在位置不與毛坯任一表面重合3 水平方向只需平行移動水平刀具垂直方向只平行移動或調整后再平行移動刀具因此調整費用e 是否付出僅取決于先后兩次垂直切割是否平行而不記是否穿插著水平切割1 / 94毛坯與工作臺接觸的底面是事先指定的5毛

4、壞、成品均為長方體，且這兩個長方體的對應面是平行的，如下圖 a,b, c 毛坯的長寬高單位厘米aa,bb,cc 最終產品的長寬高單位厘米毛坯的左表面右表面前表面后表面上表面下表面最終產品的左表面右表面前表面后表面上表面下表面(有時我們為了敘述問題的方便將其依次記為5,6,3,4,1,2)d j 最終產品與毛坯的對應表面的距離j = 1,2,，6r 水平切割單位面積費用與垂直切割單位面積費用之比e 調整一次垂直刀具的額外費用p 垂直切割單位面積費用ti 加工過程中的第i 刀切割第ti 個面wi 第i 次切割的切割費用單位元vi 第i 次切割被切割掉部分的體積單位立方厘米si 第i 次切割時切割面

5、積分別表示在切割第側面時的費率，依題意：其它變量如果出現 則在使用時另行說明四 模型的建立 (2,3,4,5,6) (3,4,5,6) (4,5,6) (5,6) (6) (1,3,4,5,6) (2,4,5,6) (3,5,6) (4,6) (5) (1,2,4,5,6) (2,3,5,6) (3,4,6) (4,5) (4)(1,2,3,4,5,6,) (1,2,3,5,6) (2,3,4,6) (3,4,5) (3) (1,2,3,4,6) (2,3,4,5) (2) (1,2,3,4,5) (1,2,3,4) (1,2,3) (1,2) (1)e=0的情形:=1,2,3,4,5,6表示

6、初態，即沒有進行任何加工； 對應一個完整的加工策略事實上為=1,2,3,4,5,6的一個全排列；而=1,2,3,4,5,6的任一子集S應某個策略在對毛坯加工過程中某個中間狀態；3）在對毛坯加工過程中某個中間狀態S它僅與在它之前截掉了那些面的組合有關,而與過程(即排列)無關；4）=1,2,3,4,5,6的  64 個子集構成方體切割的所有可能的狀態（包括初始狀態，終態）：以的64個子集構造有向圖G,，以S為起點，以為終點連邊，且, 使得對有向圖G邊賦權：任取有向圖G邊，不設其以S起點，以為終點，w (或記為）w（,）表示在狀態S，截去i所需費用這些集合按照其包含元素

7、數目的多少可分為7組，從多到少排序，相鄰兩組間構成一個決策階段；1因此得如下“6”階段動態規劃問題：Min ,)S.t =1,2,3,4,5,6.為 的一全排列 =  w（,） 的表述：記分別表示方體的長、寬、高（這1面到2面、3到4、5到6的距離），可得：)=(A,B,C)=w ,)=五 模型求解定理（最優準則）：設e=0，若策略.滿足：，則策略.必為截斷切割的最優策略。證明：某截斷切割策略.，若滿足，且，即稱構成策略.的一逆序對（逆序數？）；（以下證明對任一策略.，若策略.中存在逆序對，則總可以構造某截斷切割策略，其逆序數小于策略

8、.的逆序數，但總的切割費用不比策略.的多）        設某截斷切割策略.的逆序數大于0，則必存在相鄰的“兩刀”(k,k+1)(成策略.的一逆序對，交換、的次序，此時與比較，前者的逆序數比后者的減少“1”，而在下面證明前者的切割費用不比后者的多：1當面、相對時，僅僅交換相鄰兩刀(k,k+1)次序對切割費用沒有影響；2當面、相鄰時，不妨設、此時，與切割費用之差等于：=其符號與相同假設，即的切割費用比的少。可用mathematics編程求解，程序見附件。問題條件切割方式 最少費用Ar=1 e=0Br=1.5 e=0

9、437.5 Cr=8 e=0 540.5d r=1.5 e=215e取值 最少費用 最優切割方案e=2 445.5 e=2.1 445.9 e=2.2 446.3 e=2.3 446.7 e=2.4 447.1 e=2.5 447.5 e=3 448.5 e=3.5 449.5 e=4 450.5 e=4.5 451.5 e=5 452.5e=5.5 453.5 e=6 454.5 e=6.5 455.5 e=7 456.5 e=7.5 457.5 e=8 458.5e=8.5 459.5 e=9 460.5 e=9.5 461.5 e=10 462.5e=10.5 463.5 e=11 46

10、4.5 e=11.5 465.5 e=12 466.5 e=12.5 467.5 e=13 468.5e=13.5 469.5 e=14 470.5 e=14.5 471.5 e=15 472.5 其中1,2,3,4,5,6，代表切割的面如下圖： 6 2 3 5 4 1 由此可見對于不同的e值，會有不同的最優切割方式，當e大于2.5卻只有唯一的最優切割方式。下圖為e取不同值時最少切割費用的圖像畫出 最可能是最優切割方式的三種切割方式切割費用隨e的取值而變化的圖像：可知當e等于2.5時為突變拐點綜上對于e不同取值時對應的最優方案為 e的取值 最優切割方式 2 e<2.5 e=2.5 2.5<e15對此我們可以提出一個很實用的準則：當e較小時，換刀的費用很小，對于切割方式可以不考慮換刀的影響，選擇單純切割費用最少的方式即可；當e較大時，則必須主要考慮換刀的次數，在單純切割費用盡量小的前提下，盡量選擇換刀次數少的切割方式。六 結果分析及討論由以上的計算與分析可知，r以及e是在毛坯與成品要求已固定情況下影響費用和切割方式的重要因素，當e=0時，根據優化準則，可以找到最優的切割方式，當e不等于