What is Linear Programming? Assumptions, Properties, Advantages, Disadvantages

What is Linear Programming?

Linear programming is also a form of constrained optimisation, and quite possibly, the most commonly used. To understand the meaning of linear programming, we need to first understand what is meant by constrained optimisation.

In constrained optimisation, we have to optimise the objective function (or find the best value of the function), keeping in mind the various constraints. Therefore, the optimum feasible solution may be somewhat lower than the maximum because of the constraints.

As with any constrained optimisation, the main elements of LP are:

• Objective function
• Constraints
• Variables

In the context of operations research, LP can be defined as a mathematical tool that enables decision makers to allocate limited resources amongst competing activities in an optimal manner in situations where the problem can be expressed using a linear objective function and linear inequality constraints. It concerns the optimisation of a function of variables (i.e. the objective function), subject to a set of linear equations and/or inequalities (i.e. constraints).

The objective function could be any measure of effectiveness such as cost, time, profit, capacity, etc., that has to be achieved in the best possible way.

Let us now find out what makes a linear function. Linearity is the property of a mathematical equation in which the expressions among the variables are linear i.e. higher power of the variables and their products are not allowed. Thus, the function f of n variables x = (x1, . . . ,xn) is linear if there are constants a1, . . . , an such that:

f (x) = a1 x1 + a2 x2 . . . + an xn

---

Introduction to Linear Programming

Linear Programming (LP) is one of the most widely used techniques for effective decision-making. It is an optimisation technique that focuses on providing the optimal solution for allocating available resources amongst different competing and conflicting requirements.

The first serious attempt at the linear programming formulation and solution of a problem was done by Soviet mathematician and economist Leonid Kantorovich in 1939 during World War II, for planning the transport, scheduling, and allocation of resources within the given constraints of costs and availability.

In 1941, American mathematician Frank Lauren Hitchcock also formulated transportation problems as linear programs and developed a solution quite like the simplex method which was invented by American mathematician George B. Dantzig in 1947.

In 1979, Russian mathematician Leonid Khachi- yan first solved a linear programming problem in polynomial time. In a major breakthrough in 1984, Indian mathematician Narendra Karmarkar discovered a new interior-point method for solving linear programming problems.

The scope for application of LP is wide-range as it can be adapted to analyse diverse multi-dimensional decision-making problems. To be able to use and apply LP successfully, the formulation of a realistic model which accurately states the objectives of the decision-making is needed, subject to the restrictions in which the decision-making has to be made.

This article will allow readers to understand the meaning of linear programming and its various elements, gain an insight into how a lin- ear programming model is formulated, and how linear programming is expressed in its general, canonical and standard forms.

---

Assumptions of Linear Programming

The first and foremost assumption when using linear programming to model the real world is that a linear model is suitable. This is an important point to consider, given the fact that the real world will have plenty of non-linear relationships. Let us look at the other assumptions of linear programming:

• Proportionality / Linearity
• Certainty
• Presence of different alternatives
• Additivity
• Non-negative variable
• Finiteness
• Divisibility
• Continuity

Proportionality / Linearity

Linear programming assumes that any modification in the constraint inequalities will result in a proportional change in the objective function. This means that if it takes 10 hours to produce 1 unit of a product, then it would take 50 hours to produce 5 such products.

Certainty

Certainty in linear programming refers to the assumption that the parameters of the objective function coefficients and the coefficients of constraints are known with certainty. For example, profit per unit of product, resource availability per unit, etc. are known with certainty.

Presence of different alternatives

Linear programming assumes that different courses of action are available to the decision-maker/s and they need to decide which is the most optimal.

Additivity

Additivity means that each function in a linear programming model is the sum of the individual contributions of the respective activities. For example, the total profit is determined by the sum of profit contributed by each activity separately.

Likewise, the total amount of resources used is also determined by the sum of resources used by each activity separately. This assumption thus implies that there is no interaction among the decision variables.

Non-negative variable

Linear programming assumes that all answers or variables are non-negative. This assumption is true in the sense that negative values of physical quantities are not possible. It is not possible for the output in the production problem (such as bicycles, cars, computers, etc.) to be negative.

Finiteness

Linear programming assumes about the presence of a finite number of activities. An optimal solution is not possible in a situation where there is an infinite number of alternative activities and resource constraints.

Divisibility

Linear programming makes the divisibility assumption that the solution has to be in whole numbers i.e. integers. This assumption means that decision variable may take any value, including non-integer values, as long as functional and non-negativity constraints are satisfied.

Continuity

Linear programming assumes the continuity of decision variables. This means that a combination of outputs with fractional values plus integer values can be used.

---

Properties of Linear Programming Model

As you know by now, a linear programming model has the following conditions:

• The decision variables must have a linear relationship.
• It must have an objective function.
• Resource constraints are required.
• It must have a non-negative constraint.

A linear programming model involves an objective function, well-defined decision variables, and a set of non-negative structural constraints.

Let us try to understand these terms in the following section:

• Objective Function
• Decision Variables
• Constraint Equation
• Structural Constraints
• Non-negativity Constraint

Objective Function

The goal of an LP model is to optimise (maximise or minimise) the objective function; thus, the objective function can be defined as the mathematical equation that is a linear function of a set of variables that needs to be optimised. It is the mathematical expression that represents the aim of the system. In most cases, the objective is to maximise resources or profits and minimise the time or cost.

Decision Variables

The decision variables in a linear program are a set of variables that need to be determined to solve the problem. The aim is to determine the values of variables that yield the best value of objective function.

Constraint Equation

Decision-making problems arise mostly because the availability of resources in organisations is limited and tasks need to be performed in the most effective manner within this limit. Therefore, problems occur within these constraints in which the optimal solution to the problem needs to be identified.

An LP model thus has different linear constraints equations that are basically a mathematical statement of the limits on the resources or inputs at hand.

Structural Constraints

Structural constraints will always be present in linear programming problems. For example, the inequalities in the problem

x + y ≤ 100 20 x + 10y ≤ 1200

are the structural constraints of the linear programming problem. A constraint in an LP model restricts the value of the objective function, the value of decision variables and the use of resources at hand.

Non-negativity Constraint

As we read earlier, physical quantities cannot have negative values. Non-negativity constraint refers to a restriction added to a linear programming problem which highlights the negative values for physical quantities that cannot be shown in a solution.

It is essential to include the element of non-negativity as a constraint in a linear programming problem. In the above problem, the inequalities x ≥ 0, y ≥ 0 are the non-negative constraints.

---

Advantages of Linear Programming

There are several advantages of linear programming as mentioned below:

• Scientific approach to problem-solving
• Evaluation of all possible alternatives
• Optimal utilisation
• Helps in re-evaluation
• Improves the quality of the decision
• Addresses bottlenecks
• Applicable to diverse problems
• Formation of information base

Scientific approach to problem-solving

LP employs a scientific approach to problem-solving. It helps to determine the best possible outcome by representing complex relationships through linear functions. Thus, it presents a clear picture of problems which helps in better analysis.

Evaluation of all possible alternatives

Today’s environment presents highly complex decision-making problems to organisations which are difficult to solve by the traditional approach.

Optimal utilisation

LP enables optimal utilisation of various prevailing factors of production such as labour, raw materials, equipment, cost, etc.

Helps in re-evaluation

LP helps to re-assess a basic plan in case of changing conditions. If, the conditions change while the plan has been only executed in part, LP can be used to determine these conditions accurately to adapt the rest of the plan for the best outcome.

Improves the quality of the decision

LP helps to improve quality of decisions by incorporating the limitations of the system (which are the various restrictions which the system must conform to for the solution to be optimal). If deviating from the optimal path becomes inevitable, LP can also allow an easy estimation of the costs or penalty associated with this.

Addresses bottlenecks

Bottlenecks can cause imbalances in the production process as some machines will not be able to face the demand even at their peak performance while others may remain idle for long periods of time. LP highlights and addresses the problem of bottlenecks in the production process through optimisation.

Applicable to diverse problems

LP is quite an accommodating mathematical technique and can be adapted to analyse diverse multi-dimensional decision-making problems quite effectively.

Formation of information base

LP models can help managers obtain a highly useful information database by the analysis of the many possible alternatives taking into account the existing constraints. This database can be used to make rational decisions regarding the allocation of valuable resources.

---

Disadvantages of Linear Programming

While LP is a highly effective OR technique and has a wide range of applications in organisations, it still has certain limitations, of which we will learn about in this section.

• Assumption of linear relationship
• Constant value of objective and constraint equations
• No scope for fractional value solutions
• Degree of complexity
• Unsuitability for multiple goals
• Lack of flexibility

Assumption of linear relationship

We earlier discussed that LP assumes that the objective, variables as well as all the constraints can be stated in term of linear expressions which may not hold true for a lot of real-life situations.

Therefore, for LP models to be successfully applied, a given problem has be to clearly stated in the form of a linear relationship between different decision variables, whereas many reality-based organisational problems can be expressed quite easily in terms of a quadratic equation instead of a linear equation. LP fails to work and provide optimal solutions in these situations.

For example, LP techniques are unable to solve a problem that is expressed in the form of ax2 + bx + C = 0 where a ≠ 0.

Constant value of objective and constraint equations

LP technique can only be applied to a given problem once the values or the coefficients of the objective function as well as the constraint equations are all known with absolute certainty. In practical scenarios, however, it is not always possible to know with certainty the coefficients of objective function and the constraints equations.

In real-life scenarios, these variables may lie on a probability distribution curve and only the possibility of their occurrence can be predicted at best. LP also assumes that these values do not change over a while.

LP would lose it efficacy and might be unsuccessful in providing an optimal solution to the problem if these values were to change during the period of study. In practical situations, however, the values may change due to both external and internal factors during the course of the OR study. These assumptions limit the actual applicability of LP tools.

No scope for fractional value solutions

The solution to an LP problem may not always be quantified as an integer. A lot of times an LP offers a variety of fractional value solutions which needs to be rounded off to the next integer. In such cases, the solution would not be optimal.

Degree of complexity

A lot of real-life projects are large-scale. LP models are less useful in such cases because of the difficulty in performing the highly complex and lengthy calculations.

In such cases, various assumptions and approximations need to be made so that the given problem can be decomposed into several smaller problems and then solved individually. The validity of the final result may be unreliable in these situations.

Unsuitability for multiple goals

Most organisations’ long-term objectives are not limited to a single goal. An organisation might need to achieve multiple goals such as profit maximisation or cost minimisation, expanding market share, improving customer relationships, etc. on a priority basis to attain its long-term growth objectives.

Sometimes, there might be a conflict between the different goals and LP will fail in such cases. This is because only one goal can be expressed in the objective function in LP.

Lack of flexibility

If there are changes in decision variables in the system, it is very hard to incorporate these changes after a problem has been properly quantified in terms of objective function and the constraint equations and LP tools have been applied. Thus, LP does not have the desired operational flexibility.

---

Formulation of Linear Programming Model

The representation of an optimisation problem in a linear programming mathematical form is referred to as the formulation of an LP model.

The basic steps in the formulation of an LP model are:

• Identification of the decision variables
• Identification of the constraints
• Identification of the objective

Identification of the decision variables

The aim of an LP problem is to identify ways to optimise an objective and the answer to this problem is influenced by value of the selected decision variables. Therefore, the first step is to define the decision variables (parameters) that govern the behaviour of the objective function.

These decision variables are then stated in the form of linear algebraic functions or equations. The value of decision variables will be limited by the constraints stated in the problem which is the next step in the process.

Identification of the constraints

Once the decision variables have been determined, the next step is to identify all the constraints which limit the operations of an organisation at a given point of time.

These constraints need to be stated as linear functions in terms of the decision variables. The non-negativity constraints should also be included at this stage as decision variables cannot be negative in a physical scenario.

Identification of the objective

The next step is to identify the objective that needs to be optimised and express it in terms of the pre-defined decision variables and constraints.