Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Linear Programming

  1. Oct 19, 2005 #1
    Ok, I hope this is the right section.

    I have a problem that I cant even start. I have a set of points on a plane. I need to formulate a linear program so that the vertical distance between each point and a line is minimised. The line must have a positive gradient, positive y-intercept and each point must be below the line.

    I have no idea what Im doing. Can anyone point me in the right direction?
  2. jcsd
  3. Oct 19, 2005 #2
    Hmm, so how would I go about setting this up so I could solve it using matlab?
    thanks for the help.
  4. Oct 20, 2005 #3
    Could I let x=[1,2,3,4,5 etc] and y=[5,4,3,2,1 etc] ie the points im given.

    Then make some function Y=mx+c? And I want to minimise Y-y.

    Am I on the right track here?
  5. Oct 20, 2005 #4

    Tom Mattson

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Enuma Elish,

    While we do appreciate the work that you put into the homework help section of PF, it is nonetheless contrary to the Physics Forums Guidelines (which you agreed to) to post complete solutions to problems, or to offer assistance to students who have not shown some attempt at the problem. I have therefore soft deleted your post, and will restore it once this thread is resolved.

    Helping somone with homework is great. Doing someone's homework is not OK.

  6. Oct 20, 2005 #5


    User Avatar
    Science Advisor
    Homework Helper

    That's correct but incomplete.
  7. Oct 20, 2005 #6
    Ok, so I create that linear function, add the rest of the constraints.

    What I dont understand is how to get MATLAB to find the gradient. Is it just a matter of making m a variable too?

    I think I get this, but Im not quite there.

    Thanks for the help again Enuma. :)
  8. Oct 20, 2005 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Do you really need the gradient, or do you just need the derivative of the line?

    If it's the second, look up finite difference approximations (Taylor series expansion with higher order terms discarded)
  9. Oct 21, 2005 #8
    Well, the question asks me to find the equation for the line. Its a straight line, so I suppose the derivative is the gradient.

    Doing a Taylor series sounds a bit extreme, all Im asked to do it formulate a linear program.

    Ill have a crack and see what I can do.

    Thanks enigma.
  10. Oct 22, 2005 #9


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Taylor series with one term is nothing more than a secant approximation. Find two points close together. Compute rise over run. Viola. Looking up finite difference approximation methods give you some ways to do it to minimize error
  11. Oct 22, 2005 #10
    Hmm, ok I think I can write the problem down correctly.

    But I have no idea how to solve it using matlab. The only examples of these problems are the min f(x)=x1+x2 etc with constraints x1>2 etc.

    I am a retard at matlab.

    Heres what I just tried:

    syms X
    syms Y
    Y=mX+c (I have no idea how to write this equation out)
    How can I put in the constraints c>0, m>0, Y>y?

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook