线性规划技巧之列生成

线性规划技巧之列生成

摘要

在制造业中，常常要切割原材料，比如把纸卷、布料、钢管等等，切割成不同长度，从而满足不同产品，或者不同用户的需求。

由于需求长度不同，切割方式有多种。不同的切割方式，消耗的原料总数不同。问题是怎么切割，既能满足需求，又最节省原料。

这样的问题，称为“下料问题”。本文以下料问题为例介绍列生成算法，它可以用来解这类线性规划问题。