ie案例分析教材(已修改)
2025-03-20 16:10 本頁面
【正文】 IE案例分析 王曉光 武漢理工大學機電工程學院 案例九：一維下料問題 ? 線材合理下料問題 ? 有一批原料鋼材 (如鋼管、鋼筋、角鋼、鋼梁等 )，每根長 。現(xiàn)需做 100套鋼架，每套需要長 m、 m、 ，問如何下料使所用的原料最省 ? ? 如果現(xiàn)有原料鋼管每根 19米，客戶需求 4米的鋼管50根， 6米的鋼管 20根，以及 8米的 15根，又該如何下料最節(jié)省？如何盡可能滿足顧客需求？ 案例九：一維下料問題 ? 問題分析 ? 一維下料是生產(chǎn)實踐中常見的問題，優(yōu)化下料要求最大限度地節(jié)約原材料，提高原材料的利用率。對于優(yōu)化下料問題，屬于整數(shù)規(guī)劃問題，要想求出下料方案的最優(yōu)解，從計算復雜性理論分析， 該問題屬于 NPhard問題，可用一定數(shù)量的運算去解決多項式時間內可解決的問題。雖然整數(shù)規(guī)劃問題是NPhard問題，但是線性問題卻存在有效算法。所以可以考慮不先求解整數(shù)規(guī)劃問題而先來求解其相應的線性問題。采用線性規(guī)劃來建立數(shù)學模型，分析求最優(yōu)解。 案例九：一維下料問題 ? 問題分析 ? 例如，著名的推銷員旅行問題（ Travel Saleman Problem or TSP）：假設一個推銷員需要從香港出發(fā)，經(jīng)過廣州，北京，上海， … ，等 n 個城市， 最后返回香港。 任意兩個城市之間都有飛機直達，但票價不等?，F(xiàn)在假設公司只給報銷 C 元錢，問是否存在一個行程安排，使得他能遍歷所有城市，而且總的路費小于 C？ 案例九：一維下料問題 ? 問題分析 ? 推銷員旅行問題顯然是 NP 的。因為如果你任意給出一個行程安排，可以很容易算出旅行總開銷。但是，要想知道一條總路費小于 C 的行程是否存在，在最壞情況下，必須檢查所有可能的旅行安排！ 這將是個天文數(shù)字。 案例九：一維下料問題 ? 問題分析 ? 旅行推銷員問題是數(shù)圖論中最著名的問題之一，即“已給一個 n個點的完全圖，每條邊都有一個長度，求總長度最短的經(jīng)過每個頂點正好一次的封閉回路”。 Edmonds， Cook和 Karp等人發(fā)現(xiàn)，這批難題有一個值得注意的性質，對其中一個問題存在有效算法時，每個問題都會有有效算法。 案例九：一維下料問題 ? NP難題 ? NP （ nondeterministic polynomial 縮寫）非確定性多項式 。 ? 迄今為止，這類問題中沒有一個找到有效算法。目前傾向于接受 NP完全問題（ NPComplet 或 NPC）和 NP難題（ NPHard或 NPH）不存在有效算法這一猜想，認為這類問題的大型實例不能用精確算法求解，必須尋求這類問題的有效的近似算法。 ? 這類問題屬于整數(shù)規(guī)劃，求解十分復雜。其原因是可行的下料方式數(shù)目可能很大，從而造成要求解的整數(shù)規(guī)劃的維數(shù)很高。 ? 我們應該知道：首先，一個好的下料方案應該是原材料利用率最大，從而減少損失，降低成本，提高經(jīng)濟效益。 案例九：一維下料問題 ? 其次，要求所采用的下料方式盡可能少，即希望用最少的下料方式來完成任務。因為在生產(chǎn)中轉換下料方式需要費用和時間，導致成本上升，效率下降。因此下料問題的目標是在生產(chǎn)能力容許的條件下，以最少數(shù)量的原材料 ，盡可能按時完成需求任務 ，同時下料方式數(shù)也盡量地少。 案例九：一維下料問題 ? 根據(jù)該問題的特點，我們先從最基本的單目標決策問題入手，以材料損耗最少為目標，通過不同的數(shù)學原理建立最優(yōu)化模型，得出最初的結果。然后逐步增加其約束條件 —— 最小的下料方式數(shù)，并根據(jù)該約束條件進一步完善我們的最優(yōu)化模型，得到損耗最少，下料方式數(shù)又小的結果。 案例九：一維下料問題 ? 接下來檢驗在所得下料方式的排列中，是否存在可以滿足時間條件限制的排列方式。若存在，則該結果即為最優(yōu)解；若不存在，則這個結果就不符合題意，必須重新構建多目標決策的最優(yōu)化模型。 案例九：一維下料問題 ? 在新模型中以客戶時間需求為第一 目標，材料損耗最少，下料方式最少為第二 目標。因此，在下料時就應該優(yōu)先生產(chǎn)那些有時間限制要求的零件，并且求出在需求的時間段內下料方式和損耗的最優(yōu)結果。 案例九：一維下料問題 ? 案例一 ? 為了建立模型方便，我們把下料后余下的小于最短用料的鋼材稱為廢料頭，把下料得到的長 m、 m、 m的鋼材稱為規(guī)格鋼，把 m長的原料鋼材簡稱原鋼。 ? 因此，所用的原鋼可分解成三部分：成套利用的規(guī)格鋼、剩余的規(guī)格鋼、廢料頭。確定套裁方案，可利用窮舉法，得如下方案 (見表 1)： 案例九：一維下料問題 ?
教學課件相關推薦
鄂ICP備17016276號-1