Managerial Decision Making & Linear Programming

A manufacturing company must optimize production across two factories while

considering material shortages. Develop an LP formulation.

Abstract
Linear programming or Linear optimization is a technique that helps us to find the optimum solution for a
given problem, an optimum solution is a solution that is the best possible outcome of a given particular
problem.
In simple terms, it is the method to find out how to do something in the best possible way. With limited
resources, you need to do the optimum utilization of resources and achieve the best possible result in a
particular objective such as least cost, highest margin, or least time.
The situation that requires a search for the best values of the variables subject to certain constraints is where
we use linear programming problems. These situations cannot be handled by the usual calculus and
numerical techniques.

Introduction

Linear programming is the technique used for optimizing a particular scenario. Using linear programming
provides us with the best possible outcome in a given situation. It uses all the available resources in a
manner such that they produce the optimum result.
Components of Linear Programming:
The basic components of a linear programming (LP) problem are:
 Decision Variables: Variables you want to determine to achieve the optimal solution.

1
  Objective Function: Mathematical equation that represents the goal you want to achieve
 Constraints: Limitations or restrictions that your decision variables must follow.
 Non-Negativity Restrictions: In some real-world scenarios, decision variables cannot be
negative
Linear Programming Problems (LPP) involve optimizing a linear function to find the optimal value solution
for the function. The optimal value can be either the maximum value or the minimum value.In LPP, the
linear functions are called objective functions. An objective function can have multiple variables, which are
subjected to conditions and have to satisfy the linear constraints.
Types of Linear Programming Problems:
There are many different linear programming problems (LPP) but we will deal with three major
linear programming problems in this project work:
Manufacturing Problems
Manufacturing problems are a problem that deals with the number of units that should be produced or sold
to maximize profits when each product requires fixed manpower, machine hours, and raw materials.
Diet Problems
It is used to calculate the number of different kinds of constituents to be included in the diet to get the
minimum cost, subject to the availability of food and their prices.
Transportation Problems
It is used to determine the transportation schedule to find the cheapest way of transporting a product from
plants /factories situated at different locations to different markets.
In this project work we will mainly deal with manufacturing problem and will try to relate it with the theory
through an example.

Body

A linear programming problem consists of,

 Decision variables
 Objective function
 Constraints
 Non-Negative restrictions
Decision variables are the variables x, and y, which decide the output of the linear programming problem
and represent the final solution.
The objective function, generally represented by Z, is the linear function that needs to be optimized
according to the given condition to get the final solution.
The restrictions imposed on decision variables that limit their values are called constraints.
Now, the general formula of a linear programming problem is,

2
Objective Function: Z = ax + by
Constraints: cx + dy ≥ e, px + qy ≤ r
Non-Negative restrictions: x ≥ 0, y ≥ 0
In the above condition x, and y are the decision variables.
The primary steps for solving linear programming problems are as follows:
Step 1: Mark the decision variables in the problem.
Step 2: Build the objective function of the problem and check if the function needs to be minimized or
maximized.
Step 3: Write down all the constraints of the linear problems.
Step 4: Ensure non-negative restrictions of the decision variables.
Step 5: Now solve the linear programming problem using any method generally we use either the simplex
or graphical method.
Linear Programming Methods
We use various methods for solving linear programming problems. The two most common methods used,

Methods

Graphical Simplex
Let’s learn about these two methods in detail in this article,
Linear Programming Simplex Method
One of the most common methods to solve the linear programming problem is the simplex method. In this
method, we repeat a specific condition ‘n’ a number of times until an optimum solution is achieved.
The steps required to solve linear programming problems using the simplex method are,
Step 1: Formulate the linear programming problems based on the given constraints.
Step 2: Convert all the given inequalities to equations or equalities of the linear programming problems by
adding the slack variable to each inequality where ever required.
Step 3: Construct the initial simplex table. By representing each constraint equation in a row and writing the
objective function at the bottom row. The table so obtained is called the Simplex table.

3
Step 4: Identify the greatest negative entry in the bottom row the column of the element with the highest
negative entry is called the pivot column
Step 5: Divide the entries of the right-most column with the entries of the respective pivot column,
excluding the entries of the bottommost row. Now the row containing the least entry is called the pivot row.
The pivot element is obtained by the intersection of the pivot row and the pivot column.
Step 6: Using matrix operation and with the help of the pivot element make all the entries in the pivot
column to be zero.
Step 7: Check for the non-negative entries in the bottommost row if there are no negative entries in the
bottom row, end the process else start the process again from step 4.
Step 8: The final simplex table so obtained gives the solution to our problem.
Linear Programming Graphical Method
Graphical Method is another method than the Simplex method which is used to solve linear programming
problems. As the name suggests this method uses graphs to solve the given linear programming problems.
This is the best method to solve linear programming problems and requires less effort than the simplex
method.
While using this method we plot all the inequalities that are subjected to constraints in the given linear
programming problems. As soon as all the inequalities of the given LPP are plotted in the XY graph the
common region of all the inequalities gives the optimum solution. All the corner points of the feasible region
are calculated and the value of the objective function at all those points is calculated then comparing these
values we get the optimum solution of the LPP.
Step 1. Formulate the LPP problems and develop objective function along with all the constraints
function.
Step 2. Graph the feasible region and find the corner points. The coordinates of the corner points
can be obtained by either inspection or by solving the two equations of the lines intersecting at that
point.
Step 3. Make a table listing the value of the objective function at each corner point.
Step 4. Determine the optimal solution from the table in step 3. If the problem is of maximization
(minimization) type, the solution corresponding to the largest (smallest) value of the objective function is the
optimal solution of the LPP.
We will see this method in more detail while solving a manufacturing problem.
Linear Programming Applications
Linear Programming has applications in various fields. It is used to find the minimum cost of a process
when all the constraints of the problems are given. It is used to optimize the transportation cost of the
vehicle, etc. Various applications of Linear Programming are
Engineering Industries
Engineering Industries use linear programming to solve design and manufacturing problems and to get the
maximum output from a given condition.
Manufacturing Industries
Manufacturing Industries use linear programming to maximize the profit of the companies and to reduce the
manufacturing cost.
4
Energy Industries
Energy companies use linear programming to optimize their production output.
Transportation Industries
Linear programming is also used in transportation industries to find the path to minimize the cost of
transportation.
Let us try to relate this theory with a manufacturing industry problem.

Example:- A furniture company produces inexpensive tables and chairs. The production
process for each is similar in that both require a certain number of hours of carpentry work
and a certain number of labour hours in the painting department. Each table takes 4 hours of
carpentry and 2 hours in the painting department. Each chair requires 3 hours of carpentry
and 1 hour in the painting department. During the current production period, 240 hours of
carpentry time are available and 100 hours in painting is available. Each table sold yields a
profit of E7; each chair produced is sold for a E5 profit. Find the best combination of tables
and chairs to manufacture in order to reach the maximum profit.

The decision variables can be defined as X = number of tables to be produced & Y = number of chairs to
be produced.

Now linear programming (LP) problem can be formulated in terms of X and Y and Profit (P).
maximize P = 7X + 5Y (Objective function)
subject to 4X + 3Y ≤ 240 (hours of carpentry constraint)
2X + Y ≤ 100 (hours of painting constraint)
Where, X ≥ 0, Y ≥ 0 (non-negative constraint).

Therefore, the mathematical formulation of the LPP is:

Maximize: P = 7X + 5Y
Subject to:
4X + 3Y ≤ 240
2X + Y ≤ 100
X≥0,Y≥0

To find the optimal solution to this LP using the graphical method we first identify the region of feasible
solutions and the corner points of the feasible region through the equations 4X + 3Y ≤ 240 & 4X + 3Y ≤ 240.
On finding the various solutions for X & Y we arrive at the following corner points for our graphs

5
On testing the corner points in equation P = 7X + 5Y gives the above profits. Therefore, the highest profit of
Rs. 410 is earned when we produce 30 units of Tables (X) & 40 units of Chairs (Y). Graphically the solution
will look like the below picture:

In the above graph the green shaded portion is represented by the feasible portion, through which the
company can maximise its profit by utilising the available limited resources.
The main advantages of graphical model is:
The graphical approach is of visual nature. Graphical methods provide us with a picture to go with the
algebra of linear programming, and the picture can anchor our understanding of basic definitions and
possibilities. For these reasons, the graphical approach provides useful background for working with linear
programming concepts.
6
However, some of the limitations of the graphical method are:
 this is useful only when the decision variables are not more than two.
 It is not possible to plot the solution on a two-dimensional graph when there are more than two
variables and we must turn to more complex methods.
 Another limitation of graphical method is that, an incorrect or inconsistent graph will produce inaccurate
answers, so one need to be very careful while drawing and plotting the graph

Conclusion

Linear programming is a powerful tool

used to optimise decision making. It
provides an effective way of representing
and solving complex problems in order to
achieve the best possible solution. Linear
programming has been applied successfully
across a wide range of industries, from
agriculture to engineering, helping
organisations save time and money by
improving their processes.
The main objective of linear programming
is to maximise or minimise a certain
outcome according to given
constraints. Overall, linear programming
offers numerous advantages for problem
solving due to its ability to provide optimal
solutions quickly and efficiently. Its
applications are wide ranging and it
continues to prove itself as a valuable asset
in many business operations today.

References
 Abstract, Introduction, Body from :- https://www.geeksforgeeks.org/linear-programming/

 Conclusion from :- https://www.complexica.com/narrow-ai-glossary/linear-programming

 Sample Problem from :- https://www.arsdcollege.ac.in/wp-content/uploads/2020/03/LPP-

Business-Mathematics-1.pdf

 Pictures from :- https://www.linkedin.com/pulse/solving-linear-programming-problem-using-

or-tools-sureshkumar-yunqc