# network flow dual simplex

In the problem P, the constraint (inequalities) on the capacity of the side is removed, and the relaxed problem is P1. let the potential of each vertex corresponding to ①,②,③,④,⑤ is y1,y2,y3,y4,y5 show the dual of P . however objective function of the dual problem D is Y5-y1.

Show the complementary slackness condition of the problem P1 and the dual problem D, show the optimum solution $$x_{1,2} , x_{1,3}... x_{4,5}$$, is the optimum solution of problem P

Primal -> minimize 10$$x_{1,2}$$+$$5x_{1,3}+x_{2,5}+3x_{3,2}+2x_{3,4}+6x_{4,5}$$
subject to $$-x_{1,2}-x_{1,3}=-1$$ .... ①
$$x_{1,2}+x_{3,2}-x_{2,5}=0$$ ...②
$$x_{1,3}-x_{3,2}-x_{3,4}=0$$ ...③
$$x_{3,4}-x_{4,5}=0$$ ...④
$$x_{2,5}+x_{4,5}=1$$....⑤
$$0 \le x_{1,2} \le 1, 0 \le x_{1,3} \le 1, 0 \le x_{2,5} \le 1,$$

$$0 \le x_{3,2} \le 1, 0 \le x_{3,4} \le 1, 0 \le x_{4,5} \le 1$$

attempt :

P= 10$$x_{1,2}$$+$$5x_{1,3}+x_{2,5}+3x_{3,2}+2x_{3,4}+6x_{4,5}$$ = $$c^T x$$ we want to minimize cost in each edge, with constraint flow in =flow out $$Ax=b$$ $$\begin{bmatrix} -1 & -1 & 0 & 0 &0 &0\\ 1 & 0 & 1 & -1 &0 &0\\ 0 & 1 & -1 &0 &-1&0\\ 0 &0 &0 &0 &1 & -1\\ 0 & 0 & 0 & 1 & 0 & 1\\ \end{bmatrix}$$ $$\begin{bmatrix} x_{1,2}\\ x_{1,3} \\ x_{3,2} \\ x_{2,5} \\ x_{3,4} \\ x_{4,5} \\ \end{bmatrix}$$ = $$\begin{bmatrix} -1\\ 0 \\ 0 \\ 0 \\ 1\\ \end{bmatrix}$$

$$0 \le x_{1,2} \le 1, 0 \le x_{1,3} \le 1, 0 \le x_{2,5} \le 1 , 0 \le x_{3,2} \le 1 , 0 \le x_{3,4} \le 1, 0 \le x_{4,5} \le 1$$

dual max D = $$y_5-y_1$$ = $$b^t w$$ here we want to maximize each node in cost constraint $$A^tw \le c$$ $$\begin{bmatrix} -1 & 1 & 0 & 0 &0 \\ -1 & 0 & 1 & 0 &0 \\ 0 & 1 & -1 &0 &0\\ 0 &-1 &0 &0 &0 \\ 0 & 0 & -1 & 1 & 0 \\ 0 & 0 & 0 & -1& 1\\ \end{bmatrix}$$ $$\begin{bmatrix} y_1\\ y_2\\ y_3 \\ y_4 \\ y_5 \\ \end{bmatrix}$$ $$\le$$

$$\begin{bmatrix} 10\\ 5\\ 1 \\ 3 \\ 2 \\ 6 \\ \end{bmatrix}$$

but what is the complementary slackness? is it $$c^t x = b^t w$$ ? im not sure since i learn primal dual in linear programming but how can i apply it in graph?