Answer to Question #122096 in Linear Algebra for Zishan

Question

Obtain all the basic solution of the system of linear equations

Answer 1

As per the given question,

Let there are m linear equation which has n variables,

$\begin{cases} a_{11}x_1+a_{12}x_2.........+a_{1n}x_n=b_1 \\ a_{21}x_1+a_{21}x_2.........+a_{2n}x_n=b_2 \\ a_{31}x_1+a_{32}x_3.........+a_{3n}x_n=b_3 \\. ..\\ ...\\. ..\\ a_{n_1 1}+a_{n2}x_2.........+a_{nn}x_n=b_n \\ \end{cases}$

Let it is Ax=b

it have the basic feasible solution if,

$Ax=b ; x \geq0$

The Simplex Method uses the pivot procedure to move from one BFS to an “adjacent” BFSwith an equal or better objective function value.

Pivot Procedure:

1. Choose a pivot element $a_{ij}$
2. Divide row i of the augmented matrix $[A|b]$  by $a_{ij}$

$\begin{bmatrix} ...& a_{ij}&... & a_{il}&... \\ ...& ...&... &...&...\\ ...&...a_{kj}&...&a_{kl}&...\\ \end{bmatrix}\rightarrow \begin{bmatrix} ...& 1&... & \frac{a_{il}}{a_{ij}}&... \\ ...& ...&... &...&...\\ ...&...a_{kj}&...&a_{kl}&...\\ \end{bmatrix}$

3.For each row k(other than row i), add $−a_{kj}x$ row i to row k.

The element in row k, column l becomes $−a_{kj}×a_il+a_kl$

$\begin{bmatrix} ...& 1&... & \frac{a_{il}}{a_{ij}}&... \\ ...& ...&... &...&...\\ ...&...a_{kj}&...&a_{kl}&...\\ \end{bmatrix} \rightarrow \begin{bmatrix} ...& 1&... & \frac{a_{il}}{a_{ij}}&... \\ ...& ...&... &...&...\\ ...&...0&...&a_{kl}-\frac{a_{kj}a_{il}}{a_{ij}}&...\\ \end{bmatrix}$