Network models cont. #

Compressor shipment example #

• note that this problem only has equality constraints, which makes it a bit easier for us to use technology

• as we can see, this is very involved when trying the simplex method with this dimension

There are other approaches to simplify the simplex tableaus (procedures), at least in obtaining a more efficient initial BFS which is somewhat close to the optimal solution. Some methods to obtain such a useful initial BFS include

• northwest corner method
• minimum matrix method
• minimum row method
• minimum column method

The idea is to start with an initial guess which is likely to reduce the procedures in applying the optimality criterion.

The northwest corner method is simple to apply but it ignores the cost structure. Other methods take a bit more time to apply, but the corresponding initial BFS is expected to be “better” (closer to optimal solution), because they take the cost structure into account by favoring the variables whose corresponding costs are smaller.

Northwest corner method #

Using the example before:

Consider the table of supply and demand constraints:

We want to put value for each cell so that the supply and demand is satisfied (recall that the supply amount = demand amount, because this is a “balanced” problem).

We start with the top left (the “northwest”) cell. Try to find the max that we can place in each cell.

Now this row is finished because the supply is 0. So, we move down a row. (If we didn’t finish the row, we would move right one cell).

Now the first column is done, we move right.

After this initial BFS is obtained, we can use improvement criterion (apply optimality criteron multiple times).

When assigning values to the cells we can use the price structure by assigning to the lowest costing item first.