Linear Programming

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?
Cheers.

Hmm, so how would I go about setting this up so I could solve it using matlab?
thanks for the help.

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?

Tom Mattson
Staff Emeritus
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.

Tom

EnumaElish
Homework Helper
make some function Y=mx+c? And I want to minimise Y-y.
That's correct but incomplete.

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

enigma
Staff Emeritus
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)

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.

enigma
Staff Emeritus
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

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:
x=[1,2,3,5,7,9]
y=[4,7,9,17,9,14]

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?

Cheers.