Formellement, étant données les informations rassemblées dans l'énoncé, on a le modèle
à $n=2$ variables suivant :
\[
\begin{array}{c}
\min 4.1 x_0 + 8 x_1\\
\text{sous les contraintes}\\
x_1 \geq 12\\
x_0\leq 10\\
6 x_0 + 18 x_1 = 70\\
x_0 \geq 0\\
x_1 \geq 0
\end{array}
\]
Commençons par donner une représentation graphique des contraintes. Il n'est pas possible de représenter
directement une droite verticale avec une fonction. Mais,...
si on lui donne une pente très forte, qu'on déplace l'origine au point désiré et que l'on restreint l'étendue
de l'axe des ordonnées, le travail est fait. On notera que sans packages additionnels, il n'est pas possible
d'avoir des caractères accentués dans les graphiques.
d'obtenir un point faisable ?
Quelle valeur du terme de droite de la contrainte égalitaire permet, toutes choses égales par ailleurs, d'obtenir un point faisable ?
Si on remplace 70 par 260, le graphique suivant permet d'obtenir le maximum.
Les $m=3$ contraintes peuvent donc se reécrire :
\[
\begin{array}{c}
12\leq x_1 \leq \infty\\
0\leq x_0\leq 10\\
70\leq 6 x_0 + 18 x_1 \leq 70\\
\end{array}\hspace{.25cm}\Longleftrightarrow \hspace{.25cm}
\begin{array}{c}
12\leq 0 x_0 + 1 x_1 \leq \infty\\
0\leq 1 x_0 + 0 x_1\leq 10\\
70\leq 6 x_0 + 18 x_1 \leq 70\\
\end{array}
\]
On peut donc écrire le programme à optimiser comme suit en utilisant la commande MixedIntegerLinearProgram().
Dans un premier temps, on définit les vecteurs et matrices nécessaires :
L1
%display latex
m=3 #nombre de contraintes
n=2 # nombre de variables
A=matrix(m,n,(0,1,1,0,6,18))
bmin=[12,0,70]
bmax=[oo,10,70]
c=matrix(1,n,(4.1,8))
show(LatexExpr(r"\boldsymbol{A} = "),A,LatexExpr(r", \boldsymbol{b}\mathrm{min} = "),bmin,
LatexExpr(r", \boldsymbol{b}\mathrm{max} = "),bmax,LatexExpr(r"\text{ et } \boldsymbol{c} = "),c)
#bmin = [0,0,0] # borne inférieure des contraintes
# bmax = [5,11,8] # borne supérieure des contraintes
Puis on construit le programme :
L1
p = MixedIntegerLinearProgram(maximization=False, solver = "GLPK") # Création du MILP
# on peut remplacer GLPK par PPL pour obtenir une optimisation fractionnaire.
x = p.new_variable(integer=False, indices=[0..n-1]) # les nouvelles variables seront x[1]... x[7]}
B = A * x # m
# Construction des contraintes
for i in range(m):
p.add_constraint(B[i], min=bmin[i], max=bmax[i])
# remove_constraint() pour en retirer une
for i in range(n):
p.set_min(x[i],0)
p.set_objective(4.1*x[0]+8*x[1])# définition de l'objectif
p.show() # Vérification
On peut alors obtenir la solution par le code suivant :
L1
sol=p.solve()
show(sol)
On constate que dans ces conditions il n'y a pas de solutions. On remplace alors 70 par 260.
L1
%display latex
m=3 #nombre de contraintes
n=2 # nombre de variables
A=matrix(m,n,(0,1,1,0,6,18))
bmin=[12,0,260]
bmax=[oo,10,260]
c=matrix(1,n,(4.1,8))
p1 = MixedIntegerLinearProgram(maximization=False, solver = "GLPK") # Création du MILP
# on peut remplacer GLPK par PPL pour obtenir une optimisation fractionnaire.
x = p1.new_variable(integer=False, indices=[0..n-1]) # les nouvelles variables seront x[1]... x[7]}
B = A * x # m
# Construction des contraintes
for i in range(m):
p1.add_constraint(B[i], min=bmin[i], max=bmax[i])
# remove_constraint() pour en retirer une
for i in range(n):
p1.set_min(x[i],0)
p1.set_objective(4.1*x[0]+8*x[1])# définition de l'objectif
p1.show() # Vérification
Il ne reste plus qu'à résoudre ce programme et à afficher la solution :
