钢管下料问题用非线性整数规划的数学模型来建模以及用Lingo进行计算

其实对学过数学模型的童鞋来说,这个问题是标准的建模问题,没什么新意.

之所以把这个东西拉出来过一遍,主要是因为, 计算的时候(玩别的类似的东西的时候一样,但今天是计算)我内心特别高兴, 有一种无法表达的满足感, 算是一种休闲娱乐.

另外一个, 我知道整数规划是读研究生的时候; 而恰在此之前1年左右, 曾经在Nitto Denko待过很短一段时间, 实际中碰到非常类似的情形.

Nitto Denko在松江有分切工厂, 把日本import进来的原始的标准宽度的产品根据客户订单的需要进行切割. 每次订单都会来各种宽度规格和数量的需求.

我记得当时自己是负责接收订单, 跟客户确认各种细节, 然后再跟仓库确认库存现状, 确认好之后用邮件和电话对slitting工厂发出切割指令, 办妥之后再向客户确认订单,

签章之后Fax回传给客户.

向仓库和slitting工厂发出指令之前要计算需要的材料的种类和数量, 当时是用一个固定的带有比例系数的公式来计算的. 比如, 客户需要的全部产品的宽度加起来如果

是99, 那么订单乘以一个大于1的比例系数, 或者叫magic number, 万能比例系数, 比如1.13, 基本上就是需要的数量了. 不过有的时候,这个公式会失灵. 

我思来想去, 居然也没有一个头绪可以完美解决这个问题, 因为, 我又不是数学天才; 不过, 学了"最优化原理"之后, 我发现那个问题应该是这么解决的.

正是因为这个原因, 我对非线性整数规划这部分, 一直有特别的好感, 即使现在貌似也不大用的上了,还是想把Lingo拿出来, 重新写写代码, 轻松run一下.

照搬例题是非常轻松的事情. 所以, 下面就是一个照搬.

标准的钢管的长度是19m; 客户的订单需要 4m长的钢管50根, 5m长的钢管13根, 7m长的钢管9根, 9m长的钢管22根.

怎样安排切割废料最少? 怎样安排切割用的19m标准钢管最少?

好了, 现在就按照标准答案来解答.

假设5种不同切割模式, 每种各用标准钢管x1, x2, x3, x4, x5根

假设每根原始钢管通过 切割模式i可以得到客户所需的第j种规格(j=1,2,3,4, 对应规格4m, 5m, 7m, 9m)的钢管数量为rij;

标准钢管最少意味着 min=x1+x2+x3+x4+x5;

废料最少, 意味着不大于3的余料之和最少: min= 19*(x1+x2+x3+x4+x5)-4*(r11*x1+r21*x2+r31*x3+r41*x4+r51*x5)-5*(r12*x1+r22*x2+r32*x3+r42*x4)-7*(类似)-9*(类似)

还是线性的目标函数容易计算, 就算第一个吧, 

model:

sets:
voc/1..4/:length,number;
cut/1..5/:x;
pattern(voc,cut):r;
endsets

data:
length=4 5 7 9;
number=50 13 9 22;
origin=19;
enddata

min=@sum(cut(i):x(i));
@for(voc(i):@sum(cut(j):x(j)*r(i,j))>number(i));

@for(cut(j):@sum(voc(i):length(i)*r(i,j))@for(cut(j):@sum(voc(i):length(i)*r(i,j))>origin-@min(voc(i):length(i))+1);

@sum(cut(i):x(i))<@size(voc)+@sum(voc(j):@floor(number(j)/@floor(origin/length(j))));
@sum(cut(i):x(i))>@floor(@sum(voc(i):length(i)*number(i))/origin); !最简单算数平均的下届;

@for(voc(i):@sum(cut(j):x(j)*r(i,j))>number(i));!每一种长度的数量不小于客户需求数;

@for(cut(i):@gin(x(i)));
@for(pattern(i,j):@gin(r(i,j)));
end

局部最优解找到一个, 这种解应该比较多吧

  Local optimal solution found.
  Objective value:                              29.00000 需要原始材料29根
  Objective bound:                              29.00000
  Infeasibilities:                              0.000000
  Extended solver steps:                            3975
  Total solver iterations:                        131959


  Model Class:                                     PINLP


  Total variables:                     25
  Nonlinear variables:                 25
  Integer variables:                   25


  Total constraints:                   21
  Nonlinear constraints:                8


  Total nonzeros:                     135
  Nonlinear nonzeros:                  80


                                Variable           Value        Reduced Cost
                                  ORIGIN        19.00000            0.000000
                              LENGTH( 1)        4.000000            0.000000
                              LENGTH( 2)        5.000000            0.000000
                              LENGTH( 3)        7.000000            0.000000
                              LENGTH( 4)        9.000000            0.000000
                              NUMBER( 1)        50.00000            0.000000
                              NUMBER( 2)        13.00000            0.000000
                              NUMBER( 3)        9.000000            0.000000
                              NUMBER( 4)        22.00000            0.000000
                                   X( 1)        9.000000            1.000000
                                   X( 2)        11.00000            1.000000
                                   X( 3)        0.000000            1.000000
                                   X( 4)        2.000000            1.000000
                                   X( 5)        7.000000            1.000000
                                R( 1, 1)        3.000000            0.000000  第1种切割模式 长度为4的 3 根
                                R( 1, 2)        0.000000            0.000000  第2种切割模式, 长度为4的没

                               R( 1, 3)        1.000000            0.000000   第3种切割模式, 长度为4的 1根

                                R( 1, 4)        1.000000            0.000000 第4种切割模式 , 长度为4的1根
                                R( 1, 5)        3.000000            0.000000 第5种切割模式, 长度为4的3根
                                R( 2, 1)        0.000000            0.000000 第1种切割模式长度为5的 没有
                                R( 2, 2)        0.000000            0.000000 第2种切割模式, 长度为5的没
                                R( 2, 3)        0.000000            0.000000 第3种切割模式, 长度为5的没
                                R( 2, 4)        3.000000            0.000000 第4种切割模式, 长度为5的3根
                                R( 2, 5)        1.000000            0.000000 第5种切割模式, 长度为5的1根
                                R( 3, 1)        1.000000            0.000000 第1种切割模式长度为7的 1根
                                R( 3, 2)        0.000000            0.000000 第2种切割模式, 长度为7的没
                                R( 3, 3)        2.000000            0.000000 第3种切割模式, 长度为7的2根
                                R( 3, 4)        0.000000            0.000000 第4种切割模式, 长度为7的没有
                                R( 3, 5)        0.000000            0.000000 第5种切割模式, 长度为7的没有
                                R( 4, 1)        0.000000            0.000000 第1中切割模式, 长度为9的没有

                                R( 4, 2)        2.000000            0.000000 第2种切割模式, 长度为9的2根
                                R( 4, 3)        0.000000            0.000000 第3种切割模式, 长度为9的没有
                                R( 4, 4)        0.000000            0.000000 第4种切割模式, 长度为9的没有
                                R( 4, 5)        0.000000            0.000000 第5种切割模式, 长度为9的没有


                                     Row    Slack or Surplus      Dual Price
                                       1        29.00000           -1.000000
                                       2        0.000000            0.000000
                                       3        0.000000            0.000000
                                       4        0.000000            0.000000
                                       5        0.000000            0.000000
                                       6        0.000000            0.000000
                                       7        1.000000            0.000000
                                       8        1.000000            0.000000
                                       9        0.000000            0.000000
                                      10        2.000000            0.000000
                                      11        3.000000            0.000000
                                      12        2.000000            0.000000
                                      13        2.000000            0.000000
                                      14        3.000000            0.000000
                                      15        1.000000            0.000000
                                      16        6.000000            0.000000
                                      17        2.000000            0.000000
                                      18        0.000000            0.000000
                                      19        0.000000            0.000000
                                      20        0.000000            0.000000
                                      21        0.000000            0.000000