**Pokhara UniversitySemester-FallLevel: Master Year: 2016Program: MCISFull Mark: 100Course: Operation research Pass Mark: 60Time: 4 hrs **

Candidates are required to given their answers in their own words as far as practicable.

1

**Formulate and solve it bye graphical method. (10)**

**2. Wild West produces two types of cowboy hats. **

**Formulate the problem as an LPP so as to maximize the profit and solve by simplex method. (10)**

**3.Write the dual of the primal (5)**

Max Z=2×1+3×2+4×3

Subject to constraints

X1-5×2+3×3=7

2×1-5×2 <=3 3×2-5×3>=5

X1,x2>=0 and x3 is unrestricted in sign.

**4. A company has received a contract to supply gravel for three new construction projects located in town A, B and C. Construction engineers have estimated the required amounts of gravel which will be needed at these construction project:**

Project location | Weekly requirement (truckloads) |

A | 72 |

B | 102 |

C | 41 |

The company has 3gravel pits located in town X, Y, Z.

The amount of gravel which can be supplied by each pit is as follows:

plant | X | Y | Z |

Amount available (truckloads) | 76 | 82 | 77 |

The company has computed the delivery cost from each pit to each project site. These costs (Rs.) are shown in following table:

Project location

A | B | C |

4 | 8 | 8 |

16 | 24 | 16 |

8 | 16 | 24 |

Also find minimum cost with optimality. (15)

5 .In the modification of a plant layout of a factory, four new machine M1,M2,M3, M4 are to be installed in a machine shop. There are five vacant places A,B,C,D, E available. Because of limited space machine M2 can’t be placed at C and M3 can’t be placed at A. The cost of locating a machine at place( in hundred rupees) as follows:

A | B | C | D | E | |

M1 | 9 | 11 | 15 | 10 | 11 |

M2 | 12 | 9 | – | 10 | 9 |

M3 | – | 11 | 14 | 11 | 7 |

M4 | 4 | 8 | 2 | 7 | 8 |

Find optimal assignment schedule. (5)

**6. Use the algorithm of Dijkstra to find the shortest route in the network between node 1 and any other node. (10)**

**7. A project consisting of 6 independent activities is to be analyzed by using PERT. The following information is given. (10)**

Activity | A | B | C | D | E | F |

Predecessor activity | – | – | A | B,C | D | A |

Optimistic time | 3 | 2 | 1 | 0 | 1 | 2 |

Pessimistic time | 5 | 2 | 5 | 14 | 3 | 10 |

Most likely time | 4 | 2 | 3 | 4 | 2 | 9 |

i.Draw the diagram of the network, and show the critical path.

ii.What is expect time to complete project?

iii.What is the probability that project will be completed in 20 weeks or less

**8. Maximize z=2×1+x2**

Subject to constraints

X1+x2<=6 ‘

X1+2×2<=10

X1,x2>0 solve the following LPP by matrix method in revised simplex algorithm (10)

**9.Solve the following all-integer linear programming problem by branch and bound method.**

Max Z=3×1+5×2

subject to constraints

2×1+4×2<=25

X1<=8

2×2<=10

X1 and x1 are non negative integer.

**Or**

What is dynamic programming? solve the bounding problem by recursive method of dynamic programming.