#input parameters
Transportation_Cost = #transportationcost#;
Supply = #supply#;
Demand = #demand#;
import math
import numpy as np
from collections import Counter
if (sum(vl for vl in Supply) != sum(vl for vl in Demand)):
show('This Problem is unbalanced.')
assert()
class transportationproblem:
def __init__(self , cost_coeff , supply , demand):
#assign basic variables
self.cost_coeff = cost_coeff;
self.supply = supply;
self.demand = demand;
#assign factory and centre names
factorylist = [];
for i in range(len(supply)):
factorylist += ["F_"+str(i+1)];
centrelist = [];
for i in range(len(demand)):
centrelist += ["C_"+str(i+1)];
self.factory = factorylist;
self.centre = centrelist;
#initialize BFS
self.BFS = [[0]*len(demand) for i in range(len(supply))];
#initialize basic_variables table
self.BV = [[False]*len(demand) for i in range(len(supply))];
#end of constructor
#set IBFS using North-west Corner Method
def set_IBFS_northwest(self):
#show starting statement
show(html('
Determine starting solution (IBFS) using Northwest corner Method
'))
#define the lists supply_remain and demand_remain
supply_remain = list(self.supply);
demand_remain = list(self.demand);
counter = len(self.supply) + len(self.demand) - 1;
#initialize current position
curr_i = 0;
curr_j = 0;
show(html('First we start from the top left corner'))
while counter > 0:
#assign BFS value and deduct remain supply and demand and indicate basic_variables_location
self.BFS[curr_i][curr_j] = min(supply_remain[curr_i],demand_remain[curr_j]);
show(html('
' + str(self.BFS[curr_i][curr_j]) + ' is assigned to the cell F' + str(curr_i + 1) + 'C' + str(curr_j +1) +'
'))
supply_remain[curr_i] = supply_remain[curr_i] - self.BFS[curr_i][curr_j];
demand_remain[curr_j] = demand_remain[curr_j] - self.BFS[curr_i][curr_j];
self.BV[curr_i][curr_j] = True;
#display tableau
self.display_tab()
#move the position
moved = false;
if (supply_remain[curr_i] != 0) and moved == False:
curr_j += 1;
moved = true;
if counter > 1:
show(html('Demand of C' + str(curr_j) + ' is satisfied, move to the cell at right.'))
if (supply_remain[curr_i] == 0) and moved == False:
curr_i += 1;
moved = true;
if counter > 1:
show(html('Supply of F' + str(curr_i) + ' is full, move to the cell at bottom.'))
counter = counter - 1
if counter > 0:
show(html('___'))
show(html('
The starting solution (IBFS) is set.
'))
#set IBFS using Least Cost Method
def set_IBFS_leastcost(self):
#show starting statement
show(html('
Determine starting solution (IBFS) using Least Cost Method
'))
#define the lists supply_remain and demand_remain
supply_remain = list(self.supply);
demand_remain = list(self.demand);
supply_met = [false]*len(supply_remain);
demand_met = [false]*len(demand_remain);
counter = len(self.supply) + len(self.demand) - 1;
#find order of matrix entries
order = [];
remaining = len(self.supply) * len(self.demand);
while remaining > 0:
MIN = float('inf');
for i in range(len(self.supply)):
for j in range(len(self.demand)):
if (self.cost_coeff[i][j] < MIN) and ([i,j] not in order):
MIN = self.cost_coeff[i][j];
temp_pos = [i,j];
order += [temp_pos]
remaining = remaining - 1
#assign BFS and BV
for pos in order:
if counter <= 0:
break
if ( not supply_met[pos[0]] ) and ( not demand_met[pos[1]] ):
show(html('
The least cost is ' + str(self.cost_coeff[pos[0]][pos[1]]) + ' in cell F' + str(pos[0] + 1) + 'C' + str(pos[1] + 1) +'.
'))
self.BFS[pos[0]][pos[1]] = min(supply_remain[pos[0]] , demand_remain[pos[1]])
show(html(str(self.BFS[pos[0]][pos[1]]) + ' is assigned to this cell.'))
supply_remain[pos[0]] = supply_remain[pos[0]] - self.BFS[pos[0]][pos[1]];
demand_remain[pos[1]] = demand_remain[pos[1]] - self.BFS[pos[0]][pos[1]];
self.BV[pos[0]][pos[1]] = true;
counter = counter - 1;
#cross out row or column
if supply_remain[pos[0]] == 0:
supply_met[pos[0]] = true;
show(html('The supply of factory F' + str(pos[0] + 1) + ' is full.'))
else:
demand_met[pos[1]] = true;
show(html('The demand of centre C' + str(pos[1] + 1) + ' is satisfied.'))
#show tableau
self.display_tab_least(supply_met , demand_met)
#display last tableau
show(html('The starting basic feasible solution is set.'))
supply_met = [true]*len(supply_remain);
demand_met = [true]*len(demand_remain);
self.display_tab_least(supply_met , demand_met)
#end of IBFS_leastcost
#find position of BV of each row
def find_BVPOS(self):
self.bvpos = [[] for i in range(len(self.supply))];
for i in range(len(self.supply)):
for j in range(len(self.demand)):
if (self.BV[i][j]):
self.bvpos[i] += [j];
return self.bvpos
#end
#find UV value
def set_uv(self):
#get bvpos
self.find_BVPOS()
#initialize uv list
self.U = [0]*len(self.supply);
self.V = [0]*len(self.demand);
#initialize truth table of computed u and v
u_com = [false]*len(self.supply);
v_com = [false]*len(self.demand);
u_com[0] = true;
#initiate display html cocde
eq_code = 'Subsituting u1 = 0 . we get \\\\[ \\\\begin{alignat}{3} ';
#start to compute
counter = len(self.supply) + len(self.demand) - 1;
while counter > 0:
for i in range(len(self.supply)):
for j in range(len(self.demand)):
if j in self.bvpos[i]:
if u_com[i] and (not v_com[j]):
self.V[j] = self.cost_coeff[i][j] - self.U[i];
eq_code += '& u_{' + str(i+1) + '} + v_{' + str(j+1) + '}=' + str(self.cost_coeff[i][j]) + ' , '
eq_code += '& \\\\ \\\\ u_{' + str(i+1) + '}=' + str(self.U[i])
eq_code += ' \\\\ , \\\\ & \\\\implies \\\\ v_{' + str(j+1) +'} = ' + str(self.V[j]) + '\\\\\\\\'
counter = counter - 1;
v_com[j] = true;
if (not u_com[i]) and v_com[j]:
self.U[i] = self.cost_coeff[i][j] - self.V[j];
eq_code += '& u_{' + str(i+1) + '} + v_{' + str(j+1) + '}=' + str(self.cost_coeff[i][j]) + ' , '
eq_code += '& \\\\ \\\\ v_{' + str(j+1) + '}=' + str(self.V[j])
eq_code += ' \\\\ , \\\\ & \\\\implies \\\\ u_{' + str(i+1) +'} = ' + str(self.U[i]) + '\\\\\\\\'
counter = counter - 1;
u_com[i] =true;
eq_code = eq_code[:(len(eq_code) - 2)]
eq_code += '\\\\end{alignat} \\\\]'
show(html(eq_code))
#end of set uv
#find S matrix
def find_S(self):
self.S = [];
for i in range(len(self.supply)):
self.S += [[self.U[i] + self.V[j] - self.cost_coeff[i][j] for j in range(len(self.demand))]];
#end
#check optimality
def is_optimal(self):
self.find_S();
ans = true;
for row in self.S:
for vl in row:
if vl > 0:
ans = false;
return ans
#end
#find solution of current BFS
def solution(self):
solution = 0;
for i in range(len(self.supply)):
for j in range(len(self.demand)):
solution = solution + self.cost_coeff[i][j]*self.BFS[i][j]
return solution
#end
#pick entering position if not optimal, biggest S position if optimal
def to_enter(self):
MAX = float('-inf');
for i in range(len(self.S)):
for j in range(len(self.S[0])):
if self.S[i][j] > MAX and (not self.BV[i][j]):
MAX = self.S[i][j];
pos = [i,j];
return pos
#end
#MODI iterate
def enter(self,start):
n = len(self.supply);
m = len(self.demand);
#construct the close path
#initialize loop location
T = np.zeros((n, m))
# set basic variables location to 1 for T
for i in range(0,n):
for j in range(0,m):
if self.BV[i][j]:
T[i, j] = 1;
start = tuple(start)
T[start] = 1;
while True:
xs, ys = np.nonzero(T);
xcount, ycount = Counter(xs), Counter(ys);
for x, count in xcount.items():
if count <= 1:
T[x,:] = 0;
for y, count in ycount.items():
if count <= 1:
T[:,y] = 0;
if all(x > 1 for x in xcount.values()) and all(y > 1 for y in ycount.values()):
break
#construct path order
def dist(P,Q):
if (P[0] == Q[0] or P[1] == Q[1]) and (not(P[0] == Q[0] and P[1] == Q[1])):
return (abs(P[0]-Q[0]) + abs(P[1]-Q[1]))
else:
return np.inf
#dist = lambda (x1, y1), (x2, y2): (abs(x1-x2) + abs(y1-y2)) \\
#if ((x1==x2 or y1==y2) and not (x1==x2 and y1==y2)) else np.inf;
fringe = set(tuple(p) for p in np.argwhere(T > 0));
size = len(fringe);
path = [start];
while len(path) < size:
last = path[-1]
if last in fringe:
fringe.remove(last);
min = np.inf;
for i in range(len(list(fringe))):
if dist(last,list(fringe)[i]) < min:
nexti = i;
next = list(fringe)[nexti];
path.append(next);
#path constructed
#mark (+) and (-) for the element in path
path_neg = path[1::2];
path_pos = path[::2];
self.loop_display(path)
#find allocation value theta and leaving position
value_neg = [];
for loc in path_neg:
value_neg += [self.BFS[loc[0]][loc[1]]]
theta = math.inf;
for vl in value_neg:
if vl < theta:
theta = vl;
leaving = path_neg[value_neg.index(theta)]
#display the loop and highlight leaving position
self.display_tab_loop(path,leaving)
#show the quantity allocated and the leaving variable
show(html('\\\\begin{array}{} \\\\text{Minimum of the quantity allocated among all negative position \\\\color{brown}{(-)} is ' + str(theta) + ' ( } \\\\color{blue}{F_' + str(leaving[0] + 1) + 'C_' + str(leaving[1] + 1) + '} \\\\text{).}\\\\end{array}'))
show(html('\\\\begin{array}{} \\\\text{Subtract ' + str(theta) + ' from all \\\\color{brown}{(-)} and add it to \\\\color{brown}{(+)} .} \\\\end{array}'))
show(html('\\\\begin{array}{} \\\\text{The leaving variable is }\\\\color{blue}{F_' + str(leaving[0] + 1) + 'C_' + str(leaving[1] + 1) + '} \\\\text{.} \\\\end{array}'))
#allocate quantities to the path
for loc in path_pos:
self.BFS[loc[0]][loc[1]] = self.BFS[loc[0]][loc[1]] + theta;
for loc in path_neg:
self.BFS[loc[0]][loc[1]] = self.BFS[loc[0]][loc[1]] - theta;
#change the truth lists of Basic variables
self.BV[start[0]][start[1]] = true;
self.BV[leaving[0]][leaving[1]] = false;
#end of MODI iteration
#functions for tableau displays
#display tableau with cost coefficients and BFS
def display_tab(self):
begin_code = ' \\\\[ \\\\begin{array}';
end_code = '\\\\end{array} \\\\] '
col_code = '{ | c |';
for vl in Transportation_Cost[0]:
col_code += ' l :'
col_code += '| c |}'
#add head row
content_code = '\\\\hline & ';
for name in self.centre:
content_code += name + ' & ';
content_code += ' \\\\tt{Supply} \\\\\\\\ \\\\hline ';
for i in range(len(self.cost_coeff)):
content_code += self.factory[i] + ' & ';
for j in range(len(self.cost_coeff[0])):
content_code += ' ' + str(self.cost_coeff[i][j]) ;
if self.BV[i][j]:
content_code += ' \\\\ \\\\ \\\\textcolor{green}{(' + str(self.BFS[i][j]) +')}';
content_code += ' & '
content_code += str(self.supply[i])
content_code += '\\\\\\\\ \\\\hdashline ';
#add bottomdemand row
content_code += '\\\\hline \\\\tt{Demand} &';
for vl in self.demand:
content_code += str(vl) + ' & ';
content_code += '\\\\\\\\ \\\\hline ';
tex_code = begin_code + col_code + content_code + end_code
show(html(tex_code))
#end of display simple tableau with BFS
#display tableau with cost coefficients and BFS in least cost method
#this will only be called in function IBFS_leastcost
def display_tab_least(self , supply_met , demand_met):
begin_code = ' \\\\[ \\\\begin{array}';
end_code = '\\\\end{array} \\\\] '
col_code = '{ | c |';
for vl in Transportation_Cost[0]:
col_code += ' l :'
col_code += '| c |}'
#add head row
content_code = '\\\\hline & ';
#head row code
for name in self.centre:
content_code += name + ' & ';
content_code += ' \\\\tt{Supply} \\\\\\\\ \\\\hline ';
for i in range(len(self.cost_coeff)):
content_code += self.factory[i] + ' & ';
for j in range(len(self.cost_coeff[0])):
content_code += ' ' + str(self.cost_coeff[i][j]) ;
if self.BV[i][j]:
content_code += ' \\\\ \\\\ \\\\textcolor{green}{(' + str(self.BFS[i][j]) +')}';
content_code += ' & '
#add supply values
if supply_met[i]:
content_code += str(self.supply[i]) + '\\\\ \\\\scriptsize{\\\\color{red}{\\\\text{(satisfied)}}}';
else:
content_code += str(self.supply[i])
content_code += '\\\\\\\\ \\\\hdashline ';
#add bottomdemand row
content_code += '\\\\hline \\\\tt{Demand} &';
i = 0;
for vl in self.demand:
if demand_met[i]:
content_code += str(vl) + '\\\\ \\\\scriptsize{\\\\color{red}{\\\\text{(satisfied)}}} & ';
else:
content_code += str(vl) + ' & ';
i += 1;
content_code += '\\\\\\\\ \\\\hline ';
tex_code = begin_code + col_code + content_code + end_code
show(html(tex_code))
#end of display simple tableau with IBFS least cost
#display tableau with cost coefficients and BFS UV and S matrix
def display_tab_UVS(self):
begin_code = ' \\\\[ \\\\begin{array}';
end_code = '\\\\end{array} \\\\] '
col_code = '{ | c |';
for vl in Transportation_Cost[0]:
col_code += ' l :'
col_code += '| c : c |}'
#add head row
content_code = '\\\\hline & ';
for name in self.centre:
content_code += name + ' & ';
content_code += ' \\\\tt{Supply} & u_{i} \\\\\\\\ \\\\hline ';
for i in range(len(self.cost_coeff)):
content_code += self.factory[i] + ' & ';
for j in range(len(self.cost_coeff[0])):
content_code += ' ' + str(self.cost_coeff[i][j]) ;
if self.BV[i][j]:
content_code += ' \\\\ \\\\ \\\\textcolor{green}{(' + str(self.BFS[i][j]) +')}';
else:
if (i == self.to_enter()[0] and j == self.to_enter()[1]):
content_code += ' \\\\ \\\\ \\\\textcolor{red}{[' + str(self.S[i][j]) +']}';
else:
content_code += ' \\\\ \\\\ \\\\textcolor{orange}{[' + str(self.S[i][j]) +']}';
content_code += ' & '
content_code += str(self.supply[i]) + ' & u_{' +str(i+1) + '}=' + str(self.U[i])
content_code += '\\\\\\\\ \\\\hdashline ';
#add bottomdemand row
content_code += '\\\\hline \\\\tt{Demand} &';
for vl in self.demand:
content_code += str(vl) + ' & ';
content_code += '\\\\\\\\ \\\\hdashline ';
#add v row
content_code += 'v_{j} & ';
for j in range(len(self.V)):
content_code += 'v_{' + str(j+1) + '}=' + str(self.V[j]) + ' & '
content_code += '\\\\\\\\ \\\\hline ';
tex_code = begin_code + col_code + content_code + end_code
show(html(tex_code))
#end of full display
#display tableau with loop and highlight leaving position
#this function only called in function self.enter()
def display_tab_loop(self , path , leave):
path_neg = path[1::2];
path_pos = path[::2];
begin_code = ' \\\\[ \\\\begin{array}';
end_code = '\\\\end{array} \\\\] '
col_code = '{ | c |';
for vl in Transportation_Cost[0]:
col_code += ' l :'
col_code += '| c : c |}'
#add head row
content_code = '\\\\hline & ';
for name in self.centre:
content_code += name + ' & ';
content_code += ' \\\\tt{Supply} & u_{i} \\\\\\\\ \\\\hline ';
for i in range(len(self.cost_coeff)):
content_code += self.factory[i] + ' & ';
for j in range(len(self.cost_coeff[0])):
content_code += ' ' + str(self.cost_coeff[i][j]) ;
if self.BV[i][j]:
if (i,j) == leave:
content_code += ' \\\\ \\\\ \\\\textcolor{blue}{(' + str(self.BFS[i][j]) +')}';
else:
content_code += ' \\\\ \\\\ \\\\textcolor{green}{(' + str(self.BFS[i][j]) +')}';
else:
if (i == self.to_enter()[0] and j == self.to_enter()[1]):
content_code += ' \\\\ \\\\ \\\\textcolor{red}{[' + str(self.S[i][j]) +']}';
else:
content_code += ' \\\\ \\\\ \\\\textcolor{orange}{[' + str(self.S[i][j]) +']}';
#add plus minus sign for loop position
if (i,j) in path_neg:
content_code += ' \\\\ \\\\tt{\\\\color{brown}{(-)}}';
if (i,j) in path_pos:
content_code += ' \\\\ \\\\tt{\\\\color{brown}{(+)}}';
content_code += ' & '
content_code += str(self.supply[i]) + ' & u_{' +str(i+1) + '}=' + str(self.U[i])
content_code += '\\\\\\\\ \\\\hdashline ';
#add bottomdemand row
content_code += '\\\\hline \\\\tt{Demand} &';
for vl in self.demand:
content_code += str(vl) + ' & ';
content_code += '\\\\\\\\ \\\\hdashline ';
#add v row
content_code += 'v_{j} & ';
for j in range(len(self.V)):
content_code += 'v_{' + str(j+1) + '}=' + str(self.V[j]) + ' & '
content_code += '\\\\\\\\ \\\\hline ';
tex_code = begin_code + col_code + content_code + end_code
show(html(tex_code))
#end of MODI tableau with loop display
#display loop statements
#this function only called in function self.enter()
def loop_display(self , path):
tex_code = ' \\\[ ';
for loc in path:
tex_code += 'F_' + str(loc[0]+1) + ' C_' + str(loc[1]+1) + ' \\\\longrightarrow ';
tex_code += 'F_' + str(path[0][0]+1) + ' C_' + str(path[0][1]+1) + ' \\\\] ';
html_code1 = 'A closed loop is formed that starts and ends at the entering variable,'
html_code2 = 'and consists of vertical and horizontal segments that start and end at basic or entering variables only.'
html_code3 = 'the loop is ' + tex_code
show(html(html_code1))
show(html(html_code2))
show(html(html_code3))
show(html('\\\\[\\\\begin{array}{} \\\\text{A quantity } y \\\\text{ will be allocated to } \\\\color{red}{F_'+str(self.to_enter()[0]+1) + 'C_' + str(self.to_enter()[1]+1) + '} \\\\text{.} \\\\\\\\ \\\\text{To keep the row totals and column totals unchanged, quantities will be reduced and increased alternatively along the loop.} \\\\\\\\ \\\\text{Plus and Minus sign are marked on the loop.}\\\\end{array}\\\\]'))
P = transportationproblem(Transportation_Cost,Supply,Demand)
P.display_tab()
show(html('______'))
P.set_IBFS_northwest()
show(html('______'))
P.display_tab()
show(html('
Current total cost for this solution is ' + str(P.solution()) + '.
'))
iter = 1;
while true:
show(html('______'))
show(html('
Iteration ' + str(iter) + '
'))
show(html('
Optimality Test'))
show(html('1. Find \\\\[ u_i \\\\ and \\\\ v_j \\\\] such that \\\\[ u_i + v_j -c_{ij} =0 \\\\] for basic variables.'))
P.set_uv()
P.find_S();
show(html('
2. Find \\\\[ u_i + v_j - c_{ij} \\\\] for all the non-basic variables.'))
P.display_tab_UVS()
if P.is_optimal():
break
else:
show(html('Since there is positive values of \\\\[ u_i + v_j - c_{ij} \\\\] , the solution can be improved.'))
show(html('-------'))
show(html('Entering and Leaving'))
show(html('The entering variable is the variable with the most positive value of \\\\[ u_i + v_j - c_{ij} \\\\] , which is \\\\[ \\\\color{red}{F_' + str(P.to_enter()[0] + 1) + 'C_' + str(P.to_enter()[1] + 1) + '} \\\\] .'))
P.enter(P.to_enter())
P.display_tab()
show(html('
Current total cost for this solution is ' + str(P.solution()) + '.
'))
iter += 1;
#show solution
show(html('
All \\\\[u_i + v_j - c_{ij} \\\\leq 0\\\\] for all the non-basic variables, the optimality condition is reached.
'))
show(html('
An optimal solution is the following.
'))
P.display_tab()
show(html('
The minimum transportation cost is ' + str(P.solution()) + '.
'))