Management Science Lesson Seven and Eight

Lesson seven and eight: Graphical Analysis of Linear Programming
(maximization and minimization problems)
This section shows how a two-variable linear programming problem is solved graphically, which
is illustrated as follows:
A. Maximisation
Example 1.5:
Consider the product mix problem discussed in section 1.3
Maximize 30X1 + 40X2
Subject to: 3X1 + 2X2 ≤ 600
3X1 + 5X2 ≤ 800
5X1 + 6X2 ≤ 1100
X1≥ 0, X2 ≥ 0
From the first constraints 3X1 + 2X2 ≤ 600, draw the line 3X1 + 2X2 = 600 which passes through
the point (200, 0) and (0, 300). This is shown in the following graph as line 1.
Graph 1: Three closed half planes and Feasible Region
Half Plane - A linear inequality in two variables is called as a half plane.
Boundary - The corresponding equality (line) is called as the boundary of the half plane.
Close Half Plane – Half plane with its boundary is called as a closed half plane.
In this case we must decide in which side of the line 3X1 + 2X2 = 600 the half plane is located.
The easiest way to solve the inequality for X2 is
3X1 ≤ 600 – 2X2
And for the fixed X1, the coordinates satisfy this inequality are smaller than the corresponding
ordinate on the line and thus the inequality is satisfied for all the points below the line 1.
Similarly, we have to determine the closed half planes for the inequalities 3X1 + 5X2 ≤ 800 and
5X1 + 6X2 ≤ 1100 (line 2 and line 3 in the graph). Since all the three constraints must be satisfied
simultaneously we have consider the intersection of these three closed half planes. The complete
intersection of these three closed half planes is shown in the above graph as ABCD. The region
ABCD is called the feasible region, which is shaded in the graph.
Feasible Solution: Any non-negative value of X1, X2 that is X1 ≥ 0 and X2 ≥ 0 is known as

feasible solution of the linear programming problem if it satisfies all the existing constraints.
Feasible Region: The collection of all the feasible solution is called as the feasible region.
B. Minimisation
Example 1.6:
In the previous example we discussed about the less than or equal to type of linear programming
problem, i.e. maximization problem. Now consider a minimization (i.e. greater than or equal to
type) linear programming problem formulated in Example 1.4.
Minimize 2000X1 + 1500X2
Subject to: 6X1 + 2X2 ≥ 8
2X1 + 4X2 ≥ 12
4X1 + 12X2 ≥ 24
X1 ≥ 0, X2 ≥ 0
The three lines 6X1 + 2X2 = 8, 2X1 + 4X2 = 12, and 4X1 + 12X2 = 24 passes through the point
(1.3,0) (0,4), (6,0) (0,3) and (6,0) (0,2). The feasible region for this problem is shown in the
following Graph 2. In this problem the constraints are of greater than or equal to type of feasible
region, which is bounded on one side only.
Graph 2: Feasible Region
Exercise 1:
A company purchasing scrap material has two types of scarp materials available. The first type
has 30% of material X, 20% of material Y and 50% of material Z by weight. The second type
has 40% of material X, 10% of material Y and 30% of material Z. The costs of the two scraps are
120FCFA and 160FCFA per kg respectively. The company requires at least 240 kg of material
X, 100 kg of material Y and 290 kg of material Z. Find the optimum quantities of the two scraps
to be purchased so that the company requirements of the three materials are satisfied at a
minimum cost.
Exercise 2:
Solve the following Linear Programming Problem
Maximize 3X1 + X2
Subject to: X1 + X2 ≥ 6
-X1 + X2 ≤ 6
-X1 + 2X2 ≥ -6
and X1, X2 ≥ 0
Exercise 3:
Minimize 200X1 + 300X2
Subject to: 0.4X1 + 0.6X2 ≥ 240
0.2X1 + 0.2X2 ≤ 80
0.4X1 + 0.3X2 ≥ 180
X1, X2 ≥ 0
Exercise 4:
Consider the linear programming problem
Max Z = 44𝑥 + 16𝑥
Subject to 7𝑥 + 6𝑥 ≤ 84 (1)
4𝑥 + 2𝑥 ≤ 32 (2)
𝑥, 𝑥 ≥ 0
Exercise 5
Maximize 1170X1 + 1110X2
Subject to: 9X1 + 5X2 ≥ 500
7X1 + 9X2 ≥ 300
5X1 + 3X2 ≤ 1500
7X1 + 9X2 ≤ 1900
2X1 + 4X2 ≤ 1000
C X1, X2 ≥ 0
Find graphically the feasible region and the optimal solution.
Summary
Objective Function: is a linear function of the decision variables representing the objective of
the manager/decision maker.
Constraints: are the linear equations or inequalities arising out of practical limitations.
Decision Variables: are some physical quantities whose values indicate the solution.
Feasible Solution: is a solution which satisfies all the constraints (including the non-negative)
presents in the problem.
Feasible Region: is the collection of feasible solutions.
Multiple Solutions: are solutions each of which maximize or minimize the objective function.
Unbounded Solution: is a solution whose objective function is infinite.
Infeasible Solution: means no feasible solution.

Management Science Lesson Seven and Eight

Uploaded by

Copyright:

Available Formats

Management Science Lesson Seven and Eight

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Management Science Lesson Seven and Eight

Uploaded by

Copyright:

Available Formats

Lesson seven and eight: Graphical Analysis of Linear Programming

(maximization and minimization problems)

Consider the product mix problem discussed in section 1.3

Maximize 30X1 + 40X2

Subject to: 3X1 + 2X2 ≤ 600

3X1 + 5X2 ≤ 800

5X1 + 6X2 ≤ 1100

Half Plane - A linear inequality in two variables is called as a half plane.

3X1 ≤ 600 – 2X2

Feasible Solution: Any non-negative value of X1, X2 that is X1 ≥ 0 and X2 ≥ 0 is known as

Minimize 2000X1 + 1500X2

Subject to: 6X1 + 2X2 ≥ 8

Solve the following Linear Programming Problem

Minimize 200X1 + 300X2

Subject to: 0.4X1 + 0.6X2 ≥ 240

0.4X1 + 0.3X2 ≥ 180

Consider the linear programming problem

Max Z = 44𝑥 + 16𝑥

Maximize 1170X1 + 1110X2

Subject to: 9X1 + 5X2 ≥ 500

7X1 + 9X2 ≥ 300

5X1 + 3X2 ≤ 1500

7X1 + 9X2 ≤ 1900

2X1 + 4X2 ≤ 1000

Find graphically the feasible region and the optimal solution.

Feasible Region: is the collection of feasible solutions.

Unbounded Solution: is a solution whose objective function is infinite.

Infeasible Solution: means no feasible solution.

You might also like