Why Linear Programming at all?

  • Thread starter flyingpig
  • Start date
2,556
1
I am taking Linear Programming and I haven't completed the course yet, but here is my question.

I've notice that all these problems could have been solved just as easily with Lagrange multipliers.

We got a bunch of linear inequality constraints and an obj function, we can use Lagrange.

Why do we have all of these weird theories about corner points and duals and all?
 

AlephZero

Science Advisor
Homework Helper
6,953
291
The basic idea of the LP method is a systematic way to finding which inequality constraints are really equalities (i.e. active constraints) and which are not. Because it is systematic, it is relatively easy to write a computer program to implement it.

If you try to solve the problem using Lagrange multipliers, you have to figure out which constraints are active for yourself, from the Lagrange equations. That might be OK for a problem with 2 or 3 variables and 2 or 3 constraints, but if you try it on a "real world" problem with say 20 variables and 100 constraints (almost all of which are inactive, but you don't know which ones), you need a systematic procedure.

Apart from that, ideas like duals, Kuhn-Tucker conditions, etc also apply to general (nonlinear) optimisation problems, not just to LP problems.
 

Pyrrhus

Homework Helper
2,160
1
Linear programming is one of the successes of Mathematical Optimization (some may say OR). If you look at your Weierstrass theorem and the Local-Global, you can have a very useful result for all LP problems that have a bounded and non-empty constraint set (solution set, also called opportunity set). Thus, what you basically need is an algorithm to find a solution, and by the previous theorems you know is Global.

In terms of applications, many EXIST. You can probably google that. You'll find more than plenty.
 

lurflurf

Homework Helper
2,417
122
It is about efficiency. Many areas of mathematics are about solving problems that are easy to solve in principle. There are theoretical and practical reasons for wanting to know if a problem you know can be solved in 10^6 hours with 10^3 computers could be solved in 10^2 hours with 10^1 computers.
 
2,556
1
But we are talking about linear constraints and obj function here. Is it really faster?
 

Pyrrhus

Homework Helper
2,160
1
But we are talking about linear constraints and obj function here. Is it really faster?
YES, it is faster because the preference direction (or gradient) of the obj function is constant, and thus the solution for LP is always a CORNER or a convex combination of two corners!. All algorithms look on the boundaries!. In contrast, NonLinear Programs can have a interior solution besides boundary solutions.
 

lavinia

Science Advisor
Gold Member
3,047
517
I am taking Linear Programming and I haven't completed the course yet, but here is my question.

I've notice that all these problems could have been solved just as easily with Lagrange multipliers.

We got a bunch of linear inequality constraints and an obj function, we can use Lagrange.

Why do we have all of these weird theories about corner points and duals and all?
The simplex method provides a fast way to solve a linear program on the computer. Do you know of a faster way using Lagrange multipliers?
 

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top