Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: LinearProgramming[]
Posted:
Dec 10, 2011 6:45 AM


On 09Dec2011 11:58, é å wrote: > We know all constraints in LinearProgramming[] involve ">=" or "<=". > > How can I solve the following problem with LinearProgramming[]: > > Assuming x+2yz>0,x+yz>=60,y+2z>12,x>0,y>0 and z>1 > > we want to get the minimum of 2x+3y+4z in the abrove constraints. > > Note that there are ">" other than">=" in the constraints we have > given. > If an LP problem has a unique optimal solution then it must lie along the boundary of a polyhedron formed by the constraints. This implies that strictly less than (<) or strictly greater than (>) constraints do not fit into a LP problem formulation; i.e. the solution is no longer guaranteed to be along a boundary. This means that the function LinearProgramming is not applicable for "<" and ">" constraints.
I believe that you will find that if these strict constraints have any effect on an optimization problem, the effect will be that there is no unique solution to the problem  this applies to both linear and nonlinear optimization problems. Thus, I suggest that you try to reformulate your problem such that it can be written without any strict constraints. Here is your problem reformulated with ">" replaced by ">=".
m = {{1, 2, 1}, {1, 1, 1}, {0, 1, 2}}; b = {0, 60, 12}; s = {1, 1, 1}; c = {2, 3, 4}; bs = Transpose[{b, s}]; LinearProgramming[c, m, bs, {0, 0, 1}]
which gives {51,10,1} as the solution to,
minimize 2x + 3y + 4z subject to: x + 2y  z >= 0 x + y  z >= 60 y + 2z >= 12 x >= 0, y >= 0, z >= 1
Note, two of the constraints (6 in total) in your original problem are not satisfied. It might useful for you to plot the polyhedron formed by these constraints  graphical analysis can be enlightening.



