Linear programming is not really programming. It is a method for minimizing or maximizing a linear function in two variables, when the values taken by the variables are enclosed in a polygon on the Cartesian plane. There is no shortage of good sources of problems of this type. I’ve been happy with the ones in the UCSMP Advanced Algebra book, and a Google search turns up many links.
It’s a great topic for high school because the “real world” constraints that are given are usually plausible, and the optimization questions make sense. On top of that, students get to apply a range of skills and understandings (systems of linear inequalities, systems of linear equations, among others.) Linear programming is typically taught in Algebra 2, but done well, it could make sense with younger students if they have a strong understanding of interpreting graphs.
Unfortunately it is often taught with a cookbook, follow-the-recipe approach, with no reason given for the idea that the optimal points are among the vertices of the feasible region. I’ve posted a lesson on my Web site which should be used as an introduction to the topic, as it gets students to understand the basic ingredients of these sorts of problems. Moreover, the lesson ends with a little bit of technology, using animations that should help explain the special role of the vertices. (In fact, the animations suggest an approach to these problems which does not require trial and error: which vertex is optimal is obvious when you approach the problems that way.)
Check it out: lesson | animations
–Henri
Henri's Math Education Blog 