Transportation Problem: North West Corner Method

This is part of the course “Optimization for Programmers”.

Image for post
Image for post
GitHub Repository with Source Code

Introduction

In Simplex Method we were introducing slack variables to have an initial basic feasible solution, but in transportation problems, we can use one to find it:

  • North West Corner Rule
  • Row Minima Method
  • Column Minima Method
  • Least Cost Method or Matrix Minima Method
  • Vogel’s Approximation Method

North West Corner Rule

In this part, we will look at the North West Corner Rule to find an initial basic feasible solution. It has three steps:

  1. Find the north west corner cell of the transportation tableau. Allocate as much as possible to the selected cell, and adjust the associated amounts of supply and demand by subtracting the allocated amount.
  2. Cross out the row or column with 0 supply or demand. If both a row and a column have a 0, cross out randomly row or column.
  3. If one cell is left uncrossed, cross out the cell and stop. Otherwise, go to step 1.

Example

We start with an empty matrix with demands at the bottom and supplies at the right.

Image for post
Image for post

We take the north west corner cell, and its value becomes a minimum of d₁ and s. Since s₁ less than d₁, we cross out the first row.

Image for post
Image for post
first iteration

In the following iterations, we are doing the same steps.

Image for post
Image for post

We end up with such table and basic feasible solution.

Image for post
Image for post

Programming

We write a function that receives supply and demand. At the start, we copy arguments, since function update supply and demand on each iteration, then we make i and j equal to zero. On each iteration, we add one to i or j and put a new variable in the resulting list. When we crossed all rows and columns, we return basic variables in the form of a tuple containing position and value.

Next Part ->

Reach the next level of focus and productivity with increaser.org.

Image for post
Image for post
Increaser

Written by

Software engineer, creator of increaser.org. More at geekrodion.com

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store