钢管切割问题

KoWuDa

比如下面的题目:
原料长度:19m
客户长度:4m,6m,8m,5m
       数量:50,20,15,10

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

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

KoWuDa

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
   
10. 
    
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
    
19. 
    
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
    
29. 
    
30. SUBMODEL INTEGER_REQ:
    
31.   @FOR( PATTERN: @GIN( X));
    
32. ENDSUBMODEL
    
33. 
    
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
    
39. 
    
40. CALC:
    
41. 
    
42.   ! Set parameters;
    
43.   @SET( 'DEFAULT');
    
44.   @SET( 'TERSEO', 2); ! Turn off default output;
    
45. 
    
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);
    
51. 
    
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.   );
    
73. 
    
74.   ! Finally solve Master as an IP;
    
75.   @SOLVE( MASTER_PROB, INTEGER_REQ);
    
76. 
    
77. ENDCALC
    
78. 
    
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

复制代码

请问如果有十种长度,可以切六种规格,那个六在哪改呢

qlb061

  x

KoWuDa

1. model:
   
2. SETS:
   
3. NEEDS/1..4/:LENGTH,b;
   
4. CUTS/1..3/:X;
   
5. PATTERNS(NEEDS,CUTS):R;
   
6. ENDSETS
   
7. 
   
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

复制代码

KoWuDa

这是别人给的一种解法,可我仔细看了下,那个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

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

谢谢你们的回复啊,我这个就是例程,但我加上了一个规定,一根材料只能切三种长度.
我先得学习下你们发的代码.
稍后我会继续提问的,因为这个问题我是在程序里使用的,长度不固定,种类也不固定..

wujianjack2

qlb061 发表于 2013-10-21 19:21
谢谢加分!

   你应该被奖励，谢谢你的回答与支持！

qlb061

wujianjack2 发表于 2013-10-21 19:08
楼主你好！
   该问题似乎是《LINGO和Excel在数学建模中的应用》这本书的例1.7.2，书中程序如下：
MOD ...

谢谢加分!

qlb061

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