ASSIGNMENT-DEC 2024

SUBJECT :- OPERATION RESEARCHS

MCA – 204
By- Bhavna Tiwari

Q-1: Define Operations Research and its significance in decision making? What are the main components of a
typical OR model?
A-1
Operations research (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.

The process of operations research can be broadly broken down into the following steps:
1. Identifying a problem that needs to be solved.
2. Constructing a model around the problem that resembles the real world and variables.
3. Using the model to derive solutions to the problem.
4. Testing each solution on the model and analysing its success.
5. Implementing the solution to the actual problem.

Disciplines that are similar to, or overlap with, operations research include statistical analysis, management science, game
theory, optimization theory, artificial intelligence and network analysis. All of these techniques have the goal of solving
complex problems and improving quantitative decisions.
The concept of operations research arose during World War II by military planners. After the war, the techniques used in
their operations research were applied to addressing problems in business, the government and society.

Significance of Operations Research in Decision Making:

1.Improve efficiency: OR helps organizations identify the best course of action to maximize efficiency and effectiveness.
2.Solve complex problems: OR uses mathematical modelling, statistical analysis, and optimization techniques to solve
complex problems.
3.Enhance productivity: OR helps organizations navigate complexity and enhance productivity.
4.Improve outcomes: OR helps organizations achieve better outcomes in a wide range of operational and strategic
contexts.

Main components of a typical OR model:

1.Linear Programming (LP) Models

Linear Programming models are used to find the best outcome in a model with linear relationships, given a set of linear
constraints. They are particularly useful in optimizing resource allocation, maximizing profit, or minimizing cost.
Example: A manufacturing company wants to determine the optimal mix of products to produce within its resource
limitations. By using an LP model, the company can maximize its profit based on constraints like labor hours, material
costs, and production capacity.

2.Nonlinear Programming (NLP) Models

Nonlinear Programming models address problems where the relationship between variables is nonlinear. These models
are applied in situations where the change in output is not directly proportional to the change in input.
Example: In portfolio optimization, an investor aims to maximize the return on their investment portfolio while
minimizing risk. The relationship between risk and return is typically nonlinear, making NLP models suitable for finding
the optimal portfolio mix.

3.Integer Programming (IP) Models

Integer Programming models are used in scenarios requiring decision variables to be integers. These models are crucial
for planning, scheduling, and other problems where discrete decisions are made.
Example: A delivery company needs to decide on the number of trucks (an integer value) required for its operations to
minimize costs while meeting delivery demand. An IP model can solve this by determining the optimal number of trucks
that balances costs with service level requirements.

4.Dynamic Programming (DP) Models

Dynamic programming is used to solve multi-stage decision-making problems, where decisions at one stage affect future
stages. DP models break down a problem into simpler sub-problems and solve them sequentially.
Example: Consider the problem of inventory management over a planning horizon. A DP model can determine the
optimal quantity of stock to reorder at each period to minimize total costs, including ordering and holding costs, while
considering the inventory levels from previous periods.

5.Stochastic Models
Stochastic models are used in environments with uncertainty. They incorporate randomness and are useful for making
informed decisions under uncertainty by analysing different outcomes and their probabilities.
Example: In finance, stochastic models are used to price options. The Black-Scholes model, for example, evaluates an
option's price considering the stochastic nature of the underlying asset's price, volatility, and time to expiration.

6.Simulation Models
Simulation models mimic the operation of a real-world process or system over time. They are versatile and can
incorporate complexity and randomness, making them suitable for analyzing systems where analytical models are
impractical.
Example: In healthcare, simulation models can manage emergency department operations, simulating patient arrival
times, treatment processes, and staffing levels to improve patient flow and reduce waiting times.

---------------------------------------------------------------------------------------------------------------------------------------------------

Q-2: Define slack and surplus variables.

A-2
1.Slack variables
A slack variable is a variable that is added to a linear programming problem to replace an inequality constraint with an
equation. Slack variables are typically represented by the letter "s" and are always positive. Here are some examples of
slack variables:

If the constraint is 2x+3y≤30, then the slack variable 𝑠 satisfies the equation 2x+3y+s−30=0
Replacing an inequality with an equation

For example, if the first constraint is 4−2x1−x2−x3, then the slack variable 𝑥4 is defined as 14−2𝑥1−𝑥2−𝑥3
o Finding the difference between the left and right sides of a constraint

o Representing discontinuous derivatives

software. For example, the absolute value function can be represented by replacing one variable with two, such as 𝑥1+𝑥2
Slack variables can be used to represent functions with discontinuous derivatives in the form required by optimization

instead of |𝑥|

2.Surplus variables
Subtracted from the LHS of greater-than-or-equal-to (≥) constraints to convert them into equations. Surplus variables
indicate how much the RHS values are insufficient. They are also called negative slack variables.

An example of a surplus variable in linear programming is when a surplus variable is introduced to convert an inequality
constraint into an equality:

Inequality constraint: 2𝑥+3𝑦≤5

Surplus variable: 2𝑥+3𝑦+𝑠=5

o In this example, the surplus variable, 𝑠 represents the amount by which the left-hand side of the
inequality exceeds the right-hand side.
Surplus variables are similar to slack variables, but are associated with greater-than constraints. In a LINGO solution
report, the Slack or Surplus column indicates how close a constraint is to being satisfied as an equality.

---------------------------------------------------------------------------------------------------------------------------------------------------

Q. 3: Solve the following LPP by Simplex Method.

1.

2.

A-3 (1)

Zmax= 3x1 + 2x2

x1 + x2 + s1 = 4 -------------1
x1 – x2 + s2 = 2 -------------2

Now, we take:

Zmax = 3x1 + 2x2 + 0.s1 + 0.s2

Let us take,
B = S1 and S2
CB = Coefficients of S1 and S2
XB = Right Hand Value of eq. 1 and eq. 2
X1 = Coefficient of X1
X2 = Coefficient of X2
S1 = Coefficient of S1
S2 = Coefficient of S2

Cj
3 2 0 0
B CB XB X1 X2 S1 S2 X B / Xi
S1 0 4 1 1 1 0 4
S2 0 2 1 -1 0 1 2
Zj 0 0 0 0
Δj = Cj - Zj 3 2 0 0

In the above table, X1 is the key column.

For column, XB / Xi, S2 is the key row.
So, we have incoming variable as X1
and we have outgoing variable as S2
Key element as 1

First modified simplex table:

Cj
3 2 0 0
B CB XB X1 X2 S1 S2 X B / Xi
S1 0 2 0 2 1 -1 1
X1 3 2 1 -1 0 1
Zj 3 -3 0 3
Δj = Cj - Zj 0 5 0 -3

Second modified simplex table:

Cj
3 2 0 0
B CB XB X1 X2 S1 S2 X B / Xi
X2 2 1 0 1 1/2 -1/2
X1 3 2 1 -1 0 1
Zj 3 -1 1 2
Δj = Cj - Zj 0 3 -1 -2

Second modified simplex table:

Cj
3 2 0 0
B CB XB X1 X2 S1 S2 X B / Xi
X2 2 1 0 1 1/2 -1/2
X1 3 3 1 0 1/2 1/2
Zj 3 2 5/2 1/2
Δj = Cj - Zj 0 0 -5/2 -1/2

Since, Δj <= 0
Therefore, the solution is optimum
Hence the value of X1 = 3 and X2 = 1
Zmax = 3*3 +2*1 =11

(2)
---------------------------------------------------------------------------------------------------------------------------------------------------

Q. 4: Describe the simplex method. What are its advantages over graphical methods?
A-4
simplex method, standard technique in linear programming for solving an optimization problem, typically one involving
a function and several constraints expressed as inequalities. The inequalities define a polygonal region, and the solution is
typically at one of the vertices. The simplex method is a systematic procedure for testing the vertices as possible solutions.

Some simple optimization problems can be solved by drawing the constraints on a graph. However, this method is useful
only for systems of inequalities involving two variables. In practice, problems often involve hundreds of equations with
thousands of variables, which can result in an astronomical number of extreme points. In 1947 George Dantzig, a
mathematical adviser for the U.S. Air Force, devised the simplex method to restrict the number of extreme points that
have to be examined. The simplex method is one of the most useful and efficient algorithms ever invented, and it is still
the standard method employed on computers to solve optimization problems.

Understanding the importance of the Simplex Method in further mathematics can be observed in several ways:
 Efficiency: It can effectively solve large-scale, complex linear programming problems, providing quick and
accurate results.
 Versatility: Various fields make use of the Simplex Method, including finance, engineering, and business
operations.
 Decision-making: It provides a rational and systematic approach for effective decision-making in various
scenarios.

Advantages of simplex method over graphical methods:

The simplex method has several advantages over the graphical method for solving linear programming problems,
including:
 Scalability: The simplex method can be used for problems of any size, while the graphical method is only
practical for problems with two variables.
 Computational efficiency: The simplex method is more efficient than the graphical method, especially for large
problems.
 Guaranteed optimal solution: The simplex method is guaranteed to find the best solution by moving along the
vertices of the feasible region.
 Systematic approach: The simplex method systematically examines the feasible solution space.
 Adaptability: The simplex method can be used for both maximization and minimization problems.
 Sensitivity analysis: The simplex method can provide insights into how changes in the constraints or objective
function affect the optimal solution.
 Digitization and automation: The simplex method can be digitized and automated.
 Economic data: The simplex method generates important economic data as a side effect.

---------------------------------------------------------------------------------------------------------------------------------------------------

Q. 5: Solve the following assignment problem using the Hungarian Method:

---------------------------------------------------------------------------------------------------------------------------------------------------

Q. 6: Solve the following two-person zero-sum game using the graphical method:

---------------------------------------------------------------------------------------------------------------------------------------------------

Q. 7:
---------------------------------------------------------------------------------------------------------------------------------------------------

Q. 8: (a) Briefly explain the structure of Queuing System?

(b)We have five jobs, each of which have to be processed on two machines A & B in the order AB. Processing times
are given in the following table:

Machine JOBS
1 2 3 4 5
A 6 2 10 4 11
B 3 7 8 9 5

---------------------------------------------------------------------------------------------------------------------------------------------------

Q. 9: A supermarket has an average of 6 customers arriving per hour, and each customer takes an average of 5
minutes to check out. Simulate the customer checkout process for 10
customers and calculate the total waiting time.

---------------------------------------------------------------------------------------------------------------------------------------------------

Q. 10: Find the optimal solution to the following integer programming problem:

Maximize Z=x1–x2

subject to x 1 + 2x 2 ≤ 4

6x 1 + 2x 2 ≤ 9

x 1 , x 2 ≥ 0 and x 1 , x 2 are integers.

---------------------------------------------------------------------------------------------------------------------------------------------------