Transportation Simplex Method with Python
Algorithm
Transportation simplex method can be described in four steps.
-
Find an initial basic feasible solution with one of the methods, for example with northwest corner rule.
-
For all basic variables use u₁ = 0 and uᵢ + vⱼ = cᵢⱼ to calculate uᵢ and vⱼ. For all non-basic variables calculate wᵢⱼ = uᵢ + vⱼ -ciⱼ. If wᵢⱼ ≤ 0, the current basic feasible solution is optimal. Otherwise, choose the variable with the most positive wᵢⱼ as the entering variable.
-
Obtain a new basic feasible solution using loop pivoting, and go to step 3.
We already covered the first and second steps in the previous articles, and now we will look at how to implement steps 3 and 4.
Select Entering Variable
After we had received an initial basic feasible solution, we can calculate each uᵢ and vⱼ by going through each cell containing a basic variable.
Next, we calculate wᵢⱼ for all non-basic variables. Since there are some wᵢⱼ that are more than zero, it means we have not reached an optimal solution. Therefore we select a variable that will enter the next basic feasible solution.
With an understanding of how to select a variable that will enter the basic feasible solution, we can write a code for this. First, let’s create the function that will calculate uᵢ and *vⱼ *for each cell with a basic variable. It receives two parameters — basic feasible solution and costs, go over each basic variable and fill lists containing uᵢ and vⱼ.
Then we write a function that receives basic variables, costs, us, vs and returns list with wᵢⱼ. It calculates wᵢⱼ for each non-basic variable using a simple formula(wᵢⱼ = uᵢ + vⱼ -ciⱼ), *wᵢⱼ *represented as a tuple containing its position and value.
If this is some wᵢⱼ that more than zero, it means the solution can be improved.
If a solution can be improved, we select a variable to enter by finding *wᵢⱼ *with the largest value and return its position.
Loop Pivoting
Loop is an ordered sequence of at least four different cells that satisfy all three conditions:
-
Any two consecutive cells lie in either the same row or same column.
-
No three or more consecutive cells lie in the same row or column.
-
The last cell is in the same row or column as the first cell.
We are using loop pivoting to improve the basic feasible solution, and its process can be described in four steps.
-
Find the only loop involving the entering variable and some of the basic feasible variables.
-
Count the cells in the loop (starting from 0), label them as odd cells or even cells.
-
Find the odd cell with the smallest value. Call this value θ. This cell corresponds to the leaving variable.
-
Decrease each odd cell in the loop by θ and increase each even cell in the loop by θ.
We already knew the position of the entering variable and can find the only possible loop. At the start, we move up from the entering variable(here we choose direction randomly) then we go right to the last basic variable in the row since we can’t have three consecutive cells in the row and then one cell down.
Then we mark loop cells as even and odd.
After that, we find an odd cell with the smallest value.
Then we go over each cell in the loop and add θ to the value if the cell is even and subtract if odd.
At the end of the pivoting operation, we have a new basic feasible solution.
Now, let’s code the pivoting part. First, we write a function that returns possible next nodes for a given loop. It is pretty straightforward.
| def get_possible_next_nodes(loop, not_visited): | |
| last_node = loop[-1] | |
| nodes_in_row = [n for n in not_visited if n[0] == last_node[0]] | |
| nodes_in_column = [n for n in not_visited if n[1] == last_node[1]] | |
| if len(loop) < 2: | |
| return nodes_in_row + nodes_in_column | |
| else: | |
| prev_node = loop[-2] | |
| row_move = prev_node[0] == last_node[0] | |
| if row_move: return nodes_in_column | |
| return nodes_in_row |
Then we need a function that returns loop for a given list with basic variables positions and position of entering variable. We are using recursion in this function. If a loop can be closed we pass to the get_possible_next_nodes position of the entering variable only. If the loop can’t be closed, we recursively go over each possible next node.
The function that makes pivoting operation receives a previous basic feasible solution and loop. First, we gather even and odd cells, then take the leaving variable and return new basic variables.
Final Algorithm
Now we can put everything together.
To calculate the total sum we need to go over each cost, take the number of units from the solution, multiply the cost of transportation and number of units that will be shipped and add it to the total cost.