What is linear programming?

Linear programming is a famous mathematical modeling tool for determining the best distribution of scarce resources among competing demands. Machinery, time, personnel, raw materials, money, and space are all resources. It is used to find the most optimal solution to a problem with given constraints. The real-life situations can be formulated using linear programming concepts into a mathematical model. Linear programming problems consist of an objective function and linear equalities subjected to constraints.

In linear programming, the word linear means the relationship represented by the straight line. The relation is represented as $ax + by = c$. It can be said that it is used to describe the relationship between more than two variables that are proportional to each other.

The word "programming" describes the optimal allocation of limited resources. Linear programming is used to find a way to handle optimization problems (linear programming problems). It is a mathematical method to achieve the best outcome.

In the presence of linear inequality or equality constraints, linear programming reduces or maximizes a linear function (sometimes called an objective function). When utilizing linear programming to solve a problem, the program creates numerous linear inequalities before maximizing or reducing the inputs.

Example of Linear programming

Let's understand the concept of Linear programming by this example of a furniture dealer. The dealer can invest his money in buying chairs or tables or both. He can use different strategies to get profit. He has a maximum amount of $5000 only and his storage space can have a maximum of 60 pieces. The price of a table is $100 and that of a chair is $50. Consider the following scenarios:

• Let's say he only wants to buy tables and no chairs. The price of a table is $100. So, he can get 5000 divided by 100, equivalent to 50 tables. Since the storage capacity is 60, 50 tables can be easily stored.
• Now, suppose he wants to buy only chairs and no tables. The price of a chair is $50. So, 5000 divided by 50 is equivalent to 100 chairs. But he can store only 60 pieces. So, he only needs to buy 60 chairs which will give him a profit of (60*50), that is $3000.

So, let's understand this example in Linear equation form.

• Let x be the number of tables.
• Let y be the number of chairs.
• Both x and y are non-negative numbers.
• The Dealer has a maximum of $5000, and he can only store 60 pieces in his store.

So the constraints of the problem are

100x + 50y<=5000

x + y<=60

Formulation of Linear Programming

The formation of linear programming presents a situation of problems in mathematical form. It consists of decision variables with an objective function and constraints.

Objective function

The objective of the linear problem is identified and converted into a suitable objective function. The objective function works as an aim or goal for the system of decision variables defined in the problem. Usually, the main objective of the solution is to maximize the resources or profits or minimize the cost or time.

Decision variables

A decision variable refers to a quantity that is controlled by the decision-maker. A linear program's variables are a set of quantities that must be determined to solve the problem; that is, the problem is solved when the best values of the variables are discovered. It is challenging to decide what value each variable should have, so they are also referred to as decision variables. Variables typically indicate the amount of a resource to be used or the intensity of some activity. Defining the variables of the problem is frequently one of the most challenging and critical tasks in framing a problem into a linear program. The creative variable definition can sometimes substantially reduce a problem's size or make a non-linear problem linear.

Non-negative constraints

It is impossible to have the negative value for physical quantity, like producing several cars, tables, bags, etc. So it is necessary to include non-negative constraints only. The non-negative constraints are represented by linear inequalities: x > = 0 and y > = 0. Where x and y are the objects produced, the user cannot implement the negative number of objects. The smallest number of objects a user can produce in the case of a non-negative constraint is zero.

Forms of linear programming

• Canonical form 
• • Objective function if maximum type.
  • All the decision variables are nonnegative.
• Standard form
  • All the variables are nonnegative.
  • The objective function may be of maximization or minimization type.

Types of Solutions

• General Solution
  • A set of variables $\left[X1, X2,X3,.............,X_{n+m}\right]$ is called a solution of an L.P. problem if it satisfies its constraints.
• Feasible solution
  • If a set of variables $\left[X1, X2,X3,.............,X_{n+m}\right]$ satisfies the constraints and non-negativity restrictions of an L.P. problem, then this set of variables $\left[X1, X2,X3,.............,X_{n+m}\right]$  is called a feasible solution.
• Optimal feasible solution
  • If a basic feasible solution optimizes the objective function, it is called an optimal feasible solution.
• Unbounded Solution
  • If the value of an objective function can be increased or decreased indefinitely, the solution is called an unbounded solution.  

Methods to solve Linear programming problems

There are mainly two methods used to solve the equations of linear programming concepts.

Simplex method

It is a way to solve linear programming models using slack variables, pivot variables, and tableaus to find the optimal solution to an optimization problem. A linear program achieves the best outcome given a maximum or minimum equation with linear constraints. In most cases, linear issues are solved by using software such as MATLAB, but the simplex method is a technique to solve the problem manually.

Graphical method

The graphical method is used to optimize the Linear equations. If the problem has two variables then, the graphical method is the best method to use.

In this method, the set of inequalities is subjected to some constraints. After that, inequalities are plotted on the plane. The line insect region will decide the feasible area once all the inequalities are plotted in the XY plane graph. This feasible region is then used to decide the optimal solution.

Common Mistakes

The linear program can be used to find an optimum solution to the problem, where there is a system of equations in which the constraints and their conditions are well defined. It cannot solve the problem with unknown conditions or values. The system of equations should be well defined, where some of them overlap, then only an optimum solution can be achieved.

Context and Applications

This topic is essential in many exams for both graduate and postgraduate levels, especially for

• Bachelor of Technology in Computer Science
• Bachelor of Technology in Electrical Engineering
• Master of Technology in Computer Science

Related Concepts

• The Linear programming model
• Objective function
• Non-negativity constraints
• Cost coefficients

Practice Problems

Q1. In the linear programming problem, the feasible region is a set of points that satisfy

1. Some of the given constraints
2. The objective function
3. None of these
4. All of the given constraints

Correct answer: (4) All of the given constraints.

Explanation:- The feasible region is an area defined by a set of coordinates that holds the condition of inequality. This is the set of all possible solutions that satisfy all of the given problem's constraints.

Q2. The objective of the linear programming problem is:

1. A relation between the variable
2. A function to be optimized
3. A constraint
4. None of these

Correct answer: (2) A function to be optimized

Explanation: The objective of linear programming is to optimize the operation of particular problems with given constraints.

Q3. Which of the following statement is correct?

1. If a feasible region is unbounded, then LP has no solution.
2. Every LP problem has a unique solution.
3. Every LP problem has at least one optimal solution.
4. If an LP problem has two optimal solutions, it has many solutions.

Correct answer: (4) If an LP problem has two optimal solutions, it has many solutions.

Explanation:-Linear programming can have many solutions. A better description is that a converted set is the set of optimal solutions to a convex optimization problem. As a result, if there are at least two optimum solutions, every point in between must be optimal as well.

Q4. A feasible solution to a LP problem,

1. Must optimize the value of the objective function.
2. Need not satisfy all of the constraints, only some of them.
3. Must satisfy all of the constraints of the problem simultaneously.
4. Must be a corner point of the feasible region.

Correct answer: (3) Must satisfy all of the constraints of the problem simultaneously.

Explanation: A feasible solution to a linear program is one that always fulfils all of the criteria. Since a linear program is an algorithm that will achieve the objective function, a feasible solution must accomplish all of the linear program's constraints.

Q5. In the linear programming concepts, the most popular nongraphical procedure is classified as:

1. Simplex method
2. Graphical procedure
3. Nongraphical procedure
4. Linear procedure

Correct answer: (1) Simplex method

Explanation:- It is a way to solve linear programming models using slack variables, pivot variables, and tableaus to find the optimal solution to an optimization problem.