FUTURE INSTITUE OF TECHNOLOGY

240, Garia Boral Main Road, Kolkata - 700154 West Bengal

(Affiliated To MAKAUT)

Detailed Report on

ubmitted as CA2 in
Subject Name (Subject Code)
for
the partial fulfillment of
B. Tech in
Mechanical Engineering
ubmitted as CA2 in
Subject Name (Subject Code)
for
the partial fulfillment of
B. Tech in
Mechanical Engineering
Graphical Method of Solving Linear Programming
Problems
Submitted as CA2 in

Optimization Techniques

(PCCAIML402)

for

the partial fulfilment of

B. Tech in

Computer Science and Engineering (AI & ML)

Submitted by:

Eshika Giri

(34230822009)

Submitted on: 16th of March, 2024

Index

1. Abstract 3
2. Introduction 3
3. What is linear programming? 4
4. Methods to Solve Linear Programming Problems
a. Graphical Method 5
b. Calculation 7
5. Discussion
a. Advantages 11
b. Disadvantages 11
c. Applications 12
6. Conclusion 13
7. References 13
Abstract
This report aims to delve into the utilization of graphical methods for solving Linear
Programming Problems (LPPs). Linear Programming is a mathematical technique employed to
optimize a linear objective function subject to linear constraints. Among the various
methodologies available for solving LPPs, the graphical method stands out for its visual and
intuitive approach, particularly beneficial for problems with two decision variables. Through a
systematic demonstration, this report delineates the steps involved in the graphical method,
elucidates its application in identifying feasible solutions and determining the optimal solution,
and discusses its advantages, limitations, and practical implications.

Introduction

Linear Programming (LP) is a powerful mathematical tool used across various disciplines to
optimize linear objective functions subject to linear constraints. Within LP, the graphical method
stands out as a visually intuitive approach, particularly useful for problems with two decision
variables.

The graphical method translates complex mathematical concepts into geometric representations
on a two-dimensional plane. By visually depicting constraints and objective functions, it offers
decision-makers clear insights into feasible solutions and optimal choices. Additionally, its
simplicity makes it an effective educational tool for teaching LP principles.

While the graphical method may lack the scalability of computational algorithms, its ability to
provide quick insights and conceptual clarity remains invaluable. This report aims to explore the
graphical method, outlining its methodology, applications, and significance in both educational
and practical contexts. Through this exploration, we aim to underscore the enduring relevance of
the graphical method in the realm of linear programming.
What is Linear Programming?

Linear programming (LP) or Linear Optimisation may be defined as the problem of

maximizing or minimizing a linear function that is subjected to linear constraints. The constraints
may be equalities or inequalities. The optimisation problems involve the calculation of profit and
loss. Linear programming problems are an important class of optimisation problems, that helps
to find the feasible region and optimise the solution in order to have the highest or lowest value
of the function.

In other words, linear programming is considered as an optimization method to maximize or

minimize the objective function of the given mathematical model with the set of some
requirements which are represented in the linear relationship. The main aim of the linear
programming problem is to find the optimal solution.

Linear programming is the method of considering different inequalities relevant to a situation

and calculating the best value that is required to be obtained in those conditions. Some of the
assumptions taken while working with linear programming are:

 The number of constraints should be expressed in the quantitative terms

 The relationship between the constraints and the objective function should be linear

 The linear function (i.e., objective function) is to be optimized

Methods to Solve Linear Programming Problems

The linear programming problem can be solved using different methods, such as the graphical
method, simplex method, or by using tools such as R, open solver etc. This report will discuss
the graphical method in detail.
Graphical Method

Graphical method works for almost all different types of problems but gets more and more
difficult to solve when the number of decision variables and the constraints increases.

Step 1: Formulate the LP Problem The initial step involves formulating the Linear Programming
(LP) problem, which we have covered in a preceding section. This phase is pivotal as all
subsequent steps hinge upon the analysis conducted here.

Step 2: Construct a Graph and Plot Constraint Lines The graph must be built in 'n' dimensions,
where 'n' signifies the number of decision variables. This step's complexity escalates with an
increase in decision variables, considering our limitations in envisioning dimensions beyond
three. Constraint lines are established by connecting the horizontal and vertical intercepts derived
from each constraint equation.

Step 3: Determine the Valid Side of Each Constraint Line This step aids in delineating the
domain of available space conducive to a feasible solution. The validity of each constraint line's
side is determined by assessing whether the origin's coordinates (0,0) yield a tangible solution for
the objective function. If affirmative, the side containing the origin is deemed valid; otherwise, it
lies on the opposing side.

Step 4: Identify the Feasible Solution Region The feasible solution region on the graph
comprises the space satisfying all constraints, akin to the intersection of valid regions from each
constraint line. Any point within this area is deemed a valid solution for the objective function.

Step 5: Plot the Objective Function on the Graph As the objective function comprises linear
equations, its depiction on the graph yields a straight line. It's imperative to distinguish this line
from constraint lines to avert confusion. Assigning a random constant value in the equation
ensures clear differentiation.

Step 6: Find the Optimum Point

To find the optimum point, which always resides on one of the corners of the feasible region, a
systematic approach is essential. Follow these steps:

1. Place a ruler on the graph sheet, aligning it parallel to the objective function. Maintain the
orientation of the ruler fixed in space, focusing solely on the direction of the objective
function's straight line.

2. Start from the furthest corner of the graph and gradually slide the ruler towards the origin.

3. For minimizing the objective function, identify the point where the ruler makes contact
with the feasible region closest to the origin. This point represents the optimum solution
for minimizing the function.

4. Conversely, for maximizing the objective function, pinpoint the point of contact between
the ruler and the feasible region farthest from the origin. This serves as the optimum point
for maximizing the function.

By employing this methodical approach, one can efficiently locate the optimum point within the
feasible region, aligning with the objective of either minimizing or maximizing the function.

Step 7: Calculate the Coordinates of the Optimum Point This final step culminates in
determining the precise coordinates of the optimum point. Upon locating this pivotal point, its
coordinates can be ascertained through a straightforward geometric approach. Draw two
perpendicular lines from the point onto the coordinate axes, enabling the identification of its
coordinates.

Alternatively, if the optimum point coincides with the intersection of two constraint lines, an
algebraic approach can be pursued. By solving a set of simultaneous linear equations, the
coordinates of the optimum point can be derived. These coordinates provide the values of the
decision variables essential for optimizing the objective function.

To obtain the optimized objective function, simply substitute these parameter values into the
equation of the objective function. This straightforward calculation unveils the optimized value
of the objective function, reflecting the culmination of the linear programming analysis.

Calculation

Let us deepen our comprehension of this concept through an illustrative example.

Question:

Solve the given linear programming problems graphically:

Maximize: Z = 50x + 15y

Constraints are,

 5x + y ≤ 100

 x + y ≤ 50

 x ≥ 0, y ≥ 0

Solution:

Step 1: Finding Points

Expressing the constraints as equations:

5x+y=100 (i)

x+y=50 (ii)

To determine the points:

From equation (i):

  When x=0, y=100

 When y=0, x=20

Thus, the points are (0,100)(0,100) and (20,0)(20,0).

From equation (ii):

 When x=0, y=50

 When y=0, x=50

Thus, the points are ((0,50) and (50,0).

Step 2: Plotting Points and Finding the Feasible Region

Fig. [1]

Step 3: Determining the Objective Function Value

To establish the convenient value of the objective function Z, we calculate the least common
multiple (LCM) of the coefficients of 50x+15y, which is 150. Therefore, the value of Z is a
multiple of 150, specifically 300.
50x+15y=300

Now, to find the points:

Substitute x=0,y=20

Substitute y=0,x=6

Next, plot the line representing this objective function on the graph.

Fig. [2]

Step 4: Determining the Maximization Objective Function Line

Since the objective function is of the maximization type, we draw a line parallel to the objective
function line, positioned farthest from the origin, and having only one common point with the
feasible region. This ensures that the objective function attains its maximum value at this
intersection point.
 Fig. [3]

Step 5: Determining the Optimal Solution of the Objective Function

Having identified the common point (12.5,37.5)(12.5,37.5) with the feasible region, we proceed
to calculate the optimal solution of the objective function:

Z=50x+15y

Z=50(12.5)+15(37.5)

Z=625+562.5

Z=1187

Thus, the maximum value of Z under the given constraints is 1187.

 Discussion

Advantages:

 Intuitive Visualization: By providing a graphical representation of the problem, the method

facilitates a clear and intuitive understanding of the optimization process, enhancing problem
comprehension and interpretation. Decision-makers can visually grasp the trade-offs and
constraints involved, aiding in the formulation of effective strategies.
 Educational Utility: The graphical method serves as an invaluable pedagogical tool for
teaching linear programming concepts due to its simplicity and visual nature. Students can
actively engage with graphical representations, thereby enhancing their understanding of
fundamental principles and problem-solving techniques.
 Efficiency for Small-Scale Problems: The graphical method excels in solving small-scale
problems characterized by a limited number of decision variables and constraints. Its
straightforward approach allows for quick and efficient solution generation, making it ideal
for introductory exercises and basic analyses.

Disadvantages:

 Limited Applicability to Complex Problems: As the number of decision variables and

constraints increases, the graphical method becomes impractical. Graphical representation
becomes cumbersome and difficult to manage, making it challenging to visualize high-
dimensional problem spaces accurately. Consequently, the method may not be suitable for
tackling large-scale or highly complex optimization problems.
 Potential Inaccuracy: In cases involving non-linear objective functions or non-convex feasible
regions, the graphical method may yield approximate or inaccurate results. The method relies on
linear approximations and convexity assumptions, which may not hold true for all problem
instances. Consequently, more sophisticated solution techniques, such as linear programming
solvers or nonlinear optimization algorithms, are necessary to obtain precise solutions in such
scenarios.
Applications:

Despite its limitations, the graphical method finds application in various fields:

 Production Planning: In manufacturing and operations management, the graphical method

can aid in optimizing production schedules, resource allocation, and inventory management.
Decision-makers can visually analyze production constraints and identify optimal production
levels to maximize efficiency and minimize costs.
 Finance and Investment: In finance, the graphical method can be utilized for portfolio
optimization, risk management, and asset allocation. Investment analysts can visually assess
the trade-offs between risk and return, helping investors construct well-diversified portfolios
that align with their investment objectives.
 Transportation and Logistics: The graphical method finds application in optimizing
transportation routes, supply chain management, and logistics operations. By visually
analyzing transportation costs, capacity constraints, and delivery schedules, logistics
managers can optimize routes and minimize transportation expenses, thereby enhancing
overall supply chain efficiency.
 Project Management: In project management, the graphical method can assist in
scheduling, resource allocation, and project planning. Project managers can visually depict
project constraints, critical paths, and resource dependencies, enabling them to optimize
project timelines and allocate resources effectively to meet project objectives.

Conclusion
In conclusion, the graphical method stands as a valuable approach for solving
In conclusion, the graphical method offers a valuable approach for solving Linear Programming
Problems (LPPs), particularly in educational contexts and for addressing small-scale problems.
Its intuitive nature and straightforward methodology make it an invaluable tool for both students
and practitioners, aiding in the understanding of linear programming concepts and enabling the
generation of quick solutions. However, its applicability is limited to scenarios with few decision
variables and constraints, and it may encounter challenges in accurately solving complex
problem instances, especially those involving non-linear objective functions or non-convex
feasible regions.

Nevertheless, despite its limitations, the graphical method remains a fundamental technique in
the realm of linear programming. Serving as a cornerstone in educational settings for teaching
optimization principles, it complements more advanced algorithms when addressing larger and
more intricate problems. Its enduring significance underscores its role as a foundational tool,
contributing to the advancement of optimization theory and practice while providing initial
insights and facilitating strategic formulation in diverse applications.

References

The information presented in this report has been gathered from the following sources:

 https://www.geeksforgeeks.org/graphical-solution-of-linear-programming-problems/
 https://www.toppr.com/guides/maths/linear-programming/graphical-method-of-solving-
a-linear-programming-problem/
 https://byjus.com/maths/linear-programming/
 https://www.vedantu.com/maths/graphical-method-linear-programming