2

We want to maximize $ z = 30x_1 + 20x_2$

with $$2x_1 + x_2 \leq 140$$

$$x_1 + 2x_2 \leq 160$$

$$x_1 + x_2 \leq 90$$

$$ x_1, x_2 \geq 0$$

So my book says the first step is writing these to equalities, we do thse by introducing the slack variables $x_3, x_4, x_5$ which is pretty straightforward to me. We get a system of 4 linear equations with 6 variables, so in principle we have infinite solutions, but we want to find the one with the biggest $z$.

Here the troubles start to compile. My book writes these equations in something it calls a first simplex tableau. This is it:

enter image description here

They explain how we can easily get 1 solution, namely the one where $x_1=x_2=0$ and $x_3 = 140, x_4=160, x_5=90$ and $z=0$ (I BELIEVE it is called a basic feasible solution in english, not sure). The next step is finding a different basic feasible solution with these constraints:

  • the new basic feasible solution has to give us a $z$ which isn't smaller than the previous one (first question: So this 'basic feasible solution' is just a solution where the non-slack variables are 0?)

  • the new basic feasible solution must be allowed (I assume they mean it must obey the 4 inequalities).

Here is where I totally lose what they mean. They say that if we look at the z-row, we see that we can make the value of z bigger by making $x_1$ or $x_2$ positive (why necessarily positive, and not 'less negative'?). They continue to say that $x_1$ contributes the most (which is logical). We want $x_1$ in the basis and so one of the basis variables has to go (why do we want $x_1$ in the basis? What does that do?).

They say we can't make $x_1$ bigger than the minimum 70, 160 and 90 (i.e. 70, which I understand). So that means we can enlarge $x_1$ with 70 units and that $x_3$ is removed from the basis, because in that row we find that minimum. I understand that $x_3$ has to be removed, but I can't for the life of my figure out the WHY, the why which is so often forgotten and disregarded when taught mathematics, the WHY which makes the difference between being able to reproduce and being able to really grasp it. This question is linked with the earlier question about why we would want $x_1$ in the basis.

After that you do some pivoting, or whatever that's called, and that is just too far out of my reach without knowing the answers to these questions.

Lost1
  • 7,895
Ylyk Coitus
  • 970
  • 2
  • 10
  • 18

1 Answers1

2

If you try to solve this problem graphically, you will find the solutions can only occur at points where the constraint equations interesects. i.e. the corners of the feasible solution region. The reason for this is that, suppose, you are not a corner, you can always do better by moving toward one.

The simplex algorithm does precisely this. Everytime you are making one variable basic, you are making it largest it can without violating the constraints.

why necessarily positive, and not 'less negative'? because $x_1$ and $x_2$ are defined to be positive. You start with the solution that $x_1=x_2=0$ and $x_3=140,x_4=160,x_5=90$.

the reason you are making $x_1$ basic is arbitary, you could have elected to make $x_2$ basic instead as your first step. By making something basic, you are simply moving from a corner of the feasible region to another one. I am afraid this is the pretty much everything I can offer. If you would like a rigorous proof, you should consult a textbook.

Lost1
  • 7,895