Formulating LP problems

Formulating Linear Programming Problems

Linear programming (LP) is a mathematical method used to find the maximum or minimum of a function, known as the objective function, subject to a set of linear inequalities known as constraints.

Defining the Objective Function

Identify the objective function, the equation you’re trying to optimise (maximise or minimise). This could represent profit, cost, time etc. in real-world applications.
Express the function in terms of decision variables. These variables represent elements controlled by the decision maker, such as quantities of specific resources.
Always express the objective function as ‘Objective = function of decision variables’.

Stating the Constraints

Frame the constraints as linear inequalities. Each constraint is typically a limitation on resources or requirements that must be satisfied.
Identify what each constraint represents in the real world, this can include restrictions on time, money, materials etc.

Turning Constraints into Equations

Each constraint can be represented as an equation or inequality using the same decision variables as the objective function.
Ensure that each inequality correctly represents the constraint as either ‘greater than’, ‘less than’ or ‘equals to’.
Make sure all equations and inequalities fully represent the conditions of the problem.

Creating Graphical Representations

The graphical method is usually employed for problems with two variables. Each inequality constraint defines a half-plane in this two-dimensional space.
Visualising the constraints can help understand the feasible region, which is the area fulfilling all constraints.
Shading, or not shading, areas that are not valid gives a clear illustration of possible solutions.
The optimal solution is found at the vertices (corner points) of this feasible region.

In practice, larger LP problems can’t be solved graphically and instead use more complicated methods like the Simplex method or interior point methods. However, the basic principles of identifying an objective function, defining decision variables, stating constraints and finding feasible solutions remain the same.