Introduction To Linear Programming: EE 477 Optimization Techniques Fall 2017 Handout #4 Outline of The Handout

EE 477 Optimization Techniques Outline of the Handout
1. Introduction to Linear Programming
Fall 2017 2. Mathematical Background
3. Convex and Concave Functions

Handout #4 4. Convex Sets
5. Convexity and Linear Programming

Introduction to Linear Programming 6. Plotting the Constraints of a Linear Program
7. Common Terminology for LP Models

and the Graphical Method
8. Steps for Solving LP Problems using the Graphical Method
Prof. Mohamed Zribi 9. Examples of Solving LP Problems Using the Graphical Method
Updated 26 September 2017 10. Special Cases of LP solutions EE 477 Dr. Mohamed Zribi
1 2
Introduction
Mathematical programming is used to find the best or optimal
solution to a problem that requires a decision or set of
decisions about how best to use a set of limited resources to
1. Introduction to Linear achieve a state goal of objectives.
Steps involved in mathematical programming
Programming – Conversion of stated problem into a mathematical model

that abstracts all the essential elements of the problem.
– Exploration of different solutions of the problem.
– Finding out the most suitable or optimum solution.

EE 477 Dr. Mohamed Zribi
3 4
Linear Programming
Model Components and Formulation
Decision variables: mathematical symbols representing levels The linear programming problem is one of the simplest and most
of activity of a firm. widely used optimization problems.
Objective function: a linear mathematical relationship

describing an objective of the firm, in terms of decision The objective of linear programming (LP) is the minimization or
variables, that is maximized or minimized maximization of a linear function subject to some linear
Constraints: restrictions placed on the firm by the operating constraints.
environment stated in linear relationships of the decision

variables. A linear programming problem is a mathematical problem in
which the objective function is linear in the unknowns and the
Parameters: numerical coefficients and constants used in the
objective function and constraint equations. constraints consist of linear equalities and linear inequalities.
5 6
LP Applications Model of a Linear Program

– Long Range Production Planning
A linear programming (LP) problem is an optimization problem
– Production Process Selection for which we do the following:
– Financial/Investment Planning
– Marketing System Design – Attempt to maximize (or minimize) a linear function (called
– Plant Inventory Management
– Plant and Warehouse location Selection the objective function) of the decision variables.
– Job Routing Determination
– Distribution and Transportation System Design – The values of the decision variables must satisfy a set of
– Capacity Requirement Planning
– Shop Worker-Machine Assignment Problem constraints. Each constraint must be a linear equation or
– Job Shop Scheduling Problem
– Shop Layout Design inequality.
– etc
– A sign restriction is associated with each variable. For any
LP model has been used in almost all fields of engineering, business and
management. variable xi, the sign restriction specifies either that xi must be
EE 477 Dr. Mohamed Zribi nonnegative (xi ≥ 0) or that xi may be unrestricted in sign.
7 EE 477 Dr. Mohamed Zribi 8
Assumptions of Linear Programming Assumptions of Linear Programming
Proportionality and Additive Assumptions Divisibility Assumption

The divisibility assumption requires that each decision
The objective function for an LP must be a linear function of
variable be permitted to assume fractional values.
the decision variables has two implications:
1. The contribution of the objective function from each decision

The Certainty Assumption
variable is proportional to the value of the decision
The certainty assumption is that each parameter (objective
variable.
function coefficients, right-hand side, and technological
2. The contribution to the objective function for any variable is
coefficients) are known with certainty.
independent of the other decision variables.
EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi
9 10
Linear Programs Example 1: LP Examples
Objective function
• Linear equations (equalities)
• Linear inequalities
• Linear equations and linear inequalities are

referred to as linear constraints EE 477 Dr. Mohamed Zribi 11
12
Linear Programming Problems Linear Programming
1. LP formulations are very common in modern Linear programming methods make it possible to
industry choose the best solution from many possible solutions.
2. Nice connection between Algebra and Geometry
3. Geometry (Graphical Solution) is not useful for An important factor in the widespread use of the LP
more than 3 variables techniques is the availability of very efficient computer
4. Practical problems: 1000’s of variables software packages for solving LP problems.
5. Need Algebraic method !

13 14
Linear Programming Possible Outcomes of LP Problems
None of the variables are multiplied by another variable,

Unique optimal solution
raised to a power, or used in a nonlinear function
Many optimal solutions
No optimal solutions
Because the objective function and constraints are linear,
– Infeasible problems
they are convex. Thus, if an optimal solution to an LP
– Unbounded problems
problem is found, it is the global optimum

15 16
Formulation of LP Problems Formulation of LP Problems
A basic linear programming (LP) problem consists of two The constraints can be represented generally as
major parts:
ai1 x1 ai 2 x2 ain xn bi
– The objective function
where
– A set of constraints
aij= amount of the i-th resource that is consumed for each
For maximization problem, the objective function is unit of the j-th activity
generally expressed as
bi = amount of the i-th resource that is available
Maximize z c1x 1 c 2 x 2 cn x n
The general second type of constraints specifies that all
cj= payoff of each unit of the j-th activity that is undertaken activities must have a positive value. i.e,
xj= magnitude of the j-th activity xi 0
z = total payoff due to the total number of activities
17 18
Remark: Remark:
In solving an LP, the constraints (except the non-negativity of the
variables), are transformed into equalities. Since Max f(x) = Min (-f(x)), then any maximization
An inequality of the form
problem may be replaced by a minimization problem by
ai1 x1 ai 2 x2 ... ai n xn bi
is replaced by changing "Max f(x)“ to "Min –f(x)".
ai1 x1 ai 2 x2 ... ai n xn si bi , si 0.
The new variable si is called a slack variable.
An inequality of the form Similarly, a minimization problem may be replaced by a
ai1 x1 ai 2 x2 ... ai n xn bi
is replaced by maximization problem by changing "Min f(x)" to
ai1 x1 ai 2 x2 ... ai n xn si bi , si 0
"Max –f(x)".
The new variable si is called a surplus variable.
19 20
Standard Form of an LP Problem
Any linear program can be transformed into the following Standard Form of an LP Problem
standard form. Using compact vector notation, the standard problem
max (or min ) z c1 x1 c2 x2 cn xn
s.t. becomes Max (or Min) z cT x c0
a11 x1 a12 x2 a1n xn b1
a21 x1 a22 x2 a2 n xn b2
subject to:
am1 x1 am 2 x2 amn xn bm
x1 0, x2 0, , xn 0
Ax b and x 0 ( A is m n; x Rn )
b1 0, b2 0, , bm 0
where x is an n-dimensional column vector,
where the bi 's, ci 's and aij 's are fixed real constants, and
c is an n-dimensional column vector, A is an m by n
the xi 's are real numbers to be determined.
matrix and b is an m-dimensional column vector.
21 22
Assumptions of the LP General Solution of LP Problems

1. The system Ax = b has a solution. (The case where there is General solution(s) of LP problems can be obtained using the
no solution is of no interest).
Simplex method.
2. The system Ax = b is non-redundant, i.e., no row of [A:b] is
a linear combination of the others; hence, the row vectors of Simplex method:
[A:b] are linearly independent. This is equivalent to the – An iterative algebraic procedure
condition that rank([A:b]) = m. Hence, rank(A) = m. This
implies that m < n since the rank of a matrix cannot exceed – Graphic analysis gives insight into the logic
the number of columns. – The initial feasible solution starts at a corner point
3. The system Ax = b has more than one solution. This implies:
– Subsequent iterations result in improved intermediate
• m < n. For, if m = n, then A is an n x n matrix and, by
assumption rank(A) = n, i.e, A is nonsingular which solutions
would imply that the equation Ax = b has a unique – In general, a corner point has no more than m variables
solution. greater than 0, where m is the number of constraints
• The system Ax = b has an infinite number of solutions.
For, if x and y are two distinct solutions, then ax + (1 - a)y – When no further improvement is possible, the optimal
is also a solution for all a such that 0 < a < 1. solution has been found and the algorithm stops
23 24
Optimal Solution of an LP Definitions: Type of feasible points
Interior point: satisfies all constraint but non with
For a maximization problem, an optimal solution to an LP is a
equality.
point in the feasible region with the largest objective function
Boundary points: satisfies all constraints, at least one with
value.
equality
Similarly, for a minimization problem, an optimal solution is a
Extreme point: satisfies all constraints, two with equality.
point in the feasible region with the smallest objective function
value.
If a linear programming has an optimal solution, an
Most LPs have only one optimal solution. However, some
LPs have no optimal solution, and some LPs have an infinite extreme point is optimal.
number of solutions. EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi
25 26
Definitions Finding the Optimal Point
Feasible solution - a vector x which satisfies the How to find the optimal point?
constraints of an LP. The set of feasible solutions is Randomly draw objective function line.
called the feasible set or feasible region. Push the line in the “direction of decrease” (if minimization
problem) or the “direction of increase” (if maximization
problem)
Optimal Solution: A feasible solution that makes the value
The last point that you encounter in the feasible region is
of the objective function an optimum (maximum or the optimal point
minimum) is called an optimal solution (maximizer,
minimizer). EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi
27 28
Interesting Facts Sensitivity Analysis
Rarely are the parameters in the objective function and constraints
The feasible region will have a finite number of
known with certainty.
extreme points – Usually parameters are just estimates which don’t reflect
Extreme points are the intersections of constraints uncertainties such as absenteeism or personal transfers in the
Stratton Company problem.
(including non-negativity)
– After solving the problem using these estimated values, the
analysts can determine how much the optimal values of the
Any linear program that has an optimal solution decision variables and the objective function value Z would
be affected if certain parameters had different values. This
has an extreme point that is optimal!!
type of post solution analysis for answering “what-if”
EE 477 Dr. Mohamed Zribi questions is called sensitivity analysis. EE 477 Dr. Mohamed Zribi
29 30
A. Quadratic Functions
A function of n variables f(x1,x2,…..,xn) is called a quadratic form if
n n
2. Mathematical
f ( x1 , x 2 ,...., x n ) q ij x i x j x T Qx , where Q(nxn) = [qij] and
i 1 j 1
xT = (x1,x2,…..,xn).
Background • Q is assumed to be symmetric.
• Otherwise, Q can be replaced with the symmetric matrix
(Q+QT)/2 without changing value of the quadratic form.

31 32
Quadratic Functions Quadratic Functions
It is not necessary for Q to be symmetric.
Quadratic functions are important for some of the – Supose that the matrix P is non-symmetric
methods we will study. 1 n n
1 T
f x pij xi x j x Px
2i1 j 1 2
A quadratic function can be written in the form: xTQx
p11 p12 p1n x1
where x is the vector of variables and Q is a matrix of 1 p21 x2
x1 x2
coefficients 2 : :
pn1 pnn :
Example 2: 2 1 0 x1 1 T
x Qx where qij
1
( pij p ji )
x1 x2 x3 1 2 1 x2 2(x1 ) 2
2x1x 2 2(x 2 ) 2 2 2
0 1 2 x3 Q is symmetric
– 2x 2 x 3 2(x 3 ) 2 EE 477 Dr. Mohamed Zribi
33 34
Example 3: Example 4:
– Supose matrix P non-symmetric.
f ( x)
1 2
2x1 2x1x2 4x1x3 6x22 4x2 x3 5x32
Polynomial terms up to 2nd order:
2
2 2
2 2 4 f ( x1 , x2 , x3 ) 3 4 x2 2 x1 x2 x1 x3
1 T
f ( x) x Px, P 0 6 4
2 General form:
0 0 5 1 T
f ( x) x Ax bT x c
2
2 1 2 T T
1 T x1 2 4 0 x1 0 x1
x Qx , Q 1 6 2 1
2 x2 0 0 0 x2 4 x2 3
2 2 5 2
x3 0 0 2 x3 0 x3
Q is symmetric
35 36
Example 5: B. The Hessian Matrix
1 0 0
x1 The second derivative of an n - variable function is defined
xT x1 x2 x3 A 0 1 0 x x2
0 0 1 x3
by the n2 partial derivatives:
1 0 0 x x1
T T 1
x Ax x ( Ax ) Ax 0 1 0 x2 x2 2
f (x) 2
f (x)
0 0 1 x3 x3 , i j, , i j.
xi x j xi2
x1
T T T
F ( x) x Ax x ( Ax) x1 x2 x3 x2 x12 x22 x32
x3
F ( x) x12 x22 x32
37 38
These n2 second partial derivatives are usually represented Example 6:

by a square, symmetric matrix, termed the Hessian matrix.
The Hessian (H= 2 f ) of f (x1, x2, …, xn) is: f 15 x1 2( x2 ) 3 3 x1 ( x3 ) 2
f2 f2 f2
x12 x1 x2 x1 xn
2 2 2
f 15 3( x3 ) 2 6( x2 ) 2 6 x1 x3
f f f
2
H f x2 x1 x2 2 x2 xn
0 0 6 x3
2
H f 0 12 x2 0
f2 f2 f2
6 x3 0 6 x1
xn x1 xn x2 xn 2
39 40
f ( x) x1 x22 x2 cos x1 1 3 1 3
f ( x, y ) x y y2 xy
2
f f
2
2 2
x 12 x1 x 2 x 2 cos x 1 2x 2 sin x 1
f (x)
2
2
f f
2
2x 2 sin x 1 2x 1
3 2
x1 x 2 x 22 x y
2
f ( x, y )
Note: If the Hessian matrix of f(x) is a constant 3 2
y 2y x
matrix, f(x) is then quadratic, expressed as: 2
2 3x 1
T T H ( x, y ) f ( x, y )
f (x) 1
2 x Hx c x 1 3y 2
2
f (x) Hx c, f (x) H
41 42
C. Positive/Negative Definite Matrices D. Tests of Positive Definite Matrices

• H(x) is positive definite if and only if xTHx > 0 for all x 0. The matrix H is positive definite y T Hy 0 y 0
• H(x) is negative definite if and only if xTHx < 0 for all x 0.
• H(x) is positive semi-definite if and only if xTHx ≥ 0 for all x and Test for positive definiteness:
there exists and x 0 such that xTHx = 0.
– Show that yTHy for all y (test #1)
• H(x) is negative semi-definite if and only if xTHx ≤ 0 for all x and – Or All the eigenvalues i of H are positive
there exists and x 0 such that xTHx = 0. (test #2)

– Or Sylvester’s rule: all determinants
of H and its principal submatrices

T T
• H(x) is indefinite if and only if x Hx > 0 for some x, and x Hx <
are positive (test #3)
0 for some other x. EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi
43 44
Remark: Example 9: Test #1 for Positive and Negative Definiteness
Theorem: A matrix Q is positive definite when xTQx > 0 for all x ≠ 0.
A positive semi-definite matrix has nonnegative diagonal entries. • Q
2 1 is positive definite.
1 2
A positive definite matrix has positive diagonal entries.
A matrix Q is positive semi-definite when xTQx ≥ 0 for all x and
there exists an x ≠ 0 such that xTQx = 0.
Theorem: 1 1
• Q is positive semi-definite.
1 1
A real symmetric matrix is indefinite if and only if it has positive
and negative eigenvalues.
A matrix Q is negative definite when xTQx < 0 for all x ≠ 0.
3 1
• Q is negative definite.
1 4

45 46
Test #2 for Positive and Negative

Definiteness
A matrix Q is negative semi-definite when –Q is positive semi- A matrix M is “positive definite” if all its eigenvalues are
definite.
positive (> 0). We write M > 0.
1 1
Q is negative semi-definite.
1 1
A matrix Q is indefinite when xTQx > 0 for some x and < 0 for
A matrix is “negative definite” if all of its eigenvalues are
other x.
1 2
Q
2 2
is indefinite. negative (< 0). We write M < 0.

47 48
Test #2 for Positive and Negative Eigenvalues of a Matrix
Definiteness
Let A be an n n matrix with eigenvalue and corresponding
A matrix M is “positive semi-definite” if all of its
eigenvector x. Thus Ax = x. This equation may be written
eigenvalues are non-negative (≥ 0). We write M ≥ 0. Ax – x=0
=>
(A – In)x = 0
Solving the equation |A – In |= 0 for leads to all the eigenvalues of
A matrix M is “negative semi-definite” if all of its
A. On expanding the determinant |A – In|, we get a polynomial in .
eigenvalues are non-positive (≤ 0). We write M ≤ 0. This polynomial is called the characteristic polynomial of A.
The equation |A – In| = 0 is called the characteristic equation of A.

49 50
Remark: Remark:
If A is an n n triangular matrix, then its eigenvalues are the

entries on its main diagonal.
•If A is a diagonal matrix, then its eigenvalues are the diagonal
elements. Example 9: 1 0 0 0 0
2 0 0 0 2 0 0 0
(a) A 1 1 0 (b) A 0 0 0 0 0
•A and AT have the same eigenvalues. 0 0 0 4 0
5 3 3 0 0 0 0 3
Solution: 2 0 0
•The constant term of the characteristic polynomial of a matrix A (a) I A 1 1 0 ( 2)( 1)( 3)
is |A| (determinant of A). 5 3 3
1 2, 2 1, 3 3
(b) 1 1, 2 2, 3 0, 4 4,5 3
EE 477 Dr. Mohamed Zribi 51 EE 477 Dr. Mohamed Zribi 52
Eigenvalues Test Example 10:
A I 0
1 1 0 1 1 0 0 0
Form Eigenvalue Test A 1 1 0 A I 1 1 0 0 0 0
0 0 1 0 0 1 0 0
Positive Definite (PD)
x T A x 0 for all x , i 0 1 1 0
other than x 0 For i=1,…,n
A I 1 1 0 0
Positive Semi-def (PSD)
0 0 1
xT A x 0 for all x , and i 0
T
x A x 0 for at least one x 0 For i=1,…,n ( 1 )2 1 0
2
A I ( 1 )[( 1 )2 1] 0 (1 2 ) 1 0
2
Indefinite 0 2 0
i ( 2 ) 0
T
x A x 0 for some x i 0 1 1, 2 0, 3 2
xT A x 0 for other x EE 477 Dr. Mohamed Zribi Therefore A is NSD
53 54
Test #3 for Positive and Negative Tests

Definiteness
Tests for positive definite matrices
• All diagonal elements must be positive.
Theorem :
• All the leading principal determinants must be positive.
A real symmetric matrix M is positive definite if and only if
Tests for positive semi-definite matrices
its leading principal sub-matrices (minors) have positive determinents.
• All diagonal elements are non-negative.
• All the principal determinants are non-negative.
Theorem :
A real symmetric matrix M is positive semi-definite if and only if Tests for negative definite and negative semi-definite matrices
its leading principal sub-matrices (minors) have non-negative • Test the negative of the matrix for positive definiteness or
determinents. positive semi-definiteness.
Test for indefinite matrices
• At least two of its diagonal elements are of opposite sign.
55 56
Principal Minor of a Matrix Leading Principal Minors of a Matrix
Principal minor of order k: A sub-matrix obtained by deleting any Let the matrix A be such that:
n-k rows and their corresponding columns from an n x n matrix a11 a12 a13
Q. A a21 a22 a23
1 2 3
Consider Q 4 5 6 a31 a32 a33
7 8 9
Principal minors of order 1 are diagonal elements 1, 5, and 9.
The leading principal submatrices of A are:
Principal minors of order 2 are 1 2 1 3 5 6
, and a11 a12 a13
4 5 7 9 8 9 a11 a12
Principal minor of order 3 is Q. [a11 ], , a21 a22 a23
a21 a22
Determinant of a principal minor is called principal determinant. a31 a32 a33
• There are 2n-1 principal determinants for an n x n matrix.

57 58
Example 11: Leading Principal Minors Example 12:

1 2 3
Q 4 5 6
F ( x) 2 x12 4 x1 x3 3 x12 6 x2 x3 x32
7 8 9
Leading principal minor of order 1 is 1. 2 0 4 x1

1 2 x1 x2 x3 0 3 6 x2
Leading principal minor of order 2 is F1 2 0
4 5 0 0 1 x3
F2 6 0
2 0 2 x1
F3 24 0
Leading principal minor of order 3 is Q itself. x1 x2 x3 0 3 3 x2
2 3 1 x3
The number of leading principal determinants of an n x n matrix F is indefinite.

is n.
59 60
A. Convex Functions
Convex function: A function is convex on set D

if and only if for any two points x1 and x2 Є D
3. Convex and Concave and 0 ≤ λ ≤ 1,
• f[λx1 + (1-λ) x2] ≤ λf(x1) +(1- λ) f(x ) 2
Functions

61 62
Concave Function 1D Convex and Concave Functions

A function f(x) is called a concave function if for any two
points x1 and x2, and for all 0 1, Convex and concave functions in one variable
f x 2 (1 )x1 f (x 2 ) (1 ) f (x1 )
that is, if the line segment joining the two points lies entirely
below or on the graph of f(x).
It can be seen that a concave function bends downward and

hence the local maximum will also be its global maximum.
It can be seen that the negative of a convex function is a

concave function.

63 64
Example 13: Graph of a Strictly Convex Function Example 14: Graph of a Convex Function
f f
x1 αx1+(1-α)x2 x2 x1 x2
αx1+(1-α)x2
65 66
Example 15: Graph of a Strictly Concave Function

Example 16: Graph of Neither Convex or Concave
f f
x1 αx1+(1-α)x2 x2 x1 x2

67 68
2D Convex and Concave Functions nD Convex Functions
A function f(x) is said to be convex if for any pair of points
Convex and concave functions in two variables
x1(1) x1( 2 )
x2(1) x2( 2 )
x1 and x 2
xn(1) xn( 2 )
and all , 0 1,
f x 2 (1 )x1 f (x 2 ) (1 ) f (x1 )
that is, if the segment joining the two points lies entirely above or on the
graph of f(x).
A convex function is always bending upward and hence it is apparent that

the local minimum of a convex function is also a global minimum
69 70
Combinations of Convex Functions Test of Convexity of a Function

Proposition 1
– Let f1 and f2 be convex function on the convex set Ω. Test for convexity of a function: A function f is convex
if the Hessian matrix of f is positive definite or positive
Then the f1 + f2 is convex on Ω.
semi-definite for all values of x1, x2 ,…, xn.
Proposition 2
– Let f be a convex function over the convex set Ω.
Test for concavity of a function: A function f is concave
Then a f is convex for any a ≥ 0.
if the Hessian matrix of f is negative definite or negative
– Through the above two propositions it follows that a semi-definite for all values of x1, x2 ,…, xn.
positive combination a1 f1+a1 f2+…am fm of is again
convex. EE 477 Dr. Mohamed Zribi
71
72
Test of2 Convexity of a Function Test of Convexity of a Function
f
If f ( x) 0 then f ( x ) is concave.
x2 • f (x) is strictly convex (or just convex) if its
2
f associated Hessian matrix H(x) is positive definite
If f ( x) 2
0 then f ( x ) is convex. (semi-definite) for all x.
x
For a multivariate function f(x) the conditions are:- • f (x) is neither convex nor concave if its associated
Hessian matrix H(x) is indefinite
f(x) H(x) Hessian matrix
The terms negative definite and negative-semi-
Strictly convex +ve def definite are also appropriate for the Hessian and
convex +ve semi def provide symmetric results for concave functions.
concave -ve semi def
strictly concave -ve def Recall that a function f (x) is concave if –f (x) is
convex.
73 74
f(x)
Example 17:
Strictly concave function
f ( x) 0 Determine whether the following function is convex or concave.
f(x) = ex
x
xa xb
Solution:
f(x)
d2 f
H ( x) ex 0 for all real values of x. Hence f(x) is strictly convex.
dx 2
f ( x) 0
Strictly convex function
x
xa Zribi
EE 477 Dr. Mohamed
xb
75 76
Determine whether the following function is convex or concave.
Determine whether the following function is convex or concave. f(x1,x2) = 2x13-6x22
Solution:
f(x) = -8x2 2
f 2
f
x12 x1 x2 12 x1 0
H ( x)
f2 2
f 0 12
Solution:
x1 x2 x22
Here
d2 f
H ( x) 16 0 for all real values of x. Hence f(x) is strictly concave.
dx 2 2
f
12 x1 0 for x1 0 H(x) 144 x1 0 for x1 0
x12
0 for x1 0
0 for x1 0
Hence H(x) will be negative semidefinite and f(x) is concave for x1 ≤ 0

77 78

f (x) = 3x1x2 + x12 + 3x22 f (x) = 24x1x2 + 9x12 + 16x22
3x2 2 x1 2 3 24 x 2 18 x 1 18 24
f (x) and H( x )
f (x) and H( x ) 24 x 1 32x 2 24 32
3x1 6 x2 3 6
so |H1| = 18 and |H2| = 576 – 576 = 0
so |H1| = 2 and |H2| = 12 – 9 = 3
• Thus H is positive semi-definite (determinants of
Conclusion f (x) is strictly convex all submatrices are nonnegative) so f (x) is convex.
because H(x) is positive definite.
• Note, xTHx = 2(3x1 + 4x2)2 ≥ 0. For x1 = 4, x2 = 3,
we get xTHx = 0.

79 80
f (x) = (x2 – x12)2 + (1 – x1)2
Determine whether the following function is convex or concave.
2
4 x2 12 x 1 2 4 x1 f ( x1 , x2 , x3 ) 4 x12 3 x22 5 x32 6 x1 x2 x1 x3 3 x1 2 x2 15
H( x )
4 x1 2
Solution:
Thus the Hessian depends on the point under consideration: 2

f 2
f 2
f
2
10 4
x 1 x1 x2 x1 x3
At x = (1, 1), H(1,1) which is positive definite. 2 2 2
8 6 1
4 2 f f f
H ( X) 6 6 0
x1 x2 x22 x2 x3
2 2 2
1 0 10
2 0 f f f
At x = (0, 1), H(0,1)
0 2
which is indefinite. x1 x3 x2 x3 x32
Thus f(x) is not convex although it is strictly convex near (1, 1).
81 82
Example 24:
Here the principal minors are given by: f (x1, x2, x3) 3x12 2x22 x32 2x1x2 2x1x3 2x2x3 6x1 4x2 2x3
8 8 0
6x1 2x2 2x3 6 • H is a symmetric.
8 6
12 0 f (x1, x2, x3) 4x2 2x1 2x3 4 • All diagonal elements are positive.
6 6
2x3 2x1 2x2 2
8 6 1 • The leading principal determinants are
6 2 2
6 6 0 114 0 6 0 6 2
Hf (x1, x2, x3) 2 4 2 20 0
1 0 10 2 4
2 2 2
Hf 16 0
and hence the matrix H(x) is positive definite for all real values of • H is a positive-definite matrix, which implies f is convex function
x1, x2, x3. Therefore f(x) is strictly convex function.
83 84
Example 25: f ( x ) 2 x12 3x1 x2 2 x22 Example 26:
f (x) 2
f (x) 2
f (x) f (x) = (x2 – x12)2 + (1 – x1)2
4 x1 3 x2 4 3
x1 x12 x1 x2
4 x2 12 x12 2 4 x1
f (x) 2
f (x) H( x )
3 x1 4 x2 4 4 x1 2
x2 x22
4 3 4 3 Thus the Hessian depends on the point under consideration:
H ( x) , 1 4, 2 7 10 4
3 4 3 4 At x = (1, 1), H(1,1)
4 2
which is positive definite.
4 3 2 2 0
eigenvalues: | I 2 H| 8 7 0 At x = (0, 1), H(0,1) which is indefinite.
3 4 0 2
1 1, 2 7. Hence, f (x) is strictly convex. Thus f(x) is not convex although it is strictly convex near (1, 1).
85 86
Convex Sets
A convex set of points exists, if for any two points

in the set (say xa and xb ), all points on the line
4. Convex Sets joining xa and xb ,[ i.e. x xa (1 )xb and

0 1] are also in the same set.
Therefore, a set of points S is a convex set if the line
segment joining any two points in S lies entirely in S

87 88
Convex Sets Convex Sets
xa
xb
convex
xa region non convex
A set S is convex set (or region) if for any two
region xb points in the set the line joining those two points
is also in the set.
A convex set of points exist if for any two points, xa S is a convex set if for any two vectors x(1) and
and xb, in a region, all points: x(2) in S, the vector x = λ x(1) +(1-λ) x(2) is also in
S for λ between 0 and 1.
x xa (1 )xb , 0 1
on the straight line joining xa and xb are in the set.
If a region is completely bounded by concave functions then
the functions form a convex region. EE 477 Dr. Mohamed Zribi
89
90
Convex Sets Example 27:

The intersection of convex sets is a convex set Line segment joining any 2 pts lies inside shape
(Figure A.4).
The union of convex sets is not necessarily a
convex set (Figure A.4).
convex NOT convex

91 92
Convex set:
All pts in feasible
region on a straight
line (s).
Non-convex set
Pts on line are not in
feasible region
Region above a convex function is a convex set.

93 94
Nice Property of Convex Shapes: Intersection of convex

shapes is convex

95 96
Why do we need to discuss convexity?
Determination of convexity or concavity can be used to
establish whether a local optimal solution is also a global
5. Convexity and Linear optimal solution.
Programming If the objective function is known to be convex or

concave, computation of optimum can be accelerated by
using appropriate algorithm.

97 98
Convex Region Convexity and Linear Programs
If a region is completely bounded by • Every Half-space is convex

gj x 0 j=1,2, ,mi
and g j x s are concave functions, then the • Each inequality constraint of an LP is a half space
bounded region is convex.
=> The feasible region of an LP is a convex set
If a region is completely bounded by
gj x 0 j=1,2, ,mi
and g j x s are convex functions, then the
bounded region is convex.
99 100
Extreme Points Convexity and Linear Programs
A point P in a convex set S is an extreme point if,
for any line segment containing P which lies The extreme points of a polygon are the corner
entirely in S, P is an endpoint of that segment. points.
C
C and D are extreme points
A
The feasible region for any linear program is a
A and B are not
B
convex set.
D
101 102
Convexity and Linear Programs Convexity and Linear Programs

r
min f x min f x1 , x2 ,
x
, xr Ci xi Convex function
x i 1
s.t. gi x 0 i 1, ,m subject to
r
in which a ji xi bj j 1, 2, ,m
Convex i 1
(a) f x is a convex function, and region r
a ji xi bj j m 1, m 2, ,p
(b) each inequality constraint is a convex function i 1
xi 0 i 1, 2, ,r
(so the constraints form a convex set).
A local minimum is a global minimum.
The minimum must lie at the intersection
The local minimum of f x is also the global minimum! of several constraints, but not in the interior
of the convex region. EE 477 Dr. Mohamed Zribi
103 104
Introduction
To be able to solve an LP using the graphical method, you

need to be able to plot the constraints of the problem.
6. Plotting the Constraints
In the following, several examples are solved to show how
of a Linear Program to plot the constraints of a LP.

105 106

Plot the constraint 4x1 + 6x2 48.
Plot the line 2x+3y =c where c = 0, 3, 6 and 9
We start with:
4x1 + 6x2 = 48
At the x1 axis intercept, x2 = 0, so

4x1 + 6(0) = 48
x1 = 12
y
3
To find the x2 axis intercept, set x1 = 0 and solve for x2
2 4(0) + 6x2 = 48
x2 = 8
2x+3y = 0 1
We connect points (0, 8) and (12, 0) with a straight line, as
x
(0,0) 1.5 3 4.5 shown in the next Figure.
107 108
Example 34:
x2
18 – Plot the region where 2x+3y < 6
16 –
14 –
12 –
y
10 – (0, 8)
3
8– 2x+3y > 6
2
6– 2x+3y < 6
4x1 + 6x2 ≤ 48 1
4– x
(0,0) 1.5 3 4.5
2– (12, 0)
0– | | | | | | | | |
x1
2 4 6 8 10 12 14 16 18
109 110
Example 35: Systems of Linear Inequalities

Plot the Plane x + y + z = 1
Linear inequalities:
For example, 3x – 2y < 6 and x + y 6 are linear
inequalities involving two variables.
z
1 Plane
x+y+z=1 Solution of an inequality:
An ordered pair (a, b) is a solution of an inequality in x and y if
the inequality is true when a and b are substituted for x and y,
x respectively
1
1
y The graph of an inequality:
The collection of all solutions of the inequality

111 112
Example 36:
Sketch the graph of the inequalities (a) x > – 2 and (b) y 3
Solution:
Step 1: Replace the inequality sign with an equal sign, and
sketch the graph of the corresponding equation, e.g., x = – 2
The solutions of x > –2 are The solutions of y 3 are
points lying to the right of x points lying below (or on)
Step 2: Test one points in each of the regions formed by the = –2 (A dashed line is used the line of y = 3 (A solid
graph in step 1. If the point satisfies the inequality, then shade for > or <) line is used for or )
Notes: The corresponding equation separates the plane into two regions, and one
the entire region to denote that every point in the region of the following two statements is true
satisfies the inequality (1) All points in the region are solutions of inequality
(2) No points in the region are solutions of the inequality
113 114
Example 37: Systems of linear inequalities:

For example,
Sketch the graph of the inequalities x – y < 2 x y 12
3 x 4 y 15
Solution:
x 0
Sketch the corresponding
y 0
equation x – y = 2 first
is a system of linear inequalities
Because the origin (0, 0) satisfies
the inequality, the solution
region is the half-plane lying
above (or to the left of) the line Solution of a system of inequalities:
x–y=2
A solution is an ordered pair (x, y) satisfying each inequality in
※ Another methods to find the solution region the system
(1) Since x < y + 2, the solution points should lie to the left of x – y = 2
(2) Since y > x – 2, the solution points should lie above x – y = 2 The graph of a system of inequalities:
The above two methods also generate the correct result The collection of all solutions of the system EE 477 Dr. Mohamed Zribi
EE 477 Dr. Mohamed Zribi 115 116
Example 38:
Solving a system of inequalities
Sketch the graph (and label the vertexes) of the solution set
of the system shown below
x y 2
x 2
y 3
Notes: For complicated regions, two border lines could
Solution: intersect at a point that is not a vertex of the solution region
Vertex A(–2, –4): the intersection of x – y = 2 and x = –2
Vertex B(5, 3): the intersection of x – y = 2 and y = 3
Vertex C(–2, 3): the intersection of x = –2 and y = 3
117 118
Notes: The system might have no solution or the solution set

of a system can be unbounded
No solution Solution region

is unbounded
7. Common Terminology
x y 3 x 2y 3
x y 1 x y 3 for LP Model

119 120
Common Terminology for LP Models Common Terminology for LP Models
Objective Function:
The function being maximized or minimized is called the objective function.
Constraint: The Wyndor Glass Co. example is used to illustrate some
The restrictions of LP Model are referred to as constraints. Common Terminology for LP Model
The first m constraints are sometimes called functional constraints.
The restrictions xj ≥ 0 are called nonnegativity constraints.
A feasible solution is
located in the feasible
Feasible Solution: region.
A feasible solution is a solution for which all the An infeasible solution
is outside the feasible
constraints are satisfied. region.
Infeasible Solution:
An infeasible solution is a solution for which
at least one constraint is violated.
Feasible Region:
The feasible region is the collection of all
feasible solutions. EE 477 Dr. Mohamed Zribi
121
122
No Feasible Solutions: Optimal Solution:

It is possible for a problem to have no feasible solutions. An optimal solution is a feasible solution that has the maximum or minimum of
the objective function.
Multiple Optimal
Example 39: Solutions:
It is possible to have more
than one optimal solution.
The Wyndor Glass Co.
problem would have no
feasible solutions if the Example 40:
constraint 3x1 + 5x2 ≤ The Wyndor Glass Co. problem
50 were added to the would have multiple optimal
In this case, there
problem. is no feasible solutions if the objective function
region
were changed to Z = 3x1 + 2x2
123 124
Common Terminology for LP Models Common Terminology for LP Model
Unbounded Objective:
If the constraints do not prevent Corner-Point Feasible (CPF) Solution:
improving the value of the A corner-point feasible (CPF) is a solution that lies at a corner of the feasible
objective function indefinitely in
the favorable direction, the LP region.
model is called having an
unbounded objective. Example 42:
Example 41: The five dots are the five CPF
The Wyndor Glass Co. problem solutions for the Wyndor Glass
would have no optimal solutions
Co. problem
if the only functional constraint
were x1 ≤ 4, because x2 then could
be increased indefinitely in the
feasible region without ever
reaching the maximum value of
Z = 3x1 + 2x2 EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi
125 126

Relationship between optimal solutions and CPF solutions :
Consider any linear programming problem with feasible solutions
and a bounded feasible region. The problem must posses CPF
solutions and at least one optimal solution. Furthermore, the best
CPF solution must be an optimal solution. Therefore, if a problem
has exactly one optimal solution, it must be a CPF solution. If the
problem has multiple optimal solutions, at least two must be CPF
The prototype model has exactly one
solutions. optimal solution, (x1, x2)=(2,6), which is
a CPF solution

127 128
Common Terminology for LP Models
(2,6)
8. Steps for Solving LP
(4,3) Problems using the
The modified problem has multiple optimal
solution, two of these optimal solutions ,
(2,6) and (4,3), are CPF solutions.
Graphical Method

129 130
Solving Linear Programs Solving Linear Programs

Computer Programs are generally used to solve LP The goal of a linear program is to find the values of the
problems. xj variables that provide the largest (or smallest)
possible objective value when substituted into the
We will learn how to use the graphical method to objective function.
solve small problems and gain insight into some
theory behind solving LPs. The Graphical Method can be used to solve the LP for
these values when you have one or two decision
Nevertheless, we need to use computer software to variables. This technique helps to visualize key LP
solve LP models. concepts.
131 132
Graphical Solution Graphical Solutions of Linear
Programming Models
Graphing an LP model helps provide insight into LP
models and their solutions. Graphical solution is limited to linear programming models
containing only two decision variables. (Can be used with
While this can only be done in two dimensions, the same three variables but only with great difficulty.)
properties apply to all LP models and solutions.

Graphical methods provide visualization of how a solution
for a linear programming problem is obtained.

133 134
Solving LP Problems Using the

• Next we note that each constraint line divides the plane into two
Graphical Method
half-spaces and that on one half-space the constraint will be ≤ and
We shall use graphical method to solve LP problems. on the other it will be ≥.
First: Determination of the Feasible solution space
The non-negativity restrictions tell that the solution space is in the

• To determine the “correct” side we choose a reference point and
first quadrant.
see on which side it lies. (Normally (0,0) is chosen. If the
Then we replace each inequality constraint by an equality and then constraint line passes through (0,0), then we choose some other
graph the resulting line (noting that two points will determine a point.) Doing like this we would get the feasible solution space.
line uniquely).
135 136
Second: Determination of the optimal solution Graphic Solution of LP Problems
The determination of the optimal solution requires the direction in 1- Graph constraint to find the feasible point
which the objective function will increase (decrease) in the case 2-Identify the feasible region
of a maximization (minimization) problem. We find this by 3- Set the objective function equal to an arbitrary value so
that line passes through the feasible region.
assigning two increasing (decreasing) values for z and then
4- Move the objective function line parallel to itself until it
drawing the graphs of the objective function for these two values.
touches the last point of the feasible region .
The optimum solution occurs at a point beyond which any further
5- Solve for x1 and x2 by solving the two equation that
increase (decrease) of z will make us leave the feasible space. intersect to determine this point
6- Substitute these value into objective function to determine
its optimal solution.

137 138
Example 43: Find the solution of the following Model

30 maximize Z= 25x1 + 20x2
subject to
5x1 + 2x2 60
9. Examples of Solving 20
5x 1 2x 2 60 x1 + x2 20
x1, x2 0
LP Problems Using the

10
Graphical Method
4 12 20

139 140
maximize Z= 25x1 + 20x2 maximize Z= 25x1 + 20x2
subject to subject to
5x1 + 2x2 60 30 5x1 + 2x2 60
30 x1 + x2 20 x1 + x2 20
x 1, x 2 0
x1, x2 0
5 x1 2 x2 60
5x 1 2x 2 60 20
20
x1 x2 20
x1 x 2 20
10
10
x1 0 4 12 20
4 12 20
EE 477 Dr. Mohamed Zribi x2 0EE 477 Dr. Mohamed Zribi
141 142
The feasible region is a polygon!! How do we find the optimal solution??

30
maximize Z= 25x1 + 20x2
subject to We must graph the How??
5x1 + 2x2 60
5 x1 2 x2 60 isoprofit line.
20
x1 + x2 20 – Choose any point in
x 1, x 2 0
– Straight line the feasible region
– All points on the line – Find its objective
x1 x2 20 value (or z-value)
have the same objective
10 Feasible value – Graph the line
region
– When problem is objective function
minimization, called an = z-value.
isocost line.
x1 0 4 12 20
x2 0EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi

143 144
maximize Z = 25x1 + 20x2 maximize Z= 25x1 + 20x2
30 30 5x1 + 2x2 60
5x1 + 2x2 60 x1 + x2 20
Isoprofit line x1 + x2 20 Isoprofit line x 1, x 2 0
z = 300 x1, x2 0
20 20
10 10
4 12 20 4 12 20
Z = 25x1 + 20x2
Z = 25x1 + 20x2 EE 477 Dr. Mohamed Zribi
145 146

30 5x1 + 2x2 60 30 5x1 + 2x2 60
x1 + x2 20 x1 + x2 20
Isoprofit line x 1, x 2 0 Isoprofit line x 1, x 2 0
z = 433 1/3
20 20
optimal solution:
(20/3, 40/3)
z = 433 1/3
Z = 25x1 + 20x2
10 10
Z = 25x1 + 20x2
4 12 20 4 12 20

147 148
Binding vs. Nonbinding maximize Z= 25x1 + 20x2
subject to
30 5x1 + 2x2 60
x1 + x2 20
binding x 1, x 2 0
A constraint is binding if the optimal solution
satisfies that constraint at equality (left-hand side = 20
optimal solution:
right-hand side). Otherwise, it is nonbinding. (20/3, 40/3)
z = 433 1/3
10
Binding constraints keep us from finding better binding
solutions!!
4 12 20

149 150
Example 44:
Step 1: Model Coordinate Axes
Using the Graphical Method, find the solution of the
following maximization problem:
maximize Z=$40x1 + 50x2
subject to
1x1 + 2x2 40 hours of labor
4x1 + 3x2 120 pounds of clay
maximize Z= 40x1 + 50x2 x 1, x 2 0
subject to
1x1 + 2x2 40 (hours of labor)
4x2 + 3x2 120 ( pounds of clay)
x1, x2 0
Figure 1 Coordinates for graphical analysis

151 152
Step 2: Draw the Labor Constraint Step 3: Draw the Clay Constraint Area

1x1 + 2x2 40 hours of labor 1x1 + 2x2 40 hours of labor
4x1 + 3x2 120 pounds of clay 4x1 + 3x2 120 pounds of clay
x 1, x 2 0 x 1, x 2 0
Figure 3 The constraint area for clay

Figure 2 The labor constraint area

153 154
Step 4: Draw the Area Common to both constraints Step 5: Identify the Feasible Solution Area

x 1, x 2 0 x 1, x 2 0
Figure 4 The feasible solution area constraints

Figure 4 Graph of both model Constraints

155 156
Step 6: Draw the Objective Function = $800 Step 7: Draw Alternative Objective Functions

x 1, x 2 0 x 1, x 2 0
Figure 6 Objective function line for Z = $800 Figure 7

Alternative objective function lines for profits, Z, of $800, $1,200, and $1,600
157 158
Step 8: Draw the Optimal Solution Step 9: Identify the Optimal Solution Coordinates

x 1, x 2 0 x 1, x 2 0
Figure 8 Identification of optimal solution point Figure 9 Optimal solution coordinates

159 160
Step 10: Corner Point Solutions
Optimal Solution Z= $1360
x1 =24 Bowls
x2 = 8 mugs
maximize Z= 40x1 + 50x2
subject to
x 1, x 2 0
Solution Points with

Slack Variables
Figure 10 Solutions at all corner points

161 162
Optimal Solution for New Objective Function Example 45:

Solve the following LP problem:
Optimal Solution Z= $2100
x1 =30 Bowls
x2 = 0 mugs
maximize Z= 70x1 + 20x2 Maximize z = 5x1 + 4x2
subject to
Subject to:
x 1, x 2 0
6x1 + 4x2 < 24 (1)
x1 + 2x2 < 6 (2)
x2 - x1 < 1 (3)
x2 < 2 (4)
x1 > 0 (5)
x2 > 0 (6)
Figure 12 The optimal solution with Z = 70x1 1 20x2

163 164
Step 1: Change all equations to equality signs
6x1 + 4x2 = 24 1 - Plot the graphs of x1 = 0 and x2 = 0
x1 + 2x2 = 6 2 - Plot the graph of 6x1 + 4x2 = 24
x2 - x1 = 1 3 - Plot the graph of x1 + 2x2 = 6
x2 = 2 4
- Plot the graph of x2 - x1 = 1
x1 = 0 - Plot the graph of x2 = 2

5
x2 = 0 6

165 166
Step 2:
2) Determination of the optimum solution from among
all the feasible points in the solution space:
- After finding out all the feasible half-spaces of all
the 6 equations, feasible region is obtained by the
line segments joining all the corner points A, B, C, D, E
and F
- Any point within or on the boundary of the
solution space ABCDEF is feasible as it satisfies all the
constraints
- Feasible region ABCDEF consists of infinite number of
feasible points
167 168
- To find optimum solution identify the direction in which the - Values of x1 and x2 associated with optimum corner point
maximum profit increases , that is z = 5x1 + 4x2 C are determined by solving the equations
- Assign random increasing values to z , z = 10 and z = 15 6x1 + 4x2 = 24
5x1 + 4x2 = 10 x1 + 2x2 = 6
5x1 + 4x2 = 15 - x1 = 3 and x2 = 1.5 with z = 5 * 3 + 4 *1.5 = 21
- Plot graphs of above two equations
- Thus in this way the optimum solution occurs at corner point - So daily product mix of 3 tons of exterior paint and 1.5 tons
C which is the point in the solution space of interior paint produces the daily profit of $21,000 .
- Any further increase in z that is beyond corner point C will

put points outside the boundaries of ABCDEF feasible region
169 170
- Important characteristic of the optimum LP solution is that it is

always associated with a corner point of the solution space (where two
lines intersect)
- This is even true if the objective function happens to be parallel
to a constraint
- For example if the objective function is, z = 6x1 + 4x2
- The above equation is parallel to constraint of equation (1)
- So optimum occurs at either corner point B or corner point
C when parallel
- Actually any point on the line segment BC will be an alternative
optimum
- Line segment BC is totally defined by the corner points B and C
171 172
- Since optimum LP solution is always associated with a corner Example 46:
point of the solution space, so optimum solution can be found
Solve: Max z 3x 2 y
by enumerating all the corner points as below:-
______________Corner point (x1,x2) z___________
subject to : 2 x y 8
A (0,0) 0 x y 4
B (4,0) 20
C (3,1.5) 21 (opt. sol.) x 0, y 0
D (2,2) 18
E (1,2) 13
Steps:
F (0,1) 4 a. Graph the system of inequalities representing the constraints.
b. Find the value of the objective function at each corner of the
graphed region.
- As number of constraints and variables increases , the number of c. Use the values that you found in the prior step to determine the
corner points also increases maximum value of the objective function and the values of x
and y for which the maximum occurs.

173 174
Solution:
10
8 x 0
Graph the constraints: 6
4 y 0
2x y 8 2
-10 -8 -6 -4 -2 2 4 6 8 10
x y 4 -2
-4
x 0, y 0 -6
-8
-10
Max z 3x 2 y
Max z 3x 2 y
x y 4
x y 4
x 0, y 0
x 0, y 0
175 176
2x y 8
x y 4
Max z 3x 2 y Max z 3x 2 y
subject to : 2 x y 8 subject to : 2 x y 8
x y 4 x y 4
x 0, y 0 x 0, y 0
177 178
177 178
Objective function z = 3x+2y

Corners:
(4,0), (0,4), (0,8) Corners Objective function
(4,0) z = 3(4) + 2 (0) = 12
(0,4) z = 3(0) + 2(4) = 8
(0,8) z = 3(0) + 2(8) = 16
Max z 3x 2 y The maximum value of the objective function is 16 and

it occurs when x = 0 and y = 8
x y 4
x 0, y 0
179 180
Example 47: Solution:
Constraint 1 (C1):
Maximize 10 x1 + 9 x2
7/10 x1 + x2 ≤ 630 Always graph constraints as an equality.
Subject to:
0.7 x1 + x2 ≤ 630
In order to graph a line we need two points that fall on the line.
0.5 x1 + 5/6 x2 ≤ 600
1 x1 + 2/3 x2 ≤ 708 Arbitrarily, let x1 = 0. Then 7/10 (0) + x2 =630. Solving this equation
0.1 x1+ 0.25 x2 ≤ 135 for x2 gives x2 =630. Therefore one point on this line is (0, 630).
x1 ≥ 0, x2 ≥ 0
x1 = Number of Standard bags to be produced

Arbitrarily, let x2 =0. Then 7/10 x1 + (0) =630. Solving this equation
x1 = Number of Deluxe bags to be produced
for x1 gives x1 =6300/7=900. Therefore a 2nd point on this line is (900,
We begin the graphical solution process by graphing each linear constraint of the 0). Connect the points (0, 630) and (900,0) to draw this line.
LP model on the same graph. EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi
181 182
Solution:
Determine the Feasible Side of the Line:
In LP, on one side of the line all points are feasible (i.e. they 700
x2
600
satisfy the constraint) and on the other side all points are not
500
feasible. For instance take the point (0,0). The point x1 =0 and
400
x2 =0 satisfy the above constraint [7/10 * (0) + (0) is less than
300 C1
630]. Thus all points that are on the side of the line containing
200
this point will also satisfy this constraint. We put a red arrow to
100
indicate the feasible side of the line. 0

0 200 400 600 800 1000
x1
183 184
Constraint 2 (C2): Arbitrarily, let x2 =0. Then x1 =1200. Therefore a 2nd point
1/2 x1 + 5/6 x2 ≤ 600 on this line is (1200, 0). Connect the points (0, 720) and
In order to graph a line we need two points that fall on the (1200,0) to draw this line.
line. Arbitrarily, let x1 =0. Then 1/2 (0) + 5/6 x2 =600.
Solving this equation for x2 gives x2 =720. Therefore one Determine the Feasible Side of the Line:
point on this line is (0, 720).
Use the point (0,0) as a test point. Since x1 =0 and x2 =0
satisfies the above constraint [1/2 * (0) + 5/6 (0) is less than
Arbitrarily, let x2 =0. Then x1 =1200. Therefore a 2nd point
600]. Thus all points on the side containing the point (0,0)
on this line is (1200, 0). Connect the points (0, 720) and
will satisfy this constraint. We put a red arrow to indicate
(1200,0) to draw this line.
the feasible side of the line.
185 186
Constraint 3 (C3):
1 x1 + 2/3 x2 ≤ 708
In order to graph a line we need two points that fall on the line.
800
Arbitrarily, let x1 =0. Then x2 =1062. Therefore one point on this line is
700
(0, 1062).
600
Arbitrarily, let x2 =0. Then x1 =708. Therefore a 2nd point on this
500 C2
line is (708, 0). Connect the points (0, 1062) and (708,0) to draw this line.
x2
400
300 C1 Determine the Feasible Side of the Line:
200
Using our test point point (0,0), we find that x1 =0 and x2 =0 satisfies the
100 above constraint [1 * (0) + 2/3 (0) is less than 708]. Thus all points on the
0 side containing the point (0,0) will satisfy this constraint. We put a red
0 200 400 600 800 1000 1200
arrow to indicate the feasible side of the line.
x1
187 188
Constraint 4 (C4):
1/10 x1+ 1/4 x2 ≤ 135
1200
Arbitrarily, let x1 =0. Then x2 =540. Therefore one point on this line is (0, 540).
Arbitrarily, let x2 =0. Then x1 =1350. Therefore a 2nd point on this line is (1350, 0).
1000
C3
Connect the points (0, 540) and (1350,0) to draw this line.
800
x2
600 Determine the Feasible Side of the Line:
400 Using our test point (0,0), we find that x1 =0 and x2 =0 satisfies the above constraint
C1 [1 * (0) + 2/3 (0) is less than 708]. Thus all points on the side containing the point
C2
200
(0,0) will satisfy this constraint. We put a red arrow to indicate the feasible side of
0
the line.
0 200 400 600 800 1000
x1
189 190
Non-negativity Constraints
1200 These constraints simply restrict us to the 1st quadrant of our
1000 coordinates (i.e. only 0 or positive values of x1 and x2 are

C3
800 considered feasible on our graph when we highlight our final
feasible region).
x2
600
C1
400
C4
200
C2
0
0 200 400 600 800 1000 1200 1400
x1
191 192
1200 After graphing each of the constraints and their feasible
1000
C3
sides individually, we must determine all points on the
800 coordinates which satisfy all constraints. These points
x2
600
C1 make up the feasible region.
400
C4
200
C2
0
0 200 400 600 800 1000 1200 1400
x1
193 194
The feasible region is colored red. Extreme Points and the Optimal Solution
The corners or vertices of the feasible region are referred to

1200
C3 Once the feasible region is drawn, as the extreme points.

1000
we must determine the point in this
800
C1 region that maximizes (or
Fundamental Theorem of Linear Programming
x2
600 minimizes) the objective function.

C4
400
An optimal solution to an LP problem can be found at an
extreme point of the feasible region.
200
0
0 200 400 600 800 1000 1200 1400
x1
195 196
Extreme Points and the Optimal Solution The feasible region and the extreme points
Optimal point occurs on the objective function line
corresponding to the optimal objective function 1200
value 1000
When looking for the optimal solution, you do not 800
x2
have to evaluate all feasible solution points. 600
You have to consider only the extreme points of the 400
feasible region. 200
0
0 200 400 600 800 1000 1200 1400
x1
197 198
Drawing an Objective Function Line The feasible region and the extreme points
1. Randomly select a point in the feasible region.
2. Substitute the coordinates of this point into the objective function 1200
to obtain an objective function value.

1000
3. Plot the line obtained by setting the original objective function
equal to the objective function value obtained in 2. 800
x2
For this example 600
Step 1: The point (200,0) is in the feasible region. 400

Step 2: The OBJECTIVE FUNCTION 10 x1 + 9 x2 . (200,0) gives 10
Obj. Func. line
(200) + 9 (0)= 2000. 200
Step 3: Plot the line 10 x1 + 9 x2 =2000.

0
Connect the points (0, 222.22) and (200, 0) 0 200 400 600 800 1000 1200 1400
x1
199 200
Finding the Direction of Increase Finding the Direction of Increase
(for Maximization problems) (For Minimization problems)
Maximization problem: Finding the direction of increase Minimization problem: Finding the direction of decrease
1. Let c1= the coefficient of x1 in the objective function. 1. Let c1= - (the coefficient of x1 in the objective function).
2. Let c2= the coefficient of x2 in the objective function. 2. Let c2= - (the coefficient of x2 in the objective function).
3. Plot the point (c1, c2) on the graph. 3. Plot the point (c1, c2) on the graph.
4. Draw an arrow from the origin (the point x1=0, x2=0) to the point 4. Draw an arrow from the origin (the point x1=0, x2=0) to the point
(c1,c2). This is the direction of increase. Push the objective (c1, c2). This is the direction of decrease. Push the objective
function in this direction until you encounter the last point in the function in this direction until you encounter the last point in the
feasible region. This point is optimal. feasible region. This point is optimal.

201 202
Finding the direction of increase for this example Finding the direction of increase for this example
The objective function is 1200
1000
Maximize 10 x1 + 9 x2
800
x2
600 Direction of Increase
400 This is the optimal point.

Thus c1=10 and c2=9. I can draw an arrow from the origin Obj. Func. line
200
in the direction of the point (10,9). This is the direction of 0

0 200 400 600 800 1000 1200 1400
increase. x1
203 204
The optimal solution of the example
Constraint 1: 7/10 x1 + x2= 630
1200
Constraint 3: 1 x1 + 2/3 x2 = 708
1000
Find the point where these two lines intersect.
800
Solve the first equation for x2: => x2= 630-7/10 x1
x2
600
The optimal point is formed by Substitute the above equation for x2 in the 2nd equation.
400 the intersection of Constraint 1
and Constraint 3. x1 + 2/3(630-7/10 x1)=708
200
Solving the above equation for x1 gives, x1 = 540. Thus
0
0 200 400 600 800 1000 1200 1400 x2= 630-7/10 (540)= 252.
x1 The optimal point denoted x1*=540, x2*=252.
205 EE 477 Dr. Mohamed Zribi 206

Example 48: Find the solution of the following Model
Max Z= 7T + 5C (profit)
If we substitute the optimal point x1*=540, x2*=252 into Subject to:
3T + 4C < 2400 (carpentry hrs)
the objective function, 10 (540)+ 9 (252)= 7668.
2T + 1C < 1000 (painting hrs)
C < 450 (max # chairs)
T > 100 (min # tables)
Thus company should produce 540 Standard bags and T, C > 0 (nonnegativity)
T: Number of tables
252 Deluxe bags to receive a maximum profit of $7668.
C: Number of chairs

207 208
C
1000
C
Carpentry Constraint Line Painting Constraint Line
3T + 4C = 2400 2T + 1C = 1000
Infeasible
600 600
> 2400 hrs
Intercepts Intercepts
(T = 0, C = 600) (T = 0, C = 1000)
(T = 800, C = 0) Feasible (T = 500, C = 0)
0
< 2400 hrs
0
0 800 T 0 500 800 T

209 210
C
1000 C
Max Chair Line
Objective Function
C = 450 Line
500
7T + 5C = Profit
Optimal Point
600 400 (T = 320, C = 360)
Min Table Line
450
T = 100 300
Feasible 200
Region
0 100
0 100 500 800 T
0
211 0 100 200 300 400 500 T 212
C
Example 49: Dorian Auto
Additional New optimal point
Constraint 500 T = 300, C = 375 Dorian Auto manufactures luxury cars and trucks.
Need at least 75 more The company believes that its most likely customers
chairs than tables 400 T = 320
C = 360
are high-income women and men.
C > T + 75
No longer
Or
300
feasible To reach these groups, Dorian Auto has embarked on
C – T > 75 an ambitious TV advertising campaign and will
200
purchase 1-mimute commercial spots on two type of
100 programs: comedy shows and football games.
0
0 100 200 300 400 500 T
213 214
Solution:
Each comedy commercial is seen by 7 million high income
women and 2 million high-income men and costs $50,000. Dorian must decide how many comedy and football ads should be
purchased, so the decision variables are
Each football game is seen by 2 million high-income women
– x1 = number of 1-minute comedy ads
and 12 million high-income men and costs $100,000.
– x2 = number of 1-minute football ads
Dorian Auto would like for commercials to be seen by at least Dorian wants to minimize total advertising cost.
28 million high-income women and 24 million high-income Dorian’s objective functions is
men. min z = 50 x1 + 100x2
Dorian faces the following the constraints
Use LP to determine how Dorian Auto can meet its
– Commercials must reach at least 28 million high-income
advertising requirements at minimum cost. women. (7x1 + 2x2 ≥ 28)
– Commercials must reach at least 24 million high-income men.
(2x1 + 12x2 ≥ 24)
– The sign restrictions are necessary, so x1, x2 ≥ 0.
215 216
The Dorian LP has a convex feasible region. To solve this LP graphically begin by graphing the feasible
region.
The feasible region for the Dorian problem contains points X2
for which the value of at least one variable can assume 14 B
High-income women constraint

12
arbitrarily large values. 10

Feasible
8 Region
(unbounded)
6
z = 600
Such a feasible region is called an unbounded feasible 4 z = 320

High-income men constraint
2 E
D
region. 2
A
4 6 8 10
C
12 14 X1

217 218
Example 50: Graphical Solution
Since Dorian wants to minimize total advertising costs, Ozark farms uses at least 800 Ib of special feed is a mixture of
corn and soybean meal with the following compositions:
the optimal solution to the problem is the point in the
feasible region with the smallest z value.
An isocost line with the smallest z value passes through
point E and is the optimal solution at x1 = 3.4 and x2 =
1.4.
The dietary requirement of the special feed are at least 30%
Both the high-income women and high-income men protein and at most 5% fiber.
Ozark Farms wishes to determine the daily minimum- cost
constraints are satisfied, both constraints are binding.
feed mix.

219 220
Graphical Solution
Unlike previous examples, the second and the third

Solution:
We can consider that, constraints pass through the origin. To plot associated
straight lines, we need one additional point, which can be
And the objective function seeks to minimize the total obtained by assigning value to one of the variables and then
daily cost (in dollars) of the feed mix and is thus
solving for other variables. For example, in the second
expressed as
Subject to:
Subject to constraint, x1=200, then x2=140
constrains:

221 222
Minimize z 0.3x 1 0.9x 2

Problem
Example 51:
Optimal Solution Subject to :
x1 x 2 800 -Firm or industry has two bottling plants
0.21x 1 0.30x 2 0
0.03x 1 0.01x 2 0 -One plant located at Coimbatore and other plant
x 1, x 2 0
located at Chennai
-Each plant produces three types of drinks Coca-cola,

Fanta and Thumps-up

223 224
Number of bottles produced per day Solution:
by plant at Let x1 = number of days to produce all the three types of
Coimbatore Chennai____________ bottles by plant at Coimbatore
Coca-cola 15,000 15,000 Also let x2 = number of days to produce all the three types of
Fanta 30,000 10,000 bottles by plant at Chennai
Thumps-up 20,000 50000
Cost per day 600 400 Objective:
(in any unit) Minimize z = 600 x1 + 400 x2
Constraint:
-Market survey indicates that during the month of April there will be a 15,000 x1 + 15,000 x2 > 200,000
demand of 200,000 bottles of Coca-cola , 400,000 bottles of Fanta , and
440,000 bottles of Thumps-up 30,000 x1 + 10,000 x2 > 400,000
-For how many days each plant should be run in April so as to minimize 20,000 x1 + 50,000 x2 > 440,000
the production cost , while still meeting the market demand? x1 > 0
x2 > 0
225 226
Corner points (x1, x2) z= 600 x1 + 400 x2

A (0, 40) 16000
B (12,4) 8800
C (22,0) 13200
-In 12 days all the three types of bottles (Coca-cola, Fanta,
Thumps-up) are produced by plant at Coimbatore
-In 4 days all the three types of bottles (Coca-cola, Fanta,

Thumps-up) are produced by plant at Chennai
-So minimum production cost is 8800 units to meet the market

demand of all the three types of bottles (Coca-cola, Fanta,
Thumps-up) to be produced in April
227 228
Two brands of fertilizer available - Super-gro, Crop-quick.
Decision variables
Field requires at least 16 pounds of nitrogen and 24 pounds of x1 = bags of Super-gro
phosphate. x2 = bags of Crop-quick
Super-gro costs $6 per bag, Crop-quick $3 per bag. The objective function:
Problem : How much of each brand to purchase to minimize minimize Z = $6x1 + 3x2
total cost of fertilizer given following data ? where $6x1 = cost of bags of Super-gro
3x2 = cost of bags of Crop-quick
Chemical Contribution
Model constraints:
Nitrogen Phosphate
Brand (lb/bag) (lb/bag) 2x1 + 4x2 16 lb (nitrogen constraint)
Super-gro 2 4 4x1 + 3x2 24 lb (phosphate constraint)
Crop-quick 4 3
x1, x2 0 (nonnegativity constraint)

229 230
minimize Z = 6x1 + 3x2 minimize Z = 6x1 + 3x2

2x1 + 4x2 16 lb 2x1 + 4x2 16 lb
4x1 + 3x2 24 lb 4x1 + 3x2 24 lb
x 1, x 2 0 x 1, x 2 0
Figure 2.15 Feasible solution area

Figure 2.4 Constraint lines for fertilizer model
231 232
Surplus Variables
A surplus variable is subtracted from a constraint to convert it to an

equation (=).
minimize Z = 6x1 + 3x2

A surplus variable represents an excess above a constraint requirement
subject to level.
2x1 + 4x2 16 lb
4x1 + 3x2 24 lb Surplus variables contribute nothing to the calculated value of the
x 1, x 2 0 objective function.
Subtracting slack variables in the farmer problem constraints:

2x1 + 4x2 - s1 = 16 (nitrogen)
4x1 + 3x2 - s2 = 24 (phosphate)
Figure 2.16 The optimal solution point

233 234
Graphical Solution
Example 53:
Minimize z = 2x1 + 3x2
Subject to x1 + 3 x2 15
Min Z = 6x1 + 3x2 + 0s1 + 0s2
subject to 2 x1 + 2 x2 20
2x1 + 4x2 - s1 = 16
4x1 + 3x2 - s2 = 24 3 x1 + 2 x2 24
x 1, x 2, s 1, s 2 0
x1, x2 0
Figure 2.17 Graph of the fertilizer example

235 236
Solution: Example 54: “ The Galaxy Industry Production”
(0,12) Optimum = 22.5 at (7.5, 2.5) Galaxy manufactures two toy models:
z = 26 – Space Ray.
z = 30
– Zapper.
z= 36
Resources are limited to
z = 39
(4,6) – 1200 pounds of special plastic.
z = 42
– 40 hours of production time per week.
z = 22.5
Minimum at (7.5,2.5) (15,0) EE 477 Dr. Mohamed Zribi
EE 477 Dr. M ohamed Zribi
237 238
Marketing requirement Current production plan calls for:

– Total production cannot exceed 800 dozens. – Producing as much as possible of the more profitable product,
Space Ray ($8 profit per dozen).
– Number of dozens of Space Rays cannot exceed number of – Use resources left over to produce Zappers ($5 profit
dozens of Zappers by more than 450. per dozen).
The current production plan consists of:

Technological input
Space Rays = 550 dozens
– Space Rays requires 2 pounds of plastic and
3 minutes of labor per dozen. Zapper = 100 dozens
– Zappers requires 1 pound of plastic and
Profit = 4900 dollars per week
4 minutes of labor per dozen.

239 240
Solution:
Decisions variables:
The Linear Programming Model
– x1 = Production level of Space Rays (in dozens per week).
Max 8x1 + 5x2 (Weekly profit)
– x2 = Production level of Zappers (in dozens per week).
Objective Function: subject to

2x1 + x2 < 1200 (Plastic)
– Weekly profit, to be maximized 3x1 + 4 x2 < 2400 (Production Time)
x1 + x2 < 800 (Total production)
x1 - x2 < 450 (Mix)
x j > 0, j = 1,2 (Nonnegativity)

241 242
We now demonstrate the search for an optimal solution

X2 Start at some arbitrary profit, say profit = $2,000...
1200 Then increase the profit, if possible...

The plastic constraint: x2
1200
The + x2 < 1200
2x1 Plastic constraint ...and continue until it becomes infeasible
Total production constraint:

x1+ x2 < 800 Profit lines
Profit 4,
= $ 3,
2,
000
800
600 Infeasible
600
Production mix
constraint:
Production Feasible x1-x2 < 450
Time
3x1+4x2 < 2400 Profit =$5040
X1
600 800
x1
400 600 800

243 244
1200 x2
Let’s take a closer look at the optimal x2
point
1200 The plastic constraint:
2x1+x2
The < 1200
Plastic constraint
Total production constraint:
800 Infeasible x1+x2 < 800
600 600
A (0,600)
Infeasible
Production mix
constraint:
Production Feasible B
(480,240) x1-x2 < 450
Time C
Feasible
Feasible (550,100)
region 3x1+4x2 < 2400E (0,0)

region D (450,0)
X1
600 800
x1
400 600 800
245 246
•To determine the value for x1 and x2 at the optimal point, the two equations
of the binding constraint must be solved.
By Compensation on :
The plastic constraint: Max 8x1 + 5x2
2x1+x2 < 1200 (x1, x2) Objective fn
2x1+x2=1200
3x1+4x2=2400
x1= 480
(0,0) 0
x2= 240
(450, 0) 3600
(480, 240) 5040
Production Production mix (550, 100) 4900
Time constraint:
x1-x2 < 450 (0,600) 3000
3X1+4X2 < 2400
The maximum profit (5040) will be by producing:
Space Rays = 480 dozens, Zappers = 240 dozens
2X1+X2=1200
X1-X2=450 x1= 550
x2= 100 EE 477 Dr. Mohamed Zribi
247 248
X2
It could be find the range of optimality for an
1200
The plastic constraint:
2x1+x2
The < 1200
Plastic constraint objectives function coefficient by determining the
Total production constraint: range of values that gives a slope of the objective
x1+x2 < 800
function line between the slopes of the binding
600
Production Infeasible
Time
constraints.
Production mix
3x1+4x < 2400
constraint:
(200, 200) (550,100)
x1-x2 < 450
* (300,0) *
*
X1
600 800
Extreme
Interior
Boundary point
point EE 477 Dr. Mohamed Zribi
point EE 477 Dr. Mohamed Zribi
249 250
The binding constraints are: To find the range of optimality for Space Rays, and
2x1 + x2 = 1200 coefficient per dozen Zappers is c2= 5
3x1 + 4x2 = 2400

Thus the slope of the objective function line can be
The slopes are: -2/1, and -3/4 respectively. expressed as
–c1/5

251 252
Range optimality for Zapper, and coefficient per dozen space
rays is c1= 8
Range of optimality for C1 is found by sloving the
following for c1: Thus the slope of the objective function line can be expressed
-2/1 ≤ -c1/5 ≤ -3/4 as
–8/c2
3.75 ≤ c1≤ 10
Range of optimality for C2 is found by sloving the
following for C2:
-2/1 ≤ -8/c2 ≤ -3/4
4 ≤ c2≤ 10.667

253 254

Maximize 3x 2y
Subject to x 3y 12
x y 8
y y
2x y 10 Maximize 3x 2y
x 0 8 8
Subject to x 3y 12
y 0 7 7
x y 8
6 6
2x y 10
5 5
x 0
4 y 0 4
3 3
Nonempty
2 feasible region 2
1 1
EE 477 Dr. Mohamed Zribi x EE 477 Dr. Mohamed Zribi x
1 2 3 4 5 6 7 8 255 1 2 3 4 5 6 7 8 256
Example 56:
y
max z = 15 x + 10y
s.t. 2x + y ≤ 1500 y≥ 0
y x + y ≤ 1200 1500
Maximize 3x 2y Optimum x ≤ 500
8 solution
Subject to x 3y 12
7
x ≥ 0, 1000
x y 8
6
y≥0
2x y 10 500
5
x≥ 0
x 0
y 0 4
x
3 Feasible set (0,0) 500 1000 1500
x + y ≤ 1200
2
1
*(6, 2) x ≤ 500
EE 477 Dr. Mohamed Zribi x EE 477 Dr. Mohamed Zribi

2x+y ≤ 1500
1 2 3 4 5 6 7 8 257 258
Solution: Example 57:

max z = 15 x + 10y
ST 2x + y ≤ 1500
x + y ≤ 1200
y
x ≤ 500 15x + 10y = 5000
Solve the following problem:
x ≥ 0, y≥ 0 Maximize Z 5 x1 4 x2
y≥0 1500
15x + 10y = 13,500 subject to 3 x1 2 x2 60
1000 (300, 900)
1x1 2 x2 40
15x + 10y = 0
x1 0, x2 0
500 x≥ 0
Try point: x = 0, y = 0:
x
Feasible set (0,0) 500 1000 1500
x + y ≤ 1200
x ≤ 500
2x+y ≤ 1500
259 260
:
maximize Z = 4x1 + 5x2
subject to
x1 + 2x2 10
6x1 + 6x2 36
x1 4
x1,x2 0
We obtain x1 * 10, x2 * 15. The optimal value of the objective function

Figure The constraint equations
is Z ( x*) 5(10) 4(15) 110.

262
261 262

subject to
subject to
x1 + 2x2 1
x1 + 2x2 10
6x1 + 6x2 36
6x1 + 6x2 36
x1 4
x1 4
x1,x2 0
x1,x2 0
Figure The feasible solution space and extreme points Figure Optimal solution point

263 264
Solution:
Example 59: Let the company produce x1 type I motors and x2 type II
Electra produces two types of electric motors, each on a motors per day.
separate assembly line. The respective daily capacities of the The objective is to find x1 and x2 so as to
two lines are 150 and 200 motors. Type I motor uses 2 units
Maximize the profit z 8 x1 5 x2
of a certain electronic component, and type II motor uses
only 1 unit. The supplier of the component can provide 400
Subject to the constraints
pieces a day. The profits per motor of types I and II are $8 x1 150
and $5 respectively. Formulate the problem as a LPP and find x2 200
the optimal daily production. 2 x1 x2 400
x1 , x2 0
265 266
Example 60:
x2
Maximize z=8x1+5x2
Maximize z = 2x1 + x2
Subject to
2x1+x2 400
Optimum =1800 Subject to x1 + x2 ≤ 40
x1 150
at (100,200) 4 x1 + x2 ≤ 100
(0,200) x2 200
x1, x2 ≥ 0
z=1200
x1,x2 0
(150,100)
z=1800
z=1000

x1 EE 477 Dr. Mohamed Zribi
z=400 (150,0) z=1700 267 268
Maximize z = 2x1 + x2
Optimum = 60 at (20, 20) Subject to: x2 10
2 x1 5 x2 60
(0,40)
z maximum at x1 x2 18
(20,20)
3 x1 x2 44
x1 , x2 0
(25,0)
269 270
Solution:
Example 62:
Find the maximum value of z = 3x + 2y subject to the
z is maximum at (13, 5) constraints listed below
x 0
Max z = 31 y 0
x 2y 4
x y 1
Solution:
z = 28 At (0, 0): z = 3(0) + 2(0) = 0
(5,10)
At (1, 0): z = 3(1) + 2(0) = 3
(0,10) (10,8) [1] At (2, 1): z = 3(2) + 2(1) = 8 (maximum value of z)
z = 20 (13,5) At (0, 2): z = 3(0) + 2(2) = 4
z = 10 z = 31
※ Try testing some interior points in the
(14.6,0) region. You will see that corresponding
EE 477 Dr. Mohamed Zribi [2] EE 477 Dr. Mohamed Zribi
value of z are less than 8
z=4 [4] [3] 271 272
Why the maximum value of the objective function must occur
Example 63:
at a vertex? Solving a linear programming problem
Consider to rewrite the objective function in the form Find the maximum value of z = 4x + 6y, where x 0 and y
0, subject to the constraints
3 z x y 11
y x
2 2 x y 27
Sol: 2 x 5 y 90
※ First, the above equation represents a
family of parallel lines given different At (0, 0): z = 4(0) + 6(0) = 0
values of z, each of slope to be –3/2 At (0, 11): z = 4(1) + 6(11) = 66
※ Second, if you want to find the
At (5, 16): z = 4(5) + 6(16) = 116
maximum value of z for the shaded
region, it is equivalent to find the line At (15, 12): z = 4(15) + 6(12) = 132
with the largest y-intercept At (27, 0): z = 4(27) + 6(0) = 108
※ Finally, it is clear that such a line will
So the maximum value of z is 132, and
EE 477 pass Zribi
Dr. Mohamed through one (or more) of the
this occurs when x = 15 and y = 12
vertexes of the region 273
274
Example 64:
Solution:
Find the minimum value of the objective function
z = 5x + 7y, At (0, 2): z = 5(0) + 7(2) = 14
where x 0 and y 0, subject to the constraints At (0, 4): z = 5(0) + 7(4) = 28
2x 3 6 At (1, 5): z = 5(1) + 7(5) = 40
3 x y 15 At (6, 3): z = 5(6) + 7(3) = 51
At (5, 0): z = 5(5) + 7(0) = 25
x y 4
At (3, 0): z = 5(3) + 7(0) = 15
2x 5 y 27
So the minimum value of z is 14, and
this occurs when x = 0 and y = 2

275 276
The liquid portion of a diet is to provide at least 300 calories, 36
The maximum (or minimum) value occurs at two different vertexes
units of vitamin A, and 90 units of vitamin C daily. A cup of
To maximize the objective function z = 2x + 2y given the
following shaded region dietary drink X provides 60 calories, 12 units of vitamin A, and 10
units of vitamin C. A cup of dietary drink Y provides 60 calories,
At (0, 0): z = 2(0) + 2(0) = 0 6 units of vitamin A, and 30 units of vitamin C.
At (0, 4): z = 2(0) + 2(4) = 8
At (2, 4): z = 2(2) + 2(4) = 12 (maximum value of z) Now suppose the dietary drink X cost $.12 per cup and
At (5, 1): z = 2(5) + 2(1) = 12 (maximum value of z) drink Y costs $.15 per cup. How many cups of each drink should
At (5, 0): z = 2(5) + 2(0) = 10
be consumed each day to minimize the cost and still meet the
The maximum value occurs not only at the
vertexes (2, 4) and (5,1), but also occurs at stated daily requirements?
any point on the line segment connecting
these two vertexes EE 477 Dr. Mohamed Zribi
277 278

For calories: 60 x 60 y 300
For vitamin A: 12 x 6 y 36
For vitamin C: 10 x 30 y 90 constraints
x 0 …..Eq (4)
y 0
The cost C : C 0.12 x 0.15 y objective function
At (0, 6): C = 0.12(0) + 0.15(6) = 0.90

At (1, 4): C = 0.12(1) + 0.15(4) = 0.72
At (3, 2): C = 0.12(3) + 0.15(2) = 0.66
At (9, 0): C = 0.12(9) + 0.15(0) = 1.08
So the minimum cost is $.66 per day, and this
occurs when three cups of drink X and two EE 477 Dr. Mohamed Zribi
cups of drink Y are consumed each day 279 280
Solution:
• An equation of the form 4x1 + 5x2 = 1500 defines a straight line in
the x1-x2 plane. An inequality defines an area bounded by a straight
line. Therefore, the region below and including the line 4x1 + 5x2 =
1500 in the Figure represents the region defined by 4x1 + 5x2
1500.
• Same thing applies to other equations as well.
• The shaded area of the figure comprises the area common to all the
regions defined by the constraints and contains all pairs of xI and x2
that are feasible solutions to the problem.
• This area is known as the feasible region or feasible solution space.
The optimal solution must lie within this region.
• There are various pairs of x1 and x2 that satisfy the constraints such
as:

281 282
• Trying different solutions, the optimal solution will be: • If the objective function happens to be parallel to one of the
x1 = 270 edges of the feasible region, any point along this edge
between the two extreme points may be an optimal solution
x2 = 75 that maximizes the objective function. When this occurs, there
• This indicates that maximum income of $4335 is obtained by is no unique solution, but there is an infinite number of
producing 270 units of product I and 75 units of product II. optimal solutions.
• In this solution, all the raw material and available time are used,
because the optimal point lies on the two constraint lines for these
resources. • The graphical method of solution may be extended to a case
in which there are three variables. In this case, each constraint
• However, 1500- [4(270) + 5(75)], or 45 ft2 of storage space, is not
is represented by a plane in three dimensions, and the feasible
used. Thus the storage space is not a constraint on the optimal
solution; that is, more products could be produced before the
region bounded by these planes is a polyhedron.
company ran out of storage space. Thus this constraint is said to be
slack.
283 284
Example 68: The Reddy Mikks Problem
A market survey has established that the daily demand for the
The Reddy Mikks company owns a small paint factory that produces interior paint cannot exceed that of exterior paint by more than
both interior and exterior house paints for wholesale distribution.
1 ton. The survey also showed that the maximum demand for
Two basic raw materials, A and B, are used to manufacture the
paints. the interior paint is limited to 2 tons daily.
The maximum availability of A is 6 tons a day; that of B is 8 tons a
day. The daily requirements of the raw materials per ton of interior
The wholesale price per ton is $3000 for exterior paint and
and exterior paints are summarized in the following table.
$2000 per interior paint. How much interior and exterior paint
Tons of Raw Material per Ton of Paint
Raw Material A
Exterior
1
Interior
2
Maximum Availability (tons)
6
should the company produce daily to maximize gross income?
Raw Material B 2 1 8

285 286
Solution:
Define:
A solution is any specification of
XE = Tons of exterior paint to be produced values for the decision variables.
XI = Tons of interior paint to be produced Constraint 2: 2XE + XI 8
A feasible Solution is a solution
Constraint 3: -XE + XI 1 for which all the constraints are
I
satisfied.
Thus, the LP formulation of the Reddy-Mikks Company is as follows:
The feasible region is the set of
all feasible solutions.
Maximize z = 3XE + 2XI Notice that the feasible region is
Constraint 4: XI 2 convex
Subject to:
XE + 2XI 6 (1) (availability of raw material A)
2XE + XI 8 (2) (availability of raw material B) Constraint 1: XE + 2XI 6
-XE + XI 1 (3) (Restriction in production) Feasible

Region
XI 2 (4) (Demand Restriction)
XE , XI 0 1 2 3 4 5 6 7 E
EE 477 Dr. Mohamed Zribi 0 + 2(0) 6 EE 477 Dr. Mohamed Zribi
287 288
Graphical Solution of the Ready Mikks Example 69: A Maximization Model Example
Problem
Max z = 3XE + 2XI
Product mix problem - Beaver Creek Pottery Company
I Z= 9 Z = 12 An Optimal Solution is a
feasible solution that has How many bowls and mugs should be produced to maximize
the most favorable value of
the objective function.
profits given labor and materials constraints?
Z = 12.66 Product resource requirements and unit profit:
Point 2:
XE =4/3, Resource Requirements
XI = 1 Product Labor Clay Profit
Z=6 Point: XE =3.33, XI = 1.33
(How can we get this point?) (hr/unit) (lb/unit) ($/unit)
Bowl 1 4 40
Mug 2 3 50
1 2 3 4 5 6 7 E
Point 1: XE =2, XI = 0: Z = 6 EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi
289 290
Resource availability:
40 hours of labor per day Resource Constraints:
120 pounds of clay 1x1 + 2x2 40 hours of labor
Decision Variables:
x1=number of bowls to Non-negativity Constraints:
produce/day x1 0; x2 0
x2= number of mugs to Complete Linear Programming Model:
produce/day maximize Z=$40x1 + 50x2
subject to
Objective function 1x1 + 2x2 40
maximize Z = $40x1 + 50x2 4x2 + 3x2 120
where Z= profit per day xEE1477
, x2Dr. Mohamed
0 Zribi
291 292
Feasible/Infeasible Solutions Slack Variables
A feasible solution does not violate any of the constraints:
Example x1= 5 bowls Standard form requires that all constraints be in the form of
x2= 10 mugs equations.
Z = $40 x1 + 50x2= $700
Labor constraint check:
1(5) + 2(10) = 25 < 40 hours, within constraint A slack variable is added to a constraint to convert it to an
Clay constraint check: equation (=).
4(5) + 3(10) = 70 < 120 pounds, within constraint
An infeasible solution violates at least one of the constraints: A slack variable represents unused resources.
Example x1 = 10 bowls
x2 = 20 mugs
A slack variable contributes nothing to the objective function
Z = $1400
value.
Labor constraint check:
1(10) + 2(20) = 50 > 40 hours, violates constraint
293 294
Example 70:
The owner of Black Angus Ranch of Australia is trying to determine the correct
mix of two types of beef feed, A and B, which cost 50 cents and 75 cents per.
maximize Z=40x1 + 50x2 + 0s1 + 0s2
subject to pound, respectively. Five essential ingredients are contained in the feed, as
1x1 + 2x2 + s1 = 40 shown in the table below, which also indicates the minimum daily requirements
4x2 + 3x2 + s2 = 120 of each ingredient:
x1,x2,s1,s2 = 0
where x1 = number of bowls
x2 = number of mugs Ingredient Feed A(%) Feed B (%) Min. Daily
s1, s2 are slack variables Requirement
1 .20 .25 30
2 .30 .10 50
3 0 .30 20
4 .24 .15 60
5 .10 .20 40
Figure Solutions at points A, B, and C with slack
Find the least-cost daily blend for the ranch; that is, how many pounds of deed A and feed B will be
included in the mix? (Solve graphically). EE 477 Dr. Mohamed Zribi
295 296
Solution: Minimum ingredient
Requirement Coef.:
Two decision variables: how much of each
type to be mixed? Percentage in
Ingrel. A B Min. requmt
Let: 1 20% 25% 30
x1-amount of type A to be mixed.
2 30% 10% 50
x2-amount of type B to be mixed.
Objective Function:
3 0% 30% 20
Minimize - Total cost. Given: 4 24% 15% 60
C1 = 50, C2 = 75 5 10% 20% 40
297 298
.
Formulation:
A
Objective function Min z = 50x1+75x2 500
0.30x1+0.10x2≥50
Sub. to: 400
0.24x1+0.15x2≥60
0.20x1+0.25x2 ≥ 30
300
0.30x1+0.10x2 ≥ 50 B
0.30x2 ≥ 20 200 Optimal solution(181.80,109.10)

0.24x1+0.15x2 ≥ 60 C
100 D 0.30x2≥20
0.10x1+0.20x2 ≥ 40
0.20x1+0.25x2≥30 0.10x1+0.20x2≥40
x1, x2 ≥ 0
0 100 200 300 400 500
299 300
Example 71: For the current production period RMC has available the
following quantities of each raw material. Because of spoilage,
Problem Description
any material not used for current production must be discarded.
RMC, Inc. is a firm that produces chemical-based products. In a
particular process three raw materials are used to produce two Amount Available for Production
products. The material requirements per ton are shown below. Material 1 20 tons
Material 2 5 tons
Product Material 1 Material 2 Material 3
Material 3 21 tons
Fuel additive 2/5 0 3/5 If the contribution to profit is $40 for each ton of fuel additive
and $30 for each ton of solvent base, how many tons of each
Solvent base 1/2 1/5 3/10 product should be produced in order to maximize profit?

301 302
Solution: The Constraints:

Let
x1 = the number of tons of fuel that RCM produces
Since there are limited amounts of three raw materials available, we have
x2 = the number of tons of solvent base that RMC produces three constraints that limit the amount of fuel additive and solvent base
RMC’s profit will come from two resources that RMC can produce.
1. From producing x1 tons of fuel additive Let us consider the constraint involving material 1
2. From producing x2 tons of solvent base Total tons of material 1 required is:
Therefore 2/5 x1 + ½ x2
Total Profit = 40x1 + 30 x2 Total tons of material 1 available: 20 tons
We say that RMC’s objective is to maximize the value of its objective function. Therefore, for a production combination to be feasible, the production
Using max as an abbreviation for maximize, the objective function is written combination we select must satisfy the requirement
as follows: 2/5 x1 + ½ x2 ≤ 20
Max 40x1 + 30 x2
303 304
The Constraints:
The mathematical statement or formulation of the RMC
Similarly, the constrain for material 2 is problem is now complete. The mathematical model we
1/5 x2 ≤ 5 developed can be written as follows:
Max 40x1 + 30 x2
The constraint for material 3 is Subject to (s.t.)
3/5 x1 + 3/10 x2 ≤ 21 2/5 x1 + ½ x2 ≤ 20 Material 1
1/5 x2 ≤5 Material 2
3/5 x1 + 3/10 x2 ≤ 21 Material 3
Finally, since the decision variables can not be negative, we add non- x1, x2 ≥ 0
negativity constraints
x1 ≥ 0 and x2 ≥ 0 (Now, let’s look for a graphical solution.)

305 306

307 308
Example 72:
Nitron Carp. of Canada produces two products. Unit profit for
product A is $60; for product B, $50. Each must pass through two
machines, P and Q. Product A requires 10 minutes on machine P
and 8 minutes oil machine Q. Product B requires 20 minutes on
machine P and 5 minutes on machine Q. Machine P is available 200
minutes a day, while machine Q is available 80 minutes a day. The
company must produce at least two units of product A and five of
product B each day. Units that are not completed in a given day are
finished the next day; that is, a portion of a product can be produced
in the daily plan. What is the most profitable daily production plan?
a. Formulate.
b. Solve graphically (specifically show all constraints and the
objective function as well as the optimal solution).
c. How should the resources be allocated'

309 310
Solution:
Two decision variables:

Set:
Constraints:
x1-number of product-A to be produced
x2-number of product-B to be produced A B Total
M-P: 10(min) 20 200
Given: Profit Coefficients C1=60 C2=50 M-Q: 8 5 80
Resource Coefficients: Machine-P: 200 min. Minimum requite: A ≥ 2

Machine-Q: 80 min.
B≥5
311 312
Formulation: (a) Max. Z= 60x1+50x2
Objective Function Max: Z=60x1+50x2 s.t. 10x1+20x2 ≤ 200 (machine P)
8x1+5x2 ≤ 80 (machine Q)
Sub to: 10x1+20x2 ≤ 200 x1 ≥ 2
8x1+5x2 ≤ 80
x2 ≥ 5
x1 ≥ 2
x2 ≥ 5
x1, x2≥0

313 314
A simple product-mix problem
The time on machine P is:

The graphical solution is: 10(5.45)+20(7.27)=200;
x2 x1≥2 (i.e., it is fully utilized.)
The optimal point is:
x1=5.45, x2=7.27, z=690.9
The time on machine Q is:
15 8(5.45)+5(7.27)=80;
8x1+5x2≤80 (i.e., the machine Q is fully utilized.)
10
Optimal solution(x1=5.45,x2=7.27) x1 and x2 are produced above the minimum requirements.
10x1+20x2≤200 x1 = 5.45 instead of 2
x2≥5 x2 = 7.27 instead of 5
5
Objective function
5 10 15 20 x1 315 316
Example 73: Giapetto’s Woodcarving
Each week Giapetto can obtain:
Giapetto’s, Inc., manufactures wooden soldiers and trains. – All needed raw material.
– Each soldier built:
– Only 100 finishing hours.
• Sell for $27 and uses $10 worth of raw materials.
• Increase Giapetto’s variable labor/overhead costs by $14. – Only 80 carpentry hours.
• Requires 2 hours of finishing labor. Demand for the trains is unlimited.
• Requires 1 hour of carpentry labor.
At most 40 soldiers are bought each week.
– Each train built:
• Sell for $21 and used $9 worth of raw materials. Giapetto wants to maximize weekly profit (revenues – costs).
• Increases Giapetto’s variable labor/overhead costs by $10. Formulate a mathematical model of Giapetto’s situation that can be
• Requires 1 hour of finishing labor. used to maximize weekly profit.
• Requires 1 hour of carpentry labor.

317 318
Solution:
Giapetto’s weekly profit can be expressed in terms of the decision
The Giapetto solution model incorporates the characteristics shared
variables x1 and x2:
by all linear programming problems.
Weekly profit =
– Decision variables should completely describe the decisions to
weekly revenue – weekly raw material costs – the weekly
be made.
variable costs = 3x1 + 2x2
• x1 = number of soldiers produced each week
• x2 = number of trains produced each week Thus, Giapetto’s objective is to chose x1 and x2 to maximize
– The decision maker wants to maximize (usually revenue or weekly profit. The variable z denotes the objective function value
profit) or minimize (usually costs) some function of the of any LP.
decision variables. This function to maximized or minimized is Giapetto’s objective function is
called the objective function. Maximize z = 3x1 + 2x2
• For the Giapetto problem, fixed costs do not depend upon
The coefficient of an objective function variable is called an
the the values of x1 or x2.
objective function coefficient. EE 477 Dr. Mohamed Zribi
319 320
As x1 and x2 increase, Giapetto’s objective function grows larger. The coefficients of the decision variables in the constraints are
called the technological coefficients. The number on the right-
For Giapetto, the values of x1 and x2 are limited by the following hand side of each constraint is called the constraint’s right-hand
three restrictions (often called constraints): side (or rhs).
To complete the formulation of a linear programming problem,
– Each week, no more than 100 hours of finishing time may be
the following question must be answered for each decision
used. (2 x1 + x2 ≤ 100) variable.
– Each week, no more than 80 hours of carpentry time may be – Can the decision variable only assume nonnegative values,
used. (x1 + x2 ≤ 80) or is the decision variable allowed to assume both positive
and negative values?
– Because of limited demand, at most 40 soldiers should be • If the decision variable can assume only nonnegative
produced. (x1 ≤ 40) values, the sign restriction xi ≥ 0 is added.
• If the variable can assume both positive and negative
values, the decision variable xi is unrestricted in sign
(often abbreviated urs).
321 322
For the Giapetto problem model, combining the sign restrictions x1 Since the Giapetto LP has two variables, it may be solved
≥ 0 and x2 ≥ 0 with the objective function and constraints yields the graphically.
following optimization model: The feasible region is the set of all points satisfying the
constraints
2 x1 + x2 ≤ 100 (finishing constraint)
Max z = 3x1 + 2x2 (objective function)
x1 + x2 ≤ 80 (carpentry constraint)
Subject to (s.t.) x1 ≤ 40 (demand constraint)
2 x1 + x2 ≤ 100 (finishing constraint) x1 ≥ 0 (sign restriction)
x1 + x2 ≤ 80 (carpentry constraint) x2 ≥ 0 (sign restriction)
x1 ≤ 40 (constraint on demand for soldiers)
x1 ≥0 (sign restriction)
x2 ≥ 0 (sign restriction)
323 324
The set of points satisfying the Giapetto LP is bounded by
the five sided polygon DGFEH. Any point on or in the Having identified the feasible region for the Giapetto LP,
interior of this polygon (the shade area) is in the feasible a search can begin for the optimal solution which will be
region. the point in the feasible region with the largest z-value.
To find the optimal solution, graph a line on which the
X2
B
points have the same z-value. In a max problem, such a
100
finishing constraint Feasible Region
line is called an isoprofit line while in a min problem,

D
80
demand constraint
this is called the isocost line. The figure shows the

60
z = 100
40
carpentry constraint
isoprofit lines for z = 60, z = 100, and z = 180

20
F
z = 180
z = 60
E A C
H
10 20 40 50 60 80 X1

325 326
Example 74:
A constraint is binding if the left-hand and right-hand side of
the constraint are equal when the optimal values of the decision
variables are substituted into the constraint. RESOURCE REQUIREMENTS
– In the Giapetto LP, the finishing and carpentry Labor Clay Revenue
PRODUCT (hr/unit) (lb/unit) ($/unit)
constraints are binding. Bowl 1 4 40
A constraint is nonbinding if the left-hand side and the right- Mug 2 3 50
hand side of the constraint are unequal when the optimal

There are 40 hours of labor and 120 pounds of clay available
values of the decision variables are substituted into the each day
constraint. Solution:
Decision variables
– In the Giapetto LP, the demand constraint for wooden x1 = number of bowls to produce
soldiers is nonbinding since at the optimal solution x2 = number of mugs to produce
(x1 = 20), x1 < 40. EE 477 Dr. Mohamed Zribi

327 328
Maximize Z = $40 x1 + 50 x2 x2
50 –
Subject to: 40 –
x1 + 2x2 40 hr (labor constraint) 4 x1 + 3 x2 120 lb
4x1 + 3x2 120 lb (clay constraint) 30 –

x1 , x2 0
20 – Area common to
both constraints
Solution is x1 = 24 bowls x2 = 8 mugs
10 – x1 + 2 x2 40 hr
Revenue = $1,360 0– | | | | | |
10 20 30 40 50 60 x1
329 330
x1 + 2x2 = 40
x2
4x1 + 3x2 = 120
40 – 4 x + 3 x 120 lb 4x1 + 8x2 = 160
x1 = 0 bowls
1 2
-4x1 - 3x2 = -120 x2 x2 = 20 mugs
x1 = 224 bowls
30 – 5x2 = 40 Z = $1,000
40 – x2 = 8 mugs
x2 = 8 x1 = 30 bowls
Z = $1,360
20 – 30 – x2 = 0 mugs
x1 + 2 x2 40 hr x1 + 2(8) = 40
20 – A
Z = $1,200
x1 = 24
10 –
8 10 –
x1 B
0– | | 24 | |
0– | | | C|
10 20 30 40 10 20 30 40 x1
Z = $50(24) + $50(8) = $1,360
331 332
Example 75:
x2
40 –
4x1 + 3x2 120 lb
CHEMICAL CONTRIBUTION
Z = 70x1 + 20x2 Brand Nitrogen (lb/bag) Phosphate (lb/bag)

30 –
Optimal point: Gro-plus 2 4
x1 = 30 bowls Crop-fast 4 3
20 –A x2 = 0 mugs
Z = $2,100 Minimize Z = $6x1 + $3x2
10 – B subject to
2x1 + 4x2 16 lb of nitrogen
x1 + 2x2 40 hr
4x1 + 3x2 24 lb of phosphate
0– | | | C |
10 20 EE 477 30 40 x1, x2 0
Dr. Mohamed Zribi x1
333 334
x2
14 –
x1 = 0 bags of Gro-plus
12 – x2 = 8 bags of Crop-fast
Z = $24
10 –
8–A Z = 6x1 + 3x2

Solution Points
6– with
4–
Surplus Variables
B
2–
C
0– | | | | | | |
2 4EE 477 6Dr. Mohamed
8 Zribi
10 12 14 x1
335 336
Example 76:
To get the answer, we need to collect the following data.
The Wyndor Glass Co. produces high-quality glass products, including windows and glass
doors. It has three plants.
(a) Number of hours of production time available per week in each plant for these
Plant 1 produces Aluminum frames
Plant 2 produces wood frames two new products. (Most of the time in the 3 plants is already committed to current
Plant 3 produces the glass and assembles the products. products, so the available capacity for the 2 new products is quite limited).
The company has decided to produce two new products.
Product 1: An 8-foot glass door with aluminum framing Number of hours of production time available per week in Plant 1 for the new
Product 2: A 4x6 foot double-hung wood framed window products: 4
Each product will be produced in batches of 20. The production rate is defined as the Number of hours of production time available per week in Plant 2 for the new
number of batches produced per week.
products: 12
The company wants to know what the production rate should be in order to maximize Number of hours of production time available per week in Plant 3 for the new
their total profit, subject to the restriction imposed by the limited production capacities
available in the 3 plants. products: 18

337 338
(c) Profit per batch produced of each new product.

(b) Number of hours of production time used in each plant for each batch
produced of each new product (Product 1 requires some of the production
capacity in Plants 1 and 3, but none in Plant 2. Product 2 needs only Plants Profit per batch produced of Product 1: $3,000
2 and 3). Profit per batch produced of Product 2: $5,000
Number of hours of production time used in Plant 1 for each batch produced of
Product 1: 1
Number of hours of production time used in Plant 2 for each batch produced of The data collected are summarized in Table 3.1.
Product 1: 0 This is a linear programming problem of the classic product mix type.
Product 1: 3
Product 2: 0
Product 2: 2
Product 2: 2

339 340
Solution: Formulation as a Linear Programming Problem
To formulate the LP model for this problem, let
x1 = number of batches of product 1 produced per week

x2 = number of batches of product 2 produced per week
Z = total profit ( in thousands of dollars) from producing the two new products.
Thus, x1 and x2 are the decision variables for the model. Using the data of Table
3.1, we obtain
(Plant 1:Total production time required) (Production time available)


341 342
(4) Graphical Solution

The Wyndor Glass Co. example is used to illustrate the graphical solution.
Shaded area shows values of (x1, x2) Shaded area shows values of (x1, x2) , The value of (x1, x2) that maximize 3x1 + 5x2 is (2, 6)
allowed by x1 ≥ 0, x2 ≥ 0, x1 ≤ 4 EE 477 Dr. Mohamed Zribicalled
feasible region EE 477 Dr. Mohamed Zribi
343 344
Special Cases
So far, our models have had

– One optimal solution and an finite objective
10. Special Cases of value
Does this always happen?

LP Solutions
What if it doesn’t?

345 346
Solution(s) of Linear Programs Special Cases

Usually an LP problem will have a unique optimal
An LP has a unique optimal solution, or…..
solution. But there are problems where there may be no
It has infinite number of optimal solutions, or….. solution, may have alternative optimum solutions and
may have “unbounded” solutions.
It is unbounded, or…..
It is infeasible.
We note that the (unique) optimum solution occurs at
one of the “corners” of the set of all feasible points.
347 348
Special Cases Special Case #1: Infinite Number of Optimal Solutions
• Some LPs have an infinite number of solutions (alternative or

multiple optimal solutions). Infinite Number of Optimal Solutions occur when the
objective function (isoprofit/isocost line) lie intersects an
• Some LPs have no feasible solution (infeasible LPs). entire line segment corresponding to a binding constraint.
• Some LPs are unbounded: There are points in the feasible Infinite Number of Optimal Solutions occur when
region with arbitrarily large z-values (in a maximization isoprofit/isocost line is parallel to one of the binding
problem) or arbitrarily small z-values (in a minimization constraints.
problem).
349 350
Example 77: Infinite Number of Optimal Solutions Example 78: Infinite Number of Optimal Solutions
X2
B
60
D
Any point (solution)
50
Feasible Region
falling on line segment
40
AE will yield an optimal
solution with the same E
30
objective value z = 100
z = 120
20
z = 60
10
F
A C
10 20 30 40 50 X1

351 352
Example 79: Infinite Number of Optimal Solutions Graphical solution
x2
Maximize z=10x1+5x2
Subject to:
Maximize z 10 x1 5 x2 2x1+x2 400
(100,200) x1 150
x1 150 (0,200)
Subject to: z maximum x2 200
x2 200 =2000 at
z=600 z=1500
2 x1 x2 400 (150,100) x1,x2 0
x1 , x2 0 z=2000
z=1000
x1
353
z=400 (150,0) EE 477 Dr. Mohamed Zribi
354
Example 80: Infinite Number of Optimal Solutions

Thus we see that the objective function z is maximum Maximize z x1 x2
at the corner (150, 200) and also has an alternative
Subject to:
optimum solution at the corner (100, 200). It may also
be noted that z is maximum at each point of the line x1 x2 6
segment joining them. Thus the problem has an infinite x1 2 x2 10
number of (finite) optimum solutions. This happens x1 , x 2 0
when the objective function is “parallel” to one of the
constraint equations.

355 356
Maximize z 2 x1 x2
Subject to:
(0,6) Optimal BFSs All points on this line segment x1 x2 10
(except the endpoints) are
(0,5) optimal feasible solutions. 2 x1 x2 40
(2,4)
x1 , x2 0
We shall solve this problem by the Simplex method.
(6,0) (10,0)
Note that the objective function line is parallel to the first constraint
line. EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi
357 358
Objective function is
(30,20) parallel to a constraint
line:
maximize Z=40x1 + 30x2
All points on this line from subject to
1x1 + 2x2 40
(30,20) onwards are 4x1 + 3x2 120
Optimal solutions. x1, x2 0

359 360
Example 83: Infinite Number of Optimal Solutions Example 84: Infinite Number of Optimal Solutions
Max z = 6 x1 4 x2
x1 4
s.t.
x2
z1 z2 z3
2 x2 12
Maximize z = 3x1 – x2
4
subject to 15x1 – 5x2 30
3 x1 2 x2 18
3
2
10x1 + 30x2 120 x1 0, x2 0
x1 0, x2 0
optimal solution is ( x1, x2) = ( , ),( , ),……..

1
0 Example with alternate optimal solutions

0 1 2 3 4 x1
optimal value is z =
361 362
Special Case # 2: Unbounded Linear Programs Example 85: Unbounded LP Problems
If maximizing: there are points in the feasible region Maximization Minimization
with arbitrarily large objective values.
If minimizing: there are points in the feasible region

with arbitrarily small objective values.

363 364
Example 86: Unbounded LP Problem Example 87: Unbounded LP Problem
X2
The constraints are Feasible Region
6 D
satisfied by all points
bounded by the x2 axis 5 B
and on or above AB and z=4
CD. 4
3
There are points in the
feasible region which 2
will produce arbitrarily
large z-values 1
z=6
(unbounded LP). A C
1 2 3 4 5 6 X1

365 366

Feasible
Max 2 x1 3 x2 region is
s.t. x1 4 x2 8 unbounded
Max z = 3x1 5x2
2 x1 x2 4 x2
x1 4
x1 , x2 0
No optimal solution s.t. x1 4
x1 0, x2 0
Feasible z 3x1 5 x2
region is
unbounded
No optimal solution (4,0) x1

367 368
Example 90: Unbounded LP Problem
x
Example 91: Unbounded LP Problem
2
Maximize z = x1 + x2 z=70 No optimal solution

Subject to
y
- x1 + 3 x2 ≥ 30 - 3 x1 z=50 Maximize 5x 4y 6
+ x2 ≤ 30 Subject to 3x 2y 12 5
x1, x2 ≥ 0 x 3y 3 4
x 0
z=30 3
y 0
2
z=20 1
An unbounded LP problem 2 1
0 x
unbounded solution x1
The feasible region is unbounded.
1 2 3 4 5 6
1
No optimal solution EE 477 Dr. Mohamed Zribi 2
369 370

Value of objective function Maximize z = –x1 + x2
increases indefinitely:
subject to –x1 + 4x2 10
–3x1 + 2x2 2
maximize Z = 4x1 + 2x2 x1 0, x2 0
subject to
x1 4 Bounded objective function with an unbounded
feasible region
z3
x2 2 x2
z2
x1, x2 0 4
z1
1 No optimal solution
0
0 1 2 3 4 x1
No optimal solution
371 372
To maximize the objective function z = 4x + 2y given the
following shaded region
For this unbounded region, there is no

maximum value of z. By choosing
points (x, 0) for x 4, you can obtain No optimal solution - Unbounded problems
values of z = 4(x) + 2(0) = 4x that are
as large as you want
No optimal solution
373 374
Special Case # 3: Infeasible Linear Program Example 96: Infeasible LP Problem

x 2
Maximize z = 5x1 + 7 x2
Feasible Region is empty Subject to

2 x1 - x2 ≤ -1
- x1 + 2 x2 ≤ -1
x 1, x 2 ≥ 0
No feasible solution
x1
375 376
Example 97: Infeasible LP Problem Example 98: Infeasible LP Problem
Min 2 x1 3x2 Max z = 3x1 5x2 x2

s.t. 3 x1 4 x2 12 s.t. x1 7
7 x1 6 x2 42
2 x2 12
x1 , x2 0
3 x1 2 x2 18
x1 0, x2 0
x1
infeasible No optimal solution!

377 378
Example 99: Infeasible LP Problem Example 100: Infeasible LP Problem
y
Min 2 x1 3x2 Maximize 5x 4y 6
s.t. 3 x1 4 x2 12 Subject to x y 2 5
7 x1 6 x2 42 x 2y 6 4 x 2y 6
x 0
x1 , x2 0 3
y 0
2
x y 2
1
An infeasible LP problem 2 1
Graphical Solution 0 x
1 2 3 4 5 6
The feasible region is empty 1
EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi 2
379 380
Example 101: Infeasible LP Problem Example 102: Infeasible LP Problems
x2 Maximize z = x1 + x2
subject to 3x1 + x2 6
Every possible solution 4

3 x1 + x2 3
3
violates at least one 2
x1 0, x2 0
constraint: 1
Inconsistent constraint system
0
1 2 3 4 x1
0

subject to x1 –4 –3 –2 –1 0
0 Maximize z = x1 + x2
4x1 + 2x2 8 –1 subject to x1 – 2x2 0
x1 4 –2 –x1 +x2 1
x2 6 –3 x1 0, x2 0
–4
x1, x2 0 Constraint system allowing only nonpositive values for x1 and x2
x2

381 382
Example 103: Infeasible LP Problem Example 104: Infeasible LP Problems
No point, simultaneously,
lies both above line 1 and
No optimal solution - Infeasible problems- below lines 2 and 3
2
.
EE 477 Dr. Mohamed Zribi 3 1 EE 477 Dr. Mohamed Zribi
383 384

Introduction To Linear Programming: EE 477 Optimization Techniques Fall 2017 Handout #4 Outline of The Handout

Uploaded by

Copyright:

Available Formats

Introduction To Linear Programming: EE 477 Optimization Techniques Fall 2017 Handout #4 Outline of The Handout

Uploaded by

Document Information

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

Introduction To Linear Programming: EE 477 Optimization Techniques Fall 2017 Handout #4 Outline of The Handout

Uploaded by

Copyright:

Available Formats

EE 477 Optimization Techniques Outline of the Handout

1. Introduction to Linear Programming

Fall 2017 2. Mathematical Background

3. Convex and Concave Functions

5. Convexity and Linear Programming

7. Common Terminology for LP Models

1. Introduction to Linear achieve a state goal of objectives.

Steps involved in mathematical programming

Programming – Conversion of stated problem into a mathematical model

– Exploration of different solutions of the problem.

– Finding out the most suitable or optimum solution.

of activity of a firm. widely used optimization problems.

Objective function: a linear mathematical relationship

Constraints: restrictions placed on the firm by the operating constraints.

environment stated in linear relationships of the decision

LP Applications Model of a Linear Program

Proportionality and Additive Assumptions Divisibility Assumption

1. The contribution of the objective function from each decision

Linear Programs Example 1: LP Examples

• Linear equations (equalities)

• Linear equations and linear inequalities are

4. Practical problems: 1000’s of variables software packages for solving LP problems.

5. Need Algebraic method !

Linear Programming Possible Outcomes of LP Problems

None of the variables are multiplied by another variable,

EE 477 Dr. Mohamed Zribi

Assumptions of the LP General Solution of LP Problems

Definitions Finding the Optimal Point

Background • Q is assumed to be symmetric.

• Otherwise, Q can be replaced with the symmetric matrix

(Q+QT)/2 without changing value of the quadratic form.

EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi

These n2 second partial derivatives are usually represented Example 6:

C. Positive/Negative Definite Matrices D. Tests of Positive Definite Matrices

• H(x) is negative definite if and only if xTHx < 0 for all x 0.

there exists and x 0 such that xTHx = 0. (test #2)

of H and its principal submatrices

EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi

Test #2 for Positive and Negative

EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi

EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi

If A is an n n triangular matrix, then its eigenvalues are the

Test #3 for Positive and Negative Tests

• There are 2n-1 principal determinants for an n x n matrix.

Example 11: Leading Principal Minors Example 12:

Leading principal minor of order 1 is 1. 2 0 4 x1

The number of leading principal determinants of an n x n matrix F is indefinite.

Convex function: A function is convex on set D

EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi

Concave Function 1D Convex and Concave Functions

It can be seen that a concave function bends downward and

It can be seen that the negative of a convex function is a

EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi

Example 15: Graph of a Strictly Concave Function

EE 477 Dr. Mohamed Zribi EE 477 Dr. Mohamed Zribi

A convex function is always bending upward and hence it is apparent that

Combinations of Convex Functions Test of Convexity of a Function

f ( x) 0 Determine whether the following function is convex or concave.

Hence H(x) will be negative semidefinite and f(x) is concave for x1 ≤ 0