Introduction to Linear Programming

 We all come across situations in daily life where we need to find solutions to many different target based problems. Like maxing profits, reducing costs, or speeding up some process, etc. These kind of problems are called as Optimization Problems. How are these Optimization problems solving in mathematics. There are many various problems solving techniques to unravel such problems the most technique we'll discuss is Linear Programming. 

Introduction

Linear Programming is a technique used to find the optimum solutions for a defined problem. An optimum solution is the solution that gives the best possible outcome of the given particular problem. In simple terms, it is the method to find out how to do something in the best possible way, with given limited resources you need to do the optimum utilization of resources to achieve the best possible result in a particular objective, such as least cost, highest profit possible, or least time spent using those resources which might have multiple uses.

A linear programming problem has two basic components:

• First Part: It is the objective function that describes the primary purpose of this problem, to maximize something or to minimize something.
• Second Part: It is the system of equalities or inequalities which describe the constraints or the conditions under which Optimization is to be accomplished.

Some examples of Problems solved using linear programming:

• Manufacturing Problems: Problems related to Manufacturing costs minimization, Profit maximization or the minimization of resource usage, etc.
• Diet Problems: It is used to calculate the amount of different kinds of foods to be included in the diet in order to get the minimizing of cost while also satisfying the required constraints for the creation of the diet.

Important Terms In Linear Programming

Objective Function   

An objective function attempts to maximize profits or minimize losses based on a set of constraints and the relationship between one or more decision variables. The problem must be a clear and well-defined objective that can be stated quantitatively such as maximization of profit or minimization of cost etc.

The constraints could refer to resources such as manpower, machines, time, etc. and reflects the limitations of the environment in which, for example, a business operates. Each combination of values that apply to decision variables forms the solution of the business problem.

Constraints

These are the restrictions imposed on the resources available such as a restricted number of machines, labor material, etc. The constraints are the restrictions or limitations on the decision variables. They usually limit the value of the decision variables.

Decision Variables

Variables that compete with each other to share limited resources such as product services etc. They are interrelated and have a linear relationship, which make them capable of being deciding factors for the best optimum solution.

For example, in an optimization model for labor scheduling, the number of workers employed on workshop floor for a factory for particular shifts is a deciding variable.

Redundant Constraints

Some constraints are visibly present but do not hinder the process of the problem under study is called a redundant constraint.

Solutions

Feasible Solutions: These are the set of all possible solutions in the form of variables that satisfy the constants.

Optimum Solution: This is the best solution out of all the feasible solutions that supports the objective function in the best possible manner.

Assumptions in Linear Programming

• Non-Negative: All decision variables must be non-negative i.e., greater than or equal to zero.
• Certainty: It means that numbers in the objective and constraints are known with certainty.
• Additivity: The value of the objective function and the total amount of each resource used (or supplied), must be equal to the sum of the respective individual contribution (profit or cost) of the decision variables.
• Proportionality or Linearity: We also assume that a proportionality(or linearity) exits between the objective and constraints. 
• Divisibility: The solution values of decision variables are allowed to assume continuous values. Thus when decision variables are limited to only integer values, the LP problem fails.

Advantages of Linear Programming

• Linear Programming technique helps decision-makers to use their productive resources effectively.
• Linear Programming technique helps to arrive at optimal solution of a decision problem by taking into account constraints on the use of resources.
• Linear programming technique improves the quality of decisions. The decision-making approach of the user of this technique becomes more objective and less subjective.
• Linear Programming approach for solving decision problems highlight the bottlenecks in the process. For example, when a bottleneck occurs, machines cannot produce sufficient number of units of a product to meet demand or on the other hand, machines may remain idle. 

Limitations of Linear Programming

• Linear Programming assumes linear relationships among decisions variables. However, in real-life, the decision variables, nor the objective function and also the constraints, none of them are linearly related.
• While solving a LP model, there is no guarantee that the decision variables will get integer values.
• Parameters in a LP model are assumed to be constant which is not the case in real-life problems.
• Linear Programming does not take into consideration the effect of time and uncertainty.
• Linear Programming deals with only a single objective problem. Which is not the case in real life where a problem may have multiple objectives.

Conclusion

Linear programming and Optimization are used in various industries. The manufacturing and service industry uses linear programming on a regular basis. Some examples include:

• Manufacturing industries use linear programming for analyzing their supply chain operations. The purpose being, to maximize efficiency with minimum resource usage(time, cost, etc.).
• Linear programming is also used in retail (ex: supermarkets) for shelf space optimization. Optimization is primarily used in stores like Walmart, Reliance, Big Bazaar, D-Mart etc. Since the number of products in the market has increased a lot, it is important to understand what the customer wants. The products in the store are placed strategically keeping in mind shopping patterns of customers. The objective is to make it easy for a customer to locate & select the right products. 
• Optimizations are also used in Machine Learning. Supervised Learning works on the fundamental of linear programming. A system is trained to fit on a mathematical model of a function from the labeled input data that can predict values from an unknown test data.

The applications are not limited to the ones stated above. Keeping the limitations and assumptions in mind, Linear Programming can be applied any where and in any way required.

References

• geeksforgeeks.com
• analyticsvidhya.com
• tutorialspoint.com