Linear Programming

  • Thread starter morry
  • Start date
  • #1
136
0
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.
 

Answers and Replies

  • #2
136
0
Hmm, so how would I go about setting this up so I could solve it using matlab?
thanks for the help.
 
  • #3
136
0
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
Tom Mattson
Staff Emeritus
Science Advisor
Gold Member
5,500
8
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
EnumaElish
Science Advisor
Homework Helper
2,304
124
make some function Y=mx+c? And I want to minimise Y-y.
That's correct but incomplete.
 
  • #6
136
0
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
enigma
Staff Emeritus
Science Advisor
Gold Member
1,752
14
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
136
0
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
enigma
Staff Emeritus
Science Advisor
Gold Member
1,752
14
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
136
0
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.
 

Related Threads on Linear Programming

  • Last Post
Replies
10
Views
3K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
227
  • Last Post
Replies
0
Views
186
  • Last Post
Replies
0
Views
2K
Top