-
Notifications
You must be signed in to change notification settings - Fork 0
/
borne_lagrange.py
75 lines (55 loc) · 2.3 KB
/
borne_lagrange.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
import numpy as np
import cvxpy as cp
from donnees import *
def SP1(D, pi):
y = cp.Constant(np.zeros((len(D.Articles), D.L_max)))
nested_sum = [cp.sum(- pi[i][j] * D.Articles[i].nombre * y[i][j]).value for j in range(D.L_max) for i in range(len(D.Articles))]
obj = cp.Maximize(cp.sum(nested_sum))
constraints1 = [np.sum(y[i][j] for i in range(len(D.Articles))) <= D.e_max for j in range(D.L_max)]
constraints2 = [np.sum(y[i][j] for i in range(len(D.Articles))) >= D.e_min for j in range(D.L_max)]
constraints3 = [np.sum(D.Articles[i].indice * y[i][j] for i in range(len(D.Articles))) >= D.r_min for j in range(D.L_max)]
prob = cp.Problem(obj, constraints1 + constraints2 + constraints3)
prob.solve()
return y.value
def SP2(D, pi):
x = cp.Constant(np.zeros((len(D.Articles), D.L_max)))
nested_sum = [cp.sum((D.Articles[i].prix + pi[i][j]) * x[i][j]).value for j in range(D.L_max) for i in range(len(D.Articles))]
obj = cp.Maximize(cp.sum(nested_sum))
constraints1 = [np.sum(x[i][j] for j in range(D.L_max)) <= D.Articles[i].nombre for i in range(len(D.Articles))]
prob = cp.Problem(obj, constraints1)
prob.solve()
return x.value
def sous_grad(D):
iter = 0
alpha, rho = 0.9, 2
pi = np.zeros((len(D.Articles), D.L_max))
UB = 0
while iter < 1:
y = SP1(D, pi)
x = SP2(D, pi)
ub_courant = 0
# calcul de la borne sup
for i in range(len(D.Articles)):
for j in range(D.L_max):
ub_courant += - pi[i][j] * D.Articles[i].nombre * y[i][j] + (D.Articles[i].prix + pi[i][j])* x[i][j]
if ub_courant > UB:
UB = ub_courant
# calcul du sous gradient
grad = np.zeros((len(D.Articles), D.L_max))
for i in range(len(D.Articles)):
for j in range(D.L_max):
grad[i][j] = y[i][j] + x[i][j]
# mise à jour de pi
sum_grad = np.sum(grad)
for i in range(len(D.Articles)):
for j in range(D.L_max):
pi[i][j] += rho * ((UB - ub_courant) / sum_grad) * grad[i][j]
iter += 1
rho = alpha * rho
return UB
def main():
instance = "instances_test/test1.json"
D = import_donnees_from_json(instance)
UB = sous_grad(D)
print(UB)
main()