Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Why Linear Programming at all?

  1. Sep 23, 2011 #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?
  2. jcsd
  3. Sep 24, 2011 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.
  4. Sep 24, 2011 #3


    User Avatar
    Homework Helper

    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.
  5. Sep 25, 2011 #4


    User Avatar
    Homework Helper

    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.
  6. Sep 27, 2011 #5
    But we are talking about linear constraints and obj function here. Is it really faster?
  7. Sep 28, 2011 #6


    User Avatar
    Homework Helper

    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.
  8. Sep 28, 2011 #7


    User Avatar
    Science Advisor
    Gold Member
    2017 Award

    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook