|
Question 151666: I am trying to find the dual problem for the following question...
Maximize z= 8X1 + 3X2 + X3
Subject to : 7X1 + 6X2 + 8X3 (less than or equal to) 18
4X1 + 5X2 + 10X3 (less than or equal to) 20
with X1 (great than or equal to) 0 , X2 (greater than or equal to) 0 , X3 (greater than or equal to) 0
Answer by kev82(151)   (Show Source):
You can put this solution on YOUR website! How far have you got in attempting the problem?
Have you calculated the Lagrangian? Do you know the general form of a Lagrangian dual problem. You need to know that.
Once you know the form of the dual and the Lagrangian the problem should just be trivial algebra, which I'm sure you can do.
You'll have to let me know exactly where you have got stuck before I can give specific help.
-------------------------------------------------------------
You can wrote the problem so that all 5 constraints are in the form sum(a_i x_i)
The Lagrangian for this is g(l,x) = f(x) + sum (l_j sum(a_ij x_i - b_j)) where f is the thing you are trying to maximize and l is >=0.
As you already know we want max_{l_i} min_{x} g(l,x)
g is a linear function of x and therefore is unbounded from below unless all the coefficients of x are zero. When all those coefficients are zero the minimum is what is left over. So we want to max that subject to the conditions that the coefficients of x are zero.
That maximisation is a linear program and is infact the dual program that you are looking for. I think itis normaly written as a minimisation, but to get this simply reaise that maximising the negative of a function is te same as minimizing it.
I hope that wasn't too difficult but I don't know what level to write this at. It really is just as simple as substituting your values into the lagrangian and find the analytical minimum though.
|
|
|
| |
