Artificial Intelligence Techniques (ME-703 (B)) - Unit 3 Short Notes

UNIT 3: Artificial Intelligence Techniques (Based on Past Exam Papers)

1. Linear Programming (LP)

Formulation of LP Problems

• Decision Variables: Quantities to be determined (e.g., \(x_1, x_2\)).

• Objective Function: Linear function to maximize (profit) or minimize (cost).

  Example: Maximize \(Z = c_1x_1 + c_2x_2\).

• Constraints: Linear inequalities/equations representing resource limits.

• Non-negativity: \(x_i \ge 0\).

Standard Form (Maximization):

1. All constraints are \(\le\) type.

2. All variables \(\ge 0\).

3. Slack variables added to convert \(\le\) to \(=\).

[!TIP]

Exam Focus: Converting word problems to LP is frequently asked (e.g., Jun 2025, Dec 2024, May 2024). Identify variables, objective, and constraints clearly.

Simplex Method

Steps:

1. Convert to standard form (add slack/surplus/artificial variables).

2. Identify initial basic feasible solution (BFS) from identity matrix (slack variables as basics).

3. Pivot Operation:

   • Entering variable: Most negative coefficient in objective row (for maximization).

   • Leaving variable: Minimum positive ratio test (RHS / pivot column).

4. Update tableau via row operations.

5. Optimality Test: All objective row coefficients \(\ge 0\) → optimal.

6. Special Cases:

   • Multiple optimal solutions: Zero coefficient in objective row for non-basic variable at optimum.

   • Unbounded solution: All pivot column entries \(\le 0\).

   • Infeasible: Use two-phase method (Minimize sum of artificial variables in Phase I).

[!TIP]

Common Pitfall: Forgetting to update all rows correctly during pivot. Always make pivot element = 1 and eliminate other entries in pivot column.

2. Transportation Problems

Problem Structure

• Balanced: Total supply = Total demand.

• Unbalanced: Add dummy row/column (cost = 0) to balance.

• LP Formulation: Minimize \(\sum \sum c_{ij}x_{ij}\) subject to row/column sums.

Initial Basic Feasible Solution (IBFS)

Vogel’s Approximation Method (VAM)

1. For each row/column, compute penalty = difference between two smallest costs.

2. Select row/column with highest penalty.

3. Allocate as much as possible to the lowest cost cell in that row/column.

4. Adjust supply/demand, cross out satisfied row/column, recalc penalties.

5. Repeat until all allocations done.

North-West Corner Rule

1. Start at top-left cell (row 1, col 1).

2. Allocate \(\min(\text{supply}_i, \text{demand}_j)\).

3. Move right if demand exhausted, down if supply exhausted.

4. Repeat until all supply/demand met.

Degeneracy in Transportation

• Definition: IBFS has fewer than \((m+n-1)\) positive allocations.

• Cause: Simultaneous exhaustion of supply and demand.

• Resolution:

  • Assign a very small \(\epsilon > 0\) to one zero cell (perturbation method).

  • Or introduce artificial variable with high cost \(M\) (similar to two-phase).

Transportation with Penalties

• Dummy destination for unfulfilled demand.

• Penalty cost added to transportation cost for dummy column.

• Solve as standard balanced TP with dummy.

Optimality Test (MODI Method)

1. Compute u_i, v_j from \(u_i + v_j = c_{ij}\) for basic cells.

2. For non-basic cell \((i,j)\), calculate \(\Delta_{ij} = c_{ij} - (u_i + v_j)\).

3. If all \(\Delta_{ij} \ge 0\) → optimal.

4. If any \(\Delta_{ij} < 0\), select most negative for allocation.

[!TIP]

Exam Focus: VAM and degeneracy are repeatedly asked (Jun 2025, Dec 2024, May 2024, Nov 2023). Practice both methods thoroughly.

3. Inventory Management

Economic Order Quantity (EOQ) Model

Assumptions:

• Constant demand rate \(D\).

• Instantaneous replenishment.

• No shortages.

• Fixed ordering cost \(S\).

• Constant holding cost \(H\) per unit per year.

Derivation:

Total Cost \(TC = \frac{D}{Q}S + \frac{Q}{2}H\)

Minimize \(TC\): \(\frac{d(TC)}{dQ} = 0 \Rightarrow Q^* = \sqrt{\frac{2DS}{H}}\)

Key Formulas:

• EOQ: \(Q^* = \sqrt{\frac{2DS}{H}}\)

• Number of orders: \(N = \frac{D}{Q^*}\)

• Cycle time: \(T = \frac{365}{N}\) days (or \(\frac{Q^*}{D}\) years)

• Total annual cost: \(TC^* = \sqrt{2DSH} + PD\) (if purchase cost \(P\) included)

[!TIP]

Unit Consistency: Ensure \(D, S, H\) are in same time unit (e.g., yearly). Common mistake: mixing monthly \(D\) with yearly \(H\).

EOQ with Quantity Discounts

Price Break Analysis:

1. Compute EOQ at lowest price (ignore discount for EOQ calc).

2. If EOQ feasible (within price break range), compute \(TC\).

3. If not, compute \(TC\) at each break point (minimum order for discount).

4. Choose order quantity with lowest \(TC\).

Decision Rule: Compare total costs at:

• EOQ (at current price)

• Each break quantity (at discounted price)

ABC Analysis

• Classification by annual usage value: \( \text{Usage Value} = \text{Annual Demand} \times \text{Unit Cost} \)

• A-items: ~70% of value, ~10% of items (tight control).

• B-items: ~20% of value, ~20% of items (moderate control).

• C-items: ~10% of value, ~70% of items (loose control).

VED Analysis

• Vital: Critical items (stock always).

• Essential: Important but not critical.

• Desirable: Can be stocked minimally or procured as needed.

• Often used for spare parts.

Advantages of ABC/VED:

• Prioritization of resources.

• Efficient inventory control.

• Reduced carrying costs.

• Focus on high-value/critical items.

Role of Inventory in Logistics Supply Chain

• Buffer against demand/supply uncertainty.

• Economies of scale in ordering/transportation.

• Customer service: Stock availability → satisfaction.

• Cost trade-off: Holding vs. ordering vs. shortage costs.

[!TIP]

Exam Focus: EOQ calculations appear every year (Jun 2025, Dec 2024, May 2024, Nov 2023). ABC/VED advantages are short-note questions.

4. Supply Chain Management (SCM) Concepts

Bullwhip Effect

• Definition: Demand variability amplifies as orders move upstream (from retailer to manufacturer).

• Causes:

  1. Demand forecast updating.

  2. Order batching.

  3. Price fluctuations (forward buying).

  4. Rationing and shortage gaming.

• Consequences:

  • Excess inventory fluctuations.

  • Poor customer service (stockouts or overstock).

  • Inefficient resource allocation.

• Mitigation:

  • Information sharing (POS data to suppliers).

  • Vendor-Managed Inventory (VMI).

  • Eliminate incentives for order amplification.

Flows in SCM

Logistics in SCM

• Inbound Logistics: Activities from suppliers to production (procurement, receiving, material handling).

  Importance: Ensures timely, cost-effective material supply; impacts production continuity.

• Outbound Logistics: Activities from production to customer (distribution, delivery, customer service).

  Importance: Directly affects customer satisfaction, delivery performance, and market responsiveness.

Cross-Docking

• Concept: Inbound goods directly transferred to outbound vehicles without storage.

• Process: Receiving → sorting → shipping (minimal handling time).

• Advantages:

  • Reduced inventory holding costs.

  • Faster throughput.

  • Lower handling/damage risk.

• Disadvantages:

  • Requires precise coordination and timing.

  • High initial investment (facilities, IT).

  • Vulnerable to disruptions.

Outsourcing in SCM

• Rationale: Focus on core competencies, cost reduction, access to expertise, scalability.

• Benefits:

  • Cost savings (labor, infrastructure).

  • Flexibility.

  • Improved service levels (specialized providers).

• Risks:

  • Loss of control.

  • Dependency on supplier.

  • Quality issues, confidentiality risks.

  • Hidden costs.

Evolution: MRP → ERP → SCM

SCM and e-Business

• Linkages:

  • E-procurement: Online purchasing, auctions.

  • Electronic Data Interchange (EDI): Standardized electronic documents.

  • Online marketplaces: B2B platforms.

  • Real-time information sharing: Visibility across chain.

• Impact: Increased efficiency, transparency, responsiveness; reduced transaction costs.

Expenditure and Opportunities in SCM

• Major Cost Areas:

  • Transportation (largest).

  • Inventory carrying.

  • Warehousing.

  • Administration/order processing.

• Opportunities:

  • Process re-engineering.

  • Technology adoption (IoT, AI, blockchain).

  • Collaboration and partnerships.

  • Sustainable practices.

[!TIP]

Exam Focus: Bullwhip effect, cross-docking, MRP→ERP→SCM, and inbound/outbound logistics are repeated short-note topics (Jun 2025, Dec 2024, May 2024, Nov 2023).

5. Project Management: PERT/CPM

Network Diagrams

• AOA (Activity-on-Arrow): Arrows represent activities, nodes are events.

• AON (Activity-on-Node): Nodes represent activities, arrows show dependencies (more common).

• Logical Relationships:

  • FS (Finish-to-Start): Most common.

  • SS, FF, SF (less common).

• Dummy Activity: Zero duration, used to show dependency without time/cost.

Critical Path Method (CPM)

Forward Pass (from start):

• Earliest Start (ES): Max of all predecessors' EF.

• Earliest Finish (EF): \(ES + \text{duration}\). Backward Pass (from end):

• Latest Finish (LF): Min of all successors' LS.

• Latest Start (LS): \(LF - \text{duration}\). Float/Slack:

• Total Float = \(LS - ES\) or \(LF - EF\).

• Critical Path: Activities with zero total float.

Program Evaluation and Review Technique (PERT)

• Three-Time Estimates:

  • \(O\) (Optimistic): Minimum time if all goes well.

  • \(M\) (Most likely): Most probable time.

  • \(P\) (Pessimistic): Maximum time if all goes wrong.

• Expected Time: \(T_E = \frac{O + 4M + P}{6}\)

• Variance: \(\sigma^2 = \left(\frac{P - O}{6}\right)^2\)

Project Duration and Probability

1. Project Mean = Sum of \(T_E\) on critical path.

2. Project Variance = Sum of \(\sigma^2\) on critical path.

3. Z-score: \(Z = \frac{\text{Due Date} - \text{Project Mean}}{\sqrt{\text{Project Variance}}}\)

4. Use standard normal table to find probability.

PERT vs. CPM

Phases of Project Management

1. Initiation: Define project, feasibility.

2. Planning: Scope, schedule, budget, resources.

3. Execution: Coordinate resources, implement plan.

4. Monitoring & Controlling: Track progress, manage changes.

5. Closure: Handover, documentation, lessons learned.

[!TIP]

Exam Focus: Drawing network diagrams, finding critical path (Jun 2025), PERT time calculations, and probability of completion (Nov 2023) are common. Distinguish PERT vs. CPM clearly.

6. Queuing Theory

Basic Concepts

• Arrival Process: Often Poisson distribution with rate \(\lambda\) (avg arrivals per unit time).

  Probability of \(n\) arrivals in time \(t\):

  \[ P(n) = \frac{(\lambda t)^n e^{-\lambda t}}{n!} \]

• Service Time: Often exponential distribution with rate \(\mu\) (avg services per unit time).

  Probability service time > \(T\):

  \[ P(T) = e^{-\mu T} \]

• System Characteristics:

  • Number of servers (\(s\)).

  • Queue capacity (finite/infinite).

  • Service discipline (FCFS, LCFS, priority).

Queue Disciplines

1. FCFS (First-Come-First-Served): Most common.

2. LCFS (Last-Come-First-Served): Stack-like.

3. Priority:

   • Preemptive: Higher priority interrupts.

   • Non-preemptive: Wait in queue.

4. Random Service: Arbitrary selection.

Probability Calculations (Past Paper Examples)

• Exponential service time: \(P(\text{service} > T) = e^{-\mu T}\)

  Example: \(\mu = 20\) customers/hour → \(\mu = \frac{20}{60} = \frac{1}{3}\) per minute.

  \(P(>15 \text{ min}) = e^{-(1/3) \times 15} = e^{-5}\).

• Poisson arrivals: \(P(n \text{ arrivals in } t) = \frac{(\lambda t)^n e^{-\lambda t}}{n!}\)

  Example: \(\lambda = 8\)/hour → \(\lambda = \frac{8}{60} \times 40 = \frac{16}{3}\) in 40 min.

  \(P(6 \text{ arrivals}) = \frac{(\frac{16}{3})^6 e^{-16/3}}{6!}\).

[!TIP]

Exam Focus: Exponential and Poisson probability calculations are direct application questions (Jun 2025, Dec 2024, May 2024, Nov 2023). Convert units consistently (hour ↔ minute).

7. Game Theory

Strategic Games

• Components: Players, strategies, payoffs.

• Two-Person Zero-Sum: One’s gain = other’s loss (payoff matrix \(A\) for row player, \(-A\) for column).

• Non-Zero-Sum: Sum of payoffs ≠ 0 (e.g., Prisoner’s Dilemma).

Pure and Mixed Strategies

• Pure Strategy: Deterministic choice (specific row/column).

• Mixed Strategy: Probability distribution over pure strategies (randomized choice).

• Value of Game: Expected payoff when both use optimal mixed strategies.

Dominance Rule

• Row Dominance: Row \(i\) dominates row \(j\) if \(a_{ik} \ge a_{jk}\) for all \(k\), and \(>\) for at least one \(k\).

• Column Dominance: Column \(i\) dominates column \(j\) if \(a_{ki} \le a_{kj}\) for all \(k\), and \(<\) for at least one \(k\).

• Reduction: Eliminate dominated rows/columns to simplify matrix.

Basic Assumptions

1. Rationality: Players maximize their payoffs.

2. Common Knowledge: Rules and payoffs known to all.

3. Simultaneous/Sequential Moves: Depending on game structure.

[!TIP]

Exam Focus: Dominance rule and pure/mixed strategies are asked (Dec 2024, Nov 2023). Practice reducing matrices step-by-step.

8. Advanced Optimization Techniques

Heuristic Algorithms

• Definition: Rule-based, intuitive methods not guaranteeing optimality.

• Examples:

  • Greedy: Choose best immediate option (e.g., shortest edge first for TSP).

  • Nearest Neighbor (TSP): Start at a city, repeatedly visit nearest unvisited.

  • Local Search: Start with solution, improve by small changes.

• Use When: Exact methods too slow, NP-hard problems, good approximate solution acceptable.

Metaheuristic Algorithms

• Definition: High-level frameworks guiding heuristics to explore solution space globally.

• Examples:

  • Genetic Algorithms: Evolution-inspired (selection, crossover, mutation).

  • Simulated Annealing: Thermal process analogy (accept worse solutions with probability to escape local optima).

  • Tabu Search: Memory-based (avoid recent moves via tabu list).

• Applications: Complex combinatorial optimization, non-linear, multi-modal problems.

Network Logics (Project Management)

• Activity Dependencies: Logical constraints (FS, SS, FF, SF).

• Construction Rules:

  • No loops (cycles).

  • Single start and end node.

  • All activities represented.

• Dummy Activities: Used to:

  • Show dependency without time/cost.

  • Maintain network consistency (unique numbering).

  • Preserve logic when activities share predecessors/successors.

[!TIP]

Exam Focus: Heuristic vs. metaheuristic definitions and examples are asked as short notes (Nov 2023). Network logic construction is part of PERT/CPM diagrams.

\boxed{\text{End of Unit 3 Notes}}