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

I. LINEAR PROGRAMMING (LP)

A. Problem Formulation

• Decision Variables: Quantities to be determined (e.g., number of deluxe/ordinary models).

• Objective Function: Maximize profit or minimize cost, expressed linearly in variables.

• Constraints: Linear inequalities/equalities from resource limits (labor, budget, space).

• Non-negativity: Variables ≥ 0.

• Example: Resource allocation with skilled/semi-skilled labor constraints (Jun 2025, Nov 2023).

B. Simplex Method

Steps for Maximization:

1. Standard Form: Convert all ≤ constraints to equalities by adding slack variables (≥ 0). Objective: Maximize $$\displaystyle Z = c^T x $$.

2. Initial Tableau: Set up with slack variables as basic. Objective row: $$\displaystyle Z - \sum c_j x_j = 0 $$.

3. Optimality Test: Compute net evaluation row ($$\displaystyle C_j - Z_j $$). If all ≤ 0, current solution is optimal.

4. Entering Variable: Choose non-basic variable with most positive $$\displaystyle C_j - Z_j $$.

5. Leaving Variable: Minimum ratio test: $$\displaystyle \min \left( \frac{b_i}{a_{ij}} \right) $$ for $$\displaystyle a_{ij} > 0 $$.

6. Pivot: Make entering variable basic, update tableau via row operations.

7. Repeat until optimal.

[!TIP] Common pitfall: Forgetting to update all rows after pivot; misreading final values (basic variables from tableau columns).

C. Degeneracy in LP

• Definition: A basic feasible solution where at least one basic variable is zero.

• Occurrence: When minimum ratio test yields tie, or multiple constraints intersect at a vertex.

• Resolution:

  • Artificial Variables (Big M or Two-phase method) to avoid cycling.

  • Perturbation (ε): Add tiny ε to RHS to break ties.

  • Bland’s Rule: Choose smallest index for entering/leaving to prevent cycling.

II. TRANSPORTATION PROBLEMS

A. Problem Structure & Formulation

• Balanced: Total supply = Total demand.

• Unbalanced: Add dummy row (if supply < demand) or dummy column (if supply > demand) with zero transportation cost.

B. Initial Basic Feasible Solutions (IBFS)

1. Vogel’s Approximation Method (VAM)

Steps:

1. For each row/column, compute penalty = |second smallest cost – smallest cost|.

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 exhausted row/column.

5. Recalculate penalties for remaining rows/columns.

6. Repeat until all allocations made.

7. If penalty tie, choose any; if multiple min-cost cells, choose any.

[!TIP] VAM often yields near-optimal solution; better than NWC or LCM.

2. North-West Corner Rule

• Start at top-left cell (row1, col1).

• Allocate $$\displaystyle \min(\text{supply}_i, \text{demand}_j) $$.

• Subtract allocation; move right if demand exhausted, down if supply exhausted.

• Continue until all supply/demand satisfied.

• Simple but may ignore costs.

3. Least Cost Method

• Allocate to cell with lowest cost first, then adjust supply/demand.

C. Degeneracy in Transportation

• Cause: Number of positive allocations < $m + n - 1$ (where $m$=rows, $n$=columns).

• Resolution:

  • Allocate a very small $\epsilon$ (e.g., 0.001) to a zero cell to make it basic.

  • Adjust existing allocations slightly to create an extra positive cell.

D. Transportation with Penalties/Unfulfilled Requirements

• Add dummy destination (or origin) with penalty cost as transportation cost.

• Solve as standard balanced problem.

• Allocation to dummy indicates unfulfilled demand; total cost includes penalties.

III. INVENTORY MANAGEMENT

A. Economic Order Quantity (EOQ) Model

1. Basic EOQ (No Shortages)

Assumptions: Constant demand $D$, fixed ordering cost $S$, constant holding cost $H$ per unit per year, instantaneous replenishment, no shortages.

• EOQ Formula:

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

• Number of orders per year: $$\displaystyle N = \frac{D}{EOQ} $$

• Cycle time: $$\displaystyle T = \frac{EOQ}{D} $$ years

• Total annual cost:

$$TC = \frac{D}{Q}S + \frac{Q}{2}H + PD$$

Minimum at EOQ: $$\displaystyle TC_{\min} = \sqrt{2DSH} + PD $$

[!TIP] Ensure consistent time units: if $D$ annual, $S$ and $H$ must be annual.

2. EOQ with Quantity Discounts

• Price-break: Unit price $P$ decreases for order quantities above breakpoints.

• Steps:

  1. Compute EOQ for each price using $$\displaystyle H = i \cdot P $$ (if holding cost is percentage $i$ of price).

  2. Check feasibility: EOQ must be within price break range; if not, use break quantity.

  3. Calculate total cost $$\displaystyle TC = \frac{D}{Q}S + \frac{Q}{2}H + PD $$ for each feasible $Q$.

  4. Choose $Q$ with minimum $TC$.

• Decision rule: If EOQ at lower price is feasible, it is optimal; else, compare $TC$ at breakpoints.

3. Holding Cost Variations

• Monthly holding cost → annual: $$\displaystyle H_{\text{annual}} = H_{\text{monthly}} \times 12 $$.

• Holding cost as percentage: $$\displaystyle H = i \times C $$, where $i$ = holding cost rate, $C$ = unit cost.

B. ABC Analysis & VED Analysis

• ABC Analysis (by annual usage value):

  • A-items: High value (~70-80% total), few items (~10-20%). Tight control, frequent review.

  • B-items: Moderate value (~15-25%), moderate items (~20-30%). Normal control.

  • C-items: Low value (~5-10%), many items (~50-70%). Loose control, bulk orders.

• VED Analysis (by criticality):

  • Vital: Critical for operations; high stock.

  • Essential: Important but manageable stock.

  • Desirable: Can be stocked minimally.

• Advantages: Focuses resources on important items, reduces inventory costs, improves availability.

IV. SUPPLY CHAIN MANAGEMENT (SCM) CONCEPTS

A. Flows in SCM

Coordination essential to synchronize flows and avoid inefficiencies.

B. Logistics in SCM

1. Inbound Logistics

• Activities: Procurement, transportation to facilities, receiving, inventory management.

• Importance: Reduces costs, ensures timely supply, quality control.

2. Outbound Logistics

• Activities: Finished goods storage, order processing, distribution, delivery, customer service.

• Importance: Directly impacts customer satisfaction, competitive advantage, repeat business.

C. Bull-Whip Effect

• Definition: Demand variability amplifies upstream in supply chain.

• Causes:

  1. Demand forecasting: Each stage forecasts based on orders, not actual demand.

  2. Order batching: Large, infrequent orders cause spikes.

  3. Price fluctuations: Promotions cause forward buying.

  4. Rationing and gaming: Over-ordering when supply scarce.

• Impact: Excess inventory, stockouts, inefficiencies, increased costs.

• Mitigation:

  • Information sharing: CPFR (Collaborative Planning, Forecasting, Replenishment).

  • Vendor Managed Inventory (VMI): Supplier manages inventory.

  • Eliminate incentives for order batching, stabilize prices.

D. Cross Docking

• Process: Unload inbound trucks, sort, directly load to outbound trucks with minimal storage (<24 hours).

• Advantages: Reduced handling/storage costs, faster throughput, lower inventory, improved freshness.

• Disadvantages: Requires high coordination, accurate scheduling, significant infrastructure; not suitable for all products.

• Applications: Retail (e.g., Walmart), perishable goods.

E. MRP, ERP & SCM Integration

• MRP (Material Requirements Planning): Calculates material needs from production schedule and BOM; focuses on manufacturing.

• ERP (Enterprise Resource Planning): Integrates all business functions (finance, HR, SCM, CRM) into a single system with real-time data.

• Evolution: MRP → MRP II → ERP.

• ERP’s role in SCM: Provides integrated platform for demand planning, inventory, procurement, logistics, enabling end-to-end visibility.

F. Additional SCM Topics

• Role of inventory in logistics systems: Buffer against uncertainty, enable economies of scale, but costly. Placement (e.g., distribution centers) balances service level and cost.

• Outsourcing in SCM: Contracting logistics to 3PLs. Benefits: focus on core, expertise, cost savings. Risks: loss of control, dependency.

• SCM & E-business linkage: E-business platforms (B2B, e-procurement) enable real-time transactions, information sharing, reducing costs and improving visibility.

• Expenditures and opportunities: Major costs: transportation, inventory, warehousing. Opportunities: optimization, technology (IoT, AI), collaboration, sustainability.

V. QUEUING THEORY

A. Basic Queueing Models

• Components:

  • Arrival process: e.g., Poisson (rate $\lambda$).

  • Service mechanism: e.g., exponential (rate $\mu$), $c$ servers.

  • Queue discipline: FIFO, LIFO, priority.

  • Capacity: Finite/infinite.

  • Population size: Finite/infinite.

• Kendall’s notation: $A/B/c$ where $A$=arrival distribution, $B$=service distribution, $c$=servers. Example: $M/M/1$.

B. Poisson Arrivals & Exponential Service

• Poisson arrivals: $$\displaystyle P(N(t)=n) = \frac{e^{-\lambda t} (\lambda t)^n}{n!} $$ for $n$ arrivals in time $t$.

• Exponential service: PDF $$\displaystyle f(t) = \mu e^{-\mu t} $$, $t \ge 0$; mean $1/\mu$; memoryless: $$\displaystyle P(T > s+t \mid T > s) = P(T > t) $$.

C. Probability Calculations

• Service time > $t$: $$\displaystyle P(T > t) = e^{-\mu t} $$.

• Number of arrivals in $t$: $$\displaystyle P(N(t)=n) = \frac{e^{-\lambda t} (\lambda t)^n}{n!} $$.

• Example (Jun 2025, May 2024): If $$\displaystyle \mu = 20 $$ customers/hour, $$\displaystyle P(\text{service} > 15 \text{ min}) = e^{-(20/60) \times 15} = e^{-5} \approx 0.0067 $$.

D. Queue Disciplines

• FIFO: First-in-first-out (fair, common).

• LIFO: Last-in-first-out (stack).

• SIRO: Service in random order.

• Priority: Based on criteria (e.g., urgency), preemptive or non-preemptive.

VI. PROJECT MANAGEMENT: PERT/CPM

A. Network Diagrams

• Activity-on-Arrow (AOA): Arrows = activities, nodes = events. Less common.

• Activity-on-Node (AON): Nodes = activities, arrows = dependencies. More flexible.

• Drawing: List activities with predecessors; for AON, draw nodes, connect with arrows from predecessor to successor.

  DiagramCANVAS: AON diagram with rectangular nodes labeled "Activity (duration)", arrows showing dependencies (FS by default)

B. Critical Path Method (CPM)

• Deterministic activity times.

• Forward Pass:

  • $ES$ (earliest start) of first activity = 0.

  • $$\displaystyle EF = ES + \text{duration} $$.

  • For activity $i$: $$\displaystyle ES_i = \max(EF_{\text{predecessors}}) $$.

• Backward Pass:

  • $LF$ (latest finish) of last activity = project duration.

  • $$\displaystyle LS = LF - \text{duration} $$.

  • For activity $i$: $$\displaystyle LF_i = \min(LS_{\text{successors}}) $$.

• Slack/Float: $LS - ES$ or $LF - EF$. Zero slack = critical.

• Critical Path: Longest path with zero slack; determines project duration.

C. Program Evaluation and Review Technique (PERT)

1. Time Estimates

• Optimistic ($O$): Best-case time.

• Pessimistic ($P$): Worst-case time.

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

2. Expected Time & Variance

• Expected time:

$$\boxed{t_e = \frac{O + 4M + P}{6}}$$

• Variance:

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

3. Project Completion Probability

• Project expected duration $$\displaystyle T_e = \sum t_e $$ on critical path.

• Project variance $$\displaystyle \sigma_p^2 = \sum \sigma^2 $$ on critical path (assuming independence).

• For due date $T$, compute Z-score:

$$Z = \frac{T - T_e}{\sigma_p}$$

• Use standard normal table to find $P(\text{completion by } T)$.

• Example (Nov 2023): $$\displaystyle T_e = 60 $$ weeks, $$\displaystyle \sigma_p^2 = 9 $$ ($$\displaystyle \sigma_p=3 $$). For $$\displaystyle T=66 $$, $$\displaystyle Z=2 $$, $P \approx 0.9772$.

D. PERT vs CPM

E. Applications

• Project planning, scheduling, resource allocation, crashing (time-cost trade-off), monitoring.

VII. GAME THEORY

A. Pure vs Mixed Strategies

• Pure strategy: Deterministic choice of one action.

• Mixed strategy: Probability distribution over actions (randomized choice).

B. Basic Assumptions

1. Rational players: Maximize own payoff.

2. Fixed payoffs: Known and constant.

3. Simultaneous moves: Players choose without knowing others’ actions.

4. Common knowledge: All know rules and payoffs.

C. Dominance Rule

• Dominant strategy: Strategy $A$ dominates $B$ if $A$ yields higher payoff than $B$ for all opponent’s choices (and strictly higher for at least one).

• Row/column dominance: Compare payoffs across all columns/rows.

• Reduction: Eliminate dominated strategies to simplify payoff matrix.

• Example (Dec 2024): Reduce matrix by removing strictly dominated rows/columns.

VIII. HEURISTICS & METAHEURISTICS

A. Heuristic Algorithms

• Definition: Problem-specific rules of thumb.

• Examples: Nearest neighbor for TSP, greedy for knapsack.

• Advantages: Fast, easy to implement, good for large instances.

• Limitations: No optimality guarantee, may converge to local optimum.

B. Metaheuristic Algorithms

• Definition: General frameworks for complex optimization.

• Examples: Genetic Algorithms (GA), Simulated Annealing (SA), Tabu Search (TS).

• Exploration vs Exploitation:

  • Exploration: Search new areas of solution space.

  • Exploitation: Refine current good solutions.

• Use: NP-hard problems where exact methods are infeasible.

IX. ADDITIONAL TOPICS FROM EXAMS

A. Phases of Project Management

1. Initiation: Define project, feasibility, charter.

2. Planning: Scope, schedule (PERT/CPM), resources, budget.

3. Execution: Carry out tasks, manage team.

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

5. Closure: Formal acceptance, handover, lessons learned.

B. Network Logics

• Dependency relationships (between activities):

  • FS (Finish-to-Start): Successor starts after predecessor finishes (most common).

  • SS (Start-to-Start): Successor starts after predecessor starts.

  • FF (Finish-to-Finish): Successor finishes after predecessor finishes.

  • SF (Start-to-Finish): Successor finishes after predecessor starts (rare).

• Used in project scheduling software (e.g., MS Project).

C. Exponential Distribution in Service Systems

• PDF: $$\displaystyle f(t) = \mu e^{-\mu t} $$, $t \ge 0$, where $\mu$ = service rate (mean number served per unit time).

• Mean service time: $1/\mu$.

• Memoryless property: Remaining service time independent of elapsed time.

• Application: Service times in queuing models (e.g., $M/M/1$).