Graphical Linear Programming: Formulating LP Problems

Basics of Linear Programming

Linear Programming (LP) is a mathematical technique used for the optimisation of a linear objective function, subjected to linear equality and linear inequality constraints.
The main goal of LP is to maximise or minimise the objective function. An objective function is a mathematical equation that describes the problem’s objective.
The constraints are a set of inequalities that represent the limitations of resources or other conditions that need to be satisfied.

Formulating LP Problems

The first step is to identify the variables. These are usually the quantities we want to maximise or minimise.
Write the objective function. This entails expressing what you want to maximise or minimise as a linear function of the variables.
List the constraints. These are the inequalities that our variables must satisfy.

Graphical Representation of LP

An LP problem can be graphically represented in a two-dimensional space if it has two variables. Each constraint can be represented as a line on this graph.
The feasible region is the area where the constraints are satisfied. If a constraint is an inequality, then the feasible region is one side of the line.
The feasible region is either a bounded region, which is enclosed by the lines representing the constraints, or an unbounded region, which extends indefinitely.
The optimal solution (if one exists) must lie within the feasible region and can usually be found at one of the vertices or extreme points of the feasible region.
Multiple or infinite solutions may exist in LP problems. This can occur when the optimal solution lies along a line segment or an edge in the feasible region, where the objective function value remains constant.

Solving LP Problems

For a problem with two variables, we can plot the objective function as a line on the graph. We then find the line within the feasible region that maximises (for a maximisation problem) or minimises (for a minimisation problem) the objective function.
The best strategy is often to evaluate the objective function at all vertices of the feasible region to find the best solution(s).
Remember to consider whether the LP problem may have no feasible solutions or be unbounded. This can be determined by examining the feasible region.
Sensitivity analysis can be useful to determine how changes in the constraints affect the optimal solution.

Remember that while graphical LP problems only involve two variables, more complex LP problems with more than two variables can be solved mathematically using methods such as the Simplex method.