What algorithm can solve a linear minimization problem with given constraints?

  • Context: Undergrad 
  • Thread starter Thread starter specone
  • Start date Start date
  • Tags Tags
    Linear Minimization
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
3 replies · 2K views
specone
Messages
5
Reaction score
0
Hi all,

does anyone know what type of problem this would be classified as, and what kind of algorithm I could use to get a solution?

minimize:
P=60w1+30w2+10w3+100w4

subject to:
P ≥ 50
0 < wi ≤ 1

thanks very much
 

Discussion

Physics news on Phys.org
What are you trying to minimize? Without this, the question is incomplete. Defining what you want to minimize with these conditions is called linear programing.
 
It looks like a Linear Programming problem. The most straightforward solution algorithm is the Simplex Method.
 
The fundamental result in "linear programming" is that a minimum or maximum of a linear function, in a convex polyhedron, must occur at a vertex of the polhedron. Your condition, [itex]0< w_i\le 1[/itex], says that the "feasible region" is a n-dimensional rectangle and it is easy to calculate its [itex]2^n[/itex] vertices. However, the condition S> 50, on the target function will have to be applied after determining values. Also the fact that the faces [itex]0= w_i[/itex] are NOT in the feasible region can be a problem.