简单线性规划问题SAS编程之二

钢管长度定制问题:

假设实际生产需要303mm,251mm,202mm,151mm,107mm的钢管各100根【理论上需要一根(303+251+202+151+107)*100=101400的长钢管,这样才不会多余的边角料浪费,实际上这么长的一根钢管供货商是不便于提供的】。现供货商只能提供长度相同且长度范围为1300mm至1650mm的钢管,请问需要向订货商定制多少根和长度为多少的钢管才能保证浪费最少(即边角料的总长度最小)?

引用:http://www.mysas.net/forum/viewtopic.php?f=4&t=4768&start=10   ID:tianlai888

ps:原文中的表达不够清晰,且10根算起来不过瘾,故修改。

代码:

options nomprint;

data ex;
input  _type_$ _rhs_;
cards;
ge 100
ge 100
ge 100
ge 100
ge 100
min .
upperbd .
integer .
;
run;
%macro sxl(out=out);

proc sql;
create table &out.
  (
    numm num format = 12.       label = ‘number’,
    i  num format = 12. label = ‘length’

  );
quit;

%do i = 1300 %to 1650;

data _aa (keep=c d e f g i );
   a1=int(&i./303);
   a2=int(&i./251);
   a3=int(&i./202);
   a4=int(&i./151);
   a5=int(&i./107);
   w=&i.-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=&i.-x;
                         if x>w and x<=&i. then do;
                                                     i+1;
                                                     output;
                                                  end;
                      end;
                  end;
             end;
           end;
     end;
run;

proc sort data=_aa out=_aa(drop=i);
by descending i ;
run;

data _null_;
set _aa(drop=_all_) nobs=rows;
call symput(‘nobs’,rows);
stop;
run;

data _collect(drop=i);
LENGTH _VAR_ $8.;
set _aa;
i+1;
_VAR_=catt(‘COL’,i);
run;

proc transpose data=_aa out=_aa1;
run;
data _bb(drop=i);
do i =1 to &nobs.;
    a=1;
    b=100;
    c+1;
    output;
    end;
    run;
    proc transpose data=_bb out=_bb1;
    run;

data ex1(drop=_NAME_);
set _aa1 _bb1;
run;

data ex2;
merge ex1 ex ;
run;

ods listing close;
ods output solutionsummary=_p;
proc lp data=ex2  IMAXIT=500;
run;
ods _all_ close;
ods listing ;

proc sql noprint;
select CVALUE1  
   into :numm from _p;

    data _tem;
      numm=&numm.;
      i  = &i.;
    run;

    proc sql;       
      insert into
        &out.
      select
        *
      from
        _tem;
    quit;

%end;
data &out.;
   set &out.;
   length=numm*i;
   if numm ne lag(numm) then output;
   run;

proc sort data=&out. out=&out.;
   by length ;
   run;
proc print data=&out.;
run;
%mend sxl;
%sxl;

result:

Obs            numm               i    length

  1              69            1471    101499
  2              67            1515    101505
  3              65            1562    101530
  4              72            1411    101592
  5              63            1613    101619
  6              77            1320    101640
  7              75            1360    102000
  8              78            1310    102180
  9              70            1460    102200
10              68            1509    102612
11              66            1557    102762
12              73            1408    102784
13              64            1608    102912
14              76            1357    103132
15              79            1307    103253
16              71            1457    103447
17              80            1300    104000
18              74            1406    104044

从结果中看出,当定制1471mm的钢管时,浪费最少。需要定制69根,浪费101499-101400=99mm。

小结:实际程序跑了100s,理论上猜测应该少于30s,代码还有待优化。

简单线性规划问题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 .