求助：一道比较难的计算题？ 后面另附：反推的问题

shiyiming

谢谢徐福贵老师！您太有才了！！
三人同行必有我师，更何况我是SAS初学者。
您这段程序够我消化一阵。这比我一个个的套浪费小多了。谢谢！！

shiyiming

[quote="xgghxkhuang":1n2zpv82]这道题目是钢管下料问题。可以做的。
解决方法如下 1首先取得钢管长度1650米
四种需求长度，求得所有钢管的可行策略
算法如下首先取最多的a1钢管数x1，然后取x1-1，然后x2-2直到0
对内层算在1650-x1*a1下最多a2的钢管数，a2-1，a2-2
枚举的算出所有可行的策略。
求y1+y2 +.....yn的最小数目（代表策略n的钢管根数）
设策略n的带来a1的钢管数为yvn1
那么sum（yn*yvn1）>=10（就是每种策略可以带来a1钢管的数，和采取这种策略的钢管数目的乘积之和大于10）
同理sum（yn*yvn2）>=10
sum（yn*yvn3）>=10
sum（yn*yvn4）>=10 yn>=0
然后问题转化为每种策略用几根钢管的整数规划问题。y大于等于0,然后通过lindo的整肃规划编程就可以求出yn了，把大于o的钢管数目的策略和yn求出就可以了。整数规划已经是运筹学中可以解决的问题了，lindo也不难学，而且解决规划问题lindo要比sas专业。[/quote:1n2zpv82]

这个思路非常正确。lindo 非常强大，但是不如sas方便。
代码：

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;
                 i+1;
                         if x>w and x<=1650 then
                         output;
                      end;
                  end;
             end;
           end;
     end;
run;
proc sort data=aa out=aa(drop=i);
by descending i ;
run;


proc transpose data=aa out=aa1;
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 lp data=ex2;
run;



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

shiyiming

谢谢sxlion 老师!!
     这些数字在您聪慧的头脑和灵巧的双手下，如鱼得水，变换自如。让我真正体验了一下应用SAS编程的奇妙。
您的答案更精确。还得多多向您学习，请教！！

shiyiming

兄弟们好勤奋。知道为什么SAS能选这个网站了。哎呀，惭愧死了，好久没有碰SAS了。

shiyiming

再请教各位老师，上一问题的反推？

一段钢管上，需要截取303、251、202、151、107五个品种的钢管各10根。
那么在一根长为10140=（303+251+202+151+107）*10的钢管上截取，这是最优的解，
但实际工作中这一根太长做不到，需要截成几根（几根长度相等整数）。截取的长度范围在1300-1650之间。

求助：
假设截取长度为x,需要y根
y1截取  303*a1  251*b1  202*c1  151*d1  107*e1
y2截取  303*a2  251*b2  202*c2  151*d2  107*e2
y3截取  303*a3  251*b3  202*c3  151*d3  107*e3
......
a1+a2+a3+...=10
b1+b2+b3+...=10
...
如何截取求得最优的解，既完成任务，又浪费最小？

谢谢！！

shiyiming

你的第一问题我还没回答完。
因为我上面给出的结果是有很N种不同截法的（假如短铁丝需要根数的不是10而是100的话，N有上限但是更大，这个N值不好求）。

根据你的需要的最省截法，一般来说截法是唯一的（某些情况下有几种）。

方法如下：
下面是需要一个一个的试的，试到第19个的时候（理论上最多需要试1492次），就得到你上面拼凑出来的结果，即第7根截4段107mm的铁丝，该段铁丝剩下的最多。


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;
proc sort data=ex out=ex2(keep=r1-r5 y);
by desending y;
run;
proc print;
run;

/* second stage */
/*try one by one */

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;
         a=1;
         b=100;
                 c=1;
         output;
                 end;
do i =2 to 334;
    a=1;
        b=200;
        c+1;
        output;
        end;
        run;
        proc print;
        run;
        proc transpose data=bb out=bb1;
        run;

data ex1(keep=col1-col334);
set aa1 bb1;
run;

data ex;
input  _type_$ _rhs_;
cards;
eq 10       /* update here*/
eq 10       /*试的时候修改本区域*/
eq 10
eq 10
eq 6
min .
upperbd .
integer .
;
run;
data ex2;
merge ex1 ex ;
run;
proc print;
run;
proc lp data=ex2 primalout=p IMAXIT=500;
run;

data sxl;
set p;
where _VALUE_ NE 0;
run;
proc print;
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_    _VALUE_   c  d  e  f   g);
merge sxl collect;
by _VAR_;

run;
proc print;
WHERE _VALUE_ GE 0;
run;

shiyiming

问题2，我算的结果是：
7根 1460mm
浪费：10220-10140=80mm
不知道对吗？
（代码优化中）

shiyiming

谢谢 sxlion 老师的回复！
   您的上一段程序，我运行时，总发现错误，如：_VAR_=catt('COL',i);  这句。原来是SAS V8版不能用这句。
这几天我到处找，终于下载，安装完成SAS 9.1版。
我的问题2，还没来得及做。我有一个笨想法：
在截取的长度范围1300-1650中，一个一个的试，既长度取1300、1301、1302.....1650。
再用您教的第一问题的解法，找出最小浪费的截法，比较麻烦。
请教您有什么好的建议？

谢谢！！！！

shiyiming

问题一的后一半可以用宏来完成。ps：后一半问题的解答对于你来说有什么实际意义吗？

问题2用宏循环方法，不过时间花得很长，请问那位有秒级的代码吗？