数学建模社区-数学中国

标题: 钢管切割问题 [打印本页]
作者: KoWuDa    时间: 2013-10-21 16:45
标题: 钢管切割问题
比如下面的题目:
原料长度:19m
客户长度:4m,6m,8m,5m
       数量:50,20,15,10

如果,规定了同一根钢管上,只能切割三种长度,这样的约束条件怎么做成参数写进LINGO呢?有大神能帮忙看看吗?
还有个问题,就是切割模式的枚举,可不可以也用LINGO来枚举呢?

因为我是要在程序里面调用LINGO的,要是自己来写枚举的算法,好麻烦的...谢谢了!

作者: wujianjack2    时间: 2013-10-21 19:08
   楼主你好！
   该问题似乎是《LINGO和Excel在数学建模中的应用》这本书的例1.7.2，书中程序如下：
MODEL:
SETS:
CUTFA/1..3/:X;
!切割方法3种,X表示对应每种切割方法的钢管原材料根数;
BUJ/1..4/:L,NEED;
!四种部件,L是部件长度,NEED是每种部件的需求量;
SHUL(CUTFA,BUJ):N;
!第i种切割方法所切割出的第j种部件的数量用Nij表示;
ENDSETS
DATA:
L=4 5 6 8;   NEED=50 10 20 15;
ZL=19;  !ZL是每根钢管原材料的长度;
ENDDATA
MIN=@SUM(CUTFA:X);
!目标函数是3种切割方法所切割的钢管总根数最少;
@FOR(BUJ(J):@SUM(CUTFA(I):N(I,J)*X(I))>=NEED(J));
!切割出的每种部件总数满足需求量;
@FOR(CUTFA(I):@SUM(BUJ(J):N(I,J)*L(J))<=ZL);
!每种切割方法切割出的部件长度之和必须小于19;
@FOR(CUTFA(I):@SUM(BUJ(J):N(I,J)*L(J))>=16);
!每种切割方法切割出的部件长度之各大于15(余料小于4);
@FOR(SHUL:@GIN(N));@FOR(CUTFA:@GIN(X));
!N和X都是整数;
END

楼主可以参考下，我就不附上结果了。
作者: qlb061    时间: 2013-10-21 19:10
本帖最后由 qlb061 于 2013-10-21 19:13 编辑
  1. <p>Lingo sample 文件中有此类模型，供参考
  2. MODEL:
  3. ! Uses Lingo's programming capability to do
  4.   on-the-fly column generation for a
  5.   cutting-stock problem;
  6. SETS:
  7.   PATTERN: COST, X;
  8.   FG: WIDTH, DEM, PRICE, Y, YIELD;
  9.   FXP( FG, PATTERN): NBR;
  10. ENDSETS

  12. DATA:
  13.   PATTERN = 1..20; ! Allow up to 20 patterns;
  14.   RMWIDTH = 19;    ! Raw material width;
  15.   FG =  F4  F6  F8  F5;!Finished goods...;
  16.   WIDTH= 4   6   8   5;!their widths...;
  17.   DEM = 50  20  15 10;!and demands;
  18.   BIGM = 999;
  19. ENDDATA

  21. SUBMODEL MASTER_PROB:
  22.   [MSTROBJ] MIN= @SUM( PATTERN( J)| J #LE# NPATS:
  23.    COST( J)*X( J));
  24.   @FOR( FG( I):
  25.    [R_DEM]
  26.     @SUM( PATTERN( J)| J #LE# NPATS:
  27.      NBR( I, J) * X( J)) >= DEM( I);
  28.   );
  29. ENDSUBMODEL

  31. SUBMODEL INTEGER_REQ:
  32.   @FOR( PATTERN: @GIN( X));
  33. ENDSUBMODEL

  35. SUBMODEL PATTERN_GEN:
  36.   [SUBOBJ] MAX = @SUM( FG( I): PRICE( I)* Y( I));
  37.   @SUM( FG( I): WIDTH( I)*Y( I)) <= RMWIDTH;
  38.   @FOR( FG( I): @GIN(Y( I)));
  39. ENDSUBMODEL

  41. CALC:

  43.   ! Set parameters;
  44.   @SET( 'DEFAULT');
  45.   @SET( 'TERSEO', 2); ! Turn off default output;

  47.   ! Max number of patterns we'll allow;
  48.   MXPATS = @SIZE( PATTERN);
  49.   ! Make first pattern an expensive super pattern;
  50.   COST( 1) = BIGM;
  51.   @FOR( FG( I): NBR( I, 1) = 1);

  53.   ! Loop as long as the reduced cost is
  54.     attractive and there is space;
  55.   NPATS = 1;
  56.   RC = -1;   ! Clearly attractive initially;
  57.   @WHILE( RC #LT# 0 #AND# NPATS #LT# MXPATS:
  58.     ! Solve for best patterns to run among ones
  59.        generated so far;
  60.     @SOLVE( MASTER_PROB);
  61.     ! Copy dual prices to PATTERN_GEN submodel;
  62.     @FOR( FG( I): PRICE( I) = -@DUAL( R_DEM( I)));
  63.     ! Generate the current most attractive pattern;
  64.     @SOLVE( PATTERN_GEN);
  65.     ! Marginal value of current best pattern;
  66.     RC = 1 - SUBOBJ;
  67.     ! Add the pattern to the Master if it is attractive;
  68.     @IFC( RC #LT# 0:
  69.        NPATS = NPATS + 1;
  70.        @FOR( FG( I): NBR( I, NPATS) = Y( I));
  71.        COST( NPATS) = 1;
  72.         );
  73.   );

  75.   ! Finally solve Master as an IP;
  76.   @SOLVE( MASTER_PROB, INTEGER_REQ);

  78. ENDCALC

  80. ! This following calc section displays the
  81.   solution in a tabular format;
  82. CALC:
  83.   ! Compute yield of each FG;
  84.   @FOR( FG( F): YIELD( F) =
  85.    @SUM( PATTERN( J)| J #LE# NPATS:
  86.     NBR( F, J) * X(J))
  87.   );
  88.   ! Compute some stats;
  89.   TOTAL_FT_USED = @SUM( PATTERN( I) | I #LE# NPATS: X( I)) * RMWIDTH;
  90.   TOTAL_FT_YIELD = @SUM( FG( I) | I #LE# NPATS: YIELD( I) * WIDTH( I));
  91.   PERC_WASTE =  100 * ( 1 - ( TOTAL_FT_YIELD / TOTAL_FT_USED)) ;
  92. ! Display the table of patterns and their usage;
  93.   FW = 6;
  94.   @WRITE( @NEWLINE( 1));
  95.   @WRITE( ' Total raws used:    ', @SUM(PATTERN( I) | I #LE# NPATS: X( I)) , @NEWLINE( 2),
  96.           ' Total feet yield:   ', TOTAL_FT_YIELD , @NEWLINE( 1),
  97.           ' Total feet used:    ', TOTAL_FT_USED , @NEWLINE( 2),
  98.           ' Percent waste:    ', @FORMAT( PERC_WASTE, '#5.2G'), '%', @NEWLINE( 1));
  99.   @WRITE( @NEWLINE( 1), 24*' ', 'Pattern:', @NEWLINE( 1));
  100.   @WRITE( '   FG  Demand Yield');
  101.   @FOR( PATTERN( I) | I #LE# NPATS: @WRITE( @FORMAT( I, '6.6G')));
  102.   @WRITE( @NEWLINE( 1));
  103.   @WRITE( ' ',FW*( NPATS+3)*'=', @NEWLINE( 1));
  104.   @FOR( FG( F):
  105.     @WRITE((FW - @STRLEN( FG( F)))*' ', FG( F), ' ',
  106.       @FORMAT( DEM( F), '6.6G'), @FORMAT( YIELD( F), '6.6G'));
  107.     @FOR( FXP( F, P) | P #LE# NPATS:
  108.       @WRITE( @IF( NBR( F, P) #GT# 0,
  109.       @FORMAT( NBR( F, P), "6.6G"), '     .')));
  110.     @WRITE( @NEWLINE( 1))
  111.   );
  112.   @WRITE( ' ',FW*( NPATS+3)*'=', @NEWLINE( 1));
  113.   @WRITE( 2*FW*' ', ' Usage:');
  114.   @WRITEFOR( PATTERN( P) | P#LE# NPATS: @FORMAT( X( P), '6.6G'));
  115.   @WRITE( @NEWLINE( 1));
  116. ENDCALC
  117. END
复制代码
作者: qlb061    时间: 2013-10-21 19:14
本帖最后由 qlb061 于 2013-10-21 19:16 编辑

Total raws used:    28

Total feet yield:   500
Total feet used:    532

Percent waste:      6.0%

                        Pattern:
   FG  Demand Yield     1     2     3     4     5     6     7
============================================================
    F4     50    50          1     4     .     .     1     1     3
    F6     20    20          1     .     3     .     .     1     1
    F8     15    15          1     .     .     2     .     1     .
    F5     10    12          1     .     .     .     3     .     .
============================================================
                  Usage:     0     0     0     4     4     7    13
作者: qlb061    时间: 2013-10-21 19:21
本帖最后由 qlb061 于 2013-10-21 19:22 编辑
wujianjack2 发表于 2013-10-21 19:08
楼主你好！
   该问题似乎是《LINGO和Excel在数学建模中的应用》这本书的例1.7.2，书中程序如下：
MOD ...

谢谢加分!
作者: wujianjack2    时间: 2013-10-21 19:32
qlb061 发表于 2013-10-21 19:21
谢谢加分!

   你应该被奖励，谢谢你的回答与支持！
作者: KoWuDa    时间: 2013-10-22 15:36
谢谢你们的回复啊,我这个就是例程,但我加上了一个规定,一根材料只能切三种长度.
我先得学习下你们发的代码.
稍后我会继续提问的,因为这个问题我是在程序里使用的,长度不固定,种类也不固定..
作者: KoWuDa    时间: 2013-10-22 16:33
本帖最后由 wujianjack2 于 2013-10-23 00:00 编辑

MODEL:
SETS:
CUTFA/1..4/:X;
!切割方法3种,X表示对应每种切割方法的钢管原材料根数;
BUJ/1..4/:L,NEED;
!四种部件,L是部件长度,NEED是每种部件的需求量;
SHUL(CUTFA,BUJ):N;
!第i种切割方法所切割出的第j种部件的数量用Nij表示;
ENDSETS
DATA:
L=4 5 6 8;   NEED=50 10 20 15;
ZL=19;  !ZL是每根钢管原材料的长度;
ENDDATA
MIN=@SUM(CUTFA:X);
!目标函数是3种切割方法所切割的钢管总根数最少;
@FOR(BUJ(J):@SUM(CUTFA(I):N(I,J)*X(I))>=NEED(J));
!切割出的每种部件总数满足需求量;
@FOR(CUTFA(I):@SUM(BUJ(J):N(I,J)*L(J))<=ZL);
!每种切割方法切割出的部件长度之和必须小于19;
@FOR(CUTFA(I):@SUM(BUJ(J):N(I,J)*L(J))>=16);
!每种切割方法切割出的部件长度之各大于15(余料小于4);
@FOR(SHUL:@GIN(N));@FOR(CUTFA:@GIN(X));
!N和X都是整数;
END
你们帮我看看这个解法,这里的X,实际上是规定了最后的切割模式的,我就没看出来,哪里是限制他只能切三种材料的地方.那个地方要是改成了4或10,就是切割模式被修改了...不符合我的要求啊.

作者: KoWuDa    时间: 2013-10-22 16:51
这是别人给的一种解法,可我仔细看了下,那个X不就是切割模式吗,他在限定切割的长度种类的时候,不也同时限定了切割模式了吗!这可不符合我的要求...我的切割模式不能固定的...
model:
SETS:
NEEDS/1..4/:LENGTH,b;
CUTS/1..3/:X;
PATTERNS(NEEDS,CUTS):R;
ENDSETS

DATA:
LENGTH=4 5 6 8;
b=50 10 20 15;
CAPACITY=19;
ENDDATA
min=@SUM(CUTS:X);
@FOR(NEEDS(I):@SUM(CUTS(J):X(J)*R(I,J))>b(I));
@FOR(CUTS(J):@SUM(NEEDS(I):LENGTH(I)*R(I,J))<CAPACITY;
@SUM(NEEDS(I):LENGTH(I)*R(I,J))>CAPACITY-@MIN(NEEDS:LENGTH)+1);
@SUM(CUTS:X)>26;
@SUM(CUTS:X)<31;
@FOR(CUTS(I)|I#LT#@SIZE(CUTS):X(I)>X(I+1));
@FOR(CUTS:@GIN(X));
@FOR(PATTERNS:@GIN(R));
end
作者: KoWuDa    时间: 2013-10-22 16:51
  1. model:
  2. SETS:
  3. NEEDS/1..4/:LENGTH,b;
  4. CUTS/1..3/:X;
  5. PATTERNS(NEEDS,CUTS):R;
  6. ENDSETS

  8. DATA:
  9. LENGTH=4 5 6 8;
  10. b=50 10 20 15;
  11. CAPACITY=19;
  12. ENDDATA
  13. min=@SUM(CUTS:X);
  14. @FOR(NEEDS(I):@SUM(CUTS(J):X(J)*R(I,J))>b(I));
  15. @FOR(CUTS(J):@SUM(NEEDS(I):LENGTH(I)*R(I,J))<CAPACITY;
  16. @SUM(NEEDS(I):LENGTH(I)*R(I,J))>CAPACITY-@MIN(NEEDS:LENGTH)+1);
  17. @SUM(CUTS:X)>26;
  18. @SUM(CUTS:X)<31;
  19. @FOR(CUTS(I)|I#LT#@SIZE(CUTS):X(I)>X(I+1));
  20. @FOR(CUTS:@GIN(X));
  21. @FOR(PATTERNS:@GIN(R));
  22. end
复制代码
作者: qlb061    时间: 2013-10-22 18:30
本帖最后由 qlb061 于 2013-10-22 20:30 编辑

  x
作者: KoWuDa    时间: 2013-10-22 21:14
  1. MODEL:
  2. ! Uses Lingo's programming capability to do
  3.   on-the-fly column generation for a
  4.   cutting-stock problem;
  5. SETS:
  6.   PATTERN: COST, X;
  7.   FG: WIDTH, DEM, PRICE, Y, YIELD;
  8.   FXP( FG, PATTERN): NBR;
  9. ENDSETS

  11. DATA:
  12.   PATTERN = 1..10; ! Allow up to 20 patterns;
  13.   RMWIDTH = 6000;    ! Raw material width;
  14.   FG =  F4  F6  F8 F9 F10;!Finished goods...;
  15.   WIDTH= 1816 916 616 439 602;!their widths...;
  16.   DEM = 1000 600 200 250 500;!and demands;
  17.   BIGM = 999;
  18. ENDDATA

  20. SUBMODEL MASTER_PROB:
  21.   [MSTROBJ] MIN= @SUM( PATTERN( J)| J #LE# NPATS:
  22.    COST( J)*X( J));
  23.   @FOR( FG( I):
  24.    [R_DEM]
  25.     @SUM( PATTERN( J)| J #LE# NPATS:
  26.      NBR( I, J) * X( J)) >= DEM( I);
  27.   );
  28. ENDSUBMODEL

  30. SUBMODEL INTEGER_REQ:
  31.   @FOR( PATTERN: @GIN( X));
  32. ENDSUBMODEL

  34. SUBMODEL PATTERN_GEN:
  35.   [SUBOBJ] MAX = @SUM( FG( I): PRICE( I)* Y( I));
  36.   @SUM( FG( I): WIDTH( I)*Y( I)) <= RMWIDTH;
  37.   @FOR( FG( I): @GIN(Y( I)));
  38. ENDSUBMODEL

  40. CALC:

  42.   ! Set parameters;
  43.   @SET( 'DEFAULT');
  44.   @SET( 'TERSEO', 2); ! Turn off default output;

  46.   ! Max number of patterns we'll allow;
  47.   MXPATS = @SIZE( PATTERN);
  48.   ! Make first pattern an expensive super pattern;
  49.   COST( 1) = BIGM;
  50.   @FOR( FG( I): NBR( I, 1) = 1);

  52.   ! Loop as long as the reduced cost is
  53.     attractive and there is space;
  54.   NPATS = 1;
  55.   RC = -1;   ! Clearly attractive initially;
  56.   @WHILE( RC #LT# 0 #AND# NPATS #LT# MXPATS:
  57.     ! Solve for best patterns to run among ones
  58.        generated so far;
  59.     @SOLVE( MASTER_PROB);
  60.     ! Copy dual prices to PATTERN_GEN submodel;
  61.     @FOR( FG( I): PRICE( I) = -@DUAL( R_DEM( I)));
  62.     ! Generate the current most attractive pattern;
  63.     @SOLVE( PATTERN_GEN);
  64.     ! Marginal value of current best pattern;
  65.     RC = 1 - SUBOBJ;
  66.     ! Add the pattern to the Master if it is attractive;
  67.     @IFC( RC #LT# 0:
  68.        NPATS = NPATS + 1;
  69.        @FOR( FG( I): NBR( I, NPATS) = Y( I));
  70.        COST( NPATS) = 1;
  71.         );
  72.   );

  74.   ! Finally solve Master as an IP;
  75.   @SOLVE( MASTER_PROB, INTEGER_REQ);

  77. ENDCALC

  79. ! This following calc section displays the
  80.   solution in a tabular format;
  81. CALC:
  82.   ! Compute yield of each FG;
  83.   @FOR( FG( F): YIELD( F) =
  84.    @SUM( PATTERN( J)| J #LE# NPATS:
  85.     NBR( F, J) * X(J))
  86.   );
  87.   ! Compute some stats;
  88.   TOTAL_FT_USED = @SUM( PATTERN( I) | I #LE# NPATS: X( I)) * RMWIDTH;
  89.   TOTAL_FT_YIELD = @SUM( FG( I) | I #LE# NPATS: YIELD( I) * WIDTH( I));
  90.   PERC_WASTE =  100 * ( 1 - ( TOTAL_FT_YIELD / TOTAL_FT_USED)) ;
  91. ! Display the table of patterns and their usage;
  92.   FW = 6;
  93.   @WRITE( @NEWLINE( 1));
  94.   @WRITE( ' Total raws used:    ', @SUM(PATTERN( I) | I #LE# NPATS: X( I)) , @NEWLINE( 2),
  95.           ' Total feet yield:   ', TOTAL_FT_YIELD , @NEWLINE( 1),
  96.           ' Total feet used:    ', TOTAL_FT_USED , @NEWLINE( 2),
  97.           ' Percent waste:    ', @FORMAT( PERC_WASTE, '#5.2G'), '%', @NEWLINE( 1));
  98.   @WRITE( @NEWLINE( 1), 24*' ', 'Pattern:', @NEWLINE( 1));
  99.   @WRITE( '   FG  Demand Yield');
  100.   @FOR( PATTERN( I) | I #LE# NPATS: @WRITE( @FORMAT( I, '6.6G')));
  101.   @WRITE( @NEWLINE( 1));
  102.   @WRITE( ' ',FW*( NPATS+3)*'=', @NEWLINE( 1));
  103.   @FOR( FG( F):
  104.     @WRITE((FW - @STRLEN( FG( F)))*' ', FG( F), ' ',
  105.       @FORMAT( DEM( F), '6.6G'), @FORMAT( YIELD( F), '6.6G'));
  106.     @FOR( FXP( F, P) | P #LE# NPATS:
  107.       @WRITE( @IF( NBR( F, P) #GT# 0,
  108.       @FORMAT( NBR( F, P), "6.6G"), '     .')));
  109.     @WRITE( @NEWLINE( 1))
  110.   );
  111.   @WRITE( ' ',FW*( NPATS+3)*'=', @NEWLINE( 1));
  112.   @WRITE( 2*FW*' ', ' Usage:');
  113.   @WRITEFOR( PATTERN( P) | P#LE# NPATS: @FORMAT( X( P), '6.6G'));
  114.   @WRITE( @NEWLINE( 1));
  115. ENDCALC
  116. END
复制代码
请问如果有十种长度,可以切六种规格,那个六在哪改呢



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5