AdvancedTopic 99 of 104Engineering Mathematics
Linear programming
Optimises a linear objective under linear constraints; solved by the simplex method.
In depth
LP maximises c·x subject to Ax≤b and x≥0. The feasible region is a polytope and an optimum lies at a vertex. The simplex method moves along edges; interior-point methods cross the interior. Applied to production planning, blending and logistics.
Key points
- Shadow prices give constraint value
- Duality
- Integer programming adds difficulty
ExampleChoosing product mix to maximise profit given machine hours.
Linear programming plans production, blending and routing under limits, and it is widely used in industry for decisions with many constraints.
What is Linear programming?
Optimises a linear objective under linear constraints; solved by the simplex method.
Why is it important to understand linear programming?
Linear programming plans production, blending and routing under limits, and it is widely used in industry for decisions with many constraints.
What does the simplex method do?
It moves along the edges of the feasible region from corner to corner, improving the objective until no better corner exists.
Why does linear programming find global optima?
The feasible region is convex and the objective is linear, so any local optimum is also the global optimum.
How is Linear programming used in practice?
Typical applications include choosing a product mix that maximises profit under machine time limits, blending feed ingredients at minimum cost while meeting nutrient targets and scheduling trucks across depots to minimise distance.
What should I learn before Linear programming?
Study "Optimisation and Lagrange multipliers" first (topic 98 of 104 in Engineering Mathematics). It covers the groundwork this topic builds on.
What are the key points of Linear programming?
Shadow prices give constraint value. Duality. Integer programming adds difficulty.
Can you give an example of Linear programming?
Choosing product mix to maximise profit given machine hours.
What comes after Linear programming?
The next topic is "Graph theory", which builds directly on this one.
How difficult is Linear programming?
It is classed as Advanced in Engineering Mathematics (topic 99 of 104). It is an advanced topic. It assumes you are comfortable with the intermediate topics in Engineering Mathematics.