최소비용흐름문제

목차

최대흐름문제(Maximal Flow)

Model

Model 대안

P.276 BMZ사 문제

Model

Model 대안

최단경로문제(Shortest path)

Model

Sarah의 중고차 교체 문제

Minimum Spanning Tree

예제

solution

본문내용

변수 xij:i지점에서 j지점까지의 수송량
최대화 x61
x61=x12+x13
x12=x24+x25
X13=x34+X35
X24+X34=X46
X25+X35=X56
X46+X56=X61
X12<=6, X13<=4, X24<=3, X25<=2, X34<=2, X35<=5, X46<=6, X56<=4, X61<=∞, 모든 변수>=0

최대화 x12+x13
제약조건
x12=x24+x25
X13=x34+X35
X24+X34=X46
X25+X35=X56
X12<=6, X13<=4, X24<=3, X25<=2, X34<=2, X35<=5, X46<=6, X56<=4, 모든 변수>=0

키워드

최소비용흐름문제,   최대흐름문제,   네트워크문제