1 Chapter One: Introduction to Operations Research Operations Research (OR) started just before World

War II in Britain with the establishment of teams of scientists to study the strategic and tactical problems
involved in military operations. The objective was to find the most effective utilization of limited military
resources by the use of quantitative techniques. Following the war, numerous peacetime applications
emerged, leading to the use of OR and management science in many industries and occupations.
Operations Research (OR) is the study of mathematical models for complex organizational systems.
Optimization is a branch of OR which uses mathematical techniques such as linear and nonlinear
programming to derive values for system variables that will optimize performance. Management science
or operations research uses a logical approach to problem solving. This quantitative approach is widely
employed in business. Areas of application include forecasting, capital budgeting, capacity planning
scheduling inventory management, project management and production planning. Significance of
Operation Research ü It provides a tool for scientific analysis and provides solution for various business
problems. ü It enables proper deployment and optimum allocation of scarce resources. ü It helps in
minimizing waiting and servicing costs. ü It enables the management to decide when to buy and how
much to buy through the technique of inventory planning. ü It helps in evaluating situations involving
uncertainty. ü It enables experimentation with models, thus eliminating the cost of making errors while
experimenting with reality. ü It allows quick and inexpensive examination of large numbers of
alternatives. ü In general OR facilitates and improves the decision making process. Areas of Application ü
Inventory control ü Facility design (distribution decision) ü Product mix determination ü Portfolio analysis
ü Allocation of scarce resources 2 ü Investment decisions ü Project management. CHAPTER 2: LINEAR
PROGRAMING (LP) 2.1. Basic Concepts in LP Linear programming deals with the optimization
(maximization or minimization) of a function of variables known as objective function, subject to a set of
linear equation and /or inequalities known as constraints. Ø The objective function may be profit, cost,
production capacity, or any other measure of effectiveness which is to be obtained in the best possible
or optimal manner Ø The constraints may be imposed by different resources such as market demand,
production process and equipment, storage capacity, raw material availability, etc. Ø By linearity is
meant a mathematical expression in which the expressions among the variables are linear. Definition: LP
is a mathematical modelling technique useful for economic allocation of “scarce” or “limited” resources
(such as labor, material, machine, time, warehouse, space, capital, etc.) to several competing activities
(such as products, services, jobs, new equipment, projects etc.) on the basis of a given criterion of
optimality. All organizations, big or small, have at their disposal, men, machines, money and materials,
the supply of which may be limited. Supply of resources being limited, the management must find the
best allocation of resources in order to maximize the profit or minimize the loss or utilize the production
capacity to the maximum extent. Steps in formulation of LP model: 1. Identify activities (key decision
variables). 2. Identify the objective function as a linear function of its decision variables. 3. State all
resource limitations as linear equation or inequalities of its decision variables. 4. Add non-negative
constraints from the consideration that negative values of the decision variables do not have any valid
physical interpretation. 5. Use mathematical techniques to find all possible sets of values of the variables
(unknowns) satisfying all the function 6. Select the particular set of values of variables obtained in step
five that leads to the achievement of the objective function. v The result of the first four steps is called
linear programming. The set of solutions obtained in step five is known as the set of feasible solutions
and the solution finally selected in step six is called optimum (best) solution of the LP problem. v A
typical linear programming has two step ü The objective function ü The constraints § Technical
constraint, and § The non-negativity constraint 3 The objective function: is a mathematical
representation of the overall goal of the organization stated as a linear function of its decision variables
(Xj) to optimize the criterion of optimality. Ø It is also called the measure of performance such as profit,
cost, revenue, etc The general form of the objective function is expressed as: Optimize (Maximize or
Minimize) Z= Where: Z is the measure of performance variable (profit/cost), which is the function of X1,
X2, …,Xn. (Quantities of activities) Cj (C1, C2… Cn) (parameters or coefficients) represent the contribution
of a unit of the respective variables X1, X2, …,Xn to the measure of performance Z (the objective
function). The constraints: the constraints must be expressed linear equalities or inequalities interms of
decision variables. The general form of the constraints functions are expressed as: (, ≤, =, ≥) bi
a11X1+a12X2+…+a1nXn (, ≤, =, ≥) b1 a21X1+a22X2+…+a2nXn (, ≤, =, ≥) b2 . . . . . . . . . Am1Xm+am2X2+…
+amnXn (, ≤, =, ≥) bn v aij’s are called technical coefficients and measure the per unit consumption of
the resources for executing one unit of unknown variable (activities) Xj. Ø aij‘s can be positive, negative
or zero in the given constraints. v The bi represents the total availability of the ith resource. Ø It is
assumed that bi ≥ 0 for all i. However, if any bi < 0, then both sides of the constraint i can be multiplied
by 1 to make bi > 0 and reverse the inequality of the constraint. Requirements for a linear programming
problem: Generally speaking, LP can be used for optimization problems if the following conditions are
satisfied. 1. There must be a well defined objective function which is to be either maximized or
minimized and which can be expressed as a linear function of decision variables 2. There should be
constraints on the amount or extent of attainment of the objective and these constraints must be
capable of being expressed as linear equations or inequalities interms of variables. 3. There must be
alternative courses of action. Fore e.g., a given product may be processed by two different machines and
problem may be as to how much of the product to allocate which machine. 4. Decision variables should
be interrelated and non-negative. 5. The resource should be in limited supply. 2.2. Assumptions of Linear
Programming åCj X j åaij x j 4 A linear programming model is based on the following assumptions: 1.
Proportionality assumption: A basic assumption of LP is that proportionality exists in the objective
function and the constraints. It states that the contribution of each activity to the value of the objective
function Z is proportional to the level of the activity Xj, as represented by the CjXj term in the objective
function. Similarly, the resource consumption of each activity in each functional constraint is
proportional to the level of the activity Xj, as represented by the aijXj term in the constraint. What
happens when the proportionality assumption does not hold? In most cases we use nonlinear
programming. 2. Additivity assumption: States that every function in a linear programming model
(whether the objective function or the left-hand side of the a functional constraint)is the sum of the
individual contributions of the respective activities. What happens when the additivity assumption does
not hold? In most cases we use nonlinear programming. 3. Divisibility assumption: States that decision
variables in linear programming model are allowed to have any values, including non-integer values,
which satisfy the functional and non-negativity constraints. Thus, since each decision variable represents
the level of some activity, it is being assumed that the activities can be run at fractional levels. In certain
situations, the divisibility assumption does not hold because some of or all the decision variables must
be restricted to integer values. For this restrictions integer programming model will be used. 4. Certainity
assumption: This assumption states that the various parameters (namely, the objective function
coefficients, the coefficients in the functional constraints aij and resource values in the constraints bi are
certainly and precisely known and that their values do not change with time. However, in real
applications, the certainity assumption is seldom satisfied precisely. For this reason it is usually
important to conduct sensitivity analysis after a solution is found that is optimal under the assumed
parameter values. 5. Finiteness: An LP model assumes that a finite (limited) number of choices
(alternatives) are available to the decision-maker and that the decision variables are interrelated and
non-negative. The non-negativity condition shows that LP deals with real-life situations as it is not
possible to produce/use negative quantities. 6. Optimality: In LP, the optimal solution always occurs at
the corner point of the set of feasible solutions. Important Definitions Ø Solution: The set of values of
decision variables Xi (i=1, 2, ….,n)which satisfy the constraints of an LP problem is said to constitute
solution to that LP problem Ø Feasible solutions: The set of values of decision variables Xi (i=1, 2… n)
which satisfy all the constraints and non-negativity conditions of an LP simultaneously. Ø Infeasible
solution: The set of values of decision variables which do not satisfy all the constraints and non-
negativity conditions of an LP simultaneously. 5 Ø Optimum solution: A feasible solution which optimizes
(maximizes or minimizes) the objective function value of the given LP problem is called an optimum basic
feasible solution. Ø Unbounded solution: A solution which can increase or decrease the value of the
objective function of LP problem indefinitely is called unbounded solution. 2.3. Methods of Solving
Linear Programming Problems A linear programming problem can be solved by graphic method or by
applying algebraic method, called the simplex method. 1. Graphic method: it can be used when only two
variables are involved. This method consists of the following steps: i. Represent the given problem in
mathematical form. ii. Plot each of the constraint on the graph. iii. Identify the feasible region (or
solution space) that satisfies all the constraints simultaneously. Any point on or within the shaded region
represents a feasible solution to the given problem. iv. Locate the solution points (identify the corner
points from the solution space). v. Determine the optimal solution. A solution that optimizes the
objective function. vi. Interpret the results a) Maximization Problem: This is the case of Maximize Z with
inequalities of constraints in < form. Consider two models of color TV sets; Model A and B, are produced
by a company to maximize profit. The profit realized is $300 from A and $250 from set B. The limitations
are a. Availability of only 40 hrs of labor each day in the production department, b. A daily availability of
only 45 hrs on machine time, and c. Ability to sale 12 set of model A. How many sets of each model will
be produced each day so that the total profit will be as large as possible? Constraints Resources used per
unit Maximum Available Model A Hours (x1) Model B (x2) Labor Hours 2 1 40 Machine Hours 1 3 45
Marketing Hours 1 0 12 Profit $300 $250 6 Solution: 1. Formulation of mathematical model of LPP Max
Z=300X1 +250X2 St: 2X1 +X2< 40 X1 +3X2< 45 X1 < 12 X1, X2 > 0 2. Convert constraints inequalities into
equalities 2X1 + X2 = 40 X1 + 3X2 = 45 X1 = 12 3. Draw the graph by finding out the x– and y–intercepts
2X1 +X2 = 40 ==> (0, 40) and (20, 0) X1 +3X2 = 45 ==> (0, 15) and (45, 0) X1 = 12 ==> (12, 0) X1 , X2 = 0 4.
Identify the feasible area of the solution which satisfies all constrains. The shaded region in the above
graph satisfies all the constraints and it is called Feasible Region. 5. Identify the corner points in the
feasible region. Referring to the above graph, the corner points are in this case are: A (0, 0), B (0, 15), C
(12, 11) and D (12, 0) 6. Identify the optimal point. Corners Coordinates Max Z = 300 X1 +250X2 A (0, 0)
$0 B (0, 15) $3750 C (12, 11) $ 6350 (Optimal) D (12, 0) $3600 LP Model 2 X1 + X2 = 40 C B 15 40 12 20
45 X1 X2 A D X1 + X2 = 45 (12, 11) X1=12 X1=0 X2=0 Feasible Region 7 7. Interpret the result. Accordingly,
the highlighted result in the table above implies that 12 units of Model A and 11 units of Model B TV sets
should be produced so that the total profit will be $6350. b) Minimization Problem: In this case, we deal
with Minimize Z with inequalities of constraints in > form. Suppose that a machine shop has two
different types of machines; Machine 1 and Machine 2, which can be used to make a single product.
These machines vary in the amount of product produced per hr., in the amount of labor used and in the
cost of operation. Assume that at least a certain amount of product must be produced and that we
would like to utilize at least the regular labor force. How much should we utilize on each machine in
order to utilize total costs and still meets the requirement? Items Resource Used Minimum Required
Hours Machine 1 (X1) Machine 2 (X2) Product produced/hr 20 15 100 Labor/hr 2 3 15 Operation Cost
$25 $30 Solution: 1. The LP Model: , 0 2 3 15 20 15 100 : . 25 30 1 2 1 2 1 2 1 2 ³ + ³ + ³ = + X X X X X
X St Min Z X X Dear student, can you graph the above constraints? See step 2 below. 2. The Graph of
Constraint Equations: 20X1 +15X2=100 ==> (0, 20/3) and (5, 0) 2X1 + 3X2=15 ==> (0, 5) and (7.5, 0) X1 ,
X2 = 0 LP Model B (2.5, 3.33) A (0, 20/3) C (7.5, 0) X1 X2 5 X2 =0 X1 =0 Feasible Region 8 3. The Corners
and Feasible Solution: Corners Coordinates Min Z= 25 X1 + 30X2 A (0, 20/3) 200 B (2.5, 3.33) 162.5
(Optimal) C (7.5, 0) 187.5 Since our objective is to minimize cost, the minimum amount (162.5) will be
selected. X1 = 2.5 X2 = 3.33 and Min Z= 162.5 Note: - In maximization problems, our point of interest is
looking the furthest point from the origin (Maximum value of Z). - In minimization problems, our point of
interest is looking the point nearest to the origin (Minimum value of Z). Example3. A firm manufactures
two products A and B on which the profits earned per unit are Birr 3 and Birr 4 respectively. Each
product is processed on two machines M1 and M2. Product A requires one minute of processing time on
M1 and two minutes on M2, while B requires one minute on M1 and one minute on M2. Machine M1 is
available for not more than 7hrs. 30 minutes, while machine M2 is available for 10hrs during any working
day. Find the number of units of products A and B to be manufactured to get maximum profit. Solution
Formulation of LPP model Let x1 and x2 denote the number of units of products A and B to be produced
per day. Objective is to maximize the profit. i.e. Maximize Z = 3x1 + 4x2 Constraints are on the time
available for machines M1 and M2 i.e., for machine M1, 1x1 + 1x2 ≤ 450 for machine M2, 2x1 + 1x2 ≤
600 Ans: x1=0, x2=450 and Zmax =Birr 1800 Where x1, x2 ≥ 0. Example 4: The standard weight of a
special purpose brick is 5kg and it contains two basic ingredients B1 and B2. B1 costs Birr 5/kg and B2
costs Birr 8/kg. Strength considerations dictate that the brick contains not more than 4kg of B1 and a
minimum of 2kg of B2. Since the demand for the product is likely to be related to the price of the brick,
find graphically the minimum cost of the brick satisfying the above conditions. Solution Formulation of
LPP model Let the quantities in kg of ingredients B1 and B2 to be used to make the bricks be x1 and x2
resp. Objective is to minimize the cost of the brick. i.e., Minimize Z = 5x1 + 8x2 Ans: x1=3kg, x2= 2kg,
Zmin=Birr 31 9 Constraints are On the quantity of the ingredient B1: x1 ≤ 4, On the quantity of the
ingredient B2: x2 ≥ 2, On the weight of the brick : x1 + x2 = 5 Where x1, x2 ≥ 0. Some Special Cases of
Linear Programming There are certain special cases in linear programming problem. Some of these cases
are resulted from violations of the basic assumptions of LP. These include: 1. Multiple optimal solutions:
This is the situation when more than one optimal solution arises. This will happen whenever the
objective function equation represents a line parallel to some edge of the bounded solution space.
Example: Solve the following problems graphically Max Z = 110x1+110x2, Subject to: x1 + x2 ≤ 9, x1 ≥ 2,
20x1 + 50x2 ≤ 360, x2 ≥ 3 x1, x2 ≥ 0. 2. Unbounded solution: it exists when an LP problem has no limit on
the constraints i.e., the feasible region is not bounded in any respect. Theoretically, the value of the
decision variable increases infinitely without violating the feasibility and value of the objective function
can increase to infinity. Mostly this situation occurs when the assumption of finiteness is violating.
Example: Solve the following problems graphically Max Z = 30x1+50x2, Subject to: 3x1 +x2 ≥ 9, x1 + 2x2
≥12, x1 + 2x2 ≥9, x1, x2 ≥ 0. 3. Infeasible solution: infeasibility is a condition that exists when there is no
solution to an LP problem that satisfies all the constraints and non-negativity restrictions. It means that
the constraints in the problem are conflicting and inconsistent. Infeasibility depends solely on the
constraints and has nothing to do with the objective function Example: Solve the following problems
graphically Max Z = 3x1+2x2, Subject to: -2x1 + 3x2 ≤ 9, 3x1 - 2x2 ≤ -20, x1, x2 ≥ 0. 10 Binding and Non-
Binding Constraints (Resources) Once the optimal solution to an LPP is obtained, we may classify the
constraints as being binding and or non-binding. A constraint is termed as binding if the left hand side
and the right hand side of the constraint function s are equal when the optimal values of the decision
variables are substituted in to the constraint. On the other hand, if the substitutions of the value of the
decision variables do not lead to equality between the left and the right hand side of the constraint, it
said to be non-binding. Redundant constraint(s): If the constraint, when plotted does not form part of
the boundary marking the feasible region of the problem, it is said to be redundant. The inclusion or the
exclusion of a redundant constraint obviously does not affect the optimal solution to the problem.
Exercises: Solve the following LLPs using graphic method 1. a) Min Z = 2x1+x2, b) Max Z = 2x1+3x2 Ans. a)
x1=0, x2=2, Zmin=2, b) Unbounded Subject to: x1 - 3x2 ≤ 6, 2x1 + 4x2 ≥ 8, x1 - 3x2 ≥ -6, x1, x2 ≥ 0. 2. Max
Z = 4x1+5x2, Ans. Unbounded Solution Subject to: x1 + x2 ≥ 1, -2x1 + x2 ≤ 1, 4x1 - x2 ≥ 1 x1, x2 ≥ 0. 2. The
Simplex Method When a number of variables in a linear programming are more than two, graphic
method cannot be used because of the difficulty precisely representing the variables using more than a
two dimensional plane. That means it is impossible to represent these variables in the graph and
evaluate the corner points. In such cases, there is a comprehensive method of solving a linear
programming problem which is called the simplex method (simplex algorithm). Ø Algorithm is a process
where a systematic procedure is repeated (iterated) over and over again until the desired result is
obtained. Simplex method (algorithm) is an iterative procedure that consists of moving from one basic
feasible to another in such a way that the values of the objective function doesn’t decrease (in case of
maximization problem) and doesn’t increase (in case of minimization problem). Ø The process continues
until an optimal solution is reached if it exists, otherwise, the problem may be unbounded or not feasible
and the simplex method can’t find the solution. 11 Conditions for applications of simplex method There
are some conditions that must be fulfilled for the application of simplex method. These are: 1. The right
hand side of each of the constraints bi should be non-negative. Ø If the linear programming problem has
a negative constraint, we should convert it to positive by multiplying both sides by -1. Forexample, if one
of the constraints is given by 2x1 - 4x2 ≥ -8, we cannot apply simplex method as it is. So, we should
convert it to positive by multiply both sides by -1. i.e., -2x1 +4x2 ≤ 8 2. Each of the decision variables of
the problem should be non-negative. If one of the choice variables is not feasible, simplex method
cannot be applied. Therefore, feasibility is a necessary condition for application of simplex method. 3.
The inequality constraints of resources or any other activities must be converted in to equations. Since
simplex method cannot be applied in the case of inequalities, it is a mandatory that these inequalities
should be converted in to equations. There are some variables that help us to convert these inequalities
in to equations. These variables are: Slack and surplus variables. Slack variables: are variables that can
change the less than type inequality in to equations. Ø Slack variables represent unused amount of a
given resource by the activities or idle resources. For example, if one of the constraint is given as: § x1 ≤
4 we can convert this in to equations by introducing a slack variable. § x1 +S1 =4. The values of S1 will
range from zero to four. i.e., if x1=0, S1=4 meaning that all the available resources is not used. If x1=4,
S1=0 meaning that all the available resource is fully utilized and there is no idle resource which is left
over. Surplus variables: if the constraint inequality is of greater than type, then we can convert it into
equation by subtracting some variable called surplus variable. Surplus variables represent that the
requirement of the resource is more than the availability. Ø Surplus variables are the negative of the
slack variables. For example, if one of the constraint is given as: x2 ≥ 8, this inequality can be converted
to equation by introducing surplus variable as x2 –S1= 8. Note: Slack and surplus variables enter in to the
objective function with zero coefficients. Procedures of simplex method Step 1: Express the problem in
standard form. The given problem is said to be expressed in standard form if the decision variables are
nonnegative, R.H.S of the constraints are non-negative and the constraints are expressed as equations.
Non-negative slack variables are added to the L.H.S of the constraints to convert them in to equations.
12 Example: Max Z = 3x1+4x2, Subject to: x1 + x2 ≤ 450, 2x1 +x2 ≤ 600, Where x1, x2 ≥ 0. Standard form
of the above LP model is: Max Z = 3x1+4x2 +0S1 +0S2, Subject to: x1 + x2 + S1=450, 2x1 + x2 +S2= 600,
Where x1, x2, S1, S2 ≥ 0 Step 2: Set up the initial solution Ø In order to set up the initial solution, first we
need to determine the basic and nonbasic variables. Ø Slack variables at initial table become basic
variables and decision variables are nonbasic variables. If we have n unknowns and m constraints, then
m variables should be basic and the rest (n-m) variables should be non-basic such that their value is zero.
Ø Basic variables are those variables whose values are obtained from the basic solution where as non-
basic variables are those whose values are assumed as zero in the basic solution. Example: The initial
solution of the above standard form can be expressed in the following simplex table Contribution/unit Cj
3 4 0 0 Body matrix Identity matrix CB BV x1 x2 s1 s2 b 0 s1 1 1 1 0 450 0 s2 2 1 0 1 600 Interpretation: 1.
The first row indicates the coefficients Cj of the variables in the objective function and they are
unchanged in the subsequent tables. 2. The first column CB represents the coefficients of the current
basic variables in the obj. fun. The second column is the basis column and it represents the basic
variables of the current solution. 3. The body matrix (coefficient matrix) represents the coefficients of
the constraints. These coefficients represent the amount of resource required to make a unit of decision
variable. 4. The identity matrix represents the coefficients of slack variables in the constraints. 5. The b-
column/solution values xB column indicates the quantities of the variable resources or R.H.S values of
the constraints or values of the basic variables, S1 and S2 in the initial basic solution. Step 3: Perform
optimality test The test for optimality can be based on interms of the sign of the members of the index
row. 13 Contribution/unit Cj 3 4 0 0 Body matrix Identity matrix CB BV x1 x2 s1 s2 b 0 S1 1 (1) 1 0
450Þkey row 0 S2 2 1 0 1 600 Zj 0 0 0 0 0 ∆j = Zj- Cj -3 -4 0 0 ↑K Where: Zj=∑CBiaij and Z=∑CBixBi v
Values in the Zj represent the contribution lost per unit of the variables. i.e., the amounts by which
contribution would be reduced if one of the corresponding variables x1, x2 … was added. v ∆j is also
called the index row. This row determines whether or not the current solution is optimal. Coefficients in
this row represent the net profit (or net contribution or net marginal improvement) in the values of the
objective function Z for each unit of the respective column variable introduced into the solution. For
example, as x1 increases by one unit Z will increase by 3 units. v A positive coefficient in the Zj-Cj row
indicates the amount by which the objective function will be decreased if a unit of the corresponding
variable is introduced in to the solution where as a negative coefficient indicates the amount by which
the profit will be increased if a unit of the corresponding variable is introduced in to the solution. These
coefficients or elements are known as shadow prices or accounting values or imputed values of the
resources. v The solution is optimal if all the elements of the index row are +ve and zero. If at least one
of the elements of the index row is -ve, the given solution is not optimal and goes to the next step. The
next iteration will give as the next adjusted basic feasible solution. Step 4: Iterate towards the optimal
solution In each iteration, the simplex method moves the current basic feasible solution to an improved
basic feasible solution. This is done by replacing one current basic variable by a new nonbasic variable as
follows. v Pivot column: The column which has the maximum -ve value of Zj-Cj, is the one which should
enter the solution (entering variable). v Pivot row: The element lying at the intersection of key column
and key row is called key /pivot element and is enclosed in ( ). This pivot element corresponds to the
leaving variables. Leaving variable= (xbi /aij, aij) 0. Ø M denotes some huge positive number (very huge
penalty), for that firm manipulates the artificial variables. Steps of the big M-method algorithm Step 1:
Express the LP problem in the standard form by introducing slack variables. Ø These variables are added
to the L.H S of the constraints of (≤) and subtracted from the constraints of (≥) type. Step 2: Add non-
negative artificial variable (A) corresponding to constraints having “≥” and “=” equations. Step 3: Set up
the initial solution 16 Ø In order to set up the initial solution, first we need to determine the basic and
nonbasic variables. In the initial solution, original variables have zero value, so they are non-basic
variables. Step 4: Solve the modified LPP by the simplex method. While making iterations, using the
simplex method, one of the following three cases may arise: a. If no artificial variable remains in the
basis and the optimality condition is satisfied, then the solution is an optimal feasible solution. b. If at
least one artificial variable appears in the basis at zero level and optimality condition is satisfied, then
the solution is optimal feasible solution. But it is a degenerate solution. The constraints are consistent
though redundancy may exist in them. Redundancy means that the problem has more than the required
number of constraints. c. If at least one artificial variable appears in the basis at a non-zero level (with
+ve value in b-column) and the optimality condition is satisfied, then the original problem has no feasible
solution. Therefore, the original problem doesn’t have feasible solution because it contains artificial
variable (a very large penalty M). Remarks: 1. Slack variables are added to the constraints of (≤) type and
subtracted from the constraints of (≥) type. 2. Artificial variables are added to the constraints of (≥) and
(=) type. Equality constraints require neither slack nor surplus variables. 3. Variables, other than the
artificial variables, once driven out in iteration, may re-inter in a subsequent iteration. Example: Max Z =
3x1- x2 Subject to: 2x1 + x2 ≤ 2, x1 + 3x2 ≥3, x2 ≤ 4, x1, x2 ≥ 0. Step 1: Set up the problem in standard
form Max Z = 3x1- x2 +0s1+0s2+0s3-MA1, Subject to: 2x1 + x2 + s1 = 2, x1 + 3x2 - s2 +A1=3, x2 + s3 = 4,
x1, x2, s1, s2, s3, A1≥ 0. Step 2: Find initial basic feasible solution Substituting x1=x2 =s2=0, then the
initial b.f.s obtained is: s1=2, A1=3, s3=4, Z=-3M 17 Step 3: perform optimality test Since the Zj- Cj is -ve
under some variable columns the solution is not optimal and can be improved Step 4: Iterate in to the
optimal solution Successive iteration yields the following tables Table 1. Cj 3 -1 0 0 0 -M CB BV x1 x2 s1 s2
S3 A1 b r 0 s1 2 1 1 0 0 0 2 2 -M A1 1 (3) 0 -1 0 1 3 1 0 S3 0 1 0 0 1 0 4 4 Zj=∑ CBaij -M -3M 0 M 0 -M -3M
Þi.s ∆j = Zj- Cj -M-3 -3M+1 0 M 0 0 ↑K Table 2. Cj 3 -1 0 0 0 CB BV x1 x2 s1 s2 S3 b r 0 s1 (5/3) 0 1 1/3 0 1
3/5 -1 x2 1/3 1 0 -1/3 0 1 3 0 S3 -1/3 0 0 1/3 1 3 -9 Zj=∑ CBaij -1/3 -1 0 1/3 0 -1 Þ2 nd b.f.s ∆j = Zj- Cj -
10/3 0 0 1/3 0 ↑K Table 3. Cj 3 -1 0 0 0 CB BV x1 x2 s1 s2 S3 b 3 x1 1 0 3/5 1/5 0 3/5 -1 x2 0 1 -1/5 -2/5 0
4/5 0 S3 0 0 1/5 2/5 1 16/5 Zj=∑ CBaij 3 -1 2 1 0 1 ∆j = Zj- Cj 0 0 2 1 0 Therefore, optimal solution is given
by: X1=3/5, x2=4/5, Zmax=1 Exercise: solve the f.f. LPP Max Z = x1+2x2+3x3- x4 Subject to:
x1+2x2+3x3=15 2x1+x2+5x3=20 x1+2x2+x3+ x4 =10 x1, x2, x3, x4 ≥0 Hint: the standard form is: Max Z =
x1+2x2+3x3- x4-MA1-MA2-MA3, Subject to: x1+2x2+3x3 +0x4+A1+0A2+0A3=15 18
2x1+x2+5x3+0x4+0A1+A2+0A3=20 x1+2x2+x3+ x4 +0A1+0A2+A3=10 x1, x2, x3, x4 ,A1, A2, A3 ≥ 0 2.5.
SPECIAL CASES IN THE SIMPLEX METHOD APPLICATION 1. Tie Breaking in Simplex Method While
operating the simplex iteration, tie may occur and we may face indifference in choosing the entry or the
leaving variable. When tie may occur, the following are important to do: Tie in the choice of entering
variables: the non-basic variable that enters the basis is the one that gives the largest per unit
improvement in the objective function. Ø Variable having maximum –ve value in a maximization problem
and the maximum +ve value in the minimization problem in Zj- Cj row is the entering variable. A tie in
the entering variable exists when more than one variable has same largest (or smallest) value. To break
the tie any one of them is selected arbitrarily as the entering variable. Tie in the choice of leaving
variables: This is the case when the ratio is the same. Ø This tie can be resolved by choosing one of the
variables arbitrarily. 2. No leaving basic variable (unbounded objective function) Ø This is the case when
all elements of the pivot column are –ve or zero that no variable qualifies to be a leaving basic variable.
Ø In this case no finite solution can be determined. Because one or more of the variables can be
increased indefinitely without violating the feasibility. Ø The interpretation is that the objective function
is not constrained or the value of the objective function Z can increase indefinitely or the model is poorly
constructed. 3. Multiple optimal solutions Ø This is the case when the LPP have more than one optimal
solution. Ø In the simplex table if the Zj- Cj value is zero for a non-basic variable, it indicates that the
existence of more than one optimal solution. 4. Infeasible solution Ø If all the constraints are not
satisfied simultaneously, the model has no feasible solution. Ø In the case of big M method if at least one
of the artificial variables has positive value and the solution is optimal, then this is the indication of no
feasible solution. 2.6. MINIMIZATION CASE OF SIMPLEX METHOD For most part of finding solution for
minimization problem using simplex method are handled in the same fashion as maximization problem.
The three key exceptions are: Ø The coefficients of artificial variables (M) have positive sign in the
objective function. 19 Ø The selection of pivot column (entering variables) is based on the largest
positive number (value) in the index (∆j) row. Ø The solution is optimal when all values in the index (∆j)
row are non positive. The other alternative method of solving minimization problem is by converting it to
maximization. i.e., Min Z=Max (-Z) Example Min Z = 12x1+20x2 Subject to: 6x1 + 8x2 ≥100, 7x1 + 12x2
≥120, x1, x2 ≥ 0. Standard form: Min Z = 12x1+20x2 +0s1+0s2+MA1+MA2 Subject to: 6x1 + 8x2 -
s1+A1=100, 7x1 + 12x2 –s2+A2=120, x1, x2, s1, s2, A1, A2 ≥ 0. Cj 12 20 0 0 M M CB BV x1 x2 s1 s2 A1 A2
b r M A1 6 8 -1 0 1 0 100 25/2 M A2 7 (12) 0 -1 0 1 120 10 Zj=∑ CBaij 13M 20M -M -M M M 220M ↑I.S ∆j
= Zj- Cj 13M-12 20M-20 -M -M 0 0 ↑K Cj 12 20 0 0 M M CB BV x1 x2 s1 s2 A1 A2 b r M A1 4/3 0 -1 2/3 1
0 20 15 20 x2 7/12 1 0 -1/12 0 1 10 120/7 Zj=∑ CBaij -35/3+4/3M 20 -M -5/3+2/3M M M 200+20M ∆j =
Zj- Cj 4/3M-1/3 0 -M 2/3M-5/3 0 0 ↑K Cj 12 20 0 0 CB BV x1 x2 s1 s2 b 12 x1 1 0 -3/4 1/2 15 20 x2 0 1
7/16 -3/4 5/4 Zj=∑ CBaij 12 20 -1/4 -9 205 ∆j = Zj- Cj 0 0 -1/4 -9 CHAPTER 3: DUALITY THEORY AND
SENSITIVITY ANALYSIS IN LINEAR PROGRAMMING 3.1. Duality in Linear Programming 20 In the context of
LPP, duality implies that each linear programming problem can be analysed using two different ways
which have equivalent solutions. The original problem (primal) can be converted into dual by transposing
the rows and columns of the algebraic statement of the primal problem. The various useful aspects of
duality: v If the primal contains large number of rows (constraints) and a smaller number of columns
(variables), converting into dual reduces computational procedures. v Gives additional information as to
how the optimal solution changes as a result of changes in coefficients. v Calculation of the dual checks
the accuracy of the primal. v Duality is used to solve LPP in which the initial solution is infeasible. The
original or primal problem The dual problem Max Z= Min Z= Subject to Subject to Rules of
transformation of the primal to the dual The following rules are important to note when we develop a
dual problem: 1. If the primal contains n variables and m constraints, the dual will contain m variables
and n constraints. 2. The maximization problem in the primal becomes the minimization problem in the
dual and vice versa. 3. The maximization problem has (≤) constraints while the minimization problem has
(≥) constraints. 4. Constraints of (≤) type in the primal become (≥) type in the dual and vice versa. 5. The
coefficient matrix of the constraints of the dual is the transpose of the primal. 6. The constants c1, c2…
cn in the objective function of the primal appear in the constraints of the dual. 7. The constants b1, b2…
bn in the constraints of the primal appear in the objective function of the dual. Example: Primal Dual
Max Z = 2x1+3x2 Min Z’ = 18y1+19y2 Subject to: Subject to: 4x1 + 3x2 ≤ 18, 4y1 + 5y2 ≥ 2, 5x1 +2x2≤ 19,
3y1 + 2y2 ≥ 3, x1, x2 ≥ 0. y1, y2 ≥ 0. Economic Interpretation of Dual Problem å= n j Cj X j 1 å= n j j j b y
1 0 1 ³ å £ = j i n j i j j X a X b 0 1 ³ å £ = j i n j i j j X a X b 0 1 ³ å ³ = i j n j ji i y a y c 21 a. The
objective function of the dual problem is given by the equation: Z’ = b1y1 +b2y2 +b3y3 - - -+ bmym Ø
Each biyi is the current contribution to the objective function by having bi units of resource i available for
primal problem. Thus, yi interpreted as the contribution to the objective function per unit of resource i
when the current set of basic variables is used to obtain the primal solution. Ø In other words, yi’s are
the shadow prices. b. The constraint part which can be specified as: ∑ajiyi ≥ Cj. Ø Since each unit of
activity j in the primal problem consumes aij unit of resource i, then ∑ajiyi is interpreted as current
contribution to the objective function of the mix of resources that would be consumed if one unit of
activity j were produced. Ø Cj is interpreted as: per unit contribution to the objective function from
activity j. v Therefore, ∑ajiyi ≥ Cj can be interpreted as the current contribution to the objective function
of resources must be at least as much as the unit contribution to the objective function from activity j,
otherwise the use of resources would not be the best possible use. Yi ≥ 0, meaning that the current
contribution to the objective function of resource i must be non-negative otherwise it is better not to
use the resource at all. If we are using the resource i while its contribution to the objective function is
negative, we are devastating the resource for nothing. Solving a Dual Linear Programming The methods
of solving the dual linear programming are similar with that of the original linear programming
problems. We can use either graphic method or simplex method. v From the optimal simplex table of
the dual problem, it is possible to read the optimal solution of the primal problem. That is, the shadow
prices of the dual problem indicate the optimal values of original variables. Example: Primal Dual Max Z =
2x1+3x2 Min Z’ = 18y1+19y2 Max (-Z’) = -18y1-19y2 Subject to: Subject to: Subject to: 4x1 + 3x2 ≤ 18,
4y1 + 5y2 ≥ 2, OR 4y1 + 5y2 ≥ 2, 5x1 +2x2≤ 19, 3y1 + 2y2 ≥ 18, 3y1 + 2y2 ≥ 18, x1, x2 ≥ 0. y1, y2 ≥ 0. y1, y2
≥ 0. Standardize the problem Max Z = 2x1+3x2 +0s1+0s2 Max (-Z’) = -18y1-19y2 +0s1+0s2 –MA1-MA2
Subject to: Subject to: 4x1 + 3x2 +s1= 18, 4y1 + 5y2 -s1 +A1 = 2, 5x1 +2x2 +s2= 19, 3y1 + 2y2 - s2 +A2
=18, x1, x2, s1, s2 ≥ 0. y1, y2, s1, s2, A1, A2 ≥ 0. Solution for the primal Solution for the dual x1 =0, x2 =6
y1 =1, y2 =0 s1 =0, s2 =7 s1 =2, s2 =0 22 Index row s1 =1, s2 =0 y1 =0, y2 =7 x1 =2, x2 =0 s1 =0 , s2 =6 3.2.
Sensitivity Analysis One of the assumptions of a LPP is the assumptions of certainity. This assumption
implies that the coefficients of a LPP are completely known (determined) and do not change during the
period being studied. Ø Cj- per unit (profit or cost) contribution of each decision variable Ø bi -
availability of resources Ø aij – technical coefficients (per unit resource consumptions or production of
each decision variables) are constant and known with certainity. However, in reality, these coefficients
are subject to change with time or error. If such changes will be occurred, there should be a means to
check for how long the present optimal solution continues as optimal. The method of evaluating the
degree to which the present optimal solution is continued as optimal is called sensitivity analysis.
Sensitivity analysis is concerned with the study of ‘sensitivity’ of the optimal solution of LP problem with
changes in parameters. In this case, we are going to determine the range (both lower and upper) over
which the linear programming model parameters can change with out affecting the current optimal
solution. Changes in Cj of variables One of the important parameters of linear programming problem is
the coefficient of objective function. The test of the sensitivity of the coefficient of objective function
involves finding the range of values within which each Cj can lie without changing the current optimal
solution. a. Changes in coefficient Cj of non-basic variable xj Among the variables included in the linear
programming problem some are non-basic variables. If Cj is the coefficient of non-basic variable xj: 1. it
doesn’t affect any of Cj values of basic variables. 2. it doesn’t affect any of Zj values. 3. it affects (Zj- Cj)
values. In addition, if optimality is to be maintained, for maximization LPP, coefficients in the index row
should be non-negative (Zj- Cj) ≥ 0 for all j. Example: Max Z = 2x1+3x2 Subject to: 4x1 + 3x2 ≤ 18, 5x1
+2x2≤ 19, x1, x2 ≥ 0. 23 Cj 2 3 0 0 CB BV x1 x2 s1 s2 b r 0 s1 4 (3) 1 0 18 0 s2 5 2 0 1 19 Zj=∑ CBaij 0 0 0 0 0
∆j = Zj- Cj -2 -3 0 0 Cj 2 3 0 0 CB BV x1 x2 s1 s2 b r 3 x2 4/3 1 1/3 0 6 0 s2 7/3 0 -2/3 1 7 Zj=∑ CBaij 4 3 1 0
18 ∆j = Zj- Cj 2 0 1 0 4. In the final table, x1 and s1 are non-basic variable whereas x2 and s2 are basic
variables. 5. C1=2 is the coefficient of non-basic variable x1. Let c1 is subject to change by ∆c1
C1’=C1+∆C1 To maintain the optimality condition: ∆j (Zj- C'j) ≥0 (Zj - C'j) ≥0 Zj - (Cj+∆C1) ≥0 Z1 - C1 ≥ ∆C1
4-2 ≥ ∆C1 2 ≥ ∆C1 ∆c1 ≥ (-∞, 2] Therefore, the range over which the parameter (C1) can change without
affecting the current optimal solution (0, 6) is (-∞, 4]. Simply for non-basic variable xk, the coefficient (Cj)
can change without affecting the optimal solution if Zj- Cj ≥ ∆Ck. b. Change in Coefficient Cj of Basic
Variable Xj Change in the coefficients of basic variable can affect Zj, ∆j and the value of the objective
function. v For the above table (x2 is basic variable). And suppose C2 is changed by ∆C2. i.e., C2’=3+ ∆C2
Cj 2 3 0 0 CB BV x1 x2 s1 s2 b r 3+∆c2 x2 4/3 1 1/3 0 6 0 s2 7/3 0 -2/3 1 7 Zj=∑ CBaij 4+4/3∆c2 3+∆c2
1+1/3∆c2 0 18+6∆c2 ∆j = Zj- Cj 2+4/3∆c2 0 1+1/3∆c2 0 The current solution will be optimal if ∆j (Zj - c'j)
≥0. i.e., 2+4/3∆c2 ≥ 0 Þ ∆c2 ≥ -3/2 24 1+1/3∆c2 ≥ 0 Þ ∆c2 ≥ -3 c2’=3+ (-3/2) =1.5 The common value is
∆c2 ≥ -3 Þ ∆c2=[-3/2, +∞). Therefore, the range over which the parameter (c2) can change without
affecting the current optimal solution (0, 6) is [1.5, +∞). CHAPTER 4: INTEGER PROGRAMMING In LPP all
the decision variables were allowed to take any non-negative values as it is quite possible and
appropriate to have fractional values in many situations. However, there are several conditions in
business and industry that lead to planning models involving integer valued variables. That is, many
practical problems involve decision variables that must be integer valued. There are cases that the
fractional values of variables may be meaningless in the context of the actual decision problem. For
example: v In production, manufacturing is frequently scheduled interms of discrete quantities. v
Production of livestock involves discrete number of animals Integer programming models require all of
the assumptions implicit in linear programming models except that certain specific variables must be
integer valued. v When all the variables are constrained to be integers, it is called a pure-integer
programming model, and in case only some of the variables are restricted to have integer values, the
problem is said to be a mixed-integer programming problem. There are two methods used to solve IPP,
namely i. Gomory’s fractional cut method ii. Branch and bound method (search method) 4.1. Gomory’s
Fractional Cut Method (Algorithm) This method consists of first solving the IPP as an ordinary LPP by
ignoring the restriction of integer values and then introducing a new constraint to the problem such that
the new set of feasible solution includes all the original feasible integer solution, but does not include
the optimum non-integer solution initially found. This new constraint is called Fractional Cut or
Gomorian constraint. Then the revised problem is solved using simplex till an optimal integer solution is
obtained. Gomory’s Fractional Cut Method involves the following steps: 1. Solve the IPP as an ordinary
LPP by ignoring the restriction of integer values 2. Test the integrality of the optimum solution. Ø If all Xbi
≥ 0 and are integers, an optimum integer solution is obtained Ø If at least one bi is not an integer then go
to the next step 3. Select the source row Ø If only one Xbi is non-integer, the row corresponding to non-
integer solution will be the source row 25 Ø If more than one Xbi is non-integer, choose the row having
the largest fractional part (fi) as a source row. In this case write each Xbi as (Xbi = xbi +fi): Where xbi is
integer part of Xbi (solution) and fi is the positive fractional part of Xbi. Þ0< fi s1, move down vertically
to the second row and make the second allocation of the magnitude X21=min (s2, d1-X11) in cell (2, 1).
ii) If d1< s1, move right horizontally to the second column and make the second allocation of the
magnitude X12=min (s1-X11, d2) in cell (1, 2). iii) If d1=s1, there is a tie for the second allocation because
both the row and column are exhausted. Therefore, move diagonally to the next row and column and
make the second allocation of the magnitude X22=min (s2, d2) in cell (2, 2). 31 3. Repeat step 2 until all
the rim requirements are satisfied. 4. Check to be sure that all rim conditions are satisfied and the
numbers of occupied cells are equal to m+n-1. Examples: a). Obtain the initial basic feasible solution of
the following problem whose cost and rim requirement table is given below. D1 D2 D3 SS S1 2 7 4 5 S2 3
3 1 8 S3 5 4 7 7 S4 1 6 2 14 DD 7 9 18 b) A company has three production facilities S1, S2 and S3 with
production capacity of 7, 9 and 18 units per week of a product, respectively. These units are to be
shipped to four warehouses D1, D2, D3 and D4 with requirements of 5, 8, 7 and 14 units per week,
respectively. The transportation cost (in birr) per unit between the warehouses in the table below. D1 D2
D3 D4 S1 19 30 50 10 S2 70 30 40 60 S3 40 8 70 20 Obtain the initial basic feasible solution using NWC
method. Ø Total cost=Birr 1015 Minimum Cost Method (MCM) Since the objective is to minimize the
total transportation cost, we must try to transport as much as possible through those routes (cells)
where the unit transportation cost is lowest. Ø This method takes into account the minimum unit cost of
transportation for obtaining initial solution and can be summarized as follows: The steps involved in
Minimum Cost Method are: 1. Select the cell with the lowest unit cost in the entire transportation table
and allocate as much as possible to this cell, so that entire supply is exhausted or demand is satisfied. Ø
In case the smallest unit cost cell is not unique, then select the cell where maximum allocation can be
made. 2. After adjusting the supply and demand for all uncrossed-out rows or columns, repeat the
procedure with the next lowest unit cost among the remaining rows and columns of the transportation
table and allocate as much possible to that cell. 3. Repeat the procedure until the entire available supply
at various sources and demand at various destinations is satisfied. 4. Check to be sure that all rim
conditions are satisfied and that m+n-1 cells are allocated. Example: find the initial basic feasible solution
using MCM. 32 D1 D2 D3 D4 SS S1 19 30 50 10 7 S2 70 30 40 60 9 S3 40 8 70 20 18 DD 5 8 7 14 34 Ans:
Total cost=Birr 814 The Vogel’s Approximation Method (VAM) It is a better method for obtaining an initial
solution. However, it involves more computational effort than the NWC and MCM. This method
recognizes the costs information to find the initial solution. Ø It normally provides a solution which is
optimal or very close to optimal The steps involved in Vogel’s Approximation Method (VAM) are: 1. For
each row and column, compute the difference between the lowest cost element and the next lowest
cost element of the row/column. Ø The difference between the lowest cost and the next lowest cost for
a given row or column is said to be the penalty number for that row or column. 2. Select the row or
column having the largest penalty number. If there is a tie it can be broken by selecting the cell where
minimum cost of transportation is found. 3. Assign (allocate) the maximum number of units to the
lowest cost cell in the corresponding row or column selected in step 2. And then eliminate a row or
column whose supply is exhausted or requirement is satisfied. 4. Repeat step 1 to 3 until a complete
initial solution is obtained. 5. Check to be sure that all rim conditions are satisfied and that m+n-1cells
are allocated. Exercises: a). Find the initial basic feasible solution of the following problem using VAM D1
D2 D3 D4 SS S1 19 30 50 10 7 S2 70 30 40 60 9 S3 40 8 70 20 18 DD 5 8 7 14 34 Ans: Total cost=Birr 779
b). Determine an initial basic feasible solution for the following transportation problem by using NWC,
MCM and VAM. D1 D2 D3 D4 SS A 11 13 17 14 250 B 16 18 14 10 300 C 21 24 13 10 400 DD 200 225 275
250 33 Methods for testing the optimality and improving the solution Once an initial solution is
obtained, the next step is to check its optimality. An optimal solution is a solution which is best among all
feasible solution to achieve the objective function. Ø It is the one where there is no other set of
transportation routes (allocations) will further reduce the total transportation cost. In order to test the
optimality of the initial solution to a given transportation problem, we have to evaluate each unoccupied
cell (unused route) in the transportation table interms of an optimality to reduce total transportation
cost. There are several methods for testing and improving the initial solution of the transportation
problem. The two important once are: a) The Stepping-Stone Method, and b) The Modified-Distribution
(MODI)Method The Stepping-Stone Method The Stepping-Stone Method is an iterative procedure that
exchanges one variable that that is in the basis (i.e. occupied cell), with other variable that is not in the
basis (i.e. non-basic or empty or non-occupied cell) in such a way that the transportation cost is
improved. The procedure involved in this method will be as follows: Step 1: Test the optimality Ø In this
case each variable with a value of zero empty cells is a candidate to be selected as entering variable.
Now the question is “which non basic variables (empty cell) should be included in the new solution? To
answer this question, the stepping-stone method involves (performs) the following: i. Construct the loop
for each zero cell (empty cell). To construct a loop, Ø Start with the zero-cell, and then move horizontally
and vertically with corner cell occupied. That means, each time move in a right angle to the last move. Ø
Adding and subtracting the unit shipment cost in an alternating fashion until we end up at the zero cell.
Note: 1. There is only one loop for any given zero (empty)-cell 2. The loop crosses itself as long as the
intersection is at the right angle 3. The loop can be traversed in either clock-wise or anti-clock wise
direction ii. Compute the net contribution or improvement index for each zero cell Ø Improvement index
indicates the opportunity of reducing total transportation cost. Ø If all values of improvement index are
+ve, the total transportation cost is optimal and can’t be improved. Therefore, the solution is optimal
solution. However, if at least 34 one value of the improvement index is –ve, the total transportation cost
can be improved. Step 2: identifying the entering variable Ø Select the cell with the most negative net
contribution (improvement index)as entering variable. Step 3: Identifying the leaving variable Ø Examine
the loop for entering variable, selected in the previous step, with minus sign and select the one with
lowest (smallest) shipment (allocation) as leaving variable. Step 4: Generate a new solution Ø The new
solution can be generated by adding the shipment amount in leaving variable cell to each plus sign cells
and subtracting the amount from each minus cell in the selected loop. Step 5: Check for optimality (back
to step 1) a. Construct the loop for each zero-cell (empty cell) b. Compute the net contribution or
improvement index for each zero cell Example: obtain the optimum amount of shipments that minimize
the transportation cost. D1 D2 D3 D4 S1 19 30 50 10 S2 70 30 40 60 S3 40 8 70 20 Ans: the minimum
shipment cost is Birr 743 The Modified Distribution (MODI) Method It is an efficient method for
determining the entering variable from available non basic variable. This method is based on the dual of
the transportation problem or it uses shadow price Ui for the source (supply constraint) and Vj for the
capacity (demand constraint). Ø Ui is the relative implicit contribution (value) of an additional unit of
capacity (SS) at sources i. Ø Vj is the relative implicit contribution (value) of an additional unit of
requirement (DD) at destination j. Theorem (conditions): For balanced transportation problem, Ø For
occupied cell, Ui+Vj=Cij Ø For empty cells Cij-( Ui+Vj)=∆ij ü Ui+Vj represent the opportunity cost of
shipping one unit from source i to requirement j and ü Cij-( Ui+Vj) is the per unit net contribution to the
objective function for opening a route from i to j which is denoted by by ∆ij. Steps involved in MODI
method to test and improve the solution are the followings 35 Step 1: From the initial basic solution,
calculate Ui and Vj for each row and column using the occupied cells. Ø To start with, assign zero for a
particular Ui or Vj where there are maximum number of allocations in a row or column. If there is a tie
select arbitrarily. Ø Then, compute Ui ‘s and Vj ‘s for other rows and columns, respectively, using the
relation Cij= Ui+Vj for all occupied cells (i, j). Step 2: For unoccupied (empty) cells, calculate the net
contribution by using the relation: ∆ij =Cij-(Ui+Vj) for all i and j i. Compute the sum of Ui and Vj and write
that at the bottom left corner of that empty cell. ii. Compute the net contribution and write that at the
bottom right corner of that empty cell. Step 3: Examine the sign of ∆ij for empty cell ØThis step gives us
the opportunity criteria a. If ∆ij ≥0 for all empty cell, the current basic feasible solution is optimum. b. If
∆ij =0 for some empty cell, then the current solution will remain optimum but an alternative solution
exists. c. If ∆ij ≤ 0 for one or more empty cells, the current basic feasible solution is not optimum. So that
an improved solution can be obtained by entering unoccupied cell (i, j) in the basis. Step 4: Select an
empty cell having the largest –ve number of ∆ij as entering variable (cell). Step 5: Identify the leaving
variable (cell). ØThe method (criteria) of identifying the leaving variable and determining the new
solution is the same as the stepping-stone method. a) Construct the loop (closed path) for entering
variable (cell) b) Assign +ve and –ve sign alternatively c) Examine the loop with minus sign and select the
cell with lowest (smallest) shipment (allocation) as leaving variable. Step 6: Generate a new solution Ø
The new solution can be generated by adding the shipment (allocation) amount in leaving cell to each
plus sign cells and subtracting the amount from each minus cell in the selected loop. Step 7: Check for
optimality of the current solution. ØIf not optimal, repeat the steps from step 1 till an optimum basic
feasible solution is obtained. ØThe optimum solution is obtained when for all empty cell, ∆ij ≥0 Exercises:
1. Find the optimum solution of the following problem using MODI D1 D2 D3 D4 SS S1 19 30 50 10 7 S2
70 30 40 60 9 S3 40 8 70 20 18 DD 5 8 7 14 34 Ans: Total cost=Birr 743 2. A firm manufacturing a single
product has three plants I, II and III. They have produced 60, 35 and 40 units, respectively during this
month. The firm had made a commitment 36 to cell 22 units to customer A, 45 units to customer B, 20
units to customer C, 18 units to customer D and 30 units to customer E. find the minimum possible
transportation cost of shifting the manufactured product to the five customers. The net unit cost of
transporting from the three plants to the five customers is given below: Customers Plants Ans: (I, B) =45,
(I, E) =15, (II, A) =17, (II, D) =18, (III, A) =5, (III, C) =20, (III, E) =15, Total cost=290 Unbalanced Supply and
Demand For a feasible solution to exist, it is necessary that the total supply must equal to demand. Ø
That is, total supply =total demand However, a situation may arise when the total available supply is not
equal to the total demand. The following two cases may arise: a) If total supply exceeds total demand, Ø
An additional column (a dummy demand centre) can be added to the transportation table to absorb the
excess supply. In this case, the unit transportation cost for the cell in this column is set equal to zero
because these represent product items that are not being made (not being sent). b) If total demand
exceeds total supply, Ø A dummy row (a dummy supply centre) can be added to the transportation table
to account for the excess demand. In this case, the unit transportation cost here also for the cells in the
dummy row are equal to zero. Example: A product is manufactured by four factories A, B, C and D. The
unit production costs are Birr 2, 3, 1 and 5, respectively. Their production capacities are 50, 70, 30 and 50
units respectively. These factories supply the product to four stores, demands of which are 25, 35, 105
and 20 units respectively. Unit transportation cost in dollars from each factory to each store is given in
the table below. Stores Factories A B C D E I 4 1 3 4 4 II 2 3 2 2 3 III 3 5 2 4 4 I II III IV A 2 4 6 11 B 10 8 7 5
C 13 3 9 12 D 4 6 8 3 ( ). 1 1 å å = = = m i n j SSi DDj ( ) 1 1 å å = = > m i n j SSi DDj ( ) 1 1 å å = = <
m i n j SSi DDj 37 Determine the extent of deliveries from each of the factories to each of the stores so
that the total production and transportation cost is minimum. Degeneracy and Its Resolution of
Transportation Problems A basic feasible for the general transportation problem must consist of exactly
m+n-1 positive allocations in independent positions in the transportation table. A solution will be called
degenerate when the number of occupied cells is less than the required number, m+n-1. Ø In such cases,
the current solution cannot be improved because it is not possible to draw a closed path for every
occupied cell. In addition the values of dual values Ui and Vj which are used to test the optimality cannot
be computed. Thus, we need to remove the degeneracy to test and improve the given solution. The
degeneracy in the transportation problems may occur when obtaining an initial solution or at any stage
while moving towards optimal solution. This happens when two or more occupied cells with the same
minimum allocation become unoccupied simultaneously. How to resolve degeneracy An initial stage, to
resolve degeneracy, we proceed by allocating a very small quantity (ε)which is close to zero to one or
more (if needed) unoccupied cells so as to get m+n-1 number of occupied cells. ØThe amount is denoted
by a Greek letter ε (epsilon). This quantity would not affect the total cost as well as supply and demand
values. In minimization transportation problem it is better to allocate (ε) to unoccupied cells that have
lowest transportation costs. To resolve degeneracy which occurs during optimality test, the quantity (ε)
may be allocated to one or more cells which have become unoccupied recently to have m+n-1 number
of occupied cells in the new solution. Example: Goods have to be transported from sources S1, S2 and S3
to destinations D1, D2 and D3. The transportation cost per unit, capacities of the sources and
requirements of the destinations are given in the following table. Supply Demand Determine a
transportation schedule so that cost is minimized. Alternative Optimal Solutions D1 D2 D3 SS S1 2 4 6
120 S2 10 8 7 80 S3 13 3 9 80 DD 150 80 50 38 The existence of alternative optimal solution can be
determined by an inspection of the opportunity costs (net contribution of empty cells), ∆ij for the
occupied cells. Ø If an occupied cell in an optimal solution has opportunity cost of zero, an alternative
optimal solution can be formed with another set of allocations without increasing the total
transportation cost. Example: Consider optimal solution of the given table. The net contributions of all
unoccupied cells are positive except for the cell (X, A) which has a zero. This means if cell (X, A) is entered
in to the basis, no change in the transportation cost would occur. To determine this alternative solution,
form a closed path for cell (X, A) as shown in table below. The maximum quantity which can be allocated
to cell (X, A) is 21. After this change, the new solution is: A B C D Supply Ui W 4 +4 8 76 8 +8 0 +16 76
Ui=-16 X 16 0 24 21 16 41 0 20 82 Ui=0 Y 8 72 16 5 24 +16 0 +8 77 Ui=-8 Demand 72 102 41 20 235 Vj
V1=16 V2=24 V3=16 V4=0 A B C D Supply Ui W 4 +4 8 76 8 +8 0 +16 76 Ui=-16 X 16 (+) 0 24 21(-) 16 41 0
20 82 Ui=0 Y 8 (-) 72 16 5 (+) 24 +16 0 +8 77 Ui=-8 Demand 72 102 41 20 235 Vj V1=16 V2=24 V3=16
V4=0 39 Since all ∆ij values are positive or zero, the solution given the table is optional with a minimum
total transportation cost of 2424 which is the same as in the previous solution. Maximization
Transportation Problem In general, transportation model is used for cost minimization problems.
However, it is also used to solve problems in which the objective is to maximize total value or benefit.
That is, instead of unit cost cij, the unit profit or payoff pij associated with each route, (i, j) is given. The
objective is to maximize the total profit for which the profit matrix is given. The objective is to maximize
the total profit for which the profit matrix is given. For this we have to convert the maximization problem
in to minimization problem (profit matrix in to loss matrix) by subtracting all the elements (profit) from
the highest element (profit) in the given transportation table. This modified minimization problem can
be solved in the usual manner. Ø i.e the algorithm for solving modified problem is the same as that for
the minimization problem. Example: Solve the following transportation problem to maximize the profit.
Total profit=90x70+5x50+9x90+11x40+15x10+1x70+7x90=Birr 4580 5.2. Assignment Problems
Definitions: Given n facilities and n jobs and given the effectiveness of each facility for each job, the
problem is to assign each facility to one and only one job so as to optimize given measure of
effectiveness. A B C D Supply Ui W 4 +4 8 76 8 +8 0 +16 76 Ui=-16 X 16 21 24 0 16 41 0 20 82 Ui=0 Y 8 51
16 26 24 +16 0 +8 77 Ui=-8 Demand 72 102 41 20 235 Vj V1=16 V2=24 V3=16 V4=0 Destination Source A
B C D Supply 1 15 51 42 33 23 2 80 42 26 81 44 3 90 40 66 60 33 Demand 23 31 16 30 100 åå= = = m i
n j Maximiz 1 1 pi j xij e Z 40 The assignment problems are characterized by a need to pair items in one
group with items in another group in a one-to-one matching. There are many situations where the
assignment of people or machines and so on to different jobs. The assignment is a problem because
people possess varying abilities for performing different jobs and, therefore, the costs of performing the
jobs by different people are different. Obviously, all persons could do a job in the same time or at the
same cost then it would not matter who of them is assigned the job. Thus, in an assignment problem,
the question is how should the assignments be made in order that the total cost of performing the job is
minimum (or the total value is maximized when pay-offs are given in terms of, say profits). The
assignment problem has many applications in allocations and scheduling: Examples, Ø In assigning
salesmen to different regions Ø Vehicles and drivers to different routes Ø Products to factories Ø Jobs to
machines Ø Contracts to binders, etc Mathematical formulation of the assignment problem The
assignment model can be expressed as follows: 0, if not 1, if the i person is assigned to the j job x 1, j
1,2,...,n (only one person should be assigned to the j job ) x 1, i 1,2,...,n (one job is assigned to the i
facility) to : Z C th th ij th 1 th 1 ij n i 1 n j 1 ij î í ì = = = = = = å å åå = = = = m i n j ij xij Subject
Minimize x 41 Comparison with transportation and assignment problem Transportation problem
Assignment problem i.No. of sources and destinations need not be equal. Hence the cost matrix is not
necessarily a square matrix. No. of workers and jobs need tot be equal. Hence cost matrix is a square
matrix. ii. Xij: indicates the quantity to be transported from ith origin to jth destination and take any
possible value. Xij: indicates the jth job to be assigned to ith person and it can take either 1 or 0. iii. The
row and column sum is equal to ssi and ddj. The row and column sum is exactly1 iv. The problem is
unbalanced if ∑ss≠∑dd. The problem is unbalanced if the cost matrix is not a square matrix. Although an
assignment problem can be solved using simplex method as it is a special case of linear programming
problems, it can be easily solved manually using a special-purpose algorithm known as the assignment
method/ Hungarian Method. Methods of solving the assignment problem (Hungarian Method) Once we
have the cost matrix of a given problem, the optimum assignments (solutions) using this method can be
obtained through the following major steps: Step 1: Subtract the smallest number in each cost matrix
(table) row from every number in that row. Step 2: In the new cost table resulted from step 1 subtract
the smallest number in each column from every number in that column. As a result of this action, we get
a table called reduced cost table in which there is at least one zero in each row and each column. Step 3:
In the reduced cost table draw the minimum number of vertical and horizontal straight lines necessarily
to cover all zero elements in the table. If the number of lines equals either the number of columns in the
table then the solution is optimum and one may proceed to step 5. If the number of lines drawn is
smaller than number of rows or columns, proceed to step 4. Step 4: Subtract the smallest number not
covered by a line from every uncovered number and add the same number to any number(s) lying at the
intersection of any two lines. And then return to step 3 and continue until an optimum assignment is
reached. Step 5: Once it is confirmed that the optimum solution has been obtained as indicated in step
3, make the optimum assignments (indicated by the zero elements), as explained below; 42 a. Beginning
with row 1 of the reduced table, examine all the rows, until a row with exactly one unmarked zero is
found. (A zero is marked if it is either bolded (0) or has a symbol x over it). Bold the unmarked zero to
represent an assignment and cross out (x) all other unmarked zeros in that column. Repeat this process
until, each row has no unmarked zeros or has at least two zeros. b. Beginning with column 1, examine all
the columns, until a column with exactly one unmarked zero is found. Bold the unmarked zero to
represent an assignment and cross out (x) all other unmarked zeros in that row. Repeat this process until
each column has no unmarked zeros or has at least two zeros. c. If a complete assignment is found then
stop, otherwise go to step 4. Examples: 1. A machine tool company decides to make four subassemblies
through four contractors. Each contractor is to receive only one subassembly. The cost of each
subassembly is determined by the bids submitted by each contractor and is shown in the following table.
Contractors Subassemblies Assign the different subassemblies to contractors so as to minimize the total
cost? 2. Using the following cost matrix , determine: a. Optimal job assignment and b. The cost of
assignments Machinist Job 1 2 3 4 5 A 10 3 3 2 8 B 9 7 8 2 7 C 7 5 6 2 4 D 3 5 8 2 4 E 9 10 9 6 10 Ans: The
optimal job assignment and cost associated with the assignment pattern is: I II III IV 1 15 13 14 17 2 11
12 15 13 3 13 12 10 11 4 15 17 14 16 43 Workers Job Cost A B C D E 2 4 5 1 3 3 2 4 3 9 21 Unbalanced
assignment problems The Hungarian method of solving an assignment problem requires that the
number of columns should be equal to the number of rows. When they are equal, the problem is
balanced problem, and if not, it is unbalanced problem. In such situations, dummy column(s)/ row(s),
whichever is smaller in number, are inserted with zeros as the cost elements. After introducing dummy
columns/rows, the problem is solved in the usual manner. Example: A company has 4 machines to do 3
jobs. Each job can be assigned to one machine. The cost of doing the job in different machine is given
below. Determine the optimal job assignment which minimizes the total cost. Jobs Machine A B C D 1 18
24 28 32 2 8 13 17 18 3 10 15 19 22 Ans: The optimal job assignment and cost associated with the
assignment pattern is: Machine Job Cost 1 A 18 2 C 15 3 B 17 50 UNIT 6: NETWORK ANALYSIS WITH CPM
AND PERT 44 The techniques of operations research used for planning, scheduling and controlling large
and complex projects are often referred as network analysis, network planning or scheduling techniques.
All these techniques are based on the representation of the project as a network of activities. A network
is a graphical plan consisting of a certain configuration of arrow and nodes which indicates the logical
sequence of various activities to be performed to achieve the objectives of a project. The two well
known techniques are PERT and CPM. PERT (Program Evaluation and Review Technique) Ø It was
developed in 1956-58 by research team to help in the planning and scheduling of the US navy’s Polaris
Nuclear Submarine Missile Project which involved thousands of activities. The technique has proved to
be useful for all jobs or projects which have an element of uncertainty in the estimation of duration, as is
the case with new type of projects the like of which have never been taken up before. CPM (Critical Path
Method) ØWas developed by E.I. DuPont Company along with Remington Rand Corporation. The aim
behind its development was to provide a technique for control of maintenance of company’s chemical
plants. In course of time, use of CPM got extended to the field of cost and resource allocation. 6.1 Basic
difference between PERT and CPM PERT I. It assumes a probability distribution for the duration of each
activity. Thus, completion time estimates for all the activities are needed. II. To perform PERT analysis on
a project the emphasis is given on the completion of a task rather than the activities required to perform
to reach to a particular event or task. Thus, it is also called an event-oriented technique. III. It is used for
one-time projects involving activities of non-repetitive nature (i.e. activities which may never have been
performed before) in which time estimates are uncertain. IV. It helps in identifying critical areas in a
project so that necessary adjustment can be made to meet the scheduled completion date of the
project. CPM I. This technique was developed in connection with a construction and maintenance
project in which duration of each activity was known with certainity. II. It is suitable for establishing a
trade-off for optimum balancing between schedule time and cost of the project. 45 III. It is used for
completion of projects involving activities of repetitive nature. 6.2. Network Components and
Precedence Relationships Drawing a network diagram is the first step in network (PERT/CPM) analysis. A
network diagram represent project milestones, such as the start or the completion of activity (task) or
activities, and occur at a particular instant of time at which some specific part of the project has been or
is to be achieved. CPM/PERT network diagram consists of two major components: Events and Activities.