O objetivo é minimizar o custo para transportar as mercadorias das fontes de origem para os diversos destinos (portos).
$\\$
| Porto X | Porto Y | Porto Z | Soma | |
|---|---|---|---|---|
| Fonte A | 105 | |||
| Fonte B | 170 | |||
| Fonte C | 130 | |||
| Soma | 155 | 120 | 130 | 405 |
$\\$
| X | Y | Z | |
|---|---|---|---|
| A | 7 | 12 | 14 |
| B | 12 | 10 | 13 |
| C | 7 | 9 | 11 |
Z = ( 7x[0, 0] + 12x[0, 1] + 14x[0, 2] + 12x[1, 0] + 10x[1, 1] + 13x[1, 2] + 7x[2, 0] + 9x[2, 1] + 11*x[2, 2] )
capacidade:
$ x[0, 0] + x[0, 1] + x[0, 2] = 105\\ x[1, 0] + x[1, 1] + x[1, 2] = 170\\ x[2, 0] + x[2, 1] + x[2, 2] = 130\\ $
absorção:
$ x[0, 0] + x[1, 0] + x[2, 0] = 155\\ x[0, 1] + x[1, 1] + x[2, 1] = 120\\ x[0, 2] + x[1, 2] + x[2, 2] = 130\\ $
In [1]:
from collections import OrderedDict
from IPython.display import display
import pandas as pd
import numpy as np
import io
In [2]:
def Z(x):
_x = x.copy().fillna(0).as_matrix()
return (
7*_x[0, 0] + 12*_x[0, 1] + 14*_x[0, 2] +
12*_x[1, 0] + 10*_x[1, 1] + 13*_x[1, 2] +
7*_x[2, 0] + 9*_x[2, 1] + 11*_x[2, 2]
)
In [3]:
def calc_n_used_cells(df: pd.DataFrame, verbose=False) -> int:
"""
"""
n, m = df.shape
cells = df.values.reshape(1, n*m)
return cells[cells>0].shape[0]
def fix_table(df: pd.DataFrame, verbose=False) -> pd.DataFrame:
"""
"""
n, m = df.shape
n_used_cells = calc_n_used_cells(df)
r = n_used_cells - (n+m-1)
_used = []
if n <=2:
return df
if r < 0:
for i in range(n):
_line = df.iloc[i, :]
_l_cell_filled = _line[_line.notnull()].shape[0]
if not _l_cell_filled == 1:
continue
for j in range(m):
# just basic variable
if np.isnan(df.iloc[i, j]):
continue
_col = df.iloc[:, j]
_c_cell_filled = _col[_col.notnull()].shape[0]
if _c_cell_filled == 1:
for ii in range(n):
_id_ii = '%s,%s' % (ii, j)
if _id_ii in _used:
continue
if np.isnan(df.iloc[ii, j]):
df.iloc[ii, j] = 10**-10
_used.append(_id_ii)
r += 1
if r >= 0:
break
if r >= 0:
break
return df
In [4]:
def calc_basic_variables(df, df_cost, verbose=False):
basic_variables = OrderedDict()
n, m = df.shape
# c_ij
for i in range(n):
for j in range(m):
_id = 'c_%s,%s' % (i, j)
if not np.isnan(df.iloc[i, j]):
basic_variables[_id] = df_cost.iloc[i, j]
return basic_variables
In [5]:
def calc_multipliers(df, basic_variables, verbose=False):
multipliers = OrderedDict()
n, m = df.shape
# u_i, v_j
for i in range(n):
for j in range(m):
_id_u = 'u_%s' % i
_id_v = 'v_%s' % j
_id_c = 'c_%s,%s' % (i, j)
if not _id_c in basic_variables:
continue
if i == 0 and j == 0:
multipliers[_id_u] = 0
if ((
not _id_u in multipliers and
not _id_v in multipliers
) or (
_id_u in multipliers and
_id_v in multipliers
)):
continue
if not _id_u in multipliers:
multipliers[_id_u] = (
basic_variables[_id_c] - multipliers[_id_v]
)
else:
multipliers[_id_v] = (
basic_variables[_id_c] - multipliers[_id_u]
)
return multipliers
In [6]:
def calc_no_basic_variables(
df_cost, basic_variables, multipliers, verbose=False
):
no_basic_variables = OrderedDict()
optimo = True
n, m = df_cost.shape
# P_{ij}
for i in range(n):
for j in range(m):
_id_u = 'u_%s' % i
_id_v = 'v_%s' % j
_id_c = 'c_%s,%s' % (i, j) # cost
_id_p = 'p_%s,%s' % (i, j) # quantity
if _id_c in basic_variables:
continue
no_basic_variables[_id_p] = (
df_cost.iloc[i, j] -
multipliers[_id_u] -
multipliers[_id_v]
)
optimo = (
optimo and no_basic_variables[_id_p] >= 0
)
return optimo, no_basic_variables
In [7]:
def get_minor_no_basic(no_basic_variables, verbose=False):
φ_id = None
for k, v in no_basic_variables.items():
if φ_id is None:
φ_id = k
continue
if v < no_basic_variables[φ_id]:
φ_id = k
return φ_id
In [8]:
def get_candidate_nodes(df, ii, jj, verbose=False):
n, m = df.shape
_c_used = {}
for i in range(n):
if i == ii:
continue
if not np.isnan(df.iloc[i, jj]):
_c_used['%s,%s' % (i, jj)] = True
_r_used = {}
for j in range(m):
if j == jj:
continue
if not np.isnan(df.iloc[ii, j]):
_r_used['%s,%s' % (ii, j)] = True
return _r_used, _c_used
In [9]:
def rearange_table(df, _r_used, _c_used, ii, jj, verbose=False):
_used = []
df2 = df.copy()
run = True
for kc in _c_used:
ic, jc = map(int, kc.split(','))
for kr in _r_used:
ir, jr = map(int, kr.split(','))
if verbose:
print(ic, jr, df.iloc[ic, jr])
if not np.isnan(df.iloc[ic, jr]):
_used.append((
(ic, jr, +1, df.iloc[ic, jr]),
(ic, jc, -1, df.iloc[ic, jc]),
(ir, jr, -1, df.iloc[ir, jr]),
))
φ, φ_id = (
(df.iloc[ic, jc], (ic, jc))
if df.iloc[ic, jc] < df.iloc[ir, jr] else
(df.iloc[ir, jr], (ir, jr))
)
for ki, kj, s, v in _used[0]:
print(ki, kj, s)
df2.iloc[ki, kj] = v + (φ*s)
df2.iloc[ii, jj] = φ
df2.iloc[φ_id[0], φ_id[1]] = np.nan
run = False
break
if not run:
break
if verbose:
print('\nφ = ', φ, '\n')
print('\nSelected:', _used, φ)
display(df2)
return df2
In [10]:
# cost matrix
values_text = '''
0,1,2
0,7,12,14
1,12,10,13
2,7,9,11
'''
df_cost = pd.read_csv(io.StringIO(values_text))
print('COSTS')
df_cost
Out[10]:
In [11]:
# restriction
capacity = [105, 170, 130]
absortion = [155, 120, 130]
In [12]:
# initial basic solution with northwest corner
values_text = '''
0,1,2
0,,,
1,,,
2,,,
'''
df_initial = pd.read_csv(io.StringIO(values_text))
_capacity = list(capacity)
_absortion = list(absortion)
# iter by row
print(
'#ID'.ljust(5, ' '),
'CAPACITY'.ljust(15, ' '),
'ABSORTION'.ljust(15, ' ')
)
ii = 1
print(
('#%s' % ii).ljust(5, ' '),
str(capacity).ljust(15, ' '),
str(absortion).ljust(15, ' ')
)
i = 0
while i < df_initial.shape[0]:
# iter by column
j = 0
while j < df_initial.shape[1]:
ii += 1
r = _capacity[i] - _absortion[j]
if r > 0:
df_initial.iloc[i, j] = _absortion[j]
_absortion[j] = 0
_capacity[i] = r
elif r < 0:
df_initial.iloc[i+0, j] = _capacity[i]
_capacity[i] = 0
_absortion[j] = abs(r)
else:
df_initial.iloc[i+0, j] = _capacity[i]
_capacity[i] = 0
_absortion[j] = 0
print(
('#%s' % ii).ljust(5, ' '),
str(_capacity).ljust(15, ' '),
str(_absortion).ljust(15, ' ')
)
if _capacity[i] == 0:
break
j += 1
i += 1
df_initial = df_initial.replace(0, np.nan)
df_initial
Out[12]:
In [13]:
df = df_initial.copy()
# calculate the cost
z = Z(df)
zs = [z]
# check the result
assert z == 105*7+ 50*12 + 120*10 + 130*11
print('Z =', z)
# check
print('\ninitial table')
df = df_initial.copy()
display(df)
it_n = 0
optimo = False
while not optimo:
it_n += 1
print('\n' + '#'*80)
print('# Iteraction #:', it_n)
print('#'*80 + '\n')
df = fix_table(df)
# df.iloc[1, 2] = 10**-10
print('>>', 'table fixed')
display(df)
n, m = df.shape
'''
## Calculation of multipliers
### basic variables
$u_i + v_j = c_{ij}$
where
$u_0 = 0$
'''
basic_variables = calc_basic_variables(df, df_cost, verbose=True)
multipliers = calc_multipliers(df, basic_variables, verbose=True)
'''
### No basic variable
$P_{ij} = c_{ij} - u_i - v_j$
'''
try:
optimo, no_basic_variables = calc_no_basic_variables(
df_cost, basic_variables, multipliers, verbose=True
)
except:
break
if optimo:
break
φ_id = get_minor_no_basic(no_basic_variables, verbose=True)
ii, jj = map(int, φ_id.split('_')[1].split(','))
print('>>', 'ii', 'jj')
print(ii, jj)
_r_used, _c_used = get_candidate_nodes(df, ii, jj, verbose=True)
print('>>', '_c_used', '_r_used')
print(_c_used)
print(_r_used)
df = rearange_table(df, _r_used, _c_used, ii, jj, verbose=True)
zs.append(Z(df))
print('\n\n' + '#'*80)
print('# RESULTS')
print('#'*80)
for i, v in enumerate(zs):
print('>> %s:' % i, v)
print('\n>> final answer:')
display(df.fillna(''))