SAS中文论坛

标题: 求助：一道比较难的计算题？ 后面另附：反推的问题 [打印本页]

---

作者: shiyiming    时间: 2009-1-20 01:09
标题: 求助：一道比较难的计算题？ 后面另附：反推的问题
一批铁丝，数量不限，每一根铁丝长 1650 mm ,现需要截取下列品种、长度、数量的铁丝：

品种         长度/mm        需要数量/根
a1        303        10
a2        251        10
a3        202        10
a4        151        10
a5        107        10

注：铁丝的长度、品种的个数、品种的长度、需要数量都是变量。

怎样计算，在达到需要截取的品种、长度、数量的前提下，使用的铁丝根数最少，浪费的最小？

求助：怎样用SAS编写这样的计算程序？ 哪里有用SAS编写的这方面的资料？


谢谢！！！

---

作者: shiyiming    时间: 2009-1-20 08:47
标题: Re: 求助：一道比较难的计算题？
这难吗？小学初中的二元一次解方程而已啊。既不需要建模，也不需要运筹，甚至没必要用SAS来做。 <!-- s:shock: --><img src="{SMILIES_PATH}/icon_eek.gif" alt=":shock:" title="Shocked" /><!-- s:shock: -->

---

作者: shiyiming    时间: 2009-1-20 13:07
标题: Re: 求助：一道比较难的计算题？
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

最少需要7根。

你用lingo或者lindo CHECK 一下，应该没问题。

---

作者: shiyiming    时间: 2009-1-20 20:34
标题: Re: 求助：一道比较难的计算题？
谢谢sxlion 老师的解答!!!!!!
   
      真是“难者不会，会者不难”！真羡慕您们！

我是想问？怎样编程得到截取的方法，也就是怎样在每根铁丝上合理地截取哪些品种，截多少根，这样使每根铁丝的浪费最小？

例如：我一个品种一个品种地套，套出了一种截取方法：
第1根  303截取4根  202截取2根  用去长度1616  浪费34mm
第2根  303截取4根  202截取2根  用去长度1616  浪费34mm
第3根  303截取2根  251截取3根  151截取1根  107截取1根  用去长度1617  浪费33mm
第4根  251截取5根  202截取1根  151截取1根  用去长度1608 浪费42mm
第5根  251截取2根  202截取4根  151截取2根  用去长度1612 浪费38mm
第6根  202截取1根  151截取6根  107截取5根  用去长度1643 浪费7mm
第7根  107截取4根  用去长度428  还剩1222mm       
这样5个品种都截取了10根，用去7根，共计浪费了188mm，第7根还剩1222mm，

如果品种多，数量大，就没法套了。所以求助高人帮助！！  谢谢！

---

作者: shiyiming    时间: 2009-1-23 21:59
标题: Re: 求助：一道比较难的计算题？
求助高人:帮帮忙!!
如何让程序循环 , 排列出所有在每根铁丝上截取的方法?

---

作者: shiyiming    时间: 2009-1-24 02:48
标题: Re: 求助：一道比较难的计算题？
to tianlai888
楼主您的贴已经很成功啦，已经套住总管（当然不能总管可能是发明新的算法，您可能要花钱跟他买）和sxlion了，就不要再有别的奢求啦。

---

作者: shiyiming    时间: 2009-1-28 20:52
标题: Re: 求助：一道比较难的计算题？
这道题目是钢管下料问题。可以做的。
解决方法如下 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）&gt;=10（就是每种策略可以带来a1钢管的数，和采取这种策略的钢管数目的乘积之和大于10）
同理sum（yn*yvn2）&gt;=10
sum（yn*yvn3）&gt;=10
sum（yn*yvn4）&gt;=10 yn&gt;=0
然后问题转化为每种策略用几根钢管的整数规划问题。y大于等于0,然后通过lindo的整肃规划编程就可以求出yn了，把大于o的钢管数目的策略和yn求出就可以了。整数规划已经是运筹学中可以解决的问题了，lindo也不难学，而且解决规划问题lindo要比sas专业。

---

作者: shiyiming    时间: 2009-1-29 10:56
标题: Re: 求助：一道比较难的计算题？
我是老昏了头，给苦根煮了这么多豆子，我老得又笨又蠢，害死了苦根。
我一直还以为整数规划只是在机缘巧合的情况下才能在我老死之前算出来呢，却不知现代高科技已精进如斯。
恳请楼主原谅一个庄稼人的胡说八道。

---

作者: shiyiming    时间: 2009-1-29 14:06
标题: Re: 求助：一道比较难的计算题？
先给各位老师拜个年！ 祝各位老师牛年身体健康！万事如意！！
徐福贵老师，您好！ 千万别这样说，您的回复我感谢还来不急呢。

   我也觉得您说的有道理（这样的程序可能一辈子也跑不完）。
在长度1650米的钢管上，截取五个品种的需求长度，如果按每根允许浪费30mm的情况下，我枚举了所有的可行策略。

data  aa (drop=a1-a5 w);
a1=int(1650/303);
a2=int(1650/251);
a3=int(1650/202);
a4=int(1650/151);
a5=int(1650/107);
w=1650-30; /*每根允许浪费30mm*/
  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&gt;w and x&lt;=1650 then
  output;
end;   
end;
end;
end;
end;
run;
proc sort data=aa out=aa1;
by y ;
run;

这样在每根上有95种截取方式，现在有五个品种每种都要10根，就需要1650mm的钢管至少7根。
如果再枚举所有的排列方式(95^7)，将是一个天文数字可能一辈子也跑不完。所以我也是个又笨又蠢的人。我实在想不出其他方法。

再想请教 xgghxkhuang 和各位老师：
   接下来如何应用运筹学的整数规划或者用其他思路，解决在7根钢管上，每根截取哪些品种，多少根。这样既完成任务，又节约材料。
它需要枚举所有的可行策略吗？能不能稍微讲详细点。
谢谢！！！

---

作者: shiyiming    时间: 2009-2-2 15:26
标题: Re: 求助：一道比较难的计算题？
楼主千万别随便叫人老师，泥巴腿子消受不起。我就没有老师，要有也早给我气死啦。

---

作者: shiyiming    时间: 2009-2-2 23:16
标题: Re: 求助：一道比较难的计算题？
谢谢徐福贵老师！您太有才了！！
三人同行必有我师，更何况我是SAS初学者。
您这段程序够我消化一阵。这比我一个个的套浪费小多了。谢谢！！

---

作者: shiyiming    时间: 2009-2-3 15:44
标题: Re: 求助：一道比较难的计算题？
[quote=&quot;xgghxkhuang&quot;: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）&gt;=10（就是每种策略可以带来a1钢管的数，和采取这种策略的钢管数目的乘积之和大于10）
同理sum（yn*yvn2）&gt;=10
sum（yn*yvn3）&gt;=10
sum（yn*yvn4）&gt;=10 yn&gt;=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&gt;w and x&lt;=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软件求解多解整数线性规划 &lt;&lt;五邑大学学报(自然科学版)&gt;&gt;2004年 第18卷 第03期  邹祥福
倪勤． S AS最优化软件速成  ．北京：科学出版社， 1 9 9 8 ． 2 5 — 7 0 ．

---

作者: shiyiming    时间: 2009-2-3 23:23
标题: Re: 求助：一道比较难的计算题？
谢谢sxlion 老师!!
     这些数字在您聪慧的头脑和灵巧的双手下，如鱼得水，变换自如。让我真正体验了一下应用SAS编程的奇妙。
您的答案更精确。还得多多向您学习，请教！！

---

作者: shiyiming    时间: 2009-2-4 16:36
标题: Re: 求助：一道比较难的计算题？
兄弟们好勤奋。知道为什么SAS能选这个网站了。哎呀，惭愧死了，好久没有碰SAS了。

---

作者: shiyiming    时间: 2009-2-4 16:50
标题: Re: 求助：一道比较难的计算题？ 后面另附：反推的问题
再请教各位老师，上一问题的反推？

一段钢管上，需要截取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    时间: 2009-2-5 14:09
标题: Re: 求助：一道比较难的计算题？ 后面另附：反推的问题
你的第一问题我还没回答完。
因为我上面给出的结果是有很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&gt;=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&gt;w and x&lt;=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    时间: 2009-2-6 12:43
标题: Re: 求助：一道比较难的计算题？ 后面另附：反推的问题
问题2，我算的结果是：
7根 1460mm
浪费：10220-10140=80mm
不知道对吗？
（代码优化中）

---

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

谢谢！！！！

---

作者: shiyiming    时间: 2009-2-9 11:46
标题: Re: 求助：一道比较难的计算题？ 后面另附：反推的问题
问题一的后一半可以用宏来完成。ps：后一半问题的解答对于你来说有什么实际意义吗？

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

---

欢迎光临 SAS中文论坛 (https://mysas.net/forum/)

Powered by Discuz! X3.2