DEBREBIRHAN UNIVERSITY

COLLEGE OF BUSINESS AND

ECONOMICS
DEPARTMENT OF MANAGEMENT
MASTERS OF BUSINESS
ADMINISTRATION

OPERATIONS MANAGEMENT (MBA641)

CHAPTER 2 - LINEAR MATHEMATICAL PROGRAMMING
 LINEAR MATHEMATICAL PROGRAMMING
2.Linear Programming Models
Unit Objectives:
➢ Recognize problems that can be solved using LP
models.
➢ Formulate a LP model in mathematical terms.
➢ Solve Linear Programming Problems (LPP) using
both graphic and simplex approach.
➢ Explain special cases in both graphic and simplex
techniques.
➢ Formulate the dual of a problem, read and
interpret the solution to a dual problem, and relate
the dual solution to the prime solution
➢ Perform sensitivity analysis
 LINEAR MATHEMATICAL PROGRAMMING
2.1 INTRODUCTION
➢ Developed by Denting in 1940
➢ The term linear implies that all the mathematical relations used in the
problem are linear or straight-line relations, while the term
programming refers to the method of determining a particular
program or plan of action.
➢ Taken as a whole, the term linear programming refers to a family of
mathematical techniques for determining the optimum allocation of
resources and obtaining a particular objective when there are
alternative uses of the limited or constrained resources.
➢ LP: refers to a family of mathematical techniques for choosing the
best alternative from a set of feasible alternative, in situations in
which the objective function as well as the constraints can be
expressed as linear mathematical function.
 LINEAR MATHEMATICAL PROGRAMMING

➢ LP: is a branch of mathematical programming which is

designed to solve optimization problems where all the
constraints as well as the objectives are expressed as
linear function.
➢ LP: is a mathematical process that has been developed to
help management in decision making involving the
efficient allocation of scarce resources to achieve a
certain objective.
➢ LP: is a mathematical technique designed to aid
managers in allocating scarce resources (such as labor,
capital, or energy) among competing activities.
2.2 LINEAR PROGRAMMING MODELS

➢ Linear programming models are mathematical representations

of LP problems.
➢ Linear programming models have certain characteristics in
common.
COMPONENTS OF LP MODELS
▪Objective function,
▪Decision variables,
▪ Constraints and
▪Parameters.
ASSUMPTIONS OF LP MODELS
• Linearity (proportionality)
• Divisibility (Continuity)
• Certainty
• Additivity
• Non-negativity
LINEAR MATHEMATICAL PROGRAMMING

1) Objective and Objective Function

➢ The objective in problem solving is the
criterion by which all decisions are evaluated.
It provides the focus for problem solving.
2) Decision variables:
➢ They represent unknown quantities to be
solved for. The decision maker can control the
value of the objective, which is achieved
through choices in the levels of decision
variables. For example, how much of each
product should be produced in order to
obtain the greatest profit?
LINEAR MATHEMATICAL PROGRAMMING
3) Constraints:
➢ The decision variables in an LP problem is subject to certain
restrictions or limits coming from a variety of sources. The
restrictions may reflect
▪ Availabilities of resources (e.g., raw materials, labor time, etc.),
▪ Legal or contractual requirements (e.g., product standards, work
standards,),
▪ Technological requirements (e.g., necessary compressive
strength or stretchable strength) or they may reflect other limits
based on forecasts, customer orders, company policies, and so
on.
➢ In LP model, the restrictions are referred to as constraints. Only
solutions that satisfy all constraints in a model are acceptable and
are referred to as feasible solutions.
➢ The optimal solution will be the one that provides the best value for
the objective function.
 LINEAR MATHEMATICAL PROGRAMMING
❖ Generally speaking, a constraint has four elements:
➢ A right hand side (RHS) quantity that specifies the limit for that
constraint. It must be a constant, not a variable.
➢ An algebraic sign that indicates whether the limit is an upper
bound that cannot be exceeded, a lower bound that is the lowest
acceptable amount, or an equality that must be met exactly.
➢ The decision variables to which the constraint applies.
➢ The impact that one unit of each decision variable will have on the
right-hand side quantity of the constraint.
❖ Constraints can be arranged into three groups:
➢ System constraints – involve more than one decision variable,
➢ Individual constraints – involve only one variable, and
➢ Non-negativity constraints – specify that no variable will be
allowed to take on a negative value. The non-negativity constraints
typically apply in an LP model, whether they are explicitly stated
or not.
LINEAR MATHEMATICAL PROGRAMMING
4) Parameters
• The objective function and the constraints consist of symbols that
represent the decision variables (e.g., X1, X2, etc.) and numerical
values called parameters.
• The parameters are fixed values that specify the impact that one
unit of each decision variable will have on the objective and on any
constraint it pertains to as well as the numerical value of each
constraint
ASSUMPTIONS OF LP MODELS
Linearity (proportionality)
• The linearity requirement is that each decision variable has a linear
impact on the objective function and in each constraint in which it
appears.
Divisibility (Continuity)
• The divisibility requirement pertains to potential values of decision
variables. It is assumed that non-integer values are acceptable.
LINEAR MATHEMATICAL PROGRAMMING
Certainty
• This requirement involves two aspects of LP models. One aspect
relates to the model parameters, i.e., the numerical values. It is
assumed that these values are known and constant.
• The other aspect is the assumption that all relevant constraints
have been identified and represented in the model.
Additivity
• The value of the objective function and the total amount of each
resource used (or supplied), must be equal to the sum of the
respective individual contributions (profit or cost) by decision
variables.
Non-negativity
• It assumes that negative values of variables are unrealistic and,
therefore, will not be considered in any potential solutions. Only
positive values and zero will be allowed and the non-negativity
assumption is inherent in LP models.
 LINEAR MATHEMATICAL PROGRAMMING
2.1.4 Advantages of Linear Programming
➢ LP helps in attaining the optimum use of scarce productive
resources. It also indicates how a decision maker can employ
productive resources effectively by selecting and allocating these
resources.
➢ LP techniques improve quality of decisions. The decision making
approach of the user of this technique becomes more objective and
less subjective.
➢ LP also helps in re-evaluation of a basic plan for changing
conditions. If conditions change when the plan is carried out, they
can be determined so as to adjust the remainder of the plan for best
results.
➢ Highlighting of bottlenecks in the production process is one of the
most advantages of this technique. For example, when a bottleneck
occurs, some machines can not meet demand while others remain
idle for some of the time.
 LINEAR MATHEMATICAL PROGRAMMING
2.1.5 Limitations of Linear Programming
➢ LP treats all relationships among decision variables as linear. However,
generally neither the objective functions nor the constraints in real-life
situations concerning business and industrial problems are linearly
related to variables.
➢ While solving an LP model, there is no guarantee that we will get
integer valued solutions. For example, in finding out how many men
and machines would be required to perform a particular job, a non
integer valued solution will be meaningless.
➢ An LP model does not take in to consideration the effect of time and
uncertainty. Thus, the LP model should be defined in such a way that
any change due to internal as well as external factors can be
incorporated.
➢ It deals with only with a single objective, whereas in real-life situations
we may come across conflicting multi-objective problems.
➢ Parameters appearing in the model are assumed to be constant but, in
real life situation they are frequently neither known nor constant.
LINEAR MATHEMATICAL PROGRAMMING
2.1.6 FORMULATING LP MODELS
Linear programming algorithms (solution techniques) are widely used
and understood and computer packages are readily available for
solving LP problems.
Steps in formulating LP models:
1. Problem definition: involves the determination of the specific
objective of the linear programming problem. It is necessary to decide
the problem is maximization or minimization.
2. Identify the decision variables: involves the representation of
unknown quantity by the letter
3. Formulate the objective function: in formulating the objective
function, make sure that;
▪ All the decision variable are represented in the objective function
▪ All terms in the objective function must be inclusive with variables
▪ The unit of measurement of all coefficients in the objective function
must be the same.
LINEAR MATHEMATICAL PROGRAMMING

4. Identify and formulate the constraint:

▪ Find a mathematical expression that represents any limited
resources or constraints of unknowns.
▪ Determine appropriate values for the parameters, and determine
whether an upper limit, lower limit, or equality is called for.
▪ Include any additional constraints on the unknowns that are not
explicitly stated in the problem but are implicitly from the context
of the problem.
▪ Indicate the non-negativity constraints.
5. Building and validating the model
❖Potential sources of information include historical records,
interviews with managers and staff, and data collection. Validating the
model will involve a critical review of the output, perhaps under a
variety of inputs, in order to decide if the results are reasonable.
LINEAR MATHEMATICAL PROGRAMMING

General form of LPM

➢ The general LPM with n decision variables and m
constraints can be stated in the following form.

Max (Min) Z= c1x1+c2x2+…+cnxn-----objective function

Subject to
a11x1+a12x2+…+a1nxn.(≤ = ≥) b1
a21x1+a22x2+…+a2nxn.(≤ = ≥) b2

am1x1+am2x2+…+amnxn.(≤ = ≥) bm
x1,x2,x3… xn ≥ 0 non-negativity
LINEAR MATHEMATICAL PROGRAMMING

2.1.7 LINEAR PROGRAMMING APPLICATIONS

➢ Production management (product mix, blending
problems, production planning, Assembly line
balancing…),
➢ Marketing management (media selection, traveling
salesman problem, physical distribution),
➢ Financial management (portfolio selection, profit
planning),
➢ Agricultural application, military applications,
personnel management (staffing problem,
Determination of equitable salary and etc).
LINEAR MATHEMATICAL PROGRAMMING
➢ Product Mix :Organizations often produce similar services that use the same resources.
For example, labor, material cost, etc. because of limited resources available during any
time period a decision must be made concerning how much of each product to produce or
make available. Linear programming answers what mix of output (or service) will
maximize profit given the availability of scarce resources
➢ Diet problem :It usually involves the mixing of raw materials or other ingredients to obtain
an end product that has certain characteristics. For example, food processors and dieticians
generally are concerned with meeting dietary needs in food products. what mix of inputs
will achieve the desired results in the output for the least cost?
➢ Portfolio selection :These problems generally involve allocating a fixed dollar amount
among a variety of investments, such as bonds, sockets, real states, etc. The goal usually is
to maximize income or total return. The problems take on an added dimension when certain
other requirements are specified (for example, no more than 40 percent of the portfolio can
be invested in bonds).
➢ Blending problems :They are very similar to diet problems. Strictly speaking, however,
blending problems have additional requirement, i.e. to achieve a mix that have specific
consistency. For example, how many quarts of the different juices each with different sugar
content proportion must be mixed together to achieve one gallon that has a sugar content of
17 percent?
 LINEAR MATHEMATICAL PROGRAMMING
EXAMPLE 1. A firm that assembles computer and computer equipment is about to start
production of two new microcomputers. Each type of microcomputer will require
assembly time, inspection time, and storage space. The amount of each of these resources
that can be devoted to the production of the micro computers is limited. The manager of
the firm would like to determine the quantity of each microcomputer to produce in
order to maximize the profit generated by the sales of these microcomputers. The
manager has collected the following information from design and manufacturing
personnel.
Type I Type II
Profit per unit $60 $50
Assembly time per unit 4 hours 10 hours
Inspection time per unit 2 hours 1 hours
Storage space per unit 3 cubic feet 3 cubic feet

The manager also has acquired information on the availability of company

resources. The weekly amount are;
Resources Amount available
Assembly time 100 hours
Inspection time 22 hours
Storage space 39 cubic feet
Note: all of the two types of microcomputer that can be produced can be sold. Formulate LPM
LINEAR MATHEMATICAL PROGRAMMING
Solution
Step1: Problem definition
The firm wants to maximize their profit by producing the two type of
micro-computer. Therefore, the objective is profit maximization.
Step2. Identify decision variables
Based on the statement, the manager would like to determine the
quantity of each microcomputer to produce. The decision variable are
the quantity of each type of computer. thus,
X1 = quantity of type one mc to produce.
X2 = quantity of type two mc to produce.
Step3. Determine Objective Function
The profit per unit of type1 is $60, and type 2 is $50. so the
appropriate objective function is:
Max Z= 60X1 + 50X2
This is because, each unit of X1 contributes $60 and X2
contributes $50 to objective function
LINEAR MATHEMATICAL PROGRAMMING

Step 4. Identify and formulate the constraints

Here we have two constraints: structural and non-negativity constraints.
There are three structural constraint of resources with limited availability:
assembly time, inspection time, and storage space.
4X1 + 10X2 ≤ 100 ---------- assembly time
2X1 + X2 ≤ 22 --------------- inspection time
3X1 + 3X2 ≤ 39 ------------- storage space
X1, X2 ≥ 0 -------------------- non-negativity
Step 5. Building and validating the model
Max Z= 60X1 + 50X2
Subject to
4X1 + 10X2 ≤ 100
2X1 + X2 ≤ 22
3X1 + 3X2 ≤ 39
X1, X2 ≥ 0
LINEAR MATHEMATICAL PROGRAMMING

Example
The agriculture research institute suggested to a farmer
to spread out at least 4800kg of a special phosphate
fertilizer and not less than 7200kg of a special nitrogen
fertilizer to raise productivity of crops in his field. There
are two sources for obtaining these- mixtures A and B.
both of these are available in bags weighing 100kg each
and they cost birr 40 and birr 24 respectively. Mixture A
contains phosphate and nitrogen equivalent of 20kg and
80kg respectively, while mixture B contains these
ingredients equivalent of 50kg each. Formulate LPM
LINEAR MATHEMATICAL PROGRAMMING
Solution
Step1: Problem definition
The farmer wants to attain the requirement suggested by agriculture
institute at minimum cost. Therefore, the objective is cost minimization
Step2. Identify decision variables
Based on the statement, the farmer would like to determine the
quantity of mixture A and B to be purchase. The decision variable are
the quantity of mixture A and B. thus,
X1 = quantity of mixture A to purchase.
X2 = quantity of mixture B to purchase.
Step3. Determine Objective Function
The cost per unit of mixture A is 40, and mixture B is 24. so the
appropriate objective function is:
Minimize cost= 40X1 + 24X2
This is because, each unit of X1 costs 40 and X2
Costs 24 to objective function
LINEAR MATHEMATICAL PROGRAMMING
Step 4. Identify and formulate the constraints
Here we have two constraints: structural and non-negativity constraints.
There are two structural constraint of minimum requirements suggested by
the agriculture institute: Phosphate and Nitrogen requirement .
20X1 + 50X2 ≥ 4800 -------- Phosphate requirement
80X1 + 50X2 ≥ 7200 -------- Nitrogen requirement
X1, X2 ≥ 0 -------------------- non-negativity
Step 5. Building and validating the model
Min C= 40X1 + 24X2
Subject to:
20X1 + 50X2 ≥ 4800
80X1 + 50X2 ≥ 7200
X1, X2 ≥ 0
 LINEAR MATHEMATICAL PROGRAMMING
2) ABC private limited company is engaged in the production of
power and traction transformers. Both of these categories of
transformers pass through three basic processes: core
preparation, core to coil assembly, and vapor phase drying. A
power transformer yields a contribution of Birr 50,000 and
traction transformer contributes Birr 10,000. The time required
in the production of these two products in terms of hours for
each of the processes is as follows.
Power transformer Traction Transformer
Core preparation 75 15
Core to Coil Assembly 160 30
Vapor Phase Drying 45 10

If the capacities available are 1000, 1500, and 750 machine

hours in each processes respectively, formulate the problem as
LP?
LINEAR MATHEMATICAL PROGRAMMING
Solution
Step1: Problem definition
The firm wants to maximize their profit by producing power and traction
transformers. Therefore, the objective is profit maximization.
Step2. Identify decision variables
Since the products to be produced are power and traction transformers
using the available resource to attain the objective set, we consider them as
decision variables. This is because the organization’s problem here is how
many of each product to produce in order to attain the objective, which
requires the management decision.
Let X1 = the no of power transformers to be produced.
X2 = the no of traction transformer to be produced
Step3. Determine Objective Function .
This is because, each unit of X1 contributes Birr 50,000 and X2
contributes Birr 10,000 to objective function.
Hence,
Zmax = 50,000X1+ 10,000X2
LINEAR MATHEMATICAL PROGRAMMING
Step 4. Identify and formulate constraints
Here we have two constraints: structural and non-negativity
constraints. The structural constraint is the amount of machine
hours available in each process.
75 X1 + 15 X2 ≤ 1000 hrs- Core preparation process
160 X1 + 30 X2 ≤ 1500 hrs- Core to Coil Assembly
45 X1 + 10 X2 ≤ 750 hrs- Vapor Phase Drying
X1, X2 ≥ 0
Step 5. Building and validating the model
Z max = 50,000 X1 + 10,000X2
Subject to:
75 X1 + 15X2 ≤ 1000 hrs
160 X1 + 30X2 ≤ 1500 hrs
45 X1 + 10X2 ≤ 750 hrs
x1, x2≥0
LINEAR MATHEMATICAL PROGRAMMING
Investment Application : An individual investor has Birr 70,000 to divide
among several investments. The alternative investments are municipal
bonds with an 8.5% return, certificates of deposits with a 10% return,
Treasury bill with a 6.5% return, and income bonds with a 13% return.
The amount of time until maturity is the same for each alternative.
However, each investment alternative has a different perceived risk to the
investor; thus it is advisable to diversify. The investor wants to know how
much to invest in each alternative in order to maximize the return. The
following guidelines have been established for diversifying the investment
and lessening the risk perceived by the investor.
A. No more than 20% of the total investment should be in an income bonds.
B. The amount invested in certificates of deposit should not exceed the
amount invested in other three alternatives.
C. At least 30% of the investment should be in treasury bills and certificates
of deposits.
D. The ratio of the amount invested in municipal bonds to the amount
invested in treasury bills should not exceed 1/3. The investor wants to
invest the entire Birr 70,000
Required: Formulate a LP model for the problem.
LINEAR MATHEMATICAL PROGRAMMING
Solution
Step1: Problem definition
The investor wants to maximize his return by investing 70,000 birr. Therefore, the
objective is return maximization.
Decision variables : Four decision variables represent the monetary amount invested in
each investment alternative.
Let X1, X2, X3 and X4 represent investment on municipal bonds, certificates of deposits,
Treasury bill, and income bonds respectively.
Objective function : The problem is maximization because from the word problem we know
that the objective of the investor is to maximization return from the investment in the
four alternatives. Therefore, the objective function is expressed as:
Zmax = 0.085 X1+ 0.1X2+ 0.065X3+0.13X4
Where,
Z = total return from all investment

0.085 X1=return from the investment in municipal bonds.

0.065 X3=return from the investment in treasury bills

0.130 X4=return from the investment in income bonds
Model Constraints : In this problem the constraints are the guide lines established for
diversifying the total investment. Each guideline is transformed in to mathematical
constraint separately.
LINEAR MATHEMATICAL PROGRAMMING

Guideline 1 above is transformed as: X4 ≤20 %(70,000) ⇒ X4 ≤14,000

Guideline 2: X2≤ X1 +X3+ X4 ⇒ X2 - X1 -X3- X4≤ 0
Guideline 3: X2+ X3 ≥ 30 %( 70,000) ⇒ X2 + X3 ≥ 21,000
Guideline 4: X1/ X3≤ 1/3⇒ 3X1≤X3⇒3X1-X3≤0
Finally, X1+ X2+ X3+X4 = 70,000, because the investor’s money equals to the
sum of money invested in all alternatives.
This last constraint differs from ≤ and ≥ inequalities previously developed in
that there is a specific requirement to invest an exact amount. Therefore,
the possibility to invest more or less than Birr 70,000 is not considered.
This problem contains all three types of constraints possible in LP problems: ≤,
≥ and =. As this problem demonstrates there is no restriction on mixing
these types of constraints.
The complete LPM for this problem can be summarized as:
LINEAR MATHEMATICAL PROGRAMMING

Zmax = 0.085 X0 1+ 0.1X2+ 0.065X3+0.13X4

Subjected to:
X4 ≤ 14,000
X2 - X1 -X3 - X4 ≤ 0
X2 + X3≥21,000
3X1-X3 ≤ 0
X1 + X2 + X3 + X4 = 70,000,
X1, X2, X3, X4≥ 0
LINEAR MATHEMATICAL PROGRAMMING
Marketing Application : Supermarket store chain has hired an advertising firm
to determine the types and amount of advertising it should have for its stores.
The three types of advertising available are radio and television commercials,
and news papers advertisements. The retail chain desires to know the number of
each type of advertisement it should purchase in order to maximize exposure. It
is estimated that each ad or commercial will reach the following potential
audience and cost the following amount.
Exposure
Type of Advertisement (people /ad or commercial) Cost
Television commercial 20,000 Birr 15,000
Radio commercial 12,000 6,000
News paper advertisement 9,000 4,000
The company must consider the following resource constraints.
1. The budget limit for advertising is Birr 100,000
2. The television station has time available for 4 commercials.
3. The radio station has time available for 10 commercials.
4. The news paper has space available for 7 ads.
5. The advertising agency has time and staff available for producing no more
than a total of 15 commercials and/or ads.
LINEAR MATHEMATICAL PROGRAMMING

Step1: Problem definition

The retail chain desires to maximize exposure Therefore, the
objective is exposure maximization.
Decision variables
Let X1 = number of television commercials
X2 = number of radio commercials
X3= number of news paper ads
Objective function: It is not only profit which is to be maximized. In
this problem the objective to be maximized is audience exposure.
Zmax = 20,000x1 + 12,000x2 + 9,000x3, where
Z = total level of audience exposure
20,000x1 = estimated number of people reached by television
commercials
12,000x2 = estimated number of people reached by radio
commercials
9,000x3 = estimated number of people reached by news paper ads
LINEAR MATHEMATICAL PROGRAMMING
Model Constraints
Budget Constraints: 15,000x1 + 6,000x2 + 4,000x3 ≤Birr 100,000
Capacity constraint : Television commercials and radio commercials are limited
to 4 and 10 respectively and news paper ads are limited to 7.
X1 ≤ 4 television commercials
X2 ≤ 10 radio commercials
X3 ≤ 7news paper ads
Policy constraint : The total number of commercials and ads can not exceed 15
X 1 + X2 + X3≤ 15
The complete linear programming model for this problem is summarized as:
Zmax = 20,000X1 + 12,000X2 + 9,000X3
Sub. To:

15,000X1 + 6,000X2 + 4,000X3≤Birr 100,000

X1 ≤4
X2 ≤10
X 3≤7
X 1 + X2 +X3 ≤15
X1, X2 , X3≥0
 LINEAR MATHEMATICAL PROGRAMMING
Chemical mixture : A chemical corporation produces a chemical mixture for the
customer in 1000- pound batches. The mixture contains three ingredients-
Zinc, mercury and potassium. The mixture must conform to formula
specifications (i.e., a recipe) supplied by a customer. The company wants to
know the amount of each ingredient to put in the mixture that will meet all
the requirements of the mix and minimize total cost.
The customer has supplied the following formula specifications for each batch of
mixture.
1. The mixture must contain at least 200 lb of mercury
2. The mixture must contain at least 300 lb of zinc
3. The mixture must contain at least 100 lb of potassium
The cost per pound of mixture is Birr4, 8 and 9 for mercury, zinc and potassium
respectively.
Required: Formulate LPM for the problem
Solution
Step1: Problem definition
The company wants to produces a chemical mixture at minimum cost.
 LINEAR MATHEMATICAL PROGRAMMING

Decision variables : The model of this problem consists of three

decision variables representing the amount of each ingredient
in the mixture.
X1 = number of lb of mercury in a batch
X2 = number of lb of zinc in a batch
X3 = number of lb of potassium in a batch
Objective function
Zmin = 4x1 + 8x2 + 9x3
Constraints

X1 ≥200 lb… specification 1

X2≥300 lb… specification 2
X3≥ 100 lb… specification 3
Finally, the sum of all ingredients must equal 1000 pounds. X1 +

x2 + x3 = 1000 lb
LINEAR MATHEMATICAL PROGRAMMING

The complete LPM of the problem is:

Zmin = 4x1 + 8x2 + 9x3
Subject to:
X1≥200 lb
X2≥ 300 lb
X3 ≥ 100 lb
x1 + x2 + x3 = 1000 lb
X1 , x2 , x3 ≥0
LINEAR MATHEMATICAL PROGRAMMING
2.1.3 Solving LP Model
➢ An optimal, as well as feasible solution to an LP problem is
obtained by choosing from several values of decision variables
x1,x2…xn , the one set of values that satisfy the given set of
constraints simultaneously and also provide the optimal
(maximum or minimum) values of the given objective function.
Graphical approach/methods
➢ Graphical linear programming is a relatively straightforward
for determining the optimal solution to certain linear
programming problems involving only two decision variables.
❖ Graphical method has the following advantages:

✓ It is simple
✓ It is easy to understand, and
✓ It saves time.
Example: Solve the following LPM using graphic approach
Max Z= 60X1 + 50X2
Subject to
AT: 4X1 + 10X2 ≤ 100
IT : 2X1 + X2 ≤ 22
SS: 3X1 + 3X2 ≤ 39
NN: X1, X2 ≥ 0
Graphical solution method involves the following steps.
Steps in graphic solution
1. Plot each of the constraint on the graph
▪ 1st plotting the non-negativity of constraints, the area feasibility for
these two constraint has been shaded in order to plot the remaining
constraint;
▪ Convert the inequalities in to an equality
▪ Set x1 = 0, and find the value for x2
▪ Set x2 = 0, and find the value for x1
▪ plot the line to the graph
▪ Determine the feasible solution space and shaded it.
LINEAR MATHEMATICAL PROGRAMMING

Graphical Analysis – the Feasible Region

X2

The non-negativity constraints

X1

39
LINEAR MATHEMATICAL PROGRAMMING
LINEAR MATHEMATICAL PROGRAMMING
Step 2. Identify the feasible region:
▪ The feasible region is the solution space that satisfies all the
constraints simultaneously. It is the intersection of the entire
region represented by all constraints of the problem. We
shade in the feasible region depending on the inequality sign.
▪ If the inequality sign is less than or equal to, it represents the
region of the plane below the plotted line. If the inequality
sign is greater than or equal to, it represents the region of the
plane above the plotted line
Step 3. Locate the optimal solution:
▪ The feasible region contains an infinite number of points that
would satisfy all the constraints of the problem. Point that will
make the objective function optimum will be our optimal
solution. This point is always found among the corner points
of the solution space.
LINEAR MATHEMATICAL PROGRAMMING

➢ Once the constraints are plotted and feasible region is determined,

we use either of the two graphic methods of Graphic approach to
find a solution for LP model consisting of only two decision
variables: i) The extreme point enumeration method ii) The
objective (Iso-profit or cost) function line approach
 LINEAR MATHEMATICAL PROGRAMMING
1)The extreme point approach
➢ It states that for problems that have a single optimal solution, a
solution will occur at one of the extreme, or corner point. If it has
multiple optimal solutions, at least one will occur at the corner
point.
Steps to be followed
❖ Graph the possible problem
❖ Identify the feasible area
➢ Determine the value of decision variables at each corner point in the
feasible solution space. Some times this can be done by inspection
(observation), usually it is done using simultaneous equation.
➢ Substitute the values of the decision variable at each corner point in
the objective function to obtain its value at each corner point.
➢ Select the one with the highest value of the objective function for
maximization problem or the lowest value for minimization problem
LINEAR MATHEMATICAL PROGRAMMING

Interpretation:
▪ For a firm to maximize its profit (740), it should produce 9 units of the
Model I microcomputer and 4 units of model II.
▪ what are the values of decision variables at each corner point? (Hint:
Solve simultaneously those lines which intersected each other). Can
you mention some of the characteristics of the LP graphs consisting of
sign? ≤
LINEAR MATHEMATICAL PROGRAMMING
Objective function approach
Steps
➢ Graph the constraints
➢ Identify the feasible solution space
➢ Set the objective function equal to same amount divisible by each of the
objective function coefficient. This will yield integer value for x1, and x2
that helps to plot the line simply.
➢ Now determine the optimal point by moving a line away from the origin
(for maximization problem) or towards the origin (for minimization
problem) parallel to the objective function line.
➢ After identifying the optimal point determine which two constraints
intersect there.
➢ Solve their equation simultaneously to obtain the value of x1 and x2 at the
optimal point
➢ Substitute the values obtained in the previous step in to the objective
function to determine the value of the objective function at the optimal
LINEAR MATHEMATICAL PROGRAMMING

Example 2: given the LPM:

Min C = 20X1 + 30X2
Subject to:
6X1 + X2 ≥ 12
7X1 + 7X2 ≥ 49
3X1 + 11X2 ≥ 33
X1, X2 ≥ 0
A. Find the optimal values of the decision variables and minimum
cost using both the objective function approach and the extreme
point approach.
B. Determine the amount of surplus associated with each constraint.
Note: surplus is the amount by which the optimal solution causes a
greater than or equal to constraint to exceed the required minimum
amount. It is the amount by which the left-hand side of a constraint
exceeds the right hand side.
 LINEAR MATHEMATICAL PROGRAMMING
SLACK VERSUS SURPLUS
Slack
➢ IT is the amount of a scarce resource that is unused by a given
solution. Slack can potentially exist in a ≤ constraint. Slack variables
are considered in the objective function by using a coefficient of zero
for each of them. When all the constraints are written as equalities
after adding a slack variable to each of them, the linear program is
said to be in standard form.
Surplus
➢ IT is the amount by which the optimal solution causes a constraint
to exceed the required minimum amount. It can be determined in the
same way that slack can, i.e., substitute the optimal values of the
decision variables into the left side of the constraint and solve. The
difference between the resulting value and the original right hand
side amount is the amount of surplus. Surplus should also be
accounted for in the objective function by using coefficients of zero
like wise.
LINEAR MATHEMATICAL PROGRAMMING

Galaxy manufactures two toy models: Space Ray and Zapper.

Resources are limited to 1000 pounds of special plastic and 40 hours
of production time per week. Total production cannot exceed 700
dozens. Number of dozens of Space Rays cannot exceed number of
dozens of Zappers by more than 350.
Space Rays requires 2 pounds of plastic and 3 minutes of labor per
dozen. Zappers requires 1 pound of plastic and 4 minutes of labor per
dozen.
The current production plan calls for Producing as much as possible
of the more profitable product, Space Ray ($8 profit per dozen). Use
resources left over to produce Zappers ($5 profit per dozen), while
remaining within the marketing guidelines. Management is seeking a
production schedule that will increase the company’s profit.
Formulate LPM
LINEAR MATHEMATICAL PROGRAMMING

The Galaxy Linear Programming Model

Decisions variables:
X1 = Weekly production level of Space Rays (in dozens)
X2 = Weekly production level of Zappers (in dozens).

Objective Function:
Weekly profit, to be maximized

49
LINEAR MATHEMATICAL PROGRAMMING

The Galaxy Linear Programming Model

Max 8X1 + 5X2 (Weekly profit)
subject to
2X1 + 1X2  1000 (Plastic)
3X1 + 4X2  2400 (Production Time)
X1 + X2  700 (Total production)
X1 - X2  350 (Mix)
Xj> = 0, j = 1,2 (Nonnegativity)

50
LINEAR MATHEMATICAL PROGRAMMING

Graphical Analysis – the Feasible Region

X2

The non-negativity constraints

X1

51
 LINEAR MATHEMATICAL PROGRAMMING
Graphical Analysis – the Feasible Region
X2

1000 The Plastic constraint

2X1+X2  1000
700 Total production constraint:
X1+X2  700 (redundant)
500

Infeasible
Production Feasible
Time
3X1+4X2  2400 X1
500 700

52
 LINEAR MATHEMATICAL PROGRAMMING

Graphical Analysis – the Feasible Region

X2
1000 The Plastic constraint
2X1+X2  1000
700 Total production constraint:
X1+X2  700 (redundant)
500
Infeasible
Production mix
constraint:
Production Feasible X1-X2  350
Time
3X1+4X2 2400
X1
500 700
Interior points. Boundary points. Extreme points.
• There are three types of feasible points 53
LINEAR MATHEMATICAL PROGRAMMING
Summary of the optimal solution
Space Rays = 320 dozen
Zappers = 360 dozen
Profit = $4360
This solution utilizes all the plastic and all the production
hours.
Total production is only 680 (not 700).

Space Rays production exceeds Zappers production by only

40 dozens.

54
LINEAR MATHEMATICAL PROGRAMMING

Graphical approach/methods
Exercise: solve graphically the following LPM
Minimize C= 3X1 + 5X2
Subject to :
Minimize = 40X1 + 24X2----------Total cost
-3X1 + 4X2 ≤ 12 Subject to:
2X1 + 3X2 ≥ 12 20X1 + 50X2 ≥ 4800 -------- Phosphate requirement
80X1 + 50X2 ≥ 7200 -------- Nitrogen requirement
2X1 – X2 ≥ -2 X1, X2 ≥ 0
X1 ≤ 4 : X2 ≥ 2
X1, X2 ≥ 0
Maximize Z = 10X1 + 15X2
Subject to :
2X1 + X2 ≤ 26
2X1 + 4X2 ≤ 56
X1 – X2 ≥ -5
X1, X2 ≥ 0
LINEAR MATHEMATICAL PROGRAMMING

Graphical approach/methods
Special issues
This section points out some special issues that may arise during the
formulation or solution of LP problems. These issues are:
Unbounded problems:
an unbounded problem exists when the value of the objective function can
be increased without limit. The reason for it may be concluded to wrong
formulation of the problem such as incorrectly maximizing instead of
minimizing and/or errors in the given problem. Checking or rethinking the
problem statement will resolve the problem.
Example
Max Z = 10X1 + 20X2
Subject to:
2X1 + 4X2 ≥ 16
X1 + 5X2 ≥ 15
X1, X2 ≥ 0
LINEAR MATHEMATICAL PROGRAMMING

Graphical approach/methods
Unbounded problems:
LINEAR MATHEMATICAL PROGRAMMING

Graphical approach/methods
Redundant Constraint:
A constraint that does not form a unique point of the boundary of
the feasible solution space. A constraint is redundant if its
removal would not alter the feasible solution space.
Example
Max Z = 3X1 +2X2
Subject to:
X1 ≤ 25
2X1 +3X2 ≤ 60
2X1 +X2 ≤ 20
X1, X2 ≥ 0
Here, the 1st and 2nd constraints are redundant because they do
not form a unique boundary of the feasible solution space’
LINEAR MATHEMATICAL PROGRAMMING

Graphical approach/methods
Redundant Constraint:
LINEAR MATHEMATICAL PROGRAMMING

Graphical approach/methods
Infeasibility:
➢ it means there are no points that simultaneously
satisfy all constraints in the problem. In some cases
after plotting all the constraints on the graph, feasible
area (common region) that represents all the
constraints of the problem cannot be obtained.
Example
Max Z = 3X1 +2X2
Subject to:
2X1 +X2 ≤ 2
3X1 +4X2 ≥ 12
X1, X2 ≥ 0
LINEAR MATHEMATICAL PROGRAMMING
Graphical approach/methods
Infeasibility:
LINEAR MATHEMATICAL PROGRAMMING

Graphical approach/methods
Multiple optimal solutions:
➢ if objective function fails on more than one optimal point there
solution is said to be multiple optimal solution. i.e., different
combination of values of the decision variable will yield the same
optimal value for the objective function. The only way this
situation can exist when the slope of the objective function and
one of the constraints equation are the same.
Example
Max Z = 8X1 + 16X2
Subject to:
X1 +X2 ≤ 200
3X1 + 6X2 ≤ 900
X1 ≤ 125
X1, X2 ≥ 0
LINEAR MATHEMATICAL PROGRAMMING

Graphical approach/methods
Multiple optimal solutions:
LINEAR MATHEMATICAL PROGRAMMING

2. The simplex method

A. Maximization problem with all ≤ constraints
➢ The simplex method is an algebraic procedure that starts with a
feasible solution that is not optimal and systematically moves
from one feasible solution to another until an optimal solution
obtained.
Steps in solving LPP using simplex method
1. Formulation the LPM of the real world problem
2. Express the mathematical model of LPP in the standard form
by adding slack variables in the left hand side of the constraints
and assign a zero coefficient to these in the objective function.
3. Design the initial feasible solution. An initial basic feasible
solution is obtained by setting the decision variable to zero.
LINEAR MATHEMATICAL PROGRAMMING
2. The simplex method
4. Set up the initial simplex tableau:
➢List the variables across the top of the table and write the
objective function coefficient of each variable just above it.
➢There should be one row in the body of the table for each
constraint. list the slack variable in the basic column, one
per row.
➢In the Cj column, enter the objective function coefficient of
zero for each slack variable.
➢Compute values for row Zi
➢Compute values for Cj - Zi; index row/net evaluation row,
used to determine whether or not the current solution is
optimal or not.
LINEAR MATHEMATICAL PROGRAMMING

2. The simplex method

5. Test if the current solution is optimal or not. If the entire element in the
Cj – Zi row (index row) is negative or zeros, then the current solution is
optimal. If there exist some positive number, the current solution can be
further improved.
➢ Determine the entering variable: identifying the column with the largest
value in the Ci –Zi row of the simplex table. The column with the largest
possible entry in the Cj – Zi row is called key/pivot column. The non-
basic variable at the top of the key column is entering variable that will
replace a basic variable.
➢ Determine the departing/leaving variable: dividing each number in the
quantity column by the corresponding number in the key/pivot column
selected as entering variable. The row with the minimum positive ratio is
key row/pivot row. The corresponding variable in the key row (the
departing variable) will leave the basis.
➢ Identify the key/pivot element, the number that lies at the intersection of
the pivot column and pivot row of a given simplex tableau.
 LINEAR MATHEMATICAL PROGRAMMING
2. The simplex method
6. Evaluate the new solution by constructing a second simplex tableau. After
identifying the entering and departing variable, find the new basic feasible
solution by constructing a new simplex tableau from the current one.
7. If any of the numbers in Cj – Zi row are positive, repeat the steps (5-6)
again until an optimal solution has been obtained.
Solve the following LPM using simplex method
1. Max Z= 60X1 + 50 X2
Subject to
AT: 4X1 + 10X2 ≤ 100
IT : 2X1 + X2 ≤ 22
SS: 3X1 + 3X2 ≤ 39
NN: X1, X2 ≥ 0
2. Max Z = 40X1 + 35X2------- Profit
Subject to:
2X1 + 3X2 ≤ 60-------Row material constraint
4X1 + 3X2 ≤ 96-------Labor hours constraint
X1, X2 ≥ 0
2. The simplex method
. Max Z= 60X + 50 X +0S +0S +0S
1 2 1 2
Subject to
Initial table AT: 4X + 10X +S =100
1
IT : 2X + X +S =22
2 1
1 2 2
SS: 3X1 + 3X2 +S3 =39
NN: all variable ≥ 0
Basic V Cj 60 50 0 0 0 Quantity
X1 X2 S1 S2 S3
S1 0 4 10 1 0 0 100
S2 0 22
2 1 0 1 0
S3 0 39
3 3 0 0 1
Zi 0 0 0 0 0 0

Cj-Zi
60 50 0 0 0 Haile Y (PhD)
2. The simplex method
Second table
Basic V Cj 60 50 0 0 0 Quantity
X1 X2 S1 S2 S3
S1 0 0 8 1 -2 0 56
X1 11
60 1 1/2 0 1/2 0
S3 0 6
0 3/2 0 -3/2 1
Zi 60 30 0 30 0 660

Cj-Zi
0 20 0 -30 0
Haile Y (PhD)
2. The simplex method
Third table
Basic V Cj 60 50 0 0 0 Quantity
X1 X2 S1 S2 S3

S1 0 0 0 1 6 -16/3 24

X1 60 1 0 0 1 -1/3 9

X2 50 4
0 1 0 -1 2/3

Zi 60 50 0 10 40/3 740

Cj-Zi 0 0 0 -10 -40/3

Haile Y (PhD)
LINEAR MATHEMATICAL PROGRAMMING

2. The simplex method

➢ A firm produces three products A, B and C each of which passes

through three departments’ fabrication, finishing and packaging.
Each unit of product A requires 3, 4 and 2; a unit product B
requires 5, 4 and 4; while each unit of product C requires 2, 4 and
5 hours respectively in the three departments. Every day, 60
hours are available in the fabrication department, 72 hours in the
finishing department and 100 hours in the packaging
departments. The unit contribution of product A is birr 5, of
product B is birr 10, and of product C is birr 8.
➢ Formulate the problem as an LPM and determine the number of
units of the product that should be made each day to maximize
contribution. Also determine if any capacity would remain
unutilized.
 LINEAR MATHEMATICAL PROGRAMMING

2. The simplex method

B. Simplex maximization with mixed constraints
The big M method – introducing slack, surplus and artificial
variable
Steps
➢ If any problem constraint has negative constraint on the right side, multiply
both by -1 to obtain a constraint with a non-negative constraint (if the
constraint is an inequality, this will reverse the direction of the inequality).
➢ Introduce a slack variable in each ≤ constraints
➢ Introduce a surplus variable and an artificial variable in each ≥ constraints
➢ Introduce an artificial variable in each = constraints
▪ Artificial variable do not represent any quantity relating to the decision
problem, they must be driven out of the system and must not remain in the
final solution. This can be ensured by assigning an extremely high cost to
them. Generally, a value M is assigned to each artificial variable, where M
represents a number higher than any finite number. ----- big M method
 LINEAR MATHEMATICAL PROGRAMMING
2. The simplex method
➢ Assigning objective function coefficients for artificial variables depends on
whether the goal is to maximize or minimize.
▪ In maximization problems, assigning a large negative contribution (- M)
will ensure that an artificial variable will not appear in the optimal solution.
In a minimization problem, assigning a large positive cost (M) will have a
similar effect.
➢ Form the simplex tableau for the modified problem and solve using the
simplex method
▪ List the variable in the order of; decision variable, slack variable/surplus
variable, and finally artificial variable.
▪ For basic variable column use artificial variables, and/or slack variable, and
/or surplus variable for the initial solution.
➢ Relate the solution of the modified problem to the original problem.
▪ If the modified problem has no solution, the original problem has no
solution
▪ If any artificial variables are non-zero in the solution to the modified
problem, then the original problem has no solution
LINEAR MATHEMATICAL PROGRAMMING

2. The simplex method

Example assume the following maximization problem
with mixed constraints
1. Max Z= 6X1 + 8X2
Subject to:
X2 ≤ 4
X1+ X2 = 9
6X1 + 2X2 ≥ 24
X1, X2 ≥ 0
2. Max Z= 4X1 + 6X2
Subject to:
X2 ≥ 30
X2 ≤ 100
2X1 + X2 = 140
X1, X2 ≥ 0
Slide 1.75
2.75

LINEAR MATHEMATICAL PROGRAMMING

In standard form
Max! 6X + 8Y + 0S1 + 0S3 - MA1 – MA3
Subject to: Y+ S1 = 4
X+Y + A1 = 9
6X+ 2Y –S3 + A3 = 24
All variables ≥ 0

Saunders, Lewis and Thornhill, Research Methods for Business Students, 5th Edition, © Mark Saunders, Philip Lewis and Adrian Thornhill 75
2009
Slide 1.76
2.76

LINEAR MATHEMATICAL PROGRAMMING

Initial table
BV CBV 6 8 0 0 -M -M Quantity
X Y S1 S3 A2 A3

S1 0 0 1 1 0 0 0 4
A2 -M 1 1 0 0 1 0 9
A3 -M 6 2 0 -1 0 1 24

Z -7M -3M 0 M -M -M -33M

C-Z 6+ 7M 8+3M 0 -M 0 0

Saunders, Lewis and Thornhill, Research Methods for Business Students, 5th Edition, © Mark Saunders, Philip Lewis and Adrian Thornhill 76
2009
Slide 1.77
2.77

LINEAR MATHEMATICAL PROGRAMMING

Second table
BV CBV 6 8 0 0 -M -M Quantity
X Y S1 S3 A2 A3

S1 0 0 1 1 0 0 0 4
A2 -M 0 2/3 0 1/6 1 0 5
X 6 1 1/3 0 -1/6 0 1 4

Z 6 2-2M/3 0 -1M/6 -1 -M -M 24 - 5M
C-Z 0 6+2M/3 0 1+ M/6 0 0

Saunders, Lewis and Thornhill, Research Methods for Business Students, 5th Edition, © Mark Saunders, Philip Lewis and Adrian Thornhill 77
2009
Slide 1.78
2.78

LINEAR MATHEMATICAL PROGRAMMING

Third table
BV CBV 6 8 0 0 -M Quantity
X Y S1 S3 A2

Y 0 0 1 1 0 0 4
A2 -M 0 0 -2/3 1/6 1 7/3
X 6 1 0 -1/3 -1/6 0 8/3

Z 6 8 6 + 2M/3 -M/6 -1 -M 48 -7M/3

C-Z 0 0 -6-2M/3 1+ M/6 0

Saunders, Lewis and Thornhill, Research Methods for Business Students, 5th Edition, © Mark Saunders, Philip Lewis and Adrian Thornhill 78
2009
Slide 1.79
2.79

LINEAR MATHEMATICAL PROGRAMMING

Fourth table
BV CBV 6 8 0 0 Quantity
X Y S1 S3
Y 8 0 1 1 0 4
S3 0 0 0 -4 1 14
X 6 1 0 -1 0 5

Z 6 8 2 0 62
C-Z 0 0 -2 0

Saunders, Lewis and Thornhill, Research Methods for Business Students, 5th Edition, © Mark Saunders, Philip Lewis and Adrian Thornhill 79
2009
LINEAR MATHEMATICAL PROGRAMMING
2. The simplex method
C. Minimization linear programming problems
Steps
1. Formulate the LPM, and express in the standard form by introducing surplus and
artificial variables in the left hand side of the constraints.
➢ Assign a 0 and M as coefficient for surplus and artificial variable respectively
in the objective function. M is considered a very large number so as to finally
drive out the artificial variable out of basic solution.
2. Set up the initial simplex tableau and initial solution
3. Test for optimality of the solution. If all the entries of C – Z row are positive and
zero, the solution is optimal. If at least one of the C – Z number is less than zero,
the current solution can be further improved.
➢ Determine the variable to enter the basic solution. Identify the column with the
largest number with negative sign in the C – Z row of the table.
➢ Determine the departing variable from the basic solution. If an artificial variable
goes out of solution, discard it totally. The same procedure, as in maximization
case, is employed to determine the departing variable.
4. Update the new solution. Evaluate the entries and repeated step 3 and 4 until an
optimal solution is obtained.
LINEAR MATHEMATICAL PROGRAMMING

2. The simplex method

Example
1. Min C = 7X1 + 9X2
Subject to:
3X1 + 6X2 ≥ 36
8X1 + 4X2 ≥ 64
X1, X2 ≥ 0
2. Minimize = 40X1 + 24X2----------Total cost
Subject to:
20X1 + 50X2 ≥ 4800 -------- Phosphate requirement
80X1 + 50X2 ≥ 7200 -------- Nitrogen requirement
X1, X2 ≥ 0
Slide 1.82
2.82

LINEAR MATHEMATICAL PROGRAMMING

C. Minimization linear programming problems

Example
Minimize Z= 7X + 9Y
Subject to: 3X + 6Y ≥ 36
8X + 4Y ≥ 64
X, Y ≥ 0

Saunders, Lewis and Thornhill, Research Methods for Business Students, 5th Edition, © Mark Saunders, Philip Lewis and Adrian Thornhill 82
2009
Slide 1.83
2.83

LINEAR MATHEMATICAL PROGRAMMING

C. Minimization linear programming problems

In standard form
Minimize Z= 7X + 9Y + 0S1 + 0S2+MA1+MA2
Subject to: 3X + 6Y –S1 +A1 = 36
8X + 4Y –S2 + A2 = 64
All variables ≥ 0

Saunders, Lewis and Thornhill, Research Methods for Business Students, 5th Edition, © Mark Saunders, Philip Lewis and Adrian Thornhill 83
2009
Slide 1.84
2.84

LINEAR MATHEMATICAL PROGRAMMING

C. Minimization linear programming problems

Initial table
BV CBV 7 9 0 0 M M
X Y S1 S2 A1 A2

A1 M 3 6 -1 0 1 0 36
A2 M 8 4 0 -1 0 1 64

Z 11M 10M -M -M M M 100M

C-Z 7-11M 9-10M M M 0 0

Saunders, Lewis and Thornhill, Research Methods for Business Students, 5th Edition, © Mark Saunders, Philip Lewis and Adrian Thornhill 84
2009
Slide 1.85
2.85

LINEAR MATHEMATICAL PROGRAMMING

C. Minimization linear programming problems

2nd table
BV CBV 7 9 0 0 M M
X Y S1 S2 A1 A2

A1 M 0 9/2 -1 3/8 1 0 12
X 7 1 1/2 0 -1/8 0 1/8 8

Z 7 7/2+9M/2 - M 3M/8 -7/8 M 7/8 56 + 12M

C-Z 0 11/2- 9M/2 M -3M/8 + 7/8 0 M-7/8

Saunders, Lewis and Thornhill, Research Methods for Business Students, 5th Edition, © Mark Saunders, Philip Lewis and Adrian Thornhill 85
2009
Slide 1.86
2.86

C. Minimization linear programming problems

3rd Table
BV CBV 7 9 0 0
X Y S1 S2

Y 9 0 1 -2/9 1/12 8/3

X 7 1 0 1/9 -1/6 20/3

Z 7 9 -11/9 -5/12 212/3

C-Z 0 0 11/9 5/12

Saunders, Lewis and Thornhill, Research Methods for Business Students, 5th Edition, © Mark Saunders, Philip Lewis and Adrian Thornhill 86
2009
LINEAR MATHEMATICAL PROGRAMMING

2. The simplex method

Special cases
1. Multiple optimal solutions:
➢ This condition can be detected by examining the C – Z row of the
final tableau.
➢ If a zero appears in the column of a non-basic variable (i.e., a
variable that is not in solution), it can be concluded that an
alternative solution exists.
Example
Max Z= 60X1 + 30 X2
Subject to:
4X1 + 10X2 ≤ 100
2X1 + X2 ≤ 22
3X1 + 3X2 ≤ 39
X1, X2 ≥ 0
LINEAR MATHEMATICAL PROGRAMMING
2. The simplex method
Basic V Cj 60 30 0 0 0 Quantity
X1 X2 S1 S2 S3
S1 0 0 8 1 -2 0 56

X1 60 11
1 1/2 0 1/2 0
S3 0 6
0 3/2 0 -3/2 1
Zi 60 30 0 30 0 660

Cj-Zi
0 0 0 -30 0
LINEAR MATHEMATICAL PROGRAMMING

2. The simplex method

Basic V Cj 60 30 0 0 0 Quantity
X1 X2 S1 S2 S3
S1 0 0 0 1 6 -16/3 24

X1 60 9
1 0 0 1 -1/3
X2 30 4
0 1 0 -1 2/3
Zi 60 30 0 30 0 660

Cj-Zi
0 0 0 -30 0
LINEAR MATHEMATICAL PROGRAMMING
2. The simplex method
2. Unbounded solution (problem):
➢ unbounded solution exists when all the ratio values (values of
quantity column divided by values in the pivot column) are
negative or zero (no positive value) while determining the
leaving variable
3. Degeneracy solution:
➢ In the process of developing the next simplex tableau for a
tableau that is not optimal, the leaving variable must be
identified. When there is a tie for the lowest non-negative ratio
(two equal values of leaving variable) referred to as degeneracy.
4. Infeasibility solution:
➢ In the simplex approach, infeasibility can be recognized by the
presence of an artificial variable in a solution that appears
optimal.