Linier Programming (I)

Week 1
 Linier Inequalities in Two Variables (1)
• Definition:
 An equality that can be written in one of the
forms
ax + by + c < 0; ax + by + c ≤ 0; ax + by + c > 0;
ax + by + c≥
• Examples: Solve the inequality
1. y ≤ 5
2. 2(2x - y) < 2(x + y)- 4
2 x  y  3
3.  x  y
2 y  1  0

 Linier Inequalities in Two Variables (2)
• Solutions
 Linear Programming (1)
• 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
• 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 (2)
• 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 (3)
• The aim is to find one solution that is an
optimal solution that gives the maximum or
minimum value of the objective function.
• It can be solved by 2 method :
1. Geometric method
2. Simplex method
 Linear Programming (4)
•Example of a geometric method
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. 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?
 Linear Programming (5)
• 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
4 x0
4 y0
 Linear Programming (6)
• 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
4 2x + y  180
• Similarly, the restrictions for machines B and C give
4 x + 2y  160
4 x + y  100
• The profit function of x and y is
4 P = 4x + 6y
 Linear Programming (7)
• 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)
 Linear Programming (8)
• Constraints (2) and (3) are called nonnegative
conditions
• The region simultaneously satisfying constraints
(2) - (6) is unshaded area in figure on the
whiteboard and it is called the feasible region
• Each point in this region represents a feasible
solution
 Linear Programming (9)
• The objective function P = 4x + 6y, is equivalent to
2 P
y  x
3 6
• It defines a family 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)
 Linear Programming (10)
• Solutions
The corner points are
4 A = (40,60)
4 B = (80,20)
4 C = (90,0)
4 D = (0,0)
4 E = (0,80)
 Linear Programming (11)
• The objective function P = 4x + 6y at each point
4 P(A) = 4(40) + 6(60) = 520
4 P(B) = 4(80) + 6(20) = 440
4 P(C) = 4(90) + 6(0) = 360
4 P(D) = 4(0) + 6(0) = 0
4 P(E) = 4(0) + 6(80) = 480
• P has a maximum value of 520 at A, where x =
40 and y = 60
 Multiple Optimum Solution (1)
• Definition: It is a case when an objective
function attains its optimum value at more
than one feasible point
• Example:
Maximize Z = 2x + 4y subject to the constraints
x – 4y ≤ - 8
x + 2y ≤ 16
x, y ≥ 0
 Multiple Optimum Solution (2)
• Solution
If (x1, y1) and (x2,y2) are
two corner points, the
function will also be
optimum at all points (x,
y) where
x = (1 – t)x1 + tx2
y = (1- t)y1 + ty2

B = (8,4) ; C = (0,8)
x = (1 –t)8 + t.0 = 8 (1 –t)
y = (1 –t) 4 + t.8 = 4 (1- t)
 The Simplex Method (1)
• 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.
 The Simplex Method (2)
• 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.
 The Simplex Method (3)
• Standard Linear Programming Problems
Maximize:
Z = c1X1 + c2X2 + … +cnXn
Subject to the constraints:
a11X1 + a11X1 + … + a1nXn  b1
a11X1 + a11X1 + … + a1nXn  b1
. . . .
. . . .
. . . .

am1X1 + am1X1 + … + amnXn  bm

Where X1, X2, X3 and b1,b2,b3 are nonnegative
 The Simplex Method (4)
Examples
• 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
 The Simplex Method (5)
• 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
 The Simplex Method (6)
• 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
 The Simplex Method (7)
• 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
 The Simplex Method (8)
• Initial Simplex Tableau
B X1 X2 S1 S2 Z R
S1  2 1 1 0 0 8

S2  2 3 0 1 0 12
Z  3  1 0 0 1 0 
• The first two rows correspond to the
constraints, and the last row, called the
objective row, correspond to the objective
equation.
 The Simplex Method (9)
• 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 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
 The Simplex Method (10)
• Departing variable 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
 The Simplex Method (11)
Solution
B X1 X2 S1 S2 Z R 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 )

The Simplex Method (12)
 Degeneracy, Unbounded Solutions, and
Multiple Solutions (1)
A. Degeneracy
Definition: A basic feasible solution is
degenerate if along with the nonbasic
variables, one of the basic variables is 0.
Examples:
B X1 X2 X3 X4 Z R Quotients
departing  X 1 1 0 a13 a14 0 0  0  a13
var iable X2 0 1 a23 a24 0 a 

Z 0 0 d1 d2 1 d 3 

       
indicator
 Degeneracy, Unbounded Solutions, and
Multiple Solutions (2)
B. Unbounded Solutions
Definition: A case when there is no optimum
solution because of no quotients exists.
Example:
B X1 X2 X3 X4 Z R Quotients
departing  X 1 1  3 0 2 0 5  no quotien
var iable X 2 0 0 1 4 0 1  no quotien
Z 0  5 0 2 1 10

       
indicator
 Degeneracy, Unbounded Solutions, and
Multiple Solutions (3)
C. Multiple Solutions
Definition: A case of linier programming when there are multiple
(more than one) optimum solutions to the problem
Example:
Maximize Z = -x1 + 4x2 + 6x3 subject to
x1 + 2x2 + 3x3 ≤ 6
-2x1 – 5x2 + x3 ≤ 10
x1, x2, x3 ≥ 0
 Degeneracy, Unbounded Solutions, and
Multiple Solutions (4)
• Solution
B X1 X2 X3 s1 s2 Z R Quotients
departing  s1  1 2 3 1 0 0 6  6:3  2
var iable s2  2  5 1 0 1 010 10 : 1  1
Z  1  4 6 0 0 1 0 

       
indicator

B X1 X2 X3 s1 s2 Z R Quotients
departing  x3  1 / 3 2/3 1 1/ 3 0 0 2  2:2/3  3
var iable s2  7 / 3  17 / 3 0 1/ 3 1 0 8  no quotient
Z  3 0 0 2 0 1 12

       
indicator
 Degeneracy, Unbounded Solutions, and
Multiple Solutions (5)
B X1 X2 X3 s1 s2 Z R
departing  x2 1 / 2 1 3/ 2 1/ 2 0 0 3
var iable s2 1 / 2 0 17 / 2 5/ 2 1 0 25
Z  3 0 0 2 0 1 12 

       
indicator

x1= (1- t). 0 + t.0 = 0

x2 = (1-t) . 0 + t. 3 = 3t
x3 = (1- t ). 2 + t.0 = 2(1 – t)