Transportation Simplex Method with Python

main

Algorithm

Transportation simplex method can be described in four steps.

  1. Balance the problem.

  2. Find an initial basic feasible solution with one of the methods, for example with northwest corner rule.

  3. 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.

  4. 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.

u₁ = 0 and uᵢ + vⱼ = cᵢⱼ
u₁ = 0 and uᵢ + vⱼ = cᵢⱼ

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.

choose the variable with the most positive wᵢⱼ as the entering variable.
choose the variable with the most positive wᵢⱼ as the entering variable.

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ⱼ.

Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.

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.

Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
view raw get_ws.ipynb hosted with ❤ by GitHub

If this is some wᵢⱼ that more than zero, it means the solution can be improved.

Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.

If a solution can be improved, we select a variable to enter by finding *wᵢⱼ *with the largest value and return its position.

Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.

Loop Pivoting

Loop is an ordered sequence of at least four different cells that satisfy all three conditions:

  1. Any two consecutive cells lie in either the same row or same column.

  2. No three or more consecutive cells lie in the same row or column.

  3. The last cell is in the same row or column as the first cell.

last two examples don’t satisfy all conditions and can’t be considered as a loop.
last two examples don’t satisfy all conditions and can’t be considered as a loop.

We are using loop pivoting to improve the basic feasible solution, and its process can be described in four steps.

  1. Find the only loop involving the entering variable and some of the basic feasible variables.

  2. Count the cells in the loop (starting from 0), label them as odd cells or even cells.

  3. Find the odd cell with the smallest value. Call this value θ. This cell corresponds to the leaving variable.

  4. 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.

draw4

Then we mark loop cells as even and odd.

draw5

After that, we find an odd cell with the smallest value.

draw6

Then we go over each cell in the loop and add θ to the value if the cell is even and subtract if odd.

draw7

At the end of the pivoting operation, we have a new basic feasible solution.

draw8

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.

Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
view raw get_loop.ipynb hosted with ❤ by GitHub

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.

Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.

Final Algorithm

Now we can put everything together.

Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.

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.

Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.