Marcos

Posted on Friday, 23 May, 2003 - 07:48 am:

If we have the problem:

Maximise

$z_{1} x_{1} + z_{2} x_{2} + \dots + z_{n} x_{n}$

subject to

$\begin{matrix} a_{11} x_{1} + \dots + a_{1 n} x_{n} & \leq & b_{1} \\ \dots \\ a_{n 1} x_{1} + \dots a_{nn} x_{n} & \leq & b_{n} \end{matrix}$

then I can see how we canwrite this as:

Maximise z.x subject to Ax $\leq$ b, where z is a row vector of $z_{i}$ , x is a column vector of $x_{i}$ , A is a square matrix with $a_{ij}$ as the entry in cell (i,j) and B is a column vector of $b_{i}$ .
Thus, if we use Gaussian elimination on this, making sure (if possible) we don't "multiply through" by a negative number (which would disrupt the inequality) will we get an optimal solution to the problem?

This question is in an attempt to understand the Simplex Method and any more general explanations on this method would be greatly appreciated.

Marcos

Marcos

Posted on Friday, 23 May, 2003 - 05:53 pm:

By the way I forgot to mention that x_i are nonnegative.

I looked up Lagrange multipliers on "Eric Weisstein's World of Mathematics" but the showed how these multpliers can be used for a constraint of the form g(x₁ ,...,x_n ) = C which isn't what we've got in this problem (as far as I can see). I don't see how I can apply them here...

The simplex method is an operational analysis method to solve linear programming problems (if you don't get what I mean please ask :-)

:-)

).
Roughly speaking, the principle behind the method (as I understand it) is to take the constraints which would form a solid in n-dimensional space (axes are the x_i )focusing only in the first quadrant or octant or watever n is (2ⁿ -ant basically :-)

:-)

) as x_i are nonnegative.
Then, the method attempts to find the point that maximizes some objective function,P(x₁ ,...,x_n ). As, P = k (where k is a constant) is an n-dimensional hyperplane, the method basically moves the hyperplane further and further away from the origin until it is as away from the origin as possible but still touching the n-dimensional solid formed by the constraints...

That was probably the worst explanation I've ever done in my life so I'm extremely sorry if you can't follow :-)

:-)

...

Marcos

Kerwin Hui

Posted on Friday, 23 May, 2003 - 07:22 pm:

Marcos,

I am not sure what you mean by Gaussian elimination on this set of inequalities. If I interpret it correctly, you are using GE as though you have equality, with subtraction not allowed. The problem is - how can you be sure your "solution" actually lies in the feasible set? You have only demanded is that Z should be written as a linear combination of rows of A together with some -I (from the fact x_i nonnegative), with all coefficients nonnegative. However, the point corresponding to your solution of GE are only required to satisfy a subset of your constraints, namely only those involved in the linear combination, and may not satisfy the other constraints.

Kerwin

Marcos

Posted on Friday, 23 May, 2003 - 10:41 pm:

Kerwin,
Sorry, it may be because it's late here but I lose you after the sentence "You have only..."
You have indeed interpreted correctly what I meant by GE.

If GE goes as described, then won't x = A^-1 B necessarily be a solution to Ax < = B (with equality) and hence in the feasible set?

Marcos

Marcos

Posted on Friday, 23 May, 2003 - 10:47 pm:

Basically, if I'm not making any sense, can someone offer any information on how the simplex method actually works? (An internet search either returned maths way beyond my current level or just a statement of the steps involved)

Marcos

Kerwin Hui

Posted on Saturday, 24 May, 2003 - 12:51 am:

Here is a pathetic example to illustrate what I am talking about:

Maximise $y - x$ subject to

$\begin{matrix} x + y & \leq & 2 \\ 2 x + y & \leq & 3 \\ x, y & \geq & 0 \end{matrix}$

It is clear that the maximum occurs at $x = 0$ and $y = 2$ . However, if you use Gaussian elimination on the two inequalities

$\begin{matrix} 2 x + y & \leq & 3 & (1) \\ - x & \leq & 0 & (2) \end{matrix}$

you get $y \leq 4$ from which your method would lead to $x = 0$ , $y = 3$ , which does not lie in the feasible set.

The notation is a bit tedious, so I will try to explain at each step using an example:
Maximise f=x₁ +x₂ subjected to

Latex image click or follow link to see src

Here is the scheme of how the simplex algorithm works:
1. Start with a feasible solution
2. Test if the solution is optimal
3. If yes, stop. If no, move to an 'adjacent' and better feasible solution, and repeat step 2.

Let's assume you want to maximise

Latex image click or follow link to see src

subjected to constraints

Latex image click or follow link to see src

.
First you introduce slack variables, so you have equalities rather than inequalities. Write z_i for the slack variable we have the constraints

Latex image click or follow link to see src

.
Since it makes no difference whatsoever, let's write x_n+i for z_i to simplify our notation, and introduce the relevant zeros in the matrix (a_ij ) to get the problem in the form:
Maximise

Latex image click or follow link to see src

subjected to constraints

Latex image click or follow link to see src

.

We usually pick our initial feasible solution x_j =0 (j=1,...,n) and the slack variables to be the value of a_i0 .

In the example, you get:
Maximise f=x₁ +x₂ subjected to

Latex image click or follow link to see src

We can write this as a table

basis	x₁	x₂	x₃	x₄	a_i0
x₃	1	2	1	0	6
x₄	1	-1	0	1	3
a_0j	1	1	0	0	0

In general the table is

(a_ij : i,j> 0)	a_i0
a_0j	a₀₀

This table corresponds to the point x₁ =x₂ =0, x₃ =6, x₄ =3 and the set of equations

Latex image click or follow link to see src

Now we want to move towards a better solution. Although there are no way to tell which choice your path to make the least number of iterations, usually we are greedy and want to maximise the gain in the value of f at each stage. So:
(i) Choose some variable to enter the basis (i.e. some variable x_j where we want all of a_ij are zero except one entry). We have to pick this j so that a_0j > 0, so as to increase our f rather than decreasing it. If such a choice is not possible, we have the optimum solution.
(ii) Choose a variable to go out of the basis. If a_ij are all nonpositive, the problem is unbounded (can you see why?). In order not get outside the feasible set, we choose i such that a_ij > 0 and a_i0 /a_ij is minimised. If there are more than one such i, the problem has a degenerate solution.

In the example, let's choose j=1 (so x₁ enters the basis), and i=2 (since 3/1 < 6/1), so x₄ leaves the basis.

Now we pivot about the element a_ij to get

basis	x₁	x₂	x₃	x₄	a_i0
x₃	0	3	1	-1	3
x₁	1	-1	0	1	3
a_0j	0	2	0	-1	-3

This table corresponds to the point x₁ =3, x₃ =3, x₂ =x₄ =0 and also to the set of equations

Latex image click or follow link to see src

Now repeat the procedure again, x₃ leaves the basis and x₂ enters the basis to give

basis	x₁	x₂	x₃	x₄	a_i0
x₂	0	1	1/3	-1/3	1
x₁	1	0	1/3	2/3	4
a_0j	0	0	-2/3	-5/3	-5

This corresponds to x₂ =1,x₁ =4, x₃ =x₄ =0 and the set of equations

Latex image click or follow link to see src

Now we have reach the optimum, since we know that x₁ =4,x₂ =1, x₃ =x₄ =0 is feasible, and for any feasible x , we have f=5-2x₃ /3-5x₄ /3£ 5.

You can check that if we have chosen to get x₂ in the basis in the first step, we will still end up at the same solution.

Kerwin

Marcos

Posted on Saturday, 24 May, 2003 - 07:30 am:

Kerwin,
Actually for the first part of your post, I meant that we don't include the x_i nonnegativein the matrix but I see now that it would be extremely rare (if at all possible) that my idea could be applied as, in general, you will have to subtract somewhere...

Thanks a lot for that explanation. I'll get back to you once I've read (and understood) it...

Marcos

Marcos

Posted on Sunday, 25 May, 2003 - 10:21 pm:

Thanks a lot Kerwin,
All clear now

Marcos