| Posted on Friday, 23 May, 2003 - 07:48 am: |
If we have the problem: Maximise
|
|
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
| Posted on Friday, 23 May, 2003 - 05:53 pm: |
By the
way I forgot to mention that xi 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(x1 ,...,xn ) = 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 xi )focusing only in the first quadrant or octant or watever n is (2n -ant basically
) as xi are
nonnegative.
Then, the method attempts to find the point that maximizes some objective function,P(x1 ,...,xn ). 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
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(x1 ,...,xn ) = 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 xi )focusing only in the first quadrant or octant or watever n is (2n -ant basically
) as xi are
nonnegative.Then, the method attempts to find the point that maximizes some objective function,P(x1 ,...,xn ). 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
| 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 xi 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
| 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
| 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
| 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
|
|
The notation is a bit tedious, so I will try to explain at each step using an example:
Maximise f=x1 +x2 subjected to
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
subjected to
constraints
.
First you introduce slack variables, so you have equalities rather than inequalities. Write zi for the slack variable we have the constraints
.
Since it makes no difference whatsoever, let's write xn+i for zi to simplify our notation, and introduce the relevant zeros in the matrix (aij ) to get the problem in the form:
Maximise
subjected to
constraints
.
We usually pick our initial feasible solution xj =0 (j=1,...,n) and the slack variables to be the value of ai0 .
In the example, you get:
Maximise f=x1 +x2 subjected to
We can write this as a table
| basis | x1 | x2 | x3 | x4 | ai0 |
| x3 | 1 | 2 | 1 | 0 | 6 |
| x4 | 1 | -1 | 0 | 1 | 3 |
| a0j | 1 | 1 | 0 | 0 | 0 |
In general the table is
| (aij : i,j> 0) | ai0 |
| a0j | a00 |
This table corresponds to the point x1 =x2 =0, x3 =6, x4 =3 and the set of equations
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 xj where we want all of aij are zero except one entry). We have to pick this j so that a0j > 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 aij are all nonpositive, the problem is unbounded (can you see why?). In order not get outside the feasible set, we choose i such that aij > 0 and ai0 /aij 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 x1 enters the basis), and i=2 (since 3/1 < 6/1), so x4 leaves the basis.
Now we pivot about the element aij to get
| basis | x1 | x2 | x3 | x4 | ai0 |
| x3 | 0 | 3 | 1 | -1 | 3 |
| x1 | 1 | -1 | 0 | 1 | 3 |
| a0j | 0 | 2 | 0 | -1 | -3 |
This table corresponds to the point x1 =3, x3 =3, x2 =x4 =0 and also to the set of equations
Now repeat the procedure again, x3 leaves the basis and x2 enters the basis to give
| basis | x1 | x2 | x3 | x4 | ai0 |
| x2 | 0 | 1 | 1/3 | -1/3 | 1 |
| x1 | 1 | 0 | 1/3 | 2/3 | 4 |
| a0j | 0 | 0 | -2/3 | -5/3 | -5 |
This corresponds to x2 =1,x1 =4, x3 =x4 =0 and the set of equations
Now we have reach the optimum, since we know that x1 =4,x2 =1, x3 =x4 =0 is feasible, and for any feasible x , we have f=5-2x3 /3-5x4 /3£ 5.
You can check that if we have chosen to get x2 in the basis in the first step, we will still end up at the same solution.
Kerwin
| 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 xi 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
| Posted on Sunday, 25 May, 2003 - 10:21 pm: |
Thanks a lot Kerwin,
All clear now
Marcos