Operations Research (MTH601) - Comprehensive Study Notes

Foundations and Definition of Operations Research

• Historical Background

  • Technology—the application of science to the physical world—radically transformed industrial manufacturing and wealth creation following the Industrial Revolution.

  • Complex manufacturing systems (e.g., aircraft production) created complex system-level management and operational challenges.

  • Operational Research (OR) originated during World War II (1939–1945) when the British Government formed teams of eminent scientists to apply scientific methods to operational and management problems rather than purely technical ones.

  • The Radar Operational Research Team coined the name "Operational Research" while managing the deployment and operational installation of radar systems.

  • An OR team investigated Allied shipping losses caused by German U-boats sinking food convoys. By collecting operational data and formulating scientific hypotheses, the team significantly reduced shipping losses and contributed to the defeat of the U-boat fleet.

  • Following World War II, OR methodology expanded rapidly into commercial and industrial sectors across Britain, the United States, Europe, and globally, establishing OR as an independent interdisciplinary science.

• Formal Definitions of Operations Research

  • Morse and Kimball (1946): "OR is a scientific method of providing executive departments with a quantitative basis for decision regarding the operations under their control."

  • Blackett (1948): "OR is a scientific method of providing executives with an analytical and objective basis for decisions."

  • Morse (1948): "The term OR, has heretofore been used to connote various attempts to study operations of war by scientific methods. From a more general point of view, OR can be considered to be an attempt to study those operations of modern society which involved organizations of men or men and machines."

  • Churchman, Ackoff, and Arnoff (1957): "OR is the application of scientific methods, techniques and tools to problems involving the operations of systems so as to provide those in control of the operations with optimum solutions to the problem."

  • Saaty (1958): "The art of giving bad answers to problems to which, otherwise, worse answers are given."

  • Operational Research Society of the U.K.: "Operational Research is the application of the methods of science to complex problems arising in the direction and management of large systems of men, machines, materials and money in industry, business, government and defense. The distinctive approach is to develop a scientific model of the system, incorporating measurements of factors, such as chance and risk, with which to compare the outcome of alternative decisions, strategies and controls. The purpose is to help management determine its policies and actions scientifically."

  • Operations Research Society of America (ORSA): "OR is concerned with scientifically deciding how to best design and operate man-machine systems, usually under conditions requiring the allocation of scarce resources."

  • Concise definition: "Science applied to management."

• Distinction Between Core Concepts

  • Management: Equated directly with decision-making and control across government, industrial, and personal spheres.

  • Management Science: The abstract theoretical study of managerial problems and the application of theoretical models to practical contexts. Its core disciplines are behavioral science and quantitative methods.

  • Operations Research (OR): The direct application of quantitative methods to decision-making. It formulates operational problems incisively to assess alternative courses of action for effective executive decisions.

• The Systematic OR Approach to Problem Solving

  • The OR process follows a structured 5-step sequence:

  1. Observation: Continuous and close monitoring of the operational system to identify existing or emerging problems immediately.

  2. Definition of the Problem: Defining the exact boundaries, scope, and extent to which the problem pervades other system organs. Clear definition of organizational goals/objectives is required.

  3. Model Construction: Building an abstract mathematical or graphical representation of the physical problem. OR models express system behavior using an objective function and a set of constraints.

  4. Model Solution: Solving the mathematical model using established OR mathematical algorithms.

  5. Implementation of Results: Translating mathematical outputs into practical, actionable information for decision-makers. Solutions must be physically and operationally feasible.

• Iterative Nature of the OR Process

  • OR is a continuous feedback loop rather than a one-time static calculation.

  • Implementation results generate feedback that modifies the original model parameters, tests future conditions, or uncovers hidden underlying problems requiring model reconstruction.

• Classification of Operations Research Techniques

  • Linear Mathematical Programming: Techniques where functional relationships in the model are strictly linear, solved via structured mathematical steps (e.g., Linear Programming, Simplex algorithm, Transportation, Assignment, Integer LP, Goal LP).

  • Probabilistic Techniques: Models where parameters are subject to uncertainty and randomness. Solutions yield probabilistic outcomes (e.g., Decision Analysis, Game Theory, Markov Analysis, Queuing Theory, Simulation, Forecasting).

  • Inventory Techniques: Specific deterministic and probabilistic models designed to analyze inventory holding, ordering, and shortage costs.

  • Network Techniques: Diagrammatic/pictorial models representing system activities and event sequences (e.g., Network Flow, PERT/CPM).

  • Other Techniques: Non-linear programming, Dynamic programming, Break-even analysis.

• Application Domains of Operations Research

  • Macro-Economic Planning:

  • Input/Output Analysis via LP models (Short-term Five Year Plans up to $10\text{ years}$; Long-term plans $10\text{ to }30\text{ years}$).

  • Investment Planning using Mixed Integer Programming and LP.

  • Choice of Optimal Projects using Integer Programming and Quadratic Assignment.

  • Macroeconomic Simulation Modeling.

  • Sectorial Planning: Agricultural production, fertilizer distribution, maintenance scheduling, and financial portfolio optimization.

  • Micro-Economic Planning: Individual corporate operations, workshop layout design, and regional hospital capacity sizing.

  • Public Sector Applications: Urban structure planning, government manpower planning, civil housing allocation, fire brigade station placement, school/college facility timetabling, healthcare unit sizing, ambulance dispatching, defense logistics, and war games.

  • Industrial & Commercial Applications: Financial portfolio selection, steel mill production scheduling, advertising media scheduling, consumer loyalty measurement, and pharmaceutical depot location.

  • Transportation Sector Applications:

  • Rail: Freight management, locomotive fleet sizing, main-line terminal reconstruction.

  • Road: Urban road network design, car ownership forecasting, bus lane implementation, crew roster preparation.

  • Air: Fleet selection (Boeing 737 / Airbus 300), flight crew route allocation, airport location planning.

  • Sea: Container terminal management, optimal cargo ship sizing, shipbuilding forecasting.

• Detailed Supply Chain Operations Example (Oil Industry)

  • OR techniques apply across all six main operational steps in the petroleum industry:

  1. Field oil extraction.

  2. Crude oil transport (fields to refineries, fields to export jetties, import jetties to refineries).

  3. Crude oil storage (field tanks, port tanks, refinery tanks).

  4. Refinery unit scheduling (Crude Distillation Units [CDUs], blending units).

  5. Storage of distilled/blended products (refineries, jetties, distribution terminals).

  6. Final product transport (jetty to refinery, inter-refinery transfer, bulk distribution points to end consumers).

• Prerequisites for Successful OR Implementation

  1. Availability of qualified OR professionals capable of collaborating with ground-level operational staff.

  2. Healthy interaction with statistical machinery to ensure high-quality, factual data inputs free from managerial bias.

  3. Sufficient computing power and software support for processing complex models.

  4. Executive management willingness to accept organizational change and implement optimal analytical alternatives.

  • Stafford Beer quote: "We call that work operational (with a large O) because it is based in the world of genuine activity, the places where things actually happen… We call our work Research (with a capital R) because we deal with problems to which no one knows the answer."

Network Analysis (PERT/CPM)

• Introduction and Historical Origins

  • PERT (Program Evaluation and Review Technique): Developed by the U.S. Navy and Defense Department to plan and accelerate the development of the Polaris Ballistic Missile submarine program. PERT is an event-oriented technique designed for research and development (R&D) projects where activity completion times are uncertain, variable, and non-standard.

  • CPM (Critical Path Method): Developed simultaneously for construction and industrial maintenance projects where activity durations are known with certainty. CPM focuses on the deterministic trade-off between direct activity costs and project completion time (crashing).

  • Normal vs. Crash Duration in CPM:

  • Normal Duration: Standard completion time under normal working conditions and costs.

  • Crash Duration: Reduced completion time achieved by applying extra resources (overtime, extra labor, specialized machinery) at higher direct cost.

  • Cost Trade-off: Crashing increases direct activity costs but reduces indirect project overhead costs. CPM strikes a balance to determine the least-cost project schedule.

• Network Definitions and Components

  • A Network is a graphical representation depicting the flow of activities and events.

  • Node: Represented by a circle. Indicates an event (a specific, definable accomplishment occurring at a distinct point in time).

  • Branch / Arc: Represented by an arrow line. Indicates an activity (a time-consuming task or process).

  • Physical Network Analogies:

• Rules for Network Construction

  • Each activity is represented by one, and only one, directed arrow.

  • No two activities can share the exact same starting and ending nodes (prevents parallel loops).

  • Time flows strictly from left to right.

  • Activity arrows must not cross each other.

  • Every node (except the initial source node and final terminal node) must have at least one entering activity and at least one leaving activity.

• Dummy Activities

  • A Dummy Activity consumes zero time and zero resources. It is represented by a dashed/dotted arrow line ($-- - \rightarrow$).

  • Purposes of Dummy Activities:

  1. To maintain unique node identification when two or more concurrent activities share identical start and end events.

  2. To preserve exact logical precedence relationships among activities that are not directly connected by physical events.

• Critical Path Determination Algorithms

  • Path: A continuous chain of directed activity arrows connecting the initial start node to the final completion node.

  • Path Length: Sum of the individual completion times of all activities along that specific path.

  • Critical Path: The longest path through the network diagram. Its total duration establishes the minimum time required to complete the entire project.

  • Critical Activities: Activities lying on the critical path. Any delay in a critical activity directly extends the project completion date.

• Forward Pass Calculations (Earliest Times)

  • Earliest Start Time ($ES$): The earliest possible instant an activity can begin, assuming all predecessor activities finish as early as possible.

  • For the initial project activity starting at node $1$: $ES = 0$.

  • For activity $(i, j)$: $ES_{ij} = \text{Max}_i [EF_{\text{predecessors}}]$.

  • Earliest Finish Time ($EF$): $EF_{ij} = ES_{ij} + t_{ij}$, where $t_{ij}$ is the duration of activity $(i, j)$.

• Backward Pass Calculations (Latest Times)

  • Latest Finish Time ($LF$): The latest time an activity can finish without delaying the overall target project completion date.

  • For the terminal project event: LF_{\text{terminal}} = \text{Project Duration } T_e$.\n - For activity (i, j)$:$LF_{ij} = \text{Min}j [LS{\text{successors}}].\n - **Latest Start Time (LS$)**:$LS_{ij} = LF_{ij} - t_{ij}.\n\n\n\n- **Float / Slack Classifications**\n - **Total Float (Total Slack)**: The maximum duration an activity can be delayed without extending the overall project completion time.\n - Formula: \text{Total Float} = LS - ES = LF - EF\n - **Free Float (Free Slack)**: The time an activity can be delayed without delaying the earliest start time of any immediate successor activity.\n - Formula: \text{Free Float} = ES_{\text{next}} - EF = ES_{\text{successor}} - (ES + t_{ij})\n - **Independent Float (Independent Slack)**: The duration an activity can be delayed when preceding activities finish at their latest possible times and succeeding activities start at their earliest possible times.\n - Formula: \text{Independent Float} = ES_{\text{successor}} - LF_{\text{predecessor}} - t_{ij}\n - Note: If calculated Independent Float is negative, it is defined as 0.\n - Relationship: \text{Total Float} \times \text{Free Float} \times \text{Independent Float}\n\n\n\n- **PERT Probabilistic Time Estimates and Model Equations**\n - PERT incorporates uncertainty by utilizing three time estimates for each activity, modeled using a **Beta Distribution**:\n 1. **Optimistic Time (t_o)**: The minimum possible activity completion time under ideal working conditions.\n 2. **Most Likely Time (t_m)**: The modal completion time required under normal, standard operating conditions.\n 3. **Pessimistic Time (t_p)**: The maximum required completion time under highly adverse conditions (excluding catastrophes).\n - **Expected Activity Time (t_e)**:\n - Derived from the weighted average of the Beta distribution (1 : 4 : 1 weighting):\n    t_e = \frac{t_o + 4t_m + t_p}{6}\n - **Standard Deviation of Activity Time (S_t)**:\n    S_t = \frac{t_p - t_o}{6}\n - **Variance of Activity Time (V_t)**:\n    V_t = S_t^2 = egin{pmatrix} \frac{t_p - t_o}{6} ight)^2\n\n- **Project Probability Analysis**\n - **Expected Project Duration (T_e)**: The sum of expected activity durations along the critical path:\n    T_e = \times t_e \text{ (along critical path)}\n - **Project Variance (V_T)**: Sum of variances of all critical activities:\n    V_T = \times V_t \text{ (along critical path)}\n - **Project Standard Deviation (\times_T)**:\n    \times_T = \times{V_T}\n - **Standard Normal Variate (Z)**:\n - By the Central Limit Theorem, total project duration T_e$approaches a Normal Distribution$N(T_e, \times_T^2).\n - For a specified target due date T:\n    Z = \frac{T - T_e}{\times_T}\n - The probability of completing the project by target date T$equals the area under the standard normal curve from$-\times$to$Z.\n\n\n\n- **Resource Scheduling**\n - **Resource Leveling**: Smooths peak resource requirements across project periods by shifting non-critical activities within their available total float ranges while keeping total project duration strictly fixed.\n - **Resource Allocation**: Constrains activity scheduling based on fixed maximum limits of available resources (manpower, equipment, budget). If resource availability is insufficient, activities are postponed based on priority rules (e.g., least total float scheduled first), extending the overall project completion date.\n\n# Inventory Control and EOQ Models\n\n- **Fundamental Inventory Definitions**\n - **Inventory**: The physical stock of goods or materials held in business storage for future production, processing, or sales.\n - Core operational questions in inventory management:\n 1. **Order Quantity**: How much stock to order or manufacture at a single time?\n 2. **Reorder Timing**: When to place an order, or how frequently to replenish stock?\n\n- **The Four Major Inventory Cost Components**\n - **Item Cost (C_1$)**: Purchase cost per item from a supplier or direct unit manufacturing cost (materials, labor, overhead). Denoted as$\text{Rs. } C_1 \text{ per item}.\n - **Ordering / Setup Cost (C_2$)**: Administrative, clerical, transportation, and inspection costs per purchase order, or setup/tooling cost per production run. Denoted as$\text{Rs. } C_2 \text{ per order or setup}.\n - **Inventory Holding / Carrying Cost (C_3$)**: Storage costs, taxes, insurance, deterioration, obsolescence, handling, and capital opportunity cost per item per unit time. Denoted as$\text{Rs. } C_3 \text{ per item per unit time}.\n - **Shortage / Stockout Cost (C_4$)**: Penalty costs incurred when demand exceeds available stock (expediting, overtime, lost customer goodwill, administrative delay). Denoted as$\text{Rs. } C_4 \text{ per item per unit time of shortage}.\n\n- **Deterministic Inventory Models (Economic Order Quantity - EOQ)**\n\n - **Model 1: Purchasing Model with No Shortages (Wilson's Classic EOQ Model)**\n - Assumptions: Demand rate D$is constant and deterministic; replenishment is instantaneous (lead time$= 0$); cost parameters$C_1, C_2, C_3$are constant; no shortages allowed ($C_4 = 0).\n\n\n\n - Cost Equations Derivation:\n - Item cost per period = C_1 Q\n - Setup cost per period = C_2\n - Holding cost per period = C_3 \times \frac{Q}{2} \times t\n - Cycle time t = \frac{Q}{D}\n - Total Cost per unit time C(Q):\n      C(Q) = C_1 D + \frac{C_2 D}{Q} + \frac{C_3 Q}{2}\n\n\n\n - Minimizing C(Q)$with respect to$Q$($\frac{dC}{dQ} = 0):\n      \frac{dC}{dQ} = -\frac{C_2 D}{Q^2} + \frac{C_3}{2} = 0 \times \text{Economic Order Quantity } Q^* = \times{\frac{2 C_2 D}{C_3}}\n - Optimum Cycle Time (t^$):$t^ = \frac{Q^}{D}\n - Optimum Order Frequency (N^$):$N^* = \frac{D}{Q^}\n\n - **Model 2: Purchasing Model with Shortages Allowed**\n - Assumptions: Demand rate D$is constant; backordering is permitted at shortage cost$C_4$per item per unit time; maximum inventory level is$I_m = Q - S$, where$S represents backordered shortages.\n\n\n\n - Total Cost per unit time C(Q, S): \n      C(Q, S) = C_1 D + \frac{C_2 D}{Q} + \frac{C_3 (Q - S)^2}{2Q} + \frac{C_4 S^2}{2Q}\n - Optimal Order Quantity (Q^):\n      Q^* = \times{\frac{2 C_2 D}{C_3} \times egin{pmatrix} \frac{C_3 + C_4}{C_4} ight)}\n - Optimal Maximum Shortage Level (S^):\n      S^ = \times{\frac{2 C_2 D}{C_4} \times egin{pmatrix} \frac{C_3}{C_3 + C_4} ight)}\n - Maximum Inventory Level (I_m^$):$I_m^ = Q^* - S^\n\n - **Model 3: Manufacturing Model with Finite Replenishment, No Shortages**\n - Assumptions: Production rate R$is finite, continuous, and strictly greater than demand rate$D$($R > D$); setup cost$C_2 per production run; no shortages permitted.\n\n\n\n - Maximum Inventory Level (I_m):\n      I_m = Q egin{pmatrix} 1 - \frac{D}{R} ight)}\n - Total Cost per unit time C(Q): \n      C(Q) = C_1 D + \frac{C_2 D}{Q} + \frac{C_3 Q}{2} egin{pmatrix} 1 - \frac{D}{R} ight)}\n - Optimal Manufacturing Batch Size (Q^):\n      Q^* = \times{\frac{2 C_2 D}{C_3 egin{pmatrix} 1 - \frac{D}{R} ight)}}\n\n - **Model 4: Manufacturing Model with Finite Replenishment and Shortages**\n - Assumptions: Finite production rate R > D$; planned backordered shortages$S$allowed at cost$C_4.\n\n\n\n - Optimal Manufacturing Batch Size (Q^):\n      Q^ = \times{\frac{2 C_2 D}{C_3 egin{pmatrix} 1 - \frac{D}{R} ight)} \times egin{pmatrix} \frac{C_3 + C_4}{C_4} ight)} \n - Optimal Shortage Level (S^):\n      S^ = \times{\frac{2 C_2 D egin{pmatrix} 1 - \frac{D}{R} ight)}{C_4} \times egin{pmatrix} \frac{C_3}{C_3 + C_4} ight)} \n\n- **Order Quantity Decisions with Quantity Price Breaks**\n - Suppliers offer discounted unit purchase prices for placing bulk orders above specified threshold quantities.\n - Algorithm:\n 1. Calculate standard EOQ for the lowest unit price tier.\n 2. If calculated EOQ falls within the quantity range required for that price tier, it is feasible and optimal.\n 3. If infeasible, evaluate total annual cost (Item Cost + Order Cost + Holding Cost) at the standard EOQ and at each price break quantity threshold.\n 4. Select the order quantity yielding the lowest total annual cost.\n\n- **Dynamic Order Quantity Model for Fluctuating Demand**\n - Applies to non-uniform, seasonal, or irregular demand patterns across discrete time periods n = 1, 2, \times, N.\n - Decision Rule: An order placed in month n$should absorb demand for month$n+1 if the incremental inventory holding cost is less than the setup cost savings:\n    n^2 R_{n+1} < \frac{C_2}{C_3}\n    where R_{n+1}$is the demand in month$n+1$,$C_2$is setup cost, and$C_3 is unit monthly holding cost.\n\n- **ABC Inventory Control Classification Analysis**\n - Based on **Pareto’s Law** (the 80/20 rule: a small percentage of items represent the vast majority of total annual monetary usage value).\n - Categories:\n - **Class A**: High usage value (approx. 10\text{--}20\text{\%}$of total items accounting for$70\text{--}80\text{\%} of usage value). Requires tightest, continuous executive monitoring, low buffer stock, and precise EOQ ordering.\n - **Class B**: Moderate usage value (approx. 20\text{--}30\text{\%}$of total items,$15\text{--}20\text{\%} of usage value). Standard statistical inventory control.\n - **Class C**: Low usage value (approx. 50\text{--}60\text{\%}$of total items,$5\text{--}10\text{\%} of usage value). Simple, floor-stock visual controls with large bulk reorder lot sizes.\n - Procedural Steps:\n 1. Calculate annual monetary usage value (\text{Annual Demand} \times \text{Unit Price}) for each item.\n 2. Sort items in descending order of annual usage value.\n 3. Calculate cumulative usage values and cumulative percentages.\n 4. Plot cumulative percentage items vs. cumulative percentage value to establish cutoff points A, B, and C.\n\n- **Safety Stock, Lead Time, and Reorder Level Equations**\n - **Lead Time (LT)**: Time elapsed between placing a replenishment order and receiving goods in inventory.\n - **Lead Time Demand (LTD$)**:$\text{Average Demand Rate} \times \text{Lead Time}.\n - **Reorder Level (ROL)**: Inventory level triggering a replenishment order:\n    ROL = LTD + SS\n    where SS is Safety Stock (Buffer Stock).\n - **Safety Stock Equations**:\n - Safety Stock derived from Normal Distribution of forecast error:\n      SS = Z \times \times_{LT}\n - Relationship between Standard Deviation (\times$) and Mean Absolute Deviation ($MAD):\n      \times = \times{\frac{\times}{2}} MAD \times 1.25 \times MAD\n - Safety Stock using MAD$over Lead Time ($LT):\n      SS = K \times MAD_{LT}\n      where K = Z \times \times{\frac{\times}{2}} (Service Factor), and\n      MAD_{LT} = (0.659 + 0.341 \times LT) \times MAD\n\n# Linear Programming Formulation and Graphical Method\n\n- **Core Components of a Linear Program (LP)**\n - **Decision Variables**: Independent non-negative quantities (X_1, X_2, \times, X_n) to be determined.\n - **Objective Function**: A linear mathematical function representing total profit, contribution, or cost to be Maximized or Minimized.\n - **Constraints**: Linear equality or inequality equations (\times, =, \times) representing technological, resource, market, or capacity limitations.\n - **Non-Negativity Restrictions**: X_j \times 0 \text{ for all } j.\n\n- **Detailed Mathematical Formulations of Standard LP Problems**\n\n - **1. Product Mix Problem (Regal China Company)**\n - Variables: X_1 = \text{number of plates/day}$,$X_2 = \text{number of mugs/day}.\n - Objective: Maximize Profit Z = 4X_1 + 5X_2\n - Constraints:\n - Labor hours: 1X_1 + 2X_2 \times 40\n - Clay pounds: 4X_1 + 3X_2 \times 120\n - Non-negativity: X_1, X_2 \times 0\n\n - **2. Ingredients Mixing Problem (Fauji Foundation SUNFLOWER Cereal)**\n - Variables: X_1 = \text{oz of wheat/box}$,$X_2 = \text{oz of oats/box}$,$X_3 = \text{oz of rice/box}.\n - Objective: Minimize Cost Z = 0.4X_1 + 0.6X_2 + 0.2X_3\n - Constraints:\n - Vitamin A (mg): 10X_1 + 20X_2 + 8X_3 \times 100\n - Vitamin D (mg): 7X_1 + 14X_2 + 12X_3 \times 70\n - Non-negativity: X_1, X_2, X_3 \times 0\n\n - **3. Investment Planning Problem (Mr. Majid Khan)**\n - Total Capital: \text{Rs. } 70,000\n - Variables: X_1 = \text{National Cert}$,$X_2 = \text{Defence Savings Cert}$,$X_3 = \text{NIT}$,$X_4 = \text{Khas Deposit}.\n - Objective: Maximize Return Z = 0.085X_1 + 0.100X_2 + 0.065X_3 + 0.130X_4\n - Constraints:\n - Khas limit: X_4 \times 14,000\n - Defence limit: X_2 - X_1 - X_3 - X_4 \times 0\n - NIT & Defence minimum: X_2 + X_3 \times 21,000\n - National to NIT ratio: 3X_1 - X_3 \times 0\n - Total investment equality: X_1 + X_2 + X_3 + X_4 = 70,000\n - Non-negativity: X_1, X_2, X_3, X_4 \times 0\n\n - **4. Chemical Mixture Problem (United Chemical Company)**\n - Batch size: 1,000\text{ lbs}.\n - Variables: X_1 = \text{lbs of mercury}$,$X_2 = \text{lbs of zinc}$,$X_3 = \text{lbs of potassium}.\n - Objective: Minimize Cost Z = 4X_1 + 8X_2 + 9X_3\n - Constraints:\n - Mercury minimum: X_1 \times 200\n - Zinc minimum: X_2 \times 300\n - Potassium minimum: X_3 \times 100\n - Total batch balance: X_1 + X_2 + X_3 = 1,000\n - Non-negativity: X_1, X_2, X_3 \times 0\n\n - **5. Marketing Media Selection Problem (Bata Shoe Company)**\n - Variables: X_1 = \text{TV ads}$,$X_2 = \text{Radio ads}$,$X_3 = \text{Newspaper ads}.\n - Objective: Maximize Audience Exposure Z = 20,000X_1 + 12,000X_2 + 9,000X_3\n - Constraints:\n - Budget limit: 15,000X_1 + 6,000X_2 + 4,000X_3 \times 100,000\n - TV limit: X_1 \times 4\n - Radio limit: X_2 \times 10\n - Newspaper limit: X_3 \times 7\n - Agency total capacity: X_1 + X_2 + X_3 \times 15\n - Non-negativity: X_1, X_2, X_3 \times 0\n\n - **6. Transportation Problem as LP (Philips Television Company)**\n - Variables: Double subscripted X_{ij} = \text{units shipped from warehouse } i \text{ to store } j.\n - Objective: Minimize Shipping Cost Z = 6X_{1A} + 8X_{1B} + 1X_{1C} + 4X_{2A} + 2X_{2B} + 3X_{2C} + 3X_{3A} + 5X_{3B} + 7X_{3C}\n - Constraints:\n - Warehouse Supply: \n        X_{1A} + X_{1B} + X_{1C} = 300\n        X_{2A} + X_{2B} + X_{2C} = 100\n        X_{3A} + X_{3B} + X_{3C} = 200\n - Store Demand: \n        X_{1A} + X_{2A} + X_{3A} = 150\n        X_{1B} + X_{2B} + X_{3B} = 250\n        X_{1C} + X_{2C} + X_{3C} = 200\n - Non-negativity: X_{ij} \times 0 \text{ for all } i, j\n\n- **General Algebraic and Matrix Representations of LPP**\n - Algebraic Form:\n    \text{Maximize or Minimize } Z = \times_{j=1}^n c_j X_j\n    \text{Subject to } \times_{j=1}^n a_{ij} X_j egin{pmatrix} \times \ = \ \times ight) b_i \text{ for } i = 1, 2, \times, m\n    X_j \times 0 \text{ for } j = 1, 2, \times, n\n - Compact Matrix Form:\n    \text{Optimize } Z = \times\times\n    \text{Subject to } \times\times egin{pmatrix} \times \ = \ \times ight) \times, \text{ and } \times \times \times\n    where \times$is a row vector of objective coefficients,$\times$is a column vector of decision variables,$\times$is an$m \times n$technological coefficient matrix, and$\times is a column vector of resource capacities.\n\n- **Theoretical Assumptions and Limitations of LP**\n - **Proportionality**: Contribution to objective and resource usage are directly proportional to the variable value. Violations occur in the presence of **fixed charges/setup costs**.\n - **Additivity**: Total objective value and total resource usage equal the strict sum of individual activity contributions. Violations occur in the presence of activity joint interactions or by-product generation.\n - **Divisibility**: Decision variables can assume non-integer fractional values.\n - **Deterministic Assumption**: All coefficients (c_j, a_{ij}, b_i) are assumed known with certainty.\n\n- **Graphical Solution Procedure for Two-Variable LP Problems**\n - Step 1: Plot each constraint inequality as an equality line on Cartesian coordinates (X_1, X_2).\n - Step 2: Identify the half-space satisfying each inequality (using origin (0,0) as a reference test point).\n - Step 3: Determine the closed, bounded intersection region containing all feasible points (**Feasible Region / Solution Space**).\n - Step 4: Identify all corner points (extreme points) of the feasible convex polygon by solving intersecting line equations.\n - Step 5: Evaluate the objective function at every extreme corner point. The corner point yielding the maximum (or minimum) value is the optimal basic solution.\n - Alternative Iso-Profit Line Approach: Plot an arbitrary objective line Z = k. Shift the line parallel in the direction of increasing profit until it touches the last boundary point of the feasible region.\n\n\n\n\n\n\n\n\n\n\n\n\n\n# The Simplex Method and Duality Theory\n\n- **Fundamental Properties of Linear Programming Solutions**\n - **Property 1**: The collection of all feasible solutions to an LP forms a **convex set**.\n - **Property 2**: If a feasible solution exists, at least one **Basic Feasible Solution (BFS)** exists. Basic feasible solutions correspond mathematically to the extreme corner points of the convex feasible region.\n - **Property 3**: There exist a finite number of basic feasible solutions.\n - **Property 4**: If the objective function possesses a finite optimal value, at least one optimal solution is a basic feasible solution.\n\n- **Mathematical Definitions in Simplex Method**\n - **Slack Variable (S_i$)**: A non-negative variable added to the left-hand side of a$\times constraint to convert it into an exact equality. Represents unused/idle resource capacity.\n - **Surplus Variable (-S_i$)**: A non-negative variable subtracted from the left-hand side of a$\times constraint to convert it into an exact equality. Represents excess usage over the minimum requirement.\n - **Artificial Variable (A_i$)**: A non-negative starting variable added to$\times$or$= constraints to provide an initial identity matrix basis. Artificial variables have no real physical meaning.\n - **Basic Solution**: For m$functional constraint equations with$n$variables ($n > m$), a solution obtained by setting$(n - m)$variables equal to zero (**non-basic variables**) and solving the remaining$m$equations for the$m **basic variables**.\n - **Basic Feasible Solution (BFS)**: A basic solution where all m$basic variables are strictly non-negative ($\times 0).\n\n- **Step-by-Step Simplex Algorithm Execution (Maximization)**\n 1. **Standard Form**: Convert all constraints into equalities by adding slack variables, subtracting surplus variables, and adding artificial variables. Formulate row 0 as: Z - \times c_j X_j = 0\n 2. **Initial Simplex Tableau**: Construct the initial table with slack/artificial variables forming the initial basis matrix \times = \times\n 3. **Optimality Test**: Inspect the net evaluation row (Row 0).\n - For Maximization: If all coefficients in Row 0 are non-negative (\times 0), the current tableau is optimal.\n - If negative coefficients exist, select the variable with the **most negative** coefficient in Row 0 as the **Entering Basic Variable** (marks the Key Column).\n 4. **Leaving Variable Selection (Minimum Ratio Test)**:\n - Divide the right-hand side (RHS$) values by the corresponding positive ($> 0) entries in the key column:\n       \text{Ratio}i = \frac{RHS_i}{a{i, \text{key}}} \text{ for } a_{i, \text{key}} > 0\n - Select the row with the **smallest non-negative ratio** as the **Leaving Basic Variable** (marks the Key Row).\n - The element at the intersection of the Key Column and Key Row is the **Pivot/Key Element**.\n 5. **Gauss-Jordan Elimination Update**:\n - Divide the Key Row by the Pivot Element to make the pivot value equal to 1.\n - Perform elementary row operations to reduce all other entries in the Key Column to 0.\n 6. **Iterate**: Repeat steps 3 to 5 until the optimality condition is fully satisfied.\n\n- **Artificial Variable Techniques**\n\n - **1. Big M Method (Charnes Penalty Method)**\n - Assigns an extremely large positive penalty cost M to each artificial variable in the objective function:\n - Maximization: Include -M A_i in objective function.\n - Minimization: Include +M A_i in objective function.\n - Before initial iterations, eliminate M$from row 0 under artificial variable columns by adding/subtracting$M \times (\text{artificial constraint rows}).\n - Large penalties force artificial variables to leave the basis (A_i = 0) during optimization.\n\n - **2. Two-Phase Method**\n - Eliminates large penalty constant M computational round-off errors.\n - **Phase I**: Define an auxiliary objective function equal to the sum of all artificial variables: \text{Minimize } Z_A = \times A_i$. Solve using Simplex. If optimal$Z_A^* = 0$, all artificial variables are driven out of the basis; proceed to Phase II. If optimal$Z_A^* > 0, no feasible solution exists.\n - **Phase II**: Drop artificial variable columns. Re-introduce original objective function coefficients and solve starting from the optimal basic solution obtained at the end of Phase I.\n\n- **Special Cases and Variants in the Simplex Method**\n - **Degeneracy**: Occurs when there is a tie in the minimum ratio test for the leaving variable. In the next iteration, one or more basic variables equal zero (X_B = 0$). Can lead to **cycling** (looping infinitely through identical tableaus without improving$Z).\n - **Temporary Degeneracy**: Degenerate solution appears at an intermediate iteration but resolves naturally into a non-degenerate optimal solution.\n - **Unbounded Solution**: Occurs when all constraint coefficients in the key column are non-positive (\times 0$) during an iteration. The minimum ratio test yields no positive values ($\times$), meaning the feasible region is unbounded in the direction of optimization and$Z ightarrow \times\n - **Unbounded Feasible Region with Bounded Optimum**: Solution space extends to infinity, but constraint boundaries enclose and limit the objective function to a finite maximum value.\n\n\n\n - **Multiple / Alternative Optimal Solutions**: Occurs when a non-basic variable has a coefficient equal to zero (0$) in Row 0 of the optimal tableau. Pivoting this variable into the basis generates a different basic optimal solution yielding the exact same optimal$Z^ value.\n\n\n\n - **Non-Existing Feasible Solution (Infeasibility)**: Occurs when no point satisfies all constraints simultaneously. Identified in the final simplex tableau when row 0 satisfies optimality criteria, but one or more artificial variables remain basic at a positive value (A_i > 0).\n - **Unrestricted Variables**: If decision variable X_j is unrestricted in sign (can be positive, negative, or zero), substitute:\n    X_j = X_j' - X_j'' \text{ where } X_j' \times 0, X_j'' \times 0\n\n- **Duality Theory**\n - Every linear program (called the **Primal**) has a directly corresponding paired linear program called the **Dual**.\n\n - **Primal-Dual Relationships**:\n\n| Primal Problem (Maximization) | Dual Problem (Minimization) |\n| :--- | :--- | \n| Objective Function (Maximize Z$) | Objective Function (Minimize$W) |\n| Right-Hand Side Capacities (b_i$) | Objective Coefficients ($b_i) |\n| Objective Coefficients (c_j$) | Right-Hand Side Constants ($c_j) |\n| Technological Matrix \times$| Transposed Matrix$\times^T |\n| i\text{-th}$Constraint of type$\times$|$i\text{-th}$Dual Variable$y_i \times 0 |\n| i\text{-th}$Constraint of type$=$|$i\text{-th}$Dual Variable$y_i Unrestricted in Sign |\n| j\text{-th}$Primal Variable$x_j \times 0$|$j\text{-th}$Constraint of type$\times |\n| j\text{-th}$Primal Variable Unrestricted |$j\text{-th}$Constraint of type$= |\n\n - **Economic Interpretation of Duality**:\n - Dual variables y_i^$represent the **Shadow Prices** or **Marginal Imputed Values** of scarce resources$i.\n - y_i^$measures the rate of increase in optimal profit$Z^$per unit increase in the availability of resource$i$.

  • Fundamental Duality Theorem: If either the primal or dual problem possesses an optimal solution, the other problem also possesses an optimal solution, and the optimal objective values are strictly equal:     $Z^* = W^*$

Transportation Models

• Mathematical Model of the Transportation Problem

  • A special structured class of LP problems concerning shipping a single commodity from $m$ sources (origins) with capacities $a_i$ to $n$ sinks (destinations) with demands $b_j$ at minimum total cost.

  • Mathematical Formulation:     $\text{Minimize } Z = \times_{i=1}^m \times_{j=1}^n c_{ij} X_{ij}$     $\text{Subject to } \times_{j=1}^n X_{ij} = a_i \text{ for } i = 1, 2, \times, m \text{ (Supply Constraints)}$     $\times_{i=1}^m X_{ij} = b_j \text{ for } j = 1, 2, \times, n \text{ (Demand Constraints)}$     $X_{ij} \times 0 \text{ for all } i, j$

  • Balanced Transportation Problem Condition:     $\times_{i=1}^m a_i = \times_{j=1}^n b_j$

  • Unbalanced Transportation Problems:

  • If Total Supply $>$ Total Demand: Add a dummy destination column with demand $b_{\text{dummy}} = \times a_i - \times b_j$ and unit costs $c_{i, \text{dummy}} = 0$.

  • If Total Demand $>$ Total Supply: Add a dummy origin row with supply $a_{\text{dummy}} = \times b_j - \times a_i$ and unit costs $c_{\text{dummy}, j} = 0$.

• Algorithms for Initial Basic Feasible Solution (IBFS)

  • 1. North-West Corner (NWC) Rule

  • Step 1: Start at the top-leftmost cell $(1,1)$.

  • Step 2: Allocate maximum possible quantity $X_{11} = \text{Min}(a_1, b_1)$.

  • Step 3: Adjust remaining supply and demand. If supply is exhausted, move down to the next row. If demand is satisfied, move right to the next column.

  • Step 4: Repeat until all supply and demand are satisfied. Ignores transportation costs entirely.

  • 2. Least Cost Method (LCM) / Matrix Minimum Method

  • Step 1: Identify the cell with the lowest unit cost $c_{ij}$ across the entire matrix.

  • Step 2: Allocate maximum possible quantity $X_{ij} = \text{Min}(a_i, b_j)$ to this cell.

  • Step 3: Cross out the satisfied row or column. Repeat the process for the remaining uncrossed cells.

  • 3. Vogel’s Approximation Method (VAM)

  • Considers the unit penalty cost incurred if the lowest-cost cell is missed.

  • Step 1: For each row and column, calculate its Penalty (arithmetic difference between the lowest and next-to-lowest cost elements).

  • Step 2: Identify the row or column with the largest penalty.

  • Step 3: Allocate the maximum feasible quantity $X_{ij} = \text{Min}(a_i, b_j)$ to the lowest-cost cell in that selected row or column.

  • Step 4: Cross out the fully satisfied row or column. Re-calculate penalties for remaining rows/columns and repeat until all allocations are complete.

• Optimality Test: Modified Distribution (MODI) Method / $u_i, v_j$ Method

  • Prerequisites for Optimality Testing:

  1. Total number of occupied cells must equal exactly m + n - 1$.\n 2. Allocations must be in **independent positions** (must not contain closed loops among occupied cells).\n - **MODI Algorithm Steps**:\n 1. For all occupied cells (i, j), solve the system of equations:\n       u_i + v_j = c_{ij}\n       (Set one multiplier arbitrarily, e.g., u_1 = 0$, then solve for all$u_i$and$v_j).\n 2. For every unoccupied cell (i, j), calculate the net evaluation / Opportunity Cost:\n       \times_{ij} = c_{ij} - (u_i + v_j)\n 3. **Optimality Criterion**:\n - Minimization: If all \times_{ij} \times 0, the current schedule is optimal.\n - Maximization: If all \times_{ij} \times 0, the current schedule is optimal.\n 4. **Re-allocation Loop**: If negative \times_{ij}$exist (for minimization), select the unoccupied cell with the **most negative**$\times_{ij}$as the entering cell. Construct a closed loop starting at this cell, making alternating horizontal and vertical jumps between occupied cells. Assign alternating$+ \times$and$-\times$signs at loop corners. Set$\times = \text{Min}(\text{allocations at } -\text{ signed corners})$. Add$\times$to$+$corners and subtract$\times$from$-$ corners.

• Degeneracy in Transportation Problems

  • Occurs when the number of occupied cells is strictly less than $m + n - 1$ (typically happens when a row supply and column demand are satisfied simultaneously).

  • Resolution: Assign an infinitely small positive fictitious quantity $\times$ to one or more unoccupied, independent cells so that the total occupied count equals $m + n - 1$. The quantity $\times \rightarrow 0$ in cost calculations.

Assignment Models

• Structure and Mathematical Model

  • A specialized class of transportation problems where $n$ tasks/jobs are assigned to $n$ agents/facilities on a strict one-to-one basis.

  • Mathematical Model:     $\text{Minimize } Z = \times_{i=1}^n \times_{j=1}^n c_{ij} X_{ij}$     $\text{Subject to } \times_{j=1}^n X_{ij} = 1 \text{ for } i = 1, 2, \times, n$     $\times_{i=1}^m X_{ij} = 1 \text{ for } j = 1, 2, \times, n$     X_{ij} \times \begin{cases} 1 & \text{if job } i \text{ is assigned to person } j \ 0 & \text{otherwise} \times

• The Hungarian Algorithm (Kőnig-Egerv!ry Method)

  • Based on the principle that adding or subtracting a constant from any row or column of a cost matrix preserves the optimal assignment schedule.

  • Step-by-Step Procedure:

  1. Row Reduction: Subtract the minimum element of each row from all elements in that row.

  2. Column Reduction: Subtract the minimum element of each column from all elements in that column.

  3. Assignment Scanning: Inspect rows for a single uncrossed zero ($0$). Assign that zero ($\times$) and cross out ($\times$) all other zeros in the same column. Repeat for columns.

  4. Covering Zeros: If total assignments equal $n$, the solution is optimal. If total assignments $< n$, draw the minimum number of horizontal and vertical lines to cover all zeros using the 5-step marking rule:

     • Mark ($\times$) all unassigned rows.

     • Mark ($\times$) all columns having zeros in marked rows.

     • Mark ($\times$) all rows having assignments in marked columns.

     • Repeat until no further marks can be made.

     • Draw lines through all unmarked rows and marked columns.

  5. Matrix Revision: Find the smallest uncovered element $k$. Subtract $k$ from all uncovered elements, and add $k$ to elements at the intersection of two covering lines. Leave elements covered by a single line unchanged.

  6. Repeat assignment scanning until $n$ assignments are obtained.

• Special Variants in Assignment Problems

  • Unbalanced Assignment Problem: If rows $\neq$ columns ($m \neq n$), add dummy rows or dummy columns filled with zero costs ($c_{ij} = 0$) to make the matrix square ($n \times n$).

  • Maximization Assignment Problem: Convert profit matrix into a relative loss matrix by subtracting every element from the single largest element in the matrix, then apply standard Hungarian minimization.

  • Prohibited / Impossible Assignments: If a person cannot be assigned to a specific job, set its cost $c_{ij} = \times$ (a prohibitive infinite cost).

Queuing Theory

• System Components and Terminology

  • Input Source / Calling Population: Homogeneous pool of potential customers (finite or infinite).

  • Arrival Rate ($\times$): Average number of customer arrivals per unit time, modeled via a Poisson Distribution.

  • Service Rate ($\times$): Average number of customers served per unit time per channel, modeled via an Exponential Distribution.

  • Traffic Intensity / System Utilization ($\times$):     $\times = \frac{\times}{k \times}$     where $k$ is the number of parallel service channels. System stability requires $\times < 1$

  • Queue Discipline: Order of service selection (e.g., FCFS/FIFO: First-Come, First-Served).

• Standard Performance Notation and Key Definitions

  • $L$: Expected number of customers in the system (queue + service).

  • $L_q$: Expected number of customers in the queue.

  • $W$: Expected time spent in the system.

  • $W_q$: Expected waiting time spent in the queue.

  • $L_n$: Expected number of customers in a non-empty queue.

  • $W_n$: Expected waiting time for a non-empty queue.

• Single-Channel Infinite Population Model ($M/M/1 : \times/FCFS$)

  • Derivation Equations:

  • Probability of zero units in system (idle probability):       $P_0 = 1 - \frac{\times}{\times}$

  • Probability of $n$ units in system:       P_n = \begin{pmatrix} 1 - \frac{\times}{\times} \right) \begin{pmatrix} \frac{\times}{\times} \right)^n

  • Expected number in system ($L$):       $L = \frac{\times}{\times - \times}$

  • Expected number in queue ($L_q$):       $L_q = \frac{\times^2}{\times(\times - \times)}$

  • Expected time in system ($W$):       $W = \frac{1}{\times - \times}$

  • Expected waiting time in queue ($W_q$):       $W_q = \frac{\times}{\times(\times - \times)}$

  • Expected length of non-empty queue ($L_n$):       $L_n = \frac{\times}{\times - \times}$

  • Expected waiting time for non-empty queue ($W_n$):       $W_n = \frac{1}{\times - \times}$

  • Probability of waiting longer than time $t$ in queue:       $P(W_q \times t) = \frac{\times}{\times} e^{-(\times - \times)t}$

  • Probability of spending longer than time $t$ in system:       $P(W \times t) = e^{-(\times - \times)t}$

• Multi-Channel Infinite Population Model ($M/M/k : \times/FCFS$)

  • Probability of zero units in system ($P_0$):     P_0 = \begin{bmatrix} \times_{n=0}^{k-1} \frac{1}{n!} \begin{pmatrix} \frac{\times}{\times} \right)^n + \frac{1}{k!} \begin{pmatrix} \frac{\times}{\times} \right)^k \begin{pmatrix} \frac{k\times}{k\times - \times} \right) \right]^{-1}

  • Probability that an arriving customer must wait:     P(n \times k) = \frac{1}{k!} \begin{pmatrix} \frac{\times}{\times} \right)^k \begin{pmatrix} \frac{k\times}{k\times - \times} \right) P_0

  • Expected number in queue ($L_q$):     L_q = \begin{bmatrix} \frac{1}{(k-1)!} \begin{pmatrix} \frac{\times}{\times} \right)^k \frac{\times \times}{(k\times - \times)^2} \right] P_0

  • Expected number in system ($L$): $L = L_q + \frac{\times}{\times}$

  • Expected time in queue ($W_q$): $W_q = \frac{L_q}{\times}$

  • Expected time in system ($W$): $W = W_q + \frac{1}{\times}$

• Multi-Channel Queue with Finite Calling Population ($M/M/k : F/FCFS$)

  • System bounded by population size $M$

  • Probability $P_0$:     P_0 = \begin{bmatrix} \times_{n=0}^{k-1} \frac{M!}{(M-n)! n!} \begin{pmatrix} \frac{\times}{\times} \right)^n + \times_{n=k}^M \frac{M!}{(M-n)! k! k^{n-k}} \begin{pmatrix} \frac{\times}{\times} \right)^n \right]^{-1}

Replacement Models

• Types of Replacement Decisions

  1. Equipment deteriorating gradually over time (increasing maintenance costs, declining operational efficiency).

  2. Equipment subject to sudden, complete failure (catastrophic failure).

• Replacement Policy for Items Deteriorating Without Time Value of Money

  • Equipment capital cost $M$, salvage value $S$, running cost in year $i$ is $R_i$

  • Total Cost for $n$ years $TC(n)$:
        $TC(n) = (M - S) + \times_{i=1}^n R_i$

  • Average Annual Cost $ATC(n)$:
        $ATC(n) = \frac{TC(n)}{n} = \frac{(M - S) + \times_{i=1}^n R_i}{n}$

  • Decision Rule: Replace the equipment at the end of year $n$ when $ATC(n)$ reaches its absolute minimum, or when the running cost for the next year ($R_{n+1}$) exceeds the current average annual cost ($ATC(n)$).

• Replacement Policy for Items Deteriorating With Time Value of Money

  • Considers annual interest rate $r$ and discount factor $v = \frac{1}{1 + r}$.

  • Present Worth of total expenditure for $n$ years $P(n)$:
        $P(n) = M + R_1 + v R_2 + v^2 R_3 + \times + v^{n-1} R_n$

  • Fixed Equivalent Annual Installment Cost ($x$):     $x = \frac{P(n)}{\times_{i=1}^n v^{i-1}} = \frac{P(n) (1 - v)}{1 - v^n}$

  • Decision Rule: Replace equipment at year $n$ that minimizes equivalent annual cost $x$

• Replacement Policies for Items Subject to Sudden Complete Failure

  • Strategies:

  • Individual Replacement: Replace items only as and when they fail.

  • Group Replacement: Replace all items simultaneously at fixed periodic intervals $P$, and replace individually any items that fail in between intervals.

  • Group Replacement Algorithm:

  1. Determine probability of failure $p_i$ in week $i$ from mortality tables.

  2. Calculate expected failed units $n_i$ in week $i$ given initial stock $N_0$:        $n_0 = N_0$        $n_1 = N_0 p_1$        $n_2 = N_0 p_2 + n_1 p_1$        $n_3 = N_0 p_3 + n_1 p_2 + n_2 p_1$        $n_i = \times_{j=1}^i n_{i-j} p_j$

  3. Calculate total cumulative cost up to week $n$:        TC(n) = (N_0 \times \text{Group Cost}) + \begin{pmatrix} \times_{i=1}^n n_i \right) \times \text{Individual Cost}

  4. Calculate Average Cost per week: $ATC(n) = \frac{TC(n)}{n}$

  5. Select group replacement period $n$ yielding minimum $ATC(n)$.

  6. Compare minimum $ATC(n)$ with pure Individual Replacement average cost per week ($\frac{N_0}{\text{Mean Life}} \times \text{Individual Cost}$).

• Staff Replacement / Manpower Planning Model

  • Determines annual recruitment requirements to maintain a target constant workforce size given historical length-of-service attrition probabilities.

Dynamic Programming

• Fundamental Concept and Bellman's Principle of Optimality

  • Dynamic Programming (DP) breaks complex multi-stage decision problems into a sequence of smaller, single-stage sub-problems solved recursively.

  • Bellman’s Principle of Optimality: "An optimal policy has the property that, whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with respect to the state resulting from the first decision."

• Core Structural Characteristics of DP

  1. The problem is divided into discrete stages $n = 1, 2, \times, N$

  2. Each stage has a set of associated states $s$

  3. Decision variable $x_n$ transforms the current state at stage $n$ into a state for stage $n-1$

  4. Recursive Optimization Formula (Backward Induction):      f_n^*(s) = \text{Optimize}_{x_n} \begin{bmatrix} C_s x_n + f_{n-1}^*(s - x_n) \right]

  5. Optimization begins at the final stage ($n=1$) and moves backward stage-by-stage to the initial stage ($n=N$).

• Standard Applications and Example Formulations

  • Stagecoach Problem (Shortest Path): Finding the minimum distance route across a multi-stage network by computing backward stage returns $f_n^*(s)$.

  • Capital Allocation Problem: Allocating $S$ units of capital across $N$ business ventures to maximize total return. Stage $n$ represents venture $n$, state $s$ represents available capital, decision $x_n$ represents capital assigned to venture $n$.

  • Cargo Loading / Knapsack Problem: Loading a transport vehicle of weight capacity $W$ with $N$ item types to maximize total payload value. Stage $n$ represents item type $n$, state $s$ represents remaining weight capacity, decision $x_n$ represents quantity of item type $n$ loaded.

Miscellaneous Topics in Operations Research

• Sequencing Theory

  • Order of performing $n$ jobs through $m$ machines to minimize total elapsed time ($T$

  • Johnson’s Algorithm for $n$ Jobs on $2$ Machines (Order $AB$):

  1. Find the minimum processing time among all $A_i$ and $B_i$

  2. If the minimum time occurs on Machine $A$ ($A_i$), place job $i$ in the first available position of the sequence.

  3. If the minimum time occurs on Machine $B$ ($B_j$), place job $j$ in the last available position of the sequence.

  4. Cross out the assigned job and repeat for remaining jobs.

• Traveling Salesman Problem (TSP)

  • A salesman must visit $n$ cities and return to his starting city, minimizing total distance/cost, visiting each city exactly once.

  • Formulated as an assignment problem with infinite diagonal elements ($c_{ii} = \times$) to prevent self-loops, plus additional constraints to prevent sub-tours.

• Integer Programming

  • Requires decision variables to take strict integer values.

  • Types: Pure Integer LP, Mixed Integer LP, Zero-One (0-1) Binary LP.

  • Algorithms:

  • Gomory’s Cutting Plane Method: Systematically adds linear secondary constraints ("cuts") to eliminate non-integer space without cutting off feasible integer points.

  • Branch and Bound Method (Land-Doig / Dakin): Systematically partitions (branches) the continuous LP solution space into sub-problems by bounding fractional variables ($X_j \times \times X_j \times$ or $X_j \times \times X_j \times + 1$) until the optimal integer node is identified.

• Game Theory

  • Analyzes competitive decision situations between rational adversaries under conflicting interests.

  • Two-Person Zero-Sum Game: Total gain of one player equals total loss of the second player.

  • Saddle Point: A payoff matrix entry that is simultaneously the minimum in its row and the maximum in its column. If a saddle point exists, players use Pure Strategies.

  • Mixed Strategies: Used when no saddle point exists; players select strategies probabilistically using LP or algebraic formulas.

• Simulation Modeling

  • Computer-based imitation of dynamic real-world systems over time.

  • Monte Carlo Simulation: Employs artificial random sampling from known probability distributions (using random number generators) to evaluate complex stochastic systems analytically intractable.

• Markov Chains

  • A stochastic process possessing the Markovian Property: The conditional probability of a future state depends strictly on the present state and is independent of past historical states (memoryless property).

• Decision Analysis Environment Classifications

  • Decision Making Under Certainty: Complete, deterministic knowledge of outcomes.

  • Decision Making Under Risk: Future states of nature are probabilistic with known probability distributions.

  • Criteria: Expected Monetary Value (EMV), Expected Opportunity Loss (EOL).

  • Decision Making Under Uncertainty: Probabilities of future states of nature are completely unknown.

  • Criteria:

    • Laplace: Assumes equal probabilities for all states.

    • Maximin / Minimax: Pessimistic approach (selects best of the worst outcomes).

    • Maximax: Optimistic approach (selects best of the best outcomes).

    • Savage (Minimax Regret): Minimizes maximum regret/opportunity loss.

    • Hurwicz (Criterion of Realism): Weighted balance between optimism coefficient $\times$ and pessimism $(1 - \times)$.