1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Linear Programming

  1. Feb 9, 2006 #1
    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. jcsd
  3. Feb 9, 2006 #2

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    Displacing the objective function?
    What is meant by that?
    Please post an example, and what is bugging you about the solution procedure.
     
  4. Feb 9, 2006 #3
    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.
     
  5. Feb 9, 2006 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  6. Feb 9, 2006 #5
    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?
     
  7. Feb 9, 2006 #6

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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.)
     
  8. Feb 9, 2006 #7
    Sorry, but my english is terrible. Could you explain it with other words, namely the terms that I bolded?
     
  9. Feb 9, 2006 #8

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  10. Feb 9, 2006 #9
    Thank you NateTG! Good idea! It's a good motive to start using properly my calculator. I will try.
     
  11. Feb 9, 2006 #10

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Linear Programming
  1. Linear Programming (Replies: 12)

Loading...