简单线性规划问题SAS编程

问题:一批铁丝,数量不限,每一根铁丝长 1650 mm ,现需要截取下列品种、长度、数量的铁丝:
品种 长度/mm 需要数量/根
a1 303 10
a2 251 10
a3 202 10
a4 151 10
a5 107 10
注:铁丝的长度、品种的个数、品种的长度、需要数量都是变量。
怎样计算,在达到需要截取的品种、长度、数量的前提下,使用的铁丝根数最少,浪费的最小?
这里有两个要求:1,使用1650mm铁丝的根数最少
                        2,有一根剩下的最长
代码1:
 
data sxl;
input _ROW_$ x1 x2 x3 x4 x5 x6 _TYPE_$ _RHS_;
cards;
object 0 0 0 0 0 1 MIN .
proc1 303 251 202 151 107 -1650 lE 0
proc2 1 0 0 0 0 0 GE 10
proc3 0 1 0 0 0 0 GE 10
proc4 0 0 1 0 0 0 GE 10
proc5 0 0 0 1 0 0 GE 10
proc6 0 0 0 0 1 0 GE 10
bound 100 100 100 100 100 100 UPPERBD .
inbd 1 2 3 4 5 6 INTEGER .
;
proc print;
proc lp data=sxl;
run;

RESULT:

Variable Reduced
ol Name Status Type Price Activity Cost

1 x1 ALTER INTEGER 0 11 0
2 x2 ALTER INTEGER 0 11 0
3 x3 ALTER INTEGER 0 12 0
4 x4 ALTER INTEGER 0 11 0
5 x5 BASIC INTEGER 0 10 0
6 x6 INTEGER 1 7 1

 
代码2:
data aa (keep=c d e f g i );
   a1=int(1650/303);
   a2=int(1650/251);
   a3=int(1650/202);
   a4=int(1650/151);
   a5=int(1650/107);
   w=1650-107;
    do c=0 to a1;
          do d=0 to a2;
              do e=0 to a3;
                  do f=0 to a4;
                     do g=0 to a5;
                        x=303*c+251*d+202*e+151*f+107*g;
                        y=1650-x;
      
                         if x>w and x<=1650 then do;
                                                     i+1;
                                                     output;
                                end;
                      end;
                  end;
             end;
           end;
     end;
run;
proc print;
run;
proc sort data=aa out=aa(drop=i);
by descending i ;
run;
data collect(drop=i);
LENGTH _VAR_ $8.;
set aa;
i+1;
 _VAR_=catt(‘COL’,i);
run;
proc print;
run;
proc transpose data=aa out=aa1;
run;
proc print;
run;
data bb(drop=i);
do i =1 to 334;
    a=1;
 b=100;
 c+1;
 output;
 end;
 run;
 proc transpose data=bb out=bb1;
 run;
data ex1(keep=col1-col334);
set aa1 bb1;
run;
data ex;
input  _type_$ _rhs_;
cards;
ge 10
ge 10
ge 10
ge 10
ge 10
min .
upperbd .
integer .
;
run;
data ex2;
merge ex1 ex ;
run;
proc print;
run;
proc lp data=ex2 primalout=p;
run;
data sxl;
set p;
where _VALUE_ NE 0;
run;
proc sort data=collect out=collect;
by _VAR_;
run;
proc print;
run;
proc sort data=sxl out=sxl;
by _VAR_;
run;
proc print;
run;
data res(keep= _VAR_    _LBOUND_  _VALUE_   c  d  e  f   g);
merge sxl collect;
by _VAR_;
run;
proc print;
WHERE _VALUE_ GE 0;
run;
 

分析比较:代码1中给出的目标不准确,要求截断后的短铁丝都为10根时,结果一致,都为7根。

不过如果要求短铁丝为100根时,就会出现代码1的结果小于代码2. 因为代码1中的目标不严格。代码2还给出了具体的截断方法。

但是截断方法是有很多种的。可以根据调整某种截断方法的次数来修改重新求解。

当然上面仅仅满足了要求1.

为了满足要求2,我们需要枚举出截断最后一根铁丝的可能性方法。

代码3:

data ex;
do  a1=1 to int(1650/303);
      x1+1;  x2=0;   x3=0;   x4=0;   x5=0;
    do a2=1 to int(1650/251);
      x2+1;  x3=0;   x4=0;   x5=0;
          do a3=1 to int(1650/202);
        x3+1;   x4=0;   x5=0;
             do a4=1 to int(1650/151);
       x4+1;    x5=0;
                  do a5=1 to int(1650/107);
                       x5+1;
                       y=1650-(303*(x1-1)+251*(x2-1)+202*(x3-1)+151*(x4-1)+107*(x5-1));
                     if y>=0 then do ;
                                      r1=x1-1;
                    r2=x2-1;
                    r3=x3-1;
                    r4=x4-1;
                    r5=x5-1;
                             output;
           end;
                   end; 
     end;
   end;
  end;
end;
run;

对于最后一根(如果是10根的话对应了第7根,如果是100根对应了第90根)可能存在1492种截法。

按上面枚举的结果修改一下代码2约束要求即可。

如第一次尝试:

eq 10
eq 10
eq 10
eq 10
eq 9

对于1492次,我们可以用宏来完成这项工作(宏代码略),遇到有合理解即停止循环,得到符合要求的结果(一般来说是唯一的,某些情况下有几种)。

小结:1,这个是简单的整数线性规划问题。由于约束问题的选择的不严格,代码1出现了误差,并且当要求的量(短铁丝根数)变大时容易从结果中看出来。

         2,由于约束不够所以要求1会出现很多种结果,代码2只给出了其中的一种(按照默认的先多后少原则)。问题中的要求2,则增加了一个约束,这时结果的唯一性才有可能。对于多次的修改代码工作可以通过宏来完成。但是由于这个约束部分基于要求1的结果,所以还需要人工来识别。

       3,实际中生产还存在很多问题要求来约束解,如截断方式个数的要求,可以通过修改代码来完成这些要求。

       4,关于对1650mm的原料铁丝的长度要求的优化问题,则大大的增加了问题的难度,不过可以根据代码1的想法及非线性整数规划得到接近于最优值的解(不过不一定是正确解)。

参考:
巧用SAS/OR软件求解多解整数线性规划 <<五邑大学学报(自然科学版)>>2004年 第18卷 第03期 邹祥福
倪勤. S AS最优化软件速成 .北京:科学出版社, 1 9 9 8 . 2 5 — 7 0 .


相关博文

《简单线性规划问题SAS编程》上的3个想法

  1. 这些线性的问题,都是给定条件了。如果条件不定呢? 例如三个工厂,每个工厂生产同样的ABC三个产品,产品的成本随着个数增加,递减,但是只有历史数据没有实际模型拟合成本数据。这个时候问题就会更复杂了吧?

    1. 非线性优化也可以做的,先拟合历史数据,然后用OR优化。 你可以给出数据我试试。

发表评论

电子邮件地址不会被公开。 必填项已用*标注