# Функции
def PrintOut():
GetDual()
nCost = 0
print()
print('ПОТРЕБИТЕЛИ' + ' ' * (m * 9) + 'ПОСТАВЩИКИ')
for y in aDemand:
print('%10i' % y, end=' ')
print()
for x in range(n):
for y in range(m):
nCost += aCost[x][y] * aRoute[x][y]
if aRoute[x][y] == 0:
print('[<%2i>%4i]' %(aCost[x][y], aDual[x][y]), end=' ')
else:
print('[<%2i>(%2i)]' %(aCost[x][y], aRoute[x][y] + 0.5), end=' ')
print(' : %i' % aSupply[x])
print('Стоимость: ', nCost)
print('Нажмите ENTER чтобы продолжить')
input()
def NorthWest():
global aRoute
u = 0
v = 0
aS = [0] * m
aD = [0] * n
while u <= n - 1 and v <= m - 1:
if aDemand[v] - aS[v] < aSupply[u] - aD[u]:
z = aDemand[v] - aS[v]
aRoute[u][v] = z
aS[v] += z
aD[u] += z
v += 1
else:
z = aSupply[u] - aD[u]
aRoute[u][v] = z
aS[v] += z
aD[u] += z
u += 1
def NotOptimal():
global PivotN
global PivotM
nMax = -nVeryLargeNumber
GetDual()
for u in range(0, n):
for v in range(0, m):
x = aDual[u][v]
if x > nMax:
nMax = x
PivotN = u
PivotM = v
return (nMax > 0)
def GetDual():
global aDual
for u in range(0, n):
for v in range(0, m):
aDual[u][v] = -0.5 # null
if aRoute[u][v] == 0:
aPath = FindPath(u, v)
z = -1
x = 0
for w in aPath:
x += z * aCost[w[0]][w[1]]
z *= -1
aDual[u][v] = x
def FindPath(u, v):
aPath = [[u, v]]
if not LookHorizontaly(aPath, u, v, u, v):
print('Ошибка, нажмите любую клавишу...', u, v)
input()
return aPath
def LookHorizontaly(aPath, u, v, u1, v1):
for i in range(0, m):
if i != v and aRoute[u][i] != 0:
if i == v1:
aPath.append([u, i])
return True
if LookVerticaly(aPath, u, i, u1, v1):
aPath.append([u, i])
return True
return False
def LookVerticaly(aPath, u, v, u1, v1):
for i in range(0, n):
if i != u and aRoute[i][v] != 0:
if LookHorizontaly(aPath, i, v, u1, v1):
aPath.append([i, v])
return True
return False
def BetterOptimal():
global aRoute
aPath = FindPath(PivotN, PivotM)
nMin = nVeryLargeNumber
for w in range(1, len(aPath), 2):
t = aRoute[aPath[w][0]][aPath[w][1]]
if t < nMin:
nMin = t
for w in range(1 , len( aPath), 2):
aRoute[aPath[w][0]][aPath[w][1]] -= nMin
aRoute[aPath[w - 1][0]][aPath[w - 1][1]] += nMin
# Точка входа
aCost = [[20, 47, 30, 14]
,[47, 28, 17, 46]
,[34, 46, 15, 29]]
aDemand = [43, 42, 50, 18]
aSupply = [22, 58, 78]
n = len(aSupply)
m = len(aDemand)
nVeryLargeNumber = 99999999999
aRoute = []
for x in range(n):
aRoute.append([0] * m)
aDual = []
for x in range(n):
aDual.append([-1] * m)
NorthWest()
PivotN = -1
PivotM = -1
PrintOut()
# MAIN
while NotOptimal():
print('НОВАЯ БАЗИСНАЯ ТОЧКА: ', aDual[PivotN][PivotM])
print('СТРОКА: ', PivotN + 1)
print('СТОЛБЕЦ: ', PivotM + 1)
BetterOptimal()
PrintOut()
print("ЗАВЕРШЕНО!")