기말고사를 위하여 - 최소비용흐름문제

  최소비용 "흐름" 문제이다.

 

최소 비용으로 물건을 운반해야하는데, 제약조건에 흐름의 양 이란 것이 추가된 거라고 이해하면 된다.

 

s 에서 t 까지 물을 5만리터 보내고 싶은데, 경로가 다양하고,  그 경로는 배수관의 사이즈가 제각각인 상황이다.

 

이때 물 1리터를 그 배수관을 통해 보낼려면 비용이 x만큼 든다는 것임. 

 

근데 마을에서 쓰는 물이 3이라고 치면

 

들어오는 물이 7일때 나가는 물이 5면 쓸 수 있는 물은 2니까 말이 안 되잖아

 

그러니까 쓰는 들어오는 물 7 이면 나가는 물은 3만 가능하다. 라는 조건도 추가되는거임

 

이게 vertex 의 균형을 유지한다 라고 표현함 .

 

  정리하자면 

 

1. vertex의 균형을 유지하면서

2. 흐름의 양을 조절하는데

3. 최소비용을 만들어야한다.

 

1과 2는 무조건 만족해야하는 충분조건이고

3은 필요조건이라고 볼 수 있다..?

 

------------------------------------------------------------------------------------------------------------------

min 비용 (전체적인 비용의 느낌이 있어야 이해하기 쉬울거임)

 

sub. to 흐름의 양, vertex 균형

------------------------------------------------------------------------------------------------------------------

 

  근데 음수경로가 발생한다는 뜻이 뭐였지? 목적함수값이 감소할 수 있다고 했지.

 

벨만포드에서는 음수경로와 회로를 분리했었어

 

음수 경로는 목적함수를 감소하긴 하지만, 값이 수렴하고. (1번 케이스)

 

음수 회로가 존재할 경우에는 목적함수값이 계속해서 감소해서 - 발산한다고 했지.(2번 케이스)

 

 

  그럼 이제 본 문제로 돌아오자 

 

이 문제는 음수회로가 존재한다고 했어. 그럼 2번으로 가야할 것 같지만 제약식을 잘 봐 

------------------------------------------------------------------------------------------------------------------

sub. to 흐름의 양, vertex 균형 

------------------------------------------------------------------------------------------------------------------

 

제약식을 만족해야하기 때문에 무한히 음수회로가 삥글삥글 돌 수 없단 뜻이야

 

이게 뭘까? 수렴한다는 소리지. 

 

따라서 음수회로가 존재한다면 그 방향으로 흐름을 보내고, 

 

이는 곧 목적함수값이 감소하는 것을 의미하며,

 

이는 즉 개선방향으로 개선을 하였다는 것을 뜻하고

 

이는 결론적으로 최적해에 가까워졌다는 것을 의미해.

 

이런 과정을 계속 하다보면 어떻게 되겠어. 음수회로가 존재하지 않게 되겠지? 그럼 개선할 게 없단 소리고

 

개선 할 게 없단 소리는? 최적해란 소리야. 그럼 끝