from pylab import * from random import * import time import os ############################################## ############## Tests sur P(n) ################ ############################################## ## Génération de P(n) def P(n) : if n==0 : return [[]] else : L=[] for x in P(n-1) : L.extend([x+[0],x+[1]]) return L # n=4 # print(P(n)) ## Resolution du Sac à dos : exploration dans P(n) def PB_Sac_Partie(L,seuil) : """ trouve une meilleure répartition pour optimiser les valeurs sans dépasser seuil """ Solution=[] valeur_test=0 # valeur test à dépasser n=len(L) for x in P(n) : poids=sum([L[k][2] for k in range(n) if x[k]==1]) if poids<=seuil : # sous-ensemble valide valeur=sum([L[k][1] for k in range(n) if x[k]==1]) if valeur>valeur_test : valeur_test=valeur Solution=[[L[k] for k in range(n) if x[k]==1],valeur,poids] return Solution # n=10 # L=[[str(k),randint(1,20),randint(1,10)] for k in range(n)] # print("Sac",L," de longueur ",len(L)) # seuil=38 # # print(PB_Sac_Partie(L,seuil)) ############################################## ############## Tests récursifs ############### ############################################## def PB_Sac_Rec(L,seuil) : if len(L)==1 : if L[0][2]>seuil : return [[],0,0] else : return [L,L[0][1],L[0][2]] else : x=L[0] Res1=PB_Sac_Rec(L[1:],seuil) if x[2]>seuil : return Res1 else : Res2=PB_Sac_Rec(L[1:],seuil-x[2]) if Res1[1]>Res2[1]+x[1] : return Res1 else : return [[x]+Res2[0],x[1]+Res2[1],x[2]+Res2[2]] # n=10 # L=[[str(k),randint(1,20),randint(1,10)] for k in range(n)] # print("Sac",L," de longueur ",len(L)) # seuil=38 # # print("Tests sur P(n) :",PB_Sac_Partie(L,seuil)) # # print("Tests récursifs :",PB_Sac_Rec(L,seuil)) ############################################## ############ Temps d'exécution ############### ############################################## def Temps_Calculs(n) : LX,LT_Partie,LT_Rec=list(range(1,n+1)),[],[] for l in range(1,n+1) : L=[[str(k),randint(1,20),randint(1,10)] for k in range(l)] seuil=sum([x[2] for x in L])/2 # contrainte=moitié de la somme des poids t_1=time.clock() PB_Sac_Partie(L,seuil) t_2=time.clock() LT_Partie.append(t_2-t_1) t_3=time.clock() PB_Sac_Rec(L,seuil) t_4=time.clock() LT_Rec.append(t_4-t_3) figure() grid() xlabel("nbre d'objets") ylabel("temps d'exécution ") plot(LX,LT_Partie,marker="o",color="magenta") plot(LX,LT_Rec,marker="o",color="cyan") title(r"Performances de deux algorithmes") semilogy() axis([0,n+1,min(LT_Rec+LT_Partie)/10,max(LT_Partie+LT_Rec)*10]) legend((r'dans ${\cal P}(n)$','récursif'),'lower right',shadow=True) savefig('temps_calculs2') show() # n=23 # Temps_Calculs(n) ############################################## ######### Estimation temps calculs ########### ############################################## def LOG(t) : return log(t)/log(10) def F(t) : a=(LOG(163.522)-LOG(0.007819))/(23-9) return 10**(a*(t-23)+LOG(163.522)) def G(t) : a=(LOG(4.54687)-LOG(0.000267489))/(23-9) return 10**(a*(t-23)+LOG(4.54687)) # # figure() # grid() # LX=list(range(1,24)) # LY_Partie=[F(t) for t in LX] # LY_Rec=[G(t) for t in LX] # plot(LX,LY_Partie,color="magenta") # plot(LX,LY_Rec,color="cyan") # semilogy() # show() def Durees(n) : x_Partie,x_Rec=F(n),G(n) Mess_Partie,Mess_Rec="Durée pour l'algo dans P("+str(n)+") : ","Durée pour l'algo récursif : " a_Partie,a_Rec=int(x_Partie//(3600*24*365)),int(x_Rec//(3600*24*365)) if a_Partie>0 : Mess_Partie+=str(a_Partie)+ " année(s) " if a_Rec>0 : Mess_Rec+=str(a_Rec)+ " année(s) " x_Partie-=(3600*24*365)*a_Partie x_Rec-=(3600*24*365)*a_Rec j_Partie,j_Rec=int(x_Partie//(3600*24)),int(x_Rec//(3600*24)) if j_Partie>0 : Mess_Partie+=str(j_Partie)+ " jour(s) " if j_Rec>0 : Mess_Rec+=str(j_Rec)+ " jour(s) " x_Partie-=(3600*24)*j_Partie x_Rec-=(3600*24)*j_Rec h_Partie,h_Rec=int(x_Partie//3600),int(x_Rec//3600) if h_Partie>0 : Mess_Partie+=str(h_Partie)+ " heure(s) " if h_Rec>0 : Mess_Rec+=str(h_Rec)+ " heure(s) " x_Partie-=3600*h_Partie x_Rec-=3600*h_Rec m_Partie,m_Rec=int(x_Partie//60),int(x_Rec//60) if m_Partie>0 : Mess_Partie+=str(m_Partie)+ " minute(s) " if m_Rec>0 : Mess_Rec+=str(m_Rec)+ " minute(s) " x_Partie-=60*m_Partie x_Rec-=60*m_Rec if x_Partie>0 : Mess_Partie+=str(x_Partie)+ " seconde(s) " if x_Rec>0 : Mess_Rec+=str(x_Rec)+ " seconde(s) " print(Mess_Partie) print(Mess_Rec) # n=50 # Durees(n) ############################################## ########### Tests par heuristique ############ ############################################## def PB_Sac_Approx(L,seuil,F) : """ remplit le sac selon les valeurs croissantes de F """ L_Temp=sorted(L,key=lambda objet : F(objet[1],objet[2])) Sac=[] poids=0 valeur=0 for x in L_Temp : if poids+x[2]<=seuil : # si on peut remplir Sac.append(x) # on remplit valeur+=x[1] poids+=x[2] # on incrémente le poids ### remarque : on parcourt toute la liste car les poids ne sont pas toujours en croissance return [Sac,valeur,poids] def Heuris(x,y) : """ fonction poids/valeur """ return y/x # n=10 # L=[[str(k),randint(1,20),randint(1,10)] for k in range(n)] # print("Sac",L," de longueur ",len(L)) # seuil=38 # # print("Tests sur P(n) :",PB_Sac_Partie(L,seuil)) # # print("Tests récursifs :",PB_Sac_Rec(L,seuil)) # # print("Tests heuristiques :",PB_Sac_Approx(L,seuil,Heuris)) ## Temps de calcul def Temps_Calculs_Heuris(n) : LX,LT_Heuris=list(range(1,n+1)),[] for l in range(1,n+1) : L=[[str(k),randint(1,20),randint(1,10)] for k in range(l)] seuil=sum([x[2] for x in L])/2 # contrainte=moitié de la somme des poids t_1=time.clock() PB_Sac_Approx(L,seuil,Heuris) t_2=time.clock() LT_Heuris.append(t_2-t_1) figure() grid() xlabel("nbre d'objets") ylabel("temps d'exécution ") plot(LX,LT_Heuris,color="magenta") title(r"Performance de l'algorithme par heuristique ") semilogy() axis([0,n+1,min(LT_Heuris)/10,max(LT_Heuris)*10]) savefig('temps_calculs_heuris') show() # Temps_Calculs_Heuris(5000) ############################################## ############# Algo du simplexe ############### ############################################## def Algo_Simplexe(M_standard) : """ exécute l'algo du simplexe sur une matrice déjà formatée avec les variables hors base : dernière ligne : objectif """ M=M_standard.copy() p,q=M.shape j_max=argmax(M[-1,:-1]) while M[-1,j_max]>0 : i_ligne=0 val=inf for i in range(p) : if M[i,j_max]>0 and M[i,-1]>0 and M[i,-1]/M[i,j_max]< val : i_ligne=i val=M[i,-1]/M[i,j_max] M[i_ligne,:]/=M[i_ligne,j_max] for k in range(p) : if k!=i_ligne : M[k,:]-=M[k,j_max]*M[i_ligne,:] j_max=argmax(M[-1,:-1]) Res=[] for j in range(q-1) : if M[-1,j]==0 : for i in range(p) : if M[i,j]!= 0 : # on repère la case de la variable hors base Res.append(M[i,-1]) break else : Res.append(0) # variable de base nulle return [Res,-M[-1,-1]] # solution optimale, objectif optimal ### on va augmenter x_{j_max} au maximum pour ne pas dépasser les contraintes: ### rechercher l'index i_ligne tel que M[i,j_max] >0 et M[i,-1]/M[i,j_max] minimal ### remplacer M[k,:] par M[k,:]-M[k,j_max]*M[i_ligne,:] : M[k,j_max] devient nul (le tout pour k != i_ligne) ### mettre une matrice avec au moins un flottant.... M_standard=array([[7.,6,4,1,0,0,0,10],[1,0,0,0,1,0,0,1],[0,1,0,0,0,1,0,1],[0,0,1,0,0,0,1,1],[11,8,5,0,0,0,0,0]]) # print(M_standard) # print(Algo_Simplexe(M_standard))