Linear Program questions regarding moving from BFS's to BFS's (in
Papadimitriou)
I was hoping someone could give a little more explanation on the following
excerpt from Papadimitriou and Steiglitz's "Combinatorial Optimization":
We are given the Linear Program:
Minimize $2x_2 + x_4 + 5x_7$, with:
$$ \begin{array}{cccccccc} x_1 &+x_2 &+x_3 &+x_4 & & & &=4 \\ x_1 & & &
&+x_5 & & &=2 \\ & & x_3 & & &+x_6 & &=3 \\ &3x_2 &+x_3 & & & &+x_7 &=6 \\
x_1,& x_2,& x_3,& x_4,& x_5,& x_6,& x_7 &\ge 0 \end{array} $$
...We are also given an exploration of the problem.
We are given a basis $\{B_1, B_3, B_6, B_7\}$ organized as $B(1) = 1$,
$B(2)=3$, $B(3)=6$, $B(4) = 7$ with basic feasible solution
$x=(2,0,2,0,0,1,4)$
Next they claim we can write the nonbasic column
$$A_5 = \left( \begin{matrix} 0 \\ 1 \\ 0 \\ 0 \end{matrix} \right) $$
This is followed by:
$$A_5 = \begin{array}{cccc} x_{1 5}A_1 + &x_{2 5}A_3 + &x_{3 5}A_6 + &x_{4
5}A_7 \\ 1\cdot A_1 - &1\cdot A_3 + &1\cdot A_6 + &1\cdot A_7 \end{array}
$$
THE QUESTION
Where do $x_{1 5}$, $x_{2 5}$, $x_{3 5}$, and $x_{4 5}$ come from?
No comments:
Post a Comment