{ "cells": [ { "cell_type": "markdown", "id": "61b08b43-f9d1-4c81-9e72-0718e8ee9be7", "metadata": {}, "source": [ "
\n", " Aide à la décision
\n", "
\n", "

Navigation dans la page

\n", "

\n", " Si c'est votre première visite dans ce TP, lisez attentivement chacun des points détaillé après ce paragraphe.
\n", " Si vous avez déjà commencer à travailler sur ce TP et que vous souhaiter vous déplacer rapidement dans une partie précise vous pouvez choisir la partie que vous souhaitez rejoindre ci-dessous.
\n", "

\n", " Menu de navigation (cliquez pour dérouler)\n", " \n", "
\n", "

\n", "
\n", " Technologie jupyter (cliquer pour dérouler)\n", "

\n", " La technologie jupyter permet d'exécuter du code python par un simple clique sur Executer ci-dessus.
\n", " Les morceaux de code de cette page sont interprétées case par case. Pour savoir quelle case a été interprétée avant une autre, il suffit de repérer le numéro devant la case.
\n", " Une fois qu'une case a été interprétée (=exécutée), la page garde en mémoire les variables et fonctions lues
\n", " La plateforme propose quelques outils de purge de la mémoire : \n", "

\n", "

\n", "
\n", "

SAUVEGARDER VOTRE TRAVAIL

\n", "

\n", " Pour ne pas perdre votre travail pensez à le sauvegarder régulièrement. Par défault, la sauvegarde par un clic sur la disquette en haut à gauche de page, ou par le racourci clavier classique ctrl+S\n", " est une sauvegarde en local, sur le serveur de jupyter. Vous pouvez et devez très régulièrement sauvegarder votre travail sur votre support personnel de sauvegarde (clef USB, se l'envoyer par mail etc). Ce faisant vous disposerez d'un fichier .ipynb (IPYthon NoteBook) qu'il vous suffira de recharger pour avancer. Après le rechargement assurez vous que les fonctionnalités anciennement developpées et variables utilisées sont bien dans la mémoire de la page (en rééxecutant les cases, ou plus rapidement par Kernel > Restart & Run All.

\n", "

A NOTER : vous pouvez travailler sur le tp (et tout autre fichier .ipynb) hors connexion en installant une version local du notebook de jupyter. Il faut que votre machine possède un interpreteur de python et que vous soyez connecter à internet.\n", "

    \n", "
  1. Lancer un terminal
    2. \n", "
  2. Taper la commande suivante : pip install jupyterlab
    3. \n", "
  3. Une fois l'installation terminée portez votre attention sur les dernières lignes affichées dans votre terminal vous invitant probablement à taper une ligne de commande pour faire une mise à jour
    4. \n", "
  4. Pour lancer notebook de jupyter, taper dans votre termial : jupyter notebook
    5. \n", "
  5. Votre simulateur de serveur est lancé. Il ne faut pas fermer votre terminal, auquel cas votre simulateur de serveur s'interompera. Suivez le lien indiqué dans les dernières lignes de votre terminal pour vous diriger vers votre espace local. L'interface se présente comme celle que vous trouverez sur le web. Votre travail sera cependant toujours enregistré et jamais perdu même si vous le consultez après plusieurs jours
    6. \n", "
\n", "

\n", "
\n", "
" ] }, { "cell_type": "markdown", "id": "0a42ad92-d2ab-4006-a44c-5ecd4651759f", "metadata": {}, "source": [ "

Le $\\LaTeX$ est un langage d'édition d'équation permettant d'afficher élegament des mathématiques. Preuve, s'il en faut, l'élégante formule dû à L. Euler : $$\\sum_{n=1}^{+\\infty}\\dfrac{1}{n^2}=\\dfrac{\\pi^2}{6}$$ qui correspond au code \\sum_{n=1}^{+\\infty}\\dfrac{1}{n^2}=\\dfrac{\\pi^2}{6} (vous pouvez afficher le code source de cette case en double cliquant dessus pour vous en convaincre). Par défaut, la technologie jupyter permet cet habillage sans plus d'éffort que de connaitre $\\LaTeX$ dans les case comme celle-ci (en markdown). \n", "
\n", " Cependant, pour des raisons purement ésthétique, nous allons faire des programmes qui vont retourner du code latex et nous souhaitons que, dans des cases en python, ce code s'affice correctement. Pour ce faire il suffit d'une petite bibliothèque avec deux de ses fonctions.

" ] }, { "cell_type": "code", "execution_count": null, "id": "f9b98d39-4d2e-41ba-807d-5fea75b071cd", "metadata": {}, "outputs": [], "source": [ "from IPython.display import display, Math" ] }, { "cell_type": "code", "execution_count": null, "id": "5ac328b3-a143-46dc-b110-cd51c94c0a8b", "metadata": {}, "outputs": [], "source": [ "tex=r\"\\sum_{n=1}^{+\\infty}\\dfrac{1}{n^2}=\\dfrac{\\pi^2}{6}\"\n", "#Le 'r' devant la chaine de caractère indique à python qu'il ne doit pas exécuter les caractère d'échappement.\n", "#Ce sont les caractères tel que le saut de ligne ou la tabulation (respectivement \\n et \\t)\n", "#qui se reconnaissent par la présence d'un backslash\n", "#Cependant le backslash est également un caractère spécial du langage LaTeX d'où la présence du r\n", "display(Math(tex))" ] }, { "cell_type": "markdown", "id": "10189cf6-6f00-4755-b00d-58b24a7dd7e7", "metadata": {}, "source": [ "

Dans ce TP, nous allons programmer de nombreuses fonctions toutes utilisables (et souvent à utiliser) et avons différente structure de donnée. Vous trouverez donc, pour chaque exercice demandé un menu déroulant indiquant les fonctions précédement développées en claire et celle qui seront développés plus loin dans le TP en sombre ainsi qu'un rappel des différents outils et convention du TP. Vous pourrez cliquer sur le nom de chaque fonction pour vous déplacer dans la page et retrouver (et souvent corriger ;-) ) votre code.

\n", "\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase2(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "markdown", "id": "0562cf56-244a-4cfe-8c75-9cc9dd15f2ed", "metadata": {}, "source": [ "
\n", " Partie 1 : L'algorithme de Gauss \n", "
\n", "\n", "

\n", "

\n", " Menu de navigation (cliquez pour dérouler)\n", " \n", "
\n", "

" ] }, { "cell_type": "markdown", "id": "7ea2361f-7d06-4ef0-87fd-c51506a8f79a", "metadata": {}, "source": [ "

Dans cette partie nous allons nous intéresser à appliquer l'algorithme de Gauss-Jordan permettant d'inverser des matrices.\n", "
\n", "On considère une matrice $M$ que nous souhaitons inverser.\n", "
La méthode consiste à augmenter cette matrice en lui accollant la matrice identité et de réaliser un ensemble d'opération sur les lignes de cette matrice augmentée pour faire apparaitre la matrice identité sur la gauche. L'inverse de la matrice sera donc la partie de droite.\n", "\n", "$$\n", "\\begin{pmatrix}\n", "&&&&1&&0\\\\\n", "&&M&&&\\ddots&\\\\\n", "&&&&0&&1\n", "\\end{pmatrix}\n", "\\Longrightarrow\n", "\\begin{pmatrix}\n", "1&&0&&&&\\\\\n", "&\\ddots&&&M^{-1}&&\\\\\n", "0&&1&&&&\n", "\\end{pmatrix}\n", "$$\n", "\n", "Monsieur Gauss, démontre que trois opérations sont nécessaires et suffisantes pour y arriver.\n", "

\n", "\n", "Prenons l'exemple de la matrice $M=\\begin{pmatrix}0&1\\\\2&2\\end{pmatrix}$. Sa matrice augmentée est $\\tilde{M}=\\begin{pmatrix}0&1&1&0\\\\2&2&0&1\\end{pmatrix}$\n", "
\n", "Notons $L_i$ la $i$-ième ligne. Pour nous rapprocher de l'outil informatique nous allons noter : \n", "\n", "\n", "Alors l'algorithme de Gauss-Jordan peut donner dans notre exemple : \n", "\\begin{eqnarray*}\n", "\\begin{pmatrix}0&1&1&0\\\\2&2&0&1\\end{pmatrix} \n", "&\\Rightarrow&\n", "\\begin{pmatrix}\n", "2&2&0&1\\\\\n", "0&1&1&0\n", "\\end{pmatrix}\\qquad L_1 \\leftrightarrow L_2\\\\\n", "&\\Rightarrow&\n", "\\begin{pmatrix}\n", "2&0&-2&1\\\\\n", "0&1&1&0\n", "\\end{pmatrix}\n", "\\qquad L_1 \\leftarrow L_1-2L_2\\\\\n", "&\\Rightarrow&\n", "\\begin{pmatrix}\n", "1&0&-1&\\dfrac{1}{2}\\\\\n", "0&1&1&0\n", "\\end{pmatrix}\n", "\\qquad L_1 \\leftarrow \\dfrac{1}{2}L_1\\\\\n", "\\end{eqnarray*}\n", "\n", "Puisque nous avons réussi à faire apparaitre l'identité à gauche, la matrice de droite est l'inverse : $M^{-1}=\\begin{pmatrix}-1&\\dfrac{1}{2}\\\\1&0\\end{pmatrix}$\n", "

\n", "\n", "

Commençons par programmer les outils nous aidant à appliquer cette algorithme.

" ] }, { "cell_type": "markdown", "id": "7fbd0bd9-d106-4b1d-aece-e4d428e8ad4d", "metadata": {}, "source": [ "

Comme souvent en informatique, une matrice sera considérée comme une liste de liste. La fonction suivante permet d'afficher (élégament) une matrice. Éxecutez cette case ainsi que les deux suivantes pour la tester.

" ] }, { "cell_type": "code", "execution_count": null, "id": "fdb91986-0477-4f48-91b6-d2cc6da48fbe", "metadata": {}, "outputs": [], "source": [ "def printM(M, precision=2) : \n", " try : \n", " lig=len(M)\n", " col=len(M[0])\n", " for i in range(lig) : \n", " if(len(M[i])!=col) : return \"\"\n", " except : return \"\"\n", "\n", " tex=r'\\begin{pmatrix}'\n", " for i in range(lig) : \n", " for j in range(col) :\n", " tex+=str(round(M[i][j], 2))\n", " if(jÉcrire la fonction matriceAugmentee(M) qui renvoie la matrice $M$ passée en paramètre à laquelle on a accollé à droite la matrice identité.\n", "On rappel que len(M) permet de récupérer le nombre de ligne de $M$ et len(M[0]) le nombre de colonne.

\n", "

\n", " Cette fonction renvera None s'il y a un problème de dimension.\n", "

\n", "\n", "\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase2(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "0da863fd-a819-4dff-bd38-cffc2ced70ca", "metadata": {}, "outputs": [], "source": [ "def matriceAugmentee(M) : \n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "6e50bcb1-3985-4378-9f0a-a6a52fd547e7", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "exemple1_A=matriceAugmentee(exemple1)\n", "\n", "print(\"Exemple 1\")\n", "print(\"Matrice de départ\")\n", "printM(exemple1)\n", "print(\"Matrice augmentée\")\n", "printM(exemple1_A)\n", "\"\"\"\n", "0 1 1 0\n", "2 2 0 1\n", "\"\"\";" ] }, { "cell_type": "code", "execution_count": null, "id": "763d60e2-5103-40be-9660-3f2253f73a36", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "exemple2_A=matriceAugmentee(exemple2)\n", "\n", "print(\"Exemple 2\")\n", "print(\"Matrice de départ\")\n", "printM(exemple2)\n", "print(\"Matrice augmentée\")\n", "printM(exemple2_A)\n", "\"\"\"\n", "4 2 1 1 1 0 0 0\n", "3 1 2 4 0 1 0 0\n", "1 3 4 2 0 0 1 0\n", "2 4 3 1 0 0 0 1\n", "\"\"\";" ] }, { "cell_type": "markdown", "id": "84990ca1-4e11-4d52-918b-6394299b07e9", "metadata": {}, "source": [ "

Écrire la fonction operationGaussEchange(M, I, J) qui échange les lignes I et J de la matrice M. On prendra garde qu'une matrice M est une liste donc, infomatiquement une adresse. Il faut mieux créer une copie de la matrice pour ne pas écraser ses valeurs...

\n", "\n", "

\n", " Cette fonction renvera None s'il y a un problème de dimension.\n", "

\n", "\n", "\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase2(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "f0f934e2-877a-4a66-9a39-182bac0b5d2f", "metadata": {}, "outputs": [], "source": [ "def operationGaussEchange(M, I, J) : \n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "5225f715-d8bf-4a3c-bc9e-77e8fda1c172", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "exemple1_A_0 = operationGaussEchange(exemple1_A, 0, 1)#Echange des deux lignes\n", "\n", "print(\"Exemple 1\")\n", "print(\"Matrice de départ\")\n", "printM(exemple1)\n", "print(\"Matrice augmentée\")\n", "printM(exemple1_A)\n", "print(\"Échange des deux lignes\")\n", "printM(exemple1_A_0)\n", "\"\"\"\n", "2 2 0 1\n", "0 1 1 0\n", "\"\"\";" ] }, { "cell_type": "code", "execution_count": null, "id": "9fa1bcb1-2ad4-4a86-bd0c-20edde629e8a", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "exemple2_A_0 = operationGaussEchange(exemple2_A, 0, 2)#Echange des lignes 1 et 3\n", "\n", "print(\"Exemple 2\")\n", "print(\"Matrice de départ\")\n", "printM(exemple2)\n", "print(\"Matrice augmentée\")\n", "printM(exemple2_A)\n", "print(\"Échange : L_3<->L_1\")\n", "printM(exemple2_A_0)\n", "\"\"\"\n", "1 3 4 2 0 0 1 0\n", "3 1 2 4 0 1 0 0\n", "4 2 1 1 1 0 0 0\n", "2 4 3 1 0 0 0 1\n", "\"\"\";" ] }, { "cell_type": "markdown", "id": "db82813f-7be6-4c14-90a8-8b86b0a7f138", "metadata": {}, "source": [ "

Écrire la fonction operationGaussDilatation(M, I, coef) qui renvoie la matrice M où la ligne I est multipliée par un coefficient coef.

\n", "\n", "

\n", " Cette fonction renvera None s'il y a un problème de dimension.\n", "

\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase2(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "6965cba3-84b6-48df-982f-40e5e7c0ad68", "metadata": {}, "outputs": [], "source": [ "def operationGaussDilatation(M, I, coef) : \n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "443af2cc-fbb8-4749-82da-f6ad7f0d6e49", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "exemple1_A_1=operationGaussDilatation(exemple1_A_0, 0, 1/2)#On divise la première ligne par 2\n", "\n", "print(\"Exemple 1\")\n", "print(\"Matrice de départ\")\n", "printM(exemple1)\n", "print(\"Matrice augmentée\")\n", "printM(exemple1_A)\n", "print(\"Échange des deux lignes\")\n", "printM(exemple1_A_0)\n", "print(\"Dilation de la seconde ligne par 1/2\")\n", "printM(exemple1_A_1)\n", "\"\"\"\n", "1.0 1.0 0.0 0.5\n", " 0 1 1 0\n", "\"\"\";" ] }, { "cell_type": "markdown", "id": "9e9ade89-a1f0-4d31-8f02-8a0473153890", "metadata": {}, "source": [ "

Écrire la fonction operationGaussCombinaison(M, I, J, coef) qui renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef ($L_I\\leftarrow L_I+coef \\times L_J$).

\n", "\n", "\n", "

\n", " Cette fonction renvera None s'il y a un problème de dimension.\n", "

\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase2(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "e74b71ef-acde-418e-8b61-044cc7785427", "metadata": {}, "outputs": [], "source": [ "def operationGaussCombinaison(M, I, J, coef) : \n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "1b0a9bfa-e674-4462-a0a6-d0b4e5e4dbf7", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "exemple1_A_2=operationGaussCombinaison(exemple1_A_1, 0, 1, -1)#On écrase la première ligne par première ligne moins seconde ligne\n", "\n", "print(\"Exemple 1\")\n", "print(\"Matrice de départ\")\n", "printM(exemple1)\n", "print(\"Matrice augmentée\")\n", "printM(exemple1_A)\n", "print(\"Échange des deux lignes\")\n", "printM(exemple1_A_0)\n", "print(\"Dilation de la seconde ligne par 1/2\")\n", "printM(exemple1_A_1)\n", "print(\"Combinaison : L1<-L1-L2\")\n", "printM(exemple1_A_2)\n", "\"\"\"\n", "1.0 0.0 -1.0 0.5\n", " 0 1 1 1\n", "\"\"\";" ] }, { "cell_type": "markdown", "id": "58e5fdfd-d26f-4de1-8a9b-849be5262be8", "metadata": {}, "source": [ "

On observe en particulier que la partie de gauche de la précédente matrice est la matrice identité. L'algorithme de Gauss-Jordan indique alors que la partie de droite est la matrice inverse.

\n", "

Écrire la fonction recupInv(MAugmentee) qui renvoie la partie de droite de la matrice augmentée MAugmentee.

\n", "\n", "\n", "

\n", " Cette fonction renvera None s'il y a un problème de dimension.\n", "

\n", "\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase2(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "03d12729-4a45-45bd-8b20-652f34d73dd4", "metadata": {}, "outputs": [], "source": [ "def recupInv(MAugmentee) : \n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "c2d45654-e04d-49dd-8bcb-e2bab37d8c14", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "exemple1_A_Inv=recupInv(exemple1_A_2)#On récupère l'inverse\n", "\n", "print(\"Exemple 1\")\n", "print(\"Matrice de départ\")\n", "printM(exemple1)\n", "print(\"Matrice augmentée\")\n", "printM(exemple1_A)\n", "print(\"Échange des deux lignes\")\n", "printM(exemple1_A_0)\n", "print(\"Dilation de la seconde ligne par 1/2\")\n", "printM(exemple1_A_1)\n", "print(\"Combinaison : L1<-L1-L2\")\n", "printM(exemple1_A_2)\n", "print(\"L'inverse de la matrice de départ\")\n", "printM(exemple1_A_Inv)\n", "\"\"\"\n", "-1.0 0.5\n", " 1 0\n", "\"\"\";" ] }, { "cell_type": "markdown", "id": "d7fa5b1c-ccfb-4c28-8a12-f202ba0ed0c8", "metadata": {}, "source": [ "

Observez les opérations suivantes qui permettent de réaliser ce processus sur la seconde matrice exemple.

\n", "\n", "

A l'issu de toutes ces exécutions la matrice inverse s'approche par \n", "$$\\begin{pmatrix}\n", " 0.5& -0.15& 0.25& -0.4\\\\\n", "-0.5& 0.25& -0.75& 1.0\\\\\n", " 0.5& -0.4 & 1.0 & -0.9\\\\\n", "-0.5& 0.5 & -0.5 & 0.5\n", "\\end{pmatrix}$$\n", "

" ] }, { "cell_type": "code", "execution_count": null, "id": "de6fbf7d-8042-4c85-a718-00a254d3baa5", "metadata": {}, "outputs": [], "source": [ "exemple2_A_1 = operationGaussCombinaison(exemple2_A_0, 1, 0, -exemple2_A_0[1][0])\n", "exemple2_A_2 = operationGaussCombinaison(exemple2_A_1, 2, 0, -exemple2_A_1[2][0])\n", "exemple2_A_3 = operationGaussCombinaison(exemple2_A_2, 3, 0, -exemple2_A_2[3][0])\n", "\n", "print(\"Exemple 2\")\n", "print(\"Matrice de départ\")\n", "printM(exemple2)\n", "print(\"Matrice augmentée\")\n", "printM(exemple2_A)\n", "print(\"Échange : L_3<->L_1\")\n", "printM(exemple2_A_0)\n", "print(\"Combinaison : L2<-L2-3L1\")\n", "printM(exemple2_A_1)\n", "print(\"Combinaison : L3<-L2-4L1\")\n", "printM(exemple2_A_2)\n", "print(\"Combinaison : L4<-L4-2L1\")\n", "printM(exemple2_A_3)" ] }, { "cell_type": "code", "execution_count": null, "id": "adb87e91-b5a0-430e-9813-731139c2502f", "metadata": {}, "outputs": [], "source": [ "#Permet de faire apparaitre un '1' (pivot)\n", "exemple2_A_4 = operationGaussDilatation(exemple2_A_3, 1, 1/exemple2_A_3[1][1]) \n", "\n", "#Utilise le pivot pour faire apparaitre des '0'\n", "exemple2_A_5 = operationGaussCombinaison(exemple2_A_4, 2, 1, -exemple2_A_4[2][1])\n", "exemple2_A_6 = operationGaussCombinaison(exemple2_A_5, 3, 1, -exemple2_A_5[3][1])\n", "\n", "\n", "print(\"Dernière itération de l'algorithme\")\n", "printM(exemple2_A_3)\n", "print(\"Faire apparaitre un '1' dans la seconde ligne (pivot)\")\n", "printM(exemple2_A_4)\n", "print(\"Faire apparaitre des '0' dans le reste de la colonne\")\n", "printM(exemple2_A_6)" ] }, { "cell_type": "code", "execution_count": null, "id": "e0f1f3e6-644b-4b34-9198-9f3aad35529a", "metadata": {}, "outputs": [], "source": [ "#Permet de faire apparaitre un '1' (pivot)\n", "exemple2_A_7 = operationGaussDilatation(exemple2_A_6, 2, 1/exemple2_A_6[2][2]) \n", "\n", "#Utilise le pivot pour faire apparaitre des '0'\n", "exemple2_A_8 = operationGaussCombinaison(exemple2_A_7, 3, 2, -exemple2_A_7[3][2])\n", "\n", "\n", "print(\"Dernière itération de l'algorithme\")\n", "printM(exemple2_A_6)\n", "print(\"Faire apparaitre un '1' dans la troisième ligne (pivot)\")\n", "printM(exemple2_A_7)\n", "print(\"Faire apparaitre des '0' dans le reste de la colonne\")\n", "printM(exemple2_A_8)" ] }, { "cell_type": "code", "execution_count": null, "id": "d358a5f8-a598-4957-95af-bb100464280e", "metadata": {}, "outputs": [], "source": [ "exemple2_A_9 = operationGaussDilatation(exemple2_A_8, 3, 1/exemple2_A_8[3][3])\n", "\n", "exemple2_A_10 = operationGaussCombinaison(exemple2_A_9, 2, 3, -exemple2_A_9[2][3])\n", "exemple2_A_11 = operationGaussCombinaison(exemple2_A_10, 1, 3, -exemple2_A_10[1][3])\n", "exemple2_A_12 = operationGaussCombinaison(exemple2_A_11, 0, 3, -exemple2_A_11[0][3])\n", "\n", "exemple2_A_13 = operationGaussCombinaison(exemple2_A_12, 1, 2, -exemple2_A_12[1][2])\n", "exemple2_A_14 = operationGaussCombinaison(exemple2_A_13, 0, 2, -exemple2_A_13[0][2])\n", "\n", "exemple2_A_15 = operationGaussCombinaison(exemple2_A_14, 0, 1, -exemple2_A_14[0][1])\n", "\n", "print(\"Dernière itération de l'algorithme\")\n", "printM(exemple2_A_8)\n", "print(\"Faire apparaitre un '1' dans la dernière ligne (pivot)\")\n", "printM(exemple2_A_9)\n", "print(\"Faire apparaitre des '0' dans le reste des colonnes\")\n", "printM(exemple2_A_15)\n", "print(\"Matrice inverse\")\n", "printM(recupInv(exemple2_A_15))" ] }, { "cell_type": "markdown", "id": "1138de1e-3aab-4625-89f5-bdb93206f58f", "metadata": {}, "source": [ "

L'objectif de la suite de ce TP est d'automatiser ce processus d'inversion.

On dira qu'une matrice $M=(M_{i, j})_{1\\leqslant i\\leqslant n, 1\\leqslant j\\leqslant m}$ est échelonnée si il existe une suite $1\\leqslant i_1Le théorème de Gauss (enfin l'un des nombreux théorèmes de Gauss) indique que par l'utilisation des opérations élémentaires sur les lignes, il est toujours possible d'échelonner une matrice... enfin toujours possible si la matrice est inversible. En particulier, si en appliquant les opérations sur les lignes, il n'est pas possible d'échelonner la matrice, c'est que cette matrice n'est pas inversible

\n", "\n", "

Écrire une fonction echelonnage(M, precision=2) qui prend en paramètre une matrice M et qui renvoie la matrice après échelonnage.
\n", "A propos de la precision : python, en tout cas l'utilisation que nous en faisons ici, ne fait pas de calcul formelle. Tout ce que fait python dans ses calculs sont des approximations numérique. De ce point de vu, il est peut être (très) risqué de réaliser un test du type x==0 qui teste si x est exactement égale à zéro. D'un point de vu 'approximation', il est très rare que x soit exactement égale à zéro, mais elle peut s'en approcher. C'est l'objectif de la variable precision.
\n", "En effet, pour demander si $x=0$, on peut approximativement demander que $|x|<10^{-2}$.
\n", "La variable precision correspond à l'exposant de dix considéré.\n", "

\n", "Si $x=0.005$ alors $|x|<10^{-2}$ est vrai et on peut donc dire $x\\simeq 0$
\n", "Si $x=0.005$ alors $|x|<10^{-3}$ est faux et on peut donc dire $x\\neq 0$
\n", "\n", " \n", "\n", "

\n", "\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase2(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "62ba462d-6e9b-43bd-ba43-491a8b83991a", "metadata": {}, "outputs": [], "source": [ "def echelonnage(M, precision=2) : \n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "1a5df28f-0c0b-4ed6-aefc-98e4afeeeb0f", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "exemple1_E=echelonnage(exemple1_A)\n", "\n", "print(\"Matrice initiale\")\n", "printM(exemple1)\n", "print(\"Matrice augmentée\")\n", "printM(exemple1_A)\n", "print(\"Matrice échelonnée\")\n", "printM(exemple1_E)\n", "\"\"\"\n", "1.0 1.0 0.0 0.5\n", "0.0 1.0 1.0 0.0\n", "\"\"\";" ] }, { "cell_type": "code", "execution_count": null, "id": "748f1c88-31c0-4424-a70e-a99342145407", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "exemple2_E=echelonnage(exemple2_A)\n", "\n", "print(\"Matrice initiale\")\n", "printM(exemple2)\n", "print(\"Matrice augmentée\")\n", "printM(exemple2_A)\n", "print(\"Matrice échelonnée\")\n", "printM(exemple2_E)\n", "\"\"\"\n", " 1.0 0.5 0.25 0.25 0.25 0.0 0.0 0.0\n", "-0.0 1.0 -2.5 -6.5 1.5 -2.0 -0.0 -0.0\n", " 0.0 0.0 1.0 1.8 -0.4 0.5 0.1 0.0\n", " 0.0 0.0 0.0 1.0 -0.5 0.5 -0.5 0.5\n", "\"\"\";" ] }, { "cell_type": "markdown", "id": "7c51d0d2-7cc7-489a-b545-82aeaeae3522", "metadata": {}, "source": [ "

Une fois que la matrice est échelonnée (si c'est possible), un oeil aguérie pourra faire apparaitre la matrice identité à gauche. Ayez un oeil aguéri (voir même les deux) et instanciez la fonction algoGauss(M, precision=2) qui prend ne paramètre une matrice M (la variable precision a le même sens que la fonction précédente) et qui renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.

\n", "\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase2(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "34a97c22-b467-421f-9c1d-7c0b7074ba4e", "metadata": {}, "outputs": [], "source": [ "def algoGauss(M, precision=2) : \n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "4b6570c9-cc02-4cf1-932b-f250de9f61f4", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "print(\"Matrice\")\n", "printM(exemple2)\n", "print(\"Fin de l'algorithme de Gauss\")\n", "printM(algoGauss(exemple2))\n", "\"\"\"\n", "1.0 0.0 0.0 0.0 0.5 -0.15 0.25 -0.4\n", "0.0 1.0 0.0 0.0 -0.5 0.25 -0.75 1.0\n", "0.0 0.0 1.0 0.0 0.5 -0.4 1.0 -0.9\n", "0.0 0.0 0.0 1.0 -0.5 0.5 -0.5 0.5\n", "\"\"\";" ] }, { "cell_type": "markdown", "id": "a5ef80e7-3b98-4b40-809c-f6b8153b931c", "metadata": {}, "source": [ "

Assemblez les différentes fonctionnalités précédente pour écrire la fonction invMat(M, precision=2) qui prend en paramètre une matrice et qui renvoie la matrice inverse sir c'est possible ; si ce n'est pas possible la fonction renvoie None.

\n", "\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase2(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "365b207e-8073-4e10-819a-78e37c6c9868", "metadata": {}, "outputs": [], "source": [ "def invMat(M, precision=2) : \n", " return None" ] }, { "cell_type": "code", "execution_count": null, "id": "e2c06a51-5034-43d1-a7e3-7ab9afaaa3e9", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "print(\"L'inverse de la matrice\")\n", "printM(exemple2)\n", "print(\"est\")\n", "printM(invMat(exemple2))\n", "\"\"\"\n", " 0.5 -0.15 0.25 -0.4\n", "-0.5 0.25 -0.75 1.0\n", " 0.5 0.4 1.0 -0.9\n", "-0.5 0.5 -0.5 0.5\n", "\"\"\";" ] }, { "cell_type": "markdown", "id": "05d7f6d1-286d-4bdd-8272-34b1e1955c52", "metadata": {}, "source": [ "
\n", " Partie 2 : L'algorithme du simplexe\n", "
\n", "\n", "

\n", "

\n", " Menu de navigation (cliquez pour dérouler)\n", " \n", "
\n", "

" ] }, { "cell_type": "markdown", "id": "c76dd9d4-91ef-4a85-b80a-91888708c713", "metadata": {}, "source": [ "

Nous travaillons avec des problèmes linéaires. Pour plus de détails théorique, consultez ataraXy ici

\n", "

Un problème linéaire sera considéré comme une structure de donnée, c'est à dire un dictionnaire, avec le champs suivants : \n", "

\n", " Il y a quelques précausion à prendre. Par exemple le nombre de ligne de la matrice 'A' doit correspondre à la taille de la liste 'SYMB' etc...\n", "

" ] }, { "cell_type": "code", "execution_count": null, "id": "607e6e3a-e862-4567-ac8e-e19e6ff808c5", "metadata": {}, "outputs": [], "source": [ "PL1 = {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}\n", "\n", "PL2 = {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [-1, -2]\n", " ],\n", " 'SYMB':['<', '>'],\n", " 'MINouMAX':'Min',\n", " 'B':[11, -10],\n", " 'C':[-1, -1]\n", "}" ] }, { "cell_type": "markdown", "id": "2ff1fb9d-c8d8-44c5-b26a-7ce3f7775c6a", "metadata": {}, "source": [ "

La fonction suivante affiche élégament un problème linéaire avec une précision de celle spécifié dans le second paramètre optionnelle. Si le problème est mal saisie alors la fonction renvoie la chaine vide. Vous pourrez la tester dans la case suivante.

" ] }, { "cell_type": "code", "execution_count": null, "id": "dbaebaf0-ae86-4582-b9fc-27210b1e564b", "metadata": {}, "outputs": [], "source": [ "def printPL(PL, precision=2) : \n", " try :#test sur la structure informatique d'un problème linéaire\n", " A=PL['A']\n", " B=PL['B']\n", " C=PL['C']\n", " V=PL['VAR']\n", " S=PL['SYMB']\n", " MM=PL['MINouMAX']\n", " nb_variable = len(V)\n", " nb_contrainte=len(A)\n", " for i in range(nb_contrainte) : \n", " if(len(A[i])!=nb_variable) : return \"\"\n", " if(len(S)!=nb_contrainte) : return \"\"\n", " if(len(B)!=nb_contrainte) : return \"\"\n", " if(len(C)!=nb_variable) : return \"\"\n", " except : return \"\"\n", "\n", " tex=r\"\\left\\{\\begin{array}{*{\"+str(nb_variable)+\"}{cr}cl}\"\n", " for i in range(nb_contrainte) :#la ligne i correspond à la contrainte i\n", " premier_passage=False #Petite astuce pour ne pas afficher de '+' pour le premier terme (dans le cas où il est positif)\n", " for j in range(nb_variable) : #la colone j correspond à la variable j\n", " a=A[i][j] # on récupère le coefficient\n", " if(a!=0) :\n", " if(a>0 and premier_passage) : tex+='+' #On affiche le + (si ce n'est pas le premier terme de la ligne)\n", " premier_passage=True\n", " if(a<0) : tex+='-'\n", " tex+=' & '\n", " a=abs(a)#Le signe étant géré dans les lignes précédente, on prend la valeur absolue du coef\n", " if(a!=1) : tex+=str(abs(round(a, precision))) #On affiche le coefficient avec un nombre de décimale spécifié en paramètre\n", " tex+=V[j]\n", " else : tex+=' & '\n", " tex+=' & '\n", " #Gestion du symbole\n", " if(S[i]=='<') : tex+=r'\\leqslant'\n", " elif(S[i]=='>') : tex+=r'\\geqslant'\n", " else : tex+=S[i]\n", " tex+=str(round(B[i], precision)) #Coefficient\n", " tex+=r'\\\\' #saut de ligne\n", " #affichage du min ou du max\n", " tex+=r'\\hline '+MM+'('\n", " premier_passage=False\n", " for j in range(nb_variable) :\n", " a=C[j]\n", " if(a!=0) :\n", " if(a>0 and premier_passage) : tex+='+'\n", " premier_passage=True\n", " if(a<0) : tex+='-'\n", " tex+=' & '\n", " a=abs(a)\n", " if(a!=1) : tex+=str(abs(round(a, precision)))\n", " tex+=V[j]\n", " else : tex+=' & '\n", " tex+=' & '\n", " tex+=')'\n", " tex+=r'\\end{array}\\right.'\n", " \n", " display(Math(tex))" ] }, { "cell_type": "code", "execution_count": null, "id": "dad3616a-d21b-4ae7-9bce-603879456619", "metadata": {}, "outputs": [], "source": [ "#Tests\n", "\n", "printPL(PL1)\n", "printPL(PL2)" ] }, { "cell_type": "markdown", "id": "4b04a604-5d2e-48b0-82b1-05882bbcb8b5", "metadata": {}, "source": [ "

On renvoie au cours, pour comprendre l'algorithme du simplexe permettant de résoude les problèmes linéaires. En particulier, nous représentons un problème linéaire mis sous forme standard dans un tableau.\n", "
\n", " Dans ce TP, un tableau sera une structure de donnée (un dictionnaire en python), avec les champs suivant : \n", "

\n", " Voici un exemple : \n", "

" ] }, { "cell_type": "code", "execution_count": null, "id": "9542fffb-03f4-4e68-b8f6-a25b2b414afa", "metadata": {}, "outputs": [], "source": [ "TAB1 = {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}" ] }, { "cell_type": "markdown", "id": "777d0799-3b4d-4277-b6af-e1a795d22df3", "metadata": {}, "source": [ "

La fonction suivante affiche le tableau du simplexe.

" ] }, { "cell_type": "code", "execution_count": null, "id": "ae4c30ec-243d-4c0e-a685-7de06c41887d", "metadata": {}, "outputs": [], "source": [ "def printTAB(TAB, precision=2) : \n", " try :\n", " var_e=TAB['VAR_E']\n", " var_s=[var_e[i] for i in TAB['VAR_S']]\n", " M=TAB['MAT']\n", " nb_contrainte = len(var_s)\n", " nb_variable = len(var_e)\n", " for i in range(nb_contrainte+1) : \n", " if(len(M[i])!=nb_variable+1) : return \"\"\n", " except : return \"\"\n", "\n", " tex=r'\\begin{array}{c|*{'+str(nb_variable)+'}{c}|c}'\n", " for j in range(nb_variable) : tex+=' & '+var_e[j]\n", " tex+=r'\\\\\\hline '\n", " for i in range(nb_contrainte) : \n", " tex+=var_s[i]\n", " for j in range(nb_variable+1) : tex+=' & '+str(round(M[i][j], precision))\n", " tex+=r'\\\\'\n", " tex+=r'\\hline '\n", "\n", " tex+='Obj'\n", " for j in range(nb_variable+1) : tex+=' & '+str(round(M[nb_contrainte][j], precision))\n", " tex+=r'\\end{array}'\n", " display(Math(tex))" ] }, { "cell_type": "code", "execution_count": null, "id": "6043f8a2-ae48-4611-91b2-78b4fbb78a52", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "printTAB(TAB1)" ] }, { "cell_type": "markdown", "id": "ca8e5f45-afaf-43c6-87b7-354d3abec81c", "metadata": {}, "source": [ "

Écrire la fonction init_simplexe(PL) qui prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale. En particulier on prendra garde aux critères qui font d'un problème, un problème sous forme standard.

\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase2(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "25f08d4c-f7bf-4b3a-9ad6-58736f9cd702", "metadata": {}, "outputs": [], "source": [ "def init_simplexe(PL) : \n", " TAB = {'VAR_E':[], 'VAR_S':[], 'MAT':[]}\n", " return TAB" ] }, { "cell_type": "code", "execution_count": null, "id": "8aa2a816-b1c7-4d4f-b063-ff73d5f518ac", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "print(\"Premier problème linéaire\")\n", "printPL(PL1)\n", "printTAB(init_simplexe(PL1))\n", "\"\"\"\n", " x y e1 e2 \n", "e1 2 1 1 0 11\n", "e2 1 2 0 1 10\n", "Obj 1 1 0 0 0\n", "\"\"\";\n", "\n", "print(\"Second problème linéaire\")\n", "printPL(PL2)\n", "printTAB(init_simplexe(PL2))\n", "\"\"\"\n", " x y e1 e2 \n", "e1 2 1 1 0 11\n", "e2 1 2 0 1 10\n", "Obj 1 1 0 0 0\n", "\"\"\";" ] }, { "cell_type": "markdown", "id": "c2c2f312-8779-45db-a8be-b97cf9a722e1", "metadata": {}, "source": [ "

En suivant l'algorithme du simplexe, écrire la fonction cherchePivot(TAB) qui prend en paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si, en suivant l'algorithme du simplexe, il n'est pas possible de déterminer un pivot alors la fonction renvoie -1, -1.

\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase2(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "8d7d763c-32e6-4c38-a043-c1540e8a0751", "metadata": {}, "outputs": [], "source": [ "def cherchePivot(TAB) : \n", " return -1, -1" ] }, { "cell_type": "code", "execution_count": null, "id": "feb9bec4-6d5d-4ad9-b1c0-da77b137192d", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "TAB2=init_simplexe(PL2)\n", "printTAB(TAB2)\n", "print(\"Pivot :\", cherchePivot(TAB2)) #(0, 0)" ] }, { "cell_type": "markdown", "id": "1bd8a452-863e-4950-9ee7-8de870fea2c7", "metadata": {}, "source": [ "

En reprennant le principe de l'algorithme du simplexe, nous pouvons réaliser une itération qui est réalisé dans la case suivante et qui abouti sur le tableau\n", "$$\\displaystyle \\begin{array}{c|*{4}{c}|c} & x & y & e_{1} & e_{2}\\\\\\hline e_{1} & 1.0 & 0.5 & 0.5 & 0.0 & 5.5\\\\e_{2} & 0.0 & 1.5 & -0.5 & 1.0 & 4.5\\\\\\hline Obj & 0.0 & 0.5 & -0.5 & 0.0 & -5.5\\end{array}.\r\n", "$$ \n", "

" ] }, { "cell_type": "code", "execution_count": null, "id": "71a88fd8-3974-4990-929d-30487f9dbfcc", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "TAB2_0 = init_simplexe(PL2)\n", "M = TAB2_0['MAT']\n", "i, j = cherchePivot(TAB2_0)\n", "\n", "printTAB(TAB2_0)\n", "print(\"Pivot :\", cherchePivot(TAB2_0))\n", "\n", "M = operationGaussDilatation(M, i, 1/M[i][j])\n", "TAB2_1={'VAR_E':TAB2_0['VAR_E'], 'VAR_S':TAB2_0['VAR_S'], 'MAT':M}\n", "printTAB(TAB2_1)\n", "\n", "M = operationGaussCombinaison(M, 1, i, -M[1][j])\n", "TAB2_2={'VAR_E':TAB2_0['VAR_E'], 'VAR_S':TAB2_0['VAR_S'], 'MAT':M}\n", "printTAB(TAB2_2)\n", "\n", "M = operationGaussCombinaison(M, 2, i, -M[2][j])\n", "TAB2_3={'VAR_E':TAB2_0['VAR_E'], 'VAR_S':TAB2_0['VAR_S'], 'MAT':M}\n", "printTAB(TAB2_3)" ] }, { "cell_type": "markdown", "id": "31f2ab41-df30-4710-aa08-266a2975356d", "metadata": {}, "source": [ "

En adaptant ce code mais aussi en prennant garde à mettre à jour les variable sortante écrivez la fonction unTour(TAB, I, J) qui renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.

\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase2(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "55d0dfc0-c674-4e5c-b9f1-3e541e6393de", "metadata": {}, "outputs": [], "source": [ "def unTour(TAB, I, J) : \n", " return TAB" ] }, { "cell_type": "code", "execution_count": null, "id": "40faafec-5c82-47b9-a1ff-1980185a8b12", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "I, J = cherchePivot(TAB2)\n", "TAB2_0 = unTour(TAB2, I, J)\n", "\n", "print(\"Initialisation du problème\")\n", "printTAB(TAB2)\n", "print(\"Après un tour de simplexe\")\n", "printTAB(TAB2_0)\n", "\"\"\"\n", " x y e1 e2\n", "x 1.0 0.5 0.5 0.0 11\n", "y 0.0 1.5 -0.5 1.0 4.5\n", "Obj 0.0 0.5 -0.5 0.0 -5.5\n", "\"\"\"" ] }, { "cell_type": "markdown", "id": "a9666fc0-3fad-42ed-a5c6-298729c3f1a5", "metadata": {}, "source": [ "

En combinant les fonctions précédentes, écrire la fonction algoSimplexe(TAB) qui applique l'algorithme du simplexe sur un tableau initial.

\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase2(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "a69f7a6f-ba00-4dcc-9a9b-ec77bb6f5a05", "metadata": {}, "outputs": [], "source": [ "def algoSimplexe(TAB) :\n", " return TAB" ] }, { "cell_type": "code", "execution_count": null, "id": "7cf0f6ac-6e88-42d1-9806-d025e1c7a0d3", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "print(\"Problème linéaire\")\n", "printPL(PL2)\n", "\n", "print(\"Initialisation\")\n", "TAB2 = init_simplexe(PL2)\n", "printTAB(TAB2)\n", "\n", "print(\"A la fin de l'algorithme du simplexe\")\n", "TAB2_fin = algoSimplexe(TAB2)\n", "printTAB(TAB2_fin)\n", "\"\"\"\n", " x y e1 e2\n", "x 1.0 0.0 0.67 -0.33 4.0\n", "y 0.0 1.0 -0.33 0.67 3.0\n", "Obj 0.0 0.0 -0.33 -0.33 -7.0\n", "\"\"\";" ] }, { "cell_type": "markdown", "id": "717ec8f3-4dde-4509-96bf-6b56d85b5e58", "metadata": {}, "source": [ "

Écrire la fonction lectureTABSimplexe(TAB, PL) qui prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.

\n", "\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase2(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "ae455cbc-9b71-47a4-9b1e-fae7bcb3fd8f", "metadata": {}, "outputs": [], "source": [ "def lectureTABSimplexe(TAB, PL) : \n", " solution={}\n", " return solution" ] }, { "cell_type": "code", "execution_count": null, "id": "1a93e1ac-1cae-4e6c-8a23-1d2e8967800e", "metadata": {}, "outputs": [], "source": [ "#Test \n", "\n", "print(\"Problème linéaire\")\n", "printPL(PL2)\n", "\n", "print(\"Initialisation\")\n", "printTAB(TAB2)\n", "\n", "print(\"A la fin de l'algorithme du simplexe\")\n", "TAB2_fin = algoSimplexe(TAB2)\n", "printTAB(TAB2_fin)\n", "\n", "print(\"Solution :\", lectureTABSimplexe(TAB2_fin, PL2))#{'x': 4.0, 'y': 3.0}" ] }, { "cell_type": "code", "execution_count": null, "id": "6f27aa7f-2e65-4b63-a112-eb7ab3594357", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "PL={\n", " 'VAR':[\"x\", \"y\", \"z\"],\n", " 'A':[\n", " [0, 1, -1],\n", " [1, -1, 1],\n", " [-1, 0, 1],\n", " [1, 0, 1]\n", " ],\n", " 'SYMB':['<', '<', '<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10, 9, 8],\n", " 'C':[1, 1, 1]\n", "}\n", "\n", "printPL(PL)\n", "print(\"Solution :\", lectureTABSimplexe(algoSimplexe(init_simplexe(PL)), PL))#{'x': 0, 'y': 19.0, 'z': 8.0}" ] }, { "cell_type": "markdown", "id": "888c79bd-23ae-4e47-8962-6b1db11185ca", "metadata": {}, "source": [ "
\n", " Partie 3 : L'algorithme des deux phases\n", "
\n", "\n", "

\n", "

\n", " Menu de navigation (cliquez pour dérouler)\n", " \n", "
\n", "

" ] }, { "cell_type": "markdown", "id": "8eeb5260-2826-4050-98b9-106877a97a4a", "metadata": {}, "source": [ "

Nous reprennons exactement les même structures que précédement, sauf que la structure TAB des tableaux de simplexe, a un champ supplémentaire : 'VAR_A' qui est la liste des indices des variables artificielles.

\n", "\n", "

Écrire la fonction init_phase1(PL) qui renvoie le tableau d'initialisation de la première phase. On prendra en particulier bien garde à tous les éléments de l'initialisation à prendre en compte.

\n", "\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase2(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "846aa9ed-0a6f-4f36-a806-f870bf655df2", "metadata": {}, "outputs": [], "source": [ "def init_phase1(PL) : \n", " TAB = {'VAR_E':[], 'VAR_S':[], 'VAR_A':[], 'MAT':[]}\n", " return TAB" ] }, { "cell_type": "code", "execution_count": null, "id": "d76862c5-8ac2-4506-9ef5-4485e263c426", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "PL3 = {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [1, 2],\n", " [-1, -1],\n", " [3, 1]\n", " ],\n", " 'SYMB':['<', '<', '='],\n", " 'MINouMAX':'Max',\n", " 'B':[4, -1, 6],\n", " 'C':[2, 1]\n", "}\n", "\n", "TAB3_init1 = init_phase1(PL3)\n", "TAB3_fin1 = algoSimplexe(TAB3_init1)\n", "TAB3_fin1['VAR_A'] = TAB3_init1['VAR_A']\n", "\n", "print(\"Problème initiale\")\n", "printPL(PL3)\n", "\n", "print(\"Initialisation de la phase 1\")\n", "printTAB(TAB3_init1)\n", "\n", "print(\"Fin de la phase 1\")\n", "printTAB(TAB3_fin1)\n", "\n", "\"\"\"\n", " x y e1 e2 a1 a2\n", "e1 0.0 1.67 1.0 0.0 0.0 -0.33 2.0\n", "x 1.0 0.33 0.0 0.0 0.0 0.33 2.0\n", "e2 0.0 -0.67 0.0 1.0 -1.0 0.33 1.0\n", "Obj 0.0 0.0 0.0 0.0 -1.0 -1.0 0.0\n", "\"\"\";" ] }, { "cell_type": "markdown", "id": "d4197835-4821-407d-b6b0-f3902e17a9d8", "metadata": {}, "source": [ "

Écrire la fonction init_phase2(TAB, PL, precision=2) qui renvoie le tableau d'initialisation de la seconde phase. La variable TAB correspond au tableau du simplexe à la fin de la première phase, la variable PL correspond au problème initiale quand à la variable precision elle correspond à la précision des valeurs souhaitée

\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase2(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "3526a7f0-7664-46de-aba2-6d0f2913651d", "metadata": {}, "outputs": [], "source": [ "def init_phase2(TAB, PL, precision=2) :\n", " newTAB={'VAR_E':[], 'VAR_S':[], 'MAT':[]}\n", " return newTAB" ] }, { "cell_type": "code", "execution_count": null, "id": "5f438566-c7b2-4a3e-85cb-fef5d732e516", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "TAB3_init2=init_phase2(TAB3_fin1, PL3)\n", "TAB3_fin2=algoSimplexe(TAB3_init2)\n", "\n", "print(\"Problème initiale\")\n", "printPL(PL3)\n", "\n", "print(\"Initialisation de la phase 1\")\n", "printTAB(TAB3_init1)\n", "\n", "print(\"Fin de la phase 1\")\n", "printTAB(TAB3_fin1)\n", "\n", "print(\"initialisation de la phase 2\")\n", "printTAB(TAB3_init2)\n", "\n", "print(\"Fin de la phase 2\")\n", "printTAB(TAB3_fin2)\n", "\n", "print(\"Solution :\", lectureTABSimplexe(TAB3_fin2, PL3))#{'x': 1.5999999999999999, 'y': 1.2000000000000002}" ] }, { "cell_type": "markdown", "id": "0894d471-cb88-4b45-820a-aa1babe36566", "metadata": {}, "source": [ "

Écrire la procédure algo2phases(PL, precision=2) qui affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.

\n", "\n", "\n", "
\n", " Aide Cliquez pour dérouler\n", "
    \n", "
  1. \n", "
    Les développements de la partie 1 : L'algorithme de Gauss
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    printM(M, pecision=2)Cette procédure affiche, en $\\LaTeX$, la matrice passée en paramètre. En cas d'erreur dans la saisie, cette procédure renvoie la chaine de caractère \"\". Le paramètre optionnelle precision permet d'indiquer combien de décimale nous souhaitons afficher au maximum. Par défaut, il vaut 2
    matriceAugmentee(M)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre. En cas de problème de dimension la fonction renvoie None.
    operationGaussEchange(M, I, J)Cette fonction renvoie la matrice M où les lignes I et J ont été échangée.
    operationGaussDilatation(M, I, coef)Cette fonction renvoie la matrice M où la ligne I est multipliée par un coefficient coef.
    operationGaussCombinaison(M, I, J, coef)Cette fonction renvoie la matrice M où on a ajouté à la ligne I la ligne J multipliée par coef.
    recupInv(MAugmentee)Cette fonction renvoie l'inverse de la matrice M à partir de la matrice augmenté passé en paramètre. La fonction renvoie None si ce n'est pas possible.
    echelonnage(M, precision=2)Cette fonction renvoie la matrice passé en paramètre après échelonnage. La variable precision permet de rafiner sur les approximations numérique.
    algoGauss(M, precision=2)Cette fonction renvoie la matrice augmentée de la matrice passée en paramètre et renvoie la matrice augmentée après des opérations sur les lignes et permettant de faire apparaitre la matrice identité à gauche. Si ce n'est pas possible la fonction renvoie None.
    invMat(M, precision=2)Cette fonction renvoie l'inverse de la matrice passé en paramètre. Si ce n'est pas possible la fonction renvoie None.
    \n", "
    \n", "
    2. \n", "
  2. \n", "
    Les développements de la partie 2 : L'algorithme du simplexe
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [2, 1],\n", " [1, 2]\n", " ],\n", " 'SYMB':['<', '<'],\n", " 'MINouMAX':'Max',\n", " 'B':[11, 10],\n", " 'C':[1, 1]\n", "}Structure d'un problème linéaire dans ce TP
    printPL(PL, precision=2)Affiche un problème linéaire avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    {\n", " 'VAR_E':[\"x\", \"y\", \"e_{1}\", \"e_{2}\"],\n", " 'VAR_S':[2, 3],\n", " 'MAT':[\n", " [2, 1, 1, 0, 11],\n", " [1, 2, 0, 1, 10],\n", " [1, 1, 0, 0, 0]\n", " ]\n", "}Structure d'un tableau de simplexe dans ce TP
    printTAB(TAB, precision=2)Affiche un tableau de simplexe avec la precision spécifié. Si le problème est mal saisi, la fonction renvoie la chaine vide.
    init_simplexe(PL)Cette fonction prend en a paramètre un problème linéaire et renvoie le tableau de simplexe initiale
    cherchePivot(TAB)Cette fonction prend en a paramètre un tableau de simplexe et renvoie le tuple i, j correspondant à la ligne et la colonne du pivot. Si ce n'est pas possible alors la fonction renvoie -1, -1.
    unTour(TAB, I, J)Cette fonction renvoie le tableau de simplexe passé en paramètre après une itération autour du pivot en I, J.
    algoSimplexe(TAB)Cette fonction renvoie le tableau de simplexe passé en paramètre après l'application de l'algorithme du simplexe.
    lectureTABSimplexe(TAB, PL)Cette fonction prend en paramètre un tableau de simplexe et le problème initiale et renvoie le dictionnaire où les étiquettes sont les variables initiale du problème et les valeurs, les valeurs par lecture du tableau du simplexe.
    \n", "
    \n", "
    3. \n", "
  3. \n", "
    Les développements de la partie 3 : L'algorithme des deux phases
    \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
    init_phase1(PL)Cette fonction renvoie l'initialisation de la première phase.
    init_phase1(TAB, PL, precision=2)Cette fonction renvoie l'initialisation de la seconde phase à partir du problème initiale PL et du tableau TAB de la fin de la première phase.
    algo2phase2(PL, precision=2)Cett procédure affiche la première phase et sa conclusion et la seconde phase et sa conclusion, si c'est possible.
    \n", "
    \n", "
    4. \n", "
\n", "
" ] }, { "cell_type": "code", "execution_count": null, "id": "912cee41-fc22-441e-b278-cc30ceeb25cb", "metadata": {}, "outputs": [], "source": [ "def algo2phases(PL, precision=2) : \n", " return" ] }, { "cell_type": "code", "execution_count": null, "id": "c08ad5a0-b78e-4c24-8599-13e037f8010e", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "PL3 = {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [1, 2],\n", " [-1, -1],\n", " [3, 1]\n", " ],\n", " 'SYMB':['<', '<', '='],\n", " 'MINouMAX':'Max',\n", " 'B':[4, -1, 6],\n", " 'C':[2, 1]\n", "}\n", "\n", "algo2phases(PL3)#{'x': 1.5999999999999999, 'y': 1.2000000000000002}" ] }, { "cell_type": "code", "execution_count": null, "id": "c3c04eec-5387-4d88-b8a6-e8ef00c84789", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "PL4 = {\n", " 'VAR':[\"x\", \"y\", \"z\"],\n", " 'A':[\n", " [1, 1, 0],\n", " [-1, 0, -1],\n", " [0, 1, 1]\n", " ],\n", " 'SYMB':['>', '<', '='],\n", " 'MINouMAX':'Max',\n", " 'B':[4, -1, 6],\n", " 'C':[1, 1, 1]\n", "}\n", "\n", "algo2phases(PL4)#{'x': 1.0, 'y': 6.0, 'z': 0}" ] }, { "cell_type": "code", "execution_count": null, "id": "23662eaf-1f97-4db7-99ca-4d8ce0120374", "metadata": {}, "outputs": [], "source": [ "#Test\n", "\n", "PL5 = {\n", " 'VAR':[\"x\", \"y\"],\n", " 'A':[\n", " [9, 7],\n", " [8, 4],\n", " [1, 9]\n", " ],\n", " 'SYMB':['<', '>', '='],\n", " 'MINouMAX':'Max',\n", " 'B':[9, 7, 2],\n", " 'C':[5, 2]\n", "}\n", "\n", "algo2phases(PL5)#{'x': 0.9054054054054055, 'y': 0.12162162162162159}" ] }, { "cell_type": "code", "execution_count": null, "id": "b7917f5e-12a0-4780-ae43-985f0050e34b", "metadata": {}, "outputs": [], "source": [ "#Test\n", "PL6 = {\n", " 'VAR':[\"x_1\", \"x_2\", \"x_3\", \"x_4\", \"x_5\"],\n", " 'A':[\n", " [1, 1, 9, 6, 9],\n", " [0, 7, 8, 5, 5],\n", " [3, 3, 8, 3, 5]\n", " ],\n", " 'SYMB':['<', '=', '>'],\n", " 'MINouMAX':'Min',\n", " 'B':[6, 9, 2],\n", " 'C':[8, 3, 3, 3, 9]\n", "}\n", "\n", "algo2phases(PL6)#{'x_1': 0, 'x_2': 0.6, 'x_3': 0.6, 'x_4': 0, 'x_5': 0}" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.1" } }, "nbformat": 4, "nbformat_minor": 5 }