Linear optimization, also known as linear programming (LP), is a mathematical method for achieving the best outcome in a model represented by linear constraints. This approach is particularly important in today's dynamic business landscape where companies aim to optimize efficiency and minimize costs to remain competitive. The goal of linear optimization is to maximize or minimize a specific objective, such as profit or efficiency, while adhering to defined constraints like resource limitations or budget restrictions. There are several solution methods for linear optimization, with the simplex method being one of the most popular due to its efficiency and relative simplicity. The simplex algorithm is available in the primary and dual mode. Another solution method is the Interior-point method. The primary advantage of linear optimization is its simplicity and efficiency, as it is a well-studied field with many available tools and resources. Its main disadvantage is that it is only able to solve linear models, which may not be sufficient to accurately model real-world scenarios.
Components of a Linear Optimization Problem
A linear optimization problem consists out of three components.
- Objective Function:
The objective function represents the goal that the optimization aims to achieve. The objective function, represented as a linear function, can be used for minimization (minimizing costs) or maximization (maximizing profit or maximizing efficiency).
- Decision Variables:
They represent the decisions to be made, such as the production quantity of a product or resource allocation. These are the unknown quantities that you aim to determine through optimization. These variables can be continuous, discrete, or binary, depending on the context of the problem.
- Continuous Variables
These are variables that can take on any value within a specified range. They are not restricted to specific discrete values and can represent quantities such as time, distance, or volume.
- Discrete Variables
Unlike continuous variables, discrete variables can only take on specific, distinct values. These values are typically integers and represent quantities that cannot be subdivided further. Discrete variables are often used to model scenarios where decisions must be made in whole units.
- Binary Variables
Binary variables are a special case of discrete variables that can only take on two possible values: 0 or 1. They are commonly used to represent yes/no decisions or to activate/deactivate certain constraints or options within a model.
In a linear optimization model, only continuous variables are allowed. Discrete and binary variables require the definition of a mixed-integer optimization model.
- Continuous Variables
- Constraints
These are the conditions that the decision variables must meet. Constraints can be hard (non negotiable conditions) or soft (flexible limitations), and they represent real-world conditions that must be satisfied for a solution to be feasible. Constraints can arise from various factors, such as resource availability, capacity constraints, budget limitations, or regulatory requirements.
- Hard Constraints
Must be strictly adhered to in any feasible solution. They represent fundamental restrictions that cannot be violated without rendering the solution impractical or infeasible.
- Soft Constraints
Soft constraints, on the other hand, are flexible limitations that can be violated to some extent without completely invalidating the solution for example customer due dates, or capacity expansion. While soft constraints are still important considerations, their violation can incur penalties or trade-offs in the optimization process. Unlike hard constraints, soft constraints allow for some degree of deviation from the ideal solution to accommodate practical considerations or preferences.
- Hard Constraints
Simple Example of a Linear Program
In practice, linear optimization translates a production scenario into a mathematical puzzle, known as a linear program. The objective function, typically minimizing total cost, is defined first, followed by constraints representing limitations like production capacity, material availability, and customer demand. These constraints are expressed as linear equations or inequalities, defining the feasible region within which valid solutions to the optimization problem can be found.
Think about the following fictitious company. The Puck and Pawn Company manufactures two products (hockey sticks and chess sets).
- Each hockey stick yields an incremental profit of USD 2 and each chess set yields a profit of USD 4.
- A hockey stick requires four hours of processing at resource A and two hours at resource B.
- A chess set requires six hours at resource A, six hours at resource B, and one hour at resource C.
- Resource A has a maximum of 120 hours of available capacity per day, resource B has 72 hours, and resource C has 10 hours.
If the Puck and Pawn Company wishes to maximize profit, how many hockey sticks and how many chess sets should be produced?
- Identification of the decision variables
The first step in the process is to identify the decision variables. In this case, the decision variables are x1, which represents the number of hockey sticks produced per day, and x2, which represents the number of chess sets produced per day.
- Identification of constraints
The second step is the identification of the constraints. The constraints in this scenario are the available capacity per day for various resources. Resource A has a capacity of less than 120 hours per day, Resource B has a capacity of less than 72 hours per day, and Resource C has a capacity of less than 10 hours per day. Furthermore, there is also a constraint on the capacity consumption per unit, which must be considered.
Tabular Representation of Constraints
Resource A Resource B Resource C Consumption per hockey stick 4 h 2 h - Consumption per chess set 6 h 6 h 1 h Availability per day 120 h 72 h 10 h - Identification of the objective function
The third step involves the definition of the objective function. Here, we have two products: hockey sticks and chess sets. The incremental profit per unit for each product is USD 2 for hockey sticks, and USD 4 for chess sets. The goal is to maximize the daily profit from the sales of these products.
With this information, the mathematical model formulation can be created.
To outline the idea of the mathematical solution to this model, the model is represented in a graph and solved graphically.
- Graph to represent the feasible region
You can represent the feasible region as an area in a coordinate system with the decision variables as axes. The first axis represents the number of hockey sticks (variable x1) and the second axis represents the number of chess sets (variable x2). Each constraint is represented as a straight line, and the feasible region is the area that satisfies all constraints. In case of less than or equal to constraints, the feasible region is below the line, and for greater than or equal to constraints, it is above the line. In this example, there are three constraints (one for each resource), that are less than or equal constraints and two constraints (one for each production quantity), that are greater or equal constraints.
- Identify the feasible region
The feasible region represents all possible solutions that satisfy the given constraints of a problem. The vertices, or corners, of this region are points where different constraints intersect. The feasible region is colored in blue. According to the extreme point property, one vertice provides the optimal solution.
- Find the optimal solution
An optimal solution always resides at a vertex of the feasible region, a principle known as the extreme point property. This principle indicates that to find the optimal solution, one only must examine the vertices of the feasible region. If the objective function is to be maximized, the highest point on the objective function within the feasible region is the optimal solution. For a minimization problem, it's the lowest point within the feasible region. Graphically, the optimal solution is determined by drawing a straight line for different values of the objective function Z. In the illustration, the objective function is shown for the values 32 and 64. The optimal solution is derived by the point that intersects the objective function and the feasible region. This coordinate defines the optimal solution. In this example the optimal solution is to produce 24 hockey sticks and four chess sets, which yield a profit of USD 64.
There can be multiple optimal solutions if the objective function is parallel to one of the edges of the feasible region. If the feasible region does not exist, then the LP problem has no solution. This graphical method works only for LP problems with two variables. For problems with more than two variables, there are efficient algorithms available for optimizing linear functions subject to linear constraints. One such method is the simplex algorithm, which is an iterative algorithm that navigates through the vertices of the feasible region to find the optimal solution.
Another approach is the interior point method. Unlike the simplex method, which works on the boundaries of the feasible region, the interior point method starts from within the feasible region and moves towards the optimal solution. Both the simplex and interior point methods have their strengths and are widely used in different contexts. They are fundamental tools in operations research, computer science, and many other fields that involve optimization.
The linear programming model does not yield integer solutions, such as a production order for 1.7 products. If it is required to solve a problem in a discrete manner, aiming for solutions that reflect whole-number quantities like one, two, three, or four products, discrete optimization techniques are needed.
