Solve a linear programming minimization problem with greater-than-equal sign in the constraints using the Simplex method

Question

I need to solve the following linear programming minimization problem using the Simplex method:

Minimize  2000x1 + 1750x2 + 2200x3
s.t.
4x1 + 2.5x2 + 5x3 >= 55
5x1 + 7x2 + 4x3 >= 500
x1,x2,x3 >= 0

I am not allowed to use the dual problem, I can only use the Simplex method. How can I do this properly?

Thanks!

Answer 1

Subtract slack variables from each constraint. As these are negative if $x_1$, $x_2$ and $x_3$ are all zero, the usual initial BFS at the origin (real variables = zero, slacks = RHS values) is infeasible. So add an artificial variable to each constraint and the initial BFS is $x_1=0, x_2=0, x_3=0, A_1=55$ and $A_2=500$. Perform the usual iterations with the objective function to be minimized being: $$2000x_1 + 1750x_2 + 2200x_3 + M(A_1 + A_2)$$

$M$ being defined as much greater than any other coefficient in the problem and so guaranteeing the disappearance (i.e being forced to zero) of $A_1$ and $A_2$ after two normal iterations. At this stage the BFS is at one of the vertices of the feasible region. If this is not the optimal one by the usual test, continue iterating without any further consideration of $A_1$ or $A_2$ until the optimal one is reached.