Chapter 4.BMO, Problem 1BMO

To determine

To write:

The initial simplex tableau for the given problem and the pivot element to be used for the first iteration of the simplex method is to be identified.

Answer to Problem 1BMO

Solution:

$x$	$y$	$z$	$u$	$v$	$w$	$P$	Constant
$2$	$1$	$-1$	$1$	$0$	$0$	$0$	$3$
$1$	$-2$	$3$	$0$	$1$	$0$	$0$	$1$
$3$	$2$	$4$	$0$	$0$	$1$	$0$	$17$
$-1$	$-2$	$3$	$0$	$0$	$0$	$1$	$0$

The pivot element is $1$ that lies in row $1$ and column $2$.

Explanation of Solution

Given:

The given conditions are,

$\begin{array}{l}2x+y-z\le 3\\ x-2y+3z\le 1\\ 3x+2y+4z\le 17\\ x\ge 0,y\ge 0,z\ge 0\end{array}$

Approach:

(1) If all the entries are nonnegative, the optimal solution has been reached.

(2) If there is one or more negative entries, the optimal solution has not been reached.

Calculation:

Consider the given objective function.

Maximize $P=x+2y-3z$

Introduce the slack variables, $u$, $v$ and $w$ in the given conditions and rewrite the objective function in the standard form that gives the system of linear equation as follows,

$\begin{array}{rll}2x+y-z+u& =& 3\\ x-2y+3z+v& =& 1\\ 3x+2y+4z+w& =& 17\\ P-x-2y+3z& =& 0\end{array}$

The initial simplex table is as follows,

$x$	$y$	$z$	$u$	$v$	$w$	$P$	Constant
$2$	$1$	$-1$	$1$	$0$	$0$	$0$	$3$
$1$	$-2$	$3$	$0$	$1$	$0$	$0$	$1$
$3$	$2$	$4$	$0$	$0$	$1$	$0$	$17$
$-1$	$-2$	$3$	$0$	$0$	$0$	$1$	$0$

Table $\left(1\right)$

Calculate the pivot element.

All the element in the last row are not non negative. So, the above simplex table is not in its final form.

The most negative element in the last row is $\left(-2\right)$ that lies in column $2$.

So, the pivot column is column $2$.

Calculate the pivot row.

$x$	$y$	$z$	$u$	$v$	$w$	$P$	Constant	Ratio
$2$	$\boxed{1}$	$-1$	$1$	$0$	$0$	$0$	$3$	$\frac{3}{1}=3$
$1$	$-2$	$3$	$0$	$1$	$0$	$0$	$1$
$3$	$2$	$4$	$0$	$0$	$1$	$0$	$17$	$\frac{17}{2}=8.5$
$-1$	$-2$	$3$	$0$	$0$	$0$	$1$	$0$

The least ratio is $3$ that lies in row $1$. So the pivot row is the first row.

Therefore, the element corresponding to pivot column and the pivot row is $1$.

Conclusion:

Hence, the initial simplex table is shown in Table $\left(1\right)$ and the pivot element is $1$ that lies in row $1$ and column $2$.