What is linear programming?

I asked this inquiry on Stack Overflow yet it was shut as "not setting relevant". So I assume this is possibly the most effective area for it ...

I read over the wikipedia article, yet it appears to be past my understanding. It claims it's for optimization, yet just how is it various than any kind of various other method for maximizing points?

A solution that presents me to linear programming so I can begin diving right into some much less beginner-accessible product would certainly be most handy.

2019-05-06 21:41:18
Source Share
Answers: 3

I recommend you this write-up, which speaks about Linear Equations, Linear Programming, Integer Programming and also P = NP. It's understandable and also speak about the distinctions amongst these points

2019-05-09 09:06:57

BlueRaja's solution is absolutely extra full than this set (and also offers excellent referrals), yet below's a harsh review of linear programming. Intend that you have a straight function (in senior high school training courses, it's commonly a function of 2 variables) that you intend to maximize on a convex "viable" area bounded by straight formulas (once more, in senior high school, the bounds are commonly defined making use of straight inequalities in 2 variables).

Due to the fact that the function to maximize is straight, the set of factors for which the function has a certain value, claim c, is a line (and also all such lines are identical) and also the value of the function anywhere away of the line is more than c and also anywhere to the opposite side of the line is much less than c. So, you can think of relocating via this set of constant - value lines to increase/decrease the value of the target function as ideal to maximize it.

Given that the viable area is bounded by straight formulas, as the constant - value line relocates via and also out of the viable area, it last touches the viable area at a vertex (or perhaps in all factors on a side attaching 2 vertices), so the optimum remedy has to take place at a vertex of the viable area.

Offered all that, linear programming boils down to reviewing the target function in all the vertices of the viable area to locate the optimum value.

2019-05-08 18:53:15

The standard form (and also example) areas rather well define what it is.

Just how is it various than any kind of various other method for maximizing points?

It's, well, simply an additional method. Nonetheless, it is rather unique because several various other optimization algorithms either use linear programming as component of their remedy, or remain in fact a specialized solution to a linear programming problem. Actually , integer linear programming is NP - full , suggesting that any kind of trouble in NP can be stated as an (integer) linear programming problem.
(this additionally suggests addressing your regular integer linear programming trouble is a lot harder than if we really did not limit ourselves to integers.)

2019-05-08 18:48:48