allbases.gms : 운송 문제에 대한 가능한 모든 기본 솔루션을 열거

설명

이 문제는 다음을 충족하는 최소 비용 배송 일정을 찾습니다.
시장의 요구사항과 공장의 공급품. 표준으로 개편한다
이진 변수를 사용하여 변수가 기저에 속하는지 또는
아닙니다. 그런 다음 이진 컷을 사용하여 실행 가능한 모든 기본 솔루션을 열거합니다.
목적 함수의 정렬 순서.

Dantzig, GB, 3.3장. 선형 프로그래밍 및 확장.
프린스턴 대학 출판부, 뉴저지주 프린스턴, 1963년.

키워드: 선형 계획법, 운송 문제, 스케줄링, 완전
          열거, 미시경제학

소형 모델 유형 :MIP

카테고리 : 슬롯 게임 모델 라이브러리

메인 파일 : allbases.gms

$title 운송 문제에 대한 가능한 모든 기본 해결책을 열거합니다. (ALLBASES,SEQ=396)

$onText
이 문제는 다음을 충족하는 최소 비용 배송 일정을 찾습니다.
시장의 요구사항과 공장의 공급품. 표준으로 개편한다
이진 변수를 사용하여 변수가 기저에 속하는지 또는
아닙니다. 그런 다음 이진 컷을 사용하여 실행 가능한 모든 기본 솔루션을 열거합니다.
목적 함수의 정렬 순서.

Dantzig, GB, 3.3장. 선형 프로그래밍 및 확장.
프린스턴 대학 출판부, 뉴저지주 프린스턴, 1963년.

키워드: 선형 계획법, 운송 문제, 스케줄링, 완전
          열거, 미시경제학
$offText

세트
   i '통조림 식물' / 시애틀, 샌디에이고 /
   j 'markets' / 뉴욕, 시카고, 토피카 /;

매개변수
   a(i) '경우에 따라 식물 i의 용량'
        /시애틀 350
          샌디에이고 600 /

   b(j) '경우에 따라 시장 j의 수요'
        / 뉴욕 325
          시카고 300
          토피카 275 /;

테이블 d(i,j) '거리(천 마일)'
              뉴욕 시카고 토피카
   시애틀 2.5 1.7 1.8
   샌디에고 2.5 1.8 1.4;

스칼라 f '1,000마일당 케이스당 운임(달러)' / 90 /;

매개변수 c(i,j) '케이스당 운송 비용(단위: 수천 달러)';
c(i,j) = f*d(i,j)/1000;

변수
   x(i,j) '케이스의 선적 수량'
   z '총 운송 비용(천 달러)'
   sslack(i) '공급 제약으로 인한 여유'
   dslack(j) '수요 제약에 대한 여유';

양수 변수 x, sslack, dslack;

방정식
   비용 '목적 함수 정의'
   Supply(i) '공장 i의 공급 제한을 준수합니다.'
   수요(j) '시장 j의 수요를 충족';

비용.. z =e= sum((i,j), c(i,j)*x(i,j));

공급(i).. sum(j, x(i,j)) =e= a(i) - sslack(i);

수요(j).. sum(i, x(i,j)) =e= b(j) + dslack(j);

* 기본 정의
변수
   xind(i,j) 'x 기본 표시자'
   sslind(i) 'sslack 기준 표시기'
   dslind(j) 'dslack 기준 표시기';

바이너리 변수 xind, sslind, dslind;

방정식
   defbasis '기본 정의'
   defximp(i,j) 'xind=0 => x=0'
   defsslimp(i) 'sslind=0 => SSL=0'
   defdslimp(j) 'dslind=0 => dsl=0';

defbasis.. 카드(i) + 카드(j) =e= sum((i,j), xind(i,j)) + sum(i, sslind(i)) + sum(j, dslind(j));

defximp(i,j).. x(i,j) =l= min(a(i),b(j))*xind(i,j);

defsslimp(i)..sslack(i) =l= a(i)*sslind(i);

defdslimp(j).. dslack(j) =l= b(j)*dslind(j);

* 컷 정의
$onEmpty
세트
   nb '기본 열거 컷' / b1*b22 /
   nba(nb) '활성 컷' / /
   dslcc(nb,j) '계수 절단' / /
   xcc(nb,i,j) / /
   sslcc(nb,i) / /;
$off비어 있음

방정식 defcut(nb) 'cut';
디컷(nba)..
         카드(i)*카드(j) + 카드(i) + 카드(j) - 1
   =g= sum((i,j)$xcc(nba,i,j), xind(i,j)) + sum((i,j)$(xcc(nba,i,j) 아님), 1 - xind(i,j))
       + sum(i$sslcc(nba,i), sslind(i)) + sum(i$(sslcc(nba,i) 아님), 1 - sslind(i))
       + sum(j$dslcc(nba,j), dslind(j)) + sum(j$(dslcc(nba,j) 아님), 1 - dslind(j));

모델 운송 / 모두 /;

매개변수 담당자;

옵션 optCr = 0,solvLink = 5, limRow = 0, limCol = 0, solPrint = 자동;

루프(nb,
   z를 최소화하는 mip를 사용하여 전송을 해결합니다.
   xcc(nb,i,j) = round(xind.l(i,j));
   sslcc(nb,i) = round(sslind.l(i));
   dslcc(nb,j) = round(dslind.l(j));

   break$(transport.modelStat <> %modelStat.optimal%);

   담당자(nb,'obj','','') = z.l;
   담당자(nb,'supply.m',i,'') = 공급.m(i);
   담당자(nb,'demand.m',j,'') = 수요.m(j);
   담당자(nb,'x.l',i,j) = x.l(i,j);
   담당자(nb,'x.m',i,j) = x.m(i,j);
   nba(nb) = 예;
);
abort$(card(nba) = 카드(nb)) 'nb를 너무 작게 설정하십시오. 현재까지 실현 가능한 기본 솔루션:', 대표;
abort$(abs(rep('b21','obj','','')-177.525) > 1e-6) '잘못된 마지막 솔루션';