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问题，
但是线性问题却存在有效算法。所以可以考虑不先求解整数规划问题而先来求解其相应的线性问题。采用线性规划来建立数学模型，分析求最优解。

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