Introduction to Operations Research
Linear Programming
(GRAPHICAL SOLUTION METHODS )
Dr. Kulmani Mehar
School of Mechanical Engineering
Course Title: Introduction to Operations Research
Course Code: MIE 4313
Linear programming
Linear programming is a widely used mathematical modelling technique developed to
help decision-makers in planning and decision-making regarding optimal use of scarce
resources.
Before discussing the basic concepts and applications of linear programming, it is
important to Understand the meaning of the words – linear and programming. The
word linear refers to the linear relationship among variables in a model. That is, a
given change in one variable causes a proportional change in another variable. For
example, doubling the investment on a certain project will also double the rate of
return. The word programming refers to the mathematical modelling and solving of a
problem that involves the use of limited resources, by choosing a particular course of
action (or strategy) among the given courses of action (or strategies) in order to
achieve the desired objective.
STRUCTURE OF LINEAR PROGRAMMING MODEL
The general structure of an LP model consists of following three basic
components (or parts).
• Decision variables (activities)
• The objective function
• The constraints
GRAPHICAL SOLUTION METHODS OF LP PROBLEM
Two graphical solution methods (or approaches):
(i) Extreme point solution method
(ii) Iso-profit (cost) function line method
Extreme Point Solution Method
1. Examples of Maximization LP Problem
The maximum value of the objective function Z = 10
occurs at the extreme point (4, 2). Hence, the optimal
solution to the given LP problem is: x1 = 4, x2 = 2 and Max
Z = 10.
Since resource value (RHS) of the first constraint is
negative, multiplying both sides of this constraint by –1,
the constraint becomes: -x1 + x2 >=1.
The maximum value of objective function Z = 4 occurs at
extreme points B and C. This implies that every point
between B and C on the line BC also gives the same
value of Z. Hence, problem has multiple optimal solutions:
x1 = 0, x2 = 2 and x1 = 2, x2 = 3 and Max Z = 4.
Example 3.4 The ABC Company has been a producer of picture tubes for television sets
and certain printed circuits for radios. The company has just expanded into full scale
production and marketing of AM and AM-FM radios. It has built a new plant that can
operate 48 hours per week. Production of an AM radio in the new plant will require 2 hours
and production of an AM-FM radio will require 3 hours. Each AM radio will contribute Rs
40 to profits while an AM-FM radio will contribute Rs 80 to profits. The marketing
department, after extensive research has determined that a maximum of 15AM radios and
10 AM-FM radios can be sold each week.
(a) Formulate a linear programming model to determine the optimum production mix of
AM and FM radios that will maximize profits.
(b) Solve this problem using the graphical method.
Since the maximum value of the objective function Z =
1,160 occurs at the extreme point (9, 10), the optimum
solution to the given LP problem is: x1 = 9, x2 = 10 and
Max. Z = Rs 1,160.
Extreme Point Solution Method
2. Examples of Minimization LP Problem
The minimum (optimal) value of the objective
function Z = 13 occurs at the extreme point C (1,
5). Hence, the optimal solution to the given LP
problem is: x1 = 1, x2 = 5, and Min Z = 13.
Extreme Point Solution Method
3. Examples on Mixed Constraints LP Problems
A firm plans to purchase at least 200 quintals of scrap containing high-quality metal X and
3.10
low-quality metal Y. It decides that the scrap to be purchased must contain at least 100
quintals of metal X and not more than 35 quintals of metal Y. The firm can purchase the
scrap from two suppliers (A and B) in unlimited quantities. The percentage of X and Y
metals in terms of weight in the scrap supplied by A and B is given below.
Metals Supplier A Supplier B
X 25% 75%
Y 10% 20%
The price of A’s scrap is Rs 200 per quintal and that of B is Rs 400 per quintal. The firm
wants to determine the quantities that it should buy from the two suppliers so that the total
cost is minimized.
The maximum (optimal) value of the objective function, Z
= 22 occurs at the extreme point B (5/2, 3/2).
Hence, the optimal solution to the given LP problem is: x1
= 5/2, x2 = 3/2 and Max Z = 22.
Iso-profit (Cost) Function Line Method
SPECIAL CASES IN LINEAR PROGRAMMING
Alternative (or Multiple) Optimal Solutions
SPECIAL CASES IN LINEAR PROGRAMMING
Unbounded Solution
SPECIAL CASES IN LINEAR PROGRAMMING
Infeasible Solution