Linear Programming

A Geometrical Approach
&
A Matrix Approach
 Linear Programming (LP)
• LP was developed by George B. Danzig in the
late 1940s and was first used by US Air Force
as an aid decision making
• To maximize or minimize a function, subject
to certain restrictions (or constraint)
– A manufacturer may want to maximize a profit
function, subject to production restrictions imposed
by limitations on the use of machinery and labor
 Linear Programming (LP)…...
• The function to be maximize or minimized is
linear. A linear function in x and y has the form
Z = ax + by, where a and b are constants.
• The corresponding constraints be represented
be represented by a system of linear
inequalities (involving  or ) or linear
equation in x and y, and that all variables be
non negative.
 Linear Programming (LP)…...
• A problem involving all these conditions is
called a linear programming problem.
• The function to maximize and minimize is
called the objective function.
• There are usually infinitely many solutions
to the system of constraints. These are
called feasible solutions or feasible points.
 Linear Programming (LP)…...
• The aim is to find one solution that is an
optimal solution that gives the maximum or
minimum value of the objective function.
 A Geometrical Approach to LP
• A company produces two types of widgets;
manual and electric. Each required in its
manufacture the use of three machines; A ,
B, and C. Each manual widget requires the
use of machine A for 2 hours, machine B
for 1 hour, and machine C for 1 hour.
Whereas, the electric widget requires the
use of machine A, B, and C for 1 hour, 2
hours, and 1 hour, respectively.
 A Geometrical Approach…...
Suppose the maximum numbers of hours
available per month for the use of machine
A, B, and C are 180, 160, and 100,
respectively. The profit of manual widget is
$4, and on an electric widget it is $6. If the
company can sell all the widgets it can
produce, how many of each type should it
make in order to maximize the monthly
profit?
 A Geometrical Approach…...
• To solve the problem, let x and y denote the
number of manual and electric widgets,
respectively, that are made in a month.
• Since the number of widgets made is not
negative
 x0
 y0
 A Geometrical Approach…...
• For machine A, the time needed for working on x
manual widgets is 2x hours, and the time needed for
working on y electric widget is 1y hour. The sum of
these times cannot grater than 180, so
 2x + y  180
• Similarly, the restrictions for machines B and C give
 x + 2y  160
 x + y  100
• The profit function of x and y is
 P = 4x + 6y
 A Geometrical Approach…...
• Summarizing
– The objective function
• P = 4x + 6y (1)
– Subject to the condition that x and y must be a solution
of the system of constraints
• x0 (2)
• y0 (3)
• 2x + y  180 (4)
• x + 2y  160 (5)
• x + y  100 (6)
 A Geometrical Approach…...
• Constraints (2) and (3) are called nonnegative
conditions
• The region simultaneously satisfying constraints
(2) - (6) is shaded area in figure on the
whiteboard and it is called the feasible region
• Each point in this region represents a feasible
solution
 A Geometrical Approach…...
• The objective function P = 4x + 6y, is equivalent to
2 P
y  x
• It defines3 a family
6 of parallel lines, each having
slope of -2/3 and y intercept (0,P/6)
• This line is called isoprofit line
• This figure is called a bounded feasible region (a
feasible region is within a circle) and nonempty (a
feasible region contains at least one point)
 A Geometrical Approach…...
• The corner points are
 A = (40,60)
 B = (80,20)
 C = (90,0)
 D = (0,0)
 E = (0,80)
 A Geometrical Approach…...
• The objective function P = 4x + 6y at each point
 P(A) = 4(40) + 6(60) = 520
 P(B) = 4(80) + 6(20) = 440
 P(C) = 4(90) + 6(0) = 360
 P(D) = 4(0) + 6(0) = 0
 P(E) = 4(0) + 6(80) = 480
• P has a maximum value of 520 at A, where x = 40
and y = 60
 Exercise
• A producer grower is purchasing fertilizer
containing three nutrients, A, B and C. The
minimum needs are 160 units of A, 200
units of B and 80 units of C. There are two
popular brands of fertilizer on the market.
Fast Grow, costing $8 a bag, contains 3
units of A, 5 units of B, and 1 unit of C.
 Exercise…...
• Easy grow, costing $6 a bag, contains 2
units of each nutrient. If the grower wishes
to minimize cost while still maintaining the
nutrients required, how many bags of each
brand should be bought?
 A Matrix Approach to LP
• Solving linear programming by a geometric
approach is not practical when the number
of variables increases to three, and is not
possible beyond that.
• Now, we shall look at a different technique
the Simplex Method.
 A Matrix Approach to …...
• The simplex method begins with a feasible
solution and tests whether it is optimum
(the new solution brings closer to
optimization of the objective function).
• This new solution not be optimum, we
repeat the procedure, eventually, the
simplex method leads to an optimum
solution, if one exists.
 A Matrix Approach to …...
• Standard Linear Programming Problems
Maximize:
Z = c1X1 + c2X2 + … +cnXn
Subject to the constraints:
a11X1 + a11X1 + … + a1nXn  b1
a21X1 + a22X1 + … + a2nXn  b2
. . . .
. . . .
. . . .

am1X1 + am1X1 + … + amnXn  bm

Where X1, X2, X3 and b1,b2,b3 are nonnegative
 A Matrix Approach to …...
• Maximize
Z = 3X1 + X2 (1)
• Subject to the constraints
2X1 + X2  8 (2)
2X1 + 3X2  12 (3)
• Inequality (2) & (3) can be written as equations
by using the slack variable (S)
2X1 + X2 + S1 = 8
2X1 + 3X2 + S2 = 12
where, S1  0; S2  0
 A Matrix Approach to …...
• The variables X1 and X2 are called structural
variables
• Restate the problem in terms of equations:
Maximize: Z = 3X1 + X2 (4)
Such that
2X1 + X2 + S1 = 8 (5)
2X1 + 3X2 + S2 = 12 (6)
where, X1  0; X2  0; S1  0; S2  0
• At least two of the variables X1; X2; S1; and S2
are 0
 A Matrix Approach to …...
• Any solution where at least two of the
variables X1; X2; S1; and S2 are 0 is called a
basic feasible solution (BFS)
• The number, 2, is determined by the
expression n - m, where m is the number of
constraint (excluding the non-negativity
conditions) and n is the number of variables
that occur after these constraints are
converted to equations
• In our case, n = 4 and m = 2
 A Matrix Approach to …...
• The two variables held at zero value are
called non-basic variable, whereas the
others are called basic variable.
• Rewrite: equations (5); (6); and (4)
2X1 + X2 + S1 =8
2X1 + 3X2 + S2 = 12
-3X1 - X2 +Z =0
 A Matrix Approach to …...
• Initial Simplex Tableau
X
1 X
2 S
1 S
2 Zb

S
1 2 1 1 0 08
S 2 3 0 1 012

2 
Z3
1 0 0 10

• The first two rows correspond to the
constraints, and the last row, called the
objective row, correspond to the objective
equation.
 A Matrix Approach to …...
• In the initial BFS: X1 = 0; X2 = 0; S1 = 8; and
S2 = 12 at which Z = 0, X1 and X2 are non-
basic variable
• The numbers in the brace are indicators
• Entering variable (incoming activities) can
be found by looking at the most negative of the
number enclosed by the brace in the Z-row (By
most negative, means the negative indicator
having greatest magnitude).  pivot column
 A Matrix Approach to …...
• Departing variable (outgoing activities)
can be found by looking the smallest
quotient (must be positive value). The
quotients are obtained by dividing each
entry in the first two rows of the b-column
by entry in the corresponding row of the
entering variable column. The departing
variable is in the same row as the smallest
quotient.  pivot row
 X1 X2 S1 S2 Z b Quotients
departing  S1  2 1 1 0 0 8  8  2  4 ( smaller )
var iable S 2  2 3 0 1 0 12 12  2  6
Z  3  1 0 0 1 0 

       
indicator

entering var iable (most negative indicator )

 Exercise 1
• Maximize
Z = 5X1 + 4X2
• Subject to the constraints
X1 + X2  20
2X1 + X2  35
-3X1 + X2  12
X1  0; X2  0
 Exercise 2
• Maximize
W = 2X1 + X2 - 2X3
• Subject to the constraints
-2X1 + X2 + X3  -2
X1 - X2 + X3  4
X1 + X2 + 2X3  6
X1  0; X2  0; X3  0