Operations Research Lecture Notes By Prof A K Saxena Professor and Head Dept of CSIT G G Vishwavidyalaya, Bilaspur-India
Operations Research • • • •
•
Some important tips before start of course material to students Mostly we followed Book by S D Sharma, as prescribed for this syllabus At places, we use some internet links not necessarily mentioned there at. We acknowledge all such resources. As the course is mostly mathematical in nature, we will be solving problems in class room. The problems will involve a lot of mathematics, calculations although simple but will be so time consuming to express on computers, we leave it up to students to ask in details any particular topic or problem in class or during contact hours. So ready to take off !!!!
History of Operations Research The term Operation Research has its origin during the Second World War. The military management of England called a team of scientists to study the strategic and tactical problems which could raise in air and land defence of the country. As the resources were limited and those need to be fully but properly utilized. The team did not involve actually in military operations like fight or attending war but the team kept off the war but studying and suggesting various operations related to war.
What is Operations Research? Several definitions have been given • Operations research
(abbreviated as OR hereafter) is a scientific
method of providing executive departments with a quantitative basis for decisions regarding the operations under their control: Morse and Kimbal (1944) • OR is an analytical method of problem-solving and decision-making that is useful in the management of organizations. In operations research, problems are broken down into basic components and then solved in defined steps by mathematical analysis. • Operational Research (OR) is the use of advanced analytical techniques to improve decision making. It is sometimes known as Operations Research, Management Science or Industrial Engineering. People with skills in OR hold jobs in decision support, business analytics, marketing analysis and logistics planning – as well as jobs with OR in the title. •As such a number of definitions can be found in literature, you can express the term OR with the spirit mentioned in the literature.
Meaning of Operations Research? As stated early, the OR does not mean to get involved in the operations but suggestion for better execution of operations. Suggesting strategy how the operations can be improved and get better results. The genesis of OR is in finding better ways to solve a problem. Thus it is analytical not purely hard core action oriented. As we explore several options for the analysis of operations, we search and re-search the effects of operations. If one solution offers some result, try second solution and see and compare with previous and so on unless we satisfy ourselves. Therefore research term sounds to indicate that there would be enough thinking on the outcome of several results. Hence Operation Research.
Meaning of Operations Research? A simple example of OR Given different routs to reach from source A to destination B. Also on these routes there can be various ways to travel. For simplicity, we assume we have travelling modes x,y,z each having different travelling time and cost incurred on travel. I have a limited money or budget and a limited time also to reach destination B. Now all options can reach me A to B but they will not be fit for me. I want a solution which I can use so that I can afford journey both in terms of cost and time. OR can be used here.
Management Applications of Operations Research? 1. 2. 3. 4. 5. 6.
Finance budgeting and investment Purchase, procure and exploration Production management Marketing Personal management Research and development
Scopes of OR (elaborate following by your own as discussed in class) 1. 2. 3. 4. 5.
Agriculture: optimum allocation of land, crops, irrigation etc Finance: maximize income, profit, minimize cost etc In industries: Allocation of resources, assignment of problems to worthy employees etc Personal management: To appoint best candidate, decide minimum employees to complete job etc Production management: Determine number of units to produce to maximize profit, etc
Principles of Modeling in Operations Research? How should we model problems of OR, for this purpose following principles can be kept in mind (Some principles are given here) 1. Try to build up a simple model in stead of building complex model 2. Use only the specialized model to solve a problem rather than applying same model to fit in every problem 3. Model validation before implementation: Test a model before it is actually implemented in real world 4. Model should be practical in approach and not a pure ideal one which may face problem when put in real time problems 5. Use a model only for which it is best. It should not be pressed to do what it can not do better with 6. OR models can support decision makers in their process but can not replace or in many cases outperform decision makers.
Main Characteristics or features of Operations Research? 1.
2.
3.
4. 5.
Inter-disciplinary team approach: In OR, to model a problem, people or experts from various disciplines are joined. E.g Computer expert, Economists, mathematicians can join to model a economics problem Wholistic approach to the system: OR models have to think the whole business not for the particular unit for which it is engaged. It will see the effect of the model in entire business. Using OR techniques, we can only improve the solutions of the exiting problems but can not make them perfect due to many other factors affecting solutions Use of scientific research to apply the state of art techniques to improve solutions Total output is optimized by maximizing or minimizing output
In the present course we will consider only few well established standard problems of OR like LPP, Transportation, Assignment, Replacement, CPM/PERT. Further there can be optimization models involving Genetic, Swarm intelligence, etc beyond the scope of the course here
Expression of problems in Operations Research? A typical example of OR problem Most of the problems in OR are of the following form • Given an objective function also called fitness function which depends on certain variables or parameters. The objective function has to be optimized, i.e. maximized or minimized. •A set of constraints given which should be satisfied while solving the problem •Some conditions on the nature of parameters so as to ignore those parameters at all which do not fulfill these conditions e.g. x2 =4 will give x=+2 and x=-2 but we do not want to consider x=-2 so we have to declare x>=0 at the start of the problem.
Operations Research Introduction to LPP Equations and Inequalities/Constraints We are familiar with terms equations such as 2x+ 3y -3z = 12 is an equation as we have an equality sign relating left hand side with right hand side But in OR we will mostly deal with types of following 2x + 3y <= 14 Or 2x + 3y >= 14 These types of representations will be called as constraints or inequalities in OR LPP stands for linear Programming Problem which means finding optimum solutions (minimum or maximum) represented by a function of variables or parameters called objective function, denoted by z Subject to a set of linear equations or inequalities called constraints.
Operations Research Introduction to LPP In an LPP, the equations or inequalities are of the linear form like a11 x1 + a12 x2 + …+ a1n xn = b1 or a11 x1 + a12 x2 + …+ a1n xn >= b1 or In general
where aij, bi, and cj are given constants. aij are coefficients of decision variables x’s, bi are constraints values and cj are coefficients associated to objective function z
Operations Research Introduction to LPP A complete solution to an LPP comprises of following steps 1.Formulating problem to a proper mathematical form 2.Solving the problem graphically/algebraically In our discussion onward, we will first learn how to formulate given problem in the standard form, then learn first its graphical solution then algebraic solution. In algebraic solution, we will apply simplex method.
Operations Research Introduction to LPP An example problem in formulated form
Objective Function
Max z= 5x1 + 7x2 s.t.
x1 2x1 + 3x2 x1 + x2
< < <
6 19 8
x1 > 0 and x2 > 0
“Regular” Constraints Non-negativity Constraints
Operations Research Introduction to LPP Exercise on formulating an LPP A toy company manufactures two types of dolls, A and B. Each doll of type B takes twice as long to produce as one of type A, and the company would have time to make a maximum of 2000 per day. The supply of plastic is sufficient to produce 1500 dolls per day of A and B combined. Each B type doll requires fancy dress of which there are only 600 per day available. If the company makes a profit of Rs 3 and Rs 5 on doll A and B respectively, then how many dolls of A and B should be produced per day in order to maximize the total profit. Formulate this problem.
Operations Research Introduction to LPP Formulation of LPP In this problem (and these types of problems) start from last. We are to maximize the profit. So the objective function z will be Maximize z Then two products are dolls of A and B types. So decision variables will be x1 and x2. Now let x1 denotes the number of dolls of type A required for maximize profit z and x2 be dolls for B type. Profit on each doll of A is Rs 3 and that for each doll B is Rs 5 so Max z= 3x1 + 5x2 As x2 takes twice time than x1 and total time allowed per day can produce 2000 dolls so x1 + 2x2 <=2000 Fancy dress material is available for B type 600 dolls so X2<=600 Also plastics availability is enough to produce 1500 dolls for A and B both so x1+x2<=1500 As x1, x2 are numbers of dolls to be produced per day so x1,x2 >=0 Writing all steps together Max z= 3x1 + 5x2
(Objective Function)
s.t. x1 + 2x2 <=2000 (Time constraint) x1+ x2 <=1500 (Plastics availability constraint) X2<=600 (Fancy dress material constraint) and x1,x2 >=0 (non negativity problem)
Operations Research Introduction to LPP Formulation of LPP There are similar type of other formulation problems in LPP. The easy way to do is 1.First read the LPP to find the term Profit/Cost/Time or similar term to maximize/minimize/optimize 2.Usually the profit/time etc. associated with each of the product will determine the decision variables viz. x1,x2,… 3.Read each sentence carefully, a constraint ( in rare case an equality) with some numeric value is given. 4.Convert all such sentences to constraints/inequalities. 5.Write the objective function first like Max(Min) z=…. 6.Then write subject to (s.t.) and all inequalities in following lines below s.t. 7.Do not forget to write non negativity conditions x1>=0, x2>=0, etc…
Operations Research Introduction to LPP Formulation of LPP There are similar type of other formulation problems in LPP. The easy way to do is 1.First read the LPP to find the term Profit/Cost/Time or similar term to maximize/minimize/optimize 2.Usually the profit/time etc. associated with each of the product will determine the decision variables viz. x1,x2,… 3.Read each sentence carefully, a constraint ( in rare case an equality) with some numeric value is given. 4.Convert all such sentences to constraints/inequalities. 5.Write the objective function first like Max(Min) z=…. 6.Then write subject to (s.t.) and all inequalities in following lines below s.t. 7.Do not forget to write non negativity conditions x1>=0, x2>=0, etc…
Operations Research Introduction to LPP Solution of LPP We will see how LPP can be solved after these are formulated. There can be two type of solutions to discuss 1.Graphical solution 2. Algebraic mainly simplex method First we shall discuss graphical method to solve LPP. We adopt an easy approach here by taking a rough sketch of graphs manually but in principle correct.
Operations Research Introduction to LPP Graphical Solution of LPP The concept of graph and linear equations. In a graph, we have two axes, axis of x and axis of y. + + + y -
(-,+) IInd
(+,+) Ist O
(-,-) IIIrd
(+,-) IVth
..---------- - x ++++++++++… The axes can be divided in four quadrants. Any point (x,y) lies in one of the quadrants. The origin O is the point having (0,0) coordinates. Any point in four quadrants will be (x,y), (-x,y),(-x,-y) and (x,-y) in first, second, third and fourth quadrant respectively.
Operations Research Introduction to LPP Graphical Solution of LPP The Suppose an LPP is given in the formulated form. Max(min) z = c1 x1 +c2 x2 +…cnxn s.t. a11 x1 +a12 x2 +…..a1n xn (<=>)b1 a21 x1 +a22 x2 +…..a2n xn (<=>)b2 ……………………………………………………………
am1 x1 +am2 x2 +…..amn xn (<=>)bm with xi’s >=0 1.Consider all constraints as equations 2.Plot all lines (equations) on the graph 3.Indicate point of intersection of every two lines intersecting each other or the point of intersection of a line with axis as the case may be. If you are not using the graph accurately the solve the two lines algebraically to know point of intersection. 4.Shade the region of every line which is towards the axis (<=) or away from axis (>=).
Operations Research Introduction to LPP Graphical Solution of LPP 5. As we have xi’s >=0, all valid regions will lie in the first region going towards origin (<=) or towards infinity (>=) 6. After all lines (constraints ) are plotted and shaded, the common region, shaded and surrounded by all lines will give the feasible region. 7. Now plot objective function line z at the origin and move it parallel away from first quadrant in the +infinity direction. 8.Keep the line z sliding in the feasible region. A point will be reached which is the extreme point in the feasible region. In most of the cases of maximum, this is the farthest point from origin and for cases of minimum, this point is the closest to origin. This point is called the point of optimum solution of z. 9.Find out the value of z at this point. The point is the solution point with the value of z as calculated there. 10.For a quick solution, take all intersection points and shade the common region called feasible region. Find out the coordinates of every corner point in the feasible region. Calculate z at each of these points, and finalize the point with maximum(minimum) value of z as the solution point with value of z as calculated there at.
Operations Research Introduction to LPP Plotting of lines Suppose a line (or inequality) is given as follows x1 + 4 x2 (< = >) 4 Then first for plotting purpose write it as x1 /4 + x2 /1 (< = >) 1 (i.e. x/a + y/b =1 form) Now plotting becomes easier 21| | 1 2
| 3
| 4
(0,0)
The slanted line represents x1 + 4 x2 (< = >) 4 or x1 /4 + x2 /1 (< = >) 1 . The line cuts intercepts 4 from axis x1 and +1 from axis x2. This is why we brought the line in the form x1 /4 + x2 /1 (< = >) 1
Operations Research Introduction to LPP Plotting of lines If we have lines (or inequality) of the form x1 - 4 x2 (< = >) 4 Then first for plotting purpose write it as x1 /4 + x2 /-1 (< = >) 1 (i.e. x/a + y/b =1 form) Now plotting becomes as follows 21| | 1 2 -1- (0,0)
| 3
| 4
-2The slanted line represents x1 - 4 x2 (< = >) 4 or x1 /4 + x2 /-1 (< = >) 1 . The line cuts intercepts 4 from axis x1 and -1 from axis x2. This is why we brought the line in the form x1 /4 + x2 /-1 (< = >) 1
Operations Research Introduction to LPP Plotting of lines Similarly we can plot lines of other two types lying in second (-,+) and third (-,-) quadrants. The graphical solution to several LPP problems have been practiced in class room. Ply try solved and unsolved problems.
Operations Research Introduction to LPP General form of LPP The LPP can be in general one of the following forms Max(min) z = c1 x1 +c2 x2 +…cnxn s.t. the m constraints a11 x1 +a12 x2 +…..a1n xn (<=>)b1 a21 x1 +a22 x2 +…..a2n xn (<=>)b2 ……………………………………………………………
am1 x1 +am2 x2 +…..amn xn (<=>)bm with xi’s >=0 Slack and Surplus Variables Slack variable: If a constraint has <= sign x1 + x2 <=20 then to make it equality, we need to add some non negative term s to the left hand side of the constraint. Thus we have x1 + x2 + s =20 then s is called a slack variable. Surplus variable: If a constraint has >= sign x1 + x2 >=20 then to make it equality, we need to subtract some non negative term s from the constraint. Thus we have x1 + x2 - s =20 then s is called a surplus variable.
Operations Research Introduction to LPP Standard form of LPP The general form of LPP is given previously. The standard form has following characteristics Objective function should have only Maximum and NOT Min. So even if we have Min z = c1 x1 +c2 x2 +…cnxn, we will convert to Max form by Max z = -Min(z) or we can have Max z = -c1 x1 -c2 x2 -…cnxn, and can write z’ =-z so Min z = Max z’ Convert all constraints to equalities using slack or surplus variables so that we have a11 x1 +a12 x2 +…..a1n xn + xn+1 a21 x1 +a22 x2 +…..a2n xn + 0xn+1 + xn+2 ……………………………………………………………
am1 x1 +am2 x2 +…..amn xn + 0xn+1 + 0xn+2
……………………………………………………………
= b1 =b2 -(2) + xm+n
=bm
with all xi’s >=0 -(3) The objective function will become now Max z = c1 x1 +c2 x2 +…cnxn +0xn+1+0xn+2 +…0xn+m -(1) If any x is unrestricted in sign, convert it to x’ – x” where x’ and x” are >=0
Operations Research Introduction to LPP Matrix form of LPP The general and standard forms of LPP are given previously. The standard form can be converted to the Matrix form as follows Max z = CXT (transpose of X) subject to AX = b, b >=0 and x >=0 Where x = (x1,x2,…xn, xn+1,…xn+m) c =(c1,c2,..cn,0,…0) b= (b1,b2,…,bm) And Matrix A = a11 a12 ..a1n 1 0 0 a21 a22 ..a2n 0 1 0
… 1 … 0
………………………..
am1 am2 ..amn 0 0 0
…
0
Students are advised to attempt all problems related to the concepts so far and ask the doubts if any.
Operations Research Introduction to LPP Important Definitions of LPP See the standard form of LPP and equations 1,2,3 Solution of LPP: Any set of variables x = (x1,x2,…xn, xn+1,…xn+m) is called solution of LPP if it satisfies (2) only. Feasible Solution of LPP: Any set of variables x = (x1,x2,…xn, xn+1,…xn+m) is called feasible solution of LPP if it satisfies (2) as well as (3). Basic solutions and Basic Variable: A solution to (2) is a basic solution if it is obtained by setting n out of m+n variables equal to 0 and then solving for remaining m variables with the determinant of coefficients of these m variables is non zero. Usually we call those variables as basic variables which are used to get identity matrix in solving LPP using simplex method. Basic Feasible solutions: A basic solution to (2) is a basic feasible solution if it also satisfies (3). Optimum Basic Feasible solutions: A basic feasible solution which also satisfies (1) is called a Basic Feasible solutions. Unbounded Solution: If the value of objective function z can be increased or decreased infinitely then such a solution is called an unbounded solution. After these definitions, we are ready to start solution of LPP using simplex method.
Students must try some numeric problems based on the lectures completed so far.
Operations Research Introduction to LPP Solution of LPP problems The LPP can have following cases i.When we have purely slack based problems (<=) ii.When we have artificial variable based problems (= or >=) For (i) type problems, simple simplex method can be used. A number of exercises have been completed in class rooms. For (ii) type problems, simplex method with two phase or big M method can be used. A number of exercises have been completed in class rooms. Students must recall definitions of slack, surplus, artificial variables, basic variables etc and they should try more numeric problems based on these problems. Degeneracy in LPP While solving LPP using simplex method, some times we get min Ratio (XB /Xk ) same for more than one basic variable, then this problem is called degeneracy. Take few such examples and solve.
Operations Research Duality in LPP It has been discovered that every LPP has been associated with another LPP. One of these LPP is called Prime while the other LPP will be called Dual. Sometimes, the solution to a dual is easier than the primal so it is better to convert at that time primal into its dual. Primal LPP Suppose following LPP is given Max Zx =3x1+ 5x2 subject to x1 <=4; x2 <=6; 3 x1 + 2 x2 <=18; and x1, x2 >=0 Its corresponding dual will be as follows Dual LPP Min Zw = 4w1 + 6 w2 + 18 w3 subject to w1 +3 w3 >=3; w2 + 2w3 >=5; and w1,w2,w3 >=0 Matrix Form of Primal and Dual Suppose the matrix for LPP is
Operations Research Duality in LPP Matrix Form of Primal and Dual Suppose the matrix for LPP is Min Zx = Cx (Primal objective function), C €Rn Subject to AX<=b, b €Rn Where A is an mXn real matrix Dual of above LPP will be Minimize zw =bT w, b €Rn Subject to Atw>=cT, C €Rn Where w=(w1,w2,..wm) and AT, bT,cT are the transpose of A, B and C
Operations Research Duality in LPP General rules to convert primal into dual i.Convert objective function to max form (min z = -min z’ ) ii.Bring all inequalities to <= ( >= can be written as -<=) iii.Equality signs can be written as >= and <= so a=4 means a>=4 and a<=4; ie. –a<=-4 and a <=4 iv.Write unrestricted variables c as c’ – c’’ where c’, c’’ >=0 v.Transpose the rows and columns of constraint coefficients vi.Transpose the objective function coefficients (c’s) and right hand constants (b’s) vii.Change the inequalities from <= to >= viii.Minimize the objective function from maximize Duality is fairly simple, Try few numeric exercises
Operations Research Transportation Problems We often face the situation when we have to transport material from various places to various other places and want to minimize the time or cost of transporting these material (e.g. TV, computers etc) Transportation Problem(TP) is to transport various quantities of a single item stored at various origins to different locations or destinations such that the cost of transportation is minimum. Mathematical Formulation Suppose there are m origins, ith origin storing ai units of a certain product, there are n destinations and destination j requiring bj units of same item, the cost of transporting each of m origins to each of n destinations is known and given. Let C be the cost of shipping or transporting ith source to jth destination It is assumed that Σai = Σbj (i=1,…m; j=1,2,..m) such TP are called balanced TP. If Σai ≠ Σbj then those TP are unbalanced TP. In case of unbalanced TP we add one row or column with zero valued Cij in that row or column with the value of ai or bi = of that row as column equal to the difference of (Σ Σai - Σbj )
Operations Research Transportation Problems Mathematical Formulation So Σai = Σbj the problem is now to determine non negative values of xij satisfying the availability constraints n
∑x
for i=1,2,..,m
= ai
ij
j =1
And the requirement constraint m
∑x
ij
= bj
for j=1,2,..,n
i =1
And minimize the total cost of transportation m
z=∑ i =1
n
∑x c
ij ij
j =1
(Objective function)
Operations Research Transportation Problems Tabular Representation of TP (Given)
Warehouse/ Factories
W1
W2
..
Wn
Factory Capacities
F1
C11
C12
..
c1n
a1
F2
C21
C22
C2n
a2
…
..
..
..
Fm
Cm1
Cm2
..
Cmn
am
Requirements
b1
b2
..
bn
Σ a = Σb
…
Tabular Representation of TP (To find out)
Warehouse/ Factories
W1
W2
..
Wn
Factory Capacities
F1
x11
x12
..
x1n
a1
F2
x21
x22
x2n
a2
…
..
..
..
Fm
xm1
xm2
..
… xmn
am
Operations Research Transportation Problems To find out the solution of TP i.Find out initial basic feasible solution (ibfs) ii.Find out the optimal solution
Following methods are used to find out ibfs a.North west corner method b.Row minima method c.Column minima method d.Lowest cost entry method or matrix minima method e.Vogel’s approximation method All above ibfs methods are easy and have been discussed thoroughly with examples in class rooms. The optimal solution is obtained after ibfs is obtained by any of the five methods. The optimal solution will give the best value. The examples have been done in class room. Students are advised to contact in case of any doubt/problem about these exercises.
Operations Research Transportation Problems Degeneracy in Transportation Problems The basic feasible solution to an m-origin and n-destination TP can have maximum m+n-1 positive basic variables. If the number of basic variables is exactly m+n-1 then BFS is a non-degenerate. If however basic variables are less than m+n-1 then BFS are degenerate.
Operations Research Transportation Problems Unbalanced TP: As stated earlier that when Σai ≠ Σbj then such TP are said to be unbalanced TP e.g. given a TP, here total requirement (30) ≠ total capacity (34) so this problem is unbalanced
Mills
M1 M2
M3
M4
M5
Capacity
F1
4
2
3
2
6
8
F2
5
4
5
2
1
12
F3
6
5
4
7
3
14
Requirement
4
4
6
8
8
30≠ 34
Because there is a lack of 4 requirement so add 4 to requirement by an extra column as follows. Now the TP becomes balanced. Solve it as usual. Mills M1 M2 M3 M4 M5 Mf Capacity
F1
4
2
3
2
6
0
8
F2
5
4
5
2
1
0
12
F3
6
5
4
7
3
0
14
Requirement
4
4
6
8
8
4
34 =34
Operations Research Assignment Problems Basic We know that all fingers of our either hand are not equal. Same is the case with efficiency of each individual. One person is better in one job than another whereas other person is better than first in some other job. If we can assign suitable job to each individual then total efficiency will increase. Suppose there are n jobs to be performed by n persons and each of the persons can do each of the job but with different efficiency. Let Cij be the cost of performing jth job by ith person, the problem is to assign each job to each person such that no job is performed by more than one person or no person is assigned more than one job, and the total cost of performing all jobs is minimum.
Operations Research Assignment Problems Tabular form of assignment problem Jobs
1
Persons P1
2
..
j
..
n
C11 C12
..
C1j
..
C1n
P2
C21 C22
..
C2j
..
C2n
:
:
:
:
:
:
:
i
Ci1
Ci2
:
Cij
:
Cin
:
:
:
:
:
:
:
n
Cn1 Cn2
:
Cnj
:
Cnn
Operations Research Assignment Problems Mathematical Formulation Assignment Problem n
of
n
Minimize the total cost z = ∑ ∑ cij xij i=1,2,..n,j=1,2,..n i =1
j =1
Subject to restrictions of the form xij =
1 if ith person is assigned jth job 0 if not
n
∑x
=1
ij
j =1
n
∑x
ij
=1
(one job is done by ith person, i-1,2,..,n) (one person should be assigned jth job, j=1,2,…n)
i =1
Remember that size of the assignment table is n by n which is balanced. For unbalanced problems, we will adopt similar action as in TP, we will discuss later here.
Operations Research Assignment Problems Solution of Assignment problems Given a table of size n X n (balanced) (i)Simple method of single zero assignments first row wise then column wise or vice versa a.Find the row having only single zero. Other zeros in that row are either assigned or crossed. Mark this zero as assigned, cut all other zeros in the column of that row assignment. b.Complete all rows in manner as given a c.When all row assignments have been made, repeat the process for column assignment. Here cross all zeros of the row where column assignment has been made d.Complete all columns in manner as given a e.Check if each row and each column has one and only assignment f.Note the position of each assignment and sum the original costs at these locations. This will give the minimum cost. g.If any row or column still has one or more zeros left unassigned or uncrossed then above method will not be applicable. Then apply minimum lines drawing method as explained in classroom with many examples.
Operations Research Assignment Problems Solution of Assignment problems Given a table of size n X m (unbalanced) First check if rows m < columns n, then add additional rows with all zero values to make m=n If columns n < rows n, then add additional column with all zero values to make m=n The problem now becomes balanced Apply the same procedure explained before to solve this balanced problem Try to solve as many exercises as possible of both types Contact in case of any doubt, problem.
Operations Research Assignment Problems Travelling Salesman Problem A salesman has to visit n cities to sell/promote the sale of product of his company. The cities are connected in the form of a network. Now the salesman has to plan his visit in such a manner that he visits all n cities only once. He does not have to re-visit a city or if necessary then minimum times he re-visits a city. The total distance or the time occurred in visiting all n cities should be minimum.
Operations Research Replacement Problems Basics We know that almost every object needs replacement after a certain period. We go on repairing our vehicle again and again but after a time, repair becomes more expensive than to buy a new vehicle. Due to following factors replacement becomes necessary a.The old item has become worse, works badly or requires expensive maintenance for its operation or running. b.Old item has failed due to accident or otherwise and can not work. c.A better or more efficient item has come in the market. The question is to take a decision whether to continue with the old item or buy a new one (i.e. replace old item). More important question or the main question of replacement problem is to decide when to replace old item? Two types of replacement problems will be mainly dealt here i.When the cost value, scrap value, operational costs etc are given and to find out the time when to replace existing item. There is no increase or decrease in the value of money. The cost of a machine is Rs 40000/ today will remain same even after 10 years on today. ii.When the cost value, scrap value, operational costs etc are given and to find out the time when to replace existing item. There is an increase or decrease in the value of money. The cost of a machine is Rs 40000/ today will becomes 20% after every passing years as seen on today. Both types of problems have been explained with examples in class. Students are advised to contact in case of any doubt or problem.
Operations Research Project Management CPM/PERT Basics Please elaborate the following A project is defined as a combination of activities which must be executed in such a manner or order before the whole project or task can be completed. Steps in Project CPM/PERT techniques 1.Planning: Divide the main project into small projects which will further be divided into small activities. 2.Scheduling: Prepare a time table to show start and finish of every activity. 3.Allocation of resources: To allocate a physical resource like equipment, money, space to project. 4.Controlling : The overall activities must be controlled so that the project may complete in time. Also find out critical path. We have discussed in class room various networks, find out Earliest time, Latest time, critical path, float, slack time. Do other exercises and contact in case of doubt/problem.
Operations Research Project Management CPM/PERT Network understanding In the following network diagram A,B,.. Are activities. The numbers A(30), etc. are the time to complete the activity A etc. Nodes are circled as 1,2,..11 to show events. Dummy activities are the activities to join two other events but with zero time, i.e. dummy activities have no physical meaning just dotted lines to connect two other events like 7-8 are connected by dotted line dummy. We have already discussed in class to find earliest time, latest time to start an activity, floats and slacks. So do more exercises.
