Chapter 4.5, Problem 1P

Explanation of Solution

Giapetto problem

• ${\text{x}}_{\text{1}}$, ${\text{x}}_{\text{2}}$, ${\text{s}}_{\text{1}}$, ${\text{s}}_{\text{2}}$ and ${\text{s}}_{\text{3}}$ are the basic variables.
• For solving a linear problem using simplex algorithm, first the linear problem is converted to its standard form.
• Then a basic feasible solution is found which is easy if all the constraints are less than or equal with non-negative right hand side.
• If all nonbasic variables have nonnegative coefficients in row 0 then that basic feasible solution is optimal.
• If any variable have negative coefficient in row 0 then the variable with the most negative coefficient is chosen to enter the basis.
• If one or more constraints have a negative right hand side then there is no longer a basic feasible solution.
• For representing the linear problem into its standard form, it can be written

  $\begin{array}{l}2x_1+x_2=100\hfill \\ x_1+x_2=80\hfill \\ x_1=40\hfill \\ x_1=0\hfill \\ x_2=0\hfill \end{array}$

• Hence after Iteration 1, the initial table is

z

x1<