Linear Programming Problem 

Linear programming, commonly known as linear optimisation, is often referred to as the problem to maximise or minimise the linear function which is subjected to the linear constraints. These can be either equalities or inequalities. Linear programming problems are a vital class of problem optimisation that helps in finding reliable solutions to acquire the lowest or the highest value of the function. There are mainly four types of linear programming problems that will be discussed today in detail. 

This article talks about linear programming problems. You will find brief information on the concept of linear programming in Maths, linear programming problems along with their solutions. 

Explanation of linear programming 

In simple terms, linear programming, also known as linear optimisation or LP is a method for optimising everyday operations with certain constraints. The major objective of linear programming is to either maximise or minimise the overall numerical value. It is considered one of the most important techniques used for finding optimum utilisation of resources. 

There are four major components of linear programming. These include decision variables, data, constraints, and objective functions.  While working with linear programming, here are some assumptions that must be kept in mind to better outcomes- 

• The relationship between the objective function and constraints should be linear. 
• The constraints can only be written in quantitative terms. 
• The linear functions need to be optimised. 

Mathematical formulation of linear programming problem 

Imagine x and y are the two cabinets of type one and type two that need to be manufactured. These are non-negative and referred to as non-negative constraints. The company is ready to invest 540 hours to create 50 cabinets in total. Therefore, 

15x + 9y <= 540

x + y <= 50

These are referred to as linear constraints. Let Z be termed as the profit he earns therefore, Z = 5000x + 3000y

The company’s major objective here is to maximise the Z or the profit, known as the objective function. 

Linear programming problem 

There are four different types of linear programming problems. These are as follows –

• Optimal Assignment Problems
• Transportation Problems
• Manufacturing problems
• Diet Problems

Let’s discuss each of these in detail –

• Optimal Assignment Problems

The first linear programming problem is the optimal assignment problem which is mainly related to the completion of a specified assignment assigned by the company to a specific group of people within the given time frame. These issues are most prevalent in event management companies, large corporations, and other working areas where there is working inefficiency. 

Here, the objective function is the number of tasks completed, whereas constraints are the number of employees asked to work, the number of hours each employee is working, and so on. 

• Manufacturing problems

The manufacturing problems are related to maximising the production of products and profits of the manufactured products, which might be the function of the available workspace, machine hours, packing materials utilised, product’s market worth, raw material required, and so on. 

Here, the objective function is the production rate, whereas constraints are factors including the cost of packing materials, labour hours, and so on. 

• Diet Problems

The diet problems mainly comprise the intake of a specific food item, affecting the overall diet plan. The purpose of the diet problem is to find a set of food items that can meet the daily nutritional needs while spending the least amount of money. 

Here, the objective function is the cost of the food consumption, whereas constraints are meeting nutritional needs, taking calories, and so on. 

• Transportation Problems

Transportation problems are another type of linear programming problem which is mainly concerned with the study of effective transportation routes and how effectively one product is carried from one point to another so that the total cost of the transportation is minimised. In large organisations, it is difficult to analyse transportation issues. 

Here, the objective function is the transportation cost, whereas constraints are the demand and supply patterns. 

Method to solve a linear programming problem 

The linear programming problem is solved using a series of different methods such as simplex method, graphical method, or by using tools such as open solver, R, and so on. These will be discussed in the next study materials. 

Conclusion 

The concept of linear programming is applied broadly in the optimisation field for several reasons. Several functional problems can be represented as linear programming problems. The linear optimisation or the linear programming problems is often referred to as the problem to maximise or minimise the linear function which is subjected to the linear constraints.
In this article describing linear programming problems, we studied the concept of linear programming problems in length. We covered several other topics, such as types of linear programming problems, discussed each of these problems in detail, and other related topics.