TP de Tableur, 05.12.2013


Envoyez-moi vos solutions d'aujourd'hui. Certains continuent à traîner avec les précédents. Sachez que le délai dépassé (plus de 7 jours depuis les TP), je ferme la boîte et je ne lirai plus vos solutions. Vous ne me faites aucune faveur en m'envoyant vos exercices. Ceci influencera vos notes, si cela vous est égal, tant mieux.


Exercices

Attention ! Je viens de constater que le Solveur officiellement n'a aucune raison de marcher correctement avec des problèmes non-linéaires ! Donc, le "problème de rectangle" a pu échouer sur vos machines. Le fait que la méthode marchait sur la mienne, peut être considéré comme accidentel...

Le Solveur non-linéaire a été implémenté et marchait sur OpenOffice - le logiciel sur lequel est basé LibreOffice. Visiblement, au lieu de progresser, ils ont réussi à casser quelque chose... Je suis désolé pour la pagaille, j'aurais dû vérifier tout ceci avant.

Mais ne désespérons pas ! L'exercice sur le flot maximum (la recherche opérationnelle) est linéaire, et le Solveur doit marcher. Au travail !


Recherche opérationnelle. Un "vrai" exercice sur ce que l'on appelle la "recherche opérationnelle".

Un produit venant de Usine1 et Usine2 doit être livré à trois clients (Client 1, 2 et 3). Le transport est assuré par un système qui utilise un réseau de 5 plates-formes (PF1 à PF5). Les capacités de transport sur chacun des liens du réseau sont limitées aux valeurs données dans le graphe affiché. Les quantités de produit disponibles en stock dans les usines sont respectivement de 35 pour Usine 1 et 25 pour Usine 2. Les demandes des trois clients sont respectivement de 15 pour Client 1 et pour Client 2 et 20 pour Client 3. Trouver un programme de transport qui satisfasse la demande des clients.

Il s'agit d’un problème de flux maximal (ou : flot maximal) que nous pouvons modéliser en indiquant que la quantité de produit qui transite sur chaque arc doit rester inférieure à sa capacité, que les flux sont conservés dans tous les sommets (sauf les Usines et les Clients), et que la somme des flux arrivant aux Clients doit être maximale.

La stratégie utilisée est décrite dans le document pédagogique consacré à la recherche opérationnelle ; Exercice 7, page 23. (Auteur : Bertrand Julien). Lisez le contenu, essayez de répliquer le raisonnement et éventuellement le code (on peut le faire de manière un peu plus simple !).


L'exercice "rectangle" QUAND MÊME...

Voir les détails de l'exercice sur la page 28.11.

Puisque on a le contour : $2\cdot (x+y) = L = 156$ figé, et on cherche a maximiser l'aire $S=x\cdot y$, on peut réduire cela à un problème uni-dimensionnel : $S = x\cdot (L/2 - x)$. Comme vous le savez, quand une fonction prend son extrême, sa dérivée doit s'annuler, donc $dS/dx = 0 = \cdots$ – faites le calcul vous-mêmes.

L'équation est linéaire en $x$. Lancez Solveur, en ajoutant – peut-être – les contraintes supplémentaires, genre $x > 10$ et $x < 200$. La réponse : $x=39$ est très rapide sur mon ordinateur.


Interpolation quadratique. Ceci est un simple exercice en arithmétique, mais un peu discipliné. Si on a une liste de paires de donées $xy$, le tableur afin de tracer la courbe effectue l'interpolation linéaire entre les valeurs, comme dans un de nos anciens exercices.

Cependant, il est parfois souhaitable d'effectuer l'interpolation plus douce, que celle sur le dessin à droite.

On peut, et d'habitude on doit interpoler les données mieux que linéairement, par ex. le graphique à gauche montre une interpolation d'ordre supérieur (superposée sur la linéaire).

La stratégie est facile, mais encombrante.

Avec le tableur ce n'est pas évident, typiquement on profite des macros extérieures, écrites par quelqu'un en Basic (ou en Java, ou quelques autres langages, selon le logiciel...).

Votre exercice consiste à prendre trois points $(x_0, y_0), (x_1, y_1), (x_2, y_2)$ parmi plusieurs. Par exemple, construisez une liste (colonne) $x_i$ : $0, 0.1, 0.2, \ldots 1, 1.1, 1.2, \ldots, 2, \ldots, 2.9, 3$. Ensuite choisissez 3 points : $x_0=0, x_1=1,$ et $x_2=3$ (comme nos données ci-dessus).

Les valeurs $y$ appropriées sont : $y_0=2.5, y_1=1$, et $y_2=5.7$. Les autres cases dans la colonne $y$ resteront pour l'instant vides.

On cherche la courbe $y(x)$ telle, que $y(x_i) = y_i$. Elle doit être quadratique en $x$, c'est-à-dire : $y(x) = A x^2 + B x + C$. On a donc trois équations linéaires :

$A x_0^2 + B x_0 + C = y_0$
$A x_1^2 + B x_1 + C = y_1$
$A x_2^2 + B x_2 + C = y_2$

Vous pouvez résoudre ces équations (aussi avec le solveur, mais je le déconseille, il est vraiment mauvais...), mais vous pouvez exploiter aussi la formule de Lagrange, qui pour le polynôme de degré 2 a la forme :

$\displaystyle{y(x) = y_0\cdot\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)} + y_1\cdot\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)} + y_2\cdot\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}}$ .

Ceci ne vous donne pas les coefficients A, B et C, mais directement la dépendance fonctionnelle $y(x)$, permettant de remplir la colonne des $y$.

Faire le graphique de la fonction, entre les trois points. Si le temps vous reste, répétez avec d'autres points. Mais comment faire l'interpolation globale de la courbe entière?...



Solutions

Retour