Why Linear Programming at all?

[flyingpig]

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]

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]

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]

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.

 

[flyingpig]

But we are talking about linear constraints and obj function here. Is it really faster?

 

[Pyrrhus]

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]

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?