My Operation Research Notes

1) 📐 LPP Graphical Method

1. FINDING INTERSECTION POINTS

Never reverse inequality signs. Just change ≥/≤ to =.

Example:
Constraints: 2x + y ≥ 6 and x - y ≤ 2
Correct: Solve 2x + y = 6 and x - y = 2 → (8/3, 2/3)
Check: Plug into original inequalities to verify feasible.

2. QUICK FEASIBILITY CHECK (Parallel Lines)

If two constraints are multiples with opposite inequalities:

Format:
a x₁ + b x₂ ≤ c₁
a x₁ + b x₂ ≥ c₂

Rule:

If c₁ ≥ c₂ → Feasible strip exists between lines
If c₁ < c₂ → NO FEASIBLE REGION

Example:
x + 2y ≤ 4 (c₁ = 4)
x + 2y ≥ 8 (c₂ = 8)
Since 4 < 8 → INFEASIBLE

⚠️ This means NO solution for MAX or MIN - objective function doesn't matter!

3. FEASIBILITY vs OPTIMALITY

Feasibility: "Is there ANY point satisfying ALL constraints?"
Optimality: "WHICH feasible point gives best Z value?"

Example 1: Feasible but Different Optimality

Problem A (Minimize):
Min Z = 3x + 4y
Subject to: x + y ≥ 4, x ≥ 0, y ≥ 0
→ Feasible: ✅ (Region above line exists)
→ Optimal: Finite min at (4,0) with Z=12

Problem B (Same constraints, Maximize):
Max Z = 3x + 4y
Same constraints
→ Feasible: ✅ (Same region)
→ Optimal: UNBOUNDED (Z → ∞ as x,y increase)

📌 Key Insight: Changing objective from min to max can change optimality even if feasibility stays same!

💡 Refer to Q3 and Q4 on my handwritten notes. I've solved them there.

Example 2: Multiple/Optimal Solutions

If objective line is parallel to a constraint, all points on that constraint segment give same Z.
State: "Multiple optimal solutions along line between points A and B."

4. MULTIPLE CONSTRAINTS CHECK

A. Combining Different Variables

Given: x₁ ≤ 5 and x₂ ≥ 3
Find bounds for expression x₁ - x₂:

Maximum: Use max x₁ & min x₂ → 5 - 3 = 2
So x₁ - x₂ ≤ 2
Minimum: Use min x₁ & max x₂ → Could be -∞ (unbounded below)

Use this to check third constraint:
If third constraint says x₁ - x₂ ≥ 10 → INFEASIBLE (max is 2 < 10)
If says x₁ - x₂ ≥ -5 → FEASIBLE (can achieve values ≥ -5)

In detailed

Maximum of x₁ - x₂: To maximize x₁ - x₂, we want largest x₁ and smallest x₂.
- Largest x₁ = 5
- Smallest x₂ = 3 So Max(x₁ - x₂) = 5 - 3 = 2 ✅
Minimum of x₁ - x₂: To minimize x₁ - x₂, we want smallest x₁ and largest x₂.
- Smallest x₁ could be very small (→ -∞ if no lower bound given)
- Largest x₂ could be very large (→ +∞ if no upper bound given) So Min(x₁ - x₂) = -∞ (unbounded below)

Thus: x₁ - x₂ ≤ 2 (but NO lower bound unless other constraints exist)

B. Three Equations Contradiction

Example:
x + y ≤ 5 ...(1)
x ≥ 3 ...(2)
y ≥ 3 ...(3)

From (2)+(3): Minimum x + y = 3 + 3 = 6
But (1) says x + y ≤ 5 → INFEASIBLE

5. EXAM STRATEGY

Scan for parallel lines with c₁ < c₂ → If found, state "Infeasible"
Find intersection points using =, never reverse signs
Check each point against ALL original inequalities
If no feasible points → Infeasible problem
If feasible region exists → Evaluate objective at corners
Watch for:
- Unbounded max in unlimited region
- Finite min even in unbounded region
- Multiple solutions if objective parallel to constraint

Remember: Feasibility = constraints only. Optimality = objective function after feasibility confirmed

2) Simplex Method Master Cheat Sheet

🔑 Golden Rule: Always Convert Min to Max

Minimize: z = c₁x₁ + c₂x₂ + ...
Convert to: Maximize z' = -c₁x₁ - c₂x₂ - ...
Final Answer: Min z = - (Max z')

💡 Always use maximization rules to avoid confusion

📋 Constraint Handling

Constraint	Action	Method
`≤`	Add Slack Variable (`+ sᵢ`)	Standard Simplex
`≥`	Subtract Surplus (`- sᵢ`) + Add Artificial (`+ aᵢ`)	Big-M / Two-Phase
`=`	Add Artificial Variable (`+ aᵢ`)	Big-M / Two-Phase

📐 Minimum Ratio Test (MRT) - Leaving Variable

Process for entering variable column:

Pivot Value	Action	Example
> 0	Calculate `θ = RHS / Pivot`	`θ = 10 / 5 = 2` ✓
≤ 0	Ignore row	`θ = 10 / (-2)` → Ignore
0/0	Error - check setup

💡 Choose row with smallest non-negative θ

🎯 Variable Management During Pivots

Variable Type	Remove Column?	Reason
Artificial (aᵢ)	YES ✅	Remove when it leaves basis
Surplus (sᵢ)	NO ❌	Real variable, can re-enter
Slack (sᵢ)	NO ❌	Real variable, can re-enter

Identify replaced variable by 1 in pivot row-column intersection

✅ Optimality Check (When to STOP)

For converted MAXIMIZATION problem:

Stop when all Zⱼ - Cⱼ ≥ 0

Remember: You converted Min to Max, so this is the only condition needed!

3) Transportation Problem

📦 Basic Rules

Elimination Rules

If row supply = 0 → Cross out entire row
If column demand = 0 → Cross out entire column

Balance Check (Step 1 - ALWAYS)

Balanced: Total Supply = Total Demand
Unbalanced: Total Supply ≠ Total Demand

⚖️ Handling Unbalanced Problems

Condition	Action	Dummy Cost
Supply = Demand	Nothing - already balanced	-
Supply > Demand	Add Dummy Column	`0`
Demand > Supply	Add Dummy Row	`0`

Examples:

Supply > Demand: Add column with demand = difference, cost = 0
Demand > Supply: Add row with supply = difference, cost = 0

🔢 Tie-Breaker Rule (When Supply = Demand during allocation)

Situation: Allocation = Remaining Supply = Remaining Demand

What to do:

Allocate actual units to current cell
Cross out EITHER row OR column
Place 0 UNITS in next cell of uncrossed line

🎯 Visual Examples

Example 1: Cross Out ROW, Place 0 in COLUMN

Initial:

       W1   W2   W3   Supply
F2 |   40   60   80   ||   3
F3 |   70   20   90   ||   25
--------------------||-------
Demand |  3   14   15  ||

Steps:

Allocate 3 units to (F2, W1)
Cross out ROW F2
Place 0 units in (F3, W1)

Result:

       W1   W2   W3   Supply
F2 |  [3]   X    X   ||   0
F3 |  [0]  20   90   ||   25
--------------------||-------
Demand |  0   14   15  ||

Example 2: Cross Out COLUMN, Place 0 in ROW

Same Initial Situation:

Steps:

Allocate 3 units to (F2, W1)
Cross out COLUMN W1
Place 0 units in (F2, W2)

Result:

       W1   W2   W3   Supply
F2 |  [3]  [0]   X   ||   0
F3 |   X   20   90   ||   25
--------------------||-------
Demand |  0   14   15  ||

Why? Maintains required basic cells (m + n - 1) for optimality test

🧮 MODI Method

Choosing First Zero (uᵢ or vⱼ)

When multiple rows/columns have same max allocations:

Choose ANY ONE - doesn't affect final answer
Convention: Choose row/column with lowest index

System of Equations

uᵢ + vⱼ = cᱼ (for allocated cells)

Quick Checklist

✓ Count allocations in each row/column
✓ Find maximum number
✓ If tie → choose any one
✓ Set that uᵢ or vⱼ = 0
✓ Calculate rest using uᵢ + vⱼ = cᱼ

🗺️ Traveling Salesman Problem (TSP)

Key Insights

Multiple optimal solutions possible
Different zero-selection sequences → different Hamiltonian cycles
Both valid if: Visit each city once, return to start, valid connections

Exam Strategy

Marks	Approach
5 marks	One clean solution
10-15 marks	Show alternatives if time

Smart Tips

Trust visual intuition - row/column scanning
Never over-invest time on small-mark questions
Completed "good" solution > perfect "unfinished" solution

Remember: You now understand the "why" behind methods! 🎯

4) Game Theory

🎯 Saddle Point vs. Value of Game

Key Distinction

Concept	What It Is	Example
Value of Game	The outcome/payoff	6
Saddle Point	The cell position	(R2, C2)

What is a Saddle Point?

A cell in the matrix where:

It is the maximum in its column (best for Column player)
It is the minimum in its row (best for Row player)

📊 Visual Examples

Example 1: No Saddle Point

    C1  C2  C3  Row Min
R1 | 2   8   3  |  2
R2 | 7   6   9  |  6  ← max-min = 6
R3 | 4   5   1  |  1
----------------|----
Col Max | 7   8   9 |
        ↑
    min-max = 7 ❌ (6 ≠ 7 → No saddle point)

Example 2: Saddle Point Exists

    C1  C2  C3  Row Min
R1 | 2   8   3  |  2
R2 | 7   6   9  |  6  ← max-min = 6
R3 | 4   5   1  |  1
----------------|----
Col Max | 7   6   9 |
            ↑
        min-max = 6 ✅

Here:

Value of game = 6
Saddle point = (R2, C2)
Why? Minimum in Row 2 (6 vs 7,9) and maximum in Column 2 (6 vs 8,5)

🔍 Exam Strategy

Steps to Solve

Find max-min and min-max
If equal → that's your value
The cell where they meet is your saddle point
Report both: "Value = 6, Saddle point at (R2, C2)"

Why This Matters

Value tells you how much the game is worth
Saddle point tells you what strategies to play
Without saddle point, you don't know how to achieve the value!

5) Line Segment Formulas

🔄 The Lambda Swap Insight

Both formulas are equivalent — they just swap the roles of λ and (1-λ):

Formula 1: λ·y + (1-λ)·x
Formula 2: λ·x + (1-λ)·y

Proof: If you define μ = 1-λ in Formula 2, you get Formula 1!

📍 Parametric Line Convention

Standard Convention

V = λ·B + (1-λ)·A

Where:

λ = 0 → Point A
λ = 1 → Point B
0 ≤ λ ≤ 1 → Line segment AB

Quick Check

λ = 0: V = A ✓
λ = 1: V = B ✓
λ = 0.5: V = midpoint ✓

📝 Exam Strategy

Do

Pick one convention and stick with it
Clearly define which point is A and which is B
State your formula clearly at the start

Don't

Switch conventions mid-problem
Worry about which version to use — both work!

Remember: Your instructor's different versions are just using different labeling! ✅

6) PERT & CPM

📊 Node Notation Standards

Common Formats (All Valid)

Horizontal:

Ei | Li

First cell = Earliest time
Second cell = Latest time

Vertical (Most Common):

Ei
Li

Top = Earliest time
Bottom = Latest time

Vertical (Alternative):

Li
Ei

Top = Latest time
Bottom = Earliest time

🎯 Exam Strategy

Golden Rules

Be consistent within the same network diagram
Label clearly if unsure: Ei=5, Li=7
Evaluators check values and logic, not cell positions

Recommended for Indian Universities

Ei | Li   (horizontal)

Ei
Li     (vertical)

⏰ Float Values Rules

Float Type	Can Be Negative?	Action if Negative
Total Float (TF)	✅ Yes	Keep as is - indicates delay
Free Float (FF)	❌ No	Set to 0
Independent Float (IF)	❌ No	Set to 0

📐 Float Formulas (i→j Notation)

Float Type	Formula	Negative Handling
Total Float	`TF = Lj − Ei − tij`	Keep negative
Free Float	`FF = Ej − Ei − tij`	Set to 0 if negative
Independent Float	`IF = Ej − Li − tij`	Set to 0 if negative

Memory Aid

Only Total Float can be negative (project deadline dependent)
FF & IF must be ≥ 0 (network logic only)

📝 Key Terminology

Ei, Li = Event times at start node i
Ej, Lj = Event times at end node j
tij = Duration of activity i→j
Critical Path = Path with zero total float

7) Queuing Theory

📐 Integration Essentials for Queuing

Basic Integration Rule

[ \int e^{kx} dx = \frac{1}{k} e^{kx} + C ] Remember: Divide by k, keep ( e^{kx} )

Definite Integrals

[ \int_{a}^{b} f(x) dx = \big[ F(x) \big]_{a}^{b} = F(b) - F(a) ]

The Magic Rule

[ e^{-\infty} = 0 \quad \text{✅} \quad e^{\infty} = \infty \ \text{(not used)} ]

Why ( e^{-\infty} = 0 )

[ e^{-x} = \frac{1}{e^x} \quad \text{→} \quad \text{As } x \to \infty, \ e^x \to \infty, \ \frac{1}{e^x} \to 0 ]

Simple: Huge denominator → fraction → 0

Queuing Probability Formula

[ P(T > t) = \int_{t}^{\infty} \mu e^{-\mu x} dx = e^{-\mu t} ]

🎯 Probability Formula Selector

Use ( P(Q \geq n) = \rho^n ) when

Keywords: wait, busy, in use, delay

"Probability a person has to wait"
"Probability server is busy"
"Fraction of time phone is in use"

Use ( P(Q \leq n) = 1 - \rho^{n+1} ) when

Keywords: at most, no more than, within capacity

"Probability at most n customers"
"Probability no more than n in system"

Use ( P_n = (1-\rho)\rho^n ) when

Keywords: exactly, precisely, steady-state

"Probability of exactly n customers"
"Steady-state probability"

👥 Queuing Notation

Symbol	Meaning
Lₛ	Expected number of customers in system (service + queue)
Lq	Expected number of customers in queue (waiting only)
Lₙ	Expected length of non-empty queue
Wₛ	Expected waiting time in system (service + queue)
Wq	Expected waiting time in queue (waiting only)

Quick Examples

"Average waiting time" → Wq
"Average number in shop" → Lₛ
"Time until service completion" → Wₛ
"Number waiting for service" → Lq
"Length when queue exists" → Lₙ

💡 Exam Strategy

English Comprehension Tips

Spot keywords to select correct formula
Practice pattern recognition
Skip if truly unclear (better than wrong formula)

Integration Shortcuts

( \int_{t}^{\infty} e^{-kx} dx = \frac{1}{k} e^{-kt} )
Upper limit ∞ → always gives 0 for ( e^{-k\infty} )

You've cracked the code! Understanding the logic beats pure memorization. 💪

8) Economic Order Quantity (EOQ)

🎯 What is EOQ?

EOQ = Optimal order size per purchase that minimizes total cost

The Balance

🚚 Order too much → High storage costs
📦 Order too little → High ordering costs
✅ EOQ → Perfect balance

📊 Key Formulas & Concepts

EOQ Formula

[ EOQ = \sqrt{\frac{2DC_0}{C_h}} ] Where:

D = Annual demand
C₀ = Ordering cost per order
Cₕ = Holding cost per unit per year

Orders Per Year

[ \text{Number of Orders} = \frac{\text{Annual Demand}}{EOQ} ]

💡 Practical Example

Given:

Annual demand = 12,000 units
EOQ = 2,000 units

Calculation: [ \text{Orders per year} = \frac{12,000}{2,000} = 6 ]

Meaning:

6 orders per year
2,000 units per order

🎓 Quick Summary

Term	Represents
EOQ	Order size per purchase
Annual Demand/EOQ	Number of orders per year
Total Cost	Storage + Ordering costs

EOQ finds the sweet spot between ordering and holding costs! ✅

9) Floyd-Warshall Algorithm

🎯 Exam Strategy: Method vs Shortcut

Official Formula

[ d_{ij}^{(k)} = \min\left( d_{ij}^{(k-1)},\ d_{ik}^{(k-1)} + d_{kj}^{(k-1)} \right) ]

Smart Approach (Recommended)

Write formula at start (shows understanding)
Use visual shortcut for calculations:
- Look at row k and column k
- Check if d[i][k] + d[k][j] < d[i][j]
Present neat matrices with explanations

📊 Professional Presentation

Step 1: Write the formula
Step 2: Show D⁽⁰⁾ (initial matrix)
Step 3: Show D⁽¹⁾ with note: "Using vertex 1 as intermediate"
Step 4: Continue to final matrix

Why this works:

✅ Examiner sees you know formal method
✅ You save time with visual approach
✅ Guaranteed method marks + efficiency

10) Ford-Fulkerson Algorithm

🔀 Path Selection Strategies

Two Approaches

Approach	Where Edges Are Used	Efficiency
Simple / Naive	Only in the original graph (forward edges with capacity > 0)	Slower, more steps, may not find max flow
Full / Standard Method	In the residual graph (uses both forward and backward edges)	Faster, guaranteed to find max flow

🎯 Exam Recommendation: Use FULL Method

Why?

It's the actual algorithm – the "simple" version is incomplete.
More efficient in steps and time.
Examiners expect the use of the residual graph (backward edges).
Full marks guaranteed for demonstrating the complete concept.

Simple Rules for the Residual Graph

You are finding paths in the Residual Graph.
Residual Forward Edge: Exists if capacity - flow > 0
Residual Backward Edge: Exists if flow > 0 (it represents the capacity to cancel or push back existing flow).
Stop when: No more augmenting paths exist in the residual graph.

💡 The Critical Clarification

When you write the augmenting path in your table, you are describing a walk through the Residual Graph.

If you traverse a residual forward edge from node u to v, you write u → v.
If you traverse a residual backward edge from node p to q (which corresponds to reducing flow on the original edge q → p), you still write p → q.

You ONLY use the → arrow in your path list. The "backward" nature is an property of the original edge you are modifying, not the path you are taking.

Exam Presentation

State: "Using the Ford-Fulkerson method on the residual graph..."
Show your table with all augmenting paths using only → arrows.
Explain in words if a step used a backward edge from the original graph (e.g., "This step uses the residual backward edge B→C to cancel 2 units of flow that were previously sent along C→B").
Stop when no augmenting paths exist in the residual graph.

This is the professionally accepted method! ✅

FilesExpand file tree

DOUBTS.md

Latest commit

History