Chapter 11: Linear Programming using Graph

Chapter 11
Linear Programming using Graph

11.1 Linear Programming (LP)

Introduction: Linear programming (LP) is a mathematical method, used to determine the best
possible outcome or solution from a given set of parameters or list of requirements, which are
represented in the form of linear relationships. This method is mostly used in computer modeling
or simulation, in order to find the best solution in allocating finite resources, such as: money,
energy, manpower, machine resources, time, space and many other variables. In most cases, the
"best outcome" needed from linear programming is Maximum/Highest Profit or
Minimum/Lowest Cost. Because of its nature, linear programming is also called Linear
Optimization. Linear programming is part of an important area of mathematics called
"Optimization techniques" as it is literally used to find the most optimized solution to a given
problem. A very basic example of linear optimization usage is in logistics or the "method of
moving things around efficiently."

Importance: The importance of linear programming is everywhere in daily life, e.g., when

driving from home to work, the linear programming find the shortest route, or thinking about the

strategies to make team work efficiently for on-time delivery of the project. Linear programming

is used to obtain the most optimal solution for a problem minimizing the given constraints.

Applications of Linear Programming

Optimization through Linear Program is used in various industries. Manufacturing and service

industry uses it on regular basis. Linear Programming (LP) is mostly utilized in following areas:

1. Manufacturing industry use LP for analyzing their supply chain operations for maximum

efficiency with minimum operative cost by; reconfiguring their storage labor, adjusting

their workforce and reducing the bottlenecks.

2. LP is also used to organize retail for shelf space optimization, especially in stores and

hyper departmental store. The store products are placed strategically keeping in mind the

1
 Chapter 11: Linear Programming using Graph

customer shopping pattern, to make it easy for a customer to locate and select the right

product.

3. LP is also used in optimizing Delivery Routes, popular for problems of Traveling

Salesman. Service industry used optimization in finding the best possible route for

multiple salesmen traveling to multiple cities. The objective is to minimize cost and time.

4. Optimization is also used in Machine Learning. A system is trained to fit on a

mathematical model of a function from the labeled input data to predict values from an

unknown test data.

Example:
Suppose there are 1000 boxes of the same size of 1 cubic meter each; 3 trucks that are able to
carry 100 boxes, 70 boxes and 40 boxes respectively; several possible routes; and 48 hours to
deliver all the boxes.
Linear programming provides the mathematical equations to determine the optimal truck loading
and route to be taken, in order to meet the requirement of getting all boxes from point A to B,
with the least amount of going back and forth and, of course, the lowest cost at the fastest time
possible.

11.2 Methods of Solving Equations by Linear Programming

Linear programming method for solving the equations is classified by two methods: (1)

Graphical method and (2) Simplex method. The Simplex method for solving the equation will be

discussed in detail in next Chapter.

The graphical method for linear programming is most suitable when there are two decision

variables. Using graphs a set of linear inequality, subject to constraint, is formulated. Then the

inequalities are plotted on X/Y plane. The intersecting region gives the feasible region, which

defines or explains all values that can be taken. This also provides the optimal solution.

2
 Chapter 11: Linear Programming using Graph

The graphical method consists of two main phases:

1. Finding the ‘solution space’ (the space where we have all the valid solutions) by drawing

each constraint.

2. Finding the ‘optimal solution’ – a solution that will give us the maximum value for the

objective function.

11.3 Terminologies in Linear Programming

There are some common terminologies utilized in Linear Programming:

- Decision Variable: These are the variables that decide the output of the solution to a problem.

To solve a problem, it is necessary to identify the decision variables, denoted by A, B, X, Y.

- Objective Function: It defines the main objective for decision making. In business a company

may wish to increase its total profit, i.e., the profit is the main objective function.

- Limitations/Constraints: There may be limitations on decision variables, which limit the

value of decision variables. In a business the resources may be main constraints.

- Non-negativity Restriction: For any linear programs, the decision variables should always be

positive, i.e., non-negative values. The values of decision variables should be ≥ 0.

11.4 Components of Linear Programming

The basic components of linear programming are as follows:
- Decision Variables - These are the quantities to be determined.
- Function - This represents how each decision variable would affect the cost, or, simply, the
value that needs to be optimized.
- Constraints - These represent how each decision variable would use limited amounts of
resources.

3
 Chapter 11: Linear Programming using Graph
- Information / Data - These quantify the relationships between the objective function and the
constraints.

11.5 Bounded and Unbounded Feasible Regions

Bounded feasible Regions: A bounded feasible region will have both a maximum value and a
minimum value for the objective function. A bounded feasible region may be enclosed as shown
in a circle.
Unbounded Feasible Regions: An unbounded feasible region cannot be enclosed in a circle, no
matter how big the circle is. If the coefficients on the objective function are all positive, then an
unbounded feasible region will have a minimum but no maximum.
Unbounded feasible regions often result from standard minimization problems.
Empty Feasible Regions: If the feasible region is empty, then there is no Maximum or Minimum
value. An empty region results when there are no points that satisfy all of the constraints. If there
are no points that satisfy the constraints, there can be no points to have a maximum or minimum
value.

Existence of solution of Linear Programming Problem:

1. Initial Solution: Set of values of decision variables satisfying all the constraints of a
linear programming problem is called a solution to that problem.
2. Feasible Solution: Any solution which also satisfies the non-negativity restrictions of the
problem is called a feasible solution.
3. Optimal Feasible Solution: Any feasible solution which maximizes or minimizes the
objective function is called an optimal feasible solution. the iso-profit line increases in
value (assuming the coefficients are positive) as it moves through the feasible region.
Since the feasible region is bounded, there is a limit on how far the iso-profit line can
move. Therefore, there is a limit on how big it can get and there is a maximum value.

11.6 General Steps of Linear Programming Algorithm

4
 Chapter 11: Linear Programming using Graph
Programming refers to mathematical programming. Linear programming refers to a planning
process that allocates resources: Labor, Materials, Machines and capital; in the best possible
(Optimal) way, so that costs are minimized or profits are Maximized. In LP these resources are
known as Decision Variables and selecting the best values of the decision variables (Maximize
profit or Minimize cost) is known as Objective function. The limitations on resource availability
form, is known as a Constraint set. A Linear Program comprises four main steps:
A: Formulate the Linear programming problem: This is the most crucial step depends on
analysis. Find decision variables, the objective function and constraints in the given
problem. Get the information from given data and formulate the strategy.
B: Construct a graph and plot the constraint lines: The graph must be constructed in ‘n’
dimensions, where ‘n’ is the number of decision variables. For linear functions, at least two
points are required to plot the points on graph. The constraint lines can be constructed by
joining the horizontal and vertical intercepts found from each constraint equation. The graph
would give the idea about the complexity of number of decision variables.
C: Determine the valid side of each constraint line: This is used to determine the domain of
the available space, which can result in a feasible solution. Put the coordinates of the origin
(0,0) in the problem and determine whether the objective function takes on a physical
solution then this side of the constraint lines from the origin is the valid side; otherwise the
opposite one.
D: Identify the feasible solution space/region: The feasible solution region on the graph is
the one which is satisfied by all the constraints. It could be viewed as the intersection of the
valid regions of each constraint line as well. Choosing any point in this area would result in a
valid solution for our objective function.
E: Plot the objective function on the graph: Choose the constant value in the equation of
the objective function randomly, just to make it clearly distinguishable.
F: Find the Optimum Point: An optimum point always lies on one of the corners of the
feasible region. Place a ruler on the graph sheet, parallel to the objective function. Be sure to
keep the orientation of this ruler fixed in space. Now begin from the far corner of the graph
and tend to slide it towards the origin.
- If the goal is to minimize the objective function, find the point of contact of the ruler
with the feasible region, which is the closest to the origin. This is the optimum point
for minimizing the function.
- If the goal is to maximize the objective function, find the point of contact of the ruler
with the feasible region, which is the farthest from the origin. This is the optimum
point for maximizing the function.
G: Calculate the coordinates of the optimum point: This is the last step of the process, may
be solved: Graphically or Algebraically:
(i) Graphically: First locate the optimal point and find the coordinates. This can be
done by drawing two perpendicular lines from the point onto the coordinate axes
and noting down the coordinates.

5
 Chapter 11: Linear Programming using Graph
(ii) Algebraically: The optimum point is at the intersection of two constraint lines.
Find it by solving the set of simultaneous linear equations.
The Optimum Point gives the values of the decision variables necessary to optimize the
objective function. To find out the optimized objective function, one can simply put in the
values of these parameters in the equation of the objective function.

11.7 Graphically solution of the Linear Program system of equations by

Corner Point methods and ISO-profit / ISO-cost
Solution of LPP by Corner Point method

Definition: The optimal solution to a Linear Program Problem (LPP) occurs (if exists), at the

corners of the feasible region. The optimal solution obtained through the corner points of feasible

region is called Corner Point method.

Steps of solving LPP by Corner Point method:
A. Organize given information in a chart:
Formulate the linear programming problem.
B. Write constraints [Inequalities]:

C. Write objective function: Minimize cost: Z = 80x + 50y

Graphically find the feasible region to calculate the Objective function of the LPP.
D. Draw graph of all constraints to find feasible region; note that the last two constraints
limit the region to the first quadrant:
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. Identify the Corner point at which the value of the objective
function is Maximum or Minimum depending on the Linear Program. The coordinates of
this vertex is the optimal solution and the value of ‘Z’ is the optimal value.
E. Find coordinates of all Corner Points (From the graph):

Make a list of the objective function at each Corner point. Find the coordinates of the

each corner or vertex of the feasible region. These coordinates can be obtained from the

graph or by algebraically solving the constraint equations of the lines. If the problem is of

Maximization type, the solution corresponding to the largest value of the Objective

6
 Chapter 11: Linear Programming using Graph

function is the optimal solution of the LPP. If the problem is of Minimization type the

smallest value of the objective function is the optimal solution. Maximization LPPs are

usually identified by the less than sign in all the constraints. Minimization problems can

be identified by a Greater than sign in all the constraints.

F. Substitute each Corner Point into objective function to find Minimum cost or
Maximum profit cost:

For each corner point or vertex computer the value of the objective function
G. Answer the question:

Example 1:

A decorative item dealer wants to maximize profit function: Z = 50x + 18y

Subject to the constraints: 2x + y ≤ 100
x + y ≤ 80

x ≥ 0, y ≥0
(a) Find the Feasible solution (b) Find the Optimal solution.

Solution(a):
Since x and y are ≥ 0, only first Quadrant of the xy-plane is required.
The equations are straight line following the general equation of straight line: y = mx + c.
At least two points are required to draw the graph of the equations:
2x + y =100 –––––– (I) and x + y = 80 –––––– (II)
From Eq. I: y = 100 – 2x
For x = 0 , y = 100; x = 25 , y = 50; x = 50 , y = 0
From Eq. II: y = 80 – x
For x = 0 , y = 80; x = 40 , y = 40; x = 80 , y = 0

7
 Chapter 11: Linear Programming using Graph

The intersection of regions R1 and R1'

is the feasible solution. Therefore every
point in shaded region is a feasible
solution.

Solution(b):
Finding the Optimal solutions by Corner Point Method:
Corner Point Method:
States that the Optimal solution Linear Programming Problem occurs at the corners of the
feasible region.
Algebraically solve equations of constraints to find the coordinates of the feasible region
to get point of intersection:
2x + y =100 –––––– (I) and x + y = 80 –––––– (II)
From Eq. I: y = 100 – 2x substituting in Eq. II: x = 80 – (100 – 2x)
x = 80 – 100 + 2x  x – 2x = – 20 and x = 20
Substituting in Eq. I: 2(20) + y =100 therefore: y = 100 – 40 = 60
Find coordinates of all Corner Points (From the graph):
A is intersection of line 2 with y-axis (0,80)
B is intersection of line 1 and line 2 (20,60)
C is intersection of lines 1 with x-axis (50,0)
Substitute each Corner Point into objective function to find minimum cost:
1. At A(0,80); Z = 50x + 18y = 50(0) + 18(80) = 1,440
2. At B(20,60); Z = 50x + 18y = 50(20) + 18(60) = 2,080
3. At C(50,0); Z = 50x + 18y = 50(50) + 18(0) = 2,500
Answer:

8
 Chapter 11: Linear Programming using Graph
The optimal solution is the maximum profit. The largest value of the objective function Z
= 2,500 at (50, 0) is the optimal solution.

Example 2:

A farmer acquires 110 hectares land. He decided to grow Wheat and Barey on the land.

He has toal budget of US$10,000 and 1,200 man-days during the planning season. He

wishes to plant each variety in the 110 hectares, given the costs, net profits and labor

requirements according following data:

Variety Cost(Price/Hec) Net Profit (Price/Hec) Man-days/Hec
Wheat 100 50 10
Barley 200 120 30
Find the optimal solution and the optimal value.

Solution:
The steps to formulate the linear program:
A. Suppose total area for growing Wheat = x and total area for Barley = y.
‘x’ and ‘y’ are the decision variables.
B. Write Objective function
The net profit expected to be earned for the entire product for Wheat and Barley
for each hectare is US$50 and US$120.
So, the objective function (z) will be z = 50x + 120y
C. From the given data, there are 3 limitation/constraints:
(i) Limited budget of US$10,000. Therefore the equation becomes:
100x + 200y ≤ 10,000
(ii) The availability of man-days is 1,200. The man-days per hectare for
Wheat and Barley is given.
10x + 30y ≤ 1200
(iii) The third limitation/constraint, the values of ‘x’ and ‘y’ is greater than or
equal to zero. x ≥ 0 and y ≥ 0
D. Solving the linear program through Graphical method:
Since both x and y are ≥ 0, (Positive values: 1st Quadrant).
Simplify the first equation: 100x + 200y ≤ 10,000
Divide both sides of equation by 100: x + 2y ≤ 100 –––––––––(I)

9
 Chapter 11: Linear Programming using Graph
Simplify the second equation: 10x + 30y ≤ 1200
Divide both sides of equation by 10: x + 3y ≤ 120 –––––––––(II)
The third equation is: x + y ≤ 110 ––––––––––(III)
To draw the graph of the three equations at least two points are required for each
equation.
From Eq. I: x + 2y = 100  x = 100 – 2y
for y=40, x=100–2(40)=100-80=20; for y=30, x=100–2(30)=100-60=40
From Eq. II: x = 120 – 3y
for y=20, x=120–60=60; for y=30, x=120–90=30
From Eq. III: y = 110 – x
for y=50, x=110–50=60; for y=60, x=110–60=50
The points are: (20,40), (40,30); (60,20), (30,30); (50,60) , (60,50)
Scale: 1 division = 5 units.

From the graph it is observed that:

(i) The optimal feasible solution is
achieved at the point of intersection
where the budget and man-days
constraints are active. This means the
point at which the equation x + 2y ≤
100 and x + 3y ≤120 intersect gives the
optimal solution.
(ii) The values of ‘x’ and ‘y’ gives the
optimal solution at (60,20). To
maximize the profit the farmer should
produce Wheat and Barley in 60
hectares and 20 hectares of land
respectively.
(iii) The objective function or the maximum profit equation:
z = 50x+120y, therefore; z = 50(60)+120(20) = 3000+2400 = US$5400.

Example 3:

Graphically solved the following linear programming problem.

Maximize: Z = 18x + 24y
Subject to the constraints: 2x + y ≤ 12
3x + 6y ≤ 24
x + y ≤ 10
10
 Chapter 11: Linear Programming using Graph
2x – 0.5y ≤ 1
x ≥ 0, y ≥ 0

Solution:
The graphical method of solving linear program problem consists of two main phases:
Finding the solution space (the space where we have all the valid solutions) by drawing
each constraint.
Finding the optimal solution that will provide the maximum value for the objective
function.
First find solution space, by drawing graph of each equation. At least two points from
each equation are required to draw:
2x + y ≤ 12 3x + 6y ≤ 24 x + y ≤ 10 2x – 0.5y ≤ 1
2x + y ≤ 12 3(x + 2y) ≤ 3(8) x + y ≤ 10 2x – 0.5y ≤ 1
2x + y = 12 –– (I) x + 2y = 8 –– (II) x + y = 10 –– (III) 2x – 0.5y ≤ 1 –– (IV)
For x=0, in Eq. I; y=12-2(0)=12; For y=0, in Eq. I; 2x=12-0, x = 6
For x=0,in Eq. II; 2y = 8-0, y = 8/2 = 4; For y=0, x=8-2(0)=8; x + y ≤ 10
For x=4, in Eq. III; y = 10-4=6; For y=4, x=10-4= 6;
For y=0, in Eq. IV; 2x=1-0.5(0), x=0.5; For y=-2, 2x=1-0.5(-2), x=0;
Draw the Points are: (0,12), (6,0); (0,4), (8,0); (4,6), (6,4); (0.5,0), (0,-2);
Scale: 2-divisions = 1 units

The last constraints are x ≥ 0 and y ≥ 0, means the

solution is in the first quadrant. The solution space
is the common space of all the constraints and three
possible points (I, J and F). To find the optimum
solution, find the slope of the object function. The
slope of objective function is between the slopes of
first and second constraint: slope of first constraint
is 2/1 = 2 and slope of second constraint is ¾ = ½,
Optimum solution between: 1/2 < 0.75 < 2.

11
 Chapter 11: Linear Programming using Graph
To find the value of optimum solution, find the point of intersection of first and second
constraint: 2x + y = 12 and x + 2y = 8
Multiply first Eq. by -2 and add in second Eq.: -2(2x+y) + (x+2y) = -2(12) + 8
- 4x – 2y + x + 2y = -24 + 8 so, -3x = -16; x = 16/3 = 5.33;
Substitute in first Eq. 2(5.33)+y = 12  10.66+y = 12  y = 12-10.66 = 1.33
Substitute ‘x’ and ‘y’ in ‘Z’
Maximize Z = 18x + 24y = 18(5.33) + 24(1.33) ~ 128.87 ~ 128

Exercise 11.1
11.1.1 Graphically solve the following Linear Program system of equations:
1. Mr. Carter eats a mix of Cereal A and Cereal B for breakfast. The amount of
calories and sodium per ounce for each is shown in the table below. Mr. Carter's
breakfast should provide at least 480 calories but less than 700 milligrams of
sodium.
Cereal A Cereal B
Calories /ounce 100 140
Sodium (mg/ounce) 150 190
2. A student spending spring break in Ireland wants to visit Karachi and Lahore.
The student has at most 7 days available and at most 500 Euros to spend. Each
day spent in Karachi will cost 50 Euros and each day spent in Lahore will cost 60
Euros. Let x be the number of days the student will spend in Karachi and y, the
number of days the student will spend in Lahore. Which of the following sets of
constraints describe the constraints on the student's time and money for the
visits?
(a) x+y≤7 (b) x + 7y ≤ 500
50x + 60y ≤ 500 50x + 60y ≤ 1000

x ≥ 0; y ≥ 0 x ≥ 0; y ≥ 0
(c) x+y≥7 (d) x + y ≥ 500
60x + 50y ≥ 500 50x + 60y ≥ 7
x ≤ 0; y ≤ 0 x ≥ 0; y ≤ 0
3. Find the Vertices of the feasible set corresponding to the system of
inequalities:
x–y≥2
y + 2x ≥ 6
4. Determine if (x; y) = (1; 2) is in the feasible set for following system of
inequalities and graph the feasible set for the system of inequalities:
2x + 3y ≥ 6 2x – 3y ≥ 15

12
 Chapter 11: Linear Programming using Graph

11.1.2 Solve the LPP by Corner Point method

1. (Diet problem) A house wife wishes to mix two types of food F1 and F2 in such
a way that the vitamin contents of the mixture contain at least 8 units of vitamin
A and 11 units of vitamin B. Food F1 costs E60/Kg and Food F2 costs E80/kg.
Food F1 contains 3 units/kg of vitamin A and 5 units/kg of vitamin B while Food
F2 contains 4 units/kg of vitamin A and 2 units/kg of vitamin B. Formulate this
problem as a linear programming problem to minimize the cost of the mixtures.
2. A paint manufacturer produces two types of paint, one type of standard quality
(S) and the other of top quality (T). To make these paints, he needs two
ingredients, the Pigment and the Resin. Standard quality paint requires 2 units of
pigment and 3 units of resin for each unit made, and is sold at a profit of R1 per
unit. Top quality paint requires 4 units of pigment and 2 units of resin for each
unit made, and is sold at a profit of R1.50 per unit. He has stocks of 12 units of
pigment, and 10 units of resin. Formulate the above problem as a LPP linear
programming problem to maximize his profit?
3. Solve the Linear Programming Problem formulated in problem 1; graphically by
Corner Point method to find condition for the Minimum cost.
4. Solve the Linear Programming Problem formulated in problem 2; graphically by
Corner Point method to find condition to Maximize cost.
5. 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 Euros 7;
each chair produced is sold for a Euros 5 profit. Find the best combination of
tables and chairs to manufacture in order to reach the Maximum profit.
6. A small Shake shop produces Milkshake and Ice-juice. Suppose that production
is limited by scarce resources of Dry Milk, Strawberry and Banana. To make
Milkshake 5kg of Milk, 4kg of Banana and 35kg of Strawberry are required. To
make Ice-juice 15kg of Milk, 4 kg of Banana and 20kg of Strawberry are
required. Suppose that only 480 kg of Milk, 160kg of Banana and 1190 kg of
Strawberry are available. If the Shakes make a profit of Euros 13 for each Kg of
Milkshake and Euros 23 for each kg of Ice-juice, how much Milkshake and Ice-
juice should the Shake shop produce in order to maximize profit?
7. Graphical solve following problem:
Maximize: Z = f(x,y) = 3x + 2y
Subject to: 2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24
13
 Chapter 11: Linear Programming using Graph
x ≥ 0, y ≥ 0
8. The liquid portion of a diet is to provide at least 300 calories, 36 units of vitamin
A, and 90 units of vitamin C daily. A cup of dietary drink X provides 60 calories,
12 units of vitamin A, and 10 units of vitamin C. A cup of dietary drink Y
provides 60 calories, 6 units of vitamin A, and 30 units of vitamin C. Now,
suppose dietary drink X costs $0.12 per cup and drink Y costs $0.15 per cup. Use
Corner Point method to find how many cups of each drink should be consumed
each day to minimize the cost and still meet the state daily requirements?
9. An animal feed to be mixed from soybean meal and oats must contain at least
120 lb of protein, 24 lb of fat, and 10 lb of mineral ash. Each 100-lb sack of
soybean meal costs $15 and contains 50 lb of protein, 8 lb of fat, and 5 lb of
mineral ash. Each 100-lb sack of oats costs $5 and contains 15 lb of protein, 5 lb
of fat, and 1 lb of mineral ash. Using Corner Point method find out how many
sacks of each should be used to satisfy the minimum requirements at minimum
cost? What is the minimum cost?
10. A dietitian wishes to combine two foods, A and B, to make a mixture that
contains at least 50 g of protein, at least 130 mg of calcium, and not more than
550 calories. The nutrient values of foods A and B are given in the table.
Food Protein (g/cup) Calcium (mg./cup) Calories (cup)
A 20 20 100
B 10 50 150
Using Corner Point method find out how many cups of each of the foods should
the dietitian use?
11. A farmer planning spring planting has decided to plant up to a total of 120 acres
in corn and soybeans. An estimate of the investment required and the expected
return per acre for each appears in the table.
Crop Investment Return Investment Return
Corn $20 $50
Soybeans $35 $80
Because corn is needed for feed purposes on the farm, the farmer needs at least
38 acres of corn, and the budget can cover at most $3000 for both corn and
soybeans. How many acres of corn and how many acres of soybeans should be
planted to maximize the return from these two crops?

11.8 Graphical Solution of Linear Program by ISO–profit / ISO–cost Method

If an LPP has many constraints, then the corner point method it becomes long and tedious
to find all the corners of the feasible region. There is another alternate and more general
method to find the optimal solution of an LP, known as: ISO–profit or ISO–cost method.
In LPP the graph of the profit function is called an ISO-profit line, because "ISO" means
"Same" or "Equal" and the profit anywhere on the line is the same.

14
 Chapter 11: Linear Programming using Graph
Steps of ISO-profit / ISO-cost method of LPP
A: Optimize: Z = ax + by
Subject to the constraints: a1x + b1y ≤ ( or ≥) c1
a2x + b2y ≤ ( or ≥) c2
x≥0,y≥0
B: Draw the lines / half planes of the constraints.
C: Intersection of all the half planes are shaded, this is the Feasible Region.
D: Draw the dotted line to represent Objective Function Z = ax + by = k.
E: For Maximize ‘Z’, draw a line parallel to: ax + by = k; nearest to the origin. This
line should contain at least one point of the feasible region.
F: Find the coordinates of this point by solving the equation of the line where it lies.
G: If (x1,y1) is the point found in Step E, then: x = x1 and y = y1 is the optimal
solution of the LPP and Z = ax1 + by1 is the optimal value.
Important Note on ISO-profit/ISO-cost method:
Moving the ISO-profit dotted line towards the origin reduces the value of the objective
function, since origin limitation, the value is bounded below and so there is a minimum.
The ISO-profit line increases in value (assuming the coefficients are positive) as it moves
through the feasible region. Since the feasible region is unbounded, there is no limit on
how far the ISO-profit line can move. Therefore, there is no limit on how big it can get
and there is no maximum value. Moving the ISO-profit line down and to the left towards
the origin reduces the value of the objective function. There are boundary lines that block
how far down or to the left, so there is a Minimum value that can be reached and still stay
in the feasible region.

Example 1:
Linear Program to find the Optimal solution of the following problem:
Formulate
A company uses wood and labor to produce tables and chairs. Recall that unit profit for
tables is $6, and unit profit for chairs is $8. There are 300 board feet (bf) of wood

available, and 110 hours of labor available. It takes 30 bf and 5 hours to make a table, and

20 bf and 10 hours to make a chair.

Solution:
A. Organize given information in a chart:
Table contains the information for the Linear Programming Problem. Let x1 be
the number of tables and x2 be the number of chairs.
Resources Wood (bf) Labor (hr) Unit profit
Table (x1) 30 5 $6
Chair (x2) 20 10 $8
15
 Chapter 11: Linear Programming using Graph
Available 300 110 Z
The bottom row is used to formula the Objective function, developed in such a way
that either maximize or minimized.
B. Write constraints [Inequalities]:
In this case, the company’s management wishes to Maximize unit Profit. The wood
and labor row is used to formula the constraint set
Subject to the constraints: 30x1 + 20x1 < 300
5x1 +10 x2 < 110
x1, x1 > 0 (Non-negative condition)
C. Write objective function: Maximize profit: Z = 6x1 + 8x2

D. Graph all constraints to find feasible region; note that the last two
constraints limit the region to the first quadrant:
At least two point are required to draw a line.
For wood: 30x1 + 20x1 = 300 ––––––– (I) and
For labor: x1 +10 x2 = 110 ––––––– (II)

For Wood:
300
15
For x1= 0 in Eq. I; 30(0) +20x2 =300  20x2 =300  x2= 20 chairs
110
10
For x1= 0 in Eq. II; 0+10x2=110  10x2=110  x1= 10 tables

For Labor:
110
10
For x1=0 in Eq. II; 0+10x2=110  10x2=110  x2 = 10 tables
110
22
For x2=0 in Eq. II; 5x1+10(0)=110  5x1=110  x1 = 5 chairs
E: Determine the valid side of each constraint line:
Starting from the Origin (0,0), to check for valid side:
Substitute in (0,0) in Eq. I: 30(0) + 20(0) < 300  0 > 300 Valid side.
Substitute in (0,0) in Eq. II: 5(0) + 10(0) < 110  0 > 110 Valid side.
Draw arrow to indicate the valid side of each constraint line:

16
 Chapter 11: Linear Programming using Graph

F: Identify the Feasible Region: The feasible region is the area on the valid side of
both constraint lines. Any point located on the invalid side of a constraint line is
infeasible. Since there is non-negative condition, the feasible region is restricted to
First (Positive) Quadrant only.
G: Plot two Objective Function Lines: Objective function lines are drawn to
determine the direction of improvement by arbitrarily selecting set profit: Z = 48
and then set profit, Z = 72 and plot the two lines:
48
6
For Z = 48; 6x1 + 8x2 = 48; Put x1=0 then x2= 8 ;
48
8
Put x2=0 then x1= 6
72
9
For Z = 72; 6x1 + 8x2 = 72; Put x1=0 then x2= 8 ;
72
12
Put x2=0 then x1= 6

17
 Chapter 11: Linear Programming using Graph
Now plot the
objective function
lines for Z = 48
and Z = 72. From
the plot of the two
objective function
lines it is obvious
that Z increases on
moving away from
the origin (0,0).

H: Locate the Most Attractive Corner: To find maximize Z, draw a line parallel to
the objective function lines that touches the last point in the feasible region while
moving away from the origin. This identifies the most attractive corner, which
gives us the amounts of wood and labor that is the maximum profit (maximize
Z). Thus, this represents the optimal solution to the problem.
I: Algebraically Determine the Optimal Solution: Calculate the coordinates of the
most attractive corner, it lies at the intersection of the wood and labor constraint
lines. Solve the simultaneous equations for (wood and labor) constraints to obtain
the coordinates of Intersection of lines (most attractive corner).
30x1 + 20x2 = 300 (wood) ––––– (I) and 5x1 + 10 x2 = 110 (labor) ––––– (II)
Multiply Eq. II by -2 and add in Eq. II:
(30x1 + 20x2) - 2(5x1 +10 x2) + = 300 - 2(110)
30x1 + 20x2 - 10x1 - 20x2 = -330 + 300  30x1 - 10x1 = 300 - 220
80
4
20x1 = 80  x1 = 20 Tables
Substituting in Eq. I for the value of x2
30(4) + 20x2 = 300  120 + 20x2 = 300  20x2 = 300 – 120
180
9
30x1 = 180  x1 = 30 Chair.
The coordinates of Intersection of wood and labor equations: (9,4)
Thus, the company’s optimal solution is to make four tables and nine chairs.
J: Calculate the value of Objective Function for the optimal solution.
Substitute the values of x1 Tables and x2 Chairs in the equation of Objective
function: Z = 6x1 + 8x2 = $6(4) + $8(9) = $96.
18
 Chapter 11: Linear Programming using Graph
Thus, the Maximum profit of $96 can be obtained by producing four tables and
nine chairs.
Answer: Maximum profit $96 by producing 4 tables and 9 chairs.

Example 2:
A Mine Company own two different mines that produce an ore which, after being
crushed, is graded into three classes: high, medium and low-grade. The company has
contracted to provide a smelting plant with 12 tons of high-grade, 8 tons of medium-
grade and 24 tons of low-grade ore per week. The company’s different operating
characteristics follow in chart:
Mine’s Cost per day
Production High Medium Low
Tons / day: Z
X 180 6 3 4
Y 160 1 1 6
Ore per 12 8 24
week
How many days per week should each mine be operated to fulfill the smelting plant
contract?

Solution:
Organize given information in a chart: The chart is given.
Formulate the LP Problem (Linear Programming Problem):
Find Feasible Solution:
- Solve for how many days per week. Work 1 day a week for ‘X’ and ‘Y’ does not
seem good, as it results in only 7 tonnes a week of high-grade, insufficient to meet
contract requirement for 12 tonnes, such solution is infeasible.
- Work 4 day a week on ‘X’ and 3 days a week on ‘Y’, seems better to meet contract,
such solution is feasible. However, it is quite expensive (costly).
What is actually needed it is to translate the problem into an equivalent mathematical
description in the order:
(1) Variables; (2) Constraints; (3) Implicit constraint; and (4) Objective. This process is
often called Formulate the problem (or more strictly formulating a mathematical
representation of the problem).
(1) Variables: represent the ‘Decisions’ have to be made or the ‘Unknowns’. Let ‘x’
be the number of days per week mine X is operated, and ‘y’ be the number of
days per week mine Y is operated.
This also means: x ≥ 0 ; y ≥ 0.

19
 Chapter 11: Linear Programming using Graph
(2) Constraints: is balance the amount produced with the quantity required under
the smelting plant contract Ore:
High: 6x + 1y ≥ 12; Medium: 3x + 1y ≥ 8 and Low: 4x + 6y ≥ 24.
Inequality implies that more of some grade of Ore is produced than needed. If
choice is given between Equality and Inequality than it better to choose
Inequality because it gives more flexibility in optimizing (Maximizing and
Minimizing) the objective (Deciding values) for the decision variables that
optimize the objective.
(3) Implicit constraint (Days per week Constraint): Cannot work more than a
certain maximum number of days a week. This type of constraint is called
Implicit constraint. Therefore: x ≤ 5; y ≤ 5
(4) Objective: To minimize cost and maximize profit.
Given by: Z = 180x + 160 y.
Write constraints [Inequalities]:
Write objective function: Minimize: Z = 180x + 160y
The complete LPP (Linear Programming Problem) is represented as:
Minimize: Z = 180x + 160 y
Subject to the constraints: 6x + y ≥ 12
3x + y ≥ 8
4x + 6y ≥ 24
x ≤ 5; y ≤ 5 or x , y ≥ 0
Graph all constraints to find feasible region; note that the last two constraints limit the
region to the first quadrant:
To draw the diagram above we turn all inequality constraints into equalities and draw the
corresponding lines on the graph. Determine the Optimal Solution to the LP by plotting
(180x + 160y) = K (K constant) for different K-values (ISO-profit lines). One such line
(180x + 160y = 180) is shown dotted on the diagram.
At least two points are required to draw a line. First simplify the equations:
6x + y ≥ 12 3x + y ≥ 8 2(2x + 3y) ≥ 2(12)
6x + y = 12 –––– (I) 3x + y = 8 –––– (II) 2x + 3y = 12 –––– (III)
For x = 0; in Eq. I: y = 12; For y = 0 in Eq. I: 6x=12, x=12/6 =2;
For x = 0; in Eq. II: y = 8; For y = 0 in Eq. II: 3x = 8 – 0, x = 8/3 =
2.6;
For x=0; in Eq. III: 3y=12, y=12/3=4; For y=0 in Eq. III: 2x=12, y=12/2=6;
Objective solution line: 180x + 160y = 180: for x=0, y=1.12 and for y=0, x=1
Draw the points: (0,12),(2,0); (0,8),(2.6,0); (0,4),(6,0); Dotted line: (1,1.12)

20
 Chapter 11: Linear Programming using Graph
The smallest value of K (for Minimization problem) goes through a point in the feasible
region is the value of the optimal solution to the LP (and the corresponding point gives
the optimal values of the variables), occurs at the intersection of the feasible region
formed by the lines II and III:
i.e., 3x + y = 8 and 4x + 6y = 24.
Reading the value of point of intersection from the graph will be Inaccurate, therefore
solve algebraically.
3x + y = 8 –––– (II) 2x + 3y = 12 –––– (III)
Multiply Eq. II by -3 and add I Eq. III: -3(3x + y) + (2x + 3y) = 3(8) + 12
⇒ ⇒
-9x - 3y + 2x + 3y = -24 + 12 -7x = -12 x = 12/7=1.71
Substitute in Eq. II: 3(1.71) + y = 8 ⇒ y = 8 - 3(1.71) = 8 - 5.14 = 2.87

Multiply Eq. II by -3 and add I Eq. III: -3(3x + y) + (2x + 3y) = 3(8) + 12
⇒ ⇒
-9x - 3y + 2x + 3y = -24 + 12 -7x = -12 x = 12/7=1.71
⇒
Substitute in Eq. II: 3(1.71) + y = 8 y = 8 - 3(1.71) = 8 - 5.14 = 2.87
Substituting the value of x=1.71 and y=2.867 in Objective function:
Z = 180x + 160y = 180(1.71) + 160(2.87) = 307.8 + 459.2 = 767
Hence the Optimal solution has Minimum cost ~767 at (1.71, 2.87)

21
 Chapter 11: Linear Programming using Graph
Answer: Minimum cost ~767 at (1.71, 2.87)

Example 3:
Solve the following Linear Programming Problem by ISO-profit method.
Maximize: P = 100x + 80y
Subject to the constraints: x + y ≤ 50,000
69.75x + 85.24y ≤ 4,000,000
23.8x + 10.85y ≤ 1,000,000
x≥0,y≥0

Solution:
Formulation of the Linear Program is given; next step is to draw the constraints. Convert
the inequalities to equal and draw the graph of the constraint lines. At least two point are
required to draw a line.
x+y=50,000––(I) 69.75x+85.24y=4,000,000––(II) 23.8x+10.85y=1,000,000–(III)
For x=0; in Eq. I: y=50,000; for y=0 in Eq. I; x=50,000;
For x=0; in Eq. II: x=4,000,000/85.24=46926.32~46926;
For y=0; in Eq. II: y=4,000,000/69.75=57347.67~57348;
For x=0; in Eq. III: y=1,000,000/10.85=92165.898~92166;
For y=0; in Eq. III: x=1,000,000/23.8=42016. 8;
Dividing by 1000 to normalizing the large number.
Draw the points: (0,50) , (50,0) ; (0, 46.92) , (57.34,0) ; (0,92.16),(42.01,0)

22
 Chapter 11: Linear Programming using Graph
The shaded region corresponds to all of the possible combinations that satisfy the
constraints, this region is feasible region. The ordered pairs in the shaded region are
feasible solutions for the linear programming problem LPP.
To find which combination lead to greatest profit, pick-out possible combination from the
graph and calculate the profit at each location on the graph or pick a value for the profit
and find all the ordered pairs on the graph that match that profit.
Starting with a profit of $3,000,000. Substitute this value into the objective function to
yield the equation: P = 100x + 80y = 3,000,000. The graph of this line is drawn on graph
as labeled P = 3,000,000. This is the line on which the profit is constant is called an ISO-
profit (same profit) line.
Other levels of profit are P = 4,000,000 and P = 5,000,000. With the increase of profit the
ISO-profit lines are farther and farther from the origin. Eventually it is outside the
feasible region. The ISO-profit line P = 5,000,000 is completely outside the shaded
region, means no combination will satisfy the inequalities and earn profit $5,000,000.
The ISO-profit line P = 4,706,564 will just satisfy feasible region. Points where the
borders for the constraints cross are called corner points of the feasible region. This
means that this profit level is the maximum profit and it occurs at the corner point
(35,328.2 and 14,671.8).
Answer: Maximum profit $4,706,564 at (35,328.2 and 14,671.8)

Exercise 11.2
11.2 Solve the LPP by ISO-profit or ISO-cost method
1. A health-conscious family wants to have 5 fruit servings per day of a healthy food
by taking banana and apples. Bananas cost Rs 30/- per dozen (6 servings) and
apples cost Rs. 80/- per kg (8 servings). One banana contains 8.8 mg of Vitamin C
and one serving of 100–125g Apples contains 5.2 mg of Vitamin C. Every family
member has at least 20 mg of Vitamin C daily but would like to keep the intake
under 60mg. How much fruit servings would the family have to consume on a daily
basis per member to minimize their cost?
2. 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 demand for X in the
current week is forecast to be 75 units and for Y is forecast to be 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.

23
 Chapter 11: Linear Programming using Graph
- Solve this linear program graphically using ISO profit method.
3. A company makes two products (X and Y) using two machines (A and B). Each
unit of ‘X’ requires 50 minutes processing time on machine ‘A’ and 30 minutes
processing time on machine ‘B’. Each unit of ‘Y’ 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 demand for ‘X’ in the current week is
forecast to be 75 units and for ‘Y’ is forecast to be 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.
4. Solve the following system of equations using Linear Programming technique.
Minimize: 4a + 5b + 6c
Subject to the constraints: a + b ≥ 11
a-b≤5
c-a-b=0
7a ≥ 35 - 12b
a≥0b≥0c≥0
5. Solve the following LPP graphically using ISO-profit method:
Maximize: Z = 100x + 100y
Subject to the constraints: 10x + 5y ≤ 80
6x + 6y ≤ 66
4x + 8y ≥ 24
5x + 6y ≤ 90
x≥0,y≥0

24