이번 시간에는 환적(transshipment) 문제를 다루어보는 시간을 가졌습니다.
transportation의 확장, node가 중간에 위치할 수 있습니다.
3가지 종류의 node - origin(supply), transshipment(warehouse), destination(demand)
모든 node는 arc로 각각 연결이 가능합니다.
*transshipment node는 out=in
origin node인 denver와 atlanta는 각각의 최대 생산량을 초과하는 양을 공급할 수 없습니다. 그렇기 때문에 부등식의 방향은 =< RHS
transshipment(warehouse)는 origin으로부터 받은 만큼 destination으로 보낼 수 있기 때문에 out = in 식을 변환시키면 -IN + OUT = 0으로 변환시킬 수 있습니다.
(origin node의 값을 반대로 넘겨 - 부호를 붙여주고 우측상수를 0)
destination은 요구 수량만큼 받아야하기 때문에 부등식이 “=“ (equal)
detroit는 warehouse(kansas city + lousiville)로부터 받는 양이 200
miami는 warehouse(kansas city + lousiville)로부터 받는 양이 150
dallas는 warehouse(kansas city + lousiville)로부터 받는 양이 350
new orleans는 warehouse(kansas city + lousiville)로부터 받는 양이 300
X13, X14, X23, X24 - origin > warehouse 의 결정변수들
X35, X36, X37, X38 - warehouse > destination 의 결정변수들
결정변수의 수는 열린 arc의 수 만큼 존재(현재 닫혀있는 arc가 없고 모두 열려있기 때문)
제약조건식은 8개로, node의 수 만큼 존재합니다.
2개의 arc가 추가(결정변수 2개 추가)
X28 - atlanta에서 new orleans로 보내는 arc
X78 - dallas에서 new orleans로 보내는 arc
dallas의 제약조건식에는 new orleans로 보내는 수 만큼 빼주고 남은 값이 350 (-X78)
new orleans는 dallas로 부터 받은 수 만큼 더한 값이 300 (+X78)
Atlanta는 new orleans로 바로 보내는 수 만큼 더한 값이 400을 초과불가 (+X28) - 최대생산량을 초과하는 수를 보낼 수 없음
선택의 폭이 넓어졌기 때문에 총비용이 감소한 것 까지 확인할 수 있습니다.
5,300 > 4,600
첫댓글 차분히 잘 하고 있구나.