Day 1

primal은 들어오고 나가는 것의 balance에 대한 것이다.

dual은 arc의 balane에 관한 것이다. 시작점과 끝점 사이의 balance.

inward - outward = -b 를 이용해서 계산하는 것이다. b는 14.1에 주어져있다.

d에서 시작한 이유는 d가 leaf이기 때문이다. (스패닝트리에서 나가지 않는다)

빨간색 숫자는 계산해서 얻은 숫자다! cost가 아니다!

z of ac : -9
x of ac : 0 (complementary slacknesS)
x of fa : 6
z of fa : 0 (comlementary slackness)
y f : -15
x of fg: 0 스패닝 트리에 없으면 0다

Yg를 root노드로 정한것은 g가 abcdefg 중에 마지막이기 때문이다. 문제에서는 뭐를 루트로 잡을지 줄 것이다.

그래프의 arc를 보면 음수가 있다. 이는 dual feasible이지 않다는 것을 의미한다.

-9가 가장 negative니 바꾸고 싶은데 그러면 싸이클이 생긴다. 그래서 하나를 또 덜어내야한다. 그것이 leaving variable이 된다.

bi: amount of material being shipped to the network at node

Cij: cost of shipping one unit from i to j

xij: quantity shipped from i to j

inward flow - outward flow = bk

Day 2

x of ac 는 원래 0였으나 증가하게 될 것이다. T로.

ac가 t가 되니 fa도 변화가 생겨야한다. 6+t가 된다.

bc가 6-t가 되는 이유는 이제 t만큼 덜받아도되기때문이다.

fb도 마찬가지다.

leaving var는 하나의 arc를 지우는 것이다.

조그만 부분에서 바뀌고 나머지 빨간색은 안바뀐다. 이 이후에 root를 정한다. Yg=0라고 정했고, y들을 하난씩 계산해 나간다. y들을 다 구하고 나면, arc(a,e)에서 처럼 z들을 또 구해나갈 수 있다.

결국 헷갈리는 이유는 y랑 b, z와 f와 c등 같은 위치에 놓이는 것들을 헷갈려서 그렇다. y는 계산한 것이고 b는 주어진 것이다.
주어진 것은 b와 c다.

Day 3

bd때문에 infeasible하다. 없애고 스패닝트리는 유지되어야하니 A그룹과 B그룹을 잇는 다른 하나 추가하자.

ge를 선택하는 이유는 minimum이기 때문이다.

처음에는 숫자 없이 파란색과 빨간색 스패닝 트리만 있다. leaf node인 d에서부터 계산해 나간다. primaml을 계산 하는 것이니 inward - outward = -b를 이용하는 것이다. primal 계산인 빨간색을 다 구하고 나면 y를 구한다.