설명

문제는 최단 경로 또는 가장 낮은 교통 수단을 찾는 것입니다
각 도시에서 다른 모든 도시까지의 비용입니다.

대형 모델 유형 :LP

카테고리 : 무료 슬롯 모델 라이브러리

메인 파일 : sroute.gms

$title 최단 경로 문제(SROUTE,SEQ=6)

$onText
문제는 최단 경로나 최저 수송 수단을 찾는 것이다.
각 도시에서 다른 모든 도시로의 비용.

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

키워드: 선형 프로그래밍, 최단 경로, 네트워크 최적화
$offText

세트
   i '도시' / 보스턴, 시카고, 댈러스, 캔자스시티, 로스앤젤레스,
                     멤피스, 포틀랜드, 솔트레이크, 워시DC /
   r(i,i) '경로';

별칭(i,ip,ipp);

매개변수
   darc(i,ip) '지향된 호'
   uarc(i,ip) '방향이 지정되지 않은 호'
              / 보스턴 .chicago 58, 보스턴 .wash-dc 25
                시카고 .kansas-cty 29, 시카고 .memphis 32
                시카고 .포틀랜드 130, 시카고 .솔트레이크 85
                달라스 .kansas-cty 29, 달라스 .losangeles 85
                달라스 .멤피스 28, 달라스 .솔트레이크 75
                캔자스-cty .memphis 27, 캔자스-cty .salt-lake 66
                캔자스-cty .wash-dc 62, losangeles .portland 58
                losangeles .salt-lake 43, memphis .wash-dc 53
                포틀랜드 .솔트레이크 48 /;

darc(i,ip) = max(uarc(i,ip),uarc(ip,i));
r(i,ip) = yes$darc(i,ip);

다크 표시;

변수
   x(i,ip,ipp) '호를 찍었습니다'
   비용 '총 비용 또는 길이';

양수 변수 x;

방정식
   nb(i,ip) '노드 잔액'
   cd '비용 정의';

nb(i,ip)$(동일하지 않음(i,ip))..
   sum(ipp$darc(ipp,ip), x(i,ipp,ip)) =g= sum(ipp$dark(ip,ipp), x(i,ip,ipp)) + 1;

cd.. 비용 =e= sum((i,ip,ipp), darc(ip,ipp)*x(i,ip,ipp));

모델 경로 '최단 경로' / 모두 /;

lp를 사용하여 비용을 최소화하는 경로를 해결합니다.

매개변수 sroute(i,ip);

sroute(i,ip) = -nb.m(i,ip);

루트 표시;