Simple Minimization Problem: A few questions regarding the mechanics of solving Consider the following elementary minimization problem:
Minimize: $\phi = 2700x + 2400y + 2100z$, subject to:
$\text{Constraint 1}: 55x + 45y + 35z \geq 41000$
$\text{Constraint 2}: 30x + 35y + 50z \geq 40000$
$\text{Constraint 3}: 45x + 35y + 30z \geq 30000$
$\text{Constraint 4}: 10x + 20y + 15z \geq 15000$
$\text{Constraint 5}: x + y + z \leq 1000$
$(\text{given that }x, y, z \text{ all }\geq 0)$
My questions:


*

*Is this a STANDARD minimization problem? Why or why not?

*One of the constraints is a "Less than equal to" constraint. (C5).
Does this require any special handling?

*Should this be converted into a standard maximization problem for
solving? Your thoughts.

*Since there are 5 constraint equations, 5 slack variables will be
introduced. Is this assumption correct?

*Since there are 3 variables $(x, y \space \& \space z)$, there will
be three non-basic variables. Is this assumption correct?

*In the "Greater than or equal to" constraints, the slack variables
will be deducted. Is this assumption correct?

*In the "Less than or equal to" constraints, the slack variables will
be added. Is this assumption correct?

*Assuming that we are converting this into a standard maximization
    problem, is the initial matrix and its transform correct?
Matrix $[ A ] = \left[ \begin{array}{cccc} 55 & 45 & 35 & \| 41000
    \\ 30 & 35 & 50 & \| 40000 \\ 45 & 35 & 30 & \| 30000 \\ 10 & 20 &
    15 & \| 15000 \\ 1  & 1  & 1  & \| 1000 \space\space \\ 2700 & 2400
    & 2100 & \| 0 \space\space\space\space\space\space\space\space
    \end{array} \right]$
Matrix $[ A ]^\text{Transposed} = \left[ \begin{array}{ccccc} 55 & 30 &
    45 & 10 & 1 & \| 2700 \\ 45 & 35 & 35 & 20 & 1 & \| 2400 \\ 35 & 50
    & 30 & 15 & 1 & \| 2100 \\ 41000 & 40000 & 30000 & 15000 & 1000 & \|
    0 \space\space\space\space\space\space \end{array} \right]$

*What will be the new objective function and new constraints?


I understand that that's a significant number of questions and will require a fair amount of latex typing to answer. I have the solution in place (thanks to Excel). I'm looking for clarifications on the mechanics of solving by hand, using any of the methods like simplex, dual, 2-phase, revised simplex etc.


*

*My main doubt is conversion into a maximization problem, and how the
objective and constraints change.

*And also how slacks are introduced into GTE and LTE constraints.

 A: (I feel like I'm taking one for the team here. :) )
Starting with your main questions at the end...


*

*There are two ways to convert to a maximization problem.  One is to change the objective to maximizing $-\phi = -2700x -2400y - 2100z$.  This is because the $(x,y,z)$ triple that minimizes $\phi(x,y,z)$ will maximize $-\phi(x,y,z)$.  Another is to form the dual problem.  It looks like you're thinking about the second way, but I think the first one is a little easier, at least conceptually, so my answers will be based on that one.

*The LTE constraint is the easy one: $$x + y + z + s_5 = 1000,$$ where $s_5$ is a slack variable.  The GTE constraints are a little trickier.  For the first one, you want $$55x + 45y + 35z - s_1 = 41000.$$  This is fine mathematically, but when you move to the simplex method the usual approach of setting $x = y = z = 0$ and using the slacks as the initial basic variables doesn't work.  This is because you get $s_1 = - 41000$, which isn't feasible, since the slacks must be nonnegative.  What you have to do to get around this is introduce what's called an artificial variable $\bar{s}_1$ so that your first GTE constraint becomes $$55x + 45y + 35z - s_1 + \bar{s}_1 = 41000.$$ Then the artificial variable $\bar{s}_1$ is part of the initial basis.  You'll have to do this for all of the GTE constraints; your initial basis will be $\{\bar{s}_1, \bar{s}_2, \bar{s}_3, \bar{s}_4, s_5\}$.  Then you need to run a two-phase method.  For the first phase, the goal will be to get $\bar{s}_1, \bar{s}_2, \bar{s}_3, \bar{s}_4$ out of the basis.  If you can accomplish that, all of their values will be $0$, and so you can remove them from the problem.  What's left will be a feasible solution to your original problem; the slacks will be feasible as well.  In order to accomplish this, you need the objective in the first phase to be something like minimizing $\bar{s}_1 +  \bar{s}_2 + \bar{s}_3 + \bar{s}_4$.  For the second phase, use the original objective.



Now for the long list of questions at the start...


*

*No, because of the LTE constraint.

*Not if you formulate the problem as a maximization problem the way I described above.

*That depends on whether you're used to doing the simplex method by hand for maximization problems or for minimization problems.  Since you're talking about converting to a maximization problem, I assume that's the one you're more comfortable with.  

*Yes, but you'll also have four artificial variables for the GTE constraints - at least for the first phase.

*For the second phase, yes.  For the first phase, you'll have seven, thanks to the four additional artificial variables.

*Yes.  See my answer to #2 in your main questions.

*Yes.  See my answer to #2 in your main questions.

*If you're converting to the dual, yes.  (Again, though, you don't have to convert to a maximization problem by converting to the dual.)

*If you formulate the problem the way I describe in #1 to your main questions, the constraints do not change.  The only change to the objective is that you're maximizing $-\phi = -2700x -2400y - 2100z$.
