Simple Minimization Problem: A few questions regarding the mechanics of solving

Question

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:

1. Is this a STANDARD minimization problem? Why or why not?
2. One of the constraints is a "Less than equal to" constraint. (C5). Does this require any special handling?
3. Should this be converted into a standard maximization problem for solving? Your thoughts.
4. Since there are 5 constraint equations, 5 slack variables will be introduced. Is this assumption correct?
5. Since there are 3 variables $(x, y \space \& \space z)$, there will be three non-basic variables. Is this assumption correct?
6. In the "Greater than or equal to" constraints, the slack variables will be deducted. Is this assumption correct?
7. In the "Less than or equal to" constraints, the slack variables will be added. Is this assumption correct?

8. 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]$

9. 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.

1. My main doubt is conversion into a maximization problem, and how the objective and constraints change.
2. And also how slacks are introduced into GTE and LTE constraints.

Answer 1

(I feel like I'm taking one for the team here. :) )

Starting with your main questions at the end...

1. 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.
2. 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...

1. No, because of the LTE constraint.

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

3. 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.

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

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

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

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

8. 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.)

9. 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$.