Unit 2: Linear Programming
Introduction
● Linear programming uses a mathematical model to describe the problem
of concern.
● The adjective linear means that all the mathematical functions in this
model are required to be linear functions.
● The word programming does not refer to computer programming; rather,
it is essentially a synonym for planning.
● Thus, linear programming involves the planning of activities to obtain an
optimal result, i.e., a result that reaches the specified goal best (according
to the mathematical model) among all feasible alternatives.
Standard form
Standard form
● The function being maximized, c1x1+ c2x2+ · · ·+ cnxn, is called the
objective function.
● The restrictions normally are referred to as constraints.
● The first m constraints (those with a function of all the variables
ai1x1+ai2x2 +· · · +ainxn on the left-hand side) are sometimes called
functional constraints (or structural constraints).
● The xj≥0 restrictions are called nonnegativity constraints (or
nonnegativity conditions).
Terminology for solution
● Any specification of values for the decision variables (x1, x2, . . . , xn) is called
a solution, regardless of whether it is a desirable or even an allowable choice.
● A feasible solution is a solution for which all the constraints are satisfied.
● An infeasible solution is a solution for which at least one constraint is violated.
● The feasible region is the collection of all feasible solutions.
● It is possible for a problem to have no feasible solutions.
● An optimal solution is a feasible solution that has the most favorable value of
the objective function.
● The most favorable value is the largest value if the objective function is to be
maximized, whereas it is the smallest value if the objective function is to be
minimized.
Example
The WYNDOR GLASS CO. produces high-quality glass products, including windows and glass doors. It
has three plants. Because of declining earnings, top management has decided to revamp the company’s
product line. Unprofitable products are being discontinued, releasing production capacity to launch two
new products having large sales potential:
Product 1: An 8-foot glass door with aluminum framing
Product 2: A 4 x 6 foot double-hung wood-framed window
Product 1 requires some of the production capacity in Plants 1 and 3, but none in Plant 2. Product 2 needs
only Plants 2 and 3.
The marketing division has concluded that the company could sell as much of either product as could be
produced by these plants. However, because both products would be competing for the same production
capacity in Plant 3, it is not clear which mix of the two products would be most profitable.
Therefore, an OR team has been formed to study this question.
Example
Example
Example
Example
Graphical Method
● form a single line with a ruler to establish the slope.
● Then move the ruler with fixed slope through the feasible region in the
direction of improving Z.
● When the objective is to minimize Z, move the ruler in the direction that
decreases Z.
● Stop moving the ruler at the last instant that it still passes through a point in
this region.
● This point is the desired optimal solution.
Graphical Solution of LPP
● Unique Solution
● Infinite Solution/ Alternate Solution
● Unbounded Solution
● Bounded Solution
● Infeasible Solution
Infinite Solution
Unbounded Solution/Unbounded Region
Unbounded Region/ Bounded Solution
Infeasible Solution
Problem
Minimise Z : -50 x + 20 y
Const.:
2x-y ≥ -5
3x+3 ≥ 3
2x-y ≤ 12
X,y ≥ 0
Graphical Method
Vertices of the Boundary are of interest in feasible region
Algebraic Method
Maximise Z : 6x1+5x2
Const.:
x1+x2 ≤ 5
3x1+2x2 ≤ 12
x1, x2 ≥ 0
Algebraic Method
● Convert inequalities into equations by adding slack/surplus variable.
● Slack/Surplus variables do not add to objective function.
● Let there be total n variables including decision and slack/surplus variables
and m equations.
● Fix any m variables to some arbitrary value and solve for remaining n-m
variables. There are nCm ways.
● Easy way is to fix these variable to value of 0 called non-basic variables.
● The variables that we solve are called basic variables.
● The solution obtained by fixing non basic variables to 0 are called basic
solutions.
● Estimate the value of the objective function based on these values.
Simplex Method
