8: Linear Programming

1
Content
• Introduction
• The Linear Programming Model
• Examples of Linear Programming Problems
• Developing Linear Programming Models
• Graphical Solution to LP Problems
• The Simplex Method
• Simplex Tableau for Maximization Problem
• Marginal Values of Additional Resources
• Sensitivity Analysis
• Complications in Applying the Simplex Method
• Duality
• Solving LP Problems Using the Big ‘M’ Method
• More Examples: Solving LP Problems
• Assignment 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 achieve a state goal of objectives.
• Steps involved in mathematical 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.

• Linear programming requires that all the mathematical

functions in the model be linear functions.
3
The Linear Programming Model (1)
Let: X1, X2, X3, ………, Xn = decision variables
Z = Objective function or linear function

Requirement: Maximization of the linear function

(Z).
Z = c1X1 + c2X2 + c3X3 + ………+ cnXn …..Eq (1)
subject to the following constraints:

…..Eq (2)

where aij, bi, and cj are given constants. 4

The Linear Programming Model (2)
• The linear programming model can be
written in more efficient notation as:

…..Eq (3)

The decision variables, xI, x2, ..., xn, represent levels of n

competing activities. 5
Examples of LP Problems (1)
1) A Product Mix Problem
• A producer has fixed amounts of different resources such
as raw material, labor, and equipment.
• These resources can be combined to produce any one of
several different products.
• The quantity of the ith resource required to produce one
unit of the jth product is known.
• The decision maker wishes to produce the combination of
products that will maximize total income.

6
Examples of LP Problems (2)
2) A Blending Problem
• Blending problems refer to situations in which a number
of components (or commodities) are mixed together to
yield one or more products.
• Typically, different commodities are to be purchased. Each
commodity has known characteristics and costs.
• The problem is to determine how much of each
commodity should be purchased and blended with the
rest so that the characteristics of the mixture lie within
specified bounds and the total cost is minimized.

7
 Examples of LP Problems (3)
3) A Production Scheduling Problem
• A producer knows that he/she must supply a given
number of items of a certain product each month for the
next n months.
• They can be produced either in regular time, subject to a
maximum each month, or in overtime. The cost of
producing an item during overtime is greater than during
regular time.
• A storage cost is associated with each item not sold at the
end of the month.
• The problem is to determine the production schedule that
minimizes the sum of production and storage costs.

8
Examples of LP Problems (4)
4) A Transportation Problem
• A product is to be shipped in the amounts al, a2, ...,
am from m shipping origins and received in amounts
bl, b2, ..., bn at each of n shipping destinations.
• The cost of shipping a unit from the ith origin to the jth
destination is known for all combinations of origins
and destinations.
• The problem is to determine the amount to be
shipped from each origin to each destination such
that the total cost of transportation is a minimum.

9
Examples of LP Problems (5)
5) A Flow Capacity Problem

• One or more commodities (e.g., traffic, water,

information, cash, etc.) are flowing from one point
to another through a network whose branches have
various constraints and flow capacities.
• The direction of flow in each branch and the
capacity of each branch are known.
• The problem is to determine the maximum flow, or
capacity of the network.

10
Developing LP Model (1)
• The variety of situations to which LP has been
applied ranges from agriculture to zinc smelting
(i.e., extracting zinc from its ore by a process
involving heating and melting).
• Steps Involved:
– Determine the objective of the problem and describe it by a
criterion function in terms of the decision variables.
– Find out the constraints.
– Do the analysis which should lead to the selection of values
for the decision variables that optimize the criterion function
while satisfying all the constraints imposed on the problem.

11
Developing LP Model (2)
Example: Product Mix Problem
The N. Dustrious Company produces two products (I and II). The
raw material requirements, space needed for storage, production
rates, and selling prices for these products are given in the
following Table.
Production data for N. Dustrious Company
Products
I II
Storage space (M2/unit) 4 5
Raw material (kg/unit) 5 3
Production rate (units/hr) 60 30
Selling price ($/unit) 13 11
The total amount of raw material available per day for both
products is 1,575kg. The total storage space for all products is 1,500
M2, and a maximum of 7 hours per day can be used for production.
12
Developing LP Model (3)
Example Problem
All products produced are shipped out of the storage area at the
end of the day. Therefore, the two products must share the total
raw material, storage space, and production time. The company
wants to determine how many units of each product to produce per
day to maximize its total income.
Solution
• The company has decided that it wants to maximize its sale
income, which depends on the number of units of product I and
II that it produces.
• Therefore, the decision variables, x1 and x2 can be the number of
units of products I and II, respectively, produced per day.

13
Developing LP Model (4)
• The object is to maximize the equation:
Z = 13x1 + 11x2
subject to the constraints on storage space, raw materials, and
production time

• Each unit of product I requires 4 M2 of storage space and each

unit of product II requires 5 M2. Thus a total of 4x1 + 5x2 M2 of
storage space is needed each day. This space must be less than
or equal to the available storage space, which is 1500 M2.
Therefore,
4X1 + 5X2 £ 1500
• Similarly, each unit of product I and II produced requires 5 and
3 kg, respectively, of raw material. Hence a total of 5xl + 3x2 kg
of raw material is used. 14
Developing LP Model (5)
• This must be less than or equal to the total amount of raw material
available, which is 1575 kg. Therefore,
5x1 + 3x2 £ 1575
• Product I can be produced at the rate of 60 units per hour. Therefore,
it must take 1 minute or 1/60 of an hour to produce 1 unit of product
I. Similarly, it requires 1/30 of an hour to produce 1 unit of product II.
Hence a total of x1/60 + x2/30 hours is required for the daily
production. This quantity must be less than or equal to the total
production time available each day. Therefore,
x1 x
+ 2 £ 7
60 30
x1 2x 2 • Finally, the company cannot produce a
+ £ 7
60 60 negative quantity of any product, therefore
x 1 + 2x 2 x1 and x2 must each be greater than or equal
£ 7
60 to zero.
x 1 + 2x 2 £ 7 * 60
x 1 + 2x 2 £ 4 20 15
Developing LP Model (6)
• The linear programming model for this example
can be summarized as:
Maximize
Z = 13x1 + 11x 2
Subject to:
4 x1 + 5 x2 £ 1,500
5x1 + 3x2 £ 1,575 …..Eq (4)

x1 + 2 x2 £ 420
x1 ³ 0
x2 ³ 0
16
Graphical Solution to LP Problems (1)
Z = 13x1 + 11x 2
Solve for values of x2 when x1 = 0; and x1 when x2 = 0
x1 = 0 x2 = 0
Constraints x2 = ? x1 = ?
Storage space 4x1 + 5x2 ≤ 1,500 300 375
Raw material 5x1 + 3x2 ≤ 1,575 525 315
Time x1+ 2x2 ≤ 420 210 420
Non Negativity x1, x2 ≥ 0

17
Graphical Solution to LP Problems (2)

18
Graphical Solution to LP Problems (3)
• An equation of the form 4x1 + 5x2 = 1,500 defines
a straight line in the x1-x2 plane.
• An inequality defines an area bounded by a
straight line.
• Therefore, the region below and the line 4x1 +
5x2 = 1,500 in the Figure represents the region
defined by this equation/line.
• Same thing applies to other equations as well.

19
Graphical Solution to LP Problems (4)
• 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:

20
Graphical Solution to LP Problems (5)
• Trying different solutions, the optimal solution will be:
X1 = 270 Z = 13x 1 + 11x 2
Z max = 13(270) + 11(75)
X2 = 75 = $4,335
• This indicates that maximum
income of $4,335 is obtained by
producing 270 units of product I
and 75 units of product II.

• 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. 21
Graphical Solution to LP Problems (6)
• However, 1,500- [4(270) + 5(75)] = 45
• That is, 45 M2 of storage space, is not used.
• Thus the storage space is not a constraint
on the optimal solution
• More products could be produced before
the company runs out of storage space.
• Thus this constraint is said to be slack.
22
Graphical Solution to LP Problems (7)
• If the objective function happens to be parallel to one
of the edges of the feasible region, any point along this
edge between the two extreme points may be an
optimal solution that maximizes the objective function.

• When this occurs, there is no unique solution, but

there is an infinite number of optimal solutions.

• The graphical method of solution may be extended to a

case in which there are three variables.

o In this case, each constraint is represented by a

plane in three dimensions, and the feasible region
bounded by these planes is a polyhedron. 23
The Simplex Method (1)
• When decision variables are more than 2, it is
always advisable to use Simplex Method to
avoid lengthy graphical procedure.

• The Simplex method is not used to examine all

the feasible solutions.

• It deals only with a small and unique set of

feasible solutions, the set of vertex points (i.e.,
extreme points) of the feasible space that
contains the optimal solution.
24
The Simplex Method (2)
Steps involved:
1. Locate an extreme point of the feasible region.
2. Examine each boundary edge intersecting at this point
to see whether movement along any edge increases
the value of the objective function.
3. If the value of the objective function increases along
any edge, move along this edge to the adjacent
extreme point. If several edges indicate improvement,
the edge providing the greatest rate of increase is
selected.
4. Repeat steps 2 and 3 until movement along any edge
no longer increases the value of the objective function.
25
The Simplex Method (3)
Example: Product Mix Problem
The N. Dustrious Company produces two products: I and II. The raw
material requirements, space needed for storage, production rates,
and selling prices for these products are given below:
Production data for N. Dustrious Company
Products
I II
Storage space (M2/unit) 4 5
Raw material (kg/unit) 5 3
Production rate (units/hr) 60 30
Selling price ($/unit) 13 11

The total amount of raw material available per day for both products
is 1,575kg. The total storage space for all products is 1,500 M2, and a
maximum of 7 hours per day can be used for production. The
company wants to determine how many units of each product to be
produced per day to maximize its total income. 26
The Simplex Method (4)
Solution
• Step 1: Convert all the inequality constraints into equalities
by the use of slack variables.
• Let: S1 = unused storage space; S2 = unused raw materials;
and S3 = unused production time
• The initial LP model:
Maximize Z = 13 x1 + 11 x 2

Subject to: 4 x1 + 5 x 2 £ 1,500 …..Eq (4)

5 x1 + 3x 2 £ 1,575
x1 + 2 x 2 £ 420
x1 ³ 0
x2 ³ 0 27
The Simplex Method (5)
• Introducing these slack variables into the inequality
constraints and rewriting the objective function such
that all variables are on the LHS of the equation.
Equation 4 can be expressed as:
Z - 13 x1 - 11x2 = 0.......... .......... ..(A1)
4 x1 + 5 x2 + S1 = 1,500 .......... .......(B1)
…..Eq (5)
5 x1 + 3 x2 + S 2 = 1,575 .......... .......(C1)
x1 + 2 x2 + S 3 = 420 .......... .......... .(D1)
xi ³ 0; i = 1,2

From the equations above, it is obvious that one feasible

solution that satisfies all the constraints is: x1 = 0; x2 = 0;
S1 = 1,500; S2 = 1,575; S3 = 420; and Z = 0 28
The Simplex Method (6)
• Since the coefficients of x1 and x2 in Eq. (A1) are both negative, the
value of Z can be increased by giving either x1 or x2 some positive
value in the solution.
• In Eq. (B1), if x2 = S1 = 0, then x1 = 1500/4 = 375. That is, there is
only sufficient storage space to produce 375 units at product I.
• From Eq. (C1), there is only sufficient raw materials to produce
1575/5 = 315 units of product I.
• From Eq. (D1), there is only sufficient time to produce 420/1 = 420
units of product I.
• Therefore, considering all three constraints, there is sufficient
resource to produce only 315 units of x1. Thus the maximum value
of x1 is limited by Eq. (C1) (raw materials).
29
The Simplex Method (7)
• Step 2: From Equation C1, which limits the maximum value of x1.

…..Eq (6)

Substituting this equation into Eq. (5) yields the following new
formulation of the model.

…..Eq (7)

30
The Simplex Method (8)
• It is now obvious from these equations that the new
feasible solution is:

x1 = 315, x2 = 0, S1 = 240, S2 = 0, S3 = 105, and Z = 4,095

• It is also obvious from Eq.(A2) that it is also not the

optimum solution

• Why? The coefficient of x1 in the objective function

represented by A2 is negative ( -16/5), which means
that the value of Z can be further increased by giving x2
some positive value.
31
The Simplex Method (9)
• Following the same analysis procedure used in step 1, it
is clear that:

In Eq. (B2), if S1 = S2 = 0, then x2 = (5/13)(240) = 92.3.

From Eq. (C2), x2 can take on the value (5/3 )(315) = 525,
if x1 = S2 = 0

From Eq. (D2), x2 can take on the value (5/7)(105) = 75, if

S2 = S3 = 0
• Therefore, constraint D2 (time) limits the maximum value
of x2 to 75. Thus a new feasible solution includes x2 = 75,
S2 = S3 = 0.
32
The Simplex Method (10)
Step 3: From Equation D2:

…..Eq (8)

Substituting this equation into Eq. (7) will yield:

…..Eq (9)

From these equations, the new feasible solution is readily found to

be: x1 = 270, x2 = 75, S1 = 45, S2 = 0, S3 = 0, Z = 4,335.
33
The Simplex Method (11)
• Because the coefficients in the objective
function represented by Eq. (A3) are all positive,
this new solution is also the optimum solution.

34
Simplex Tableau for Maximization

35
Simplex Tableau for Maximization (1)
Continue with the same LP model:
Maximize
Z = 13x1 - 11x2
Subject to:
4 x 1 + 5 x 2 £ 1 , 500
5 x 1 + 3 x 2 £ 1 , 575
x 1 + 2 x 2 £ 420
x1 , x 2 ³ 0

36
Simplex Tableau for Maximization (2)
Step I: Set up the initial tableau using Eq. (5). In any iteration, a variable
Z - 13 x1 - 11x2 = 0.......... .......( A1 ) that has a nonzero value in
4 x1 + 5 x2 + S1 = 1,500 .......... ...( B1 ) …..Eq (5) the solution is called a basic
variable.
5 x1 + 3 x2 + S 2 = 1,575 .......... ...(C1 )
x1 + 2 x2 + S 3 = 420 .......... .......( D1 ) In the Tableau:
Cj = Coefficient of objective function
xi ³ 0, i = 1,2
BV = Basic variables
Initial Tableau
Row Cj Coefficients of: RHS Upper Bound on Entering Variables
No. BV Z x1 x2 S1 S2 S3 (UBEV)

A1 Z 1 -13 -11 0 0 0 0
B1 S1 0 4 5 1 0 0 1,500 375 (x1, if x2= S1=0 in B1)=1500/4
C1 S2 0 5 3 0 1 0 1,575 315 (x1, if x2= S2=0 in C1)=1575/5
D1 S3 0 1 2 0 0 1 420 420 (x1, if x2= S3=0 in D1)=420/1

NOTE: Upper Bound on Entering Variables = the x1-intercepts of

corresponding constraints - see also the Simplex Method (6)
37
Simplex Tableau for Maximization (3)
• Step II: . Identify the variable that will be assigned a
nonzero value in the next iteration so as to increase the
value of the objective function. This variable is called the
entering variable.
o It is that nonbasic variable which is associated with the
smallest negative coefficient in the objective function.
o If two or more nonbasic variables are tied with the
smallest coefficients, select one of these arbitrarily and
continue.

38
Simplex Tableau for Maximization (4)
Initial Tableau

Row Cj Coefficients of: RHS Upper Bound

No. on Entering
Variables
BV Z x1 x2 S1 S2 S3
A1 Z 1 -13 -11 0 0 0 0
B1 S1 0 4 5 1 0 0 1,500 375
C1 S2 0 5 3 0 1 0 1,575 315
D1 S3 0 1 2 0 0 1 420 420

Shaded column = the key column

Row with the least positive solution = the key row

39
Simplex Tableau for Maximization (5)
• Step III: Identify the variable, called the leaving variable,
which will be changed from a nonzero to a zero value in the
next solution.
Initial Tableau
Row Cj Coefficients of: RHS Upper Bound
No. on Entering
Variables
BV Z x1 x2 S1 S2 S3
A1 Z 1 -13 -11 0 0 0 0
B1 S1 0 4 5 1 0 0 1,500 375
C1 S2 0 5 3 0 1 0 1,575 315
D1 S3 0 1 2 0 0 1 420 420
Entering variable = x1 Key column value (element) = -13
Leaving variable = S2 Key element (value) = 5
40
Simplex Tableau for Maximization (6)
• Step IV: . Enter the basic variables for the second tableau. The
row sequence of the previous tableau should be maintained,
with the leaving variable being replaced by the entering
variable. Initial tableau
Row Cj Coefficients of: RHS Upper Bound
No. on Entering
BV Z x1 x2 S1 S2 S3 Variables
A1 Z 1 -13 -11 0 0 0 0
B1 S1 0 4 5 1 0 0 1,500 375
C1 S2 0 5 3 0 1 0 1,575 315
D1 S3 0 1 2 0 0 1 420 420

Initial tableau
Row Cj Coefficients of: RHS Upper Bound
No. on Entering
BV Z x1 x2 S1 S2 S3 Variables
A2 Z
B2 S1
C2 x1
D2 S3
41
Simplex Tableau for Maximization (7)
• Step V: Compute the coefficients for the second tableau. A
sequence of operations will be performed so that at the end the
x1 column in the second tableau will have the following
coefficients:

The second tableau yields the following feasible solution:

x1 = 315, x2 = 0, S1 = 240, S2 = 0, S3 = 105, and Z = 4,095

42
Simplex Tableau for Maximization (8)
• Step IV: . Enter the basic variables for the second tableau. The
row sequence of the previous tableau should be maintained,
with the leaving variable being replaced by the entering
variable. Initial tableau
Row Cj Coefficients of: RHS Upper Bound
No. on Entering
BV Z x1 x2 S1 S2 S3 Variables
A1 Z 1 -13 -11 0 0 0 0
B1 S1 0 4 5 1 0 0 1,500 375
C1 S2 0 5 3 0 1 0 1,575 315
D1 S3 0 1 2 0 0 1 420 420

Initial tableau
Row Cj Coefficients of: RHS Upper Bound
No. on Entering
BV Z x1 x2 S1 S2 S3 Variables
A2 Z
B2 S1
C2 x1
D2 S3
43
Simplex Tableau for Maximization (9)
Compute the new values (coefficients) for the row, starting with the
“key row” in the initial tableau: OldValue
C 21 =
KeyValue

0 5 3 0 0 0
C 21 = = 0 C 22 = =1 C 23 = C 24 = =0 C 26 = =0 C 26 = =0
5 5 5 5 5 5
1,575
Second tableau at the end of 1st iteration C 2 RHS = = 315
5
Row Cj Coefficients of: RHS Upper Bound
No. on Entering
Variables
BV Z x1 x2 S1 S2 S3
A2 Z
B2 S1
C2 x1 0 1 3/5 0 1/5 0 315
D2 S3

Continue with computation of new values (coefficients) for other

rows, starting with the objective function row 44
Simplex Tableau for Maximization (10)
Compute the new values (coefficients) for the objective function
row:
æ KeyColumnV alue * KeyRowValu e ö
NewValue = OldValue - çç ÷÷
è KeyValue ø
Second tableau at the end of 1st iteration
Row Cj Coefficients of: RHS Upper Bound
No. on Entering
BV Z x1 x2 S1 S2 S3 Variables
A2 Z 1 0 -16/5 0 13/5 0 4,095
B2 S1
C2 x1 0 1 3/5 0 1/5 0 315
D2 S3

Continue with computation of new values (coefficients)

for rows number B2 and D2
45
Simplex Tableau for Maximization (11)
Computation of new values (coefficients) for the objective function
row:
æ KeyColumnV alue * KeyRowValu e ö
NewValue = OldValue - çç ÷÷
è KeyValue ø
æ - 13 * 0 ö
A21 = 1 - ç ÷ = 1+ 0 = 1
è 5 ø
æ - 13 * 5 ö æ - 13 * 5 ö æ - 13 * 5 ö
A22 = -13 - ç ÷=ç ÷-ç ÷=0
è 5 ø è 5 ø è 5 ø
æ - 13 * 3 ö éæ - 11 * 5 ö æ - 13 * 3 ö ù æ - 55 49 ö - 16
A23 = - 11 - ç ÷= êç 5 ÷ - ç 5 ÷ ú = ç 5 + 5 ÷ = 5
è 5 ø ëè ø è øû è ø
æ - 13 * 0 ö éæ 0 * 5 ö æ - 13 * 0 ö ù æ - 0 - 0 ö
A24 = 0 - ç ÷= êç 5 ÷ - ç 5 ÷ ú = ç 5 + 5 ÷ = 0
è 5 ø ëè ø è øû è ø
æ - 13 * 1 ö éæ 0 * 5 ö æ - 13 * 1 ö ù æ 13 ö 13
A25 = 0 - ç ÷= ç
ê 5 ÷ - ç ÷ ú = ç 0 + ÷=
è 5 ø ëè ø è 5 øû è 5 ø 5
æ - 13 * 0 ö éæ 0 * 5 ö æ - 13 * 0 ö ù
A26 = 0 - ç ÷= êç 5 ÷ - ç 5 ÷ ú = (0 + 0 ) = 0
è 5 ø ëè ø è øû
46
Simplex Tableau for Maximization (12)
Using the same operation, compute the new values (coefficients)
for the remaining two rows (B2 and D2) and the upper bound
entering variables
æ KeyColumnV alue * KeyRowValu e ö
NewValue = OldValue - çç ÷÷
è KeyValue ø

Second tableau at the end of 1st iteration

Row C Coefficients of: RHS Upper Bound on Entering Variables

j
No. BV Z x1 x2 S1 S2 S3
A2 Z 1 0 -16/5 0 13/5 0 4,095
B2 S1 0 0 13/5 1 -4/5 0 240 92.3 (x2, if S1 = 0 in B2) = (5/13)240
C2 x1 0 1 3/5 0 1/5 0 315 525 (x2, if x1 = S2 =0 in C2) = (5/3)(315)
D2 S3 0 0 7/5 0 -1/5 1 105 75 (x2, if S2 = S3 = 0 in C2) = (5/3)(315)

47
Simplex Tableau for Maximization (13)
• Identify the new “key column”, “key row”
and “key value” in the 2nd tableau:
Second tableau at the end of 1st iteration
Row RHS Upper Bound on
Cj Coefficients of:
No. Entering Variables
BV Z x1 x2 S1 S2 S3

A2 Z 1 0 -16/5 0 13/5 0 4,095

B2 S1 0 0 13/5 1 -4/5 0 240 92.3

C2 x1 0 1 3/5 0 1/5 0 315 525
D2 S3 0 0 7/5 0 -1/5 1 105 75

Entering variable = x2 Key column value (element) = -16/5

Leaving variable = S3 Key element (value) = 7/5

48
Simplex Tableau for Maximization (14)
• Step VI: Check for optimality. The second feasible
solution is also not optimal, because the objective
function (row A2) contains a negative coefficient.
Another iteration beginning with step 2 is necessary.
• Following the same steps as in the first iteration, our
third tableau at end of second and final iteration will
show coefficients as given in the next slide.

49
Simplex Tableau for Maximization (15)

50
Simplex Tableau for Maximization (16)
• In the third tableau, all the coefficients in the
objective function (row A3) are positive. Thus
an optimal solution has been reached and it is
as follows:
x1 = 270, x2 = 75, S1 = 45, S2 = 0, S3 = 0, and Z = 4335

51
Marginal Values of Additional Resources (1)
• From the previous slide, the Simplex solution yields the
optimum production program for N. Dustrious Company.
o The company can maximize its sale income to $4,335 by
producing 270 units of product I and 75 units of product
II.
o There will be no surplus of raw materials or production
time.
o But there will be 45 units of unused storage space.
• The managers are interested to know if it is worthwhile to
increase its production by purchasing additional units of
raw materials and by either expanding its production
facilities or working overtime. 52
Marginal Values of Additional Resources (2)
• The critical questions are:
o What is the income value (or marginal value) of each
additional unit of each type of resources?
o What is the maximum cost ( or marginal cost) that they should
be willing to pay for each additional unit of resources?
• Answers to these questions can be obtained from the objective
function in the last tableau of the simplex solution:

53
Marginal Values of Additional Resources (3)
• Because S1, S2 and S3 represent surplus resources, the
negatives of these variables (i.e., -S1, -S2, -S3) represent
additional units of these resources that can be made
available.
• The income values or marginal values of additional units of
these resources can be obtained by taking the partial
derivatives of Z with respect to -S1, -S2 and -S3.
• Therefore, the marginal value of one additional unit of:

54
Marginal Values of Additional Resources (4)
• Thus, the marginal values of additional units of resources
can be obtained directly from the coefficients of the
objective function in the last tableau of a Simplex solution.
• The N. Dustrious Company should be willing to pay up to
$15/7 for an additional unit of raw materials and $16/7 for
an additional unit of production time.
• If the actual cost of an additional unit (i.e., marginal cost) of
these resources are smaller than the marginal value, the
company should be able to increase its income by increasing
production.
• The marginal values above are valid, however, only as long
as there is surplus storage space available.
55
Sensitivity Analysis (1)
• Sensitivity analysis helps to test the sensitivity of
the optimum solution with respect to changes of
the coefficients in the objective function, in the
constraints inequalities (the constant terms in
the constraints).

56
Sensitivity Analysis (2)
• For Example in the case study discussed:
o The actual selling prices (or market values) of the two
products may vary from time to time. Over what ranges can
these prices change without affecting the optimality of the
present solution?
o Will the present solution remain the optimum solution if the
amount of raw materials, production time, or storage space
is suddenly changed because of shortages, machine failures,
or other events?
o The amount of each type of resources needed to produce
one unit of each type of product can be either increased or
decreased slightly. Will such changes affect the optimal
solution ?
57
Complications in Simplex Method (1)
• An objective function to be minimized instead of maximized.
• Greater-than-or-equal-to constraints.
• Equalities instead of inequalities for constraints.
• Decision variables unrestricted in signs.
• Zero constants on the right-hand side of one or more
constraints.
• Some or all decision variables must be integers
• Non-positive constants on the RHS of the constraints.
• More than one optimal solution, that is, multiple solutions
such that there is no unique optimal solution.
58
Complications in Simplex Method (2)
• The constraints are such that no feasible solution
exists.
• The constraints are such that one or more of the
variables can increase without limit and never violate a
constraint (i.e., the solution is unbounded).
• Some or all of the coefficients and RHS terms are given
by a probability distribution rather than a single value.

59
Complications in Simplex Method (3)
Minimization Problem – Solution 1

• This objective function can be converted to the standard form of

maximization. Let Z’ = -Z, so:

• Since maximum Z’ = minimum (Z), the objective function

becomes:

• After the Z’ value is found, replace Z = -Z’

60
Complications in Simplex Method (4)
Minimization Problem – Solution 2
• In the case of a minimization problem, an optimum
solution is reached when:
o All the nonbasic variables have nonpositive
coefficients in row 1 of the simplex tableau
o The entering variable will be one which has the largest
positive coefficient in row 1.
• All the other operations in the simplex method remain
unchanged.

61
Complications in Simplex Method (5)
• In the standard form of the linear programming model, the
constraints are all expressed as less than or equal to (£) a
certain amount, that is,

• In many occasions, the constraints must specify the lower

bounds rather than the upper bounds such as:

which involves the inequality "greater than or equal to"

62
Complications in Simplex Method (6)
Example: Greater- Than-Or-Equal- To Constraints

• To start the solution, slack variables must first be assigned

to convert all in-equalities to equalities. Let S1 and S2 be
slack variables.
• Re- arrange the objective function so that all the variables
are on the left-hand side of the equation.
63
Complications in Simplex Method (7)

…….Eq. (2)

• The negative signs for S1 and S2 make it no longer feasible to set

all the decision variables (i.e., y1, y2, y3) equal to zero as the
initial solution.
• To assure a starting feasible solution, artificial variables can be
added to the greater-than-or-equal-to constraints. Let W1 and
W2 be two artificial variables. Hence the Eq. (2) becomes:

…….Eq. (3)
64
Complications in Simplex Method (8)
• A starting feasible solution can be easily derived from Eq.
(3) as follows:

• The objective function in Eq. (3) then becomes:

…….Eq. (4)
• From Eq. (3):

65
Complications in Simplex Method (9)
• Substituting these expressions in Eq. (4) yields the following
new expression for the objective function:

• The objective function may now be combined with Eq. (3) to

express the problem model as follows:
P = 43,500 y1 + 38,425 y 2 + 14,580 y 3 - 5,000S1 - 5,000S 2 = 120,000
4 y1 + 5 y 2 + y 3 - S1 + W1 = 13
…….Eq. (5)
5 y1 + 3 y 2 + 2 y 3 - S 2 + W = 11
2

• The coefficients and constants in Eq. (5) can now be arranged

in the Tableau format as shown in next slide.
66
Complications in Simplex Method (10)

67
Complications in Simplex Method (11)
Equality Constraint
• An equality constraint has the following general form:

o An artificial variable must be assigned to each equality

constraint to start the simplex solution. Otherwise, the
constraint would be violated when all the decision variables
are assumed to be zero.
o Sometimes a decision variable may take on either negative or
positive values. If x1 is unrestricted in sign, replace it
throughout the model by the difference of two new
nonnegative variables:
xj = xj’ – xj’’ where xj’ ³ 0, xj’’ ³ 0 68
Complications in Simplex Method (12)
Equality Constraint …
• Because xj’ and xj’’ can have any
nonnegative values their difference (xj’ –
xj’’) can have any value (positive or
negative). After substitution, the simplex
method can proceed with just nonnegative
variables.

69
Complications in Simplex Method (13)
Degenerate Solution
• If the number of basic variables is fewer than the number
of constraints in a solution, the solution is said to be
degenerate.
• A zero constant term for one or more basic variables in any
iteration of the simplex solution would be a clear indication
of a degenerate solution.
• The normal simplex procedure cannot solve a degenerate
problem.
• Advanced methods are available to solve degenerate
problems.
70
Complications in Simplex Method (14)
Integer and Mixed-Integer Problems
• A linear programming problem in which all the decision
variables must have integer values is called an integer
programming problem.
• A problem in which only some of the decision variables
must have integer values is called a mixed-integer
programming problem.
• Sometimes, some (or all) of the decision variables must
have the value of either 0 or 1. Such problems are then
called zero-one mixed-integer programming problems.
• Simplex method cannot be used to such problems.
Advanced methods are available for this purpose. 71
Duality (1)
• With every LP problem, there is associated another LP
problem which is called the dual of the original (primal)
problem.
Formulating the Dual problem
• Consider again the production mix problem of N. Dustrious
Company.
• Suppose that the company is considering leasing out the
entire production facility to another company, and it must
decide on the minimum daily rental price that will be
acceptable.
• This decision problem can also be formulated as a linear
programming problem. 72
Duality (2)
• Let y1, y2 and y3 represent the unit price of each unit of storage
space, raw materials, and production time, respectively.
• The unit prices are in fact the income values of each unit of
resource to the N. Dustrious Company.
• There are available 1,500 M2 of storage space, 1,575 kg of raw
materials 420 minutes of production time per day.
• Thus the total income value (P) of all the available resources may
be expressed as follows :
• P = 1500y1 + 1575y2 + 420y3
• The objective of the problem is to minimize P subject to the
condition that the N. Dustrious Company will earn at least as
much income as when it operates the production facility itself.
73
Duality (3)
• Since the market value (or selling price) of 1 unit of product
I is $13 and it requires 4M2 of storage space, 5kg of raw
materials, and 1 minute of production time, the following
constraint must be satisfied:
4y1 + 5y2 + y3 ³ 13
• Similarly, for Product II:
5y1 + 3y2 + 2y3 ³ 11

• In addition, the unit prices y1, y2 and y3 must all be greater

than or equal to zero.

74
Duality (4)
• The new linear programming problem may now be
summarized as follows :

…….Eq. (1)

• The following interesting observations can now be made:

• P = Z = $4,335
• y1 = $0; y2 = $15/7 and y3 = $16/7
• This problem is the same as maximization problem in the
previous example and can now be solved accordingly.
75
Duality (5)
The Primal-Dual Relationship

76
Duality (6)
Complete Regularization of the Primal Problem
• Consider the following primal problem:

• The first inequality requires no modification.

77
Duality (7)
• The second inequality can be changed to the less-than-or-
equal-to type by multiplying both sides of the inequality by
-1 and reversing the direction of the inequality; that is,

• The equality constraint can be replaced by the following

two inequality constraints:

• If both of these inequality constraints are satisfied, the

original equality constraint is also satisfied.

78
Duality (8)
• Multiplying both sides of the inequality by –1 and reversing
the direction of the inequality yields:

• The primal problem can now take the following standard

form:

79
Duality (9)
• The dual of this problem can now be obtained as
follows:

80
Duality (10): Binding & nonbinding constraints
• The slack of a resource constraint is the amount of the
corresponding resource that will not be used if the optimal
solution is implemented.
• The surplus of a minimum requirement constraint is the
amount by which the requirement will be exceeded if the
optimal solution is implemented.
• A binding constraint implies that the corresponding
resource or requirement is restricting the optimal solution
and objective value. A binding constraint has slack or
surplus of zero.
• A nonbinding constraint is one in which there is positive
slack or surplus when evaluated at the optimal solution. 81
Solving LP Problems Using
the Big ‘M’ Method

82
Solving LP problem using Big ‘M’ method (1)
• We now know how to use the Simplex method to solve LP
problems. We can also solve LP problems using the Big ‘M’
method.
• The Big ‘M’ method is a modified version of the Simplex
method (the two are basically the same methods)
• The only difference is that:
– the Simplex method contains ≤ in which case we have to add
slack variables (+S);
– the Big ‘M’ method contains the ≥ in which case we have to
subtract surplus variables (-S) and add artificial variables (A),
i.e.:
• ≤ = add slack variables (+S)
• ≥ = subtract surplus variables (-S); and add artificial variables (+A) 83
Solving LP problem using Big ‘M’ method (2)
• Solve the following Linear Programming (LP) using Big ‘M’
method

Minimize
Z = 7 x1 + 15 x2 + 20 x3
Subject to:
2 x1 + 4 x 2 + 6 x3 ³ 24
3 x1 + 9 x 2 + 6 x3 ³ 30
x1 , x 2 , x3 ³ 0

84
Solving LP problem using Big ‘M’ method (3)
• Solution step 1

Minimize
Z = 7 x1 + 15 x2 + 20 x3
Subject to:
2 x1 + 4 x 2 + 6 x3 - S1 + A1 = 24
3 x1 + 9 x 2 + 6 x3 - S 2 + A2 = 30
x1 , x 2 , x3 , S1 , S1 , A1 , A2 ³ 0

85
Solving LP problem using Big ‘M’ method (4)
• Solution step 2 – Construct the initial table

Cj Soln Ratio
CB BV x1 x2 x3 S1 S2 A1 A2
R1
R2

Where:
CB = Coefficient of basic variables
BV = Basic variables
Cj = Coefficient of objective function
R1 = Row 1
R1 = Row 2
86
Solving LP problem using Big ‘M’ method (5)
• Solution step 3: Rewrite the objective function as:
Minimize
Z = 7 x1 + 15 x 2 + 20 x3 + 0 S1 + 0S 2 + MA1 + MA2
Where: MA1 and MA2 are maximum positive values
• Solution step 4: Enter the corresponding coefficient of
objective function (Cj), BV, and CB in the initial table as:
Cj 7 15 20 0 0 M M Soln Ratio
CB BV x1 x2 x3 S1 S2 A1 A2
R1 M A1
R2 M A2
87
Solving LP problem using Big ‘M’ method (6)
• Solution step 5: Use the rewritten form of objective
functions to fill the coefficients of the remaining two rows
in the initial Table.
Minimize
Z = 7 x1 + 15 x 2 + 20 x3 + 0S1 + 0S 2 + MA1 + MA2
Subject to:
2 x1 + 4 x 2 + 6 x3 - S1 + A1 = 24
3x1 + 9 x2 + 6 x3 - S 2 + A2 = 30
x1 , x 2 , x3 , S1 , S1 , A1 , A2 ³ 0

Cj 7 15 20 0 0 M M Soln Ratio
CB BV x1 x2 x3 S1 S2 A1 A2
R1 M A1 2 4 6 -1 1 1 0 24
R2 M A2 3 9 6 0 -1 0 1 30
88
Solving LP problem using Big ‘M’ method (7)
• Solution step 6: Calculate the values of Zj and fill them in
the respective cells of the initial table as:
Z j = å (CBi ) * (aij ) = (CB of R1 x Element) + (CB of R2 x Element)
2

i =1

Cj 7 15 20 0 0 M M
CB Soln Ratio
BV x1 x2 x3 S1 S2 A1 A2

R1 M A1 2 4 6 -1 1 1 0 24

R2 M A2 3 9 6 0 -1 0 1 30

Zj 5M 13M 12M -M -M M M 54M

89
Solving LP problem using Big ‘M’ method (8)
• Solution step 7: Calculate the values of Cj – Zj and fill them
in the respective cells of the initial table as:

Cj 7 15 20 0 0 M M
CB Soln Ratio
BV x1 x2 x3 S1 S2 A1 A2
R1 M A1 2 4 6 -1 1 1 0 24
R2 M A2 3 9 6 0 -1 0 1 30
Zj 5M 13M 12M -M -M M M 54M
Cj – Zj 7-5M 15-13M 20-12M M M 0 0

90
Solving LP problem using Big ‘M’ method (9)
• Solution step 8: Check for optimality condition
(minimization problem) which requires that all:
Cj - Zj ³ 0
Cj 7 15 20 0 0 M M
CB Soln Ratio
BV x1 x2 x3 S1 S2 A1 A2
R1 M A1 2 4 6 -1 1 1 0 24
R2 M A2 3 9 6 0 -1 0 1 30
Zj 5M 13M 12M -M -M M M 54M
Cj – Zj 7-5M 15-13M 20-12M M M 0 0

Some values of the solution (Cj – Zj) have negative signs (see the
shaded cells). The optimum solution was therefore not reached so we
proceed farther to the 1st Iteration
91
Solving LP problem using Big ‘M’ method (10)
• Solution step 9: To proceed with the 1st one has to
identify the “key column” (with the most negative value),
the “key row” and the key element:

The key column is shaded: column with the most +ve value

Cj 7 15 20 0 0 M M
CB Soln Ratio
BV x1 x2 x3 S1 S2 A1 A2
R1 M A1 2 4 6 -1 1 1 0 24
R2 M A2 3 9 6 0 -1 0 1 30
Zj 5M 13M 12M -M -M M M 54M
Cj – Zj 7-5M 15-13M 20-12M M M 0 0

92
Solving LP problem using Big ‘M’ method (11)
• Before establishing the “ key row” calculate the ratio A1
and A2, enter them in the initial table and the row with
the least positive value will be the “key row”.

Cj 7 15 20 0 0 M M
CB Soln Ratio
BV x1 x2 x3 S1 S2 A1 A2
R1 M A1 2 4 6 -1 1 1 0 24 6
R2 M A2 3 9 6 0 -1 0 1 30 10/3
Zj 5M 13M 12M -M -M M M 54M
Cj – Zj 7-5M 15-13M 20-12M M M 0 0
24 30 10
Ratio A1 = = 6 =
Ratio A2 =
4 9 3
In this table, the “key column value” = 4; and the “key value” = 9
93
Solving LP problem using Big ‘M’ method (12)
• Solution step 10: Prepare the 1st Iteration with x2 = the
entering variable, and A2 = the leaving variable, then find
new values for R4 and R3 as:
KeyRowValue
R4 =
KeyValue
Cj 7 15 20 0 0 M M Soln Ratio

CB BV x1 x2 x3 S1 S2 A1 A2
R3 M A1
R4 15 X2 1/3 1 2/3 0 -1/9 0 - 10/3

• Then calculate R3 values as:

æ KeyColumnValue * KeyRowValue ö OR;
R3 = OldValue - çç ÷÷
è KeyValue ø

R3 = OldValue - KeyColumnValue * R4
94
Solving LP problem using Big ‘M’ method (13)
• Calculation of R3 values: æ KeyColumnValue * KeyRowValue ö
R3 = OldValue - çç ÷÷
è KeyValue ø
4 6-4 2
R 31 = 2 - 4 * = =
3 3 3
R 32 = 4 - 4 *1 = 4 - 4 = 0
2 8 18 - 8 10
R 33 = 6 - 4 * =6- = =
3 3 3 3
R 34 = -1 - 4 * 0 = -1
-1 4
R 35 = 0 - 4 * =
9 9 4 * 10 24 - 40 72 - 40 32
R3 so ln = 24 - = = =
R 36 =1- 4*0 =1 3 3 3 3

Cj 7 15 20 0 0 M M Soln Ratio

CB BV x1 x2 x3 S1 S2 A1 A2
R3 M A1 2/3 0 10/3 -1 4/9 1 - 32/3
R4 15 X2 1/3 1 2/3 0 -1/9 0 - 10/3
95
Solving LP problem using Big ‘M’ method (14)
• Solution step 11: After framing the table for iteration 1,
calculate Zj, and Cj – Zj :
Cj 7 15 20 0 0 M M
CB Soln Ratio
BV x1 x2 x3 S1 S2 A1 A2
R3 M A1 2/3 0 10/3 -1 4/9 1 - 32/3
R4 15 x2 1/3 1 2/3 0 -1/9 0 - 10/3
Zj 2/3M+5 15 10/M+10 -M 4/9M-5/3 M - 32/3+ 50
Cj – Zj -2/3M+2 0 10/3M+10 M -4/9M=5/3 0 -

• Check for optimality: C j - Z j ³ 0

• See the shaded cell with negative values
• The optimum solution was therefore not reached so
we proceed farther to the 2nd Iteration
96
Solving LP problem using Big ‘M’ method (15)
• Solution step 12: Proceed with iteration 2 – start by
identifying the key column (with the most positive value,
the key row and the key element in the 1st iteration
Cj 7 15 20 0 0 M M
CB Soln Ratio
BV x1 x2 x3 S1 S2 A1 A2
R3 M A1 2/3 0 10/3 -1 4/9 1 - 32/3
R4 15 x2 1/3 1 2/3 0 -1/9 0 - 10/3
Zj 2/3M+5 15 10/M+10 -M 4/9M-5/3 M - 32/3+ 50
Cj – Zj -2/3M+2 0 10/3M+10 M -4/9M=5/3 0 -

• The shaded column is the key column

97
Solving LP problem using Big ‘M’ method (16)
• Before establishing the key row – calculate ratios A1 and
A2, then enter them in the 1st Iteration table:
Cj 7 15 20 0 0 M M
CB Soln Ratio
BV x1 x2 x3 S1 S2 A1 A2
R3 M A1 2/3 0 10/3 -1 4/9 1 - 32/3 32/3*3/10 = 16/5
R4 15 x2 1/3 1 2/3 0 -1/9 0 - 10/3
Zj 2/3M+5 15 10/M+10 -M 4/9M-5/3 M - 32/3+ 50 10/3*3/2 = 5
Cj – Zj -2/3M+2 0 10/3M+10 M -4/9M=5/3 0 -

• The row with the least positive value will be the key
row (shaded)
• In this table x3 is the entering variable, and A1 is the
leaving variable
• The “key element” = 10/3
98
Solving LP problem using Big ‘M’ method (17)
• Prepare the 2nd iteration – find the new values for R5
KeyRowValue
R5 =
KeyValue

Cj 7 15 20 0 0 M M
CB Soln Ratio
BV x1 x2 x3 S1 S2 A1 A2
R5 20 x3 1/5 0 1 -3/10 2/15 - - 16/5
R6 15 x2

• Note that: Rsoln for R5 2nd is brought forward from the

1st iteration; i.e.
16
R3 so ln =
5

99
Solving LP problem using Big ‘M’ method (18)
• Find the new values for R6
R6 = OldValue - OldValue - KeyColumnValue * R5
Cj 7 15 20 0 0 M M
CB Soln Ratio
BV x1 x2 x3 S1 S2 A1 A2
R5 20 x3 1/5 0 1 -3/10 2/15 - - 16/5
R6 15 x2 1/5 1 0 1/5 -1/5 - - 6/5

1 æ 2 1ö 1 2 5- 2 1
R61 = -ç * ÷ = - = =
3 è 3 5 ø 3 15 15 5
æ2ö
R62 = 1 - ç ÷ * 0 = 1
è3ø
2 æ2 ö
R63 = - ç *1÷ = 0
3 è3 ø
æ 2 -3ö 2 1
R64 = 0 - ç * ÷ = 0+ =
è 3 10 ø 10 5
-1 æ 2 2 ö -1 4 - 5 - 4 - 9 -1
R65 = -ç * ÷ = - = = =
9 è 3 15 ø 9 45 45 45 5
10 æ 2 16 ö 10 32 50 - 32 18 6
R6 So ln = -ç * ÷ = - = = =
3 è 3 5 ø 3 15 15 15 5 100
Solving LP problem using Big ‘M’ method (19)
• Find Zj, and Cj – Zj; and check for optimality:
Cj 7 15 20 0 0 M M
CB Soln Ratio
BV x1 x2 x3 S1 S2 A1 A2
R5 20 x3 1/5 0 1 -3/10 2/15 - - 16/5
R6 15 x2 1/5 1 0 1/5 -1/5 - - 6/5
Zj 7 15 20 -3 -1/3 - -
Cj – Zj 0 0 0 3 1/3 - - 82

= 0 + 18 + 66 = 82
Cj - Zj ³ 0
All values of the solution (Cj – Zj) have positive signs. The optimum
solution has therefore been reached as equal to 82 and the values of
x1, x2, and x3 are:
Substituting the values of x1, x2, and x3 in the
x1 = 0
original optimizing function we have:
6
x2 = Min ( Z ) = 7 x 1 + 15 x 2 + 20 x 3
5 æ 6 ö æ 16 ö
= 7 ( 0 ) + 15 ç ÷ + 20 ç ÷
16 è 5 ø è 5 ø
x3 =
5 = 0 + 18 + 66 = 82 101
More Examples: Solving LP Problems

102
Maximization examples

103
Example 1:
• A company makes two products (R and S) within three
departments (X, Y and Z). Production times per unit,
contribution per unit, and the hours available in each
department are shown below:
Product R Product S Capacity (hrs)
Contribution/Unit $4 $8
Hours/Unit Hours/Unit
Department X 8 10 11,000
Department Y 4 10 9,000
Department Z 12 6 12,000

• Question: What is the optimum production plan in

order to maximize contribution? 104
Define the problem
• Let product R = x
• Let product S = y
• Let maximize contribution = Z

105
Objective function
Z = 4x + 8y
Product R Product S Capacity (hrs)
Contribution/Unit $4 $8
Hours/Unit Hours/Unit
Department X 8 10 11,000
Department Y 4 10 9,000
Department Z 12 6 12,000

106
 Constraints

Department X 8x + 10y ≤ 11,000

Department Y
Department Z

107
Constraints
Department X 8x + 10y ≤ 11,000
Department Y 4x + 10y ≤ 9,000
Department Z

108
Constraints
Department X 8x + 10y ≤ 11,000
Department Y 4x + 10y ≤ 9,000
Department Z 12x + 6y ≤ 12,000
Non Negativity

109
Constraints
Department X 8x + 10y ≤ 11,000
Department Y 4x + 10y ≤ 9,000
Department Z 12x + 6y ≤ 12,000
Non Negativity x, y ≥ 0

110
 y=0
Constraints x=?
Department X 8x + 10y ≤ 11,000
Department Y 4x + 10y ≤ 9,000
Department Z 12x + 6y ≤ 12,000
Non Negativity x, y ≥ 0

111
 y=0 x=0
Constraints x=? y=?
Department X 8x + 10y ≤ 11,000
Department Y 4x + 10y ≤ 9,000
Department Z 12x + 6y ≤ 12,000
Non Negativity x, y ≥ 0

112
 y=0 x=0
Constraints x=? y=?
Department X 8x + 10y ≤ 11,000 1,375 1,100
Department Y 4x + 10y ≤ 9,000
Department Z 12x + 6y ≤ 12,000
Non Negativity x, y ≥ 0

113
 y=0 x=0
Constraints x=? y=?
Department X 8x + 10y ≤ 11,000 1,375 1,100
Department Y 4x + 10y ≤ 9,000 2,250 900
Department Z 12x + 6y ≤ 12,000 1,000 2,000
Non Negativity x, y ≥ 0

114
 y=0 x=0
Constraints x=? y=?
Department X 8x + 10y ≤ 11,000 1,375 1,100
Department Y 4x + 10y ≤ 9,000 2,250 900
Department Z 12x + 6y ≤ 12,000 1,000 2,000
Non Negativity x, y ≥ 0

115
 y=0 x=0
Constraints x=? y=?
Department X 8x + 10y ≤ 11,000 1,375 1,100
Department Y 4x + 10y ≤ 9,000 2,250 900
Department Z 12x + 6y ≤ 12,000 1,000 2,000
Non Negativity x, y ≥ 0

116
Graph
Graph showing the maximum contribution of x and y
y

2,000

1,000

x
1,000 2,000

117
Graph …
Graph showing the maximum contribution of x and y
y

2,000

1,000

Dept X Constraint

x
1,000 2,000

118
Graph …
Graph showing the maximum contribution of x and y
y

2,000

1,000 Dept Y Constraint

Dept X Constraint

x
1,000 2,000

119
Graph …
Graph showing the maximum contribution of x and y
y

2,000 Dept Z Constraint

1,000 Dept Y Constraint

Dept X Constraint

x
1,000 2,000

120
Graph …
Graph showing the maximum contribution of x and y
y

2,000 Dept Z Constraint

1,000 Dept Y Constraint

2
3
Dept X Constraint
4

1 5

x
1,000 2,000

121
Graph …
Graph showing the maximum contribution of x and y
y

2,000 Dept Z Constraint

Feasible Region
1,000 Dept Y Constraint

2
3
Dept X Constraint
4

1 5

x
1,000 2,000

122
Iso-Contribution Line (ICL)
• A line showing points of equal contribution
Z = 4x + 8y
Z = $ 4000

• If x = 0, then y = 500
• If y = 0, then x = 1,000

123
Graph …
Graph showing the maximum contribution of x and y
y

2,000 Dept Z Constraint

Feasible Region

1,000 Dept Y Constraint

IC Line
2
3
Dept X Constraint
500 4

1 5

x
1,000 2,000

124
Graph …
Graph showing the maximum contribution of x and y
y

2,000 Dept Z Constraint

Feasible Region

IC Line
1,000 Dept Y Constraint

2
3
500 Dept X Constraint
4

1 5

x
1,000 2,000

125
Graph …
Graph showing the maximum contribution of x and y
y

2,000 Dept Z Constraint

Feasible Region Optimal Solution

IC Line
1,000 Dept Y Constraint

2
3
500 Dept X Constraint
4

1 5

x
1,000 2,000

126
Graph …
Graph showing the maximum contribution of x and y
y

2,000 Dept Z Constraint

Feasible Region
Optimal Solution
IC Line

1,000 Dept Y Constraint

2
y’
3 Dept X Constraint
500
4

1 5

x’ x
1,000 2,000

127
Optimal Solution

Simultaneous Equations:
Dept X: 8x + 10y = 11,000
Dept Y: 4x + 10y = 9,000

128
Optimal Solution …
Simultaneous Equations:
Dept X: 8x + 10y =11,000
Dept Y: 4x + 10y = 9,000
4x + 0 = 2,000
x = 500
Substituting x in the 1st equation:
(8 x 500) + 10y = 11,000
y = 700
Maximum Combination: = 4 x 500 + 8 x 700
= 7,600
129
Example 2
• A company makes two products (R and S) within three
departments (X, Y and Z). Production times per unit,
contribution per unit, and the hours available in each
department are shown below:
Product R Product S Capacity (hrs)
Contribution/Unit $3 $2
Hours/Unit Hours/Unit
Department X 2 1 100
Department Y 1 1 80
Department Z 1 0 40

• Required: What is the optimum production plan in

order to maximize contribution? 130
Follow same steps as in illustration 1
Max : Z = 3x + 2y
Subject to: 2x + y ≤ 100 (Dept 1)
x+y ≤ 80 (Dept 2)
x ≤ 40 (Dept 3)
x, y ≥0

131
 y=0 x=0
Constraints x=? y=?
Department X 2x + y ≤ 100 50 100
Department Y x + y ≤ 80 80 80
Department Z x ≤ 40 40
Non Negativity x, y ≥ 0

132
 y Graph showing the maximum contribution of
x and y
100

80

5 Dept Z

Feasible
Region
Dept Y

3 Dept X

1 2
x
40 50 80
133
IC Line
• A line showing points of equal contribution
Z = 3x + 2y
Z = $ 60

• If x = 0, then y = 30
• If y = 0, then x = 20

134
Optimal Solution
Simultaneous Equations:
Dept X: 2x + y =100
Dept Y: (-)x + y = 80
x+ 0 = 20
x = 20
Substituting x in the 1st equation:
(2 x 20) + y = 100
y = 60
Maximum Combination: = 3 x 20 + 2 x 60
= 180
135
 y Graph showing the maximum contribution of
x and y
100
The optimal solution (the
intersection of Dept X and
Dept Y constraints) = (20, 60)
80

5 Dept Z
60
4
Z = $ 60

The next Z value

must be greater
than 60 for a
30 Dept Y maximization
problem
3 Dept X (e.g. Z = 120 etc)

1 2
x
20 40 50 80
136
Example 3
• A farmer owns 240 acres of land and can make profits
of $ 40/acre and $ 30/acre from growing corn and oat
respectively. If the total labor available is 320 hours
and corn and oat require 2 hrs and 1 hrs respectively,
how many acres of each should be planted to maximize
profit?
Corn (X) Oats (Y) Available
Profit/acre $40 $30
Acre/Hours Acre/Hours
Land (X) 15 20 240
Labor (Y) 10 5 320

137
Define the problem
• Let x = number of acres of corn
• Let y = number of acres of oats
• Let maximize = P

138
 Objective function
P = 40x + 30y = Total income from corn + Total income from oats

Corn (X) Oats (Y) Available

Profit/acre $40 $30
Acre/Hours Acre/Hours
Land (X) 15 20 240
Labor (Y) 10 5 320

139
Constraints
y=0 x=0
Constraints x=? y=?
Land (X) x + y ≤ 240 240 240
Labor (Y) 2x + y ≤ 320 180 320
Non Negativity x, y ≥ 0

140
Graph
Graph showing the optimal amount of x and y

B=(0,240)
320
Labor

240

C=(80,160) Land

x
A=(0,0) D=(160,0) 160 240 141
Optimal Solution
Simultaneous Equations:
Labor X: 2x + y = 320
Land Y: x+ y = 240
x+ 0 = 80
x = 80
Substituting x in the 1st equation:
(2 x 80) + y = 320
y = 160
Optimal combination (point C): = 40 x 80 + 30 x 160
= 8,000
Calculate P (total income) at points A, B and D. 142
Comparison (P = 40x + 30y)
At A (0,0) P = (40 x 0) + (30 x 0) = 0
At B (160,0) P = (40 x 160) + (30 x 0) = 6,400
At C (80,160) P = (40 x 80) + (30 x 160) = 8,000
At D (0,240) P = (40 x 0) + (30 x 240) = 7,200

Thus, total income (P) is the highest at point C

143
Minimization examples

144
Example 4
• A rancher is mixing tow types of feed ingredients
(Brand X and Brand Y) for his cattle. If each serving is
required to have 60g of protein and 30g of fat, where
Brand X has 15g of protein and 10g of fat and costs 80
Cents/unit, and Brand Y contains 20g of protein and 5g
of fat and costs 50 Cents per unit. How much of each
type should be used to minimize cost to the rancher?

Brand X Brand Y Requirement (g)

Price/Unit $0.8 $0.5
grams grams
Protein (X) 15 20 60
Fats (Y) 10 5 30
145
Define the problem
• Let Brand X = x
• Let Brand Y = y
• Let minimize cost = C

146
 Objective function
C = 0.8x + 0.5y

Brand X Brand Y Requirement (g)

Price/Unit $0.8 $0.5
grams grams
Protein (X) 15 20 60
Fats (Y) 10 5 30

147
Constraints
y=0 x=0
Constraints x=? y=?
Protein (X) 15x + 20y ≥ 60 4 3
Fats (Y) 10x + 5y ≥ 30 3 6
Non Negativity x, y ≥ 0

148
Graph
Graph showing the optimal amount of x and y

A=(0,6)
6 Fats

Feasible
Region
3

Protein
B=(2.4,1.2)
C=(4,0)
x
3 4 149
Optimal Solution
Simultaneous Equations (elimination by addition):
Protein X: 15x + 20y = 60
Fats Y: (-4)10x + 5y = 30
-25x + 0 = -60
x = 2.4
Substituting x in the 1st equation:
(15 x 2.4) + 20y = 60
y = 1.2
Optimal combination (point B): = 0.8 x 2.4 + 0.5 x 1.2
= 2.52
Calculate total cost (TC) at points A and C (for
comparison)
150