# Homework Help: Linear Programming

1. Feb 9, 2006

### PPonte

How do you resolve linear programming problems? I don't like the way my math textbook and my teacher does. I think it's a bit innacurate, if I make me understand. They do it by displacing the objective function.

2. Feb 9, 2006

### arildno

Displacing the objective function?
What is meant by that?
Please post an example, and what is bugging you about the solution procedure.

3. Feb 9, 2006

### PPonte

It's difficult to post an example since my textbook is in portuguese and I am very bad at drawing. Let's do it in another way, could you show me your way of solving this problems.

4. Feb 9, 2006

### HallsofIvy

That's not how you "solve" linear programming problems- the point of "displacing the object function" is to show why the methods work.

A linear programming problem involves a linear object function that you want to maximize or minimize, such as, say, ax+ by. Typically, you are required to find a point in some convex polygon (formed by linear inequalties) that makes the object function maximum or minimum. The graph of ax+ by= M, for a given M, is a straight line with slope -a/b (solve for y: y= (-a/b)x+ M/b). The slope does not depend upon M so different values of M give different parallel lines. The point of "displacing" the line (increasing or decreasing M) is to show that eventually those lines will leave the convex polygon. The largest or smallest values of M will occur just as the line "leaves" the polygon- at a vertex of the polygon.

THAT'S how you solve a linear programming problem (in 2 variables): determine the vertices of the polygon (where the line graphs of the equations associated with the inequalities intersect) and evaluate the object function at those points.

If there are 3 variables, your graph becomes 3 dimensional and the boundaries are planes but its the same idea: solve the corresponding equations to find the vertices and evaluate the object function at those points.

If there are more than 4 variables, it becomes impossible to graph or visualize the vertices- that's when you use the simplex method which is much more complicated.

5. Feb 9, 2006

### PPonte

HallsofIvy thank you for your explanation, thats exactly how was taught to resolve. Nevertheless, I don't like to displace the object function, since I can just do that drawing in a paper or in the graphic calculator. The graphic calculator (mine is a TI 84) is not very precise in the determination of the point or points, that, for example, maximize the function. Do you know any programm for the calculator that could help me?

6. Feb 9, 2006

### NateTG

Actually, you should be able to zoom in with the graphing calculator. That said, you could try googling "simplex method". I'm pretty sure that the TI 84 can be programmed to do it, but you'll end up using the matrix stuff. (You might consider writing the program as an excercise.)

7. Feb 9, 2006

### PPonte

Sorry, but my english is terrible. Could you explain it with other words, namely the terms that I bolded?

8. Feb 9, 2006

### NateTG

Matrices (the plural of matrix) are a notation device that is used when dealing with a lot of linear equations or inequalities. They're freqently used in linear algebra and linear programming.

'Writing the program' means creating a list of instructions in a format that the TI-84 understands that will make it find the optimum for a particular problem.

9. Feb 9, 2006

### PPonte

Thank you NateTG! Good idea! It's a good motive to start using properly my calculator. I will try.

10. Feb 9, 2006

### NateTG

You might want to start with something less ambitious.