Maximization Case: Assignment Problem (Operations Research)

In Operations Research, the standard Hungarian Method is designed to minimize costs. To use it for maximization (e.g., maximizing profit, sales, or efficiency), we must first convert the problem into a minimization problem by creating a Regret Matrix.

The Problem Scenario

Imagine a company has 4 Salesmen (A, B, C, D) and 4 Territories (1, 2, 3, 4). The matrix below shows the estimated Profit ($) each salesman can generate in each territory.

Objective: Assign one salesman to one territory to maximize total profit.

Initial Profit Matrix (Input)

	Territory 1	Territory 2	Territory 3	Territory 4
Salesman A	16	10	14	11
Salesman B	14	11	15	15
Salesman C	15	15	13	12
Salesman D	13	12	14	15

---

Step 1: Convert to Minimization (Regret Matrix)

We turn "Profit" into "Opportunity Loss" to use the Hungarian Method.

1. Identify the Maximum Value: The highest value in the entire matrix is 16.
2. Subtract All Elements: Subtract every number in the matrix from 16.
   • Formula: New Value = Maximum Value - Current Value

Logic: The "best" profit (16) becomes 0 cost. A lower profit (10) becomes a high cost (6). Now, minimizing "cost" actually maximizes profit.

Resulting Regret Matrix

	T1	T2	T3	T4
A	0 (16-16)	6 (16-10)	2 (16-14)	5 (16-11)
B	2 (16-14)	5 (16-11)	1 (16-15)	1 (16-15)
C	1 (16-15)	1 (16-15)	3 (16-13)	4 (16-12)
D	3 (16-13)	4 (16-12)	2 (16-14)	1 (16-15)

---

Step 2: Row Reduction

Find the smallest number in each row and subtract it from every number in that row. (Row mins: A=0, B=1, C=1, D=1)

	T1	T2	T3	T4
A	0	6	2	5
B	1	4	0	0
C	0	0	2	3
D	2	3	1	0

---

Step 3: Column Reduction

Find the smallest number in each column and subtract it from every number in that column. (Col mins: All are 0, so the matrix remains unchanged in this example).

---

Step 4: Optimality Test

Draw the minimum number of lines needed to cover all zeros.

1. Line through Row B (covers two 0s).
2. Line through Row C (covers two 0s).
3. Line through Column T4 (covers remaining 0 in Row D).
4. Line through Column T1 (covers remaining 0 in Row A).

Result: Number of lines (4) = Matrix Size (4). The solution is Optimal.

---

Step 5: Make the Assignments

Select zeros such that there is only one per Row and one per Column.

1. Row A: Assign (A, T1). Cross out other zeros in T1.
2. Row C: Assign (C, T2). (Cannot use T1 as it is taken).
3. Row D: Assign (D, T4). Cross out other zeros in T4.
4. Row B: Assign (B, T3). (Cannot use T4 as it is taken).

---

Step 6: Final Calculation

Map assignments back to the Original Profit Matrix.

Salesman	Assigned Territory	Original Profit ($)
A	Territory 1	16
C	Territory 2	15
B	Territory 3	15
D	Territory 4	15
TOTAL		$61

Conclusion: The maximum possible profit is $61.

---

Run Locally

Prerequisites: Node.js

1. Install dependencies: npm install
2. Set the GEMINI_API_KEY in .env.local to your Gemini API key
3. Run the app: npm run dev

---