Transportation Simplex

Question 1

Simplex

Answer 1

Slack variables start as basic variables

Constraints should be <=
Objective should be Max (if Min just negate)

Top row is the objective function ( Z-objective=0)
Not optimized until there are negative coefficients
left column are the basic variables
The basic variable should have their column as an identity (1 in the row they are placed, 0 everywhere else)
RHS is the value of the basic variables

Entering variable most negative, Leaving variable Min Ratio Test (positive RHS, divide by coef, take min -> first to reach feasible region boundary)

Question 2

Nonbasic/basic variables

Answer 2

Nonbasic = forced to 0
basic = can be anything above or equal to 0

Question 3

number of basic variables

Answer 3

There will be m+n constraints
m demands and n supplies

For which we have m+n-1 basic variables

Question 4

ui / vj

Answer 4

ui dual variable corresponding to the supply constraints

vj dual variable corresponding to the demand constraints

Question 5

Initial Basic Feasible Solution: Northwest Corner Rule

Answer 5

Start at the cell which is in the upper left corner.

Write assigned supply in the cells; draw a path

Assign the most supply you can to this cell
if demand satisfied and there is still supply go to the next cell in the row (can delete previous column) and try to also give it as much supply.
if supply runs out but still demand delete row and go one cell down.
If supply and demand runs out at the same time, go one cell down and give 0 (degenerate)

You’re done when all supply and demand has been given

This method doesn’t pay attention to cost

Question 6

Setting up transportation table

Answer 6

Rows are souces/supplies
Columns are destinations/demands

RHS you see the supply available for each source
bottom row see overall demand of destination
Table coefficients are the costs

next to supply column have a column ui (dual variable supply constraint)
under the demand row have a row vj (dual variable demand constraint)

Question 7

Steps transportation simplex

Answer 7

1. Northwest Corner Rule: Initial Basic Feasible Solution

2. Fill the values of the nonbasic variables + entering variable

Question 8

Fill the values of the nonbasic variables + entering variable

Answer 8

After doing the Northwest Corner Rule
We have an initial BFS, but we don’t know the potential values of the nonbasic

the potential values = cij - ui - vj

we know cij but ui and vj are unknown.
Set one row to have ui = 0 (choose the one with the most basic variables)
then we can solve the vj for the basic variables of that row
then can solve the next ui and we repeat the process until finding all ui and vj

This way we can compute the values of all non basic. The entering variable is the one with the most negative value.

Question 9

Leaving variable

Answer 9

From the entering variable we do a chain reaction (represents how the change spreads, what we add and remove.)
Start your path from the entering variable with + coefficient, every time you meet a basic variable need to alternate +/- and turn. Once the path join back the staring point: cycle.
Look at the variables with a - sign, take the min value (not its cost but the flow assign), can break ties. The entering variable takes the value of the leaving (then deduct or add this value to the rest of the chain). If 0 degenerate.
Update weights
continue until there are no more - and thus no entering variable.