钢管切割问题
比如下面的题目:原料长度:19m
客户长度:4m,6m,8m,5m
数量:50,20,15,10
如果,规定了同一根钢管上,只能切割三种长度,这样的约束条件怎么做成参数写进LINGO呢?有大神能帮忙看看吗?
还有个问题,就是切割模式的枚举,可不可以也用LINGO来枚举呢?
因为我是要在程序里面调用LINGO的,要是自己来写枚举的算法,好麻烦的...谢谢了!
楼主你好！
该问题似乎是《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:13 编辑
<p>Lingo sample 文件中有此类模型，供参考
MODEL:
! Uses Lingo's programming capability to do
on-the-fly column generation for a
cutting-stock problem;
SETS:
PATTERN: COST, X;
FG: WIDTH, DEM, PRICE, Y, YIELD;
FXP( FG, PATTERN): NBR;
ENDSETS
DATA:
PATTERN = 1..20; ! Allow up to 20 patterns;
RMWIDTH = 19; ! Raw material width;
FG = F4 F6 F8 F5;!Finished goods...;
WIDTH= 4 6 8 5;!their widths...;
DEM = 50 20 15 10;!and demands;
BIGM = 999;
ENDDATA
SUBMODEL MASTER_PROB:
MIN= @SUM( PATTERN( J)| J #LE# NPATS:
COST( J)*X( J));
@FOR( FG( I):
@SUM( PATTERN( J)| J #LE# NPATS:
NBR( I, J) * X( J)) >= DEM( I);
);
ENDSUBMODEL
SUBMODEL INTEGER_REQ:
@FOR( PATTERN: @GIN( X));
ENDSUBMODEL
SUBMODEL PATTERN_GEN:
MAX = @SUM( FG( I): PRICE( I)* Y( I));
@SUM( FG( I): WIDTH( I)*Y( I)) <= RMWIDTH;
@FOR( FG( I): @GIN(Y( I)));
ENDSUBMODEL
CALC:
! Set parameters;
@SET( 'DEFAULT');
@SET( 'TERSEO', 2); ! Turn off default output;
! Max number of patterns we'll allow;
MXPATS = @SIZE( PATTERN);
! Make first pattern an expensive super pattern;
COST( 1) = BIGM;
@FOR( FG( I): NBR( I, 1) = 1);
! Loop as long as the reduced cost is
attractive and there is space;
NPATS = 1;
RC = -1; ! Clearly attractive initially;
@WHILE( RC #LT# 0 #AND# NPATS #LT# MXPATS:
! Solve for best patterns to run among ones
generated so far;
@SOLVE( MASTER_PROB);
! Copy dual prices to PATTERN_GEN submodel;
@FOR( FG( I): PRICE( I) = -@DUAL( R_DEM( I)));
! Generate the current most attractive pattern;
@SOLVE( PATTERN_GEN);
! Marginal value of current best pattern;
RC = 1 - SUBOBJ;
! Add the pattern to the Master if it is attractive;
@IFC( RC #LT# 0:
NPATS = NPATS + 1;
@FOR( FG( I): NBR( I, NPATS) = Y( I));
COST( NPATS) = 1;
);
);
! Finally solve Master as an IP;
@SOLVE( MASTER_PROB, INTEGER_REQ);
ENDCALC
! This following calc section displays the
solution in a tabular format;
CALC:
! Compute yield of each FG;
@FOR( FG( F): YIELD( F) =
@SUM( PATTERN( J)| J #LE# NPATS:
NBR( F, J) * X(J))
);
! Compute some stats;
TOTAL_FT_USED = @SUM( PATTERN( I) | I #LE# NPATS: X( I)) * RMWIDTH;
TOTAL_FT_YIELD = @SUM( FG( I) | I #LE# NPATS: YIELD( I) * WIDTH( I));
PERC_WASTE = 100 * ( 1 - ( TOTAL_FT_YIELD / TOTAL_FT_USED)) ;
! Display the table of patterns and their usage;
FW = 6;
@WRITE( @NEWLINE( 1));
@WRITE( ' Total raws used: ', @SUM(PATTERN( I) | I #LE# NPATS: X( I)) , @NEWLINE( 2),
' Total feet yield: ', TOTAL_FT_YIELD , @NEWLINE( 1),
' Total feet used: ', TOTAL_FT_USED , @NEWLINE( 2),
' Percent waste: ', @FORMAT( PERC_WASTE, '#5.2G'), '%', @NEWLINE( 1));
@WRITE( @NEWLINE( 1), 24*' ', 'Pattern:', @NEWLINE( 1));
@WRITE( ' FG Demand Yield');
@FOR( PATTERN( I) | I #LE# NPATS: @WRITE( @FORMAT( I, '6.6G')));
@WRITE( @NEWLINE( 1));
@WRITE( ' ',FW*( NPATS+3)*'=', @NEWLINE( 1));
@FOR( FG( F):
@WRITE((FW - @STRLEN( FG( F)))*' ', FG( F), ' ',
@FORMAT( DEM( F), '6.6G'), @FORMAT( YIELD( F), '6.6G'));
@FOR( FXP( F, P) | P #LE# NPATS:
@WRITE( @IF( NBR( F, P) #GT# 0,
@FORMAT( NBR( F, P), "6.6G"), ' .')));
@WRITE( @NEWLINE( 1))
);
@WRITE( ' ',FW*( NPATS+3)*'=', @NEWLINE( 1));
@WRITE( 2*FW*' ', ' Usage:');
@WRITEFOR( PATTERN( P) | P#LE# NPATS: @FORMAT( X( P), '6.6G'));
@WRITE( @NEWLINE( 1));
ENDCALC
END
本帖最后由 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:22 编辑
wujianjack2 发表于 2013-10-21 19:08 static/image/common/back.gif
楼主你好！
该问题似乎是《LINGO和Excel在数学建模中的应用》这本书的例1.7.2，书中程序如下：
MOD ...
谢谢加分! qlb061 发表于 2013-10-21 19:21 static/image/common/back.gif
谢谢加分!
你应该被奖励，谢谢你的回答与支持！ 谢谢你们的回复啊,我这个就是例程,但我加上了一个规定,一根材料只能切三种长度.
我先得学习下你们发的代码.
稍后我会继续提问的,因为这个问题我是在程序里使用的,长度不固定,种类也不固定.. 本帖最后由 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,就是切割模式被修改了...不符合我的要求啊.
这是别人给的一种解法,可我仔细看了下,那个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 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
页:
[1]
2