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

1. LINEAR PROGRAMMING (LP)

1.1 Formulation of LP Problems

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

• Objective Function: Linear function to be maximized (profit) or minimized (cost).

$$\text{Maximize/Minimize } Z = c_1x_1 + c_2x_2 + ... + c_nx_n$$

• Constraints: Linear inequalities/equations representing resource limits.

$$a_{11}x_1 + a_{12}x_2 + ... \le, =, \ge b_1$$

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

[!TIP]

Exam Focus: Converting word problems into standard LP form is a very high-frequency question. Clearly define variables first.

1.2 Simplex Method (Maximization with ≤ constraints)

1. Convert to Standard Form: Add slack variables \(s_i \ge 0\) to \(\le\) constraints.

2. Initial Tableau: Set up with basic variables (slacks) and non-basic (original) at zero.

3. Pivot Operation:

   • Entering Variable: Column with most positive \(c_j - z_j\) (net evaluation).

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

   • Pivot Element: Intersection of entering column & leaving row.

4. Iterate until all \(c_j - z_j \le 0\).

5. Optimal Solution: Read from final tableau. Basic variables = values; non-basic = 0.

6. Shadow Price (Dual Value): Value in 'Value' column for a slack row = marginal worth of one extra unit of that resource.

[!TIP]

Common Pitfall: Forgetting to update the entire row during pivot. Use row operations: New Row = Old Row – (Pivot Element × Pivot Row).

1.3 Special Cases

[!TIP]

For \(\ge\) or \(=\) constraints, use Big-M (penalty \(-M\) for max, \(+M\) for min) or Two-Phase (Phase I: min sum of artificials).

2. TRANSPORTATION PROBLEMS (TP)

2.1 Problem Structure & Balanced vs. Unbalanced

• Matrix: Sources (Rows) with Availabilities \(a_i\), Destinations (Columns) with Requirements \(b_j\), Cost \(c_{ij}\).

• Balanced: \(\sum a_i = \sum b_j\).

• Unbalanced: Add Dummy Row (if \(\sum a_i > \sum b_j\)) or Dummy Column (if \(\sum b_j > \sum a_i\)) with zero cost. For penalties, use penalty cost in dummy column.

2.2 Initial Basic Feasible Solution (IBFS)

[!TIP]

VAM Steps: Penalty → Select Row/Col → Min Cost Cell → Allocate → Cross-out Row/Col → Repeat.

2.3 Optimality Test: MODI (U-V) Method

1. For IBFS with \(m+n-1\) allocations, set \(u_1 = 0\).

2. Compute \(v_j = c_{ij} - u_i\) for allocated cells.

3. Compute Opportunity Cost \(\Delta_{ij} = c_{ij} - (u_i + v_j)\) for unallocated cells.

4. Optimality: All \(\Delta_{ij} \ge 0\) (minimization).

5. If not optimal, select most negative \(\Delta_{ij}\) for improvement.

2.4 Improving Non-Optimal Solution

1. Form closed loop for selected cell \((p,q)\).

2. Allocate \(\theta = \min\) (allocations at \(-\) cells in loop).

3. Adjust: \(+ \theta\) at \(+\) cells, \(- \theta\) at \(-\) cells.

4. New solution is basic & feasible. Repeat MODI.

2.5 Special Cases in TP

[!TIP]

Penalty Problem (Jun 2025): Create dummy destination 'D' with penalty costs. Solve as standard minimization TP.

3. INVENTORY MANAGEMENT

3.1 Economic Order Quantity (EOQ) Model

Assumptions: Constant demand \(D\), instantaneous replenishment, fixed ordering cost \(S\), fixed holding cost \(H\) per unit/year, no shortages.

$$ \boxed{EOQ = \sqrt{\frac{2DS}{H}}} $$

• Number of Orders/year: \(N = D / EOQ\)

• Cycle Time: \(T = 365 / N\) days (or \(1/N\) years)

• Total Annual Cost (TAC): \(TAC = \frac{EOQ \cdot H}{2} + \frac{D}{EOQ} \cdot S\)

3.2 EOQ with Finite Production Rate (\(P > D\))

• Assumption: Production rate \(P\) > demand rate \(D\); gradual replenishment.

• Formula:

$$EOQ = \sqrt{\frac{2DS}{H \left(1 - \frac{D}{P}\right)}}$$

• Max Inventory: \(I_{max} = EOQ \left(1 - \frac{D}{P}\right)\)

3.3 EOQ with Price Discounts

Procedure:

1. Compute EOQ at each price break.

2. Feasibility Check: Is EOQ within the price break's quantity range?

3. For infeasible EOQs, use minimum quantity of that price break.

4. Compute TAC for all feasible EOQs and at all break quantities.

5. Select minimum TAC.

[!TIP]

Always calculate TAC at price break quantities even if EOQ is feasible, because lower price may offset higher holding cost.

3.4 Inventory Control Systems

[!TIP]

ABC vs VED: ABC = monetary value; VED = functional criticality. Often used together (e.g., VED for A-items).

4. SUPPLY CHAIN MANAGEMENT (SCM)

4.1 Core Concepts & Flows

• Three Key Flows:

  • Material Flow: Physical movement of goods.

  • Information Flow: Orders, forecasts, status updates.

  • Money/Cash Flow: Payments, credit, settlements.

• Objectives: Reduce total cost, improve service level, increase responsiveness.

4.2 Key SCM Strategies & Phenomena

4.3 Logistics in SCM

[!TIP]

High-Frequency: "Explain importance of inbound/outbound logistics" – focus on cost impact, customer satisfaction, and competitive advantage.

4.4 Evolution & Integration

• MRP (Material Requirements Planning): Material planning for dependent demand.

• MRP II (Manufacturing Resource Planning): Integrated capacity, shop floor, and financial planning.

• ERP (Enterprise Resource Planning): Enterprise-wide integration (finance, HR, sales, etc.).

• SCM: Extended network beyond enterprise (suppliers, customers, logistics partners). Focus on coordination & collaboration.

4.5 Other Aspects

• Outsourcing in SCM: Contracting non-core activities (e.g., logistics) to 3PLs. Benefits: Focus on core, cost savings, expertise. Risks: Loss of control, dependency, hidden costs.

• Role of Inventory: Buffer against uncertainty (demand, supply). Trade-off: Higher inventory → higher holding cost but better service level.

5. QUEUING THEORY

5.1 Basic Structure & Terminology

Components: Arrival Process, Service Mechanism, Queue Discipline, Population Size, System Capacity.

• Queue Disciplines (High Frequency):

  • FIFO/FCFS: First-In-First-Out (most common).

  • LIFO/LCFS: Last-In-First-Out.

  • SIRO: Service-In-Random-Order.

  • Priority: Based on assigned priority.

  • Random: Random selection from queue.

5.2 M/M/1 Queue (Single Server)

Assumptions:

• Arrivals: Poisson process with rate \(\lambda\).

• Service Times: Exponential with rate \(\mu\).

• Single server (\(\infty\) queue, \(\infty\) population).

• Traffic Intensity: \(\rho = \lambda / \mu\) must be < 1 for steady-state. Performance Measures:

[!TIP]

Little's Law: \(L = \lambda W\) and \(L_q = \lambda W_q\) (holds for most queues).

5.3 Probability Distributions

• Exponential Distribution (Service Time):

$$P(T > t) = e^{-\mu t}$$

**Memoryless Property:** Future independent of past.

• Poisson Distribution (Arrivals in interval \(t\)):

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

[!TIP]

Exam Problem: "Probability service takes > 15 mins" → Use \(P(T > t) = e^{-\mu t}\) with \(\mu\) from "20 customers/hour" → \(\mu = 20/60 = 1/3\) per minute.

6. PROJECT MANAGEMENT (PERT/CPM)

6.1 Network Diagram

• AOA (Activity-on-Arrow): Arrows = activities, nodes = events. Dummy activity (0 time) used for logic.

• AON (Activity-on-Node): Nodes = activities, arrows = precedence. More common (no dummies needed).

• Forward Pass: \(ES = \max(EF \text{ of predecessors})\); \(EF = ES + \text{time}\).

• Backward Pass: \(LF = \min(LS \text{ of successors})\); \(LS = LF - \text{time}\).

6.2 Critical Path Method (CPM)

• Deterministic time estimates.

• Float/Slack:

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

  • Free Float: \(FF = ES \text{ of next activity} - EF \text{ of current}\).

• Critical Path: Path with zero total float. Longest path determines project duration.

6.3 Program Evaluation and Review Technique (PERT)

• Probabilistic time estimates:

  • Optimistic (\(a\)): Best-case (if everything goes right).

  • Pessimistic (\(b\)): Worst-case (if everything goes wrong).

  • Most Likely (\(m\)): Most probable estimate.

• Expected Time:

$$\boxed{t_e = \frac{a + 4m + b}{6}}$$

• Variance:

$$\boxed{\sigma^2 = \left(\frac{b-a}{6}\right)^2}$$

6.4 Project Analysis with PERT

1. Build network with \(t_e\).

2. Find critical path (using CPM rules).

3. Project Expected Duration (\(T_e\)): Sum of \(t_e\) on critical path.

4. Project Variance (\(\sigma_p^2\)): Sum of variances (\(\sigma^2\)) on critical path.

5. Probability of Completion by Due Date (\(d\)):

$$Z = \frac{d - T_e}{\sqrt{\sigma_p^2}}$$

Use standard normal table for \(P(Z \le z)\).

[!TIP]

Critical Path may change when considering variance! Path with largest \(T_e / \sqrt{\sigma_p^2}\) is often critical for probability.

6.5 Phases of Project Management

1. Initiation

2. Planning

3. Execution

4. Monitoring & Controlling

5. Closure

6.6 PERT vs CPM

7. GAME THEORY (Introduction)

7.1 Basic Concepts

• Players: Decision-makers.

• Strategies: Possible actions.

• Payoff Matrix: Gains for each strategy combination.

• Zero-Sum Game: One player's gain = other's loss.

• Non-Zero-Sum: Gains/losses don't necessarily sum to zero.

7.2 Solution Methods

• Pure Strategies:

  • Saddle Point: Element that is min in row & max in column.

  • Maximin (Row Player): Maximize the minimum payoff (security level).

  • Minimax (Column Player): Minimize the maximum loss.

  • Value of Game (\(v\)): Payoff at saddle point.

  • Dominance Rule: If row \(i\) ≤ row \(j\) for all columns, row \(i\) is dominated (inferior) and can be deleted. Similarly for columns.

• Mixed Strategies: (Brief) When no saddle point, players randomize over strategies. Value solved via expected payoff equations.

7.3 Assumptions

• Rationality (players maximize payoff).

• Knowledge of payoffs & opponent's strategies.

• Simultaneous choice (no knowledge of opponent's move).

• Fixed number of players.

8. ADVANCED HEURISTIC & META-HEURISTIC ALGORITHMS

8.1 Definitions

• Heuristic: Problem-specific, rule-of-thumb procedure for quick, feasible solutions. Not guaranteed optimal (e.g., Nearest Neighbor for TSP).

• Meta-heuristic: General-purpose framework that guides heuristics to escape local optima. Applicable to wide range of problems.

  • Examples: Simulated Annealing, Genetic Algorithms, Tabu Search, Ant Colony Optimization.

8.2 Context in OR

• Used for complex combinatorial optimization problems (NP-hard) where exact methods (e.g., Simplex) are computationally infeasible for large instances.

• Applications: Large-scale scheduling, vehicle routing, facility layout, network design.

• Goal: Find near-optimal solution in reasonable time.

[!TIP]

Exam Short Note: Distinguish: Heuristic = specific rule; Meta-heuristic = general framework that controls heuristics. Mention 1-2 examples.