Step 1:

Compute \(\text{y}_A, \text{y}_B, \dots, \text{y}_E\) where \(\text{c}_{\text{ij}}=\text{y}_j-\text{y}_i, \forall(\text{i,j})\in \text{T} \text{ and } \text{y}_E=0\)

\[\left\{\begin{matrix} c_{BA}= y_A-y_B=1\\ c_{AC}= y_C-y_A=4\\ c_{CD}= y_C-y_D=3\\ c_{BE}= y_E-y_B=5 \end{matrix}\right. \Rightarrow \left\{\begin{matrix} y_E=0\\ y_A=-9\\ y_B=-10\\ y_C=-5\\ y_D=-2 \end{matrix}\right.\]

Step 2:

We compute \(\bar{\mathrm{c}}_{\text{ij}}=\text{c}_{\text{ij}}+\text{y}_i-\text{y}_j, \forall (i,j) \notin T\)

\[ \left\{\begin{matrix} \bar{c}_{BC}=c_{BC}+y_B-y_C=2+(-10)-(-5)=-3<0\\ \bar{c}_{BE}=c_{BE}+y_B-y_E=5+(-10)-(0)=-5<0\\ \bar{c}_{DA}=c_{DA}+y_D-y_A=-6+(-2)-(-9)=1 \end{matrix}\right. \\ \Rightarrow \text{Choose (B,E) is}\textbf{ entering arc}\]

Step 3:

\[ \left\{\begin{matrix} \text{u}_{BE}=40\geq \theta \geq 0\\ 60-\theta \geq 0\\ 90-\theta \geq 0\\ 80-\theta \geq 0 \end{matrix}\right.\] \(\theta^*=40=\text{x}_{BE} \Rightarrow \text{(B,E)} \textbf{ leaving arc}\)

Step 4:

The new Feasible tree solution

Step 1:

Compute \(\text{y}_A, \text{y}_B, \dots, \text{y}_E\) where \(\text{c}_{\text{ij}}=\text{y}_j-\text{y}_i, \forall(\text{i,j})\in \text{T} \text{ and } \text{y}_E=0\)

\[\left\{\begin{matrix} c_{BA}= y_A-y_B=1\\ c_{AC}= y_C-y_A=4\\ c_{CD}= y_C-y_D=3\\ c_{CE}= y_E-y_C=5 \end{matrix}\right. \Rightarrow \left\{\begin{matrix} y_E=0\\ y_A=-9\\ y_B=-10\\ y_C=-5\\ y_D=-2 \end{matrix}\right.\]

Step 2:

We compute \(\bar{\mathrm{c}}_{\text{ij}}=\text{c}_{\text{ij}}+\text{y}_i-\text{y}_j, \forall (i,j) \notin T\)

\[ \left\{\begin{matrix} \bar{c}_{BC}=c_{BC}+y_B-y_C=2+(-10)-(-5)=-3<0\\ \bar{c}_{EB}=c_{EB}+y_E-y_B=-5+(0)-(-10)=5\\ \bar{c}_{DA}=c_{DA}+y_D-y_A=-6+(-2)-(-9)=1 \end{matrix}\right. \\ \Rightarrow \text{Choose (B,C) is} \textbf{ entering arc}\]

Step 3:

\[ \left\{\begin{matrix} 50-\theta \geq 0\\ 40-\theta \geq 0 \end{matrix}\right.\] \(\theta^*=40=\text{x}_{BA} \Rightarrow \text{(B,A)} \textbf{ leaving arc}\)

Step 4:

The new Feasible tree solution

Step 1:

Compute \(\text{y}_A, \text{y}_B, \dots, \text{y}_E\) where \(\text{c}_{\text{ij}}=\text{y}_j-\text{y}_i, \forall(\text{i,j})\in \text{T} \text{ and } \text{y}_E=0\)

\[\left\{\begin{matrix} c_{AC}= y_C-y_A=4\\ c_{BC}= y_C-y_B=2\\ c_{CD}= y_C-y_D=3\\ c_{CE}= y_E-y_C=5 \end{matrix}\right. \Rightarrow \left\{\begin{matrix} y_E=0\\ y_A=-9\\ y_B=-7\\ y_C=-5\\ y_D=-2 \end{matrix}\right.\]

Step 2:

We compute \(\bar{\mathrm{c}}_{\text{ij}}=\text{c}_{\text{ij}}+\text{y}_i-\text{y}_j, \forall (i,j) \notin T\)

\[ \left\{\begin{matrix} \bar{c}_{DA}=c_{DA}+y_D-y_A=-6+(-2)-(-9)=1\\ \bar{c}_{BA}=c_{BA}+y_B-y_A=1-7+9=3\\ \bar{c}_{EB}=c_{EB}+y_E-y_B=-5+0-7=2 \end{matrix}\right. \]

Consider The linear relations:

min: \(6x_{AD}+4x_{AC}+2x_{BC}+5x_{CE}+5x_{BE}+3x_{CD}\)

Substitute the value in the above expression:

\[ \left\{\begin{matrix} x_{AD}=40\\ x_{AC}=10\\ x_{CD}=30\\ x_{BC}=40\\ x_{CE}=20\\ x_{BE}=40 \end{matrix}\right.\]

\[\Rightarrow Z = 6\times 40+4\times 10+2\times 40+3\times 30+5\times 20+5\times 40=750\]