KARATINA UNIVERSITY

KARATINA UNIVERSITY
KARATINA UNIVERSITY
BBM 355: OPERATIONS RESEARCH 1

QUEUING THEORY (WAITING LINE MODELS)

A queue is formed when units or customers requiring service wait for the service e.g. queues
in a bank, doctor’s clinic, bus stops, ticket booths, etc. Customers wait for service when the
total number of customers exceeds the number of service facilities.
There are two types of costs that are associated with queuing:

(a) Waiting costs – estimated in terms of lost sales, lost goodwill, lost production etc.
(b) Service costs – cost of offering the service e.g. salaries of employees, machine
running costs etc.

The two costs are inversely proportional to each other

Cost

Total cost

Service costs

Waiting costs

Service level(S)
Problem:
What is the optimal service level S that minimizes total costs associated with a queue?

Queuing Models
(1) Single phase single channel model
(2) Single phase multi-channel model
(3) Multiphase multi-channel model

Summary of queuing system components characteristics

1. Arrival characteristics
i. Size/population-Finite or Infinite
ii. Arrival pattern (probability distribution for arrivals): Random or Scheduled e.g. if
a doctor sees a patient at appointed time.
iii. Behaviour: Patient-willing to wait, Balk–look at queue and goes, Reneging –
waits for a little and goes, Jockey – changing queues.

2. Waiting line characteristics

i. Length of the waiting line– limited (restricted) or Unlimited (unrestricted)
ii. Queue discipline/order of service – FIFO, LIFO, Service in ranches order (SIRO),
Priority systems (e.g. in hospitals)

3. Service facility characteristics

i. Pattern/probability distribution of service time: Constant e.g. automated processes
or Random (if so exponential distribution is the best fit)
ii. Design (configuration): Number of servers (channels)-one or many, Number of
lines (phases)-one or many.

Single Channel Queuing Model

In this model, customers form a single line and are served by one service facility on first
come first served basis.

Assumptions of the model

(1) Arrivals are from an infinite population
(2) Arrivals are random and poisson distributed f(x)= [e-λ λx]/x!
for x = 0, 1, 2, ... and λ > 0, where λ is both the mean and the variance of X.
(3) Arrivals are served on First Come First Served basis
(4) Every arrival waits to be served regardless of the length of the line
(5) Arrivals are independent of preceding arrivals, but the average number of arrivals (λ)
does not change with time
(6) Service times occur according to the negative exponential probability distribution
[f(x)=μ e-μx]
(7) Average service rate (μ) is constant
(8) Average service rate is greater than the average arrival rate

Operating characteristics/queuing formulae

A: Simple queues
Let λ = Arrival rate = mean number of arrivals per unit time
µ = Service rate = mean number of customers or items served per unit time.
Then:

λ
a) Length of the system, Ls =
μ−λ
λ2
b) Length of the queue, Lq =
μ (µ−λ)
1
c) Waiting time in the system, Ws =
µ−λ
λ
d) Waiting time in the queue, Wq=, Lq =
μ (µ−λ)
λ
e) Traffic intensity ie probability that the system is busy , ℓ=
μ
f) Probability that system is idle (zero customers or units in the system) =1- ℓ
g) The probability that the number of customers in the system is greater than some value
k

h) The probability that there are n units in the system

B: Queuing Equations for Multi-Channel Model

Let m = number of channels open

λ = average arrival rate
µ = average service rate at each channel
mµ >λ

1) The probability that there are zero customers or units in the system

2) The average number of customers or units in the system

3) The average time a customer or a unit spends in the system (in the queue and being
served)

Or

4) The average number of customers or unit in the queue waiting for service
Or
5) The average time a customer or unit spends in the queue

Or Or

6) Utilization rate i.e. probability that the service facilities (jointly) are busy

Example1:
For a single queue, single service point system with Poisson arrivals and exponential service
time, show how the average number of people in the system could vary if an average of 12
people needed the service every hour and the average service rate took alternative values of
24, 18 and 15 per hour. What is the probability that a person entering the system would have
to queue?

a. λ = 12 µ = 24
Probability of queuing P = 12 = 0.5
24
Average number of customers in the system = 12/ (24-12) = 1 person

b. λ = 12 µ = 18
Probability of queuing = P = 12/18 = 2/3
Average number of customers in system = 12/6= 2 people

c. λ = 12 µ = 15
Probability of queuing = P = 12 = 4
15 5
Average number of customers in system =12/3= 4 people

Example 2:
A team of 15 men is employed to unload Lorries at a terminal. The team works a 6 hour day
during which 36 lorries arrive (i.e. 6 per hour) and it takes 7 ½ minutes to unload one lorry
with the team acting as a single unit. Lorries are served on a FIFO basis.
It has been estimated that the cost of keeping Lorries waiting is sh 6 per hour. Members of
the team are each paid Sh 2.50 per hour. It is also estimated that if the size of the team
increased to 20 men, the average service time would fall to 5 minutes.
Required:
Calculate the cost of the present system and the cost of the proposed system, and determine
whether an increase in the size of the team would be justified on grounds of cost.

Solution:
The cost of service with
15 man team = 15 x 2.50 x 6 = sh. 225 per day
20 man team = 20 x 2.50 x 6 = sh. 300 per day

The daily cost of lorry waiting time, at sh.6 per hour may be calculated in either of 2 ways.
By calculating the average number of lorries in the system and multiplying this number by
(sh 6 per hour x 6 hours per day) Sh. 36 per day or
By calculating the average waiting time in the system, and multiplying this time by sh.6 per
hour and by the number of lorries in a 6 hour day i.e. 36.

Average number of customers in the system = λ or P

µ-λ 1–P

15 man team 20 man team

λ =6 µ = 60/7.5=8 P =0.75 λ =6 µ = 60/5=12 P =0.5

Average number in system = 6 =3 Average number in system = 6 =1

8–6 12 – 6

Cost per day per customer = 36 Cost per day per customer = 36
Total cost 3 x 36 = 108 Total cost = 1x 36 = 36

Summary Sh Summary Sh
Cost of service per day 225 Cost of service per day 300
Cost of waiting time per 108 Cost of waiting time per 36
day day
Cost of system, per day 333 Cost of system per day 336

The 15 man team is marginally more economical by sh 3 per day

Questions
Question 1
Consider a situation where the mean arrival rate is one customer every 4 minutes and the
mean service rate is 2½ minutes per customer.
Required:
(a) The average number of customer in the system
(b) The average queue length
(c) The average time a customer spends in the system
(d) The average time a customer spends in before being served.

Question 2
Rapid Fit Ltd. is a modern quick motor service centre in Kampala. It has a single engineer
and a technician. The Engineer can attend to incoming cars at a rate of 8 per hour. Cars enter
the centre randomly at a rate of 6 per hour
Required:
a) What is the average number of cars at the centre (either waiting or being attended to
by the Engineer
b) What is the average number of cars waiting for the Engineer?
c) What average time per car is spent in the queuing system?
d) What is the probability that the Engineer will be idle?
e) If the cars generate an average of Sh.5,000 an hour for their owners, how much
money is lost by the owners in an 8 hour-day in the centre?
f) If another technician was added to the centre, the Engineer could attend to cars at a
rate of 9 per hour. Should this technician be added at wages of Sh.600 per hour
g) List the practical limitations of using the basic queuing model for management
decision making.
Question 3
A tax consulting firm has four service stations or counters in its office to receive people who
have problems and complaints about their income, wealth and taxes. Arrivals average 80
persons in an 8-hour service day. Each tax adviser spends an irregular amount of time
servicing the arrivals which have been found to have an exponential distribution. The
average service time is 2 minutes per customer.
Required:
Calculate:
(a) The average number of customers in the system
(b) The average number of customers waiting to be served
(c) The average time a customer spends in the system
(d) The average queue waiting time.

KARATINA UNIVERSITY
BBM 355 coursework
Question one
A truck costs sh 3000,000. The annual running cost (sh 000) and the resale price (sh 000) in
a given year is as follows:-
Year (End) 1 2 3 4 5 6 7
Running cost 400 500 600 700 800 1100 1300
Selling price 2100 1300 1000 750 500 300 300

The truck may be replaced by a second hand one too, which may be one, two up to six
years old. The cost (sh 000) of buying a truck of various ages follows:
Age of lorry (years) 1 2 3 4 5 6
Purchase price 2400 1700 1400 1100 800 700
Required: Given this possibility, determine the optimal age to buy and sell the truck (20
marks)
Question two
Using an example in each case below, demonstrate your understanding on:
-Critical path analysis
-Project evaluation review technique
-Activity crashing with cost implications
As used in networks analysis

MULTIPLE STAGE/SEQUENTIAL DECISION UNDER RISK

Some decisions problems span more than 1 stage e.g. contemplate acquiring additional
information say through market research consultants (so as to have better understanding or
insight into the kind of market demand expected) before making decision.

Stage 1 Stage 2
Acquire information - Make decision
Or not acquire
If a problem spans more than 1 stage, it is no longer convenient to use a decision table. We
use a decision trees
Decision Tree
Definition-A decision tree is a graphic representation of a decision process and indicates the
decision alternative, the various states of nature, their probabilities and condition pay offs.

- Decision nodes from which one of the several alternatives may

be chosen which is controllable.

- Circles are used to represent events or states of nature out of

which one state of nature will occur.

- Lines are used to denote a decision alternative or a probability

branch.

STEPS IN ANALYSING PROBLEMS USING DECISION TREE

i. Define and understand the problem.
ii. Draw out the decision tree clearly depicting decision alternatives and events.
iii. Assign probabilities to the states of nature
iv. Estimate the payoffs for each possible combination of a decision alternative of a
state of nature.
v. Solve the problem by computing EMV’s at each state of nature node and
extending to the next decision node. Proceeds from the last event node to the first
(roll back).
Select the alternative which is indicated by the “best” EMV at the staff decision node.

Expected value of sample information (EV of SI)

EV of SI is the value of obtaining sample or additional information such as conducting a
market research or survey. The basic question is:
Is it worth the cost?
EV of SI = EV of best decision with Expected value of
Sample information - decision without
Assuming no cost to gather it information
Revision of probabilities
Bayes Theorem
P (B/A) = P (A/B) P (B)/p(A)
P (A) = P (A/B1) P (B1) + P (A/B2) P (B2) + …….. P (A/Bn) P (Bn)

Example:
A cooking oil manufacturing firm based in Eldoret is considering opening a new production
plant in Thika. The opening of a new plant will, however, depend on the demand for the
cooking oil in the Thika region. Information concerning the demand for the cooking oil is
available and is as shown below:
H - High demand and leads to a profit of shs.6,000,000 per year.
M - Moderate demand and leads to a profit of shs.1,500,000 per year.
L - Low demand and leads to a loss of shs.2,500,000 per year.
The chances of having high, moderate and low demand are assessed at 30%, 30% and 40%
respectively by the firm’s management. A market research group could be employed to
provide information on which market demand will be realized. Past experience with work in
the same market with this group shows its information cannot be relied on to be absolutely
accurate.

The market research group classifies its results as either there being good prospects (G) or
poor prospects (P). The table below gives the extent of reliability of this market research
group.
Market Survey Actual State of Nature
Result
H M L
G 0.7 0.6 0.2
P 0.3 0.4 0.8
The market research group would charge a fee of shs.60,000 if it was hired.
Required: By use of a decision tree, determine whether the market research is justified, i.e.
determine the expected value of imperfect information.

Solution:

Not open
0

1250 0.3 H:
6000
open 0.3 M:
1500 n
1250
B D 0.4 L:-
2500
No Not open

open 0
A E n
Good 2845 2845
Surve .45, H:
6000
G .38, M:
1500
.17, L:-
2500
Poor Not open
1337.15
open
C F n
0
0
-135 .17 H:
6000
H .23 M:
1500
.6 L: -
2500

Revision of probabilities (probability tree)

Prior information
Bayes theorem Posterior (Revised
information)
Additional information

H 0.3 x 0.7 = 0.21

M 0.1 x 0.6 = 0.18

Good
L 0.4 x 0.2 = 0.08
P(G)=0.47
H 0.3 x 0.3 = 0.09
Poor
M 0.3 x 0.4 = 0.12

L 0.4 x 0.8 = 0.32

P(P)=0.58

P (H/G) = 0.21 = 0.45

0.47
P (M/G) = 0.18 = 0.38
0.47
P (L/G) = 0.02 = 0.17
0.47 1
P (H/P) = 0.09 = 0.17
0.53
P (M/P) = 0.12 = 0.23
0.53
P (L/P) = 0.32 = 0.60
0.53 1

Revision by Bayes Theorem

Therefore, P (H/G) = P(G/H) P(H)
P(G)
Where, P (G) = P(G/H)PH + P(G/M) P(M) + P(G/L) P(L)
= 0.7205 + 0.6 X 0.3 + 0.2 x 0.4
= 0.47
P (P) = 1 – P(G)
= 1 – 0.47 = 0.53
P (H/G) = 0.7 x 0.3 = 0.45
0.47
P (M/P) = P(P/M) P(M) but P(P) = 0.53
P (P)
= 0.4 x 0.3 = 0.23
0.53
Node
A Survey

B Open

C Emv = 1337.15

D Emv = 0.3 x 600 + 0.3x 1,500 + 0.4 x (2500) = 1,250

E Open

F Not open

G Emv = 0.45 x 600 + 0.38 x 1500 + 0.17 x (2500) = 2,845

H Emv = 0.17 x 600 + 0.23 x 1500 + 0.6 x (2500) = -135

Recommendation: The firm should undertake the market research and if the results are good
prospects (G) open the plant otherwise if there are poor prospects (P) do not open the plant.

Expected value of sample information

Ev of SI = Best EMV with information - Best Emv

Assuming costless without information

= 1337.15 - 1,250 = 87.15, hence the survey is justified since Sh 60, 000 is less than
Sh 87, 150 (which is the maximum amount that can be committed towards the
research)

4 Competition
In this environment, the decision maker is not alone. There is at least one other participant
(There is at least one active opponent). For example: Body of knowledge (Game theory)

ENVIRONMENT OF COMPETITION (GAME THEORY)

Two-person, zero sum games
Game theory embodies studies and theories expounded through time by game theorists. In
the decision-making environment there is at least one active opponent. In the business
context the term “games” refers to conflict through time. It is to do with business situations
where usually the success of one person is at the expense of another. A way of solving
problems in competitive situations has been advanced by logicians through time for example
A Raiffa (German Mathematician), Oskar Morgenstern (US Economist), John von Neumann
(US Mathematician)
Conflict can occur for a number of competitions. However for our purposes, we shall study
only 2 person games.
Illustration
Player Y
Strategy Q Strategy P
Player X Strategy M X wins 2 points X wins 3 points
Strategy N Y wins 1 points Y wins 3 points
Problem – which strategy shall each of the players adopt?
Components of a game
1. Players
2. Strategies
3. Pay offs
Assumptions (Conditions)
1. Economic rationality - Each player is assumed to be economically rational i.e. each
desires to win. i.e. None of the players is charitable.
Each player prefers more of a good thing than less and vice versa.
2. Information: Both players have the same information set i.e. each player knows the
strategies of the opponent and the consequential pay offs.
3. Zero sum nature of the game. The gain of a given player exactly equals the loss to the
other player so that the game is zero sum.
X = m: +3
Y = P: -3
∑=0
4. No indifference – each player has to play.
5. Repeatedness – The game is played repeatedly over a long time.
6. Number of players – we assume they are finite i.e. 2 in this case.

Standard Notation (Zero Sum Games Only)

Convention
Gain to x (losses to y) are +ve
Gain to y (losses to x) are –ve
Standard form
Y
Y1 Y2
X X1 2 3
X2 -1 -3

Solution
x = X1 v = 2
y = Y1

PURE AND MIXED STRATEGIES

Whenever there is only 1 strategy for x and y which they both mutually and logically agree,
this is termed as pure strategy game, and the solution to the game is known as a saddle point.
Mathematically, a saddle point is one which is a maximum with respect to one variable and a
minimum with respect to the other.
Rule
If a game is pure strategy, the saddle point will be given by the element which is both
maximum in its column and minimum in its row (minimax).
Furthermore, if a game, is not pure strategy, then it is mixed strategy in which case each
player oscillates between his or her strategies through time.

(a) Player Y
Y1 Y2
Player X X1 2 3
X2 -1 -3
(b) Player Y
Y1 Y2 Y3
Player X X1 2 0 4
X2 1 -3 2
(c) Player B
b1 b2 b3 b4 b5
Player A a1 -2 0 0 5 3
a2 3 5 1 2 2
a3 -4 -3 0 -2 6
a4 5 -3 -1 -2 -6

(d) Player Y
Y1 Y2
Player X X1 2 6
X2 -1 -2
X3 3 1

SOLUTION TO MIXED STRATEGY GAMES (JOINT PROBABILITY APPROACH)

When there is no saddle point, players will result to mixed strategies i.e. each of the available
strategies will be played a certain percentage of total time.
Principle (Expectation theory) – Theory of rational expectation
Logically one wants to divide the time between his strategies so that he wins as much when
the other is playing either of his alternative.

GAME REDUCTION: DOMINANCE PRINCIPLE

In d above, one of the Xs must be eliminated to have 3 strategies.
Considering X1 and X3
If Y=Y1, X=X3 and if Y=Y2, X= X1, Hence non is dominant
Considering X1 and X2
If Y=Y1, X=X1 and if Y=Y2, X= X1, hence X1 dominates X2, such that X2 shall never be
played as long as X1 exists hence it is dropped. The reduced game becomes
(d) Player Y
Y1 Y2
Player X X1 2 6
X3 3 1

GAME REDUCTION: DOMINANCE PRINCIPLE

In d above, one of the Xs must be eliminated to have 3 strategies.
Considering X1 and X3
If Y=Y1, X=X3 and if Y=Y2, X= X1, Hence non is dominant
Considering X1 and X2
If Y=Y1, X=X1 and if Y=Y2, X= X1, hence X1 dominates X2, such that X2 shall never be
played as long as X1 exists hence it is dropped. The reduced game becomes
(d) Player Y
Y1 Y2
Player X X1 2 6
X3 3 1

Obtaining the proportions of time dedicated to strategies:

If Y plays Y1, X scores 2X1 + 3X3
If Y plays Y2, X scores 6X1 + X3
The two scores must be the same (rational expectation theory) hence
2X1 + 3X3 = 6X1 + X3
i.e. 4X1 - 2X3=0
but X1 + X3 =1 since are proportions, hence on solving
X1 =1/3
X3 = 2/3
Likwise, If X plays X1, Y scores 2Y1 + 6Y2
If X plays X3, Y scores 3Y1 + Y2
The two scores must be the same (rational expectation theory) hence
2Y1 + 6Y2 = 3Y1 + Y2
i.e. Y1 – 5Y2=0
but Y1 + Y2 =1 since are proportions, hence on solving
Y1 =5/6
Y2 = 1/6
Joint probabilities
P(X1 and Y1) =1/3*5/6=5/18
P(X1 and Y2) =1/3*1/6=1/18
P(X3 and Y1) =2/3*5/6=10/18
P(X3 and Y2) =2/3*1/6=2/18
Value of the game = 1/18[2*5+1*6+10*3+2*1]=48/18=2.667
Therefore, X should devote 1/3 of time to play X 1, 2/3 to play X3 while Y should devote 5/6
of time to play Y1, 1/6 to play Y2. Overall, X wins 2.667 which Y loses

NON-ZERO SUM GAMES

An assumption in zero sum games is that the gain of a given player exactly equals the loss to
the other player. This may be possible in some games e.g.
- Game of sports such as athletics, soccer etc.
- In a fixed market (what other firms gain, the other losses). However in the business
many competitive situations cannot be realistically modeled as zero-sum. In many
cases, the players may all gain e.g. (in fierce competition), some may gain while
others loose (and not necessarily the same amounts) etc.
Example: prisoner’s dilemma
Two criminals are being held in connection with a crime which the police are convinced they
are guilty of. They are interrogated separately and each of them is warned that if he fails to
confess and his accomplice confesses, he will face a 10 year jail term while the other goes
free. Similarly, if he confesses and the accomplice denies, he will go free while the
accomplice will be jailed for 10 years.
The prisoners are both aware that if both do not confess, the worst that can happen is that
they will be jailed for 3 months each. If both confess they will face a jail term of 6 years
each.
Required:
Determine the payoff matrix and suggest the best strategy.
Solution: Criminal B
Criminal A Confess Not confess
Confess (-6, -6) (0, -10)
Not confess (-10, 0) (-0.25, -0.25)

If A confess, B confess. If A does not confess, B, confess. Therefore irrespective of what A

does, B confess. A realizes so and ends up confessing hence both ends up confessing. This is
the non-cooperative solution also called Nash equilibrium (John Nash). Its character is
individualistic, associated with conflict, strikes, intransigence, suspicion, wars etc.
A better or more efficient solution however is where both do not confess. This is the co-
operative solution also called pareto equilibrium, and its character is not individualistic. It is
collective and is associated with co-operation, negotiations, collusion, trust, compromise,
peace etc.

Some possible areas of applications of Game theory

Game theory has been used in business and industries to:
 Develop bidding tactics
 For collective bargaining
 For pricing policies
 To device advertising strategies
 For timing of introduction of new models into the market.

However, it still faces a number of limitations, as follows:-

 Weak, theoretical, foundations e.g. it does not adequately cater for:-
- Negotiations
- Collusions
- Coalitions
- Information
- Information asymmetry (“unequal “ access to information)
 Presence of government; it is usually a participant sometimes an active player and in
other situation, it acts as an arbitrator (Referee)
 Presence of a trade union: Trade union members belong to competing firms, how
should this be incorporated in a game theoretic framework?
 As number of players increase, the analysis becomes exceedingly complex.
 Data availability – Strategies of opponent
- Pay off specification

Self-test questions
Question 1
Mr. Kimani is a manufacturer who is contemplating putting up a plant
which could be large or small. The following data has been gathered:
States of Nature (Market Demand in K£)
Favourable Market Unfavourable Market
(FM) (UM)
Large plant 200,000 -180,000
alternatives
Decision

Small plant 100,000 -20,000

No plant 0 0

Further Mr. Kimani believes that FM and UM are equally likely.

a) Advice Mr. Kimani using (i) EMV criterion
(ii) EOL criterion
b) Suppose Mr. Kimani is able to acquire flawless information at a fee
of K£65,000, should he pay?

Question 2
Watt Limited (WL) is trying to decide whether or not to drill for oil on a
particular site in North Eastern Kenya. The Chief Engineer has assessed
the probabilities that there will be oil as follows, based on past
experience. P (oil) = 0.2, P (No oil) = 0.8
It is possible for WL to hire a firm of international consultants to carry out
a complete survey of the site. WL has used the firm many times before
and has made the following estimates.
(i) If there is really oil, then there is a 95% chance that the report will
be favourable
(ii) If there is no oil, then there is only a 10% chance that the report will
be favourable.
The following additional information is also provided:
 Cost of drilling is Ksh.10 million
 Value of the benefits if oil is found is Ksh.70 million
 Cost of obtaining information is Ksh.3 million
Required:
(a) Advise the company on whether to acquire addition information
from the consultants. (Use a decision tree).

(b) Compute the expected value of perfect information

Question 3

Solve the games below:

(a) Player Y
Y1 Y2
Player X X1 2 3
X2 -1 -3
(b) Player Y
Y1 Y2 Y3
Player X X1 2 0 4
X2 1 -3 2
(c) Player B
b1 b2 b3 b4 b5
Player A a1 -2 0 0 5 3
a2 3 5 1 2 2
a3 -4 -3 0 -2 6
a4 5 -3 -1 -2 -6

(d) Player Y
Y1 Y2
Player X X1 10 -5
X2 -7 21

(e) Player Y
Y1 Y2
Player X X1 2 6
X2 -1 -2
X3 3 1

(f) Player Y
Y1 Y2 Y3
Player X X1 -5 1 5
X2 3 -4 4
X3 -6 -4 4

KARATINA UNIVERSITY
BBM 355 OR1-DECISION THEORY
Definition
Decision making is concerned with choosing a course of actions from among available
alternatives.
STEPS
1. Define the problem at hand.
2. List the possible alternative courses of action.
3. Identify the possible outcomes (states of nature/and their probability if possible).
4. Estimate the conditional pay offs for each combination of a decision alternative/state of
nature.
5. Select a suitable or appropriate mathematical tool from among the techniques.
6. Apply the model and hence recommend the best course of action.
7. Perform sensitivity or (what if? Or post optimality) analysis, set up controls and
implement.

STRUCTURE/ANATOMY OF A DECISION PROBLEM

Decision
alternatives
States of nature/possible outcomes
S1 S2 Sn
a1 P11 P1 ……………... P1n
a2 P21 P22 …………….. P2n

am Pm1 Pm2 ……………. Pmm

EXPLANATIONS/DEFINITIONS
1. Alternative ai = this is a course of action or strategy that may be chosen by the decision
marker (It is controllable). We assume decision alternatives are mutually exclusive. (If
one is selected, all the others are left).
2. States of nature, sj = this represent an outcome or occurrence over which the decision-
maker has little or no control. The chances of occurrence of various states of nature may
or may not be available. (Assumption: No control).
3. Conditional pay offs (Pijs) = This is a consequence or outcome normally expressed in
monetary value that occurs as a result of a particular alternative and a state of nature.
Illustration (A farmer)

SON
DA
Little Rain Moderate Rain Much Rain
Maize -1 2 5
Beans 5 7 -3
Wheat 1 3 -4
None 0 0 0

DECISION MAKING ENVIRONMENTS

The study of decision making is greatly facilitated by classifying decision making scenarios
or environments depending on the level of knowledge about the possible outcomes or states
of nature and the number of participants in the decision making environment. To this extent
four decision making environments have been defined.
These are:-
 Environment of certainty
 Environment of uncertainty
 Environment of risk
 Environment of competition / Game theory

1 Environment of Certainty
This is where all the information about a state of nature is known for sure. The model used to
recommend the best course(s) of action in this environment are certainty models
(deterministic model.)
2 Environment of uncertainty
In this enviroment the probabilities for the various states of nature are not known or may be
unreliable. Uncertain events are those events that cannot be predicted with statistical
confidence i.e the decision maker does not know the relevant variables nor their probability
therefore decision making in this environment depends on the risk attitude of the decision
maker i.e. risk averse or a risk seeker or risk neutral.
A risk averse avoids risk at all cost; the individual is conservative and assumes the worst
situation will occur.
A risk seeker takes high risks in expectation of high returns. He assumes that the best
outcome will occur.
A risk neutral person is not affected by risks. Such people will make decisions based on
something else but not risk.
Some criteria used under this environment are
a) Maximax
b) Maximin
c) Minimax regret
d) Hurwicz
e) Laplace

MAXIMAX
Selects the best of the best for all possible decision alternatives. It is a criterion of
extreme optimism.
USERS
- Risk takers
- Large firms which are able to absorb huge losses in case the state of nature
turns out to be unfavourable.
Example
Alternative high medium low No Action Max. of row
Expand 50,000 25,000 -25,000 -45,000 50,000
Contract 70,000 30,000 -40,000 -80,000 70,000
Subcontract 30,000 15,000 -10,000 -10,000 30,000
Maxmax payoff is sh70,000 corresponding to contract alternative.

MAXIMIN
This method selects the maximum out of all minima for all decision alternatives. It is a
criterion of extreme pessimism.
USERS
- Risk averters
- Small firms which cannot absorb large losses in case things turn out to be
unfavourable.
Example
Min in row (sh 000)
-45
-80
-10
Max of min is -10 hence subcontract

HURWICZ (criterion or realism)

This is a compromise between maximax and Maximin.
Argument: It is unrealistic to view decision-makers as extreme optimists or pessimists.
Solution: Obtain the degree of optimism of the decision-maker (coefficient of optimism) 
(alpha) 0 <  < 1.
When  = 0, we have an extreme pessimist (Maximin)
 = 1, we have an extreme optimist (maximax)
Thus: For each alternative we obtain the following:
Expected pay off = Best payoff) + (worst payoff) (1 -).
Example
Assuming an  of 0.8 then
EMVs (sh 000) are
Expand=50,000*0.8- 45,000*0.2=31
Contract=40
Sub contract=22
Hence contract

Laplace (Equally likely)

Also called the criterion of rationality. This method takes all states of nature as equally likely.
Thus for any states of nature, the probability of each state = 1/n
The effect is to transform the decision environment from that of under uncertainty to that of
under the environment of risk.
Example
Expand1/4(50,000+25,000 -25,000 -45,000)= 1250
= -500
= 8500
Hence subcontract

MINIMAX REGRET (Savage criterion)

This concept is based on opportunity loss. The idea is to minimize the maximum possible
opportunity loss i.e. when a decision has been taken, the decision maker may experience
some loss; the question is what the maximum possible loss that will be experienced is? The
method then seeks to minimize this maximum possible loss for each decision alternative.

Alternative High Moderate low No action Max

Expand 20,000 5,000 24,000 35,000 35,000
Construct 0 0 39,000 70,000 70,000
Subcontract 40,000 15,000 0 0 40,000
The company should expand because this decision will minimise its regret which is Sh.
35,000.

3 Environment of risk.
In this environment it is not known exactly which state of nature will occur. However, there
is sufficient or partial information for us to estimate the chances of occurrence of various
states of nature. Two decisions criteria may be used:
- Maximize expected monetary value (EMV) or
- Minimize expected opportunity loss (EOL)
However, both consistently rank the various alternatives.

Definition-Opportunity loss is the amount a decision maker would lose by not taking the best
alternative. Opportunity loss is also known as the amount of regret. For any states of nature
this is the difference between the consequence of any alternative and the best possible
alternative. The decision making on the environment of risk can be for single or multi stage.
A payoff table is suitable for single stage analysis while a tree is preferred for multistage
analysis.

Value of information
Perfect information – this is true or flawless information. In many organizations it can be
obtained at a fee. What is the maximum amount that one should be willing to pay for such
information?
(EV of PI) = EV with PI – Best EMV with existing (imperfect) information.
Example
Metaballs Manufacturing Company Ltd. is considering introducing two new products in the
market. The company has the following options:
Option 1: Introduce both products
Option 2: Introduce either of the products.
Option 3: Introduce none of the products, depending on their performance in the
market.
An analysis of the products’ likely performance indicates the probability of a good
performance as 30%, fair performance as 50% and poor performance as 20% and the sales
revenue as shown in the table below:
State of nature
Decision S1 S2 S3
(Sh. million) (Sh. million) (Sh. million)
Neither 0 0 0
Product 1 only 10.0 10 2.4
Product 2 only 8.4 4.8 2.4
Both 17.6 8.8 3.2
Where S1 = good performance
S2 = fair performance
S3 = poor performance
Required:
(i) The expected monetary value for each decision.
(ii) The decision you would recommend.
(iii) The expected value of perfect information
(iv) Would the decision in (ii) change if EOL was used?

Solution:
i)
EMV (neither) = 0
EMV (1) = 10 × 0.3+10 × 0.5+2.4 × 0.2=8.48
EMV (2) =5.4
EMV (both) =10.32
ii) Decision: both products
(iii) The value of perfect information
EV with PI=(17.6 × 0.3) + (10 × 0.5) + (3.2 × 0.2) = 10.92
Expected maximum monetary value = 10.92
∴ Expected value of perfect information = 10.92 – 10.32 =0.6
iv) Regret table
State of nature
Decision S1 S2 S3
(Sh. million) (Sh. million) (Sh. million)
Neither 17.6 10 3.2
Product 1 only 7.6 0 0.8
Product 2 only 9.2 5.2 0.8
Both 0 1.2 0
EOL (neither) =10.92
EOL (1) =2.44
EOL (2) =5.52
EOL (both) =0.6
Decision: Both products hence no change
KARU
BBM 355 OPERATIONS RESEARCH

LINEAR PROGRAMMING

A: Introduction
Every organization faces the problem of allocation of resources. The resources include men,
machine, material, capital, information, etc. Most of the decisions are made subject to
constraints. In other words, no organization operates permanently with unlimited resources;
consequently management must continually allocate scarce resources to achieve the
organization’s goals, whatever they might be. Organizations can have many goals. Here are a
few examples.
1) A bank wants to allocate its funds to achieve the highest possible return. It must
operate within the liquidity limits set by regulatory agencies, and it must maintain
sufficient flexibility to meet the loan demands of its customers.
2) Development of a production schedule by minimizing total production and inventory
costs to satisfy future demands for a company’s product.
3) Selection of different blends of raw materials in feed mills to produce finished feed
combinations at minimum cost.
4) Determination of a distribution system for minimizing total shipping cost from several
warehouses to various market locations.
5) Allocation of a limited advertising budget among various advertising media like TV,
Radio, and newspapers in order to maximize advertising effectiveness.
6) Determination of how much to produce of different grades of petroleum products in
an oil refinery to yield the maximum profit.
7) Determination of the capital budget which maximizes the net present value of the
firm, subject to several financial, managerial, environmental and other constraints.

B: What is Linear Programming?

Linear Programming is an optimization technique for finding an optimal (maximum or
minimum) value of a function, called the objective function, of several independent variables,
the variables being subject to various restrictions (or constraints) expressed as equations or
inequalities. The term ‘linear’ indicates that the function to be maximized or minimized is
linear and that the corresponding constraints be represented by a system of linear inequalities
or linear equations involving the variables.
In simpler terms Linear Programming is a mathematical technique for finding the best uses of
an organization’s resources.

In order to apply LP the following requirements must be met.

1) There should be one objective which should be clearly identifiable and measurable in
quantitative terms. For multiple objects, goal programming is used.
2) The activities to be included should be distinctively identifiable and measurable in
quantitative terms.
3) The resources of the system which are to be allocated for the attainment of the goal
should also be identifiable, measurable and limited in supply.
4) The relationships representing the objective, the resource limitations, consideration
represented by the objective function and the constraints equations or inequalities
must be linear in nature.
5) There should be a series of feasible alternative courses of action (more than one way
of determining the solution) available to the decision maker that is determined by
resource constraints.

When these conditions are satisfied in a given situation the problem can be expressed in
algebraic form called LP problem.

C: LP Assumptions
1) Certainty - All the decision variables, parameters and constraints are known. If not

stochastic method is used.

2) Static time period- a given solution applies to a given time period and all such similar

periods. To appreciate that different time periods have different requirements, dynamic
programming is used.
3) Divisibility – The solution values and decision variables or resources can take any

positive values i.e. integers and fractions. Where this is violated integer programming is
used.
4) Additivity – the sum of resources used by different activities must be equal to total

quantity of resources used by each activity individually and correctively i.e. every
function in a linear programming model (whether the objective function or constraint) is
the sum of the individual contributions of the respective activities.
5) Proportionality – The level of any activity is proportional to the level of the decision

variables.eg if 1 unit of product yields sh 15 in profits then 20 units will yield sh 300.
6) Non negativity– all decision variables and parameters are zero or positive.
D: Formulating Linear Programming Mathematical Model:

Step 1: Decision Variables

Identify your decision variables. These represent the actions that the decision maker needs to
take e.g. quantity of resources to be allocated or number of units to be produced and sold.
Decision variables are usually represented by small letters.
E.g. x1, x2…xn
Example:
Let x1 = number of white board markers to be produced and sold to KCA during Jan- May
semester.
Let x2 = number of dusters to be produced and sold to KCA during Jan-May semester.

Step 2: Objective
A certain objective the decision maker needs to meet. LP models always attempt to optimize
a single goal which is either:
a) Maximum level of a desired goal, where the objective is to be made as large as
possible. OR
b) Minimum level of a desirable outcome, where the objective is to be made as small as
possible.

Step 3: Cost/Profit
Determine the cost in case of a minimization problem or the profit (or any other desirable
goal) in case of maximization problem per unit of each of the decision variables. Objective
function is normally expressed as follows.

Maximize/Minimize
Z = c1x1 + c2x2 +…+ cnxn
Where ci = cost/profit per unit

Step 4: Constraints
Determine the constraints or limitations or restrictions imposed on the problem. These
represent maximum availability of resources or minimum requirements or equality. These
constraints are represented as ≤ inequalities or ≥ inequalities or = type of equalities.

E: Solving a LP problem
Two methods can be used:
1) Graphical method.
2) Simplex method.

Graphical Method:
This involves plotting all the inequalities on the same graph and identifying the region that
satisfies all the inequalities. This is called the feasible region. Each point in the feasible
region is a viable solution to LP. The points are called feasible solution. A feasible solution is
one that satisfies all the constraints. If a solution fails to satisfy at least one of the constraints,
it is called unfeasible solution.
To draw the inequalities, 1st replace the inequality sign with an equal sign. Draw the
resulting graph. This is done by identifying any 2 points on the line which are joined by a
straight line. Identify the side of the line that does not satisfy the inequality and shade it. This
is done by selecting any point that is not on the line and substituting the values in the
inequality. If the values obtained satisfy the inequality, then that point is on the wanted side
of the line. The unwanted side is therefore the opposite one. Shade the unwanted side.
To determine the solution that will maximize the total contribution, we first identify the co-
ordinates of the points at the corners of feasible region. At each corner point, compute the
total contribution. The point that gives the maximum value is the one that maximizes the
contribution. This is called the optimal solution. For minimization, the optimal solution is the
one that has the minimum value.

Example:
Geosoft Paints Ltd. produces both interior and exterior paints from two raw materials, M1
and M2. The following table provides the basic data of the problem:

Exterior (tons) Interior (tons) Maximum

Daily availability (tons)
M1 6 4 24
M2 1 2 6

The profit per ton (Ksh.’000’) for Exterior and Interior paints is 5 and 4 respectively.
A market survey indicates that the daily demand for interior paint cannot exceed that of
exterior paint by more that 1 ton. Also, the maximum daily demand of interior paint is 2 tons.
Geosoft wants to determine the optimum (best) product mix of interior and exterior paints
that maximizes the total daily profit.

Solution:
Let x1 and x2 represent the number of tons of Exterior and Interior paint produced and sold
respectively.
The objective is to maximize profit, Z = 5x1 + 4x2
Subject to:
6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
-x1 + x2 ≤ 1
x2 ≤ 2
x1, x2 ≥ 0

Solution
X2
6

4 Demand difference

2 H Interior demand
E D
1 C

-1 0A B G
1 2 3 4 5 6 M2 X1
M1

The solution is x1 = 3 and x2 = 1.5 with Z = 21 (Ksh.’000’)

Note: Do resource utility test & comment on dual/shadow price

F: Sensitivity Analysis/post optimality

An LP model is a snapshot of a real situation in which the model parameters (objective and
constraint coefficients) assume static values. To enhance the applicability of LP in practice,
we need to add a dynamic dimension that investigates the impact of making changes in the
model parameters (objective and constraint coefficients) on the optimal solution. The
procedure is referred as sensitivity analysis because it studies the sensitivity of the optimal
solution to changes made in the model and since it is done after attaining the optimal
solution, it is also referred to as post optimality. If a minor change in a factor causes a large
change in the solution then the LPP is said to be sensitive to the factor otherwise insensitive.
Sensitivity analysis includes the following:
a) Objective coefficients range.
b) The right hand side ranges.
c) Shadow prices (also known as the dual prices).

a) Changes in the Objective Function Coefficients

The general objective function in a two-variable LP problem can be written as
Maximize or Minimize Z = c1x1 + c2x2
Changes in the coefficients c1 and c2 will change the slope of Z and, hence, possibly, the
optimal corner point. However, there is a range of variation for both c1 and c2 that will keep
the current optimum unchanged. Specifically, we are interested in determining the range of
optimality for the ratio c1/c2 (or c2/c1) that will keep the present solution unchanged. The
solution will change when the objective function is rotated clockwise and anticlockwise
to be parallel or coincide with the binding constraint

Example:
Consider the Geosoft Paint Ltd. model in working example above. In [the graph already
drawn], the optimum solution at C provides the maximum value of Z = 5x1 + 4x2.
If we change the objective function to Z = c1x1 + c2x2, then the solution at C will remain
optimum so long as the slope of Z lies between the slopes of the two lines intersecting at C-
namely, 6x1 + 4x2 = 24 (raw material, M1) and x1 + 2x2 = 6 (raw material, M2). We can
express this relationship algebraically as:

If c1 ≠ 0, then 4/6 ≤ c2/c1 ≤ 2/1

Or If c2 ≠ 0, then 1/2 ≤ c1/c2 ≤ 6/4

What the conditions for c1/c2 and c2/c1 say is that so long as these ratios are within the
specified limits, the optimum solution remains unchanged at C.
We can use the given conditions to determine the optimal range for one of the coefficients,
given that the other remains as originally given in Z = 5x1 + 4x2.

Thus given c2 = 4, the associated optimal range for c1 is determined from the condition
1/2 ≤ c1/c2 ≤ 6/4 by substituting c2 = 4, which yields 2 ≤ c1 ≤ 6. This means that the unit
contribution of x1 can be increased by a max of 1 or reduced by a min of 3 without changing
the current optimal solution.
Similarly, given c1 = 5, the condition will yield 10/3 ≤ c2 ≤ 10

b) Right Hand Side Ranges (Change in availability of resources)

In LP models, constraints, directly or indirectly represent the usage of limited resources. In
this case, the right-hand side can be thought of as representing limits on the availability of the
resources. The RHS range is the range within which the capacity of the constraint can be
adjusted without violating any other constraint (or before the current shadow price of that
resource change). The shadow price will change when the current optimal point is shifted
to coincide with the most immediate corner points

Example:
Consider the Geosoft Paint Ltd. model above. The graph shows that the current optimum
occurs at C, the intersection of the lines associated with raw materials M1 and M2. When the
availability of M1 changes (increases or decreases around its current level of 24 tons), and
given M2 = 6 tons, the optimum solution at point C will “slide” along the line segment DG.
Any change in M1 outside the range of this segment will render point C (intersection of the
lines associated with M1 and M2) infeasible. For this reason, we say that the end points D =
(2, 2) and G = (6, 0) delineate the feasibility range for M1.
Thus,

Amount of M1 at D = 6x1 + 4x2 = 6(2) + 4(2) = 20 tons.

Amount of M1at G = 6x1 + 4x2 = 6(6) + 4(0) = 36 tons.

It then follows that, given M2 = 6, the feasibility range for M1 is

20 ≤ M1 ≤ 36
The result shows that M1 can be decreased by as much as 4 tons or increased by as much as
12 tons while guaranteeing that the optimum solution point will be given by the intersection
of the lines associated with M1 and M2.

Next, consider raw material M2. The graph shows that the feasibility range for M2 (given M1
= 24 tons) is delineated by the end points B and H, where B = (4, 0) and H = (8/3, 2), where
point H is defined by the intersection of lines ED and BC. Thus,

Amount of M2 at B = x1 + 2x2 = 1(4) + 2(0) = 4 tons.

Amount of M2 at H = x1 + 2x2 = 1(8/3) + 2(2) = 20/3 tons.

Thus, given M1 = 24, the feasibility range for M2 is

4 ≤ M2≤ 20/3
The result shows that M2 can be decreased by as much as 2 tons or increased by as much as
2/3 tons while guaranteeing that the optimum solution point will be given by the intersection
of the lines associated with M1 and M2.

100 Percent Rule for Objective Function Coefficients

For all objective function coefficients that are changed simultaneously, sum the percentages
of the allowable increases and the allowable decreases. If the sum of the percentages is less
than or equal to 100%, the optimal solution does not change. Note that the 100% rule does
not say that the optimal solution will change if the sum of the percentages of the allowable
increases and the allowable decreases is greater that 100%. All we can say is that if the sum
of the percentages is greater than 100%, a different optimal solution may exist.

c) Shadow prices [also known as Dual Prices]

The shadow price of a resource is the change in the optimal value of the objective function
per unit increase of the resource.
The shadow price gives us the unit worth of a resource, which is defined as the rate of
change in the optimum objective value that results from making changes in the available
amount of a resource.

Letting yi represent the worth per unit of resource i, the associated formula for computing this
measure is:

yi = change in value of Z corresponding to the feasible range of resource i

Feasible range of resource i

Example
From the graph the feasible range for M1, 20 ≤ M1 ≤ 36, is delineated by points D and G.
Thus, we have
y1 = change in Z from D to G
Change in M1 from D to G

Given D = (2, 2) and G = (6, 0), then

Z at D = 5(2) + 4(2) = 18 (Ksh.’000’)
Z at G = 5(6) + 4(0) = 30 (Ksh.’000’)
It then follows that
y1 = (30 – 18)/ (36 – 20) = 0.75 (Ksh.’000’ per ton of M1)

The result shows that a 1-ton change in M1 in the range 20 ≤ M1 ≤ 36 will change the
optimum value of Z by Ksh.750.

Next, we consider raw material M2. its range of feasibility, 4 ≤ M2≤ 20/3, is delineated by
points B and H as shown in the graph. Thus,

y2 = change in Z from B to H
Change in M2 from B to H

Where Z at B = 5(4) + 4(0) = 20 (Ksh.’000’)

Z at H = 5(8/3) + 4(2) = 64/3 (Ksh.’000’)

It then follows that

y2 = (64/3 – 20)/ (20/3 – 4) = 0.5 (Ksh.’000’ per ton of M2)

Once again this result says that an increase (decrease) in M2 by 1 ton in the range
4 ≤ M2≤ 20/3 increases (decreases) the profit by Ksh.500.

Note
The shadow (dual) price can also be obtained by solving the equations of the lines meeting at
the optimum corner point, by adjusting the RHS by 1 unit, and then substituting the values
obtained in the objective function. The difference between value and the optimal solution
value is the shadow price.

Uses of shadow prices:

1) The shadow price shows the additional value obtained by adjusting the capacity of a
constraint by 1 unit. This shows the additional improvement in the optimum value
when a constraint’s capacity is adjusted by 1 unit. Moreover it indicates the maximum
additional cost the management should incur to avail an extra unit of the constraint.
2) Shadow prices indicate the constraint that is more profitable to employ extra
resources. Holding other factors at constant, this should be the constraint with highest
shadow price.
3) The shadow prices help to determine the opportunity cost of introducing a new
product into the process. A new product can only be introduced with economic
viability if its opportunity cost is lower than its marginal contribution.

Slack and Surplus:

The slack of a constraint is the amount of unused capacity of the constraint. This applies to
the constraints that have a maximum amount available that can’t be exceeded i.e. ≤
constraint. The slack is computed as the difference between the used capacity of the
constraint and the maximum capacity.
Slack = Maximum capacity – Used capacity.
A constraint which has some idle capacity i.e. has a non zero slack has a shadow price of
zero. This is because the available amount is not completely used up.

The surplus of a constraint is the amount by which the minimum capacity is exceeded. The
surplus applies to those constraints where there’s a minimum value that must be exceeded i.e.
≥ constraints. It is computed as follows:
Surplus = Used capacity – Minimum capacity.

LP…
Uses of shadow prices:
4) The shadow price shows the additional value obtained by adjusting the capacity of a
constraint by 1 unit. This shows the additional improvement in the optimum value
when a constraint’s capacity is adjusted by 1 unit. Moreover it indicates the maximum
additional cost the management should incur to avail an extra unit of the constraint.
5) Shadow prices indicate the constraint that is more profitable to employ extra
resources. Holding other factors at constant, this should be the constraint with highest
shadow price.
6) The shadow prices help to determine the opportunity cost of introducing a new
product into the process. A new product can only be introduced with economic
viability if its opportunity cost is lower than its marginal contribution.
Slack and Surplus:
The slack of a constraint is the amount of unused capacity of the constraint. This applies to
the constraints that have a maximum amount available that can’t be exceeded i.e. ≤
constraint. The slack is computed as the difference between the used capacity of the
constraint and the maximum capacity.
Slack = Maximum capacity – Used capacity.
A constraint which has some idle capacity i.e. has a non zero slack has a shadow price of
zero. This is because the available amount is not completely used up.

The surplus of a constraint is the amount by which the minimum capacity is exceeded. The
surplus applies to those constraints where there’s a minimum value that must be exceeded i.e.
≥ constraints. It is computed as follows:
Surplus = Used capacity – Minimum capacity.

Simplex Method:
Is a matrix based method used to solve LPP with 2 or more variables.

Symbol Treatment
Type
1 ≤ Add a Slack (si) variable to the LHS of the equation.
e.g. x1 + 3x2 ≤ 12, now becomes
x1 + 3x2 + s1 = 12
2 ≥ Subtract the Surplus / Excess (Ei) variable and add Artificial
(Ai) variable to LHS of the equation.
e.g. 4x1 + 3x2 ≥ 6, now becomes
4x1 + 3x2 - E1 + A1 = 6
3 = e.g. 5x1 + 7x2 = 14
5x1 + 7x2 + A1 = 14

Basic Simplex Method Terminologies

1) Basic Variable
Is a variable which in the current solution do have positive values ie If the column is cleared
out and has only one non-zero element in it, then that variable is a basic variable.
2) Non-Basic Variable
Is a variable which in the current solution do have zero values ie If a column is not cleared
out and has more than one non-zero element in it, that variable is non-basic and the value of
that variable is zero.
3) Entering Variable
This is one of the current non-basic variables which can improve the objective function better
than other non-basic variables, if its value is raised above zero.
4) Entering/Key/Pivot Column
This is the column that contains the entering variable.
5) Leaving Variable
This is one of the current basic variables which must leave the basic and become non-basic
when the entering variable enters the basic.
6) Leaving/Key/Pivot Row
This is the row which contains the leaving variable.
7) Pivot Element
This is the positive coefficient at the intersection of the key column and the key row. It is
used for determining the leaving variable.
8) Old Pivot Equation
This is the equation of the current leaving variable.
9) New Pivot Equation
This is the equation to be taken by the entering variable. To determine the value divide the
old pivot equation by pivot element [old pivot equation ÷ pivot element]
10) Optimally Condition Rule
This is the rule used for determining the entering variable and also checking on whether the
solution is optimal or not. It states that for a maximization problem, the entering variable is
the current non-basic variable with the most negative coefficient in the objective function
(indicator) row.
If all of the non-basic coefficients in the objective function are positive then the optimal
solution has been obtained. The reverse is true for minimization problem.
11) Feasibility Rule/Condition
This is used for determining the leaving variable. It states that for both maximization and
minimization problems, the leaving variable are the current basic variable with the smallest
ratio or value in the RHS of the matrix. Use always positive coefficients in the entry column
to get these values. Ignore zero and negative coefficients.
Summary of steps in simplex procedure for a maximization problem:
1) Formulate the problem as a LP mathematical model using decision variables.
2) Introduce supplemental variables to convert the primal model into a standard form.
3) Construct a simplex tableau and enter the inequalities into the simplex tableau.
4) Find the initial solution.
5) Identify the variable with the most negative coefficient in the objective.
6) Identify the leaving variable. It is the variable in the row having the smallest ratio in
the RHS of the tableaus.
7) Determine the new pivot equation by dividing all the elements of the old pivot
equation by the pivot element.
8) Compute the values of the remaining rows using the formula
New row = Old row – [Element in the Pivot column X Element in the new
Pivot equation]
9) If there is negative value in the objective function, return to Step 6, however if there is
no negative value, stop because the current position is optimal.
Note: There are alternatives approaches like c-z being indicator row

Example
A company wants to know the most profitable mix of its product. At the moment it
manufactures transistors, resistors and electronic tubes with profit per hundred units of
sh.100, sh.60 and sh.40 respectively.
To produce a shipment of transistors containing 100 units requires 1 hour of engineering
services, 10 hours of direct labor and 2 hours of administrative services.
To produce 100 resistors requires 1 hour, 4 hours and 2 hours of engineering, direct labor and
administrative time respectively.
To produce one shipment of 100 of electronic tubes requires 1 hour of engineering, 5 hours
direct labor and 6 hours of administration.
There are 100 hours of engineering services, 600 hours of direct labor and 300 hours of
administrative available in the company.
Required:
Using the simplex determine the company’s profitable mix.

Solution
Decision variables
x1 = number of units in hundreds of transistors to be manufactured and sold.
x2 = number of units in hundreds of resistors to be manufactured and sold.
x3 = number of units in hundreds of electronic tubes to be produced and sold.

Primal model
Maximize Z = 100x1 + 60x2 + 40x3
Subject to constraints:
x1 + x2 + x3 ≤ 100 [Engineering hours]
10x1 + 4x2 + 5x3 ≤ 600 [Direct labor hours]
2x1 + 2x2 + 6x3 ≤ 300 [Administrative time]
x1, x2, x3 ≥ 0 [Non-negativity]

Standard form
Maximize Z= -100x1 - 60x2 - 40x3 = 0
Subject to constraints:
x1 + x2 + x3 + s1 = 100
10x1 + 4x2 + 5x3 + s2 = 600
2x1 + 2x2 + 6x3 + s3 = 300
x1, x2, x3, s1, s2, s3 ≥ 0

Simplex
Tableau
Basic
Variable x1 x2 x3 s1 s2 s3 RHS
s1 1 1 1 1 0 0 100
s2 10 4 5 0 1 0 600
s3 2 2 6 0 0 1 300
Z -100 -60 -40 0 0 0 0

s1 0 0.6 0.5 1 -0.1 0 40

x1 1 0.4 0.5 0 0.1 0 60
s3 0 1.2 5 0 -0.2 1 180
Z 0 -20 10 0 10 0 6000

x2 0 1 0.83 1.67 -0.17 0 66.67

x1 1 0 0.17 -0.67 0.17 0 33.33
s3 0 0 4 -2 0 1 100
Z 0 0 26.6 33.4 6.66 0 7,333.40

Sensitivity using simplex

RHS ranges:
Divide solutions with coefficients of Si and identify the min +ve and –ve value. The min +ve
represents the allowable reduction while the –ve represent the allowable increase. Eg
66.67/1.67=39.9;33.33/-0.67= -49.7;100/-2= -50
Hence max allowable decrease for resource 1 is 39.9 and decrease is 49.7
OF coefficients:
Divide Z row values aij coefficients in the matrix and identify the min +ve and –ve value.
The min +ve represents the allowable reduction while the –ve represent the allowable
increase. Eg
Substitution effect
This provides the consequences of withdrawal of a unit of resource or output in the process
eg
60*1.67-100*0.67=33.4 means by withdrawing a unit of constraint one from the process, you
lose 0.67 of x1 and gain 1.67 of x2 affecting the contribution by 33.4.
Special Situations in Linear Programming:
1) Unboundedness: This occurs the objective function can be improved without limits.

In maximization we can improve the solution indefinitely while for minimization we

reduce to zero. Using simplex, solution is unbounded when it is not possible to
determine the min ratio bj/aij yet it is not optimal
2) Redundancy-A constraint is said to be redundant if it does affect the feasible or
solution region. A redundant constraint is however not necessarily non-binding. A
binding constraint is one that determines the optimal solution.
3) Degeneracy: It is a situation in linear programming where one of the binding

constraint is redundant. In simplex, some of the basic variables [decision variables]

have a value of zero.
4) Multiple or alternate optimal solutions: This is a situation where there are several

solutions that optimize the objective function. This occurs when one of the constraints
has the slope as the objective function. In simplex, this is indicated by zero(s) in the
indicator row
5) Infeasibility: This is a situation where none of the solutions satisfies all the

constraints. In simplex, solution is infeasible when there is an artificial variable in the

basic column. This occurs due to wrong formulation.
Duality
This is the mirror image associated to any LPP. The original problem is referred to as the
primal and the mirror image the dual. Both are so much associated that the information for
one can be obtained from the other. In fact, the OF value for both is the same.
Primal-Dual relationship
1 if primal is a maxima, dual is a minima and vice versa
2 if primal has <= signs, dual has >= signs and vice versa
3 The number of constraints in primal is equal to the number of decision variables in dual and
vice versa
4 The column of constraints coefficients in primal forms the rows of constraint coefficients in
dual and vice versa
5The OF coefficients in primal forms the RHS values in dual
6 The dual of dual is the primal
7 If a problem has mixed constraints, ensure that they are of the same type before formulating
one problem to the other.
Using Excel's Built-In Solver
Max Z = 5x1 + 4x2
Subject to:
6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
-x1 + x2 ≤ 1
x2 ≤ 2
x1, x2 ≥ 0
A B C D E
1 x1 x2
2 Output 0 0
3 Unit profit 5 4 =formula
4 Resources: Used Available
5 M1 6 4 =formula 24
6 M2 1 2 =formula 6
7 DD diff -1 1 =formula 1
8 X2 DD 0 1 =formula 2

Solution steps
1. Click Solver button on the Excel Data tab, or the Premium Solver button on the Add-Ins
tab, which displays the Solver Parameters dialog.
2. In the Set Objective (or Set Target Cell) edit box, click on cell with the objective
function/formulae (D3)
3. In the By Changing Variable Cells edit box, select the cells that will contain the output
(B2:C2).
4. To add the constraints, we click on the Add button and select cells with the total resource
use formula in the Cell Reference edit box (D5:D8) (the left hand side), and select cells with
the available resources currently in the Constraint edit box(E5:E8) (the right hand side). The
default relation <= is OK
5. We choose the Add button again (either from the Add Constraint dialog above, or from the
main Solver Parameters dialog) to define the non-negativity constraint on the decision
variables. (Alternatively, we can check the Make Unconstrainted Variables Non-Negative
option in the Solver Parameters dialog.)
6. Click on the Solve button. The message "Solver found a solution" appears in the Solver
Results dialog
7. Click on "Answer" (and sensitivity if you wish)in the Reports list box to produce an
answer and sensitivity reports, and click OK.
Objective Cell (Max)
Original
Cell Name Value Final Value
$D$3 Unit profit 21 21
Variable Cells
Original
Cell Name Value Final Value Integer
$B$2 output x1 3 3 Contin
$C$2 output x2 1.5 1.5 Contin
Constraints
Cell Name Cell Value Formula Status Slack
$D$5 Used 24 $D$5<=$E$5 Binding 0
$D$6 Used 6 $D$6<=$E$6 Binding 0
Not
$D$7 Used -1.5 $D$7<=$E$7 Binding 2.5
Not
$D$8 Used 1.5 $D$8<=$E$8 Binding 0.5

Final Reduced Objective Allowable Allowable

Cell Name Value Cost Coefficient Increase Decrease
$B$2 output x1 3 0 5 1 3
$C$2 output x2 1.5 0 4 6 0.666666667
Final Shadow Constraint Allowable Allowable
Cell Name Value Price R.H. Side Increase Decrease
$D$5 Used 24 0.75 24 12 4
$D$6 Used 6 0.5 6 0.666666667 2
$D$7 Used -1.5 0 1 1E+30 2.5
$D$8 Used 1.5 0 2 1E+30 0.5

KARATINA UNIVERSITY
BBM355: OPERTAIONS RESEARCH I
REPLACEMENT ANALYSIS
Introduction
Replacement theory is concerned with the prediction of the replacement cost and the
determination of the most economic policy. Replacement deals with situation where
physical assets like machine vehicles or even human assets need replacement over
time. The assets need replacement because when they become old they tend to become
uneconomical due to increased cost of maintenance. Also advancement in technology
may lead to better equipment with higher efficiency than the ones currently being used.
There are two most common replacement analysis.
i. Items that deteriorate with time.
ii. Items that fail suddenly.
Assumption
- Replacement is with an identical asset in terms of:-
Maintenance cost
Depreciation profile
Useful life
Purchase cost
- The firm is a going concern

1) ITEMS THAT DETERIORATE WITH TIME (CAPITAL ITEMS)

There are relatively expensive items which could be kept functioning at increased
maintenance/running cost. The loss in capital value however decreases through time.

Features
- Relatively expensive
- Maintenance/running cost increase with time
- Capital loss decreases through time.
Total cost
Maintenance cost

Cmin

Capital loss

Problem/objective – what is the best replacement time, T, which will minimize average total
cost of the asset in the long run?

In respect of equipment that deteriorates in performance with passage of time, the optimal
for replacement is determined as follows.
n
Total cost over a given = c-s+∑ Mt = maintenance +Depn
t =1

Period of time
n
Average cost= 1/n(C-S+∑ Mt ) =1/n (maintenance+ Depn)
t =1

Where: C= purchase cost/price

S= value remaining after n years (scrap value)/salvage
M=maintenance cost over n years
Example 1
An electromechanical equipment has purchase price of kshs 70,000
Its running cost per year and the sales values are given as follows

Year 1 2 3 4 5 6 7 8
Running cost(sh 20 21 23 26 30 35 41 46
000)
Resale value( sh 40 30 22 16 14 7 7 7
000)
At which year is the replacement due
Solution

Year Maintenance Cumulative Resale C-S Total cost Average

(cost(Mt) Maintenance Value(s) 70-S (C-S+ total cost
n n
000 1/n(c-s+
cost ∑ M t ∑ Mt
t =1 t −1
n

∑M0
t −1
1 20 20 40 30 50 30
2 21 41 30 40 81 40.5
3 23 64 22 48 112 37.3336
4 26 90 16 54 144 36
5 30 120 14 56 176 35.2
6 35 155 7 63 218 36.33
7 41 196 7 63 259 37
8 46 242 7 63 305 38.125

Example 2
a) A machine costs sh.100,000. The annual running cost and the resale price in a given year
is as follows:-
Year (End) 1 2 3 4 5 6
Running 5,000 6,000 7500 8,000 8500 9500
cost(sh)
Selling price 95,000 93000 90,000 88,000 86,000 85,000
sh

If such type of a machine will be used for the foreseeable future, how frequently should it
be replaced?

b) The type in (a) above may be replaced by a second hand one, which may be one, two up
to five years old. The cost of buying the machine at various ages are as follows:
Age (years) 1 2 3 4 5
Purchase price (£ 000) 96 93 90 88 86
Required
Given this possibility, determine the optimal age to buy and sell the machine.

Suggested solution:
Cumulative maintenance cost
Age at sale
Age at 1 2 3 4 5 6
purchase
0 5000 11000 18500 26500 35000 44500
1 - 6000 13500 21500 30000 39000
2 - - 7500 15500 24000 33500
3 - - - 8000 16500 26000
4 - - - - 8500 18000
5 - - - - - 9500

Cumulative capital cost

1 2 3 4 5 6
0 5000 7000 10000 12,000 14000 15000
1 - 3000 6000 8000 10000 11000
2 - - 3000 5000 7000 8000
3 - - - 2000 4000 5000
4 - - - - 2000 3000
5 - - - - - 1000

Cumulative total cost

1 2 3 4 5 6
0 10,000 18,000 28,500 38,500 49,000 59,500
1 - 9,000 19,500 29,500 40,000 50,000
2 - - 10,500 20,500 31,000 41,500
3 - - - 10,000 20,500 31,000
4 - - - - 10,500 21,000
5 - - - - - 10,500

Average Total cost

1 2 3 4 5 6
0 10000 9000 9500 9625 9800 9917
1 - 9000 9750 9833 10000 10000
2 - - 10500 10250 10333 10375
3 - - - 10000 10250 10333
4 - - - - 10500 10500
5 - - - - - 10500

Conclusion: Buy a new one and replace after every2 years or buy a one year old and replace
after 1 year.
Example 3
Africa Airline purchases a particular type of plane at a cost of £40 million. The company
estimate that average capital cost and average operating cost are a function of x, the number
of hours of flight time since it started operation. The salvage value of a plane in £ is
expressed by the function.
S (x) = 36,000,000 – 10,000 x. Average operating cost in £ per hour of flight time is
estimated by a function C (x) = 500 + 0.4x
Required
a) Determine the total capital loss function and the average capital loss after x number of
flight hours.
b) Determine how many hours a plane should be flown before replacement if the objective is
to minimize the sum of average capital and average operating cost/hour.
c) What is the minimum average cost per hour?
d) What is the total cost of operating a plane in its life time?
e) What is the salvage value expected to equal.

a) i) Total capital cost

TC = Cost – Salvage
= 40m – 36m + 10,000x
= 4,000,000 + 10,000x
Total capital cost
ii. Average capital loss/cost =
x
4,000,000
= +10,000
x

b) hours of flight, before replacement

f (x) = Average capital + Average operating cost
4,000,000
f (x) = +10,000+500+0.4 x
x
df
= -4,000,000 x-2 + 0.4 = 0
dx

0.4 = 4,000,000 x-2

0.4 1
=
4,000,000 x

X=
√ 4,000,000
0.4
= 3162.28 hrs

c) Minimum Average cost f(x)

4,000,000
f(x) = + 10,000 + 500 + 0.4 (3162)
3162
= £13,029.8

d) Total operating cost

TC = Capital loss + Operating/running cost
= 4,000,000 + 10,000x + 500x + 0.4x2
= 4,000,000 + 10,000 (3162) + 500 (3162) + 0.4 (3162)2
TC = £41,200,297.6

e) Salvage value
f (x) = 36,000,000 – 10,000x
= 36,000,000 – 10,000 (3162)
= £4,380,000

2) ITEMS THAT FAIL SUDDENLY

These are items that either work well or fail completely. The loss of usefulness is
sudden and complete e.g. light bulbs, tubes e.t.c. The period between installation and
failure is not constant for any item but some probabilities can be assigned for analysis
purposes. These items are inexpensive in themselves but the cost consequence of
their failure could be huge/immense e.g. breakdown of a pipe costing sh 100 could
lead the entire refinery to be shut down.
There are two policies
a) Individual replacement policy
Under this policy an item is replaced immediately after its failure in a given system. This
ensures smooth running of the system.
b) Group replacement policy
Items are replaced at fixed intervals of time with
i) Those failing before mass replacement time replaced immediately
ii) Those failing before mass replacement time replaced as a batch at fixed period

Example
A firm has 200 bulbs. If a bulb fails it is replaced at a cost of sh 45. However there is a mass
replacement plan which reduces the individual cost by sh 20 open for choice by the firm. The
following survival rates of the bulbs over time has been provided
T 0 1 2 3 4 5 6 7 8
S(t) % 100 95 87 75 56 31 11 1 0
Required: The best policy assuming that under mass replacement, individual failures before
the fixed intervals of replacement are replaced as a batch at fixed times.

Suggested solution
Mass replacement
Month (i) Probability of a bulb failing in a given month (Pi) ∑ iPi
1 0.05 0.05
2 0.08 0.16
3 0.12 0.36
4 0.19 0.76
5 0.25 1.25
6 0.20 1.20
7 0.10 0.7
8 0.01 0.08
4.56

Let ni be the number of bulbs failing within every month. Therefore

no= 2000
n1 = 2000 x 0.05 = 100
n2 = 2000 x 0.08 + 0.05 x 100 = 165
n3 =2000 x 0.12 + 165 + 0.08 x 100 = 256
n4 = 2000 x 0.18 + 0.05 x 256 + 0.08 x 765 + 0.12 x 100 = 418
n5 = 2000 x 0.25 + 0.05 x 418+ 0.08 x 256 + 0.12 x 165 + 0.19 x 100 = 580
n6 = 2000 x 0.2 + 0.05 x 580 + 0.08 x 418 + 0.12 x 256 + 0.19 x 165 + 0.25 x 100 = 667
n7 = 2000 x 0.10 + 0.05 x 667+ 0.08 x 580 + 0.12 x 418 + 0.19 x 256 + 0.25 x 165 + 0.20 x
100 = 440
n8 = 2000 x 0.01 + 0.05 x 440 + 0.08 x 667 + 0.12 x 580 + 0.18 x 418 + 0.25 x 256 + 0.20 x
165 + 0.1 x 100 = 351
Cost analysis
Duration Average monthly cost Sh
Every 1 month 25 x 2000 50,000

Every 2 months 50,000+45 x 100 27,250

2
Every 3 months 50,000+45 x 265 20,642
3
Every 4 months 50,000+45 x 521 18361.25
4
Every 5 months 50,000+45 x 939 18,451
5
Every 6 months 50,000+45 x 1519 19,726
6
Every 7 months 50,000+45 x 2186 21,196
7
Every 8 months 50,000+45 x 2626 21,021
8

Individual replacement
Expected monthly cost = Individual replacement cost x Expected monthly failures of bulbs in
the long term
1
= 45 x 2000 x
∑ i Pi
1
= 45 x 2000 x
4.56
= sh 19,736
Recommendation: Do mass replacement after every 4 months

Question (post optimality)

At what group replacement price per tube should a policy of strictly individual replacement
become preferable to the adopted policy?

a) For individual replacement to be preferable

Individual replacement cost ≤ Mass replacement cost
Let C be the mass replacement cost then
2000 c+ 45 x 521
19736 =
4

2000 c+521 x 45
19736 =
4
C =sh 27
Beyond mass replacement cost of 27 use individual replacement.
Question: Suppose under mass replacement, bulbs failing before the fixed mass replacement
period are replaced as and when they fail, what would be the decision?

KARATINA UNIVERSITY
CMS 201: OPERATIONS RESEARCH 1
SIMULATION
Definition
Simulation can be defined as a quantitative technique which describes a
process by developing a model of that process and then conducting a
series of organized trial and error experiments to predict the behaviour of
the process through time often with an aid of a computer. It is not an
analytical technique neither is it an optimisation tool.

It is a general method which can be used to solve problems in areas of

management e.g. Queuing theory (waiting lines), Capital budgeting,
Project management, CVP analysis (Profit analysis) etc. It is usually used
when the number of assumptions is violated.

When Simulation is used

1. When you have unattainable/untenable/unrealistic assumptions.
2. When system takes too long to observe e.g population/demographic
issues.
3. Cost and danger of experimenting with real world situations is high.
4. Difficulty of observation e.g. space research, molecular (particle)
research.

Steps in Simulation
1. Define the problem you require to solve.
2. Identify the relevant decision variables.
3. Formulate the model you intend to use.
4. Specify values of the decision variables to be tested and collect the
relevant data.
5. Test the model by comparing its behaviour with that of the actual
problem environment i.e. run the simulation trials.
6. Change the values of the decision variables in step 4 and run the
simulation again. This process is repeated until the results
approximate reality as close as possible or some other object is
achieved e.g. until average daily costs is minimized, profit is
maximized etc.
MONTE-CARLO SAMPLING TECHNIQUES
This is a technique or a way of allocating random numbers. When a
system contains elements that exhibit chance in their behavior, the
method of Monte-Carlo sampling may be applied. The basis of this
method is experimentation on the chance or probabilistic elements
through sampling.

STEPS
1. Set up probability distributions for the relevant random variables.
2. Build a cumulative probability distribution for each variable in step 1.
3. Establish intervals of random number for each variable and allocate the
random number ranges.
4. Obtain the random numbers from a calculator, a computer or a table of
random numbers.
5. Perform the simulation.

Example
1. X1 Prob Cum Random no.
prob range
10 0.1 0.1 0
20 0.4 0.5 1–4
30 0.3 0.8 5–7
40 0.2 1.0 8, 9

2. Y1 Prob Cum Random no.

prob range
1 0.05 0.05 00 – 04
2 0.10 0.15 05 - 14
3 0.31 0.46 15 – 45
4 0.29 0.75 46 – 74
5 0.11 1.00 75 – 99

3. W1 Prob Cum Random no.

prob range
1 0.11 0.111 000 – 110
1
2 0.52 0.634 111 – 633
3
3 0.18 0.822 634 – 821
8
4 0.17 1.000 822 - 999
8
Role of Computer in Simulation (Advantages)
1. It generates random numbers.
2. A computer simulates thousands of trials.
- Extremely fast
- Accurately
- Reliably
- Also stores massive quantities of data
3. The computer simulates several combinations of decision variables e.g.
order quantity and reorder levels in a matter of seconds.
4. It provides management with reports which are sued in decision
making.

ADVANTAGES OF SIMULATION
1. Simulation is well suited for problems that are difficult or impossible to
solve analytically e.g. where many assumptions could be violated e.g.
inventory management, queuing problems, capital budgeting.
2. Simulation allows an analyst or decision maker to experiment with
system behaviour in a controlled environment instead of real life
setting which can be very costly due to inherent risk.
3. It enables a decision maker to compress time in order to evaluate long
time effect of various alternatives.
4. It can serve as a mode for training decision makers by enabling them
to observe the behaviour of a system under different conditions
without experimenting with the actual system.

DISADVANTAGES OF SIMULATION
1. Simulation is not precise. It is not an optimization process and does
not necessarily yield on optimal answer but merely provides a set of
the systems responses to different operating conditions. In many
cases, this lack of precision is difficult to measure. However, as the
number of trials increase, precision increases provided the probability
distribution of the relevant variables do not change.
2. A good simulation model many be expensive in terms of
i. Design personnel (Consultant)
ii. Computing facilities, especially appropriate software.
3. Each simulation model is unique. Its solutions and inferences are not
usually transferable to either problems and thus further increase the
cost of simulation.
4. Simulation can take time in terms
i. Data collection
ii. Design of model. This would delay decision making which is
costly in the long run.
Example
Nyundo service station intends to open a new service in Mlolongo town. A
market has projected the inter arrival times of the vehicles at the new
service station as follows.
Inter -arrival time (minutes) probability
3 0.17
4 0.25
5 0.25
6 0.20
7 0.13
The management of the service station intends to install only one
dispensing pump at the new service station. The attendant at the new
service station can serve customers at the following rates.
Service time (minutes) probability
3 0.10
4 0.30
5 0.40
6 0.15
7 0.05
The following random numbers have been provided.
24395745772768296458868985148939618402115623729483830297998
310933433534994377922122787007943131449
Required
i) If the station opens at 7am, simulate a system of 15 vehicles and
determine the number of vehicles waiting for service at any time (12
marks).
ii) The average waiting time per vehicle from your calculations in (i)
above (3 marks)

(a) Arrival Prob. Cum. RN- Servic Prob. Cum. RN-

time Prob. Range e time Prob. Range
(Min) (min)
3 0.17 0.17 00-16 3 0.10 0.10 00-09
4 0.25 0.42 17-41 4 0.30 0.40 10-39
5 0.25 0.67 42-66 5 0.40 0.80 40-79
6 0.20 0.87 67-86 6 0.15 0.95 80-94
7 0.13 1.00 87-99 7 0.05 1.00 95-99

Vehicl RN Inter- Arriva RN Servic Servic Servic Waitin

e No. arrival l time e e e g time
time time begin end
(Min) (min)
1 24 4 7.04 39 4 7.04 7.08 0
2 57 5 09 45 5 09 14 0
3 77 6 15 27 4 15 19 0
4 68 6 21 29 4 21 25 0
5 64 5 26 58 5 26 31 0
6 86 6 32 89 6 32 38 0
7 85 6 38 14 4 38 42 0
8 89 7 45 39 4 45 49 0
9 61 5 50 84 6 50 56 0
10 02 3 53 11 4 56 8.00 3
11 56 5 58 23 4 8.00 04 2
12 72 6 8.04 94 6 04 10 0
13 83 6 10 83 6 10 16 0
14 02 3 13 97 7 16 23 3
15 99 7 20 83 6 23 29 3
11

(ii) Average waiting time for each vehicle = 11/15 min per vehicle

SIMULATION USING A CONTINUOUS PROBABILITY DISTRIBUTION

It is possible to perform simulation using a continuous probability
distribution e.g. normal distribution, depending on the likely nature of the
distribution of the relevant variables. For the normal distribution, a table
of random numbers would contain Z values (no. of standard deviations
away from the mean) with µ = 0 and θ = 1, but distributed as per the
density of the normal variate.

Therefore, to obtain a simulated value for a normal variate.

Simulated value = Mean + Z* standard deviation.
X = µ + Zθ
X−μ
Z=
θ
Hence, for the variable to be simulated, µ and θ must be stated.

Illustration
A firm deals in a product whose demand can be approximated by the
normal distribution. The sales department of the firm is particularly
interested in the impact of increasing its capacity of processing of orders
received, which is currently limited to a maximum of 45 orders on any one
day. The number of orders arriving per day, like the demand for the
product is also approximately normal with a mean of 50 orders and a
standard deviation of 10 orders. The sales department is considering
hiring an extra clerk to reduce processing time, this would increase the
possible number of orders to be processed to 55 daily, and in turn reduce
back-order costs. Back order costs are currently shs.8,000 per month on
average. The company operates for 25 days a month and the extra
additional clerk would be paid shs.5,000 per month. Back order costs are
shs.20 per back-order per day.

Required: Assuming back orders from the previous month are 7, should
the additional clerk be hired.

Working assumption 1
Capacity = 55 units, µ = 50 θ = 10

SIMULATION WORKSHEET
DAY Z NO. OF BACK TOTAL TO NO. NO. NOT
based ORDERS ORDERS BE PROCESSE PROCESSE
on RN ARRIVING PROCESSE D D (BACK-
= 50 + D ORDERS)
10z
1 .5 55 7 62 55 7
2 .1 51 7 58 55 3
3 1.5 65 3 68 55 13
4 1.0 60 13 73 55 18
5 1.4 64 18 82 55 27
6 .9 59 27 86 55 31
7 1.2 62 31 93 55 38
8 -1.5 35 38 73 55 18
9 -.07 43 18 61 55 6
10 1.4 64 6 70 55 15
11 -0.5 45 15 60 55 5
12 -1.4 36 5 41 41 -
13 -1.0 40 - 40 40 -
14 -0.0 50 - 50 50 -
15 1.4 64 - 64 55 9
16 -1.8 32 9 41 41 -
17 -0.1 49 - 49 49 -
18 -1.3 37 - 37 37 -
19 1.0 60 - 60 55 5
20 0.3 53 5 58 55 5
21 -1.8 32 3 35 35 -
22 -1.2 38 - 38 38 -
23 0.7 57 - 57 55 2
24 -0.4 46 2 48 48 -
25 -1.4 36 - 36 36 -
200
Working assumption 2
The number of orders arriving is not affected by hiring an extra clerk

Cost analysis proposed system

Back order cost = 200 x 20 = shs.4, 000
Clerks salary = shs.5, 000
Shs.9, 000
Current cost = shs.8, 000
Recommendation – Retain the current system i.e. do not hire the clerk.

Self-test questions
Question One
The demand for a product on a given day is random. The unit price is sh.10 and unit variable
cost is sh 7. The fixed cost is sh. 5000 per day. The distribution of daily demand is as follows:
Days Demand Probability
1000 0.05
1500 0.10
2000 0.31
2500 0.29
3000 0.25
1.00
Required
(a) Simulate profits for this product for 10 days and hence calculate the average daily profit
(b) From the simulation results determine the following:
i. Probability of at least breaking even
ii. Probability of a loss of sh.1000 or worse
iii. Probability of making a profit greater than sh.2500

Question Two
Vincent an MBA student at a University has been having problems balancing his cash book.
His monthly income is derived form a graduate research assistantship; however, he also
makes extra money in most months by tutoring undergraduates in their quantitative analysis
course. His chances of various income levels are as shown.
Monthly Income (sh) Probability
350 0.40
400 0.20
450 0.30
500 0.10
Assume this income is received at the beginning of each month.
Vincent’s expenditures also vary from month to month and he estimates that they will follow
this distribution:
Monthly Expenses (sh) Probability
300 0.10
400 0.45
500 0.30
600 0.15
He begins his final year with sh 600 in his account. Simulate the 12 months cash flow and
discuss his financial picture.

Question Three
Management of the FCB is concerned over a loss of customers at its main office downtown.
One solution that has been proposed is to add one or more “drive-through” teller stations to
make it easier for customers in cars to obtain quick service without parking. Chris, the bank
president, thinks the bank should only risk cost of installing one drive-through. He is
informed by his staff that the cost (amortized over a 20-year period) of building a drive
through is sh 12000 per year. It costs sh. 16000 per year in wages and benefits to staff each
new teller window.
The director of Management Analysis, Anita Greenberg, believes that the following two
factors encourage the immediate construction of two drive-through stations, however.
According to a recent article in banking research magazine, customers who wait in long
lines for drive-through teller service will cost banks an average of sh 1.00 per minute ,in loss
of goodwill. Also, adding a second drive-through will cost an additional sh.16000 in staffing,
but amortized construction costs can be cut to a total of sh.20000 per year if two drive-
through are installed together, instead of one at a time. To complete her analysis mrs
Greenberg, collected one month’s worth of arrival and services rates competing downtown
bank’s drive-through stations. These data are shown as observation analysis 1 and 2 below.

LP…
Uses of shadow prices:
7) The shadow price shows the additional value obtained by adjusting the capacity of a
constraint by 1 unit. This shows the additional improvement in the optimum value
when a constraint’s capacity is adjusted by 1 unit. Moreover it indicates the maximum
additional cost the management should incur to avail an extra unit of the constraint.
8) Shadow prices indicate the constraint that is more profitable to employ extra
resources. Holding other factors at constant, this should be the constraint with highest
shadow price.
9) The shadow prices help to determine the opportunity cost of introducing a new
product into the process. A new product can only be introduced with economic
viability if its opportunity cost is lower than its marginal contribution.
Slack and Surplus:
The slack of a constraint is the amount of unused capacity of the constraint. This applies to
the constraints that have a maximum amount available that can’t be exceeded i.e. ≤
constraint. The slack is computed as the difference between the used capacity of the
constraint and the maximum capacity.
Slack = Maximum capacity – Used capacity.
A constraint which has some idle capacity i.e. has a non zero slack has a shadow price of
zero. This is because the available amount is not completely used up.

The surplus of a constraint is the amount by which the minimum capacity is exceeded. The
surplus applies to those constraints where there’s a minimum value that must be exceeded i.e.
≥ constraints. It is computed as follows:
Surplus = Used capacity – Minimum capacity.

Simplex Method:
Is a matrix based method used to solve LPP with 2 or more variables.

Symbol Treatment
Type
1 ≤ Add a Slack (si) variable to the LHS of the equation.
e.g. x1 + 3x2 ≤ 12, now becomes
x1 + 3x2 + s1 = 12
2 ≥ Subtract the Surplus / Excess (Ei) variable and add Artificial
(Ai) variable to LHS of the equation.
e.g. 4x1 + 3x2 ≥ 6, now becomes
4x1 + 3x2 - E1 + A1 = 6
3 = e.g. 5x1 + 7x2 = 14
5x1 + 7x2 + A1 = 14

Basic Simplex Method Terminologies

1) Basic Variable
Is a variable which in the current solution do have positive values ie If the column is cleared
out and has only one non-zero element in it, then that variable is a basic variable.
2) Non-Basic Variable
Is a variable which in the current solution do have zero values ie If a column is not cleared
out and has more than one non-zero element in it, that variable is non-basic and the value of
that variable is zero.
3) Entering Variable
This is one of the current non-basic variables which can improve the objective function better
than other non-basic variables, if its value is raised above zero.
4) Entering/Key/Pivot Column
This is the column that contains the entering variable.
5) Leaving Variable
This is one of the current basic variables which must leave the basic and become non-basic
when the entering variable enters the basic.
6) Leaving/Key/Pivot Row
This is the row which contains the leaving variable.
7) Pivot Element
This is the positive coefficient at the intersection of the key column and the key row. It is
used for determining the leaving variable.
8) Old Pivot Equation
This is the equation of the current leaving variable.
9) New Pivot Equation
This is the equation to be taken by the entering variable. To determine the value divide the
old pivot equation by pivot element [old pivot equation ÷ pivot element]
10) Optimally Condition Rule
This is the rule used for determining the entering variable and also checking on whether the
solution is optimal or not. It states that for a maximization problem, the entering variable is
the current non-basic variable with the most negative coefficient in the objective function
(indicator) row.
If all of the non-basic coefficients in the objective function are positive then the optimal
solution has been obtained. The reverse is true for minimization problem.
11) Feasibility Rule/Condition
This is used for determining the leaving variable. It states that for both maximization and
minimization problems, the leaving variable are the current basic variable with the smallest
ratio or value in the RHS of the matrix. Use always positive coefficients in the entry column
to get these values. Ignore zero and negative coefficients.
Summary of steps in simplex procedure for a maximization problem:
10) Formulate the problem as a LP mathematical model using decision variables.
11) Introduce supplemental variables to convert the primal model into a standard form.
12) Construct a simplex tableau and enter the inequalities into the simplex tableau.
13) Find the initial solution.
14) Identify the variable with the most negative coefficient in the objective.
15) Identify the leaving variable. It is the variable in the row having the smallest ratio in
the RHS of the tableaus.
16) Determine the new pivot equation by dividing all the elements of the old pivot
equation by the pivot element.
17) Compute the values of the remaining rows using the formula
New row = Old row – [Element in the Pivot column X Element in the new
Pivot equation]
18) If there is negative value in the objective function, return to Step 6, however if there is
no negative value, stop because the current position is optimal.
Note: There are alternatives approaches like c-z being indicator row

Example
A company wants to know the most profitable mix of its product. At the moment it
manufactures transistors, resistors and electronic tubes with profit per hundred units of
sh.100, sh.60 and sh.40 respectively.
To produce a shipment of transistors containing 100 units requires 1 hour of engineering
services, 10 hours of direct labor and 2 hours of administrative services.
To produce 100 resistors requires 1 hour, 4 hours and 2 hours of engineering, direct labor and
administrative time respectively.
To produce one shipment of 100 of electronic tubes requires 1 hour of engineering, 5 hours
direct labor and 6 hours of administration.
There are 100 hours of engineering services, 600 hours of direct labor and 300 hours of
administrative available in the company.
Required:
Using the simplex determine the company’s profitable mix.

Solution
Decision variables
x1 = number of units in hundreds of transistors to be manufactured and sold.
x2 = number of units in hundreds of resistors to be manufactured and sold.
x3 = number of units in hundreds of electronic tubes to be produced and sold.

Primal model
Maximize Z = 100x1 + 60x2 + 40x3
Subject to constraints:
x1 + x2 + x3 ≤ 100 [Engineering hours]
10x1 + 4x2 + 5x3 ≤ 600 [Direct labor hours]
2x1 + 2x2 + 6x3 ≤ 300 [Administrative time]
x1, x2, x3 ≥ 0 [Non-negativity]

Standard form
Maximize Z= -100x1 - 60x2 - 40x3 = 0
Subject to constraints:
x1 + x2 + x3 + s1 = 100
10x1 + 4x2 + 5x3 + s2 = 600
2x1 + 2x2 + 6x3 + s3 = 300
x1, x2, x3, s1, s2, s3 ≥ 0

Simplex
Tableau
Basic
Variable x1 x2 x3 s1 s2 s3 RHS
s1 1 1 1 1 0 0 100
s2 10 4 5 0 1 0 600
s3 2 2 6 0 0 1 300
Z -100 -60 -40 0 0 0 0

s1 0 0.6 0.5 1 -0.1 0 40

x1 1 0.4 0.5 0 0.1 0 60
s3 0 1.2 5 0 -0.2 1 180
Z 0 -20 10 0 10 0 6000

x2 0 1 0.83 1.67 -0.17 0 66.67

x1 1 0 0.17 -0.67 0.17 0 33.33
s3 0 0 4 -2 0 1 100
Z 0 0 26.6 33.4 6.66 0 7,333.40

Sensitivity using simplex

RHS ranges:
Divide solutions with coefficients of Si and identify the min +ve and –ve value. The min +ve
represents the allowable reduction while the –ve represent the allowable increase. Eg
66.67/1.67=39.9;33.33/-0.67= -49.7;100/-2= -50
Hence max allowable decrease for resource 1 is 39.9 and decrease is 49.7
OF coefficients:
Divide Z row values aij coefficients in the matrix and identify the min +ve and –ve value.
The min +ve represents the allowable reduction while the –ve represent the allowable
increase. Eg
Substitution effect
This provides the consequences of withdrawal of a unit of resource or output in the process
eg
60*1.67-100*0.67=33.4 means by withdrawing a unit of constraint one from the process, you
lose 0.67 of x1 and gain 1.67 of x2 affecting the contribution by 33.4.
Special Situations in Linear Programming:
6) Unboundedness: This occurs the objective function can be improved without limits.

In maximization we can improve the solution indefinitely while for minimization we

reduce to zero. Using simplex, solution is unbounded when it is not possible to
determine the min ratio bj/aij yet it is not optimal
7) Redundancy-A constraint is said to be redundant if it does affect the feasible or
solution region. A redundant constraint is however not necessarily non-binding. A
binding constraint is one that determines the optimal solution.
8) Degeneracy: It is a situation in linear programming where one of the binding

constraint is redundant. In simplex, some of the basic variables [decision variables]

have a value of zero.
9) Multiple or alternate optimal solutions: This is a situation where there are several

solutions that optimize the objective function. This occurs when one of the constraints
has the slope as the objective function. In simplex, this is indicated by zero(s) in the
indicator row
10) Infeasibility: This is a situation where none of the solutions satisfies all the

constraints. In simplex, solution is infeasible when there is an artificial variable in the

basic column. This occurs due to wrong formulation.
Duality
This is the mirror image associated to any LPP. The original problem is referred to as the
primal and the mirror image the dual. Both are so much associated that the information for
one can be obtained from the other. In fact, the OF value for both is the same.
Primal-Dual relationship
1 if primal is a maxima, dual is a minima and vice versa
2 if primal has <= signs, dual has >= signs and vice versa
3 The number of constraints in primal is equal to the number of decision variables in dual and
vice versa
4 The column of constraints coefficients in primal forms the rows of constraint coefficients in
dual and vice versa
5The OF coefficients in primal forms the RHS values in dual
6 The dual of dual is the primal
7 If a problem has mixed constraints, ensure that they are of the same type before formulating
one problem to the other.
Using Excel's Built-In Solver
Max Z = 5x1 + 4x2
Subject to:
6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
-x1 + x2 ≤ 1
x2 ≤ 2
x1, x2 ≥ 0
A B C D E
1 x1 x2
2 Output 0 0
3 Unit profit 5 4 =formula
4 Resources: Used Available
5 M1 6 4 =formula 24
6 M2 1 2 =formula 6
7 DD diff -1 1 =formula 1
8 X2 DD 0 1 =formula 2

Solution steps
1. Click Solver button on the Excel Data tab, or the Premium Solver button on the Add-Ins
tab, which displays the Solver Parameters dialog.
2. In the Set Objective (or Set Target Cell) edit box, click on cell with the objective
function/formulae (D3)
3. In the By Changing Variable Cells edit box, select the cells that will contain the output
(B2:C2).
4. To add the constraints, we click on the Add button and select cells with the total resource
use formula in the Cell Reference edit box (D5:D8) (the left hand side), and select cells with
the available resources currently in the Constraint edit box(E5:E8) (the right hand side). The
default relation <= is OK
5. We choose the Add button again (either from the Add Constraint dialog above, or from the
main Solver Parameters dialog) to define the non-negativity constraint on the decision
variables. (Alternatively, we can check the Make Unconstrainted Variables Non-Negative
option in the Solver Parameters dialog.)
6. Click on the Solve button. The message "Solver found a solution" appears in the Solver
Results dialog
7. Click on "Answer" (and sensitivity if you wish)in the Reports list box to produce an
answer and sensitivity reports, and click OK.
Objective Cell (Max)
Original
Cell Name Value Final Value
$D$3 Unit profit 21 21
Variable Cells
Original
Cell Name Value Final Value Integer
$B$2 output x1 3 3 Contin
$C$2 output x2 1.5 1.5 Contin
Constraints
Cell Name Cell Value Formula Status Slack
$D$5 Used 24 $D$5<=$E$5 Binding 0
$D$6 Used 6 $D$6<=$E$6 Binding 0
Not
$D$7 Used -1.5 $D$7<=$E$7 Binding 2.5
Not
$D$8 Used 1.5 $D$8<=$E$8 Binding 0.5

Final Reduced Objective Allowable Allowable

Cell Name Value Cost Coefficient Increase Decrease
$B$2 output x1 3 0 5 1 3
$C$2 output x2 1.5 0 4 6 0.666666667
Final Shadow Constraint Allowable Allowable
Cell Name Value Price R.H. Side Increase Decrease
$D$5 Used 24 0.75 24 12 4
$D$6 Used 6 0.5 6 0.666666667 2
$D$7 Used -1.5 0 1 1E+30 2.5
$D$8 Used 1.5 0 2 1E+30 0.5

THE TRANSPORTATION MODEL

Background
Suppose there is an item, which is kept in geographically dispersed or
separated locations and is required similarly at geographically dispersed
locations. Each source can only supply a certain quantity in a given period
while each destination has periodic minimum requirements.
To transport an item from a given source is to a given destination requires
some money per unit.
The network

C11 D1
S1
C12

C21

C22

S2 D2
The problem – How many units should be transported from source to a
given destination in order to minimize total transportation cost or
maximize the schedule

The structure
1 2 N Supply

1 C C C a1
11 12 1n
X11 X12 X1n
2 C C C a2
21 22 2n
X21 X22 X2n

M C C am
m1 mn
Xm1 Xmn
Demand b1 b2 bn

The symbol.
C ij ≡ Unit transportation cost from source i to destination j
X ij≡ Number of units transported from source i to destination j
(the unknown or the decision variables)
ai ≡ maximum capacity of source i in a given period.
j≡ Minimum requirements by destination j
Let C ≡ total transportation cost – to be minimized (objective function
value)
O F Min C = C11,X11+C12,X12+………………………..+CmnXmn
St
1) Source constraints (maximum supply)
X11+X12+…….Xm1≤a1
X21+X22+…….X2m≤a2 etc

2) Destination constraints (minimum demand)

X11+X21+…….Xm1≥b1
X12+X22+…….Xm2≥b2 etc

3) Non- negativity
All x1 ≥ 0

Steps followed in solving a Transportation problem.

1. Ensure that the problem is balanced i.e total supply = total demand. If
it is not balanced, creates a dummy / fictitious source or destination to
take up the surplus.
2. Set up the initial transportation table, which will have supply for every
source, demand for every source to every destination and unit cost of
transportation an item from every source to every destination.
3. Obtain an initial allocation (solution) by using one of the following
methods.
i) North west corner method (NWC)
ii) Least cost sell method (LCCM)
iii) Vogel’s Approximation Method (VAM)
4. Test for degeneracy: This a problem that arises when the number of
satisfied cells is less than r+c-1. The difference between the two is
called the degree of degeneracy. In practice it means the solution to
the problem is indeterminate since it oscillates in a manner such that
the shadow prices of the unsatisfied cells cannot be fully determined. It
occurs when there is a simultaneous satisfaction of a cell row wise and
column wise.
Remedy: Fill up hypothetical cell(s) to the extent of the degree of
degeneracy in the row/column(s) that gave rise to the problem to
facilitate the determination of shadow prices of the unfilled up cells. No
units can be transferred from such a cell(s) but units can be loaded
there into.
5. Evaluate the initial solution for optimality. This requires that every
empty cell is assessed to determine if the solution can be improved by
moving units to that cell. At optimality, all shadow prices must be ≥ 0
for a minimization problem. Zero implies that the solution is not unique
(not the only one ie there are alternatives as many are the number of
zeros)
If the solution is not optimal, take units to the cell that has the highest
negative improvement index (also called shadow price or opportunity
cost). In case of a tie, take units to the cell that can accommodate the
highest number of units & in case of a further tie allocate arbitrary
Repeat iterations 4 and 5 till optimality.
There are 2 optimality evaluation methods.
i) Stepping stone method (SSM)
ii) Modified distribution method(MOD)
North West corner Rule (NWCR).

A B C Supply

W 4 8 8
56 56

X 16 24 16
16 66 82

Y 8 16 24
36 41 77

Demand 72 102 41 215

Least cost cell method (LCCM) INITIAL SOLUTION.

We begin allocation with the cell which has the least cost progressing to
the next least cost cell which can accept units until all cells which can
accept units are satisfied. If there is a tie, take units to the cell, which can
accept more but if there is still a tie. allocate arbitrarily. This method gives
a better initial solution than NWC since we explicitly take the cost into
account.

A B C Supply

W 4 8 56
8
56
X 1 1 82
24
6 6
41
41
Y 8 77
16 24
16
61
Demand 72 106 41 215

Vogel’s Approximation method (VAM) (initial solution)

VAM is a technique that is based on the concept of minimizing opportunity
cost which is given as the difference between the lowest cost and the
second lowest cost for each row and column for cells which can accept
units.
Principle: If we fail to put units in the lowest cost cell in a given row or
column, by how much will we be losing in possible cost savings if we put
units in the next lowest cost cell? This method gives a very good initial
solution.

Steps
1. For each eligible row / column, find the difference between the lowest
cost and the next lowest cost cell which can take units. These are
known as ‘’penalties’’ or ‘’opportunity cost’’
2. Identify the largest penalty and allocate as many units as possible to
the cell with the lowest cost in the row or column in which the largest
penalty falls. If there is a tie in the cost, allocate units to the cell which
can take more, but if there is still a tie in number of units, allocate
arbitrarily
3. Calculate the penalties again and reallocate, continue with the iteration
until all eligible cells are filled.
When recalculating the penalties, cells which cannot take units do not
participate since their opportunity costs are zero.

Initial solution by VAM

A B C Supply penalties

W 56,0 4
4 8 8
56
X 82,41,0 8,8
16 24 16
41 41
Y 77,5,0 8,8
8 16 24
72 5
Demand 72,0 102,46,5 41,0 215
,0
penalties 4,8 8,8 8,8
Optimality check
1. Stepping stone method (SSM)
SSM is a method for evaluating a transportation problem for optimality
which uses the concept of opportunity cost.
The question is by moving units to an unfilled cell (removed from a filled
cell) is it possible to lower total transportation cost? If it is possible then
the problem is not optimal. This would be the case if there are negative
shadow prices which represent possible cost savings, To minimize the
number of iterations/ tables we take units to the cell with the highest
positive shadow price (this is the entering variable). The leaving variable
would be the cell with the smallest quantity to be subtracted. This process
is continued until all shadow prices are zero or positive.
Initial solution by LCCM
A B C Supply

W 4 8 8
56 56

X 16 24 16
41 41 82

Y 8 16 24
16 61 77

Demand 72 102 41 215

Degeneracy check.
r +c-1 =+3+3-1 = 5
Filled up/satisfied=5 hence not degenerate
Shadow prices of unsatisfied cells
WB=8-4+8-16=-4
WC=8-16+24-16+8-4=4
XA=0
YC=16
Not optimal due to –ve shadow price. Therefore take 56 units from cell WA
(leaving cell) to cell WB (entering cell). To maintain the row and column
totals, remove 56 units from cell YB and add the same to cell YA. Test for
optimality again (shadow prices shown in blue)
A B C Supply
W 4 56 8 56
X 0 41 41 82
Y 72 5 16 77
Demand 72 102 41 215
All the shadow prices are ≥0 hence solution is optimal but not unique.
The solution is
From To units*cost TC
W B 56*8= 448
X B 41*24= 984
X C 41*16= 656
Y A 72*8= 576
Y B 5*16= 80
2744
2. Modified distribution method (MODI)
MODI is an alternative method for SSM for optimality check which makes
use of row and column indices. These are computed using the fact that
the opportunity cost of a filled cell is zero. This enables a series of
equation to be obtained so that the various row and column indices can
be found. This then makes it possible to evaluate the empty cells.

ILLUSTRATION
Obtain the initial solution using LCCM and check for optimality using MODI
K1=?) K2=? K3=?
A B C Supply

W (r1=0) 4 8 8
56 56

X (r2=?) 16 24 16
41 41 82

Y (r2=?) 8 16 24
16 61 77

Demand 72 102 41 215

Notes;
1. Let ri and kj represent row i and column j indices respectively.
2. The opportunity cost of any cell is given by cij –ri – kj,
cij ≡ unit transportation cost from source i to destination j.
3. For any filled cell opportunity cost / shadow price is zero.
4. Thus for any filled cell, cij – Ri – Kj = 0, Cij =R1 +Kj
1. R1+K1= 4 No of unknown = 6
2. R2+K2 = 24 no of equation = 5
3. R2+K3 = 16 shortage in equation = 1
4. R3+K1 = 8 traditionally R1=0
5. R3+K2 = 16
This means that R3 =4, k2=12, r2=12, k3=4 hence
Shadow the prices
WB=+8-12-0=-4
XA=0
WC=+8-4=4
YC=16
Therefore take 56 units from cell XA (leaving cell) to cell WB (entering
cell). To maintain the row and column totals, remove 56 units from cell YB
and add the same to cell YA. Test for optimality again

A (k1=0) B (k2=8) C Supply

(k3=0)
W (r1=0) 4 56 8 56
X (r2=16) 0 41 41 82
Y (r3=8) 72 5 16 77
Demand 72 102 41 215
The shadow prices are shown in blue (all >=0) hence solution is optimal
but not unique.

SPECIAL CASES IN TRANSPORTATION MODEL.

1. Unbalance problem.
Is where total demand and supply are not equal. If a transportation
problem is not balanced, create a dummy/ fictitious source or
destination to take the excess supply or demand.
Specifically if:
Supply > demand create dummy destination
Supply < demand create dummy source.
Since dummy cells are nonexistent, unit transportation for such cells
are zero.
When using LCCM or VAM for initial solution, we ignore the dummy
cells since the objective is not to allocate units to dummy cells. For
VAM too, dummy cells do not participate in calculation of the penalties.
2. Infeasible or impossible routes.
Is where it is not possible to transfer units from a particular source to a
certain destination due to restrictions. Ignore the route or attach a very
large unit transportation cost (for minimization) or a very low unit
contribution (for maximization) such that it is prohibitive to put units in
such a cell and continue with the usual transportation procedures.

ILLUSTRATION.
Suppose source W can supply an additional 20 units i.e 76 units in total
and also W cannot supply A, Obtain the initial solution using VAM and
check for optimality using MODI.
Excess supply = 20 units ¿> ¿ create a dummy destination to take these
additional 20 units.

A B C Dummy Supply

W 76 76
X 0 21 41 20 82
Y 72 5 77
Demand 72 102 41 20 235

Degeneracy check
R+C=1=3+4+1 = 6
Number of official cell = 6
Remarks
Initial solution is optimal since all shadow prices are ≥0
The optimal solution is not unique since there is a zero shadow price in
cell Xa.
Dummy allocation – plant X will manufacture 82-20 = 62 units => .It will
have idle/ excess capacity of 20 units.
TC = Sh 2424.
3. Degeneracy
Degeneracy occurs when a row and column totals are simultaneously
satisfied by an entry or filling of a common cell.
ILLUSTRATION
Solve the following transportation problem for minimization use LCCM for
initial solution and MODI for optimal check.
TABLE 1
1 2 3 Suppl
y
A -3 40 40
B 35 +5 35
C 0 30 10 40
Demand 35 70 10 115
Degeneracy check.
R+c-1=3+3-1=5
Number of filled cells =4
Problem is degenerated – 1 degree
Solution not optimal since there are positive shadow prices
Entering variable = A1
Leaving variable = C3
TABLE 2
1 2 3 Suppl
y
A 10 30 +2 40
B 25 +2 10 35
C 03 40 +3 40
Demand 35 70 10 115
Degeneracy check.
R+c-1=3+3-1=5
Number of filled cells =5
Problem not degenerated – positive degree
Remarks
Solution is optimal since all shadow prices are positive.
Solution is unique since no zero shadow price
TC =10x3+30x4+25x4+10x2+40x4 =sh 380
MULTIPLE STAGE/SEQUENTIAL DECISION UNDER RISK
Some decisions problems span more than 1 stage e.g. contemplate acquiring additional
information say through market research consultants (so as to have better understanding or
insight into the kind of market demand expected) before making decision.

Stage 1 Stage 2
Acquire information - Make decision
Or not acquire
If a problem spans more than 1 stage, it is no longer convenient to use a decision table. We
use a decision trees
Decision Tree
Definition-A decision tree is a graphic representation of a decision process and indicates the
decision alternative, the various states of nature, their probabilities and condition pay offs.

- Decision nodes from which one of the several alternatives may

be chosen which is controllable.

- Circles are used to represent events or states of nature out of

which one state of nature will occur.

- Lines are used to denote a decision alternative or a probability

branch.
STEPS IN ANALYSING PROBLEMS USING DECISION TREE
vi. Define and understand the problem.
vii. Draw out the decision tree clearly depicting decision alternatives and events.
viii. Assign probabilities to the states of nature
ix. Estimate the payoffs for each possible combination of a decision alternative of a
state of nature.
x. Solve the problem by computing EMV’s at each state of nature node and
extending to the next decision node. Proceeds from the last event node to the first
(roll back).
Select the alternative which is indicated by the “best” EMV at the staff decision node.

Expected value of sample information (EV of SI)

EV of SI is the value of obtaining sample or additional information such as conducting a
market research or survey. The basic question is:
Is it worth the cost?
EV of SI = EV of best decision with Expected value of
Sample information - decision without
Assuming no cost to gather it information
Revision of probabilities
Bayes Theorem
P (B/A) = P (A/B) P (B)/p(A)
P (A) = P (A/B1) P (B1) + P (A/B2) P (B2) + …….. P (A/Bn) P (Bn)

Example:
A cooking oil manufacturing firm based in Eldoret is considering opening a new production
plant in Thika. The opening of a new plant will, however, depend on the demand for the
cooking oil in the Thika region. Information concerning the demand for the cooking oil is
available and is as shown below:
H - High demand and leads to a profit of shs.6,000,000 per year.
M - Moderate demand and leads to a profit of shs.1,500,000 per year.
L - Low demand and leads to a loss of shs.2,500,000 per year.

The chances of having high, moderate and low demand are assessed at 30%, 30% and 40%
respectively by the firm’s management. A market research group could be employed to
provide information on which market demand will be realized. Past experience with work in
the same market with this group shows its information cannot be relied on to be absolutely
accurate.

The market research group classifies its results as either there being good prospects (G) or
poor prospects (P). The table below gives the extent of reliability of this market research
group.
Market Survey Actual State of Nature
Result
H M L
G 0.7 0.6 0.2
P 0.3 0.4 0.8
The market research group would charge a fee of shs.60,000 if it was hired.
Required: By use of a decision tree, determine whether the market research is justified, i.e.
determine the expected value of imperfect information.
Solution:

Not open
0

1250 0.3 H:
6000
open 0.3 M:
1500 n
1250
B D 0.4 L:-
2500
No Not open

open 0
A E n
Good 2845 2845
Surve .45, H:
6000
G .38, M:
1500
.17, L:-
2500
Poor Not open
1337.15
open
C F n
0
0
-135 .17 H:
6000
H .23 M:
1500
.6 L: -
2500

Revision of probabilities (probability tree)

Prior information
Bayes theorem Posterior (Revised
information)
Additional information

H 0.3 x 0.7 = 0.21

M 0.1 x 0.6 = 0.18

Good
L 0.4 x 0.2 = 0.08
P(G)=0.47
H 0.3 x 0.3 = 0.09
Poor
M 0.3 x 0.4 = 0.12

L 0.4 x 0.8 = 0.32

P(P)=0.58

P (H/G) = 0.21 = 0.45

0.47
P (M/G) = 0.18 = 0.38
0.47
P (L/G) = 0.02 = 0.17
0.47 1
P (H/P) = 0.09 = 0.17
0.53
P (M/P) = 0.12 = 0.23
0.53
P (L/P) = 0.32 = 0.60
0.53 1

Revision by Bayes Theorem

Therefore, P (H/G) = P(G/H) P(H)
P(G)
Where, P (G) = P(G/H)PH + P(G/M) P(M) + P(G/L) P(L)
= 0.7205 + 0.6 X 0.3 + 0.2 x 0.4
= 0.47
P (P) = 1 – P(G)
= 1 – 0.47 = 0.53
P (H/G) = 0.7 x 0.3 = 0.45
0.47
P (M/P) = P(P/M) P(M) but P(P) = 0.53
P (P)
= 0.4 x 0.3 = 0.23
0.53
Node
A Survey

B Open

C Emv = 1337.15

D Emv = 0.3 x 600 + 0.3x 1,500 + 0.4 x (2500) = 1,250

E Open
F Not open

G Emv = 0.45 x 600 + 0.38 x 1500 + 0.17 x (2500) = 2,845

H Emv = 0.17 x 600 + 0.23 x 1500 + 0.6 x (2500) = -135

Recommendation: The firm should undertake the market research and if the results are good
prospects (G) open the plant otherwise if there are poor prospects (P) do not open the plant.

Expected value of sample information

Ev of SI = Best EMV with information - Best Emv

Assuming costless without information

= 1337.15 - 1,250 = 87.15, hence the survey is justified since Sh 60, 000 is less than
Sh 87, 150 (which is the maximum amount that can be committed towards the
research)

4 Competition
In this environment, the decision maker is not alone. There is at least one other participant
(There is at least one active opponent). For example: Body of knowledge (Game theory)

ENVIRONMENT OF COMPETITION (GAME THEORY)

Two-person, zero sum games
Game theory embodies studies and theories expounded through time by game theorists. In
the decision-making environment there is at least one active opponent. In the business
context the term “games” refers to conflict through time. It is to do with business situations
where usually the success of one person is at the expense of another. A way of solving
problems in competitive situations has been advanced by logicians through time for example
A Raiffa (German Mathematician), Oskar Morgenstern (US Economist), John von Neumann
(US Mathematician)
Conflict can occur for a number of competitions. However for our purposes, we shall study
only 2 person games.
Illustration
Player Y
Strategy Q Strategy P
Player X Strategy M X wins 2 points X wins 3 points
Strategy N Y wins 1 points Y wins 3 points
Problem – which strategy shall each of the players adopt?
Components of a game
4. Players
5. Strategies
6. Pay offs
Assumptions (Conditions)
7. Economic rationality - Each player is assumed to be economically rational i.e. each
desires to win. i.e. None of the players is charitable.
Each player prefers more of a good thing than less and vice versa.
8. Information: Both players have the same information set i.e. each player knows the
strategies of the opponent and the consequential pay offs.
9. Zero sum nature of the game. The gain of a given player exactly equals the loss to the
other player so that the game is zero sum.
X = m: +3
Y = P: -3
∑=0
10. No indifference – each player has to play.
11. Repeatedness – The game is played repeatedly over a long time.
12. Number of players – we assume they are finite i.e. 2 in this case.

Standard Notation (Zero Sum Games Only)

Convention
Gain to x (losses to y) are +ve
Gain to y (losses to x) are –ve
Standard form
Y
Y1 Y2
X X1 2 3
X2 -1 -3

Solution
x = X1 v = 2
y = Y1

PURE AND MIXED STRATEGIES

Whenever there is only 1 strategy for x and y which they both mutually and logically agree,
this is termed as pure strategy game, and the solution to the game is known as a saddle point.
Mathematically, a saddle point is one which is a maximum with respect to one variable and a
minimum with respect to the other.
Rule
If a game is pure strategy, the saddle point will be given by the element which is both
maximum in its column and minimum in its row (minimax).
Furthermore, if a game, is not pure strategy, then it is mixed strategy in which case each
player oscillates between his or her strategies through time.

(a) Player Y
Y1 Y2
Player X X1 2 3
X2 -1 -3
(b) Player Y
Y1 Y2 Y3
Player X X1 2 0 4
X2 1 -3 2
(c) Player B
b1 b2 b3 b4 b5
Player A a1 -2 0 0 5 3
a2 3 5 1 2 2
a3 -4 -3 0 -2 6
a4 5 -3 -1 -2 -6

(d) Player Y
Y1 Y2
Player X X1 2 6
X2 -1 -2
X3 3 1

SOLUTION TO MIXED STRATEGY GAMES (JOINT PROBABILITY APPROACH)

When there is no saddle point, players will result to mixed strategies i.e. each of the available
strategies will be played a certain percentage of total time.
Principle (Expectation theory) – Theory of rational expectation
Logically one wants to divide the time between his strategies so that he wins as much when
the other is playing either of his alternative.

GAME REDUCTION: DOMINANCE PRINCIPLE

In d above, one of the Xs must be eliminated to have 3 strategies.
Considering X1 and X3
If Y=Y1, X=X3 and if Y=Y2, X= X1, Hence non is dominant
Considering X1 and X2
If Y=Y1, X=X1 and if Y=Y2, X= X1, hence X1 dominates X2, such that X2 shall never be
played as long as X1 exists hence it is dropped. The reduced game becomes
(d) Player Y
Y1 Y2
Player X X1 2 6
X3 3 1