We have already read that the linear programming problems are the ones which seek to optimize a quantity that is described linearly in terms of a few decision variables. Now, we will look at the broad classification of the different types of linear programming problems one can encounter when confronted with one. So let us begin!
Suggested Videos
Types of Linear Programming Problems
I. Diet Problems
As the name suggests in itself, such problems involve optimizing the intake of certain types of foods rich in certain nutrients that could help one follow a particular diet plan. More precisely, the goal of a diet problem is to select a set of foods that will satisfy a set of a daily nutritional requirement at a minimum cost.
- Constraints – The specified nutritional requirements, that could be a specific calorie intake or the amount of sugar or cholesterol in the diet.
- Objective function – The cost of the food intake.
Example: A kitchen manager at Nulife Hospital has to decide the food mix for the patients. Dietary instructions are that each patient must get at least:
- One gram of protein
- One gram of fat
- Three gms. of carbohydrates
Additional guidelines mention that the carbohydrate content of any patient by any chance, shouldn’t exceed six grams. The availability of protein, fat, and carbohydrates in gms per kg of chicken, rice, and bread; along with the market costs of each of these food items is as given below:
| Protein | Fat | Carbohydrates | Price/kg (Rs.) | |
| Chicken | 10 | 2 | 1 | 30 |
| Rice | 2 | 1 | 15 | 5 |
| Bread | 2 | 0 | 10 | 4 |
Formulate a suitable diet mix by minimizing the cost, subject to the given constraints, assuming 100 patients on that day.
Browse more Topics Under Linear Programming
- Different Types of Linear Programming Problems
- Graphical Method of Solving Linear Programming Problems
- Linear Programming Problem and Its Mathematical Formulation
Download Linear Programming Problem Cheat Sheet
II. Manufacturing Problems
These problems involve optimizing the production rate or the net profits of the manufactured products, which could be a function of the available workspace, the number of labourers, machine hours, packaging material used, raw materials required, the market value of the product etc. These find application in the industrial sectors and hence the prediction of a company’s possible capital increase over the years.
- Constraints – Variables like the work-hours, the cost of the packaging material used etc.
- Objective function – The production rate
Example: A company makes two products (X and Y) using two machines (A and B). Each unit of X that is produced requires 50 minutes processing time on machine A and 30 minutes processing time on machine B. Each unit of Y that is produced requires 24 minutes processing time on machine A and 33 minutes processing time on machine B.
At the start of the current week, there are 30 units of X and 90 units of Y in stock. Available processing time on machine ‘A’ is forecast to be 40 hours and on machine ‘B’ is forecast to be 35 hours.
The forecast of demand for X in the current week is 75 units and for Y is 95 units. Company policy is to maximize the combined sum of the units of X and the units of Y in stock at the end of the week.
- Formulate the problem of deciding how much of each product to make in the current week as a linear program.
- Solve this linear program graphically.
⇒ Clearly, this product involves optimizing the production rate, subject to the given constraints on the production of the two products (A and B) due to a constraint on the machine hours. Such problems are very typical in manufacturing sectors.
III. Transportation Problems
These problems are related to the study of the efficient transportation routes i.e. how efficiently the product from different sources of production is transported to the different markets, such as the total transportation cost is minimum. Analysis of such problems is very crucial for big companies with several production plants and a widespread area to cater to.
- Constraints – The specific supply and demand patterns.
- Objective function – The transportation cost
Example: A firm has 3 factories – Alpha, Tango, and Kingston. There are four major warehouses situated at locations PTR, CNB, DLS, and MMB. The average daily production of the product at Alpha, Tango, Kingston is 30, 40 and 50 units respectively. The average daily requirement of this product at PTR, CNB, DLS, and MMB is 35, 30, 32, 25 units respectively.
The transportation cost (in Rs.) per unit of product from each factory to each warehouse is given below:
| Factory↓ / Warehouses → | PTR | CNB | DLS | MMB | Supply (units) |
| Alpha | 6 | 10 | 8 | 5 | 30 |
| Tango | 10 | 7 | 8 | 9 | 40 |
| Kingston | 5 | 5 | 8 | 12 | 50 |
| Demand (units) | 35 | 30 | 32 | 25 |
Following the data from this table, calculate the total transportation costs of the products, subject to the constraints due to limited production and limited requirements. The goal here is to minimize the total transportation costs.
IV. Optimal Assignment Problems
These problems are concerned with the completion of a particular task/assignment of a company by choosing a certain number of employees to complete the assignment within the required deadline, given that a single person works on only one job within the assignment. Such problems find their application in event planning/management in big companies etc.
- Constraints – The number of employees, the work-hours of each employee etc.
- Objective function – The total assignments done
Example: The Watson Toys and Watches Company has four men available for work on four separate jobs. Only one man can work on any one job. The cost of assigning each man to each job is given in the following table.
| Person↓ / Job → | 1 | 2 | 3 | 4 |
| A | 20 | 25 | 22 | 21 |
| B | 19 | 18 | 23 | 17 |
| C | 15 | 17 | 21 | 25 |
| D | 20 | 21 | 25 | 25 |
Find a suitable system of assigning men to the jobs in such a way that the total cost of the assignment is minimum.
Solved Examples for You
Question 1: You need to buy some filing cabinets. You know that Cabinet X costs $10 per unit, requires six square feet of floor space, and holds eight cubic feet of files. Cabinet Y costs $20 per unit, requires eight square feet of floor space, and holds twelve cubic feet of files. You have been given $140 for this purchase, though you don’t have to spend that much. The office has room for no more than 72 square feet of cabinets. How many of which model should you buy, in order to maximise storage volume? Write the maximum storage volume in the provided box.
- 0
- 100
- 200
- 300
Answer : Let the number of X models be x and let the number of Y models be y,
For floor 6x + 8y = 72
or 3x + 4y = 36
10x +20y ≤ 140
Volume = 8x + 12y
Now x + 2y ≤ 14
Hence 2x + 4y ≤ 14
Volume = 8x + 12y = 8x +108 – 9x = 108 – x
2x + 4y ≤ 28
2x + 36 – 3x ≤ 28
x ≥ 8
So volume is maximum when x is minimum, x = 8. Hence, maximum volume = 108 – 8 = 100
Question 2: What is an appropriate example of the linear programming problem?
Answer: Some of the linear programming problems have distinct optimal solutions such as the problem of finding a possible solution to a system of linear inequalities is one of the linear programming problems where the objective function is the zero function.
Question 3: What is the linear programming problem when it comes to the operations research?
Answer: In the Operations Research process the Linear Programming is a mathematical modeling method used for the allocation of the limited resources, for example, material, machines, etc. to several competing actions such as plans, projects, services, etc.
Question 4: What are some types of linear programming (LPs)?
Answer: Some types of Linear Programming (LPs) are as follows:
Solving Linear Programs (LPs) by Graphical Method.
Solve Linear Program (LPs) Using R.
Solve Linear Program (LPs) using Open Solver.
Through the Simplex Method.
The Northwest Corner Technique and the Least Cost Technique.
Applications of Linear Programming (LPs).
Question 5: What is the importance of linear programming in mathematics?
Answer: Linear Programming (LP) is important and useful for the problems related to optimization. We optimize a scenario built upon a number of constraints which administer that situation.
Leave a Reply