UNIT 1: ARTIFICIAL INTELLIGENCE TECHNIQUES (Short Notes)

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 be maximized (profit) or minimized (cost).

$$Z = c_1x_1 + c_2x_2 + ... + c_nx_n$$

• Constraints: Linear inequalities/equations (\(\le, \ge, =\)) representing resource limits.

• Non-negativity: \(x_j \ge 0\) for all \(j\).

• Conversion: Real-world problems (e.g., product mix) are translated into this standard form.

Simplex Method

• Purpose: Iterative algorithm to find the optimal solution.

• Step 1: Convert to Standard Form

  • \(\le\) constraints → add slack variables (\(s_i \ge 0\)).

  • \(\ge\) constraints → subtract surplus variables and add artificial variables (\(a_i \ge 0\)).

• Step 2: Find Initial Basic Feasible Solution (IBFS)

  • Set non-basic variables to 0.

  • Basic variables = RHS values if no artificial variables.

  • With artificial variables, use Big-M or Two-Phase method.

• Step 3: Optimality Test

  • Examine objective row (Z-row) coefficients in simplex tableau.

  • Maximization: If all coefficients are \(\ge 0\), current solution is optimal.

  • Minimization: If all coefficients are \(\le 0\), current solution is optimal.

• Step 4: Pivot Operation (if not optimal)

  • Entering Variable: Most negative (for max) or most positive (for min) Z-row coefficient.

  • Leaving Variable: Minimum positive ratio test: \(\frac{\text{RHS}}{\text{Pivot Column Coefficient}}\).

  • Perform row operations to make pivot element = 1 and other elements in pivot column = 0.

• Special Cases:

  • Unbounded Solution: All pivot column coefficients \(\le 0\) (for max) → Z can increase indefinitely.

  • Infeasible Solution: Artificial variable remains positive in final tableau (Big-M/Two-Phase).

  • Multiple Optimal Solutions: Zero coefficient in Z-row for a non-basic variable at optimum.

  • Degeneracy: Basic variable = 0. Can cause cycling; resolved by perturbation (ε) or Bland's rule.

[!TIP] Exam Focus: Simplex tableau setup, pivot operations, and interpreting final tableau (optimal solution, shadow prices from Z-row coefficients for RHS changes) are very frequent.

2. TRANSPORTATION PROBLEMS (TP)

Initial Basic Feasible Solution (IBFS) Methods

• North-West Corner (NWC) Rule:

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

  2. Allocate as much as possible: \(\min(\text{row availability}, \text{col requirement})\).

  3. Adjust row/column availabilities.

  4. If row exhausted → move down; if column exhausted → move right.

  5. Repeat until all allocations made.

• Vogel’s Approximation Method (VAM):

  1. For each row and column, calculate penalty = difference between two smallest costs.

  2. Select row/column with highest penalty.

  3. In that row/column, allocate to cell with lowest cost.

  4. Adjust availabilities, recalc penalties for affected rows/cols.

  5. Repeat. More accurate than NWC, often near-optimal.

Optimality Test & Improvement

• MODI (Modified Distribution) Method:

  1. For occupied cells: \(u_i + v_j = c_{ij}\).

  2. Set one \(u\) or \(v\) = 0, solve for others.

  3. For unoccupied cells: compute improvement index \(\Delta_{ij} = c_{ij} - (u_i + v_j)\).

  4. Optimal if all \(\Delta_{ij} \ge 0\) (for minimization).

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

• Stepping Stone Method:

  • Trace closed loop for unoccupied cell.

  • Calculate net change in cost by alternately adding/subtracting allocation at loop corners.

  • Improvement index = net change per unit.

Degeneracy in TP

• Definition: Number of occupied cells \(< (m + n - 1)\) in IBFS or during MODI.

• Cause: Two or more smallest allocations in a row/col during NWC/VAM.

• Resolution: Introduce epsilon (ε) allocation (very small positive number, e.g., 0.001) in a zero cell to maintain \(m+n-1\) basic variables. Treat ε as occupied for MODI calculations but cost = 0.

Unbalanced TP & Penalties

• Unbalanced: Total supply \(\neq\) total requirement.

  • Dummy Row/Column: Add with zero cost to balance.

• With Penalties (Unfulfilled Demand):

  • Add penalty column for each destination with penalty cost.

  • Dummy source with supply = total shortage capacity.

  • Solve as regular TP; allocations in penalty columns indicate unfulfilled demand.

[!TIP] Exam Focus: VAM steps, MODI optimality check, and handling degeneracy with ε are highly testable. For penalty problems, remember to add penalty destinations and balance.

3. INVENTORY MANAGEMENT

Economic Order Quantity (EOQ) Model

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

• Derivation: Minimize Total Annual Cost (TAC).

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

where \(Q\) = order quantity, \(P\) = unit purchase price.

• Optimal Order Quantity:

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

• Key Metrics:

  • Optimum orders/year: \(N = \frac{D}{Q^*}\)

  • Optimum period/order: \(T = \frac{Q^*}{D}\) years (or \(T = \frac{365}{N}\) days)

  • Minimum TAC (excluding purchase cost): \(\sqrt{2DSH}\)

EOQ with Quantity Discounts

• Procedure:

  1. Calculate EOQ at each price break using \(H = i \times \text{price}\) (if holding cost is % of price).

  2. Feasibility Check: EOQ must be within the price break's quantity range. If not, use boundary quantity for that break.

  3. Compute Total Cost \(TC = \frac{D}{Q}S + \frac{Q}{2}H + PD\) for all feasible \(Q\) (EOQ or boundary).

  4. Select \(Q\) with minimum TC.

EOQ with Shortage Costs

• Shortages Allowed: Maximum inventory \(= Q(1 - \frac{C}{H+C})\), where \(C\) = shortage cost per unit per year.

• Modified EOQ:

$$\boxed{Q^* = \sqrt{\frac{2DS}{H} \cdot \frac{H+C}{C}}}$$

*   If \(C \to \infty\) (no shortages), reduces to standard EOQ.

ABC & VED Analysis

• ABC Analysis: Classifies inventory by annual usage value.

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

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

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

• VED Analysis: For spare parts based on criticality.

  • V (Vital): No stock → production stops (tight control).

  • E (Essential): High impact, but some alternatives (moderate control).

  • D (Desirable): Low impact, easy alternatives (loose control).

• Advantages: Prioritizes management effort, reduces inventory costs, optimizes capital.

[!TIP] Exam Focus: EOQ formula derivation is rare; application is key. For discounts, always check feasibility of EOQ. ABC/VED definitions and advantages are short note favorites.

4. SUPPLY CHAIN MANAGEMENT (SCM) CONCEPTS

Bull-Whip Effect

• Definition: Demand distortion amplifies as orders move upstream (retailer → wholesaler → manufacturer).

• Causes:

  1. Demand Forecasting: Upstream uses orders, not actual sales.

  2. Order Batching: Periodic large orders.

  3. Price Fluctuations: Forward buying during promotions.

  4. Rationing & Gaming: Quota systems induce over-ordering.

• Mitigation:

  • Information Sharing: POS data sharing (CPFR).

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

  • Reduce Lead Times.

  • Eliminate incentives for forward buying.

Logistics in SCM

• Inbound Logistics: Flow of raw materials to production.

  • Activities: Procurement, transportation, receiving, warehousing, inventory management of inputs.

  • Importance: Ensures smooth production, reduces input costs, quality control.

• Outbound Logistics: Flow of finished goods to customers.

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

  • Importance: Directly impacts customer satisfaction, market responsiveness, and final cost.

MRP, ERP, and SCM Evolution

Cross-Docking

• Definition: Inbound goods are directly transferred to outbound trucks with minimal/no storage.

• Importance:

  • Reduces handling & inventory holding costs.

  • Faster throughput, reduced lead time.

  • Lower warehousing space requirement.

• Disadvantages:

  • Requires high coordination & real-time IT.

  • Not suitable for all products (e.g., need for quality check).

  • High dependency on inbound/outbound synchronization.

SCM Expenditure & Opportunities

• Major Cost Areas: Procurement, production, transportation, inventory carrying, administration.

• Opportunities:

  • Outsourcing non-core activities.

  • Technology adoption (IoT, AI, blockchain).

  • Process re-engineering.

  • Collaboration with supply chain partners.

SCM & E-Business Linkage

• E-Procurement: Online purchasing, auctions, catalogs → reduces transaction costs.

• E-Marketplaces: Connect buyers/sellers globally.

• Online Order Tracking: Enhances visibility & customer service.

• Impact: Faster information flow, reduced paperwork, better coordination, new business models.

[!TIP] Exam Focus: Bull-Whip causes/mitigation and MRP→ERP→SCM evolution are very common 7-mark questions. Cross-docking pros/cons are also frequent.

5. PROJECT MANAGEMENT (PERT/CPM)

Network Diagram Construction

• AON (Activity-on-Node): Node = activity, arrow = dependency. More common.

• AOA (Activity-on-Arrow): Arrow = activity, node = event. Requires dummy activities to show dependencies without work.

• Precedence Relationships: Finish-to-Start (FS), Start-to-Start (SS), etc.

• Dummy Activity: Zero duration, used to maintain correct logic in AOA.

Critical Path Method (CPM)

• Deterministic time estimates.

• Forward Pass (ES, EF):

  • \(ES = \max(EF \text{ of all immediate predecessors})\)

  • \(EF = ES + \text{Activity Time}\)

• Backward Pass (LS, LF):

  • \(LF = \min(LS \text{ of all immediate successors})\)

  • \(LS = LF - \text{Activity Time}\)

• Float/Slack:

  • Total Float (TF): \(LS - ES\) or \(LF - EF\). Zero on critical path.

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

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

Program Evaluation and Review Technique (PERT)

• Probabilistic time estimates for research/development projects.

• Three Time Estimates:

  • \(O\) = Optimistic (best case)

  • \(M\) = Most Likely

  • \(P\) = Pessimistic (worst case)

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

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

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

• Probability of Completion by Due Date (T):

  1. \(Z = \frac{T - T_e}{\sigma_p}\) (where \(T_e\) = expected project duration).

  2. Use standard normal table to find \(P(Z \leq z)\).

PERT vs. CPM

[!TIP] Exam Focus: Drawing network diagrams and forward/backward passes for CPM are fundamental. For PERT, calculating \(t_e\), \(\sigma^2\), and Z-score probability are guaranteed questions.

6. QUEUING THEORY

Basic Concepts

• Arrival Process: Pattern of customers entering system (often Poisson).

• Service Mechanism: Number of servers, service time distribution (often Exponential).

• Queue Discipline: Order of service (FCFS, LCFS, Priority, Random).

• System Capacity: Maximum number of customers allowed (finite/infinite).

• Population Size: Source of customers (finite/infinite).

Poisson Arrivals & Exponential Service

• Poisson Distribution (Number of arrivals in time \(t\)):

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

where \(\lambda\) = mean arrival rate (per unit time).

• Exponential Distribution (Service time \(T\)):

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

where \(\mu\) = mean service rate (per unit time). **Memoryless property.**

• Key Relationship: For stability in infinite queue, \(\rho = \lambda / \mu < 1\).

Probability Calculations

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

  • Example: If \(\mu = 20\) customers/hour, \(P(\text{service} > 3 \text{ min}) = e^{-(20/60) \times 3}\).

• Exactly n arrivals in t: Use Poisson formula with \(\lambda t\).

  • Example: \(\lambda = 8\)/hour, \(t = 40\) min = \(2/3\) hour → \(\lambda t = 16/3\).

[!TIP] Exam Focus: Converting units (hours/minutes) and applying \(P(T>t)=e^{-\mu t}\) or Poisson \(P(n)\) are very common. Always check \(\rho < 1\) for system stability.

7. GAME THEORY

Pure & Mixed Strategies

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

• Mixed Strategy: Probability distribution over actions. Player randomizes to avoid being predictable.

• Saddle Point (Pure Strategy Equilibrium):

  • Maximin (row player's security level) = Minimax (column player's security level).

  • Cell value = Value of the Game (\(v\)).

  • Test: Maximin = Minimax and cell value equals both.

• Expected Payoff (Mixed Strategy): Sum over all strategy pairs of (probability row \(p_i\) × probability col \(q_j\) × payoff \(a_{ij}\)).

Dominance Rule

• Row Dominance: Row \(i\) is dominated by row \(k\) if \(a_{kj} \ge a_{ij}\) for all \(j\) (and > for at least one). Row \(i\) can be eliminated.

• Column Dominance: Column \(j\) is dominated by column \(l\) if \(a_{il} \le a_{ij}\) for all \(i\) (and < for at least one). Column \(j\) can be eliminated.

• Use: Reduces payoff matrix size before solving for mixed strategies.

Basic Assumptions

1. Rationality: Players aim to maximize their own payoff.

2. Known Payoffs: Payoff matrix is common knowledge.

3. Simultaneous/Sequential Moves: Players choose independently (simultaneous) or with knowledge of prior moves (sequential).

4. Fixed Rules: Game structure is constant.

[!TIP] Exam Focus: Identifying saddle points and applying dominance to reduce matrices are short note staples. Mixed strategy calculations (solving 2x2 or reduced games) also appear.

8. HEURISTIC & METAHEURISTIC ALGORITHMS

Heuristics

• Definition: Problem-specific "rule-of-thumb" for quick, good (not optimal) solutions.

• Examples: Greedy algorithm (choose best immediate option), Nearest Neighbor for TSP.

• Pros: Fast, simple, easy to implement.

• Cons: Solution quality varies, no optimality guarantee, often problem-specific.

Metaheuristics

• Definition: High-level, problem-independent frameworks that guide heuristic search to explore large/complex spaces and escape local optima.

• Characteristics: Stochastic, iterative, uses exploration vs. exploitation balance.

• Examples:

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

  • Simulated Annealing (SA): Mimics cooling process; accepts worse moves with decreasing probability.

  • Tabu Search (TS): Uses memory (tabu list) to avoid cycling.

  • Ant Colony Optimization (ACO): Swarm intelligence, pheromone trails.

• Applications: NP-hard problems (scheduling, routing, design optimization).

[!TIP] Exam Focus: Distinguish heuristic (specific, fast) vs. metaheuristic (general framework, iterative). List 2-3 examples of each with their core idea.

9. ADDITIONAL TOPICS FROM OPTIONAL QUESTIONS

Network Logics (in Project Management)

• Finish-to-Start (FS): Successor cannot start until predecessor finishes. Most common.

• Start-to-Start (SS): Successor cannot start until predecessor starts.

• Finish-to-Finish (FF): Successor cannot finish until predecessor finishes.

• Start-to-Finish (SF): Rare; successor cannot finish until predecessor starts.

• Lag/Lead: Delay (lag) or overlap (negative lag/lead) between activities.

Phases of Project Management

1. Initiation: Define project, feasibility, charter.

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

3. Execution: Coordinate people/resources, implement plan.

4. Monitoring & Controlling: Track progress, manage changes, ensure alignment with plan.

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

[!TIP] Exam Focus: Network logics are often asked with diagram drawing. Phases are a direct 7-mark question. Know the 5 phases in order.