# Linear Programming

1. Oct 19, 2005

### morry

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.

2. Oct 19, 2005

### morry

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

3. Oct 20, 2005

### morry

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?

4. Oct 20, 2005

### Tom Mattson

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

5. Oct 20, 2005

### EnumaElish

That's correct but incomplete.

6. Oct 20, 2005

### morry

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

7. Oct 20, 2005

### enigma

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

8. Oct 21, 2005

### morry

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.

9. Oct 22, 2005

### enigma

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

10. Oct 22, 2005

### morry

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.