0
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.