network simplex

Question 1

leaving variable definiton

Answer 1

the 1st to reach its upperbound (uij) or lowerbound (0)
when xij=uij (variable has an arc capacity and the flow theta we can add is at the bound of the capacity) then it is replaced by xij=uij-yij(see impact on RHS). yij is the flow in the opposite direction which is at most = uij if becomes basic (reduce flow). Thus the arc ij changes changes direction and the cost c becomes -c as reducing flow reduce cost.
The supply and demand of the nodes the arc connect need to be adapted, flow is removed where the reversed arc lands and added where it originates. The flow of these nodes need to be adapted accordingly !
When the simplex is done the arc must be reversed with their max flow and the supply/demand/flow put back.

Question 2

selecting entering variable

Answer 2

consider every nonbasic arc.

Try to add a flow theta to it then spread it in a cycle:
Have a positive theta for the arcs that go in the same direction as the one you consider becoming basic and a negative theta for the others (as if a node sends more flow somewhere it needs to reduce the flow it was sending elsewhere).

compute the Z with this flow: theta times the cost of an arc, sum for each arc in cycle (cost negative if reversed arc).

The arc that leads to the most negative Z (as this is a minimization problem) is the entering variable.

Question 3

selecting leaving variable

Answer 3

Look at the list of the arc capacities and lower bounds by including the - and + theta that the entering variables create. Check by increasing theta which constraint is met first. - theta check lower bound, + theta upperbound.
If the bound met is the capacity of the arc entering then reverse it (and it becomes nonbasic)! This means putting opposite cost and replacing xij by uij - yij (this deducts the capacity from the supply and add it to the demand)

Question 4

optimality test

Answer 4

if no candidate entering varibale leads to a negative Z then we reached optimality

Question 5

initial BF

Answer 5

a spanning tree is given, these are the basic arcs. If there is a reverse arc given, put opposite cost(removing flow cost less), compute the new demand and supply of the concerned node (replace xij by uij-yij(cost-y, y is flow below capacity) and see new RHS. Usually supply will be deducted the arc capacity and demand will be added the capacity). Put all the nonbasic arcs to 0 and compute the flow the basic arcs accordingly.

Question 6

basic variables

Answer 6

there is one redundant constrains so there are n-1 basic variables
BFS will correspond to feasible spanning trees.

Question 7

Flow graph to LP program

Answer 7

xij : arc from i to j
cij: cost from i to j

min cij xij
st (no cost coefficients in constraint because it only checks the amount)
sum xij (go out) for i supply difference xji (go in)= [supply]
sum xij (go in) for j transhipment difference xji (go out) = 0
sum xij (go out)for i demand difference xji (go in) = [demand]
-> - xij if edge out, -+ if edge in

xij>=0

if xij reaches capacity uij then xij should be replaced in the objective function and all constraints by : uij - yij -> this makes the flows and demands update
yij >= 0

upper bounds are not explicitly written as constraints and hold thanks to this

Question 8

Once the simplex is done

Answer 8

if all Z are positive it is done

flip back the reversed arcs, replace the capacities and supply/demands to their original values