-
Notifications
You must be signed in to change notification settings - Fork 0
/
column_minima.py
125 lines (96 loc) · 4.29 KB
/
column_minima.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
import numpy as np
from transportation import Transportation
class ColumnMinima:
"""
Column minima method Steps (Rule)
Step-1: In this method, we allocate as much as possible in the lowest cost cell of the first Column, i.e. allocate min(si,dj).
Step-2:
a. Subtract this min value from supply si and demand dj.
b. If the supply si is 0, then cross (strike) that row and If the demand dj is 0 then cross (strike) that column.
c. If min unit cost cell is not unique, then select the cell where maximum allocation can be possible
Step-3: Repeact this process for all uncrossed (unstriked) rows and columns until all supply and demand values are 0.
Source: https://cbom.atozmath.com/example/CBOM/Transportation.aspx?he=e&q=cm
"""
def __init__(self, trans):
self.trans = trans
self.table = trans.table.copy()
self.alloc = []
def allocate(self, x, y):
mins = min([self.table[x, -1], self.table[-1, y]])
self.alloc.append([self.table[x, 0], self.table[0, y], mins])
if self.table[x, -1] < self.table[-1, y]:
#delete row and supply x then change value of demand y
self.table = np.delete(self.table, x, 0)
self.table[-1, y] -= mins
elif self.table[x, -1] > self.table[-1, y]:
#delete column and demand y then change value of supply x
self.table = np.delete(self.table, y, 1)
self.table[x, -1] -= mins
else:
#delete row and supply x, column and demand y
self.table = np.delete(self.table, x, 0)
self.table = np.delete(self.table, y, 1)
def solve(self, show_iter=False):
while self.table.shape != (2, 2):
cost = self.table[1:-1, 1:-1]
supply = self.table[1:-1, -1]
demand = self.table[-1, 1:-1]
#select first column
y = 0
mins = np.where(cost[:, y] == min(cost[:, y]))[0]
max_alloc = []
for x in mins:
max_alloc.append(min([supply[x], demand[y]]))
x = mins[np.argmax(max_alloc)]
#allocated row x to column y or vice versa
self.allocate(x + 1, y + 1)
#print table
if show_iter:
self.trans.print_frame(self.table)
return np.array(self.alloc, dtype=object)
if __name__ == "__main__":
#example 1 balance problem
cost = np.array([[19, 30, 50, 10],
[70, 30, 40, 60],
[40, 8, 70, 20]])
supply = np.array([7, 9, 18])
demand = np.array([5, 8, 7, 14])
#example 2 unbalance problem
cost = np.array([[ 4, 8, 8],
[16, 24, 16],
[ 8, 16, 24]])
supply = np.array([76, 82, 77])
demand = np.array([72, 102, 41])
#initialize transportation problem
trans = Transportation(cost, supply, demand)
#setup transportation table.
#minimize=True for minimization problem, change to False for maximization, default=True.
#ignore this if problem is minimization and already balance
trans.setup_table(minimize=True)
#initialize column minima method with table that has been prepared before.
CM = ColumnMinima(trans)
#solve problem and return allocation lists which consist n of (Ri, Cj, v)
#Ri and Cj is table index where cost is allocated and v it's allocated value.
#(R0, C1, 3) means 3 cost is allocated at Row 0 and Column 1.
#show_iter=True will showing table changes per iteration, default=False.
allocation = CM.solve(show_iter=False)
#print out allocation table in the form of pandas DataFrame.
#(doesn't work well if problem has large dimension).
trans.print_table(allocation)
#Result from example problem above
'''
example 1 balance problem
C0 C1 C2 C3 Supply
R0 19(5) 30 50 10(2) 7
R1 70 30 40(7) 60(2) 9
R2 40 8(8) 70 20(10) 18
Demand 5 8 7 14 34
TOTAL COST: 779
example 2 unbalance problem
C0 C1 C2 Dummy Supply
R0 4(72) 8(4) 8 0 76
R1 16 24(21) 16(41) 0(20) 82
R2 8 16(77) 24 0 77
Demand 72 102 41 20 235
TOTAL COST: 2712
'''