IE案例分析教材(PPT 71頁)

線材合理下料問題
有一批原料鋼材(如鋼管、鋼筋、角鋼、鋼梁等)，每根長7.4m。現需做100套鋼架，每套需要長2.9 m、2.1 m、1.5m的鋼材各一根，問如何下料使所用的原料最省?
如果現有原料鋼管每根19米，客戶需求4米的鋼管50根，6米的鋼管20根，以及8米的15根，又該如何下料最節省？如何盡可能滿足顧客需求？
問題分析
一維下料是生產實踐中常見的問題，優化下料要求最大限度地節約原材料，提高原材料的利用率。對於優化下料問題，屬於整數規劃問題，要想求出下料方案的最優解，
從計算複雜性理論分析， 該問題屬於NP-hard問題，可用一定數量的運算去解決多項式時間內可解決的問題。雖然整數規劃問題是NP-hard問題，
但是線性問題卻存在有效算法。所以可以考慮不先求解整數規劃問題而先來求解其相應的線性問題。采用線性規劃來建立數學模型，分析求最優解。

..............................