네트워크와 알고리즘 수업을 듣는데 모형화 후에, 답을 구해보고 싶어서 찾아보니 matlab을 사용하면 쉽게 풀이 가능하네요.

 

네트워크로 모형화했다고 하더라도 matlab으로 문제를 풀이할 때는 행렬로 자료를 입력해서 답을 구합니다.

 

방법은 다음 링크를 보시면 있습니다.

 

 

 

최단경로문제 Shortest path problem

http://www.mathworks.co.kr/kr/help/bioinfo/ref/graphshortestpath.html

 

최대유량문제 Maximum flow problem

http://www.mathworks.co.kr/kr/help/bioinfo/ref/graphmaxflow.html

 

최단경로문제는 유량문제에서 유량의 lower bound capacity와 upper bound capacity가 각각 0, 1의 정수인 특이한 경우의 문제라고 생각할 수 있다는 재미있는 사실.

 

 

수송문제 Transportation problem

http://www.mathworks.co.kr/kr/help/optim/ug/linprog.html#f414218

수송문제는 경영과학에서 선형계획법 Linear programming으로 풀이 가능합니다. 네트워크로 모형화해도 행렬로 나타내야 하는데, 그걸 다시 각각 변수에 따라 행렬로 나타내서 푸는게 자료 입력하는데 편하네요. 다른 방법이 있는지 교수님께 여쭤봐야겠음.

수송문제의 답은 정수로 나와야 하므로 아래를 사용해야함

http://www.mathworks.co.kr/kr/help/optim/ug/intlinprog.html

Posted by 공돌이pooh

댓글을 달아 주세요