Types of Linear Programming

What is Linear Programming?

Linear programming is defined as the issues of maximizing or minimizing a linear function  that  is dependent on linear constraints. The constraints may be equalities or inequalities. The optimization problems include the profit and loss calculation. Linear programming problems are a crucial factor of optimization problems, that enable us to find the feasible area and optimize the solution with a view to achieve the highest or lowest value of a function.

Linear programming is the procedure of considering different inequalities relating to a situation and calculating the optimum value that is required to be obtained in those circumstances.

What is a Linear Programming Problem?

Linear programming or linear optimization is a method that considers certain variable relationships to obtain a feasible solution to a mathematical model. It is also represented by Lpp. It deals with various problems such as maximization of profit minimization of cost or minimum usage of resources. These issues can be solved through the simplex method or graphical method. The linear programming applications are present in different fields such as commerce, engineering, manufacturing sector, etc.

Types of Linear Programming problems

Explain the Types of Linear Programming with Examples

The different types of  LPP are:

• Transportation problem

• Diet Problem

• Optimal Assignment problem

• Manufacturing problem

1. Transportation Problems

These issues are allied to the study of the efficient transportation routes i.e. how skilfully the product is transferred from distinct source of production to the different markets such that the total transportation cost is minimized. Analysis of such problems is an important factor for big companies with multiple production plants and widespread areas to cater the needs.

Constraints – The patterns of particular supply and demand Objective function- The transportation cost for transferring the product.

Example -

A firm has three different companies A, B and C. There are four different warehouses of the company situated at different locations namely CCD, QTR, SML and NNC. The average daily production of the product at A, B ,and C are 30, 40 ,and 50 units respectively. The average daily requirements of these products at  CCD, QTR, SML, and NNC are 35,30,32,and 25 units respectively.

The transportation cost (in Rs.) for transferring product from each factory to each warehouse is represented below in the  tabular form.

From the data given in the above table, calculate the total production cost of the product, subject to constraints due to the limited products and requirements. The aim here is to minimize the total transportation cost.

2. Optimal Assignment problems

These problems are concerned with the completion of a specific task, assignment of a company by selecting a certain number of employees to complete the assignment within the time-frame, considering that a single person works only one job within the given assignment. Such issues find their applications in event planning /management in big companies.

Constraints - The number of employees and the working hour of each employee

Objective function- The total assignment done by the employees within a given period

Example -

The Titan watch company has four men available for work for 4 different jobs. Only one man can work on any one of the given jobs. The cost of assigning each man to each job is represented in the below table:

Finding an optimal way of appointing each man to each job in  such a way that the total cost of the project is minimum.

3. Diet Problems

Most of the time the dietician and nutrition are  required to maintain health and diet charts for the patients.The aim of this diet is to include all types of nutrients that are needed by the human body  to maintain health. The diet chart should be available at low cost. Thus in the diet chart,  the dieticians are required to include all important types of minimum nutrients and accordingly the cost of such a diet should be minimum. Linear programming is widely applied in this sector.

Example - 

A kitchen manager at Max hospital has to decide the food mix of the patient. Dietician instruction is that each patient should get:

• One gram of nuts

• 3 grams of carbohydrates

• One gram of fat

Additional guidelines mentioned by the dietician is that the carbohydrate content of each patient should not exceed six grams. The availability of protein, fat and carbohydrate in gms of per kg of chicken, rice and bread along with the market cost of each of these products is mentioned below.

Design a suitable diet mix by minimising the cost subject to give constraint, estimating 100 patients on that day.

4. Manufacturing Problems

These problems include optimizing the speed of the production or the net profit of the manufactured products which could be a task of availability of workspace, the number of laborers, packaging material used, raw material required, etc. These factors find application in the industry sector and hence the estimation of company possible capital increase in recent years.

Constraints - variables such as work hours,cost of packaging material used.

Objective function - The production capacity of the company.

Linear programming Problem and Solution Example

Here is an example of a linear programming problem and solution

1. A chocolate manufacturing company produces only two types of products Urban Coca and Cadbury pista. Both the chocolates only need choco and milk to produce chocolate. To manufacture each unit of Urban Coca and Cadbury pista the below-mentioned quantities are required.

• Each unit of Urban Coca  needs one unit of milk and 3 units of choco

• Each unit of Cadbury pista needs one unit of milk and 2 units of choco.

The company kitchen has a total of five units of milk and 12 units of choco.The company makes a below-given profit on its every sale:

• Rs.6 per unit Urban Coca sold

• Rs. 5 per unit Cadbury pista sold.

Now, the company wants to maximise profit. How many units of Urban Coca and Cadbury pista should the company produce respectively?

Solution: The first step is to represent the problem in a tabulated form for better understanding:

• Let the total number of unit Urban Coca produced in the factory is =X

• Let the total number of unit Cadbury pista produced in the factory is = Y

Now, the total profit is represented by Z.

The total profit of the company is derived by the total number of units produced by Urban Coca and Cadbury pista multiplied by its per-unit profit of Rs 6 and Rs.5 respectively.

Profit: Max Z=  6x +5y

The company will produce as many units of Urban Coca  and Cadbury pista to maximize profit. But resources such as milk and choco are available in limited amounts.

According to the above table, each unit of Urban Coca and Cadbury pista needs 1 unit of milk. The total quantity of milk available is 5 units. Representing this mathematically,

X + Y ≤  5

Also, each unit of Urban Coca and Cadbury pista needs 3 units and 2 units of choco respectively. The total quantity of choco available is 12 units. Representing this mathematically,

3X + 2Y ≤  12

Also, the values for units of  Urban Coca can only be integers  

Now we have two more constraints X ≥  0, Y ≥  O

For the company to make maximum profit, the above inequalities have to be satisfied.

This is called formulating a real-world problem.

Solved Examples:

1. Find the maximum value for the following constraints

Maximise Z= 5x + 3y

Constraints:= 3x + 5y ≤ 15x, 5x+ 2y ≤ 10,  x ≥ 0,  y ≥ 0

Solution: Maximise Z= 5x + 3y

Subject to,

3x + 5y ≤ 15x

5x +2y ≤ 10

x ≥ 0

y ≥ 0

3x + 5y ≤ 15x                                                                                                   

5x +2y ≤ 10

(image will be uploaded soon)

Hence, Z = 235/19 is maximum at (20/19), (45/19)             

2. A manufacturer produces two products. The two products are nuts and bolts. It takes an hour of work on machine M and 1 hour of machine N to produce nuts. It takes 3 hours of work on machine M and 1hour of machine N to produce bolts. The manufacturer earns a profit of Rs. 17.50 per package on buts and Rs. 7 per package on bolts. How many packages of each should be produced in a day to maximize profit, if he operates his machine for at least 112 hours in a day?

Solution: Let the number of nuts produced be x

And, the number of bolts produced by y

According to the questions

Also x ≥ 0, y ≥ 0

As, we need to maximize profit

Hence, the function used here will be Maximise Z

Profit on each nut - Rs. 17.50

Profit on each bolt - Rs. 7.0

∵ Maximize Z = 17.50 + 7y

Combining all the constraints, we get

Maximize Z=  17.50 + 7y

Subject to constraints:

• x + 3y  ≤  12

• 3x + y  ≤ 12

• x ≥ 0, y ≥ 0

x + 3y  ≤  12                                                                                                  

 3x + y  ≤ 12

(image will be uploaded soon)

Hence, the profit will be maximize if the company produce 

Total number of bolts- 3 packages

Total number of nuts - 3 packages

Maximum profit - 73.5.

Quiz Time

1. Which of the following is the property of all linear programming problems?

1. Use of graph in the solution

2. A computer program

3. Minimization of some objective

4. The alternative course of action to choose from

5. Usage of linear and non-linear equations and inequalities.

2. The first step in formulating a linear programming problem is

1. Graph the problem

2. Perform a sensitivity analysis

3. Identify the object and constraints

4. Define the decision variables

5. Understand the marginal issues been faces

3. In break- even analysis, we assume

1. Linear relationships

2. Non-linear relationships

3. Diminishing returns to the variable factors of production

4. Non- proportional relationships