Optimality test

After obtaining an initial feasible solution using one of the methods such as the North West Corner method or the Least Cost method, we need to check if the solution is optimal. This involves checking whether there exists any other feasible solution that has a lower total cost.

The optimality test can be performed using various methods such as the stepping stone method, the modified distribution method, or the Vogel’s approximation method. Here, we will discuss the stepping stone method.

The stepping stone method involves calculating the opportunity cost for each empty cell in the allocation table. The opportunity cost represents the amount by which the cost of an allocated cell would have to increase or decrease to make another allocation possible in the same row or column without violating the supply or demand constraints.

The steps involved in the stepping stone method are as follows:

1. Select an empty cell (i,j) in the allocation table.
2. Starting from the cell (i,j), draw a closed loop that includes only allocated cells.
3. Count the number of cells in the loop. If the count is odd, then the opportunity cost for cell (i,j) is the smallest cost among all the cells in the loop. If the count is even, then the opportunity cost for cell (i,j) is zero.
4. Repeat steps 1-3 for all empty cells in the allocation table to obtain the opportunity cost for each cell.
5. If all the opportunity costs are non-negative, then the current solution is optimal. Otherwise, select the cell with the most negative opportunity cost and perform an improvement move.

An improvement move involves adding or subtracting the opportunity cost from each cell in the closed loop and updating the allocation table accordingly. The process is repeated until an optimal solution is obtained.

Note that there may be multiple optimal solutions with the same total cost.

Optimality test examples

Let’s continue with the example from the previous question:

We will use the stepping stone method to check whether this solution is optimal.

Step 1: Select an empty cell. Let’s select cell (1,1).

Step 2: Draw a closed loop that includes only allocated cells starting from cell (1,1) and going right, then down, then left, and finally up to cell (1,1). The closed loop is shown in red in the table below.

Step 3: Count the number of cells in the loop. The loop has four cells, which is an even number. Therefore, the opportunity cost for cell (1,1) is zero.

Step 4: Repeat steps 1-3 for all other empty cells.

For cell (1,2), the loop goes down, left, up, and right to cell (1,2), and has an odd number of cells. The smallest cost among the cells in the loop is 2, which is the opportunity cost for cell (1,2).

For cell (1,4), the loop goes down, right, up, and left to cell (1,4), and has an odd number of cells. The smallest cost among the cells in the loop is 1, which is the opportunity cost for cell (1,4).

The corrected table after the optimality test using the stepping stone method is as follows:

Since all the opportunity costs are non-negative, the current solution is optimal. Therefore, the optimal allocation is:

• Allocate 50 units from F1 to W1
• Allocate 120 units from F2 to W2
• Allocate 120 units from F1 to W3
• Allocate 60 units from F2 to W4
• Allocate 100 units from F3 to W1
• Allocate 10 units from F3 to W4
• The total cost for this allocation is $7,900.