Optimizing Photoshoot Timelines with MODI

The Theory Behind MODI: Duality and Opportunity Costs

Before diving into the mechanics, it's useful to understand what MODI accomplishes. Given your background in Operations Research, you'll recognize that the transportation problem is a special type of linear program. The MODI method is an efficient, specialized algorithm for solving this LP. It works by calculating the dual variables (also called shadow prices or potentials) associated with the supply and demand constraints.

In essence, MODI evaluates the "opportunity cost" for each empty cell in our allocation table. It asks: "For every unit of time we could shift into this currently unused outfit-pose combination, what would be the net change in total cost?" If this change is negative (i.e., a cost saving), our current solution is not optimal, and MODI shows us exactly how to improve it.

Step 1: Start with an Initial Basic Feasible Solution (IBFS)

To demonstrate the improvement process, we will start with the initial solution generated by the North-West Corner (NWC) rule from our previous lesson. While we know the VAM solution was better, the NWC solution is more likely to be sub-optimal, giving us a clear path for improvement.

Here is our starting point:

• Cost Matrix (Regret Cost):
  | | Combo A | Combo B | Combo C | Combo D |
  | :--- | :---: | :---: | :---: | :---: |
  | Morning | 1 | 3 | 4 | 6 |
  | Afternoon| 2 | 0 | 5 | 2 |

• NWC Allocation Plan & Total Cost:
  | | Combo A | Combo B | Combo C | Combo D | Supply |
  | :--- | :---: | :---: | :---: | :---: | :---: |
  | Morning | 80 | 40 | | | 120 |
  | Afternoon| | 60 | 50| 70| 180 |
  | Demand | 80 | 100| 50 | 70 | 300 |

The initial total regret cost is 590. Before we begin, we check for non-degeneracy: the number of allocated cells must equal $m+n-1$, where $m$ is the number of rows and $n$ is the number of columns. Here, we have 5 allocated cells, and $2+4-1=5$. The condition holds.

Step 2: The MODI (UV) Method - Iteration 1

The MODI method follows a clear, iterative process. A great way to learn it is to see it in action.

Let's apply this process to our photoshoot problem.

A. Calculate Dual Potentials ($u_i,v_j$)

We introduce a potential $u_i$ for each row and $v_j$ for each column. For every occupied cell, they must satisfy the equation: $u_i+v_j=c_{ij}$.

1. By convention, we set $u_1=0$ (for the Morning row).
2. Cell (M, A) is occupied, with $c_{11}=1$. So, $u_1+v_1=1⟹0+v_1=1⟹v_1=1$.
3. Cell (M, B) is occupied, with $c_{12}=3$. So, $u_1+v_2=3⟹0+v_2=3⟹v_2=3$.
4. Cell (A, B) is occupied, with $c_{22}=0$. So, $u_2+v_2=0⟹u_2+3=0⟹u_2=-3$.
5. Cell (A, C) is occupied, with $c_{23}=5$. So, $u_2+v_3=5⟹-3+v_3=5⟹v_3=8$.
6. Cell (A, D) is occupied, with $c_{24}=2$. So, $u_2+v_4=2⟹-3+v_4=2⟹v_4=5$.

Our calculated potentials are: $u_1=0,u_2=-3$ and $v_1=1,v_2=3,v_3=8,v_4=5$.

B. Calculate Opportunity Costs for Empty Cells

Now, for each empty cell, we calculate the opportunity cost, or improvement index (${\Delta }_{ij}$), using the formula: ${\Delta }_{ij}=u_i+v_j-c_{ij}$. A positive value indicates a potential cost saving.

• Cell (M, C): ${\Delta }_{13}=u_1+v_3-c_{13}=0+8-4=+4$.
• Cell (M, D): ${\Delta }_{14}=u_1+v_4-c_{14}=0+5-6=-1$.
• Cell (A, A): ${\Delta }_{21}=u_2+v_1-c_{21}=-3+1-2=-4$.
• Cell (C, C): This cell is not in our problem. Apologies for any confusion in the prior step's summary. Let's re-verify the empty cells: (M,C), (M,D), (A,A), (M,C) is a typo. Let's recheck the empty cells: (M,C), (M,D), (A,A) and (M,B) is occupied, (A,B) is occupied. Hmm, let me check the matrix again. Ah, NWC solution was (M,A), (M,B), (A,B), (A,C), (A,D). The empty cells are (M,C), (M,D), (A,A) and (M,A) is occupied. Oh, I see my mistake. The empty cells are (M,C), (M,D), (A,A) and... wait, a 2x4 matrix should have 8 cells. 5 are occupied. So 3 are empty. (M,C), (M,D), (A,A). My calculation list was off.
  Let's recalculate for the correct 3 empty cells.
• Cell (M, C): ${\Delta }_{13}=u_1+v_3-c_{13}=0+8-4=+4$.
• Cell (M, D): ${\Delta }_{14}=u_1+v_4-c_{14}=0+5-6=-1$.
• Cell (A, A): ${\Delta }_{21}=u_2+v_1-c_{21}=-3+1-2=-4$.

The optimality condition states that if all ${\Delta }_{ij}\le 0$, the solution is optimal. We have a positive value (${\Delta }_{13}=+4$), so our solution is not optimal. We can improve it by shifting time allocation into the (Morning, Combo C) cell.

C. Form a Closed Loop to Improve the Solution

We select the empty cell with the most positive ${\Delta }_{ij}$, which is (M, C). This is our "entering cell."

1. Draw the Loop: Starting from the entering cell (M, C), we trace a closed path of horizontal and vertical lines, where every corner of the path is an occupied cell.

   • Start at (M, C) and place a +.
   • Move horizontally to (M, B), place a -.
   • Move vertically to (A, B), place a +.
   • Move horizontally to (A, C), place a -.
   • Move vertically back to (M, C) to close the loop.

   Our loop is: (M, C) $\to$ (M, B) $\to$ (A, B) $\to$ (A, C) $\to$ (M, C).

2. Reallocate: Look at the cells in the loop with a - sign: (M, B) has 40 minutes, and (A, C) has 50 minutes. We find the minimum of these values, which is 40.

   • Subtract 40 from the quantities in the - cells.
   • Add 40 to the quantities in the + cells.

   The new allocations become:

   • (M, C): $0+40=40$
   • (M, B): $40-40=0$ (This cell becomes empty)
   • (A, B): $60+40=100$
   • (A, C): $50-40=10$

Our new allocation table (Iteration 2) is:

The new total cost is $(80\times 1)+(40\times 4)+(100\times 0)+(10\times 5)+(70\times 2)=80+160+0+50+140=430$.
Our cost has dropped from 590 to 430, a significant improvement!

Step 3: Test for Optimality - Iteration 2

Is the solution optimal now? We must repeat the process.

A. Recalculate Potentials for the New Table

Our occupied cells are now (M, A), (M, C), (A, B), (A, C), (A, D).

1. Set $u_1=0$.
2. (M, A), $c_{11}=1$: $u_1+v_1=1⟹0+v_1=1⟹v_1=1$.
3. (M, C), $c_{13}=4$: $u_1+v_3=4⟹0+v_3=4⟹v_3=4$.
4. (A, C), $c_{23}=5$: $u_2+v_3=5⟹u_2+4=5⟹u_2=1$.
5. (A, B), $c_{22}=0$: $u_2+v_2=0⟹1+v_2=0⟹v_2=-1$.
6. (A, D), $c_{24}=2$: $u_2+v_4=2⟹1+v_4=2⟹v_4=1$.

Potentials: $u_1=0,u_2=1$ and $v_1=1,v_2=-1,v_3=4,v_4=1$.

B. Recalculate Opportunity Costs for New Empty Cells

The new empty cells are (M, B), (M, D), (A, A).

• Cell (M, B): ${\Delta }_{12}=u_1+v_2-c_{12}=0+(-1)-3=-4$.
• Cell (M, D): ${\Delta }_{14}=u_1+v_4-c_{14}=0+1-6=-5$.
• Cell (A, A): ${\Delta }_{21}=u_2+v_1-c_{21}=1+1-2=0$.

All opportunity costs (${\Delta }_{ij}$) are now zero or negative. This satisfies the optimality condition. There are no empty cells that would provide a cost reduction if we were to allocate time to them.

Conclusion

We have successfully tested and improved our photoshoot time allocation plan. The final plan, with a total regret cost of 430, is now proven to be optimal.

Key Takeaways:

• MODI as an Optimality Test: The MODI method provides a definitive test to determine if an initial feasible solution from methods like NWC or VAM is optimal.
• The Role of Dual Potentials: The $u_i$ and $v_j$ values are dual variables that allow us to calculate the opportunity cost (${\Delta }_{ij}$) for each unallocated cell.
• Iterative Improvement: If any opportunity cost is positive, the solution is not optimal. MODI provides a systematic way to improve the solution by identifying an entering cell, forming a closed loop, and reallocating resources.
• Stopping Condition: The algorithm terminates when all opportunity costs (${\Delta }_{ij}$) are less than or equal to zero, guaranteeing that the current solution is the true optimum.

Interestingly, the optimal solution we reached by improving the NWC result is the exact same solution we found directly using Vogel's Approximation Method in the last lesson. This beautifully illustrates why VAM is such a powerful heuristic: it often gets you very close to, or even directly to, the optimal solution, saving significant work in the optimization phase.

In our next lesson, we will shift our focus to a different type of allocation problem. We will apply the Hungarian Method to optimally assign specific outfits to photoshoot time slots to maximize the total 'sexiness' score, tackling a pure assignment problem.