TYBMS SEM 6 : Operation Research (Q.P. April 2025 with Solution)

  Paper/ Subject Code 86001/ Operation Research

TYBMS SEM 6 :

Operation Research 

(Q.P. April 2025 with Solution)

_____________________________

Important Write a short Notes

1) April 2019 Q.P. with Solution (PDF) 

2) November 2019 Q.P. with Solution (PDF)

3) November 2022 Q.P. with Solution (PDF)

4) April 2023 Q.P. with Solution (PDF)

5) April 2024 Q.P. with Solution (PDF)

____________________________________

Please check whether you have got the right question paper.

Note:

1. All questions are compulsory. (Subject to Internal Choice)

2. Figures to the right indicate full marks

3. Use of non-programmable calculator is allowed and mobile phones are not allowed.

4. Normal distribution table is printed on the last page for reference. Support your answers with diagrams / illustrations, wherever necessary

6. Graph papers will be supplied on request.

______________________________________

Q1 A) State whether following Statements are True or False (Any Eight):        (08)

1. Linear Programming Problems consist of decision variables, an objective function, and constraints.

Ans: True

2. In the Graphical Method of Linear Programming, the feasible region is always a polygon.

Ans: True

3. The Assignment Problem can have multiple optimal solutions.

Ans: True

4. In a balanced transportation problem, the total supply must be equal to the total demand.

Ans: True

5. Dummy activities are used in network diagrams to maintain logical dependencies

Ans: True

6. The Program Evaluation and Review Technique (PERT) considers three time estimates for activity duration.

Ans: True

7. Crashing a project reduces both time and cost simultaneously.

Ans: False

8. In job sequencing, idle time refers to the time a machine remains unutilized.

Ans: True

9. A two-person zero-sum game means that one player's gain is exactly equal to the other player's loss.

Ans: True

10. In the Simplex Method, slack variables are introduced to convert inequalities into equations. 

Ans: True

QI B) Match the Column Questions: (Any SEVEN)                (07)

Column A	Column B
1. Feasible Region	a) Method to solve transportation problems
2. Redundant Constraint	b) Project scheduling technique
3. Decision Variables	c) Represents unused or excessive restrictions in LPP
4. Unbounded Solution	d) Graphical area satisfying all constraints in LPP
5. Duality in Linear Programming	e) Used in Linear Programming Formulation
6. MODI Method	f) When there is no finite optimal solution
7. Slack Variable	g) Difference between primal and dual problems
8. Network Diagram	h) Extra variable added to convert "<" constraint into equality
9. Zero-Sum Game	i) One player's gain is equal to the other player's loss
10. Least Cost Method (LCM)	j) Heuristic approach for transportation problems

Ans:

Column A	Column B
1. Feasible Region	d) Graphical area satisfying all constraints in LPP
2. Redundant Constraint	c) Represents unused or excessive restrictions in LPP
3. Decision Variables	e) Used in Linear Programming Formulation
4. Unbounded Solution	f) When there is no finite optimal solution
5. Duality in Linear Programming	g) Difference between primal and dual problems
6. MODI Method	a) Method to solve transportation problems
7. Slack Variable	h) Extra variable added to convert "<" constraint into equality
8. Network Diagram	b) Project scheduling technique
9. Zero-Sum Game	i) One player's gain is equal to the other player's loss
10. Least Cost Method (LCM)	j) Heuristic approach for transportation problems

Q2 A) Vitamins B1 and B2 are found in two foods F1 and F2. 1 unit of F1 contains 3 units of B1 and  4 units of B2. 1 unit of F2 contains 5 units of B1 and 3 units of B2. The minimum daily prescribed consumption of B1 & B2 is 50 and 60 units, respectively. The cost per unit of F1 & F2 is Rs.6 & Rs.3, respectively.                                                                    08

Formulate as LPP (Linear Programming Problem).

Solution

Q2 B) Solve the following Linear Programming problem by simplex method.    07

Max. Z = 3X₁ + 5X2

Subject to the constraints:

X₁ + X₃ = 4

X₂ + X4 =  6

3X₁ + 2X2 + X3  = 12

X₁, X₂ X₃, X4, X₅  ≥ 0

Does degeneracy occur in this problem?

Solution

OR

Q2 C) During the modification of a factory layout at BMS Auto Parts, four newly acquired machines-M1, M2, M3, and M4-need to be installed in a machine shop. The shop has five available locations: A, B, C, D, and E, which are suitable for installation.

However, due to size constraints:

M1 cannot be placed at C, and

M3 cannot be placed at A.

The installation cost (in hundreds of rupees) for each machine at different locations is given in the following table

Find the optimal assignment that minimizes the total installation cost.                (07)

Solution

Q2 D) Solve the following LPP by the graphical Method

Maximize Z = 50X₁ + 20X2

Subject to Constraints 

X₁ + X₂ ≤  600 

X₁ + X₂ ≥ 300

6X₁ + 2X₂ ≥ 1200

X₁, X₂ ≥ 0

Solution

Q3 A) For a project, different activities along with time and cost estimates are given below:

Indirect cost is Rs. 100 per day.

(a) Construct the project network and identify the critical path. What is the normal duration and corresponding total cost of the project?

(b) Systematically Crash the project and find the minimum cost and optimal time. Also, find out the additional costs required to reach the optimal time. 

(c) Find the total cost required to reach the minimum time.

Q3 B) A company is transporting its units from three factories F1, F2 and F3 to four warehouses W1, W2, W3, and W4. The transportation cost per unit (in Rs.), along supply and demand details, is provided below. The total demand for warehouses is as follows: W1 400 units W2: 500 units W3 700 units W4: 800 units. The total supply available from the factories is: F1: 800 units F2: 600 units F3: 1000 units A feasible solution, including allocations and unit cost data, is presented in the table below.

(i) Test the given solution for optimality using the Modified Distribution Method (MODI Method). 

(ii) If the solution is not optimal, modify it to obtain the best possible solution.

(iii) Determine the minimum transportation cost.

OR

Q3 C) M/s Motwani Limited have taken up a special project consisting of 10 activities whose three point time estimates are listed in the table below. Activities are marked with their node numbers. 

(a) Draw network diagram and find expected completion time of project.

(b) Identity critical path.

(c) Find the probability that the project is completed in 17 weeks.

(d) What is the probability that the project will not be completed in 20 weeks?

(e) If the project includes a penalty clause of Rs.1,000 per week for any delay beyond 19 weeks. What is the probability of paying a penalty of more than Rs. 5,000. 

Q.4 a)Six jobs P, Q, R, S, T, and U are to be processed on two machines M and N in the order MN. The processing time (in minutes) for each job on the respective machines is given below:    08

a) The optimal sequence of jobs to minimize total elapsed time.

b) The total elapsed time.

c) Idle time for each machine.

Q4 B) Alpha Corp (Firm A) and Beta Ltd (Firm B) are two competing firms in a market. Each firm has three possible strategic choices to maximize their payoffs. The following payoff matrix represents the outcomes for Alpha Corp based on the strategic interactions with Beta Ltd.

Find:

1. Identify the optimal maximin strategy for Alpha Corp.

2. Determine the optimal minimax strategy for Beta Ltd.

3. Compute the value of the game and check if a saddle point exists

OR

Q.4 C) A company has 3 plants P1, P2 and P3. It supplies to 4 warehouses W1, W2, W3 and W4. Cost per unit and demand-supply data is as given below. Find the Initial Feasible Solution (IFS) using the Least Cost Method (LCM).

Q4 D) Six jobs G, H, I, J, K, L are to be processed on three machines A, B, C in the order A→B 07 →C. The processing times (in hours) are:

Find:

1. The optimal job sequence that minimizes total elapsed time.

2. The total elapsed time.

3. Idle time on Machine A, Machine B, and Machine C.

Q5 A) Explain Forward pass and Backward Pass calculation of Network Analysis

Forward Pass

The forward pass is a calculation performed to determine the earliest possible start and finish times for each activity in a project network. It begins at the start node and progresses through the network to the end node. The forward pass helps establish the earliest time an activity can begin and the earliest the project can be completed.

Steps in the Forward Pass

1. Start Node: Assign an earliest start time (ES) of 0 to the first activity (or activities) in the network.

2. Calculate Earliest Finish Time (EF): For each activity, calculate the earliest finish time by adding the activity's duration (tij) to its earliest start time:    EF = ES + tij

3. Determine Earliest Start Time for Successors: For each activity, the earliest start time of its successor(s) is equal to the earliest finish time of the predecessor activity. If an activity has multiple predecessors, its earliest start time is the maximum of the earliest finish times of all its predecessors.

4. Repeat: Repeat steps 2 and 3 for all activities in the network, moving from left to right (or from start to finish).

5. Project Completion Time: The earliest finish time of the last activity (or activities) in the network represents the earliest possible completion time for the entire project.

Backward Pass

The backward pass is a calculation performed to determine the latest possible start and finish times for each activity in a project network without delaying the project's overall completion. It begins at the end node and progresses backward through the network to the start node. The backward pass helps identify how much slack or float each activity has.

Steps in the Backward Pass

1. End Node: Assign a latest finish time (LF) to the last activity (or activities) in the network. This is typically equal to the earliest finish time of the project determined in the forward pass. If a project deadline is specified, the LF can be set to that deadline.

2. Calculate Latest Start Time (LS): For each activity, calculate the latest start time by subtracting the activity's duration (tij) from its latest finish time: LS = LF + tij

3. Determine Latest Finish Time for Predecessors: For each activity, the latest finish time of its predecessor(s) is equal to the latest start time of the successor activity. If an activity has multiple successors, its latest finish time is the minimum of the latest start times of all its successors.

4. Repeat: Repeat steps 2 and 3 for all activities in the network, moving from right to left (or from finish to start).

5. Start Node: The latest start time of the first activity (or activities) should ideally be 0. If it is not 0, it indicates that the project cannot be completed by the target date (if the LF of the end node was set to a specific deadline).

Q5 B) Explain Different techniques of Operation Research.

Linear Programming

Linear programming (LP) is a mathematical technique for optimizing a linear objective function, subject to linear equality and inequality constraints. It's a cornerstone of OR, widely used for resource allocation, production planning, and scheduling.

Concepts:

• Objective Function: A mathematical expression that represents the quantity to be maximized or minimized (e.g., profit, cost).

• Decision Variables: Variables that represent the quantities to be determined (e.g., number of units to produce).

• Constraints: Linear equations or inequalities that restrict the values of the decision variables (e.g., resource limitations, demand requirements).

• Feasible Region: The set of all possible solutions that satisfy all the constraints.

• Optimal Solution: The feasible solution that yields the best value for the objective function.

Methods for Solving LP Problems:

• Graphical Method: Suitable for problems with two decision variables, involving plotting the constraints and identifying the feasible region.

• Simplex Method: An iterative algebraic procedure for solving LP problems with any number of variables and constraints. It systematically explores the vertices of the feasible region to find the optimal solution.

• Software Packages: Specialized software like Gurobi, CPLEX, and open-source solvers like PuLP and SciPy are used to solve large-scale LP problems efficiently.

Applications:

• Production Planning: Determining the optimal production levels for different products to maximize profit while considering resource constraints.

• Transportation: Finding the most cost-effective way to transport goods from multiple sources to multiple destinations.

• Blending: Determining the optimal mix of ingredients to meet specific quality requirements at the lowest cost.

• Financial Portfolio Optimization: Allocating investments across different assets to maximize returns while managing risk.

Network Analysis

Network analysis involves the study of networks, which are collections of nodes (or vertices) connected by edges (or arcs). It provides tools for analyzing and optimizing flows, paths, and connections within networks.

Concepts:

• Nodes: Represent locations, facilities, or entities in the network.

• Edges: Represent connections or relationships between nodes.

• Flow: The movement of goods, information, or people through the network.

• Capacity: The maximum amount of flow that can pass through an edge.

• Path: A sequence of nodes and edges connecting two nodes.

• Distance: The length or cost associated with an edge.

Common Network Optimization Problems:

• Shortest Path Problem: Finding the shortest path between two nodes in a network.

• Maximum Flow Problem: Finding the maximum amount of flow that can be sent from a source node to a sink node in a network.

• Minimum Spanning Tree Problem: Finding a set of edges that connects all nodes in a network with the minimum total cost.

• Transportation Problem: Finding the optimal way to transport goods from multiple sources to multiple destinations.

Applications:

• Transportation: Optimizing delivery routes, designing transportation networks, and managing traffic flow.

• Telecommunications: Designing communication networks, routing data packets, and managing network capacity.

• Supply Chain Management: Optimizing the flow of goods and materials through the supply chain.

• Project Management: Scheduling project activities and allocating resources.

OR

Q5 C) Write Short Notes (ANY THREE):                (15)

1. Vogel's Approximation Method (VAM) in Transportation Problems

Vogel's Approximation Method (VAM) is a heuristic algorithm used to find an initial feasible solution to the transportation problem. It is generally considered to be more efficient than other methods like the Northwest Corner Rule or the Least Cost Method, as it often provides a starting solution that is closer to the optimal solution.

Steps Involved in VAM

The VAM algorithm involves the following steps:

1. Calculate Penalties: For each row and each column in the transportation table, calculate the penalty by subtracting the smallest cost from the next smallest cost in that row or column. These penalties represent the opportunity cost of not assigning a unit to the cell with the lowest cost in that row or column.

2. Identify the Row or Column with the Largest Penalty: Select the row or column with the largest penalty. If there is a tie, choose arbitrarily.

3. Allocate as Much as Possible to the Cell with the Lowest Cost in the Selected Row or Column: In the selected row or column, identify the cell with the lowest cost. Allocate as much as possible to this cell, subject to the supply and demand constraints. This means allocating the minimum of the supply available at the origin and the demand required at the destination corresponding to that cell.

4. Adjust Supply and Demand: Reduce the supply of the origin and the demand of the destination by the amount allocated to the cell.

5. Eliminate Satisfied Rows or Columns: If the supply of an origin is exhausted or the demand of a destination is satisfied, eliminate the corresponding row or column from further consideration.

6. Recalculate Penalties (if necessary): If any rows or columns have been eliminated, recalculate the penalties for the remaining rows and columns.

7. Repeat Steps 2-6: Repeat steps 2 through 6 until all supply and demand are satisfied.

Advantages of VAM

• Better Initial Solution: VAM generally provides a better initial feasible solution compared to the Northwest Corner Rule and the Least Cost Method, leading to fewer iterations to reach the optimal solution.

• Easy to Understand and Implement: The algorithm is relatively simple to understand and implement, making it a practical choice for solving transportation problems.

• Considers Opportunity Costs: By considering the penalties, VAM takes into account the opportunity costs of not assigning units to the cells with the lowest costs, leading to a more efficient allocation.

Limitations of VAM

• Heuristic Method: VAM is a heuristic method, which means it does not guarantee the optimal solution. It only provides an initial feasible solution that needs to be further optimized using other techniques like the Stepping Stone Method or the MODI method.

• Ties in Penalties: When there are ties in penalties, the choice of the row or column to select is arbitrary, which can affect the quality of the initial solution.

• Degeneracy: VAM can sometimes lead to degenerate solutions, where the number of allocated cells is less than m + n - 1 (where m is the number of origins and n is the number of destinations). This requires special handling during the optimization phase.

2. North-West Corner Rule for Initial Feasible Solution

The North-West Corner Rule is a method used to compute a feasible solution of the transportation problem. The transportation problem is a special type of linear programming problem that deals with the distribution of goods from several sources to several destinations. The objective is typically to minimize the total transportation cost while satisfying both the supply limits at the sources and the demand requirements at the destinations.

The North-West Corner Rule is one of several methods used to find an initial feasible solution. Other methods include the Least Cost Method and Vogel's Approximation Method (VAM). While the North-West Corner Rule is easy to implement, it often results in a solution that is far from optimal, requiring further iterations to reach the best possible solution.

Here's a step-by-step guide on how to apply the North-West Corner Rule:

Step 1: Construct the Transportation Table

Create a table representing the transportation problem. The rows represent the sources (origins), and the columns represent the destinations. Each cell in the table represents the cost of transporting one unit from a specific source to a specific destination. Also, include the supply (capacity) of each source and the demand (requirement) of each destination.

Step 2: Start at the North-West Corner

Begin with the cell in the upper-left corner of the transportation table (the "north-west corner").

Step 3: Allocate as Much as Possible

Compare the supply of the source and the demand of the destination corresponding to the current cell. Allocate the smaller of the two values to the cell. This represents the amount transported from that source to that destination.

Step 4: Adjust Supply and Demand

• If the supply of the source is smaller than the demand of the destination, the source's supply is exhausted. Subtract the allocated amount from the destination's demand. Move to the next cell in the same column (downwards).

• If the demand of the destination is smaller than the supply of the source, the destination's demand is satisfied. Subtract the allocated amount from the source's supply. Move to the next cell in the same row (rightwards).

• If the supply and demand are equal, both the source's supply and the destination's demand are satisfied. Subtract the allocated amount from both. You can move either to the next cell in the same row or the next cell in the same column. To avoid degeneracy, allocate zero to one of the adjacent cells.

Step 5: Repeat

Repeat steps 3 and 4 until all supply and demand are satisfied. This means that all rows and columns have been exhausted.

Step 6: Calculate the Total Transportation Cost

Multiply the allocated amount in each cell by the corresponding transportation cost and sum up all these values to obtain the total transportation cost for the initial feasible solution.

3. Differences Between Balanced and Unbalanced Transportation Problems 

A transportation problem is a special type of linear programming problem that deals with the distribution of a single commodity from several sources (origins) to several destinations. The objective is usually to minimize the total transportation cost or maximize the total profit.

A balanced transportation problem is one where the total supply from all sources equals the total demand at all destinations. In other words, the available quantity of goods at the origins is exactly equal to the required quantity at the destinations.

An unbalanced transportation problem is one where the total supply from all sources is not equal to the total demand at all destinations. This means either the supply exceeds the demand (excess supply) or the demand exceeds the supply (shortage).

the main differences:

1. Total Supply vs. Total Demand

   • Balanced: The total supply equals the total demand.

   • Unbalanced: The total supply does not equal the total demand (either supply exceeds demand or demand exceeds supply).

2. Feasibility of Solution

   • Balanced: Since supply matches demand, a feasible solution always exists without needing adjustments.

   • Unbalanced: To make the problem solvable, dummy rows or columns are introduced to balance supply and demand.

3. Use of Dummy Variables

   • Balanced: No dummy source or destination is needed.

   • Unbalanced: A dummy source (if demand is higher) or dummy destination (if supply is higher) is added, usually with zero transportation cost.

4. Interpretation

   • Balanced: The problem reflects real supply and demand conditions directly.

   • Unbalanced: The dummy variables represent excess supply (unsold goods) or unmet demand.

5. Complexity

   • Balanced: Simpler to solve since no adjustments are required.

   • Unbalanced: Requires an initial balancing step before applying solution methods like the North-West Corner Rule, Vogel’s Approximation, or MODI method.

4. Concept of Free Float, Total Float, and Independent Float in CPM

Total Float (TF)

Total Float, also known as Slack, represents the amount of time an activity can be delayed without delaying the project completion date or violating any imposed schedule constraints. It indicates the maximum flexibility available for an activity.

Calculation:

Total Float (TF) can be calculated using the following formulas:

• TF = Late Start (LS) - Early Start (ES)

• TF = Late Finish (LF) - Early Finish (EF)

Where:

• ES = Early Start (The earliest possible time an activity can begin)

• EF = Early Finish (The earliest possible time an activity can be completed)

• LS = Late Start (The latest possible time an activity can begin without delaying the project)

• LF = Late Finish (The latest possible time an activity can be completed without delaying the project)

Free Float (FF)

Free Float represents the amount of time an activity can be delayed without delaying the Early Start of any immediately following (successor) activity. It indicates the flexibility available for an activity without impacting subsequent activities, assuming all preceding activities are completed as early as possible.

Calculation:

Free Float (FF) can be calculated using the following formula:

FF = ES (Successor) - EF (Predecessor)

Where:

• ES (Successor) = The Early Start of the immediately following activity.

• EF (Predecessor) = The Early Finish of the activity in question.

If an activity has multiple successors, the earliest ES of all successors is used in the calculation.

Independent Float (IF)

Independent Float represents the amount of time an activity can be delayed without delaying the Early Start of any successor activity, even if all preceding activities are completed as late as possible, and all succeeding activities start as early as possible. It is the most conservative measure of float.

Calculation:

Independent Float (IF) can be calculated using the following formula:

IF = ES (Successor) - LF (Predecessor) - Duration (Predecessor)

Which can be simplified to:

IF = ES (Successor) - LF (Predecessor) - (EF(Predecessor) - ES(Predecessor))

Where:

• ES (Successor) = The Early Start of the immediately following activity.

• LF (Predecessor) = The Late Finish of the activity in question.

• Duration (Predecessor) = The duration of the activity in question.

If the result of the calculation is negative, Independent Float is considered to be zero.

5. Saddle Point and Its Significance in Game Theory

In game theory, a saddle point represents an equilibrium in a two-player zero-sum game. It's a specific entry in the payoff matrix that is simultaneously the minimum value in its row and the maximum value in its column. This unique characteristic implies that neither player can improve their outcome by unilaterally changing their strategy, assuming the other player maintains their current strategy.

To identify a saddle point in a payoff matrix, follow these steps:

1. Find the Row Minimums: For each row in the payoff matrix, identify the smallest value. This represents the worst possible outcome for the row player (Player A) if the column player (Player B) knows their strategy.

2. Find the Column Maximums: For each column in the payoff matrix, identify the largest value. This represents the worst possible outcome for the column player (Player B) if the row player (Player A) knows their strategy.

3. Identify the Maximin and Minimax: The maximin value is the largest of the row minimums. This is the best of the worst-case scenarios for Player A. The minimax value is the smallest of the column maximums. This is the best of the worst-case scenarios for Player B.

4. Check for Equality: If the maximin value equals the minimax value, then the corresponding entry in the payoff matrix is a saddle point.

Significance of a Saddle Point

The existence of a saddle point in a game has significant implications for the optimal strategies of the players:

1. Optimal Pure Strategies: When a saddle point exists, both players have optimal pure strategies. Player A should choose the row corresponding to the saddle point, and Player B should choose the column corresponding to the saddle point. These strategies guarantee that each player achieves their best possible outcome, given the other player's strategy.

2. Value of the Game: The value of the game is the payoff at the saddle point. This represents the expected outcome of the game when both players play their optimal strategies. In the example above, the value of the game is 2.

3. Equilibrium: The saddle point represents a stable equilibrium. Neither player has an incentive to deviate from their optimal strategy because doing so would only worsen their outcome.

Elective: Operation Research (CBCGS)
Year	Month	Q.P.	Link
IMP Q.			Solution
Obj. Q			Solution
2019	April	Download	Solution
2019	November	Download	Solution
2022	November	Download	Solution
2023	April	Download	Solution
2023	November	Download	Solution
2024	April	Download	Solution
2024	November		Solution
2025	April	Download	Solution