```
import math
import numpy as np
############################################
class Intervalle:
"""Classe intervalle.
Les attributs définissant les bornes inférieure et supérieure sont cachés
et en lecture seule.
"""
def __init__(self, inf, sup):
"""Concstructeur d'intervalle.
Parameters
----------
inf: float, optionel
Borne inférieure.
sup: float, optionel
Borne supérieure.
"""
self.__inf = inf
self.__sup = sup
@property
def inf(self):
"""Accès à la borne inférieure.
"""
return self.__inf
@property
def sup(self):
"""Accès à la borne supérieure.
"""
return self.__sup
def __str__(self):
"""Chaîne de caractères représentant un intervalle.
"""
return '[{}, {}]'.format(self.inf, self.sup)
def __eq__(self, y):
"""Teste l'égalité de deux intervalles (mêmes bornes).
Parameters
----------
y: Intervalle
Returns
-------
True si les itervalles sont égaux: boolean
"""
return self.inf == y.inf and self.sup == y.sup
def __neg__(self):
"""Retourne l'opposé d'un intervalle.
Returns
-------
Opposé de l'intervalle: Intervalle
"""
return Intervalle(-self.sup, -self.inf)
def __add__(self, y):
"""Somme de deux intervalles.
Parameters
----------
y: Intervalle
Returns
-------
Somme de deux intervalles: Intervalle
"""
return Intervalle(self.inf + y.inf, self.sup + y.sup)
def __sub__(self, y):
"""Différence de deux intervalles. S'appuie sur add et neg.
Parameters
----------
y: Intervalle
Returns
-------
Différence de deux intervalles: Interval
"""
return self + (-y)
def __mul__(self, y):
"""Produit de deux intervalles.
Parameters
----------
y: Intervalle
Returns
-------
Produit des deux intervalles: Interval
"""
lst = [a*b for a in (self.inf, self.sup) for b in (y.inf, y.sup)]
return Intervalle(min(lst), max(lst))
def __truediv__(self, y):
"""Quotient de deux intervals. Une exception est levée si le
dénominateur contient 0.
Parameters
----------
y: Intervalle
Returns
-------
Quotient des deux intervalles: Interval
"""
# If 0 in the interval, at least one bound is infinite
if y.inf * y.sup <= 0:
raise Exception('Attention division par un intervalle contenant zéro')
else:
# y ne contient pas 0. On peut donc diviser self par y
lst = [a/b for a in (self.inf, self.sup) for b in (y.inf, y.sup)]
return Intervalle(np.nanmin(lst), np.nanmax(lst))
def __pow__(self, n):
"""Puissance entière d'un intervalle.
Parameters
----------
n: integer
Returns
-------
Puissance de l'intervalle : Intervalle
"""
lst = [self.inf**n, self.sup**n]
# Si la puissance est paire, cas particulier des intervalles contenant 0
if n % 2 == 0:
if self.inf * self.sup <= 0:
return Intervalle(0, max(lst))
return Intervalle(min(lst), max(lst))
def __contains__(self, val):
"""Teste si une valeur fait partie d'un intervalle.
Parameters
----------
val: float
Returns
-------
Vrai si `val` est dans l'intervalle: boolean
"""
return self.inf <= val <= self.sup
def width(self):
"""Largeur d un intervalle.
Returns
-------
la largeur de l intervalle: float
"""
return self.sup - self.inf
def mid(self):
""" Milieu de l intervalle.
Return
------
Le mileu de l intervalle: float
"""
return (self.inf+self.sup)/2
def sqrt(x):
r"""Extension de la fonction sqrt à un intervalle.
Parameters
----------
x: Intervalle
Returns
-------
Racine carrée de l'intervalle `x`: Intervalle
:math:`\sqrt{x}`
"""
# Cas particulier d'un intervalle négatif
if x.sup < 0:
raise Exception('Attention racine d un intervalle contenant négatif')
# Cas particulier de la borne inf négative
elif x.inf < 0:
return Intervalle(0, x.sup**0.5)
else:
return Intervalle(x.inf**0.5, x.sup**0.5)
def exp(x):
r"""Extension de la fonction exponentielle à un intervalle.
Parameters
----------
x: Intervalle
Returns
-------
Exponentielle de l'intervalle: Intervalle
:math:`e^x`
"""
return Intervalle(math.exp(x.inf), math.exp(x.sup))
def log(x):
r"""Extension de la fonction logarithme à un intervalle.
Parameters
----------
x: Intervalle
Returns
-------
Logarithme de l'intervalle : Intervalle
:math:`\log{x}`
"""
# Cas particulier de la borne inf négative ou nulle
if x.inf <= 0:
raise Exception('Attention logarithme d un intervalle contenant zéro')
else:
return Intervalle(math.log(x.inf), math.log(x.sup))
############################################
def branchandBound(f, I):
lst = [I] # initialisation de la liste avec l'intervalle en entier
ftilde = float('inf')
while len(lst) > 0:
X = lst.pop() # extraction de la tete de lst
borne = f(X) # calcul d'un minorant et d'un majorant de f sur X
# on enleve 1e-6 pour être sur de trouver vraiment une meilleur solution
if borne.inf < ftilde - 1.e-6:
# il est possible de trouver une meilleur solution dans X
mid = X.mid() # calcul du milieu de X
test = f(Intervalle(mid, mid)) # evaluation de f au point milieu
# nous somme obligé de faire ainsi car f retourne un intervalle
# et non un nombre flottant
test = test.mid()
if test < ftilde:
# on a trouvé une meilleur solution
ftilde = test # on stocke la nouvelle solution
xtilde = mid
X1 = Intervalle(X.inf, mid) # on decoupe X en deux intervalles
X2 = Intervalle(mid, X.sup)
# on ajoute X1 et X2 à la liste des intervalles restant à traiter
lst.append(X1)
lst.append(X2)
return xtilde, ftilde
def mafonction(x):
return x**5 + x + exp(x**2) - x*exp(x)
############################################
if __name__ == '__main__':
x1 = Intervalle(1, 2)
x2 = Intervalle(2, 6)
print(x1 * x2**2 - exp(x1 + x2))
x_sol, f_sol = branchandBound(mafonction, Intervalle(-1, 1))
print("Le minimum est atteint en ", x_sol)
print("La valeur du minimum de f sur [-1,1] est : ", f_sol)
```
Sign in with Wallet
Connect another wallet