설명
과제는 다양한 크기의 종이 제품을 잘라내는 것입니다.
고객의 주문을 충족하기 위해 대형 원시 종이 롤. 목표
필요한 롤 용지 수를 최소화하는 것입니다.
소형 모델 유형 :MIP
메인 파일 : cutstock.gms
$title 절단 스톡 - 열 생성 접근 방식(CUTSTOCK,SEQ=294)

$onText
임무는 다양한 크기의 종이 제품을 잘라내는 것입니다.
고객의 주문을 충족하기 위해 대형 원시 종이 롤. 목표
필요한 롤 용지 수를 최소화하는 것입니다.

P. C. Gilmore 및 R. E. Gomory, 선형 계획법에 대한 접근 방식
절단 재고 문제, 1부, Operations Research 9(1961), 849-859.

P. C. Gilmore 및 R. E. Gomory, 선형 계획법에 대한 접근 방식
절단 재고 문제, 2부, Operations Research 11(1963), 863-888.

키워드: 혼합 정수 선형 계획법, 재고 절단, 열 생성,
          제지 산업
$offText

i '너비' / w1*w4 /를 설정합니다.

매개변수
   r '원시 너비' / 100 /
   w(i) '너비' / w1 45, w2 36, w3 31, w4 14 /
   d(i) '수요' / w1 97, w2 610, w3 395, w4 211 /;

* 길모어-고모리 컬럼 생성 알고리즘
세트
   p '가능한 패턴' / p1*p1000 /
   pp(p) 'p의 동적 부분 집합';

매개변수 aip(i,p) 'p에서 성장하는 패턴의 너비 i 수';

* 마스터 모델
변수
   xp(p) '사용된 패턴'
   z '객관변수';

정수 변수 xp;
xp.up(p) = sum(i, d(i));

방정식
   numpat '사용된 패턴 수'
   수요(i) '수요 충족';

numpat.. z =e= sum(pp, xp(pp));

수요(i).. sum(pp, aip(i,pp)*xp(pp)) =g= d(i);

모델 마스터 / numpat, 수요 /;

* 가격 문제 - 배낭형 모델
변수 y(i) '새 패턴';

정수 변수 y;
y.up(i) = ceil(r/w(i));

방정식
   데포브
   배낭 '배낭 제약';

defobj.. z =e= 1 - sum(i, 수요.m(i)*y(i));

배낭.. sum(i, w(i)*y(i)) =l= r;

모델 가격 / defobj, 배낭 /;

* 초기화 - 초기 패턴은 단일 너비를 갖습니다.
pp(p) = ord(p) <= 카드(i);
aip(i,pp(p))$(ord(i) = ord(p)) = Floor(r/w(i));
*디스플레이 aip;

Set pi(p) '마지막 패턴 집합';
파이(p) = ord(p) = 카드(pp) + 1;

옵션 optCr = 0, limRow = 0, limCol = 0, solPrint = off;

while(카드(pp) < 카드(p),
   z를 최소화하는 rmip를 사용하여 마스터를 해결합니다.
   z를 최소화하는 mip를 사용하여 가격 책정을 해결합니다.

   break$(z.l >= -0.001);

* 발견된 마스터 모델을 개선할 수 있는 패턴
   aip(i,pi) = round(y.l(i));
   pp(pi) = 예;
   파이(p) = 파이(p-1);
);
'롤 수의 하한' 표시, master.objVal;

옵션 solPrint = 켜기;

z를 최소화하는 mip를 사용하여 마스터를 해결합니다.

매개변수
   patrep '솔루션 패턴 보고서'
   demrep '솔루션 수요 공급 보고서';

patrep('# 생성됨',p) = round(xp.l(p));
patrep(i,p)$patrep('# 생성됨',p) = aip(i,p);
patrep(i,'total') = sum(p, patrep(i,p));
patrep('생산된 수','총계') = sum(p, patrep('생산된 수',p));

demrep(i,'생산됨') = sum(p, patrep(i,p)*patrep('# 생산됨',p));
demrep(i,'수요') = d(i);
demrep(i,'over') = demrep(i,'생산됨') - demrep(i,'수요');

patrep, demrep 표시;