설명

옥수수 한 부셸을 들고 거위를 동반한 농부
늑대가 강에 왔습니다. 그는 할 수 있는 보트를 발견했습니다
자신과 그의 소유물 중 하나(옥수수, 거위 또는
늑대 - 하지만 더 이상은 아닙니다. 이제 그는 옥수수를 혼자 둘 수 없었습니다.
거위도, 거위도 늑대와 함께 혼자 있는 것도 아니고,
다른 하나를 소비하십시오. 그럼에도 불구하고 그는 자신을 얻는 데 성공했습니다.
그리고 그의 물건은 무사히 강을 건넜습니다.

소형 모델 유형 :MIP

카테고리 : 피망 슬롯 모델 라이브러리

메인 파일 : cross.gms

$title 알쿠인 강 건너기 (CROSS,SEQ=191)

$onText
거위를 데리고 옥수수 한 부셸을 짊어진 농부
늑대가 강에 왔습니다. 그는 할 수 있는 보트를 발견했습니다
자신과 그의 소유물 중 하나(옥수수, 거위 또는
늑대 - 하지만 더 이상은 아닙니다. 이제 그는 옥수수를 혼자 둘 수 없었습니다.
거위도, 거위도 늑대와 함께 혼자 있는 것도 아니고,
다른 하나를 소비하십시오. 그럼에도 불구하고 그는 자신을 얻는 데 성공했습니다.
그리고 그의 물건은 무사히 강을 건넜습니다.

Borndoerfer, R, Groetschel, M 및 Loebel, A, Alcuin의
운송 문제와 정수 계획법. 콘라드 추세
Informationstechnik를 위한 Zentrum, 베를린, 1995.

Soren Nielsen 제공, 수리 과학 연구소
               코펜하겐대학교

키워드: 혼합정수선형계획법, 알쿠인의 수송 문제
$offText

세트
   i '아이템' / 거위, 늑대, 옥수수 /
   t '시간' / t1*t10 /;

매개변수 dir(t) '교차 - 가까운 곳에서 먼 곳은 +1 - 먼 곳에서 가까운 곳 -1';
dir(t) = power(-1,ord(t) - 1);

디렉토리 표시;

변수
   y(i,t) '1 시간 t에 항목이 먼 쪽에 있는 경우'
   cross(i,t) '강을 건너다'
   done(t) '먼 쪽의 모든 항목'
   nocross '교차하지 않는 기간의 수';

이진변수 y;
양수 변수 교차 완료;

방정식
   DefDone(i,t) '먼 쪽의 모든 것'
   DefCross(i,t) '교차점'
   림크로스(t)
   먹다없음1(t)
   먹다없음2(t)
   오브제;

DefCross(i,t+1).. y(i,t+1) =e= y(i,t) + dir(t)*cross(i,t);

DefDone(i,t) .. done(t) =l= y(i,t);

limCross(t+1).. sum(i, cross(i,t)) =l= 1;

EatNone1(t).. dir(t)*(y('goose',t) + y('wolf',t) - 1) =l= done(t);

EatNone2(t).. dir(t)*(y('goose',t) + y('corn',t) - 1) =l= done(t);

Obj..nocross =e= sum(t, done(t));

모델 강 / 모두 /;

y.fx(i,t)$(ord(t) = 1) = 0;

옵션 optCr = 0;
nocross를 최대화하는 mip를 사용하여 강을 해결합니다.

y.l, cross.l을 표시합니다.