Efficiently Solving Linear Programming Problems: A Better Approach

[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.

 

[arildno]

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

 

[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.

 

[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.

 

[PPonte]

HallsofIvy thank you for your explanation, that's 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?

 

[NateTG]

HallsofIvy thank you for your explanation, that's 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?

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 exercise.)

 

[PPonte]

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.)

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

 

[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.

 

[PPonte]

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

 

[NateTG]

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

You might want to start with something less ambitious.

Regardless, google is your friend...

http://www.tamuk.edu/math/mathclub/

Is a TI-89 users group which has a simplex (linear programming) program.