Unit-1 Introduction

 Decision Making, Quantitative Approach to Decision Making, Nature and

Significance of OR in Decision Making

Decision Making in Business

Decision making is the process of selecting the best course of action from among alternatives. In a business
context, it involves analyzing options and choosing the one that aligns with organizational objectives. It is a
fundamental process for managers, leaders, and teams in any organization.

Quantitative Approach to Decision Making

The quantitative approach to decision making uses mathematical models, statistical techniques, and data
analysis to make decisions. This approach focuses on using numbers and data to optimize decision-making
processes and reduce subjectivity or bias.

Key elements of a quantitative approach include:

1. Data-Driven Decisions: Using statistical analysis, trend analysis, and forecasting to support decisions.
For example, historical sales data might be analyzed to forecast future demand.
2. Optimization Models: These models focus on finding the best solution, such as minimizing cost or
maximizing profit. Some examples include:
o Linear Programming: Used for optimizing resource allocation where constraints and objectives
are linear.
o Integer Programming: Similar to linear programming, but variables must take integer values.
o Dynamic Programming: Involves breaking down problems into smaller sub-problems, useful in
multi-stage decision-making problems.
3. Decision Trees: A graphical representation of decisions and their possible consequences, including
probabilities, costs, and outcomes. Decision trees help visualize and choose between various alternatives
based on expected results.
4. Simulation: Using simulations to model complex systems and predict outcomes under different
conditions. This is helpful in scenarios where analytical methods are not feasible or the system is too
complex.
5. Risk Analysis: Quantitative approaches often involve risk analysis to evaluate the probability and
impact of different decision alternatives. Techniques like Monte Carlo simulations and sensitivity
analysis assess risk and uncertainty.
6. Queuing Theory: Used in service systems and production planning, queuing theory analyzes the
waiting times and congestion to optimize service delivery or production processes.

Nature and Significance of Operations Research (OR) in Decision Making

Operations Research (OR) is a field of study that applies advanced analytical methods to help make better
decisions. OR involves using mathematical models, statistics, and algorithms to solve complex decision-making
problems and optimize processes. The significance of OR in decision-making includes the following:
Nature of Operations Research in Decision Making:

1. Interdisciplinary Approach: OR integrates techniques from different disciplines such as mathematics,

economics, engineering, and computer science. It allows managers to approach problems from a variety
of perspectives, considering both qualitative and quantitative factors.
2. Model-Based Decision Making: OR relies on creating models that represent the real-world system or
problem. These models can be mathematical (such as linear programming or network flow models),
simulation-based, or heuristic.
3. Optimization: A key aspect of OR is optimizing resources, time, and cost. It seeks to find the most
efficient way to achieve the organization’s objectives, be it maximizing profits, minimizing costs, or
reducing time.
4. Problem Solving and Analysis: OR helps break down complex problems into manageable parts. By
using systematic approaches like linear programming, decision analysis, and inventory models, OR
supports managers in solving a wide range of operational and strategic problems.
5. Quantitative Decision Support: OR techniques provide objective, data-driven insights to decision
makers, helping them make informed decisions backed by rigorous analysis rather than intuition or
guesswork.

Significance of Operations Research in Decision Making:

1. Improved Decision Quality:

o OR provides a more structured, systematic, and rational approach to decision-making, improving
decision quality by reducing uncertainty.
o It allows managers to analyze multiple scenarios and understand the potential outcomes of
different decisions.
2. Optimization of Resources:
o OR helps in optimizing resources such as labor, capital, and materials. For example, it can assist
in determining the optimal production schedule or the best way to allocate resources in a supply
chain.
3. Cost Reduction:
o By using mathematical modeling and analysis, OR helps identify areas where costs can be
minimized without sacrificing quality or output. For example, linear programming can be used
to reduce transportation costs or inventory holding costs.
4. Increased Efficiency:
o Operations research techniques help improve efficiency in operations. For example, queuing
models can optimize customer service processes, and inventory models help balance stock
levels.
5. Risk Management:
o OR helps organizations evaluate risk by using techniques like sensitivity analysis, Monte Carlo
simulation, and forecasting. By assessing risk in different scenarios, OR ensures that decision-
makers are better prepared for uncertainties.
6. Enhanced Strategic Planning:
o OR aids in long-term planning by helping organizations forecast future trends, analyze market
conditions, and plan production schedules. Game theory and network optimization models are
examples of OR tools that help in strategic decision-making.
7. Support for Complex Decision Making:
o Some problems are inherently complex due to multiple variables and constraints, such as supply
chain logistics, production planning, or project management. OR offers methodologies that make
these problems manageable by breaking them into solvable parts.
Examples of OR Applications in Decision Making:

1. Supply Chain Optimization:

o OR techniques like linear programming and transportation models help businesses optimize
their supply chain by minimizing transportation costs and maximizing the efficiency of inventory
management.
2. Production Scheduling:
o Linear programming and simulation models are used to optimize the scheduling of machines
and labor in production, ensuring that resources are utilized efficiently and deadlines are met.
3. Financial Decision Making:
o OR techniques such as portfolio optimization and capital budgeting models help financial
managers make decisions regarding investments, asset allocation, and project financing to
maximize returns and minimize risks.
4. Project Management:
o Tools like critical path method (CPM) and program evaluation and review technique
(PERT), both of which are rooted in OR, help managers plan, schedule, and control complex
projects to ensure timely completion and budget control.
5. Marketing and Sales Decisions:
o OR methods are used to develop pricing strategies, forecast demand, and optimize advertising
expenditure based on predictive models and data analytics.

 Scientific Methods in Operations Research, Models in Operations Research,

Application Areas of OR in Management

Scientific Methods in Operations Research

Operations Research (OR) is a discipline that uses advanced analytical methods to help make better decisions.
The core of OR involves applying scientific methods to model complex systems and make informed decisions.
Here are some of the main scientific methods used in OR:

1. Problem Formulation:
o Identification of Objectives: The first step in OR is to clearly define the problem and the
objectives of the decision-making process. This involves understanding the goal (e.g.,
maximizing profit, minimizing cost, or optimizing resources).
o Identifying Variables: Identifying the key decision variables that impact the problem and
determining how they interact.
2. Model Development:
o Once the problem is identified, the next step is to develop a mathematical model to represent
the system. This model includes:
 Decision Variables: Quantities that can be controlled or changed.
 Objective Function: A mathematical expression that describes the goal of the decision-
making process (e.g., profit, cost, efficiency).
 Constraints: Limitations or restrictions on the decision variables (e.g., budget limits,
resource constraints).
 Parameters: Constants or coefficients that are given values and are usually determined
through data collection.
 3. Solution Methods:
o Solving the mathematical model using appropriate analytical techniques such as linear
programming, simulation, dynamic programming, etc. The methods help determine the best
values for the decision variables that achieve the objective.
4. Validation and Sensitivity Analysis:
o Validation involves checking whether the model represents the real-world system accurately.
o Sensitivity Analysis evaluates how changes in the parameters or assumptions affect the solution,
allowing decision-makers to assess the robustness of the solution under different scenarios.
5. Implementation and Monitoring:
o The final solution is implemented, and its performance is continuously monitored. If necessary,
adjustments can be made to optimize the system further.

Models in Operations Research

OR uses several models to solve problems. These models can be classified based on the nature of the problem
and the techniques used:

1. Linear Programming (LP) Models:

o Linear programming is one of the most widely used techniques in OR. It involves optimizing
an objective function subject to a set of linear constraints.
o Example: A company wants to maximize profit by determining how many units of different
products to produce, given resource constraints (e.g., labor hours, materials).
2. Integer Programming (IP) Models:
o This is a variation of linear programming where decision variables are constrained to integer
values (e.g., number of units, number of machines).
o Example: A company decides how many units of products to produce in whole numbers (no
fractional units allowed).
3. Dynamic Programming (DP) Models:
o Dynamic programming is used for solving multi-stage decision problems where decisions in one
stage affect decisions in later stages.
o Example: Optimizing the production schedule over multiple time periods, where decisions in one
period affect the availability of resources in later periods.
4. Queuing Models:
o Queuing theory models the waiting lines in service systems to optimize factors like wait time
and service efficiency. These models are used in applications like customer service,
manufacturing, and healthcare.
o Example: Determining the number of service desks required at a bank to minimize customer
waiting time.
5. Simulation Models:
o Simulation involves creating a computer-based model to replicate real-world processes and
experiment with different scenarios without real-world risks.
o Example: Simulating traffic patterns in a city to identify where traffic congestion occurs and
what measures could reduce delays.
6. Network Models:
o These models focus on systems where various elements are interconnected, such as supply
chains, transportation systems, and project scheduling.
o Example: The Critical Path Method (CPM) and Program Evaluation and Review Technique
(PERT) are used to optimize project schedules by determining the longest path (critical path) of
tasks that must be completed in time.
 7. Game Theory Models:
o Game theory analyzes situations where the outcome of a decision depends not only on one’s own
actions but also on the actions of others. It is used in competitive environments.
o Example: In business strategy, companies use game theory to predict competitors' responses to
pricing changes or market entry strategies.
8. Markov Decision Process (MDP) Models:
o These models are used to handle decision-making under uncertainty, where outcomes depend on
both the current state and the actions taken.
o Example: In inventory management, MDP can be used to determine the optimal order quantity
when demand is uncertain.

Application Areas of Operations Research in Management

Operations Research has wide applications in various areas of management, helping organizations optimize
their operations, resources, and decision-making processes. Some of the key application areas include:

1. Production and Operations Management

 Production Planning and Scheduling: OR helps in optimizing production schedules, determining the
quantity of goods to produce, and managing plant resources to meet demand.
 Inventory Management: Models like Economic Order Quantity (EOQ), Just-in-Time (JIT), and
Material Requirements Planning (MRP) help manage inventory levels, reduce holding costs, and
ensure timely availability of materials.
 Capacity Planning: OR models are used to determine the optimal capacity (e.g., number of machines or
workers) required to meet production goals.
 Facility Layout Design: Helps in designing factory layouts that minimize the cost and time involved in
material handling.

2. Supply Chain Management

 Logistics Optimization: OR models, such as the Transportation Problem, are used to optimize
distribution networks, minimizing transportation costs while ensuring timely delivery.
 Supply Chain Coordination: Optimization models help coordinate different parts of the supply chain
(suppliers, manufacturers, distributors) to reduce lead times and costs.
 Demand Forecasting and Inventory Control: OR tools help in predicting demand patterns and
determining the right inventory levels to meet customer needs without overstocking.

3. Financial Management

 Portfolio Optimization: Linear programming and other OR techniques help manage investment
portfolios, balancing risk and return by determining the optimal allocation of assets.
 Capital Budgeting: OR helps in evaluating different investment opportunities, using techniques like
Net Present Value (NPV) and Internal Rate of Return (IRR), to determine which projects to
undertake.
 Risk Management: OR methods like Monte Carlo Simulation help businesses evaluate financial risks
and their impact under different scenarios.
4. Marketing and Sales Management

 Market Research: OR techniques, such as cluster analysis and conjoint analysis, are used to segment
markets, study consumer behavior, and design effective marketing strategies.
 Pricing Optimization: Game Theory and other OR models are used to set optimal prices based on
demand elasticity and competitive behavior.
 Sales Forecasting: OR models help forecast sales based on historical data, trends, and external factors,
enabling better resource allocation.

5. Human Resource Management

 Workforce Scheduling: OR models are used to create efficient employee schedules, ensuring proper
coverage while minimizing overtime and labor costs.
 Staffing Optimization: Linear programming can be used to determine the optimal number of
employees required for various shifts, considering demand and skill requirements.
 Performance Management: OR techniques help evaluate employee performance using various metrics,
allowing for more effective human resource decisions.

6. Project Management

 Project Scheduling: CPM and PERT help plan and control the timing of project tasks, identify critical
paths, and ensure that the project is completed on time.
 Resource Allocation: OR models optimize the allocation of resources (people, equipment, and
materials) across different tasks to minimize costs and project durations.

7. Healthcare Management

 Patient Flow Optimization: OR models are used to improve hospital management, including patient
flow, reducing wait times, and optimizing the use of hospital resources (e.g., beds, doctors).
 Healthcare Facility Location: OR methods help in determining the optimal locations for healthcare
facilities based on factors like population density, demand for services, and transportation access.
 Supply Chain in Healthcare: OR tools help optimize the distribution of medical supplies, ensuring
hospitals have the necessary materials while reducing waste and cost.

8. Transportation and Distribution

 Routing and Scheduling: OR methods help in optimizing transportation routes and schedules,
minimizing transportation costs while meeting delivery deadlines.
 Fleet Management: Helps optimize fleet size and operations to reduce costs and improve delivery
service.

9. Energy and Environmental Management

 Energy Optimization: OR models can be applied to optimize energy usage in production, minimizing
energy costs while reducing environmental impact.
 Environmental Impact Assessment: OR can help in evaluating and mitigating the environmental
impact of industrial activities through simulations and modeling.
Unit-2 Linear Programming
 Model Formulation, Graphical Method, Simplex Method, Degeneracy in L.P.P
Model Formulation in Operations Research (LPP)

Linear Programming Problems (LPP) are mathematical problems where the objective is to optimize
(maximize or minimize) a linear objective function subject to a set of linear constraints. The steps to formulate a
Linear Programming Problem include:

1. Define Decision Variables:

These are the variables that need to be determined in order to optimize the objective function. For example, if a
company produces two types of products, let x1x_1 and x2x_2 represent the quantities of each product to be
produced.

2. Construct the Objective Function:

The objective function is the goal to be maximized or minimized. It is usually a linear combination of the
decision variables.

 Example: Maximizing profit from producing x1x_1 units of Product 1 and x2x_2 units of Product 2
could be written as: Z=c1x1+c2x2Z = c_1 x_1 + c_2 x_2 Where c1c_1 and c2c_2 are the profits per unit
of each product.

3. Formulate Constraints:

Constraints represent the limitations on resources or conditions that the solution must satisfy. These can be in
the form of inequalities or equations.

 Example: If resources like labor and material limit production, the constraints may be:
a1x1+a2x2≤b1a_1 x_1 + a_2 x_2 \leq b_1 a3x1+a4x2≤b2a_3 x_1 + a_4 x_2 \leq b_2 Where
a1,a2,a3,a4a_1, a_2, a_3, a_4 are the resource coefficients and b1,b2b_1, b_2 are the available amounts
of resources.

4. Non-Negativity Constraints:

The decision variables are usually required to be non-negative, as it doesn’t make sense to have negative
quantities of products or resources.

x1≥0,x2≥0x_1 \geq 0, \quad x_2 \geq 0

Graphical Method

The Graphical Method is a visual approach to solving a Linear Programming Problem. It is only applicable to
problems with two decision variables (i.e., a 2-dimensional space). The steps are:

1. Plot the Constraints:

o Each constraint is plotted as a straight line on the graph.
 o For inequalities (e.g., x1+x2≤5x_1 + x_2 \leq 5), shade the region that satisfies the inequality.
For constraints like x1+x2=5x_1 + x_2 = 5, plot the line and determine the feasible region.
2. Identify the Feasible Region:
o The feasible region is the set of all points that satisfy all the constraints. It is usually a polygon or
a bounded area on the graph.
3. Plot the Objective Function:
o The objective function (e.g., Z=c1x1+c2x2Z = c_1 x_1 + c_2 x_2) is plotted by drawing lines of
constant value, known as iso-profit lines (for maximization problems) or iso-cost lines (for
minimization problems).
4. Find the Optimal Solution:
o The optimal solution lies at one of the vertices (corner points) of the feasible region. Evaluate the
objective function at each vertex, and the one that gives the maximum (for maximization
problems) or minimum (for minimization problems) value is the optimal solution.

Simplex Method

The Simplex Method is an iterative algorithm for solving Linear Programming Problems with more than two
variables. It moves along the edges of the feasible region to find the optimal solution.

Steps in the Simplex Method:

1. Convert the LPP to Standard Form:

o Ensure all constraints are in the form of equalities (i.e., ≤\leq constraints are converted to
equalities by introducing slack variables).
o The objective function should be in the form of Z=c1x1+c2x2+...+cnxnZ = c_1 x_1 + c_2 x_2 +
... + c_n x_n, and the goal is to maximize it.
2. Initial Simplex Tableau:
o Set up an initial tableau with the coefficients of the variables, the objective function, and the
constraints.
o The first row of the tableau corresponds to the objective function, and the other rows correspond
to the constraints.
3. Identify Pivot Column:
o Choose the most negative coefficient in the objective row (for maximization problems). This is
the entering variable.
4. Identify Pivot Row:
o Compute the ratio of the right-hand side (RHS) value to the coefficient of the pivot column for
each constraint. The row with the smallest positive ratio determines the leaving variable.
5. Pivot Operation:
o Perform row operations to make the pivot element 1, and all other elements in the pivot column
0, so that the system remains consistent with the constraints.
6. Iterate:
o Repeat the process of selecting pivot columns and rows, performing row operations until there
are no negative coefficients in the objective row (for maximization problems), indicating that the
optimal solution has been reached.
7. Solution:
o The final tableau will give the values of the decision variables that maximize (or minimize) the
objective function, along with the optimal value.
Degeneracy in Linear Programming

Degeneracy occurs in a Linear Programming Problem when there is more than one optimal solution or when
multiple constraints intersect at a single point. This can lead to cycling or ambiguity in the Simplex Method.

Causes of Degeneracy:

1. Multiple Constraints: Multiple constraints might intersect at the same point in the feasible region,
leading to more than one solution.
2. Zero Pivot Element: In some cases, when selecting pivot elements, there may be multiple constraints
that result in zero values for some variables, which can stall the progress of the Simplex algorithm.

Handling Degeneracy:

1. Anti-Cycling Rules: Specialized pivoting techniques, such as Bland’s Rule, ensure the Simplex
Method will not cycle. This rule specifies which variable to enter and leave the basis when there are ties
in the ratio test.
2. Artificial Variables: In some cases, artificial variables are introduced to break ties and resolve
degeneracy, ensuring that the Simplex algorithm progresses toward the optimal solution.

Summary

1. Model Formulation: Linear Programming involves formulating problems with decision variables,
objective functions, constraints, and non-negativity conditions.
2. Graphical Method: A visual method used to solve two-variable LP problems by plotting constraints,
identifying the feasible region, and evaluating the objective function at the vertices.
3. Simplex Method: An iterative, algebraic method for solving LP problems with more than two variables.
It uses a tableau to move towards the optimal solution by pivoting across feasible solutions.
4. Degeneracy in LPP: Degeneracy occurs when multiple solutions exist or when pivoting leads to an
infinite loop. It can be handled through anti-cycling rules or introducing artificial variables.

These techniques are central to solving Linear Programming Problems and finding the optimal solution in real-
world scenarios.

 Sensitivity Analysis Applied to Linear Programming Problems.

Sensitivity Analysis in Linear Programming

Sensitivity Analysis is a crucial aspect of Linear Programming (LP) that explores how the optimal solution of
an LP model changes when there are variations in the coefficients of the objective function or constraints. This
helps decision-makers understand the stability and robustness of the solution in response to changes in input
parameters. It answers questions like:

 How much can the coefficients of the objective function or the constraints change before the optimal
solution changes?
 Which constraints or coefficients are most critical to the solution?
Key Components in Sensitivity Analysis

1. Objective Function Coefficients Sensitivity:

o Sensitivity analysis examines how changes in the coefficients of the objective function affect the
optimal solution.
o If the change in an objective coefficient does not alter the optimal basis (set of variables that are
part of the solution), then the optimal solution remains unchanged.
o However, if a coefficient changes enough to cause a variable to enter or leave the solution, the
optimal solution will change.
2. Right-Hand Side (RHS) of Constraints Sensitivity:
o The RHS of a constraint defines the available resources or limits (such as labor hours, budget,
etc.). Sensitivity analysis investigates how changes in these values influence the optimal
solution.
o For example, if the RHS of a constraint increases, it may allow more of the decision variable to
be included in the optimal solution, possibly leading to higher profits (for maximization
problems).
o The analysis helps in determining the range within which the RHS values can vary without
changing the optimal solution.
3. Constraint Coefficients Sensitivity:
o Sensitivity analysis also looks at changes in the coefficients of the constraints (e.g., the amount
of resource required for a specific decision variable).
o These changes can affect the feasible region of the problem, and hence the optimal solution.
Understanding the impact of changes in constraint coefficients helps managers prioritize which
constraints need more attention.

Types of Sensitivity Analysis

1. Sensitivity to Changes in Objective Function Coefficients:

 Range of Optimality: The range within which the objective function coefficients can change without
affecting the current optimal solution. If the objective function coefficient of a variable falls within this
range, the optimal solution remains the same.
o Example: Suppose the objective function is Z=4x1+5x2Z = 4x_1 + 5x_2, and after performing
sensitivity analysis, we find that the coefficient of x1x_1 can change between 3 and 6 without
altering the optimal solution.
 Impact on the Optimal Solution: If a coefficient falls outside this range, the current optimal solution
might no longer be optimal, and a new optimal solution must be computed.

2. Sensitivity to Changes in Right-Hand Side (RHS) Values of Constraints:

 Feasible Region Adjustment: When the RHS of a constraint changes (for example, an increase in
available resources), it could expand or contract the feasible region. The solution will depend on the
magnitude of the change.
 Shadow Price: The shadow price represents the change in the objective function’s value for a one-unit
increase in the RHS of a constraint, assuming all other factors remain constant. The shadow price can be
interpreted as the marginal value of an additional unit of resource.
o Example: If the RHS of a resource constraint increases by 1 unit, and the shadow price is 2, the
objective function (profit) will increase by 2 units.
  Range of Feasibility: This is the range within which the RHS value of a constraint can change without
altering the optimal basis. Outside this range, a new optimal solution might be required.

3. Sensitivity to Changes in Constraint Coefficients:

 Dual Variables: Each constraint in a linear programming problem has an associated dual variable or
shadow price, which indicates the rate of change in the objective function as the constraint’s coefficient
changes.
 Impact on Feasibility and Optimality: When constraint coefficients change, it can shift the feasible
region, potentially making some variables non-binding or introducing new constraints that might affect
the optimal solution.

Steps to Perform Sensitivity Analysis

1. Solve the Initial Linear Programming Problem:

o Use methods like the Simplex Method or Graphical Method (for two-variable problems) to
find the initial optimal solution.
2. Identify the Key Elements:
o Focus on the objective function coefficients, the RHS values of the constraints, and the
constraint coefficients.
3. Calculate the Range of Optimality and Feasibility:
o For changes in the objective function coefficients, identify the range within which the current
optimal solution will remain unchanged.
o For changes in the RHS of constraints, compute the shadow price and the range of feasibility.
4. Perform Perturbation:
o Introduce small changes in the coefficients (either objective or constraint) and observe how the
solution changes.
o If necessary, resolve the problem after perturbing the values and compare the new solution with
the previous one.
5. Interpret the Results:
o Based on the sensitivity analysis, interpret how robust the current solution is to changes in the
model's parameters.
o Identify which constraints or objective function coefficients have the greatest influence on the
optimal solution.

Example of Sensitivity Analysis

Consider a simple Linear Programming Problem (LPP):

Maximize Z=3x1+2x2Z = 3x_1 + 2x_2

Subject to:

x1+x2≤4x_1 + x_2 \leq 4 2x1+x2≤52x_1 + x_2 \leq 5 x1≥0,x2≥0x_1 \geq 0, x_2 \geq 0

Initial Solution Using Simplex Method:

Let's assume that the optimal solution to this problem is at x1=2x_1 = 2, x2=2x_2 = 2, with Z=12Z = 12.

Now, we will analyze how sensitive this solution is to changes in the objective function coefficients and the
constraints.

1. Objective Function Coefficients Sensitivity:

o If the coefficient of x1x_1 changes from 3 to 4, the optimal solution will change. You would
need to compute the new objective function and solve the problem again.
2. RHS Sensitivity:
o If the RHS of the first constraint increases from 4 to 6, you would need to check if this change
causes the feasible region to expand and potentially lead to a better (higher) value for the
objective function.
o The shadow price of the first constraint indicates how much the objective function would
improve with an additional unit of resource (an additional unit of the resource available for
x1+x2x_1 + x_2).
3. Constraint Coefficients Sensitivity:
o Changes in the coefficients of the constraints (e.g., x1+x2≤4x_1 + x_2 \leq 4 becoming
2x1+x2≤42x_1 + x_2 \leq 4) could affect the feasible region, changing the optimal solution. This
requires recalculating the feasible region and checking if the current solution still holds.

Key Takeaways from Sensitivity Analysis

1. Robustness of the Solution: Sensitivity analysis helps in determining how stable the optimal solution is
when there are small changes in the coefficients or constraints. If the solution is highly sensitive to small
changes, then the model is less robust.
2. Strategic Decision-Making: Sensitivity analysis aids managers in understanding which parameters
(objective coefficients or constraints) are most critical to the optimal outcome, helping in focusing
efforts where changes are most impactful.
3. Resource Allocation: By using the concept of shadow prices, sensitivity analysis provides valuable
insights into how the marginal value of resources impacts the objective function, helping organizations
make informed decisions about resource allocation.
4. Prepares for Uncertainty: It helps organizations plan for uncertainty in inputs (e.g., changes in demand
or resource availability) and prepare alternative strategies if the conditions change.

In summary, Sensitivity Analysis in Linear Programming is essential for assessing how robust a solution is to
changes in model parameters and is a powerful tool in decision-making processes under uncertainty.

 Duality in Linear Programming. Dual Simplex Method.

Duality in Linear Programming

Duality is a fundamental concept in linear programming (LP) that establishes a relationship between every
linear programming problem (called the primal problem) and another linear programming problem (called the
dual problem). These two problems are mathematically linked, and solving one provides insights into solving
the other.
Key Concepts of Duality

1. Primal and Dual Problems:

o The primal problem is the original LP problem that we aim to solve.
o The dual problem is derived from the primal problem and represents a different perspective,
often providing valuable insights into resource allocation, shadow prices, and constraints.
2. Primal and Dual Relationship:
o For every LP problem, there is a corresponding dual problem, where:
 If the primal is a maximization problem, the dual is a minimization problem.
 If the primal has greater than or equal constraints (≥\geq), the dual will have less than
or equal constraints (≤\leq), and vice versa.
 The objective function coefficients in the primal become the RHS values in the dual
constraints, and the RHS values in the primal constraints become the coefficients in the
dual objective function.

Primal Problem (Standard Form):

Maximize Z=c1x1+c2x2+⋯+cnxnZ = c_1 x_1 + c_2 x_2 + \dots + c_n x_n

Subject to:

A1x1+A2x2+⋯+Anxn≤b1A_1 x_1 + A_2 x_2 + \dots + A_n x_n \leq b_1 x1,x2,…,xn≥0x_1, x_2, \dots, x_n
\geq 0

Dual Problem:

Minimize W=b1y1+b2y2+⋯+bmymW = b_1 y_1 + b_2 y_2 + \dots + b_m y_m

Subject to:

A1y1+A2y2+⋯+Amym≥c1A_1 y_1 + A_2 y_2 + \dots + A_m y_m \geq c_1 y1,y2,…,ym≥0y_1, y_2, \dots,
y_m \geq 0

Duality Theorems:

1. Weak Duality Theorem: The value of the objective function in the dual problem is always greater than
or equal to the value of the objective function in the primal problem for any feasible solution. In
mathematical terms:

W≥ZW \geq Z

This implies that the optimal solution to the primal problem is always less than or equal to the optimal
solution to the dual problem.

2. Strong Duality Theorem: If both the primal and dual problems have feasible solutions, then they have
the same optimal objective value. In other words, the optimal value of the objective function of the
primal is equal to the optimal value of the objective function of the dual:

Z∗=W∗Z^* = W^*
 where Z∗Z^* and W∗W^* are the optimal values of the primal and dual objective functions,
respectively.

3. Complementary Slackness: If xix_i is a basic variable in the primal solution, the corresponding dual
constraint must be satisfied with equality, and vice versa. This relationship is essential for determining
the optimal solutions from the primal and dual simultaneously.

Dual Simplex Method

The Dual Simplex Method is a variant of the Simplex Method used to solve Linear Programming (LP)
problems, particularly when the primal feasible solution is not available, but the dual feasible solution is. It’s a
valuable technique for problems where an initial feasible solution might not be readily available, or when the
problem data is updated dynamically.

When to Use the Dual Simplex Method:

 When the primal problem is infeasible but the dual is feasible (this situation can occur, for example,
during the post-optimality analysis or when constraints change).
 When the solution procedure needs to be updated in cases such as changes in resources, technology, or
constraints, and the primal LP is no longer feasible.
 In some cases, when the primal solution is not feasible, but the dual solution is feasible, the Dual
Simplex Method can be used to restore feasibility in the primal.

How the Dual Simplex Method Works:

1. Start with a Dual Feasible Solution:

o The algorithm begins with a solution that is feasible for the dual problem but not necessarily for
the primal.
2. Maintain Dual Feasibility:
o In each iteration, the method ensures that the solution remains dual feasible (i.e., the constraints
of the dual problem are satisfied).
3. Primal Infeasibility Handling:
o The algorithm iterates through the steps of the Simplex Method, focusing on improving primal
feasibility while maintaining dual feasibility.
o During each iteration, the algorithm looks for a variable to enter the basis (like in the Simplex
Method) and makes pivoting adjustments to move towards primal feasibility.
4. Termination:
o The process continues until both primal and dual feasibility are satisfied. At this point, the
optimal solution is reached for both the primal and dual problems, and the optimal objective
values for both problems are equal, as per the Strong Duality Theorem.

Steps of the Dual Simplex Method:

1. Initialization:
o Start with a feasible solution to the dual problem (i.e., all dual variables are non-negative). The
primal may not be feasible.
2. Iterative Improvement:
o Identify the most negative entry in the primal constraint row (indicating primal infeasibility).
 o
Perform pivoting to move towards primal feasibility, while ensuring that dual feasibility is
maintained.
3. Feasibility Check:
o After each iteration, check for dual feasibility (i.e., ensure the current solution satisfies all dual
constraints).
o If any dual constraint is violated, adjust by pivoting until both primal and dual feasibility are
satisfied.
4. Termination:
o The algorithm terminates when an optimal solution is found, which satisfies both primal and dual
feasibility. At this point, the objective values of the primal and dual problems will be equal.

Example of Duality in Linear Programming

Consider the following primal problem:

Primal Problem (Maximization): Maximize Z=4x1+5x2Z = 4x_1 + 5x_2

Subject to:

x1+2x2≤8x_1 + 2x_2 \leq 8 3x1+2x2≤123x_1 + 2x_2 \leq 12 x1,x2≥0x_1, x_2 \geq 0

Dual Problem (Minimization):

From the primal problem, the dual problem can be formulated as:

Minimize W=8y1+12y2W = 8y_1 + 12y_2

Subject to:

y1+3y2≥4y_1 + 3y_2 \geq 4 2y1+2y2≥52y_1 + 2y_2 \geq 5 y1,y2≥0y_1, y_2 \geq 0

Interpretation of Dual Problem:

 The dual variables y1y_1 and y2y_2 represent the shadow prices associated with the constraints of the
primal problem.
 The dual objective seeks to minimize the cost of the resources (8 and 12 units, respectively) required to
meet the primal demand.
 Solving the dual gives us insights into the value of additional resources (in terms of constraints) and
their impact on the primal objective function.