02/01/2026 21:08 Untitled34
In [1]: import numpy as np
def simplex_max(c, A, b, eps=1e-9, max_iter=10_000):
"""
Résout: max c^T x s.c. A x <= b, x >= 0
Méthode: tableau du simplexe (slack variables).
Retour: (x_opt, z_opt)
"""
A = [Link](A, dtype=float)
b = [Link](b, dtype=float)
c = [Link](c, dtype=float)
m, n = [Link]
# Tableau: [A | I | b]
tableau = [Link]((m + 1, n + m + 1), dtype=float)
tableau[:m, :n] = A
tableau[:m, n:n+m] = [Link](m)
tableau[:m, -1] = b
# Ligne objectif: Z - c^T x = 0 => coefficients = -c
tableau[m, :n] = -c
# Base initiale = slack variables
basis = list(range(n, n + m))
def pivot(row, col):
pivot_val = tableau[row, col]
tableau[row, :] /= pivot_val
for r in range([Link][0]):
if r != row:
tableau[r, :] -= tableau[r, col] * tableau[row, :]
basis[row] = col
it = 0
while it < max_iter:
it += 1
# 1) variable entrante: coefficient le plus négatif dans la ligne Z
obj = tableau[m, :-1]
col = [Link](obj)
if obj[col] >= -eps:
break # optimal
# 2) variable sortante: ratio min b_i / a_i,col (avec a_i,col > 0)
ratios = []
for i in range(m):
a = tableau[i, col]
if a > eps:
[Link](tableau[i, -1] / a)
else:
[Link]([Link])
row = int([Link](ratios))
if ratios[row] == [Link]:
raise ValueError("Problème non borné (unbounded).")
pivot(row, col)
localhost:8888/doc/tree/[Link] 1/3
02/01/2026 21:08 Untitled34
# Extraction solution
x = [Link](n + m)
for i in range(m):
x[basis[i]] = tableau[i, -1]
x_opt = x[:n]
z_opt = tableau[m, -1]
return x_opt, z_opt
if __name__ == "__main__":
# Exemple proche du cours: max Z = 30x1 + 40x2
# s.c. 2x1 + 3x2 <= 120
# 4x1 + 1x2 <= 100
# x >= 0
c = [30, 40]
A = [
[2, 3],
[4, 1]
]
b = [120, 100]
x_opt, z_opt = simplex_max(c, A, b)
print("x_opt =", x_opt)
print("Z_opt =", z_opt)
x_opt = [18. 28.]
Z_opt = 1660.0
In [2]: from collections import deque, defaultdict
def edmonds_karp(capacity, source, sink):
"""
capacity[u][v] = capacité de l'arc u->v (>=0)
Retour: flot max (int/float)
"""
# Construire le graphe résiduel initial
res = defaultdict(lambda: defaultdict(float))
adj = defaultdict(set)
for u in capacity:
for v, cap in capacity[u].items():
res[u][v] += cap
res[v][u] += 0.0
adj[u].add(v)
adj[v].add(u)
max_flow = 0.0
while True:
# BFS pour trouver un chemin augmentant le plus court
parent = {source: None}
q = deque([source])
while q and sink not in parent:
u = [Link]()
for v in adj[u]:
if v not in parent and res[u][v] > 1e-12:
parent[v] = u
localhost:8888/doc/tree/[Link] 2/3
02/01/2026 21:08 Untitled34
[Link](v)
if sink not in parent:
break # plus de chemin augmentant => flot maximal
# Calculer delta = min capacité résiduelle sur le chemin
delta = float("inf")
v = sink
while v != source:
u = parent[v]
delta = min(delta, res[u][v])
v = u
# Augmenter le flot dans le résiduel
v = sink
while v != source:
u = parent[v]
res[u][v] -= delta
res[v][u] += delta
v = u
max_flow += delta
return max_flow
if __name__ == "__main__":
# Exemple du cours:
# csA = 10, csB = 5, cAB = 3, cAt = 8, cBt = 7 => flot max = 15
capacity = {
"s": {"A": 10, "B": 5},
"A": {"B": 3, "t": 8},
"B": {"t": 7},
"t": {}
}
f = edmonds_karp(capacity, "s", "t")
print("Flot maximal =", f)
Flot maximal = 15.0
In [ ]:
In [ ]:
In [ ]:
localhost:8888/doc/tree/[Link] 3/3