TYBMS SEM 6 Operation Research : Write a short Notes (Important Questions)

 TYBMS SEM 6 

Operation Research 

Write a short Notes 

(20 Important Questions) 

(i) Feasible region solution in LPP graphical method.

Ans:  In Linear Programming Problems (LPPs), the feasible region represents the set of all feasible solutions that satisfy the constraints of the problem. When using the graphical method to solve LPPs, the feasible region is visually represented by the area in the graph where all constraints are simultaneously satisfied.

The feasible region is determined in the graphical method:

1. Plot Constraints: Each constraint in the LPP is represented as a linear inequality on the graph. For example, if the constraint is \(ax + by \leq c\), then it represents a line on the graph. If it is an equality, then it represents a boundary line, and if it is an inequality, it represents a boundary line and a half-plane.

2. Identify Feasible Region: The feasible region is the intersection of all half-planes formed by the constraints. It is the region of the graph where all constraints are satisfied simultaneously. This region is typically bounded by the constraint lines or may extend to infinity if the problem is unbounded.

3. Determine Feasible Solutions: Any point within the feasible region represents a feasible solution to the LPP. These solutions satisfy all the constraints of the problem. The objective is to find the optimal solution within this feasible region that maximizes or minimizes the objective function.

4. Optimal Solution: Once the feasible region is identified, the optimal solution is determined by evaluating the objective function at various points within the feasible region. The point that maximizes or minimizes the objective function while lying within the feasible region is considered the optimal solution.

(ii) Basis and non-basis variable in simplex table

Ans: 

In the simplex method, which is an algorithm for solving linear programming problems, the terms "basis" and "non-basis" variables are used to describe the variables involved in the current solution of the linear program. 

1. Basis Variables: Basis variables are those variables that are explicitly set to non-zero values in the current feasible solution. These variables correspond to the basic feasible solution, which is a solution where a subset of the variables is set to non-zero values, while the rest are set to zero. The number of basis variables is equal to the number of constraints in the linear programming problem. The values of basis variables are determined by solving a system of linear equations derived from the constraints.

2. Non-Basis Variables: Non-basis variables are those variables that are not explicitly set to non-zero values in the current feasible solution. These variables correspond to the non-basic variables, which are usually set to zero in the current solution. Non-basis variables are typically represented as variables that can potentially enter the basis to improve the objective function value. During each iteration of the simplex method, a non-basis variable may become a basis variable by entering the basis, while an existing basis variable may exit the basis and become a non-basis variable.

In the simplex table, basis variables are usually represented as columns, while non-basis variables are represented as rows. The table contains coefficients representing the contributions of each variable to the objective function and the constraints. The simplex method iteratively modifies this table to improve the objective function value until an optimal solution is found.

Understanding basis and non-basis variables is crucial for implementing the simplex method and solving linear programming problems efficiently. By iteratively adjusting the basis and non-basis variables, the simplex method converges to the optimal solution of the linear programming problem.

(iii) Three-time estimates in PERT

Ans: In Program Evaluation and Review Technique (PERT), three time estimates are utilized to estimate the duration of activities within a project. These estimates help in predicting the most likely duration for completing each activity. The three time estimates are:

1. Optimistic Time (a): This is the shortest possible time that an activity can be completed in under ideal conditions. It assumes that everything proceeds as smoothly as possible without any delays or obstacles. The optimistic time estimate represents the best-case scenario.

2. Most Likely Time (M): This estimate represents the duration that the activity is most likely to take under normal circumstances. It considers typical factors such as resources, skills, and potential obstacles that may arise during the activity's execution.

3. Pessimistic Time (b): The pessimistic time estimate reflects the longest duration that an activity might take if everything goes wrong or if unexpected problems occur. It considers worst-case scenarios, such as resource shortages, technical difficulties, or unforeseen delays.

These three time estimates are used to calculate the Expected Time (TE) for each activity using the formula:

T_e = a + 4m + b / 6

Once the Expected Time for each activity is determined, it is used in conjunction with the project network diagram to calculate the overall project duration and identify the critical path—the sequence of activities with the longest total duration, which determines the minimum time required to complete the project.

(iv) Project crashing

Ans:  In that case, the critical path will have to be shortened or reduced. This can be done by reducing completion time of some or all of the critical activities. To achieve this, we will need to employ extra resources. This process of shortening the critical path to achieve earlier completion of the project is called project crashing.

(v) Objectives of critical path

Ans: The critical path method (CPM) is a project management technique used to identify the sequence of tasks that determine the minimum duration required to complete a project. The critical path represents the longest path through a project network diagram and determines the shortest possible project duration. The primary objectives of identifying and analyzing the critical path include:

1. Determining Project Duration: By identifying the critical path, project managers can determine the shortest possible duration required to complete the project. This information is crucial for planning and scheduling resources effectively.

2. Resource Allocation: Understanding the critical path helps in allocating resources efficiently. Tasks on the critical path cannot be delayed without extending the project's overall duration. Thus, it is essential to ensure that sufficient resources are allocated to critical tasks to prevent delays in the project timeline.

3. Task Prioritization: Tasks on the critical path are critical to the project's success. Therefore, they require special attention and priority in terms of monitoring, management, and resource allocation. By identifying the critical path, project managers can focus their efforts on managing these critical tasks to keep the project on track.

4. Risk Management: The critical path highlights tasks that are most susceptible to delays. By focusing on these critical tasks, project managers can proactively identify potential risks and develop strategies to mitigate them. This helps in minimizing the likelihood of delays and ensuring successful project completion.

5. Schedule Compression: Knowing the critical path allows project managers to identify opportunities for schedule compression. By focusing on critical tasks or adding resources to critical activities, project managers can accelerate the project timeline without affecting its overall duration. 

(Vi) Northwest Corner Method (NWCM)

 

(vii) limitation of operation research techniques

Ans:  Quantitative techniques can be classified in two groups, statistical techniques and programming techniques.

(A) Statistical techniques: Statistical techniques are applied in Statistics for data collection, data organization and data analysis. Some of the examples are:

(1) Mean, median and mode

(2) Mean deviation and standard deviation

(3) Probability theory

(4) Regression analysis and correlation analysis

(5) Sampling

(6) Statistical quality control

(B) Programming techniques: These are OR techniques. These techniques involve problem formulation, building mathematical models, substituting data in mathematical models, testing the model, using appropriate OR technique to solve the problem, obtaining optimal solution. Some examples are:

(1) Linear programming.

(2) Transportation problems.

(3) Assignment problems.

(4) Critical path method.

(5) Decision theory.

(6) Inventory management.

Some of the major limitations of OR techniques are:

(1) In construction of mathematical models, sometimes assumptions are necessary to simplify model construction. But over- simplification of a model or too many assumptions can make the model unrealistic.

(2) OR techniques are quantitative in nature. Hence, these techniques do not consider qualitative or intangible factors such as customer perceptions, employee motivation levels, quality of executives, advantage of experience etc.

(3) All business situations cannot be responded with quantitative techniques. Some business situations require gut feeling, initiative or managerial judgement. OR techniques cannot be applied in such situations. 

(Viii) Interfering float/ Total Float/ Interdepend Float/ Free Float

These are terms related to project management, specifically in the context of Critical Path Method (CPM) scheduling. Each term represents a different type of scheduling flexibility for tasks in a project. Here's an explanation of each:

1. Total Float

Definition: Total Float is the amount of time a task can be delayed without delaying the project’s completion date or violating a project constraint.
Formula:
$\text{Total Float} = \text{Late Start (LS)} - \text{Early Start (ES)}$
or
$\text{Total Float} = \text{Late Finish (LF)} - \text{Early Finish (EF)}$
Key Points:

• It reflects the overall scheduling flexibility of a task.
• A task on the critical path has a Total Float of zero.

2. Free Float

Definition: Free Float is the amount of time a task can be delayed without affecting the Early Start of its successor tasks.
Formula:
$\text{Free Float} = \text{Earliest Start (ES) of Next Task} - \text{Earliest Finish (EF) of Current Task}$
Key Points:

• Free Float is always equal to or less than Total Float.
• It measures flexibility within local task relationships.

3. Interfering Float

Definition: Interfering Float is the portion of Total Float that, if used, would delay the Early Start of successor tasks but not the project completion.
Formula:
$\text{Interfering Float} = \text{Total Float} - \text{Free Float}$
Key Points:

• It shows how much float can "interfere" with downstream tasks.
• Highlights potential conflicts with dependent tasks.

4. Independent Float

Definition: Independent Float is the amount of time a task can be delayed without affecting the Early Start of successor tasks or being delayed by the Late Finish of predecessor tasks.
Formula:
$\text{Independent Float} = \max(0, \text{Earliest Start of Successor} - \text{Latest Finish of Predecessor} - \text{Duration})$
Key Points:

• It reflects the flexibility a task has independently of its surrounding tasks.
• Independent Float is often less than or equal to Free Float.

 

(ix)  Dummy activity and its use in network analysis

 Ans: DUMMY ACTIVITY:

A Dummy activity does not consume any time or resources. It is represented by a dotted line. The purpose of Dummy activity is to represent logical relationship of dependency.

Dummy activity is required in following cases: (a) Two activities are performed concurrently and a third activity depends on both of these activities. 

(b) Two concurrent activities which need to be connected to correctly represent the precedence relationship of succeeding activities. 

X) Principles of Dominance

Ans: Principles of Dominance are used for reducing the game matrix of a two person zero-sum game, if the game matrix contains large number of strategies.

Principles:

(1) Rules for Rows: If All the elements in a Row are less than or equal to the corresponding elements in another Row, then this Row is said to be dominated by the another Row and can be eliminated from the game matrix to reduce the order of the matrix.

(2) Rules for Columns: If All the elements in a Column are greater than or equal to the corresponding elements in another Column, then this Column is said to be dominated by the another Column and can be eliminated from the game matrix to reduce the order of the matrix.

(Xi) Assumptions in Job Sequencing

Ans: PRINCIPAL ASSUMPTIONS:

(1) Each machine can perform only one type of operation and can undertake only one job at a time.

(2) Only one machine of each type is available. 

(3) All jobs require the same sequence of operations.

(a) In a two machines problem, each job is processed first on machine A and then on machine B.

(b) In a three machine problem, the sequence of operations is A, B,C.

(4) The processing times of all jobs on all machines are known and remain constant.

(5) Each job must be completed before another job is taken up for processing.

(6) No job is required more urgently than the other. 

(7) Transit time to move a job from one machine to another is negligible.

Xii) Assumptions in LPP

Ans: 

(1) Available quantities of resources and consumption per unit from resources is known exactly and with certainty.

(2) Production of finished products is possible in any fractions, so is consumption of resources.

(3) All external factors are constant.

(4) The problem involves only one major objective.

Xiii) Degeneracy in Transportation

Ans: DEGENERACY IN TRANSPORTATION:

Degeneracy occurs when in a Transportation table, number of allocations are less than [number of rows + number of columns - 1].

It means the rim condition is not satisfied.

Rim Condition:

Number of allocations should be equal to [m + n - 1] . Where,

m = Number of Rows.

n = Number of Columns.

If a transportation solution is degenerate, i.e., having degeneracy then we cannot calculate values of u and v'.

Hence, the solution cannot be tested for optimally (A cannot be calculated).

To remove degeneracy, we add an imaginary entry called Epsilon (e) in the solution.

Epsilon is a zero value allocation Its only purpose is to facilitate calculation of 'u and v'

Where to place Epsilon (e): Epsilon is placed in an independent position i.e., a position where it does not form a closed loop with other allocations.

This kind of looping between the allocations and Epsilon should not take place.

Xiv) Distinguished between PERT and CPM. 

CPM	PERT
In CPM there is only one time given for each activity.	In the PERT there are three time estimates. Optimistic time, Most likely time and Pessimistic time. From these, we find Expected time for completion of an activity (te)
After drawing the network we find critical path, which gives us project completion time.	We draw the network using Expected time (te) and then we find critical path, which gives us expected project completion time
There is no probability information in CPM	Probability is associated with Project completion time (Te). The probability of completing the project in that duration is 50% (0.5). In other words, the probability that the project will be completed in expected project completion time is 50%.
There is no standard deviation and variance for activities. We assume that all activities will be completed in specified time.	We find standard deviation and variance of critical activities and from that we find variance and standard deviation of the critical path.
As there is no probability, there is no relation with normal distribution table	We can find "z" value and from "z" value the probability of completing the project in specified time duration.

xv) Discuss the signification of theory of game. Briefly discuss the terms. Player and pay off.

 Ans: 

Every one business party. The situation (also called competitive situation) involves more parties involved could be corporate. individuals, small firms or A number of outcome alternatives are available to each party for decision making. The (i.e. profit or loss) of the business decision does not depend on the alternative selected by one party alone, but on the interaction between the decisions of all the parties involved in the situation. Each party will try to select the alternative which maximizes gains for it, at the cost of its competitors. "Games Theory" deals with such business situations or problems where multiple parties are involved in the conflict through interaction of their alternatives or decisions.

Players: The various participants or decision markers in the game are called "Players". A game must have minimum two players (or competitors). A game having two competitors opposing each other is called 'two person game' and a game having more than 2 players is called 'n-person game'.

Payoff: Payoff is the outcome of the interaction of selected strategies of opponents in the game. Positive payoff is gain and negative payoff is loss. In a 'two person game', when one party gains, the other party loses.

xvi) Redundant constraints and infeasible solution in linear programming. 

 Ans: A redundant constraint is the one which does not affect the optimal solution. Even if that constraint is not considered, we can still obtain the solution to the problem. Since the constraint is not required for obtaining the optimal solution, it is called redundant constraint cost.

Following sketch explains redundancy (redundant constraint):

There is no common feasible region for line AB and line CD

Hence, solution is infeasible.

A redundarnt constraint is the one which does not affect the optimal solution. Even if that constraint is not considered, we can still obtain the solution to the problem. Since the constraint is not required for obtaining the optimal solution, it is called redundant constraint. cost.

Following sketch explains redundancy (redundant constraint):

The feasible region for the above problem is OABC. The 3rd constraint does not affect the feasible region. Hence, the constraint [X1 S 16] is redundant constraint.

xvii) Discuss any 5 areas where techniques of operation Research can be applied

Ans:

OR techniques are applied to a variety of business problems. Some examples are:

(A) Production management:

(1) To calculate loss of time due to waiting time, queuing time etc.

(2) To decide optimum allocation of jobs and optimum sequence in which jobs should be sequenced.

(B) Personnel management:

(1) To study labour turnover. (2) To do human resource planning. (3) To decide number of personnel required to be kept on standby in case of demand for higher manpower.

(C) Inventory management: (1) To study economic lot size to be ordered.

(D) Marketing management: (1) To decide optimal product mix for maximum profit. (2) Media selection for advertising for maximum reach. (3) Sales forecasting.

(E) Transportation management: (1) To determine transportation schedule for minimum cost or minimum time.

(F) Project management (1) To identify critical and non-critical activities of a project (2) To determine minimum project completion time. (3) To determine optimal project cost.

(G) Financial management: project. (1) To decide investment portfolio to maximize return on investment. of such nature that it is impossible to find a feasible solution that can satis1y a the constraints.

xviii) LCM Least Cost Method or VAM

 Ans: The Least Cost Method and Vogel's Approximation Method (VAM) are both techniques used in solving transportation problems, a type of optimization problem commonly encountered in logistics and supply chain management.

1. Least Cost Method: This method is a straightforward approach to allocating goods from multiple sources to multiple destinations while minimizing total transportation cost. The steps involved are:

   - Start with the cell having the lowest cost and allocate as much as possible without violating the supply and demand constraints.

   - Once a cell is filled, either the corresponding row or column gets eliminated, depending on whether the supply or demand of that source or destination is exhausted.

   - Repeat the process until all supplies are exhausted or all demands are met.

2. Vogel's Approximation Method (VAM): This method is a more sophisticated approach that takes into account not only the cost but also the differences in costs between different routes. The steps involved are:

   - Calculate the penalty for each row and column by finding the difference between the two lowest costs in each.

   - Select the row or column with the highest penalty and allocate as much as possible to the cell with the lowest cost within that row or column.

   - Update the penalties and repeat the process until all supplies are exhausted or all demands are met.

While the Least Cost Method is simpler and easier to understand, Vogel's Approximation Method often yields better solutions, especially when there are significant differences in transportation costs between different routes. However, Vogel's method is more computationally intensive. The choice between the two methods depends on the specific characteristics of the transportation problem at hand and the computational resources available.

xix) what is meant by expected time of an activity in PERT? How is it calculated? 

Ans: Concepts of 'Expected time (te)'

When we combine the value pf optimistic time (a), most likely time (m) and pessimistic time (b) in a statistical manner, we can arrive at the expected time of activity (te).

'a' and 'b' are assumed to be end points of the beta distribution. 'm' is the mode i.e. the time value with maximum frequency. The expected time divides the curve in two equal areas. If the total area Inder the curve is 100%, then area to the left and right of te is 50% each. 

Hence, we can say that the probability that an activity will be completed in 'te' time is 50%

Derivation of formula for Expected time (te):

The distribution based on a, b, m is skewed to the right i.e. positively skewed.

The expected time (te) divides the area under the curve in two equal parts. It means there is 50% chance that the activity will be completed in time te.

Midpoint of 'a' and b' = (a + b)/2

Distance between 'm' and midpoint of 'a' and b' = (a + b)/2 - m

Distance between origin and location of prime 'te' = m + 1/3 * [(a + b)/2 - m]

    te = m + (a + b)/6 - m/3 

        = (6m + a + b - 2m)/6 

therefore te = (a + 4m + b)/6

XX) Assignment Problem v/s transportation Problem 

Ans.: Following are the points of difference:

Assignment Problem	Transportation Problem
(1) It is a problem of finding optimal allocation of two variables, such as workers & jobs.	(1) It is the problem of finding optimal transportation schedule from Supply centres to Demand centres.
(2) Method of solution is Hungarian method.	(2) To find Initial Feasible solution, we use VAM, LCM or NWCR. To find optimal solution, we use MODI (Modified Distribution method).
(3) The problem is unbalanced when number of rows is not equal to number of columns.	(3)The problem is unbalanced when total supply is not equal to total demand.