Study guide
15.3 Operations Research: Linear Programming & Transportation/Assignment
Coal India Management Trainee CIL MT
Track your progress as you read
Finished sections get a check mark.
1 Chapter 1: CIL MT Exam Overview & Coal Sector Landscape
1.1 CIL MT Exam Pattern, Marking Scheme & Strategy 1.2 Coal India Limited: Corporate Structure, Maharatna Status & Subsidiaries 1.3 Indian Coal Mining Sector, Energy Mix & Environmental Regulations
2 Chapter 2: Paper-I General Awareness, Polity & Current Affairs
2.1 Indian Constitution, Governance & Statutory Bodies 2.2 Indian Economy, Union Budget & Economic Planning 2.3 Indian Geography, Mineral Belts & Environmental Ecology 2.4 Modern Indian History, Freedom Struggle & Cultural Heritage 2.5 General Science: Physics, Chemistry & Biology Fundamentals 2.6 Inventions, Discoveries & Scientific-Technological Development 2.7 Uses of Internet, Computer Awareness & Digital Governance 2.8 National & International Organisations 2.9 Awards, Honours & Sports 2.10 Books & Authors, Important Monuments & Places of India 2.11 Ports, Power Plants & Infrastructure of India 2.12 Climate Change, SDGs, National Parks & Wildlife Sanctuaries 2.13 Flagship Government Programmes & Current Affairs Method 2.14 World Physical, Social & Economic Geography
3 Chapter 3: Paper-I Reasoning & Logical Ability
3.1 Series Completion, Coding-Decoding & Semantic Analogies 3.2 Syllogisms, Logical Deduction & Venn Diagrams 3.3 Seating Arrangements, Linear/Circular Alignments & Puzzles 3.4 Direction Sense, Blood Relations & Order/Ranking 3.5 Alphabetical & Alphanumeric Series 3.6 Statement & Conclusions, Statement & Arguments 3.7 Clocks & Calendars 3.8 Cubes, Dice & Figure Counting 3.9 Mirror Images, Water Images, Embedded Figures & Non-Verbal Series 3.10 Decision Making & Data Analysis in Reasoning
4 Chapter 4: Paper-I Numerical Ability & Quantitative Aptitude
4.1 Arithmetic Foundations: Percentages, Profit & Loss, Ratio & Proportion 4.2 Averages, Simple/Compound Interest, Alligations & Mixtures 4.3 Time & Work, Pipes & Cisterns, Time, Speed & Distance 4.4 Algebra, Mensuration, Geometry & Data Interpretation (DI) 4.5 Number System, LCM, HCF & Decimal Fractions 4.6 Surds, Indices & Simplification 4.7 Problems on Ages 4.8 Boats & Streams and Problems on Trains 4.9 Permutations & Combinations 4.10 Probability for Quantitative Aptitude
5 Chapter 5: Paper-I General English & Verbal Ability
5.1 English Grammar, Error Spotting & Sentence Correction 5.2 Vocabulary Building: Synonyms, Antonyms, Idioms & Phrases 5.3 Reading Comprehension, Cloze Tests & Para Jumbles 5.4 Fill in the Blanks, Cloze Passages & Sentence Completion 5.5 Jumbled Sentences & Sentence Improvement
6 Chapter 6: Paper-II Engineering Mathematics
6.1 Matrix Algebra, Rank & Systems of Linear Equations 6.2 Eigenvalues, Eigenvectors & the Cayley-Hamilton Theorem 6.3 Limits, Continuity, Differentiability & Mean Value Theorems 6.4 Maxima-Minima, Indeterminate Forms & Taylor Series 6.5 Definite, Improper, Double & Triple Integrals 6.6 Partial Derivatives, Total Derivative & Multivariable Optimisation 6.7 First-Order Differential Equations: Linear & Non-Linear 6.8 Higher-Order Linear Differential Equations & Engineering Applications 6.9 Laplace Transforms & Transfer-Function Methods 6.10 Probability, Conditional Probability & Bayes' Theorem 6.11 Random Variables, Distributions & Descriptive Statistics 6.12 Numerical Methods: Root Finding, Integration & ODE Solvers
7 Chapter 7: Paper-II Engineering Mechanics & Statics-Dynamics
7.1 Force Systems, Coplanar Equilibrium & Lami's Theorem 7.2 Plane Trusses, Friction Mechanics & Screws/Wedges 7.3 Centroids, Center of Gravity & Moment of Inertia 7.4 Kinematics, Kinetics of Particles & Rigid Body Dynamics 7.5 Virtual Work & Lagrange's Equation 7.6 Rolling Friction, Belt-Pulley Drives, Brakes, Clutches & Vehicle Dynamics
8 Chapter 8: Paper-II Mechanics of Materials & Structural Integrity
8.1 Simple Stresses, Strains, Elastic Moduli & Thermal Stresses 8.2 Principal Stresses, Strain Energy & Mohr's Circle 8.3 Shear Force & Bending Moment Diagrams, Beam Bending & Shear Stresses 8.4 Torsion of Circular Shafts, Springs & Column Buckling 8.5 Thin Cylinders, Spheres & Thick-Walled Pressure Vessels 8.6 Deflection of Beams: Double Integration, Macaulay & Moment-Area 8.7 Shear Centre & Unsymmetrical Bending 8.8 Strain Gauges, Rosettes & Experimental Stress Analysis 8.9 Mechanical Testing: Universal Testing Machine, Hardness & Impact
9 Chapter 9: Paper-II Theory of Machines & Mechanical Vibrations
9.1 Simple Mechanisms, Kinematic Inversions & Velocity/Acceleration Diagrams 9.2 Cams & Followers, Toothed Gearing & Epicyclic Gear Trains 9.3 Flywheels, Centrifugal/Inertia Governors & Rotor Balancing 9.4 Free, Damped & Forced Single-Degree-of-Freedom Vibrations 9.5 Gyroscopic Couple & Gyroscopic Effects
10 Chapter 10: Paper-II Machine Design & Failure Theories
10.1 Static Failure Theories & Variable/Fatigue Loading 10.2 Design of Threaded Fasteners, Welded & Riveted Joints 10.3 Design of Shafts, Keys, Couplings & Rolling/Sliding Bearings 10.4 Design of Spur, Helical, Bevel & Worm Gears 10.5 Design of Helical, Leaf & Torsion Springs 10.6 Design of Brakes & Clutches: Energy, Lining Pressure & Heat
11 Chapter 11: Paper-II Fluid Mechanics & Hydraulic Machinery
11.1 Fluid Properties, Hydrostatic Forces & Buoyancy 11.2 Fluid Kinematics, Continuity & Bernoulli's Equation 11.3 Viscous Flow in Pipes, Boundary Layer & Minor Losses 11.4 Hydraulic Turbines, Centrifugal & Reciprocating Pumps 11.5 Dimensional Analysis, Similitude & Model Testing 11.6 Control-Volume Analysis: Continuity, Momentum & Energy
12 Chapter 12: Paper-II Thermodynamics, Thermal Cycles & Turbomachinery
12.1 Fundamental Concepts, First & Second Laws of Thermodynamics 12.2 Entropy, Availability, Exergy & Properties of Pure Substances 12.3 Air-Standard Gas Power Cycles: Otto, Diesel, Dual & Brayton 12.4 Vapour Power Cycles: Ideal, Reheat & Regenerative Rankine Cycles 12.5 Thermodynamic Relations: Maxwell, Clausius-Clapeyron & Joule-Thomson 12.6 Behaviour of Ideal & Real Gases and Equations of State 12.7 Air & Gas Compressors: Reciprocating, Rotary & Multi-Stage 12.8 Steam & Gas Turbines: Impulse, Reaction & Velocity Diagrams
13 Chapter 13: Paper-II Heat Transfer, Refrigeration & Air Conditioning
13.1 Steady & Unsteady Conduction, Extended Surfaces (Fins) 13.2 Forced/Natural Convection, Radiation & Heat Exchanger LMTD/NTU 13.3 Vapour Compression & Vapour Absorption Refrigeration Systems 13.4 Psychrometric Properties, Processes & Air Conditioning Systems 13.5 Gas Refrigeration, Heat Pump Cycles & Cryogenics
14 Chapter 14: Paper-II Materials Science, Metallurgy & Manufacturing Technology
14.1 Crystal Structures, Phase Diagrams & Iron-Iron Carbide Equilibrium 14.2 Heat Treatment Processes & Engineering Alloy Steels 14.3 Casting Processes, Metal Forming & Welding Metallurgy 14.4 Metal Cutting Mechanics, Tool Life & Machine Tools 14.5 Plastic Deformation, Yield Criteria & Load Estimation in Bulk Forming 14.6 Sheet Metal Forming: Shearing, Bending & Deep Drawing 14.7 Powder Metallurgy 14.8 Brazing, Soldering & Adhesive Bonding 14.9 Non-Traditional Machining: EDM, ECM, USM, AJM, LBM & EBM 14.10 Abrasive Machining, Grinding & Superfinishing 14.11 Principles of Work Holding, Jigs & Fixtures 14.12 Economics of Machining & Tool Life Optimisation
15 Chapter 15: Paper-II Metrology, Quality Control & Industrial Engineering / OR
15.1 Limits, Fits, Tolerances, Gauges & Surface Metrology 15.2 Production Planning, Forecasting & Inventory Control Models 15.3 Operations Research: Linear Programming & Transportation/Assignment 15.4 Project Management: CPM, PERT, Network Analysis & Crashing 15.5 Comparators & Interferometry 15.6 Coordinate Measuring Machines & Machine Tool Alignment Testing 15.7 Computer Integrated Manufacturing: CAD/CAM & Integration Tools 15.8 NC/CNC Machines & CNC Part Programming 15.9 Material Requirements Planning, Scheduling & Sequencing 15.10 Queuing Theory & Simple Queuing Models 15.11 Network Flow Models: Shortest Route, Maximal Flow & Spanning Tree
15.3 Operations Research: Linear Programming & Transportation/Assignment
Key Takeaways Explain This Topic AI
The Fundamental Theorem of Linear Programming guarantees that if an optimal solution exists, at least one corner point of the convex feasible region is optimal
Simplex iterations identify the entering variable via the most positive C_j - Z_j in maximization and select the leaving variable via the minimum positive ratio test
The dual of a maximization LPP with <= constraints is a minimization LPP with >= constraints; the optimal dual variables represent the economic shadow prices of the primal resources
A transportation problem with m origins and n destinations has an initial basic feasible solution with exactly m + n - 1 non-degenerate independent allocated cells
The Hungarian algorithm solves an n x n assignment problem in polynomial time by operating on the reduced cost matrix
Last updated: August 2026
Operations Research: Linear Programming & Transportation/Assignment
Optimization is central to modern industrial management. In Coal India's multi-subsidiary logistics networks, Operations Research (OR) models dictate coal blending proportions, fleet allocation from open-cast pits to washeries, railway siding dispatch schedules, and overhaul worker assignments.
1. Linear Programming Problem (LPP) Formulation & Geometry
General Mathematical Model Maximize / Minimize Z = ∑ j = 1 n c j x j = c T x \text{Maximize / Minimize } Z = \sum_{j=1}^n c_j x_j = \mathbf{c}^T \mathbf{x} Maximize / Minimize Z = j = 1 ∑ n c j x j = c T x Subject to: ∑ j = 1 n a i j x j ( ≤ , = , ≥ ) b i , i = 1 , 2 , … , m \text{Subject to: } \sum_{j=1}^n a_{ij} x_j (\le, =, \ge) b_i, \quad i = 1, 2, \dots, m Subject to: j = 1 ∑ n a ij x j ( ≤ , = , ≥ ) b i , i = 1 , 2 , … , m and Non-negativity: x j ≥ 0 , j = 1 , 2 , … , n \text{and Non-negativity: } x_j \ge 0, \quad j = 1, 2, \dots, n and Non-negativity: x j ≥ 0 , j = 1 , 2 , … , n
Geometric Characteristics and Corner Point Theorem
Convex Set: A region S S S is convex if for any two points x 1 , x 2 ∈ S \mathbf{x}_1, \mathbf{x}_2 \in S x 1 , x 2 ∈ S , the entire line segment connecting them λ x 1 + ( 1 − λ ) x 2 ∈ S \lambda \mathbf{x}_1 + (1 - \lambda)\mathbf{x}_2 \in S λ x 1 + ( 1 − λ ) x 2 ∈ S for all λ ∈ [ 0 , 1 ] \lambda \in [0, 1] λ ∈ [ 0 , 1 ] .
Convex Feasible Region: The intersection of linear half-spaces forms a convex polygon (2D) or convex polyhedron ( n n n D).
Extreme Point (Corner Point) Theorem: The objective function achieves its optimal value (maximum or minimum) at one of the extreme (corner) points of the convex feasible region. x2 ^
- |
- | Binding Constraint 2
- |\ Optimal Vertex (x1*, x2*)
- | \______ *
- | \ \____ |\ Iso-profit line: Z = c1*x1 + c2*x2
- | \ Feasible\ | \
- | \ Region \| \
- | \ | \
- 0 +------\--------+----\-----> x1
- Binding Constraint 1
- Classification of LPP Solutions
Solution Category Graphical Behavior Algebraic Condition
Unique Optimal Objective line touches the feasible region at a single distinct corner vertex. Single basic feasible solution satisfies optimality criterion.
Multiple / Alternate Optimal Objective line is parallel to a binding constraint edge; touches an entire boundary segment. C j − Z j = 0 C_j - Z_j = 0 C j − Z j = 0 for a non-basic variable in the optimal simplex tableau.
Unbounded Solution The feasible region is open/unbounded in the direction of optimization, allowing Z → ∞ Z \to \infty Z → ∞ . In simplex, all substitution rates a i r ≤ 0 a_{ir} \le 0 a i r ≤ 0 in the key column (no valid leaving variable).
Infeasible Solution No point satisfies all constraints simultaneously (feasible region is empty, ∅ \emptyset ∅ ). Simplex terminates with one or more artificial variables remaining in the basis at a non-zero level.
Degenerate Solution Three or more constraint lines intersect at the same 2D vertex ( > m > m > m hyperplanes in n n n D). A tie occurs in the minimum ratio test; one or more basic variables become zero in the next tableau.
Redundant Constraint A constraint whose removal does not alter the geometry of the feasible region. Does not form any boundary of the active feasible region.
- 2. Simplex Method Fundamentals
- Standard Form Conversion
To solve via Simplex, constraints must be converted into equalities with non-negative right-hand sides ( b i ≥ 0 b_i \ge 0 b i ≥ 0 ):
≤ \le ≤ Constraint: Add a Slack variable s i ≥ 0 s_i \ge 0 s i ≥ 0 (cost in objective = 0 = 0 = 0 ). ∑ a i j x j + s i = b i \sum a_{ij} x_j + s_i = b_i ∑ a ij x j + s i = b i
≥ \ge ≥ Constraint: Subtract a Surplus variable e i ≥ 0 e_i \ge 0 e i ≥ 0 (cost = 0 = 0 = 0 ) and add an Artificial variable A i ≥ 0 A_i \ge 0 A i ≥ 0 (penalty cost in objective = − M = -M = − M for Maximize, + M +M + M for Minimize). ∑ a i j x j − e i + A i = b i \sum a_{ij} x_j - e_i + A_i = b_i ∑ a ij x j − e i + A i = b i
= = = Constraint: Add an Artificial variable A i ≥ 0 A_i \ge 0 A i ≥ 0 . ∑ a i j x j + A i = b i \sum a_{ij} x_j + A_i = b_i ∑ a ij x j + A i = b i
Basic Definitions in Simplex
For a system of m m m linear equations with n n n variables ( n > m n > m n > m ):
Basic Solution: Set ( n − m ) (n - m) ( n − m ) non-basic variables to 0 and solve for the remaining m m m basic variables.
Basic Feasible Solution (BFS): A basic solution where all basic variables are non-negative ( x B i ≥ 0 x_{Bi} \ge 0 x B i ≥ 0 ).
Maximum possible basic solutions: ( n m ) = n ! m ! ( n − m ) ! \binom{n}{m} = \frac{n!}{m!(n - m)!} ( m n ) = m ! ( n − m )! n ! .
- Step-by-Step Simplex Iteration Mechanics +------------------------------+
- | Formulate Standard Tableau |
- +------------------------------+
- |
- v
- +------------------------------+
- | Compute Net Evaluations |
- | Delta_j = C_j - Z_j |
- +------------------------------+
- |
- +--------------+--------------+
- | |
All Delta_j <= 0? Any Delta_j > 0?
- | |
- v v
- +-----------------+ +-------------------+
- | OPTIMALITY | | KEY COLUMN |
- | REACHED | | Enter Max Delta_j |
- +-----------------+ +-------------------+
- |
- v
- +-------------------+
- | KEY ROW |
- | Min Positive Ratio|
- | theta = b_i / a_ir|
- +-------------------+
- |
- v
- +-------------------+
- | PIVOT OPERATION |
- | Gauss-Jordan Row |
- | Transformations |
- +-------------------+
- |
- + (Loop back)
Net Evaluation (Index) Row Δ j \Delta_j Δ j : Δ j = C j − Z j = C j − ∑ i = 1 m c B i a i j \Delta_j = C_j - Z_j = C_j - \sum_{i=1}^m c_{Bi} a_{ij} Δ j = C j − Z j = C j − i = 1 ∑ m c B i a ij
Optimality Criterion (for Maximization):
If all Δ j = C j − Z j ≤ 0 \Delta_j = C_j - Z_j \le 0 Δ j = C j − Z j ≤ 0 , the current solution is optimal .
Entering Variable (Key Column r r r ): Select variable with max ( C j − Z j > 0 ) \text{Select variable with } \max(C_j - Z_j > 0) Select variable with max ( C j − Z j > 0 )
Leaving Variable (Key Row k k k - Minimum Positive Ratio Test): θ = min i { b i a i r ∥ a i r > 0 } \theta = \min_{i} \left\{ \frac{b_i}{a_{ir}} \;\middle\|\; a_{ir} > 0 \right\} θ = i min { a i r b i a i r > 0 }
Pivot Element: Intersection of Key Column and Key Row ( a k r a_{kr} a k r ). Perform Gauss-Jordan row transformations to make a k r = 1 a_{kr} = 1 a k r = 1 and all other entries in column r r r equal to 0 0 0 .
3. Duality in Linear Programming
Every linear programming problem (the Primal ) has an associated twin problem (the Dual ) formed from the same underlying parameters.
Primal-Dual Relationships
Feature Primal Problem (Standard Form) Dual Problem
Objective Maximize Z = c T x \text{Maximize } Z = \mathbf{c}^T \mathbf{x} Maximize Z = c T x Minimize W = b T y \text{Minimize } W = \mathbf{b}^T \mathbf{y} Minimize W = b T y
Constraints A x ≤ b \mathbf{A}\mathbf{x} \le \mathbf{b} Ax ≤ b A T y ≥ c \mathbf{A}^T \mathbf{y} \ge \mathbf{c} A T y ≥ c
- Variables n n n variables, x ≥ 0 \mathbf{x} \ge 0 x ≥ 0 m m m variables, y ≥ 0 \mathbf{y} \ge 0 y ≥ 0
- Equations m m m constraints n n n constraints
- RHS Constants b \mathbf{b} b c \mathbf{c} c (Objective coefficients of primal)
- Objective Coefficients c \mathbf{c} c b \mathbf{b} b (RHS constants of primal)
- Dual of Dual Dual of Dual is the Primal —
- Fundamental Duality Theorems
Weak Duality Theorem: For any feasible primal solution x \mathbf{x} x and feasible dual solution y \mathbf{y} y : c T x ≤ b T y \mathbf{c}^T \mathbf{x} \le \mathbf{b}^T \mathbf{y} c T x ≤ b T y
Strong (Fundamental) Duality Theorem: If either the primal or dual has a finite optimal solution, the other also has a finite optimal solution, and their optimal objective values are identical: Z ∗ = c T x ∗ = b T y ∗ = W ∗ Z^* = \mathbf{c}^T \mathbf{x}^* = \mathbf{b}^T \mathbf{y}^* = W^* Z ∗ = c T x ∗ = b T y ∗ = W ∗
Unboundedness Theorem: If the primal is unbounded, the dual is infeasible. If the dual is unbounded, the primal is infeasible.
Shadow Prices ( y i ∗ y_i^* y i ∗ ): The optimal value of dual variable y i ∗ y_i^* y i ∗ represents the marginal economic value (shadow price) of resource i i i : y i ∗ = ∂ Z ∗ ∂ b i y_i^* = \frac{\partial Z^*}{\partial b_i} y i ∗ = ∂ b i ∂ Z ∗ It represents the maximum amount a manager should pay for one additional unit of resource b i b_i b i .
Complementary Slackness Theorem: x j ∗ [ ( A T y ∗ ) j − c j ] = 0 , ∀ j x_j^* \left[(\mathbf{A}^T \mathbf{y}^*)_j - c_j\right] = 0, \quad \forall j x j ∗ [ ( A T y ∗ ) j − c j ] = 0 , ∀ j y i ∗ [ b i − ( A x ∗ ) i ] = 0 , ∀ i y_i^* \left[b_i - (\mathbf{A} \mathbf{x}^*)_i\right] = 0, \quad \forall i y i ∗ [ b i − ( A x ∗ ) i ] = 0 , ∀ i (If a primal constraint is non-binding with positive slack, the corresponding dual variable is zero; if a dual variable is strictly positive, the corresponding primal constraint is strictly binding).
4. The Transportation Problem
The Transportation Problem is a special class of LPP where a homogeneous commodity is transported from m m m sources ( a i a_i a i capacity) to n n n destinations ( b j b_j b j requirement) at unit cost c i j c_{ij} c ij . Minimize Z = ∑ i = 1 m ∑ j = 1 n c i j x i j subject to ∑ j = 1 n x i j = a i , ∑ i = 1 m x i j = b j \text{Minimize } Z = \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij} \quad \text{subject to } \sum_{j=1}^n x_{ij} = a_i, \quad \sum_{i=1}^m x_{ij} = b_j Minimize Z = i = 1 ∑ m j = 1 ∑ n c ij x ij subject to j = 1 ∑ n x ij = a i , i = 1 ∑ m x ij = b j
Balanced condition: ∑ i = 1 m a i = ∑ j = 1 n b j \sum_{i=1}^m a_i = \sum_{j=1}^n b_j ∑ i = 1 m a i = ∑ j = 1 n b j .
Initial Basic Feasible Solution (IBFS) Methods
North-West Corner Method (NWCM): Allocates purely based on top-left position without regard to unit costs. Fast but yields the highest initial cost.
Least Cost Method (LCM / Matrix Minimum): Allocates iteratively to the cell with the lowest unit transportation cost c i j c_{ij} c ij .
Vogel's Approximation Method (VAM / Penalty Method):
Step 1: Compute the penalty (difference between the two lowest costs) for each row and column.
Step 2: Identify the row or column with the maximum penalty .
Step 3: Allocate the maximum possible amount min ( a i , b j ) \min(a_i, b_j) min ( a i , b j ) to the minimum cost cell in that chosen row/column.
Step 4: Adjust supply/demand and cross out satisfied rows/columns. Recompute penalties and repeat until all allocations are complete.
Result: VAM yields an initial solution very close to (or identical to) the global optimum.
Degeneracy & MODI ( u − v u-v u − v ) Optimality Method
Non-degeneracy Condition: An IBFS must have exactly m + n − 1 m + n - 1 m + n − 1 allocated cells located at independent positions (no closed loops among allocated cells).
If allocations < m + n − 1 < m + n - 1 < m + n − 1 , the problem is degenerate. Allocate an infinitesimal amount ϵ > 0 \epsilon > 0 ϵ > 0 to an unallocated cell with the lowest cost that does not form a loop. MODI (u-v) OPTIMALITY METHOD
----------------------------
ALLOCATED CELLS (Basic): UNALLOCATED CELLS (Non-basic):
- Solve: u_i + v_j = c_ij Compute: Delta_ij = c_ij - (u_i + v_j)
- (Set u_1 = 0 as reference) Optimality: All Delta_ij >= 0
Optimality Rule:
If all Δ i j = c i j − ( u i + v j ) ≥ 0 \Delta_{ij} = c_{ij} - (u_i + v_j) \ge 0 Δ ij = c ij − ( u i + v j ) ≥ 0 , the current solution is optimal .
If any Δ i j < 0 \Delta_{ij} < 0 Δ ij < 0 , the solution can be improved. Select the most negative Δ i j \Delta_{ij} Δ ij , construct a closed alternating + / − θ +/-\theta + / − θ loop with existing allocated cells, shift allocation by θ = min ( negative loop corners ) \theta = \min(\text{negative loop corners}) θ = min ( negative loop corners ) , and retest.
5. The Assignment Problem & Traveling Salesperson Problem (TSP)
The Assignment Problem assigns n n n workers to n n n jobs on a 1-to-1 basis ( x i j ∈ { 0 , 1 } x_{ij} \in \{0, 1\} x ij ∈ { 0 , 1 } ) to minimize total cost ∑ ∑ c i j x i j \sum \sum c_{ij} x_{ij} ∑∑ c ij x ij .
Hungarian Algorithm (Flood's Technique)
Row Reduction: Subtract the minimum element of each row from all elements in that row.
Column Reduction: In the resulting matrix, subtract the minimum element of each column from all elements in that column.
Zero Covering: Draw the minimum number of horizontal and vertical lines L L L to cover all zeros in the reduced matrix:
If L = n L = n L = n (matrix size), an optimal assignment is possible. Proceed to step 5.
If L < n L < n L < n , proceed to step 4.
Matrix Modification:
Find the smallest uncovered element, denoted as k k k .
Subtract k k k from all uncovered elements.
Add k k k to elements at the intersection of two covering lines.
Leave elements covered by a single line unchanged .
Return to step 3.
Optimal Assignment: Assign zeros uniquely such that exactly one zero is selected per row and per column.
Traveling Salesperson Problem (TSP)
A salesperson must visit n n n cities and return to the starting city such that each city is visited exactly once and total tour distance is minimized. Formulated as an assignment problem with c i i = ∞ c_{ii} = \infty c ii = ∞ plus sub-tour elimination constraints .