Linear Programming is a math method used to make the best use of limited resources like time, money, or materials. It helps in planning so that you can either get the highest possible profit or the lowest possible cost while following certain rules or limits. These limits could be things like budget restrictions, availability of resources, or production capacity. In simple terms, it’s a way to find the most effective solution to a problem when you have constraints. This method is widely used in business, manufacturing, and many other fields to ensure resources are used in the best possible way.

What is Linear Programming?

Linear Programming is a method for determining optimum values of a linear function subject to constraints expressed as linear equations or inequalities. Linear Programming technique was formulated by a Russian mathematician L.V. Kantorovich, but the present version of the simplex method was developed by Geoge B. Dentzig in 1947.

In military operation, the effect is to inflict maximum damage to the enemy at a minimum cost and loss. In an industry, the management always tries to utilize its resources in the best possible manner. A salaried person tries to make investments in such a manner that the returns on investment are high but at the same time income tax liability is kept low.

In all the above cases, if the constraints are represented by linear equations/inequations(in one, two or more variables), and a particular plan of action from several alternatives is to be chosen, we use Linear Programming. The word linear means that all inequalities using the function to be maximized or minimized are linear, and the word programming refers to planning(choosing amongst alternatives) rather than the computer programming sense.

The basic components of Linear Programming are mentioned below.

• Decision Variables,
• Constraints,
• Data,
• Objective Functions,
• Feasible Region and Feasible Solution, and
• Optimal Solution.

Linear Programming Definition

Linear programming is a method used to find the best possible result in a given situation. It works with a mathematical formula, called the objective function, which is made up of straight-line equations or inequalities. These equations set certain limits or rules, called constraints. By using linear programming, we can figure out how to get the highest possible value (maximize) or the lowest possible value (minimize) of the objective function while following all the given rules.

Linear Programming Formula

In linear programming, every problem is made up of four main parts: decision variables, an objective function, constraints, and non-negative restrictions.

• Decision variables (like x and y) are the unknowns we need to find. They decide the final answer to the problem.
• The objective function (Z) is a formula that shows what we want to achieve — either the highest value (maximize) or the lowest value (minimize).
• Constraints are limits or rules that the decision variables must follow. These are usually written as inequalities (≤ or ≥).
• Non-negative restrictions mean that the values of x and y cannot be negative.

General formula:

• Objective function: Z = ax + by
• Constraints: cx + dy ≤ e, fx + gy ≤ h (or ≥)
• Non-negative: x ≥ 0, y ≥ 0

Characteristics of Linear Programming

The Characteristics of Linear Programming are listed below.

• Decision variable: They are represented by x, y, etc., and are referred to as limited resources.
• Objective function: It is the linear function between decision variables, that is to be maximized or minimized. In most businesses the objective is to maximize profits or minimize cost.
• Constrains: These are the restrictions or limits which are determined to make the situation optimum.
• Non negativity: The relationship between variables must be linear.
• Additivity: It is the total of all activities is the sum of each individual activity. None of the activities interact with one another.
• Divisibility: Decision variables may have fractional values.
• Deterministic or Certainty: All the parameters are assumed to be known exactly.
• Finiteness: There are always a finite number of decision variables and constraints.

Types of Linear Programming Problems

Linear Programming Problems (LPP) can be of different types depending on the situation.

1. Manufacturing Problems

These problems focus on deciding how many units of each product should be made or sold to earn the highest profit.
Here, each product needs a fixed amount of resources like manpower, machine time, and raw materials.

2. Diet Problems

This type helps find the cheapest diet plan that still provides all the necessary nutrients.
It considers the availability, nutritional value, and price of different food items to create the best combination.

3. Transportation Problems

These problems help find the least expensive way to move goods from factories or warehouses to different markets.
It ensures that products are delivered at the lowest cost while meeting demand.

Linear Programming Methods

There are two methods to solve a Linear Programming Problem(LPP). These are explained below.

Simplex Method

The simplex method is used to obtain the optimal solution of a linear system of constraints, in a linear objective function. It works by beginning at the basic vertex of the feasible region, and then iteratively moving towards the adjacent vertices, also improving upon the solution each time until the optimal solution is found.

For example, The advertising alternatives for a company includes television, newspaper and radio advertisement. The cost for each medium with its audience coverage is provided below.

The local newspaper limits the number of advertisements from a single company upto ten. Moreover, to balance the advertising among the three types of media, no more than the half of the total number of advertisements can occur on the radio. And at least of 10% should occur on televisions. The weekly advertising budget provided is $18,200. How many advertisements should be run in each of the three types of media so that the total audience is maximum?

Step 1: Identification of Decision Variables

Let \( X_1,\ \ X_2,\ \ X_3 \) represent the total number of ads for television, newspaper, and radio respectively.

Step 2: Identification of Objective Function

The objective of the company is to maximize the audience.So the objective function is given as, \( Z=100000X_1+40000X_2+18000X_3 \)

Step 3: Constraints

It is clear from the question that we have a budget constraint. The total provided budget is $18,200, and the individual cost per advertisement for television, newspaper and radio advertisements is $2000, $600 and $300 respectively.

This can be represented by the equation, \( 2000X_1+600X_2+300X_3\le18200 \)

Now for a newspaper advertisement there is an upper cap on the number of advertisements to 10. So the first constraint is \( X_2<10 \)

The second constraint is the number of advertisements on television. As the company wants at least 10% of the total advertisements to be on television, so it can be represented as \( X_1\ge0.1\left(X_1+X_2+X_3\right) \)

The last constraint is the number of advertisements on the radio which cannot be more than half of the total number of advertisements. So it can be represented as \( X_3\le0.5\left(X_1+X_2+X_3\right) \)

Now the Linear Programming Problem is formulated. We have reiterated all the constraints as follows.

\( 2000X_1+600X_2+300X_3\le18200 \)

\( X_2<10 \)

\( X_1\ge0.1\left(X_1+X_2+X_3\right)\Rightarrow-9X_1+X_2+X_3\le0 \)

\( X_3\le0.5\left(X_1+X_2+X_3\right)\Rightarrow-X_1-X_2+X_3\le0 \)

As we have a total of 4 equations so to balance out each equation we are introducing 4 slack variables \( S_1,\ \ S_2,\ \ S_3,\ \ and\ \ S_4 \)

Now our equations are as follows.

\( 2000X_1+600X_2+300X_3+S_1=18200 \)

\( X_2+S_2=10 \)

\( -9X_1+X_2+X_3+S_3=0 \)

\( -X_1-X_2+X_3+S_4=0 \)

Now after solving these equations we get the values \( X_1=4,\ \ X_2=10,\ \ X_3=14 \).

On solving the objective function we get the maximum weekly audience as 1,052,000, which is the required result.

Graphical Method

The graphical method involves formulating a set of linear inequalities subject to the constraints. Then the inequalities are plotted on an XY plane. Once we have plotted all the inequalities on a graph the intersection region gives us a feasible region. This feasible region explains what all values our model can take which also gives us the optimal solution.

For example, A farmer has recently acquired a piece of land of 110 hectares . He has decided to grow wheat and barley on this land. Due to the good quality of the sunlight and the region’s excellent climate, the entire production of wheat and barley can be sold in the market. He wants to know how to plant each variety of the two crops in these 110 hectares, given the costs, net profits and labor requirements are provided in data shown below.

The farmer has a budget of $10,000 and availability of 1,200 days during the planning horizon. What will be the optimal solution and the optimal value?

Step 1: Identification of Decision Variables

X (in hectares) = Total area for growing wheat

Y (in hectares) = Total area for growing barley

So X and Y are the decision variables.

Step 2: Identification of Objective Function

As the production from the entire land can be sold in the market. The farmer would want to maximize the profit of his total produce. We are given net profit for both the crops. The farmer earns a net profit of $50 for each hectare of wheat and $120 for each hectare of barley.

Thus, our objective function is, Max Z = 50X + 120Y

Step 3: Constraints

We have an upper cap on the total cost spent by the farmer due to the given budget.

So we can write the equations as, \( 100X+200Y\le10,000 \)

The next constraint is the upper cap on the availability of the total number of days for the planning horizon. As the total number of days available is 1200, so the equation will be, \( 10X+30Y\le1200 \)

The third constraint is the total area given for plantation. The total available area is 110 hectares and thus the equation becomes, \( X+Y\le110 \)

Step 4: Non-negativity Restriction

The values of X and Y must be greater than or equal to 0, so \( X\ge0,\ Y\ge0 \)

Now we solve this formulated LPP.

Since we know that latex] X\ge0,\ Y\ge0 [/latex], so we will consider only the first quadrant. Before plotting we simply the equations as follows.

\( 100X+200Y\le10,000\Rightarrow X+2Y\le100 \)

\( 10X+30Y\le1200\implies X + 3Y ≤ 120 \)

The third equation is already in its simplified form, \( X+Y\le110 \).

The first 2 lines on a graph are plotted in the first quadrant. The optimal feasible solution is achieved at the point of intersection where the budget & number of days constraints are active. This means the point at which the equations \( X+2Y\le100 \) and \( X+3Y\le120 \) intersect gives us the optimal solution.

The values for X and Y which give the optimal solution is at (60,20). Thus to maximize profit the farmer should produce wheat and barley in 60 hectares and 20 hectares of land respectively.

The maximum profit is, Max Z = \( 50\times60+120\times20=\$5400 \)

In the above graph, the blue colored part is the feasible region which indicates the maximum profit.

Learn about linear equations in one variables and linear equations in two variables

Steps to Solve a Linear Programming Problem

There are four general steps in the mathematical formulation of a Linear Programming Problem(LPP) and solving it as mentioned below.

Step 1: To identify the objective function as a linear combination of variables and to construct all constraints i.e., linear equations and inequalities involving these variables.

Thus, an LPP can b stated mathematically as,

Maximize(or minimize) Z = ax+by, subject to the conditions, \( a_ix+b_iy\le\left(or\ \ge\ or\ =\ or\ >\ or\ <\right)c_i \), where i = 1 to n, and the non-negative restrictions, \( x\ge0,\ y\ge0 \).

Step 2: To find the solutions(feasible region) of these equations and inequations by some mathematical method. Here we will study only the graphical method.

Step 3: To find the optimal solution i.e., to select particular values of the variables x and y that give the desired value(maximum/minimum) of the objective function.

Step 4: Explicitly state the non-negativity restriction i.e., we mention any kind of non-negative restrictions and write the equation accordingly.

Applications of Linear Programming

Linear Programming has vast applications on industry level as listed below.

• It is used to solve questions on matching diets to nutritional and other additional constraints with a minimum amount of changes.
• This mathematical technique allows the generation of optimal solutions that satisfy several constraints at once.
• Linear Programming is used in the Food and agriculture industry where farmers can generate more revenues for their land for making profits.
• The transportation industry works on linear programming techniques for cost and time efficiency.
• Manufacturing units work on this technique to generate more profit for the company.

Learn about Linear Equations in Two Variables

Properties of Linear Programming 

Linear Programming (LP) has some key features that make it different from other problem-solving methods:

1. Objective Function – LP always has a goal, like earning the highest profit or spending the least money. This goal is written as a simple mathematical equation.
2. Decision Variables – These are the unknown values we want to find. They decide the final result. For example, how many units of a product to make.
3. Constraints – These are the limits or rules that must be followed. They could be related to money, time, raw materials, or manpower.
4. Non-Negativity – In LP, the decision variables cannot be negative. You can’t produce a negative number of items or use negative resources.
5. Linearity – Both the objective function and the constraints must be linear. This means no powers, roots, or complicated formulas—only simple addition and multiplication.

Important Notes on Linear Programming

Here are some important points about Linear Programming (LP) explained simply:

• Linear programming is a way to find the best solution for a problem where the goal and limits are written as straight-line equations or inequalities.
• You can solve LP problems using methods like the simplex method or the graphical method.
• In any LP problem, the decision variables (unknown values we are solving for) must always be zero or greater — they cannot be negative.

Linear Programming Solved Examples

Problem 1: A store has requested a manufacturer to produce pants and sports jackets.For materials, the manufacturer has \( 750\ m^2 \) of cotton textile and \( 1000\ m^2 \) of polyester. Every pair of pants (1 unit) needs \( 1\ m^2 \) of cotton and \( 2\ m^2 \) of polyester. Every jacket needs \( 1.5\ m^2 \) of cotton and \( 1\ m^2 \) of polyester. The price of the pants is fixed at Rs 50 and the jacket at Rs 40. What is the number of pants and jackets that the manufacturer must give to the stores so that these items obtain a maximum sale?

Solution:

First we identify the decision variables as x = number of pants, and y = number of jackets

Then we write the objective function as \( f(x,\ y)=50x+40y \)

Next to write the constraints we use a table.

\( x+1.5y\le750 \)

\( 2x+3y\le1500 \)

\( 2x+y\le1000 \)

As the number of pants and jackets are natural numbers, there are two more constraints,

\( x\ge0 \)

\( y\ge0 \)

Now represent the constraints graphically.

As \( x\ge0 \) and \( y\ge0 \), we work in the first quadrant.

The area of intersection of the solutions of the inequalities would be the solution to the system of inequalities, which is the set of feasible solutions.

The optimal solution, if unique, is in a vertex. These are the solutions to the systems.

\( 2x+3y=1500;\ x=0(0,500) \)

\( 2x+y=1000;\ y=0(500,0) \)

\( 2x+3y=1500;\ 2x+y=1000(375,250) \)

Problem 2: A shopkeeper deals in two items-wall hanging and artificial plants. He has Rs 15000 to invest and a space to store utmost 80 pieces. A wall hanging costs him Rs 300 and an artificial plant Rs 150. He can sell a wall hanging at a profit of Rs 50 and an artificial plant at a profit of Rs 18. Assuming that he can sell all the items that he buys, formulate a linear programming problem in order to maximize his profit.

Solution:

Let x be the number of wall hangings and y be the number of artificial plants that the dealer buys and sells. Then the profit of the dealer is Z = 50x + 18y, which is the objective function.

As a wall hanging costs Rs 300 and an artificial plant costs Rs 150, the cost of x wall hangings and y artificial plants is 300x + 150y. We are given that the dealer can invest at most Rs 15000.

Hence the investment constraint is,

\( 300x+150y\le15000 \)

\( \Rightarrow2x+y\le100 \)

As the dealer has space to store at most 80 pieces, we have another constraint.

\( x+y\le80 \)

Also the number of wall hangings and artificial plants can not be negative. Thus we have the non-negative constraints.

\( x\ge0,\ y\ge0 \)

Thus the mathematical formulation of the LPP is:-

Maximize Z = 50x + 18y subject to the constraints,

\( 2x+y\le100,\ \ x+y\le80,\ \ x\ge0,\ \ y\ge0 \)

Do you want to score well in your Math exams? Then, you are at the right place. The Testbook platform offers weekly tests preparation, live classes, and exam series. Prepare a smart and high-ranking strategy for the exam by downloading the Testbook App right now.