{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "$$\n", "\\def\\CC{\\bf C}\n", "\\def\\QQ{\\bf Q}\n", "\\def\\RR{\\bf R}\n", "\\def\\ZZ{\\bf Z}\n", "\\def\\NN{\\bf N}\n", "$$\n", "# Option Alg\u00e8bre et Calcul Formel de l'Agr\u00e9gation de Math\u00e9matiques: Programmation lin\u00e9aire\n", "\n", "Ce support de cours est principalement inspir\u00e9 de l'excellent livre \u00abLinear Programming\u00bb de Va\u0161ek Chv\u00e1tal \\[Chvatal\\_LP\\]\\_. C'est un extrait mis \u00e0 jour d'un [cours de Recherche Op\u00e9rationnelle et Optimisation Discr\u00e8te](http://Nicolas.Thiery.name/RO/) donn\u00e9 dans le cadre du M1 de Math\u00e9matiques et Ing\u00e9nierie Math\u00e9matique de l'Universit\u00e9 Lyon I en 2001-2003. Dans le cadre de la pr\u00e9paration \u00e0 l'agr\u00e9gation, l'objectif est de donner un aper\u00e7u rapide de la programmation lin\u00e9aire et de ses applications en combinatoire polyh\u00e9drale.\n", "\n", "## Programmation lin\u00e9aire\n", "\n", "### Qu'est-ce que la programmation lin\u00e9aire?\n", "\n", "#### Exemple: le probl\u00e8me du r\u00e9gime de Pauline\n", "\n", "**Exemple (\\[Chvatal\\_LP\\]\\_ p. 3)**\n", "\n", "Besoins journaliers:\n", "\n", "> - \u00c9nergie: 2000 kcal\n", "> - Prot\u00e9ines: 55g\n", "> - Calcium: 800 mg\n", "\n", "Nourriture disponible:\n", "\n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", ">
Portion\u00c9nergie (kcal)Prot\u00e9ines (g)Calcium (mg)Prix/portion
C\u00e9r\u00e9ales28g110423
Poulet100g205321224
Oeufs2 gros160135413
Lait entier237cc16082859
Tarte170g42042220
Porc et haricots260g260148019
\n", ">\n", "Quels menu pour Pauline?\n", "\n", "Contraintes:\n", "\n", "> - C\u00e9r\u00e9ales: au plus 4 portions par jour\n", "> - Poulet: au plus 3 portions par jour\n", "> - Oeufs: au plus 2 portions par jour\n", "> - Lait: au plus 8 portions par jour\n", "> - Tarte: au plus 2 portions par jour\n", "> - Porc\u00a0et\u00a0haricots: au plus 2 portions par jour\n", "\n", "1. Pauline peut-elle trouver une solution ?\n", "2. Comment formaliser le probl\u00e8me ? (mod\u00e9lisation)\n", "3. Qu'est-ce qui fait la sp\u00e9cificit\u00e9 du probl\u00e8me ?\n", "4. Savez-vous r\u00e9soudre des probl\u00e8mes similaires ?\n", "\n", "**Mod\u00e9lisation et r\u00e9solution avec Sage**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "p = MixedIntegerLinearProgram(maximization=False)\n", "cereales = p['cereales']\n", "poulet = p['poulet']\n", "oeufs = p['oeufs']\n", "lait = p['lait']\n", "tarte = p['tarte']\n", "porc = p['porc']" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "p.add_constraint( cereales <= 4)\n", "p.add_constraint( poulet <= 3)\n", "p.add_constraint( oeufs <= 2)\n", "p.add_constraint( lait <= 8)\n", "p.add_constraint( tarte <= 2)\n", "p.add_constraint( porc <= 2)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "p.add_constraint( 110*cereales + 205*poulet + 160*oeufs + 160*lait + 420*tarte + 260*porc >= 2000)\n", "p.add_constraint( 4*cereales + 32*poulet + 13*oeufs + 8*lait + 4*tarte + 14*porc >= 55)\n", "p.add_constraint( 2*cereales + 12*poulet + 54*oeufs + 285*lait + 22*tarte + 80*porc >= 800)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "p.set_objective( 3*cereales + 24*poulet + 13*oeufs + 9*lait + 20*tarte + 19*porc)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "92.5" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p.solve()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4.0" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p.get_values(cereales)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(4.0, 0.0, 0.0, 4.5, 2.0, 0.0)\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p.get_values(cereales), p.get_values(poulet), p.get_values(oeufs), p.get_values(lait), p.get_values(tarte), p.get_values(porc)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Forme standard d'un programme lin\u00e9aire\n", "\n", "**Exemples (\\[Chvatal\\_LP\\]\\_ p. 5)**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "Maximiser: 5*x1 + 4*x2 + 3*x3\n", "\n", "Sous les contraintes: 2*x1 + 3*x2 + x3 <= 5\n", " 4*x1 + x2 + 2*x3 <= 11\n", " 3*x1 + 4*x2 + 2*x3 <= 8\n", "\n", " x1, x2, x3 >= 0" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "Minimiser: 3*x1 - x2\n", "\n", "Sous les contraintes: - x1 + 6*x2 - x3 + x4 >= -3\n", " 7*x2 + 2*x4 = 5\n", " x1 + x2 + x3 = 1\n", " x3 + x4 <= 2\n", "\n", " x2, x3 >= 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**D\u00e9finitions**\n", "\n", "Programme lin\u00e9aire sous *forme standard:*\n", "\n", "Maximiser:\n", "\n", "$$z:=\\sum_{j=1}^nc_jx_j$$\n", "\n", "Sous les contraintes:\n", "\n", "$$\\sum_{j=1}^na_{ij}x_j\\leq b_i\\text{, pour $i=1,\\ldots,m$ }$$\n", "\n", "$$x_j\\geq0 \\text{, pour $j=1,\\ldots,n$}$$\n", "\n", "Un choix des variables $(x_1,\\ldots,x_n)$ est appel\u00e9 *solution* du probl\u00e8me.\n", "\n", "Une solution est *faisable* si elle v\u00e9rifie les contraintes.\n", "\n", "$z$ est appel\u00e9 *fonction objective*. \u00c0 chaque solution elle associe une valeur.\n", "\n", "Une solution est *optimale* si elle est faisable et maximize la fonction objective.\n", "\n", "**Exercice**\n", "\n", "Peut-on mettre sous forme standard les exemples pr\u00e9c\u00e9dents ?\n", "\n", "#### Existence de solutions optimales ?\n", "\n", "**Exercice (\\[Chvatal\\_LP\\]\\_ p. 7)**\n", "\n", "On consid\u00e8re les quatre programmes lin\u00e9aires standard suivants, \u00e9crits avec la syntaxe du syst\u00e8me de calcul formel `MuPAD` :\n", "\n", "D\u00e9terminer pour ces quatre probl\u00e8mes les solutions faisables, les solutions optimales. Illustrer sur un dessin au tableau.\n", "\n", "**Solution**\n", "\n", "- Premier cas: une solution optimale unique;\n", "- Deuxi\u00e8me cas: pas de solution faisable;\n", "- Troisi\u00e8me cas: pas de solution optimale: on peut faire tendre la fonction objective vers l'infini avec des solutions faisables;\n", "- Quatri\u00e8me cas: une infinit\u00e9 de solutions optimales.\n", "\n", "### Algorithme du simplexe\n", "\n", "#### Mini rappel d'alg\u00e8bre affine\n", "\n", "**Probl\u00e8me**\n", "\n", "Consid\u00e9rons le syst\u00e8me suivant:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "s1 + 2*x1 + 3*x2 + x3 = 5\n", " s2 + 4*x1 + x2 + 2*x3 = 11\n", " s3 + 3*x1 + 4*x2 + 2*x3 = 8" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Que peut-on dire dessus?\n", "\n", "**Solution**\n", "\n", "C'est un syst\u00e8me *affine* \u00e0 6 inconnues et 3 \u00e9quations.\n", "\n", "L'ensemble des solutions est un sous espace affine de dimension $3$ de $\\mathbb{R}^3$, que l'on peut d\u00e9crire en prenant comme param\u00e8tres $x_1$, $x_2$ et $x_3$.\n", "\n", "En effet, vu la forme \u00e9chelon r\u00e9duite, $s_1$, $s_2$ et $s_3$ s'expriment en fonction de $x_1$, $x_2$ et $x_3$.\n", "\n", "En particulier, on lit imm\u00e9diatement les valeurs de $s_1,s_2,s_3$ au point de coordonn\u00e9es $x_1=x_2=x_3=0$.\n", "\n", "**Exercice**\n", "\n", "Transformer le syst\u00e8me pour prendre comme param\u00e8tres $s_1$, $s_2$ et $x_1$.\n", "\n", "**Solution**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[s1 s2 s3|x1 x2 x3| 0]\n", "[--------+--------+--]\n", "[ 1 0 0| 2 3 1| 5]\n", "[ 0 1 0| 4 1 2|11]\n", "[ 0 0 1| 3 4 2| 8]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s = var('s1,s2,s3')\n", "x = var('x1,x2,x3')\n", "A = matrix([[2,3,1],[4,1,2],[3,4,2]])\n", "B = vector([5,11,8]).column()\n", "M = block_matrix([[matrix([[s1,s2,s3]]), matrix([[x1,x2,x3]]), 0], [1,A,B]]); M" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[x2 x3 s3|x1 s1 s2| 0]\n", "[--------+--------+--]\n", "[ 3 1 0| 2 1 0| 5]\n", "[ 1 2 0| 4 0 1|11]\n", "[ 4 2 1| 3 0 0| 8]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M.swap_columns(4,0)\n", "M.swap_columns(5,1); M" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ x2 x3 s3| x1 s1 s2| 0]\n", "[-----------------+-----------------+-----]\n", "[ 1 0 0| 0 2/5 -1/5| -1/5]\n", "[ 0 1 0| 2 -1/5 3/5| 28/5]\n", "[ 0 0 1| -1 -6/5 -2/5|-12/5]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "M[1:] = M[1:].echelon_form()\n", "M" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### Premi\u00e8re r\u00e9solution d'un programe lin\u00e9aire\n", "\n", "Consid\u00e9rons le syst\u00e8me suivant:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "x1,x2,x3 = var('x1,x2,x3')\n", "Chvatal13 = [[2*x1 + 3*x2 + x3 <= 5,\n", " 4*x1 + x2 + 2*x3 <= 11,\n", " 3*x1 + 4*x2 + 2*x3 <= 8],\n", " 5*x1 + 4*x2 + 3*x3]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Questions**\n", "\n", "Solution faisable ?\n", "\n", "Am\u00e9lioration de la solution ?\n", "\n", "##### Introduction de variables d'\u00e9cart\n", "\n", "Id\u00e9e: on transforme le probl\u00e8me en un syst\u00e8me d'*\u00e9quations* affines avec des contraintes de positivit\u00e9:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "Maximiser: z = 5*x1 + 4*x2 + 3*x3\n", "Sous les contraintes: s1 + 2*x1 + 3*x2 + x3 = 5\n", " s2 + 4*x1 + x2 + 2*x3 = 11\n", " s3 + 3*x1 + 4*x2 + 2*x3 = 8\n", "\n", " s1,...,x3 >=0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Premier pivot \u00e0 la main\n", "\n", "Am\u00e9lioration locale: en augmentant $x_1$ jusqu'\u00e0 $5/2$, on fait tomber $s_1$ \u00e0 z\u00e9ro.\n", "\n", "On transforme le syst\u00e8me pour se ramener \u00e0 une situation similaire \u00e0 la pr\u00e9c\u00e9dente, o\u00f9 l'on a trois variables et la fonction objective qui s'expriment en fonction des autres variables:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "Maximiser: z = - 7/2 x2 + 1/2*x3 - 5/2*s1 + 25/2\n", "Sous les contraintes: x1 + 3/2*x2 + 1/2*x3 + 1/2*s1 = 5/2\n", " s2 - 5*x2 - 2*s1 = 1\n", " s3 - 1/2*x2 + 1/2*x3 - 3/2*s1 = 1/2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On appelle cette op\u00e9ration un *pivot*.\n", "\n", "Le nom n'est pas un accident. On a effectu\u00e9 cette op\u00e9ration au moyen d'une substitution. Mais on a vu en r\u00e9solvant les syst\u00e8mes lin\u00e9aires qu'une substitution n'est qu'un cas particulier de pivot de Gau\u00df, et qu'il est g\u00e9n\u00e9ralement plus puissant de se mettre dans un cadre matriciel.\n", "\n", "##### Premier pivot sous forme matricielle\n", "\n", "Pour cela, nous chargeons un petit [fichier annexe](../_images/programmation_lineaire.py):" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "load(\"~/Enseignement/Agregation/media/programmation_lineaire.py\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![](media/programmation_lineaire.py)\n", "\n", "qui contient quelques utilitaires comme:\n", "\n", "Mettons notre syst\u00e8me sous forme matricielle:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|s1 s2 s3|x1 x2 x3| 0]\n", "[--+--------+--------+--]\n", "[ 1| 0 0 0|-5 -4 -3| 0]\n", "[--+--------+--------+--]\n", "[ 0| 1 0 0| 2 3 1| 5]\n", "[ 0| 0 1 0| 4 1 2|11]\n", "[ 0| 0 0 1| 3 4 2| 8]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = matrice_systeme(Chvatal13, (x1,x2,x3)); m" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Noter les signes n\u00e9gatifs pour $z$ : pour plus de coh\u00e9rence avec les variables d'\u00e9cart, on a \u00e9crit l'\u00e9quation d\u00e9finissant la fonction objective sous la forme:\n", "\n", "$$z -5x_1-4x_2-3x_3 = 0$$\n", "\n", "Rejouons maintenant le pivot. On veut remplacer le param\u00e8tre $x_1$ par $s_1$. Pour cela on \u00e9change les colonnes correspondantes:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|x1 s2 s3|s1 x2 x3| 0]\n", "[--+--------+--------+--]\n", "[ 1|-5 0 0| 0 -4 -3| 0]\n", "[--+--------+--------+--]\n", "[ 0| 2 0 0| 1 3 1| 5]\n", "[ 0| 4 1 0| 0 1 2|11]\n", "[ 0| 3 0 1| 0 4 2| 8]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t = copy(m)\n", "t.swap_columns(1,4); t" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "et on remets sous forme \u00e9chelon:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x1 s2 s3| s1 x2 x3| 0]\n", "[----+--------------+--------------+----]\n", "[ 1| 0 0 0| 5/2 7/2 -1/2|25/2]\n", "[----+--------------+--------------+----]\n", "[ 0| 1 0 0| 1/2 3/2 1/2| 5/2]\n", "[ 0| 0 1 0| -2 -5 0| 1]\n", "[ 0| 0 0 1|-3/2 -1/2 1/2| 1/2]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t[1:] = t[1:].echelon_form()\n", "t" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### S\u00e9quence compl\u00e8te de pivots matriciels\n", "\n", "On automatise l'op\u00e9ration de pivot avec:\n", "\n", "Ce qui donne:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|s1 s2 s3|x1 x2 x3| 0]\n", "[--+--------+--------+--]\n", "[ 1| 0 0 0|-5 -4 -3| 0]\n", "[--+--------+--------+--]\n", "[ 0| 1 0 0| 2 3 1| 5]\n", "[ 0| 0 1 0| 4 1 2|11]\n", "[ 0| 0 0 1| 3 4 2| 8]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = matrice_systeme(Chvatal13, (x1,x2,x3)); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x1 s2 s3| s1 x2 x3| 0]\n", "[----+--------------+--------------+----]\n", "[ 1| 0 0 0| 5/2 7/2 -1/2|25/2]\n", "[----+--------------+--------------+----]\n", "[ 0| 1 0 0| 1/2 3/2 1/2| 5/2]\n", "[ 0| 0 1 0| -2 -5 0| 1]\n", "[ 0| 0 0 1|-3/2 -1/2 1/2| 1/2]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pivot(m, 1, 4)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "m = _" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et on r\u00e9it\u00e8re: on augmente $x_3$ jusqu'\u00e0 $1$, ce qui fait tomber $s_3$ \u00e0 0:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|x1 s2 x3|s1 x2 s3| 0]\n", "[--+--------+--------+--]\n", "[ 1| 0 0 0| 1 3 1|13]\n", "[--+--------+--------+--]\n", "[ 0| 1 0 0| 2 2 -1| 2]\n", "[ 0| 0 1 0|-2 -5 0| 1]\n", "[ 0| 0 0 1|-3 -1 2| 1]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pivot(m, 3, 6)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "m = _" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et maintenant, que fait-on?\n", "\n", "#### Variables d'\u00e9cart\n", "\n", "Est-ce que l'introduction de ces variables change le probl\u00e8me ?\n", "\n", "#### Tableaux\n", "\n", "**D\u00e9finition: tableau initial**\n", "\n", "*Tableau initial:*\n", "\n", "$$z-\\sum_{j=1}^nc_jx_j=0$$\n", "\n", "$$s_i+\\sum_{j=1}^na_{ij}x_j = b_i \\text{, pour $i=1,\\ldots,m$}$$\n", "\n", "Ou sous forme matricielle:\n", "\n", "$$\\begin{aligned}\n", " z- & CX & = 0\\\\\n", " S+ & AX & = B\\\\\n", " X >= 0\n", "\\end{aligned}$$\n", "\n", "**Exercice**\n", "\n", "Mettre sous forme matricielle le probl\u00e8me suivant:\n", "\n", "**Solution**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|s1 s2 s3 s4|x1 x2 x3| 0]\n", "[--+-----------+--------+--]\n", "[ 1| 0 0 0 0|-5 -5 -3| 0]\n", "[--+-----------+--------+--]\n", "[ 0| 1 0 0 0| 1 3 1| 3]\n", "[ 0| 0 1 0 0|-1 0 3| 2]\n", "[ 0| 0 0 1 0| 2 3 -1| 2]\n", "[ 0| 0 0 0 1| 2 -1 2| 4]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = matrice_systeme(Chvatal19, (x1,x2,x3)); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**D\u00e9finitions: tableaux**\n", "\n", "De mani\u00e8re g\u00e9n\u00e9rale, un *tableau* est un ensemble d'\u00e9quations de la forme:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "z + 5/2 x2 - 11/2 x3 + 5/2 s4 = 5\n", " x1 + 3/2 x2 - 1/2 x3 + 1/2 s4 = 4\n", " s1 + 3/2 x2 + 3/2 x3 - 1/2 s4 = 2\n", " s2 + 3/2 x2 + 5/2 x3 + 1/2 s4 = 3\n", " s3 - 4 x2 + 3 x3 - s4 = 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$x_1,s_1,s_2,s_3$ sont les variables *basiques*; $\\{x_1,s_1,s_2,s_3\\}$ est la *base*.\n", "\n", "$x_2,x_3,s_4$ sont les variables *non basiques*.\n", "\n", "**Notes de terminologie**\n", "\n", "On utilise dans ce cours les *tableaux*, plut\u00f4t que les *dictionnaires* utilis\u00e9s par exemple dans \\[Chvatal\\_LP\\]\\_. La diff\u00e9rence est minime: on fait juste passer les variables non basiques d'un c\u00f4t\u00e9 ou de l'autre des \u00e9quations. D'autre part, on utilise $s_1,s_2,s_3,s_4$ plut\u00f4t que $x_4,x_5,x_6,x_7$ comme noms pour les variables d'\u00e9carts.\n", "\n", "Voici le dictionnaire correspondant au tableau pr\u00e9c\u00e9dent:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "x1 = 1 - 3/2 x2 + 1/2 x3 - 1/2 x7\n", "x4 = 2 - 3/2 x2 - 3/2 x3 + 1/2 x7\n", "x5 = 3 - 3/2 x2 - 5/2 x3 - 1/2 x7\n", "x6 = 2 + 4 x2 - 3 x3 + x7\n", " z = 5 - 5/2 x2 + 11/2 x3 - 5/2 x7" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\u00c0 noter aussi que, afin d'utiliser commod\u00e9ment la forme \u00e9chelon sur les tableaux repr\u00e9sent\u00e9s par des matrices par bloc Sage, on a choisi de faire passer l'expression de $z$ de l'autre c\u00f4t\u00e9, ce qui peut diff\u00e9rer des conventions utilis\u00e9es dans certains syst\u00e8mes (ex. MuPAD).\n", "\n", "La caract\u00e9ristique essentielle d'un tableau est que, connaissant les variables non-basiques, on peut imm\u00e9diatement calculer les variables basiques et la fonction objective (d'o\u00f9 le terme de *dictionnaire*). Le calcul devient m\u00eame imm\u00e9diat si toutes les variables non-basiques sont nulles.\n", "\n", "#### Point de vue g\u00e9om\u00e9trique\n", "\n", "**Remarques**\n", "\n", "- Les \u00e9quations d'un tableau d\u00e9crivent un sous-espace affine $E$ de $\\mathbb{R}^{n+m}$.\n", "- Un point $p$ de cet espace est caract\u00e9ris\u00e9 par ses coordonn\u00e9es dans les variables non-basiques.\n", "- L'op\u00e9ration de pivot pr\u00e9serve ce sous-espace affine.\n", "\n", "**Exercice**\n", "\n", "Calculer directement le tableau correspondant aux variables non-basiques $x_1,s_2,s_3$ du programme lin\u00e9aire suivant:\n", "\n", "Conclusion: un tableau est d\u00e9termin\u00e9 par le choix des variables non basiques.\n", "\n", "**Remarques**\n", "\n", "- Chaque choix de variables non-basiques correspond \u00e0 une base affine de ce sous-espace.\n", "- Chaque choix met en valeur le comportement du sous-espace au voisinage d'un point particulier: celui de coordonn\u00e9es nulles dans les variables non-basiques.\n", "\n", "**D\u00e9finitions**\n", "\n", "Le point de coordonn\u00e9es $(0,\\ldots,0)$ dans les variables non-basiques est appell\u00e9 *solution basique* du tableau.\n", "\n", "Un tableau est *faisable* si la solution basique est une solution faisable.\n", "\n", "De mani\u00e8re \u00e9quivalente, un tableau est faisable si les constantes dans $B$ sont toutes positives (ou nulles).\n", "\n", "Un tableau est *optimal* si la solution basique est une solution optimale.\n", "\n", "**Exercice (en TP)**\n", "\n", "Revenons \u00e0 notre exemple:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|s1 s2 s3 s4|x1 x2 x3| 0]\n", "[--+-----------+--------+--]\n", "[ 1| 0 0 0 0|-5 -5 -3| 0]\n", "[--+-----------+--------+--]\n", "[ 0| 1 0 0 0| 1 3 1| 3]\n", "[ 0| 0 1 0 0|-1 0 3| 2]\n", "[ 0| 0 0 1 0| 2 3 -1| 2]\n", "[ 0| 0 0 0 1| 2 -1 2| 4]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = matrice_systeme(Chvatal19, (x1,x2,x3)); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|x1 s2 s3 s4|s1 x2 x3| 0]\n", "[--+-----------+--------+--]\n", "[ 1| 0 0 0 0| 5 10 2|15]\n", "[--+-----------+--------+--]\n", "[ 0| 1 0 0 0| 1 3 1| 3]\n", "[ 0| 0 1 0 0| 1 3 4| 5]\n", "[ 0| 0 0 1 0|-2 -3 -3|-4]\n", "[ 0| 0 0 0 1|-2 -7 0|-2]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pivot(m, 5, 1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Oups, mauvais pivot! Essayons plut\u00f4t:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| s1 s2 x1 s4| s3 x2 x3| 0]\n", "[-----+-----------------------+-----------------+-----]\n", "[ 1| 0 0 0 0| 5/2 5/2 -11/2| 5]\n", "[-----+-----------------------+-----------------+-----]\n", "[ 0| 1 0 0 0| -1/2 3/2 3/2| 2]\n", "[ 0| 0 1 0 0| 1/2 3/2 5/2| 3]\n", "[ 0| 0 0 1 0| 1/2 3/2 -1/2| 1]\n", "[ 0| 0 0 0 1| -1 -4 3| 2]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pivot(m, 5, 3)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "m = _" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| s1 s2 x1 x3| s3 x2 s4| 0]\n", "[-----+-----------------------+-----------------+-----]\n", "[ 1| 0 0 0 0| 2/3 -29/6 11/6| 26/3]\n", "[-----+-----------------------+-----------------+-----]\n", "[ 0| 1 0 0 0| 0 7/2 -1/2| 1]\n", "[ 0| 0 1 0 0| 4/3 29/6 -5/6| 4/3]\n", "[ 0| 0 0 1 0| 1/3 5/6 1/6| 4/3]\n", "[ 0| 0 0 0 1| -1/3 -4/3 1/3| 2/3]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pivot(m, 7, 4)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "m = _" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| s1 x2 x1 x3| s3 s2 s4| 0]\n", "[------+---------------------------+--------------------+------]\n", "[ 1| 0 0 0 0| 2 1 1| 10]\n", "[------+---------------------------+--------------------+------]\n", "[ 0| 1 0 0 0|-28/29 -21/29 3/29| 1/29]\n", "[ 0| 0 1 0 0| 8/29 6/29 -5/29| 8/29]\n", "[ 0| 0 0 1 0| 3/29 -5/29 9/29| 32/29]\n", "[ 0| 0 0 0 1| 1/29 8/29 3/29| 30/29]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pivot(m, 6, 2)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "m = _" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercice (TP)**\n", "\n", "Utilisez l'algorithme du simplexe pour r\u00e9soudre les programmes lin\u00e9aires suivants:\n", "\n", "**Exemple**\n", "\n", "Essayons d'appliquer l'algorithme du simplexe aux programmes lin\u00e9aires de \\[Chvatal\\_LP\\]\\_ (p. 7). Que se passe-t'il ?" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|s1 s2|x1 x2| 0]\n", "[--+-----+-----+--]\n", "[ 1| 0 0|-1 -1| 0]\n", "[--+-----+-----+--]\n", "[ 0| 1 0| 1 0| 3]\n", "[ 0| 0 1| 0 1| 7]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = matrice_systeme(Chvatal7a, (x1,x2)); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|x1 s2|s1 x2| 0]\n", "[--+-----+-----+--]\n", "[ 1| 0 0| 1 -1| 3]\n", "[--+-----+-----+--]\n", "[ 0| 1 0| 1 0| 3]\n", "[ 0| 0 1| 0 1| 7]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 3, 1); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|x1 x2|s1 s2| 0]\n", "[--+-----+-----+--]\n", "[ 1| 0 0| 1 1|10]\n", "[--+-----+-----+--]\n", "[ 0| 1 0| 1 0| 3]\n", "[ 0| 0 1| 0 1| 7]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 4, 2)\n", "m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| s1 s2| x1 x2| 0]\n", "[---+-------+-------+---]\n", "[ 1| 0 0| -3 1| 0]\n", "[---+-------+-------+---]\n", "[ 0| 1 0| 1 1| 2]\n", "[ 0| 0 1| -2 -2|-10]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = matrice_systeme(Chvatal7b, (x1,x2)); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|s1 s2|x1 x2| 0]\n", "[--+-----+-----+--]\n", "[ 1| 0 0|-1 1| 0]\n", "[--+-----+-----+--]\n", "[ 0| 1 0|-2 1|-1]\n", "[ 0| 0 1|-1 -2|-2]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = matrice_systeme(Chvatal7c, (x1,x2)); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|s1 x1|s2 x2| 0]\n", "[--+-----+-----+--]\n", "[ 1| 0 0|-1 3| 2]\n", "[--+-----+-----+--]\n", "[ 0| 1 0|-2 5| 3]\n", "[ 0| 0 1|-1 2| 2]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pivot(m, 3, 2)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|s1|x1 x2| 0]\n", "[--+--+-----+--]\n", "[ 1| 0|-1 -1| 0]\n", "[--+--+-----+--]\n", "[ 0| 1| 1 1| 1]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = matrice_systeme(extra, (x1,x2)); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|x1|s1 x2| 0]\n", "[--+--+-----+--]\n", "[ 1| 0| 1 0| 1]\n", "[--+--+-----+--]\n", "[ 0| 1| 1 1| 1]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pivot(m, 2, 1)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Pi\u00e8ges et comment les \u00e9viter\n", "\n", "#### Bilan des \u00e9pisodes pr\u00e9c\u00e9dents\n", "\n", "On a un algorithme qui marche sur quelques exemples.\n", "\n", "Il faut v\u00e9rifier trois points pour savoir s'il marche en g\u00e9n\u00e9ral:\n", "\n", "1. Initialisation\n", "2. It\u00e9ration\n", "3. Terminaison\n", "\n", "#### It\u00e9ration\n", "\n", "**Proposition**\n", "\n", "\u00c9tant donn\u00e9 un tableau faisable, on peut toujours effectuer l'une des op\u00e9rations suivantes:\n", "\n", "1. Conclure que le syst\u00e8me a une solution optimale unique, la calculer et la certifier;\n", "2. Conclure que le syst\u00e8me a une infinit\u00e9 de solutions optimales, les calculer et les certifier;\n", "3. Conclure que le syst\u00e8me est non born\u00e9, et le certifier en d\u00e9crivant une demi-droite de solutions sur laquelle $z$ prend des valeurs aussi grandes que voulu.\n", "4. Trouver une variable entrante, une variable sortante, et effectuer un pivot. Par construction, le tableau obtenu est \u00e9quivalent au tableau pr\u00e9c\u00e9dent, et est encore faisable. De plus, $z$ a *augment\u00e9 au sens large* (i.e. la constante $z^*$ dans la nouvelle expression de $z$ est sup\u00e9rieure ou \u00e9gale \u00e0 l'ancienne).\n", "\n", "**D\u00e9monstration**\n", "\n", "Il suffit d'analyser le tableau faisable. Notons $S_1,\\ldots,S_m$ les variables basiques, $X_1,\\ldots,X_n$ les variables non-basiques, et $C_1,\\ldots,C_n,z^*$ les coefficients tels que $z=z^*+\\sum C_iX_i$.\n", "\n", "Par exemple, dans le tableau final du probl\u00e8me\\[probleme:simplexe1\\], on a $X_1=x_2$, $X_2=s_1$, $X_3=s_2$, $S_1=x_1$, $S_2=x_3$, $S_3=s_3$, $C_1=-3$, $C_2=-1$, $C_3=-1$ et $z^*=13$.\n", "\n", "1. Si $C_i<0$, pour tout $i$, alors la solution basique du tableau, de coordonn\u00e9es $X_1^*=\\cdots=X_n^*=0$ est l'unique solution optimale. V\u00e9rifiez le en prouvant qu'une toute solution faisable quelconque de coordonn\u00e9es $X_1,\\ldots,X_n$ donnant la m\u00eame valeur $z=z^*$ \u00e0 la fonction objective est \u00e9gale \u00e0 la solution basique du tableau.\n", "2. Si $C_i\\leq0$ pour tout $i$, la solution basique du tableau est optimale, et l'ensemble des solutions optimales est d\u00e9crit par les in\u00e9quations lin\u00e9aires du syst\u00e8me et l'annulation des variables non-basiques $X_i$ pour lesquelles on a $C_i<0$. Les d\u00e9tails sont similaires au 1.\n", "3. Sinon, on peut prendre $X_i$, variable non-basique avec un coefficient $C_i>0$. Si les \u00e9quations du tableau n'imposent pas de limite sur $X_i$, le syst\u00e8me est non born\u00e9: la demi-droite d\u00e9crite par $(0,\\ldots,0,X_i,0,\\ldots,0)$ pour $X_i\\geq0$ est compos\u00e9e de solutions faisables qui donnent des valeurs aussi grandes que voulu \u00e0 $z$.\n", "4. Autrement, une des variables basiques $S_j$ tombe \u00e0 z\u00e9ro, et on peut faire un pivot entre la variable entrante $X_i$ et la variable sortante $S_j$. Par construction, la nouvelle solution basique correspond \u00e0 une solution faisable $(0,\\ldots,0,X_i,0,\\ldots,0)$ pour un $X_i\\geq0$. En particulier le nouveau tableau est faisable, et comme $C_i\\geq0$, la constante $z^*$ a augment\u00e9 au sens large.\n", "\n", "**Exemple (\\[Chvatal\\_LP\\]\\_ p. 29)**\n", "\n", "Syst\u00e8me o\u00f9 $z$ n'augmente pas strictement lors du pivot:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|s1 s2 s3|x1 x2 x3| 0]\n", "[--+--------+--------+--]\n", "[ 1| 0 0 0|-2 1 -8| 0]\n", "[--+--------+--------+--]\n", "[ 0| 1 0 0| 0 0 2| 1]\n", "[ 0| 0 1 0|-1 3 4| 2]\n", "[ 0| 0 0 1| 2 -4 6| 3]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = matrice_systeme(Chvatal29, (x1,x2, x3)); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x3 s2 s3| x1 x2 s1| 0]\n", "[---+-----------+-----------+---]\n", "[ 1| 0 0 0| -2 1 4| 4]\n", "[---+-----------+-----------+---]\n", "[ 0| 1 0 0| 0 0 1/2|1/2]\n", "[ 0| 0 1 0| -1 3 -2| 0]\n", "[ 0| 0 0 1| 2 -4 -3| 0]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 6, 1); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x3 s2 x1| s3 x2 s1| 0]\n", "[----+--------------+--------------+----]\n", "[ 1| 0 0 0| 1 -3 1| 4]\n", "[----+--------------+--------------+----]\n", "[ 0| 1 0 0| 0 0 1/2| 1/2]\n", "[ 0| 0 1 0| 1/2 1 -7/2| 0]\n", "[ 0| 0 0 1| 1/2 -2 -3/2| 0]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 4, 3); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x3 x2 x1| s3 s2 s1| 0]\n", "[-----+-----------------+-----------------+-----]\n", "[ 1| 0 0 0| 5/2 3 -19/2| 4]\n", "[-----+-----------------+-----------------+-----]\n", "[ 0| 1 0 0| 0 0 1/2| 1/2]\n", "[ 0| 0 1 0| 1/2 1 -7/2| 0]\n", "[ 0| 0 0 1| 3/2 2 -17/2| 0]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 5, 2); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| s1 x2 x1| s3 s2 x3| 0]\n", "[----+--------------+--------------+----]\n", "[ 1| 0 0 0| 5/2 3 19|27/2]\n", "[----+--------------+--------------+----]\n", "[ 0| 1 0 0| 0 0 2| 1]\n", "[ 0| 0 1 0| 1/2 1 7| 7/2]\n", "[ 0| 0 0 1| 3/2 2 17|17/2]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 6, 1); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Lorsque $z$ n'augmente pas, on est forc\u00e9ment dans une situation de d\u00e9g\u00e9n\u00e9rescence: le pivot change le tableau, mais pas la solution basique d\u00e9crite par le tableau.\n", "\n", "#### Terminaison\n", "\n", "**Probl\u00e8me**\n", "\n", "Peut-on garantir que l'algorithme va finir par s'arr\u00eater ?\n", "\n", "**Proposition**\n", "\n", "Si l'algorithme du simplexe ne cycle pas, il termine en au plus $\\binom{n+m}m$ it\u00e9rations.\n", "\n", "**R\u00e9sum\u00e9 de d\u00e9monstration**\n", "\n", "Chaque it\u00e9ration correspond \u00e0 un tableau faisable.\n", "\n", "Un tableau faisable est enti\u00e8rement caract\u00e9ris\u00e9 par le choix des variables basiques.\n", "\n", "Il n'y a que $C(n+m,m)$ choix possibles de variables basiques.\n", "\n", "**Remarque**\n", "\n", "L'algorithme ne peut cycler qu'en pr\u00e9sence de d\u00e9g\u00e9n\u00e9rescence.\n", "\n", "**Exemple (\\[Chvatal\\_LP\\]\\_ p. 31)**\n", "\n", "Avec une strat\u00e9gie incorrecte, l'algorithme du simplexe peut cycler \u00e9ternellement:\n", "\n", "Syst\u00e8me cyclant en 6 it\u00e9rations avec la strat\u00e9gie:\n", "\n", "- Choix de la variable entrante avec le coefficient dans l'expression de $z$ le plus fort\n", "- Choix de la variable sortante avec le plus petit index" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| s1 s2 s3| x1 x2 x3 x4| 0]\n", "[----+--------------+-------------------+----]\n", "[ 1| 0 0 0| -10 57 9 24| 0]\n", "[----+--------------+-------------------+----]\n", "[ 0| 1 0 0| 0.5 -5.5 -2.5 9| 0]\n", "[ 0| 0 1 0| 0.5 -1.5 -0.5 1| 0]\n", "[ 0| 0 0 1| 1 0 0 0| 1]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = matrice_systeme(Chvatal31, (x1, x2, x3, x4)); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x1 s2 s3| s1 x2 x3 x4| 0]\n", "[-----+-----------------+-----------------------+-----]\n", "[ 1| 0.0 0 0| 20.0 -53.0 -41.0 204.0| 0]\n", "[-----+-----------------+-----------------------+-----]\n", "[ 0| 1.0 0 0| 2.0 -11.0 -5.0 18.0| 0]\n", "[ 0| 0.0 1 0| -1.0 4.0 2.0 -8.0| 0]\n", "[ 0| 0.0 0 1| -2.0 11.0 5.0 -18.0| 1]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 4, 1); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x1 x2 s3| s1 s2 x3 x4| 0]\n", "[-----+-----------------+-----------------------+-----]\n", "[ 1| 0 0.0 0| 6.75 13.25 -14.5 98.0| 0]\n", "[-----+-----------------+-----------------------+-----]\n", "[ 0| 1.0 0.0 0|-0.75 2.75 0.5 -4.0| 0]\n", "[ 0| 0.0 1.0 0|-0.25 0.25 0.5 -2.0| 0]\n", "[ 0| 0.0 0.0 1| 0.75 -2.75 -0.5 4.0| 1]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 5, 2); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x3 x2 s3| s1 s2 x1 x4| 0]\n", "[-----+-----------------+-----------------------+-----]\n", "[ 1| 0.0 0 0|-15.0 93.0 29.0 -18.0| 0]\n", "[-----+-----------------+-----------------------+-----]\n", "[ 0| 1.0 0 0| -1.5 5.5 2.0 -8.0| 0]\n", "[ 0| 0.0 1.0 0| 0.5 -2.5 -1.0 2.0| 0]\n", "[ 0| 0.0 0.0 1| 0 0 1.0 0| 1]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 6, 1); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x3 x4 s3| s1 s2 x1 x2| 0]\n", "[-----+-----------------+-----------------------+-----]\n", "[ 1| 0 0.0 0|-10.5 70.5 20.0 9.0| 0]\n", "[-----+-----------------+-----------------------+-----]\n", "[ 0| 1.0 0.0 0| 0.5 -4.5 -2.0 4.0| 0]\n", "[ 0| 0.0 1.0 0| 0.25 -1.25 -0.5 0.5| 0]\n", "[ 0| 0.0 0 1| 0 0 1.0 0| 1]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 7, 2); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| s1 x4 s3| x3 s2 x1 x2| 0]\n", "[-----+-----------------+-----------------------+-----]\n", "[ 1| 0.0 0 0| 21.0 -24.0 -22.0 93.0| 0]\n", "[-----+-----------------+-----------------------+-----]\n", "[ 0| 1.0 0 0| 2.0 -9.0 -4.0 8.0| 0]\n", "[ 0| 0.0 1.0 0| -0.5 1.0 0.5 -1.5| 0]\n", "[ 0| 0 0 1| 0 0 1.0 0| 1]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 4, 1); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| s1 s2 s3| x3 x4 x1 x2| 0]\n", "[-----+-----------------+-----------------------+-----]\n", "[ 1| 0 0.0 0| 9.0 24.0 -10.0 57.0| 0]\n", "[-----+-----------------+-----------------------+-----]\n", "[ 0| 1.0 0.0 0| -2.5 9.0 0.5 -5.5| 0]\n", "[ 0| 0.0 1.0 0| -0.5 1.0 0.5 -1.5| 0]\n", "[ 0| 0 0 1| 0 0 1.0 0| 1]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 5, 2); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Probl\u00e8me**\n", "\n", "Comment garantir que l'algorithme ne cyclera pas ?\n", "\n", "##### La m\u00e9thode des perturbations\n", "\n", "L'algorithme du simplexe ne peut cycler qu'en pr\u00e9sence de d\u00e9g\u00e9n\u00e9rescence.\n", "\n", "**Probl\u00e8me**\n", "\n", "Comment se d\u00e9barasser des d\u00e9g\u00e9n\u00e9rescences ?\n", "\n", "Id\u00e9e: supprimer les d\u00e9g\u00e9n\u00e9rescences en perturbant l\u00e9g\u00e8rement le syst\u00e8me\n", "\n", "**Exemple (\\[Chvatal\\_LP\\]\\_ p. 34, 35)**\n", "\n", "On introduit des constantes $\\varepsilon_1>>\\cdots>>\\varepsilon_n$ :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| s1 s2 s3| x1 x2 x3 x4| 0]\n", "[----+--------------+-------------------+----]\n", "[ 1| 0 0 0| -10 57 9 24| 0]\n", "[----+--------------+-------------------+----]\n", "[ 0| 1 0 0| 0.5 -5.5 -2.5 9| e1]\n", "[ 0| 0 1 0| 0.5 -1.5 -0.5 1| e2]\n", "[ 0| 0 0 1| 1 0 0 0| e3]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = matrice_systeme(Chvatal35, (x1, x2, x3, x4)); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x1 s2 s3| s1 x2 x3 x4| 0]\n", "[------------+--------------------------------------+---------------------------------------------------+------------]\n", "[ 1| 0.0 0 0| 20.0 -53.0 -41.0 204.0| 20.0*e1]\n", "[------------+--------------------------------------+---------------------------------------------------+------------]\n", "[ 0| 1.0 0 0| 2.0 -11.0 -5.0 18.0| 2.0*e1]\n", "[ 0| 0.0 1 0| -1.0 4.0 2.0 -8.0| -e1 + e2]\n", "[ 0| 0.0 0 1| -2.0 11.0 5.0 -18.0|-2.0*e1 + e3]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 4, 1); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x1 x2 s3| s1 s2 x3 x4| 0]\n", "[----------------------+--------------------------------------------------------------------+-------------------------------------------------------------------------------------------+----------------------]\n", "[ 1| 0 0.0 0| 6.75 13.25 -14.5 98.0| 6.75*e1 + 13.25*e2]\n", "[----------------------+--------------------------------------------------------------------+-------------------------------------------------------------------------------------------+----------------------]\n", "[ 0| 1.0 0.0 0| -0.75 2.75 0.5 -4.0| -0.75*e1 + 2.75*e2]\n", "[ 0| 0.0 1.0 0| -0.25 0.25 0.5 -2.0| -0.25*e1 + 0.25*e2]\n", "[ 0| 0.0 0.0 1| 0.75 -2.75 -0.5 4.0|0.75*e1 - 2.75*e2 + e3]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 5, 2); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Inconv\u00e9nient: solution approch\u00e9e, ou introduction de calcul symbolique\n", "\n", "##### La m\u00e9thode du plus petit index\n", "\n", "**Th\u00e9or\u00e8me**\n", "\n", "L'algorithme du simplexe termine si, lorsqu'il y a ambigu\u00eft\u00e9 sur le choix de la variable entrante ou sortante, on choisit toujours la variable de plus petit index.\n", "\n", "Cette m\u00e9thode est simple et \u00e9l\u00e9gante.\n", "\n", "Par contre, elle emp\u00eache toute strat\u00e9gie pour faire converger l'algorithme plus vite.\n", "\n", "##### M\u00e9thodes mixtes\n", "\n", "Strat\u00e9gie au choix, mais si $z$ n'augmente pas pendant plus d'un certain nombre d'it\u00e9rations, on bascule sur la strat\u00e9gie du plus petit index jusqu'\u00e0 ce que l'on soit sorti de la d\u00e9g\u00e9n\u00e9rescence.\n", "\n", "#### Initialisation\n", "\n", "Pour le moment, l'algorithme du simplexe n\u00e9cessite de partir d'un tableau faisable.\n", "\n", "**Probl\u00e8me**\n", "\n", "Dans le cas g\u00e9n\u00e9ral, comment se ramener \u00e0 un tableau faisable?\n", "\n", "Le syst\u00e8me pourrait m\u00eame ne pas avoir de solution!\n", "\n", "**Exemple (\\[Chvatal\\_LP\\]\\_ p. 39)**\n", "\n", "Syst\u00e8me $P_1$ :\n", "\n", "Maximiser: $x_1-x_2+x_3$\n", "\n", "Sous les contraintes:\n", "\n", "$2x_1-x_2+2x_3\\leq4$\n", "\n", "$2x_1-3x_2+x_3\\leq-5$\n", "\n", "$-x_1+x_2-2x_3\\leq-1$\n", "\n", "$x_1,x_2,x_3\\geq0$\n", "\n", "Introduction d'un *syst\u00e8me* auxiliaire $P_0$ pour d\u00e9terminer si $P$ est faisable:\n", "\n", "Maximiser: $-x_0$\n", "\n", "Sous les contraintes:\n", "\n", "$2x_1-x_2+2x_3-x_0\\leq4$\n", "\n", "$2x_1-3x_2+x_3-x_0\\leq-5$\n", "\n", "$-x_1+x_2-2x_3-x_0\\leq-1$\n", "\n", "$x_0,x_1,x_2,x_3\\geq0$\n", "\n", "Remarques:\n", "\n", "- $P_0$ est faisable (prendre $x_0$ suffisamment grand);\n", "- Les solutions faisables de $P$ correspondent aux solutions faisables de $P_0$ avec $x_0=0$;\n", "- $P$ est faisable si et seulement si $P_0$ a une solution faisable avec $x_0=0$.\n", "\n", "\u00c9tudions ce nouveau syst\u00e8me:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|s1 s2 s3|x1 x2 x3 x0| 0]\n", "[--+--------+-----------+--]\n", "[ 1| 0 0 0| 0 0 0 1| 0]\n", "[--+--------+-----------+--]\n", "[ 0| 1 0 0|-1 1 -2 -1|-1]\n", "[ 0| 0 1 0| 2 -3 1 -1|-5]\n", "[ 0| 0 0 1| 2 -1 2 -1| 4]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = matrice_systeme(Chvatal40, (x1,x2,x3,x0)); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|s1 x0 s3|x1 x2 x3 s2| 0]\n", "[--+--------+-----------+--]\n", "[ 1| 0 0 0| 2 -3 1 1|-5]\n", "[--+--------+-----------+--]\n", "[ 0| 1 0 0|-3 4 -3 -1| 4]\n", "[ 0| 0 1 0|-2 3 -1 -1| 5]\n", "[ 0| 0 0 1| 0 2 1 -1| 9]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 7, 2); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x2 x0 s3| x1 s1 x3 s2| 0]\n", "[----+--------------+-------------------+----]\n", "[ 1| 0 0 0|-1/4 3/4 -5/4 1/4| -2]\n", "[----+--------------+-------------------+----]\n", "[ 0| 1 0 0|-3/4 1/4 -3/4 -1/4| 1]\n", "[ 0| 0 1 0| 1/4 -3/4 5/4 -1/4| 2]\n", "[ 0| 0 0 1| 3/2 -1/2 5/2 -1/2| 7]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 5, 1); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x2 x3 s3| x1 s1 x0 s2| 0]\n", "[----+--------------+-------------------+----]\n", "[ 1| 0 0 0| 0 0 1 0| 0]\n", "[----+--------------+-------------------+----]\n", "[ 0| 1 0 0|-3/5 -1/5 3/5 -2/5|11/5]\n", "[ 0| 0 1 0| 1/5 -3/5 4/5 -1/5| 8/5]\n", "[ 0| 0 0 1| 1 1 -2 0| 3]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 6, 2); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Maintenant, nous savons que le syst\u00e8me $P$ est faisable.\n", "\n", "En fait, en \u00e9liminant $x_0$ on obtient m\u00eame un tableau faisable pour $P$ (apr\u00e8s pivotage de la fonction objective)!\n", "\n", "**Algorithme du simplexe en deux phases**\n", "\n", "Entr\u00e9e: un probl\u00e8me $P$ sous forme standard Sortie: une description compl\u00e8te des solutions optimales de $P$\n", "\n", "Phase I:\n", "\n", "1. Si $(0,\\ldots,0)$ est solution faisable de $P$, on passe directement \u00e0 la phase II.\n", "2. D\u00e9finir un probl\u00e8me auxiliaire $P_0$.\n", "3. Le premier tableau pour $P_0$ est infaisable.\n", "4. Le rendre faisable par un pivot appropri\u00e9 de $x_0$.\n", "5. Appliquer le simplexe habituel:\n", " 1. Si \u00e0 une \u00e9tape donn\u00e9e, $x_0$ peut sortir de la base, le faire en priorit\u00e9:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " En effet, il y a une solution faisable avec $x_0=0$, et on peut passer en phase II.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "2. Si \u00e0 une \u00e9tape donn\u00e9e on atteint une solution optimale:\n", " 1. Si $x_0$ n'est pas basique:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " Il y a une solution faisable avec $x_0=0$. On peut donc passer en phase II.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "2. Si $x_0$ est basique et $z_0<0$ :" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " $P$ est infaisable, et on s'arr\u00eate.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "3. Sinon $x_0$ est basique et $z_0=0$ :" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " Situation impossible si on fait toujours sortir $x_0$ en priorit\u00e9 de la base.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "6. Tirer de $P_0$ un tableau faisable pour $P$.\n", "\n", "Phase II:\n", "\n", "1. Appliquer le simplexe habituel \u00e0 partir du tableau donn\u00e9 par $P_0$.\n", "\n", "**Exercice (\\[Chvatal\\_LP\\]\\_ ex 3.9a p. 44) (TP)**\n", "\n", "R\u00e9soudre \u00e0 l'aide de l'algorithme du simplexe en deux phase le programme lin\u00e9aire suivant:\n", "\n", "**Solution**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|s1 s2 s3|x1 x2| 0]\n", "[--+--------+-----+--]\n", "[ 1| 0 0 0|-3 -1| 0]\n", "[--+--------+-----+--]\n", "[ 0| 1 0 0| 1 -1|-1]\n", "[ 0| 0 1 0|-1 -1|-3]\n", "[ 0| 0 0 1| 2 1| 4]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = matrice_systeme(Chvatal44_39a, (x1,x2)); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|s1 s2 s3|x1 x2 x0| 0]\n", "[--+--------+--------+--]\n", "[ 1| 0 0 0| 0 0 1| 0]\n", "[--+--------+--------+--]\n", "[ 0| 1 0 0| 1 -1 -1|-1]\n", "[ 0| 0 1 0|-1 -1 -1|-3]\n", "[ 0| 0 0 1| 2 1 -1| 4]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = matrice_systeme(Chvatal44_39a0, (x1, x2, x0)); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|s1 x0 s3|x1 x2 s2| 0]\n", "[--+--------+--------+--]\n", "[ 1| 0 0 0|-1 -1 1|-3]\n", "[--+--------+--------+--]\n", "[ 0| 1 0 0| 2 0 -1| 2]\n", "[ 0| 0 1 0| 1 1 -1| 3]\n", "[ 0| 0 0 1| 3 2 -1| 7]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 6, 2); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x1 x0 s3| s1 x2 s2| 0]\n", "[----+--------------+--------------+----]\n", "[ 1| 0 0 0| 1/2 -1 1/2| -2]\n", "[----+--------------+--------------+----]\n", "[ 0| 1 0 0| 1/2 0 -1/2| 1]\n", "[ 0| 0 1 0|-1/2 1 -1/2| 2]\n", "[ 0| 0 0 1|-3/2 2 1/2| 4]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 4, 1); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x1 x2 s3| s1 x0 s2| 0]\n", "[----+--------------+--------------+----]\n", "[ 1| 0 0 0| 0 1 0| 0]\n", "[----+--------------+--------------+----]\n", "[ 0| 1 0 0| 1/2 0 -1/2| 1]\n", "[ 0| 0 1 0|-1/2 1 -1/2| 2]\n", "[ 0| 0 0 1|-1/2 -2 3/2| 0]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 5, 2); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|s1 s2 s3|x1 x2| 0]\n", "[--+--------+-----+--]\n", "[ 1| 0 0 0|-3 -1| 0]\n", "[--+--------+-----+--]\n", "[ 0| 1 0 0| 1 -1|-1]\n", "[ 0| 0 1 0|-1 -1|-3]\n", "[ 0| 0 0 1| 2 1| 4]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = matrice_systeme(Chvatal44_39a, (x1, x2)); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x1 x2 s3| s1 s2| 0]\n", "[----+--------------+---------+----]\n", "[ 1| 0 0 0| 1 -2| 5]\n", "[----+--------------+---------+----]\n", "[ 0| 1 0 0| 1/2 -1/2| 1]\n", "[ 0| 0 1 0|-1/2 -1/2| 2]\n", "[ 0| 0 0 1|-1/2 3/2| 0]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 4, 1)\n", "m = pivot(m, 5, 2); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x1 x2 s2| s1 s3| 0]\n", "[----+--------------+---------+----]\n", "[ 1| 0 0 0| 1/3 4/3| 5]\n", "[----+--------------+---------+----]\n", "[ 0| 1 0 0| 1/3 1/3| 1]\n", "[ 0| 0 1 0|-2/3 1/3| 2]\n", "[ 0| 0 0 1|-1/3 2/3| 0]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 5, 3); m" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Conclusion: il existe une unique solution optimale de coordonn\u00e9es $x_1=1$ et $x_2=2$. La fonction objective y vaut $z=5$.\n", "\n", "> sage: \\#\n", "\n", "### Le th\u00e9or\u00e8me fondamental de la programmation lin\u00e9aire\n", "\n", "L'algorithme du simplexe, comme l'algorithme de Gau\u00df, est int\u00e9ressant non seulement d'un point de vue pratique, mais aussi \u00e0 cause de ses cons\u00e9quences th\u00e9oriques.\n", "\n", "**Th\u00e9or\u00e8me**\n", "\n", "Tout programme lin\u00e9aire $P$ sous forme standard a l'une des propri\u00e9t\u00e9s suivantes:\n", "\n", "1. Si $P$ n'a pas de solutions optimales, alors $P$ est infaisable ou non born\u00e9;\n", "2. Si $P$ a une solutions faisable, alors $P$ a une solution basique faisable;\n", "3. Si $P$ a une solution optimale, alors $P$ a une solution basique optimale.\n", "\n", "D'un point de vue g\u00e9om\u00e9trique: l'ensemble des solutions faisables est un poly\u00e8dre convexe, et s'il existes une solution optimale, alors il en existe une sur un des sommets du poly\u00e8dre convexe.\n", "\n", "### Efficacit\u00e9 de l'algorithme du simplexe\n", "\n", "Pour une discussion compl\u00e8te sur ce th\u00e8me, nous renvoyons au livre de r\u00e9f\u00e9rence \\[Chvatal\\_LP\\]\\_, ainsi qu'\u00e0 l'excellente Foire Aux Questions pour les \u00e9volutions r\u00e9centes.\n", "\n", "En tr\u00e8s bref:\n", "\n", "- L'algorithme du simplexe est de complexit\u00e9 exponentielle en th\u00e9orie, mais quasi-lin\u00e9aire dans les probl\u00e8mes pratiques.\n", "- R\u00e9soudre un programme lin\u00e9aire est un probl\u00e8me de complexit\u00e9 polynomiale (ex: algorithme de l'Ellipso\u00efde)\n", "\n", "### Le th\u00e9or\u00e8me de dualit\u00e9\n", "\n", "#### Motivation: estimer la valeur optimale de la fonction objective\n", "\n", "**Exemple**\n", "\n", "On consid\u00e8re le probl\u00e8me suivant:\n", "\n", "> Maximiser: $z =4x_1+x_2+5x_3+3x_4$\n", ">\n", "> Sous les contraintes:\n", ">\n", "> > $x_1-x_2-x_3+3x_4\\leq1$\n", "> >\n", "> > $5x_1+x_2+3x_3+8x_4\\leq55$\n", "> >\n", "> > $-x_1+2x_2+3x_3-5x_4\\leq3$\n", "> >\n", "> > $x_1,x_2,x_3,x_4\\geq0$\n", "\n", "- Borne inf\u00e9rieure sur la valeur optimale $z^*$?\n", "- Borne sup\u00e9rieure sur la valeur optimale $z^*$?\n", "\n", "D'apr\u00e8s la seconde contrainte:\n", "\n", "$$z^*\\leq4x_1+x_2+5x_3+3x_4\\leq\\frac{25}3x_1+\\frac53x_2+5x_3+\\frac{40}3x_4\\leq\\frac{275}3$$\n", "\n", "En utilisant la somme de la deuxi\u00e8me et troisi\u00e8me contrainte:\n", "\n", "$$z^*\\leq4x_1+3x_2+6x_3+3x_4\\leq58$$\n", "\n", "**Probl\u00e8me**\n", "\n", "Comment faire cela de mani\u00e8re syst\u00e9matique ?\n", "\n", "On recherche des combinaisons lin\u00e9aires des contraintes:\n", "\n", "- $y_1$ fois la premi\u00e8re contrainte: $x_1-x_2-x_3+3x_4\\leq1$\n", "- $y_2$ fois la seconde contrainte: $5x_1+x_2+3x_3+8x_4\\leq55$\n", "- $y_3$ fois la troisi\u00e8me contrainte: $-x_1+2x_2+3x_3-5x_4\\leq3$\n", "\n", "Ce qui donne:\n", "\n", "$$(y_1+5y_2-y_3)x_1+(-y_1+y_2+2y_3)x_2+(-y_1+3y_2+3y_3)x_3+(3y_1+8y_2-5y_3)x_4$$\n", "\n", "$$\\leq y_1+55y_2+3y_3$$\n", "\n", "Quelles sont les contraintes pour obtenir une borne sur $z^*$ ?\n", "\n", "Pour garder le sens des in\u00e9galit\u00e9s: $y_1,y_2,y_3\\geq0$\n", "\n", "Pour obtenir une majoration de $z=4x_1+x_2+5x_3+3x_4$ :\n", "\n", "- $y_1+5y_2-y_3\\geq4$\n", "- $-y_1+y_2+2y_3\\geq1$\n", "- $-y_1+3y_2+3y_3\\geq5$\n", "- $3y_1+8y_2-5y_3\\geq3$\n", "\n", "Si $y_1,y_2,y_3$ satisfont ces conditions, on obtient la borne $z\\leq\n", "y_1+55y_2+3y_3$.\n", "\n", "On veut donc minimiser $y_1+55y_2+3y_3$!\n", "\n", "Par exemple, en prenant $y_1=0$ et $y_2=y_3=1$, on retrouve l'in\u00e9galit\u00e9 $z\\leq58$.\n", "\n", "#### Le probl\u00e8me dual\n", "\n", "**D\u00e9finition**\n", "\n", "Soit $P$ un programme lin\u00e9aire sous *forme standard:*\n", "\n", "Maximiser:\n", "\n", "$$z=\\sum_{j=1}^nc_j\\ x_j$$\n", "\n", "Sous les contraintes:\n", "\n", "$$\\sum_{j=1}^na_{ij}\\ x_j\\leq b_i,\\textrm{ pour }i=1,\\ldots,m$$\n", "\n", "$$x_j\\geq0,\\textrm{ pour }j=1,\\ldots,n$$\n", "\n", "Le *dual* de $P$ est le probl\u00e8me:\n", "\n", "Minimiser:\n", "\n", "$$w=\\sum_{i=1}^mb_i\\ y_i$$\n", "\n", "Sous les contraintes:\n", "\n", "$$\\sum_{i=1}^ma_{ij}\\ y_i\\geq c_j,\\textrm{ pour }j=1,\\ldots,n$$\n", "\n", "$$y_i\\geq0,\\textrm{ pour }i=1,\\ldots,m$$\n", "\n", "$P$ est appel\u00e9 probl\u00e8me *primal.*\n", "\n", "**Proposition**\n", "\n", "Si $x_1,\\ldots,x_n$ est une solution faisable du probl\u00e8me primal et $y_1,\\ldots,y_m$ une solution faisable du probl\u00e8me dual, alors $z\\leq w$, *i.e.*\n", "\n", "$$\\sum_{j=1}^nc_j\\ x_j\\leq\\sum_{i=1}^mb_i\\ y_i$$\n", "\n", "**D\u00e9monstration**\n", "\n", "Il suffit d'appliquer les in\u00e9galit\u00e9s qui d\u00e9finissent les solutions faisables:\n", "\n", "$$z=\\sum_{j=1}^nc_j\\ x_j\\leq\\sum_{j=1}^n\\left(\\sum_{i=1}^ma_{ij}\\ y_i\\right)x_j=\\sum_{i=1}^m\\left(\\sum_{j=1}^na_{ij}\\ x_j\\right)y_i\\leq\\sum_{i=1}^mb_i\\ y_i=w$$\n", "\n", "En particulier:\n", "\n", "- Si, comme dans l'exemple pr\u00e9c\u00e9dent, on conna\u00eet une solution faisable du probl\u00e8me dual, on obtient une borne sur le probl\u00e8me primal et r\u00e9ciproquement!\n", "- Si on conna\u00eet une solution faisable du probl\u00e8me primal et une solution faisable du probl\u00e8me dual telles que $z=w$, *i.e.*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " $$\\sum_{j=1}^nc_j\\ x_j=\\sum_{i=1}^mb_i\\ y_i,$$\n", "\n", " alors on sait que ces deux solutions sont optimales!\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exercice (TP)**\n", "\n", "Prouver que les solutions faisables $x_1=0$ , $x_2=14$, $x_3=0$, $x_4=5$ et $y_1=11$, $y_2=0$, $y_3=6$ du probl\u00e8me original et de son dual sont optimales.\n", "\n", "La donn\u00e9e de $(y_1,y_2,y_3)$ donne un *certificat* de l'optimalit\u00e9 de la solution $(x_1,x_2,x_3,x_4)$ :\n", "\n", "Quelqu'un qui veut faire une v\u00e9rification peut le faire quasiment sans calcul: il suffit de tester que les solutions sont faisables et que $z=w$!\n", "\n", "**Probl\u00e8me**\n", "\n", "Est-il toujours possible de trouver un tel certificat ?\n", "\n", "La r\u00e9ponse est oui, et c'est le th\u00e9or\u00e8me central de la programmation lin\u00e9aire.\n", "\n", "#### Le th\u00e9or\u00e8me de dualit\u00e9\n", "\n", "**Th\u00e9or\u00e8me**\n", "\n", "Si le probl\u00e8me primal a une solution optimale $(x_1^*,\\ldots,x_n^*)$, alors le probl\u00e8me dual a une solution optimale $(y_1^*,\\ldots,y_m^*)$ telle que $w^*=z^*$, *i.e.*\n", "\n", "$$\\sum_{j=1}^nc_j\\ x_j^*=\\sum_{i=1}^mb_i\\ y_i^*.$$\n", "\n", "Ce th\u00e9or\u00e8me nous assure de l'existence d'un certificat.\n", "\n", "Mais y-a-t'il une technique pour le calculer ?\n", "\n", "Oui, car la preuve va \u00eatre *constructive*: son principe va pr\u00e9cis\u00e9ment \u00eatre de construire une solution optimale, en utilisant le tableau final obtenu par l'algorithme du simplexe.\n", "\n", "**Exemple**\n", "\n", "Faisons un peu de magie. Le tableau initial est:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z|s1 s2 s3|x1 x2 x3 x4| 0]\n", "[--+--------+-----------+--]\n", "[ 1| 0 0 0|-4 -1 -5 -3| 0]\n", "[--+--------+-----------+--]\n", "[ 0| 1 0 0| 1 -1 -1 3| 1]\n", "[ 0| 0 1 0| 5 1 3 8|55]\n", "[ 0| 0 0 1|-1 2 3 -5| 3]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = matrice_systeme(Chvatal54, (x1, x2, x3, x4)); m" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "L'algorithme du simplexe donne comme tableau final:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[ z| x4 s2 x2| x1 s3 x3 s1| 0]\n", "[---+-----------+---------------+---]\n", "[ 1| 0 0 0| 1 6 2 11| 29]\n", "[---+-----------+---------------+---]\n", "[ 0| 1 0 0| 1 1 1 2| 5]\n", "[ 0| 0 1 0| -5 -11 -9 -21| 1]\n", "[ 0| 0 0 1| 2 3 4 5| 14]\n" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = pivot(m, 7, 1)\n", "m = pivot(m, 5, 3); m" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "#" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ce calcul donne la solution optimale: $(x_1^*:=0,\\ x_2^*:=14,\\ x_3^*:=0)$.\n", "\n", "Ce calcul donne aussi un certificat, mais pour le v\u00e9rifier, il faut refaire tout le calcul!\n", "\n", "Sortons le lapin du chapeau \u2026\n", "\n", "La variable $y_1$ est associ\u00e9e \u00e0 la premi\u00e8re contrainte, qui elle m\u00eame est associ\u00e9e \u00e0 la variable d'\u00e9cart $s_1$. Hop, on prends pour $y_1^*$ l'oppos\u00e9 du coefficient de $s_1$ dans l'expression de $z$ dans le tableau final. De m\u00eame pour $y_2^*$ et $y_3^*$ :\n", "\n", "$$y_1^*:=11,\\ y_2^*:=0,\\ y_3^*:=6.$$\n", "\n", "$(y_1^*,y_2^*,y_3^*)$ est une solution faisable du probl\u00e8me dual.\n", "\n", "Par \u00abmiracle\u00bb, on obtient $w^*=z^*$.\n", "\n", "On a donc pu lire le certificat voulu directement sur le tableau final!\n", "\n", "Voyons maintenant pourquoi cela marche dans le cas g\u00e9n\u00e9ral.\n", "\n", "**D\u00e9monstration du th\u00e9or\u00e8me de dualit\u00e9**\n", "\n", "Il suffit de construire une solution *faisable* $(y_1^*,\\ldots,y_m^*)$ v\u00e9rifiant $w^*=z^*$.\n", "\n", "On applique l'algorithme du simplexe au probl\u00e8me initial, en introduisant comme d'habitude les variables d'\u00e9cart $s_1,\\ldots,s_m$. Dans le tableau final, $z$ est de la forme\n", "\n", "$$z=z^*+\\sum_{j=1}^n\\overline{c_j}\\ x_j+\\sum_{i=1}^md_i\\ s_i,$$\n", "\n", "o\u00f9 les $\\overline{c_j}$ et $d_i$ sont des coeffs nuls pour les variables basiques, et n\u00e9gatifs pour les autres.\n", "\n", "On pose comme dans l'exemple:\n", "\n", "$$y_i^*:=-d_i\\text{, pour $i=1,\\ldots,m$ }.$$\n", "\n", "Il ne reste plus qu'\u00e0 v\u00e9rifier que $(y_1^*,\\ldots,y_m^*)$ est faisable et donne $w^*=z^*$.\n", "\n", "C'est un calcul fastidieux mais direct (surtout sous forme matricielle!):\n", "\n", "Pour une solution quelconque $(x_1,\\ldots,x_n)$, on a par d\u00e9finition:\n", "\n", "$$z=\\sum_{j=1}^nc_j\\ x_j$$\n", "\n", "$$s_i=b_i-\\sum_{j=1}^na_{ij}\\ x_j$$\n", "\n", "En rempla\u00e7ant dans l'expression ci-dessus, on obtient\n", "\n", "$$\\sum_{j=1}^nc_j\\ x_j=z^*+\\sum_{j=1}^n\\overline{c_j}\\ x_j-\\sum_{i=1}^my_i^*(b_i-\\sum_{j=1}^na_{ij}x_j)$$\n", "\n", "$$\\sum_{j=1}^nc_j\\ x_j=z^*-\\sum_{i=1}^mb_i\\ y_i^*+\\sum_{j=1}^n(\\overline{c_j}+\\sum_{i=1}^ma_{ij}\\ y_i^*)\\ x_j$$\n", "\n", "Cette \u00e9galit\u00e9 \u00e9tant v\u00e9rifi\u00e9e quel que soit le choix de $(x_1,\\ldots,x_n)$, il doit y avoir \u00e9galit\u00e9 des coefficients des $x_j$ de part et d'autre. On en d\u00e9duit d'une part que\n", "\n", "$$z^*=\\sum_{j=1}^nb_i\\ y_i^*=w^*,$$\n", "\n", "comme voulu, et d'autre part que\n", "\n", "$$\\sum_{i=1}^ma_{ij}\\ y_i^*=c_j-\\overline{c_j}\\geq c_j,$$\n", "\n", "c'est-\u00e0-dire que $(y_1^*,\\ldots,y_m^*)$ est une solution faisable du probl\u00e8me dual.\n", "\n", "#### Relations entre un probl\u00e8me et son dual\n", "\n", "**Proposition**\n", "\n", "Le dual du dual d'un probl\u00e8me $P$ est le probl\u00e8me $P$ lui-m\u00eame.\n", "\n", "(matriciellement: on transpose $A$ et on \u00e9change $B$ et $C$)\n", "\n", "**Exercice**\n", "\n", "V\u00e9rifiez-le sur un exemple.\n", "\n", "Il s'ensuit:\n", "\n", "**Th\u00e9or\u00e8me**\n", "\n", "On a les relations suivantes entre un probl\u00e8me $P$ et son dual $Q$ :\n", "\n", "1. $P$ admet une solution optimale si et seulement si $Q$ en admet une.\n", "2. Si $P$ est faisable, alors $Q$ est born\u00e9; si $Q$ est faisable, alors $P$ est born\u00e9.\n", "\n", "**Exemple**\n", "\n", "Un probl\u00e8me et son dual peuvent \u00eatre simultan\u00e9ment infaisables:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "Maximiser: 2*x1-x2\n", "Sous les contraintes: x1-x2 <= 1\n", " -x1+x2 <= -2\n", " x1, x2 >= 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le tableau suivant r\u00e9sume les possibilit\u00e9s (*nb*: un probl\u00e8me non born\u00e9 est faisable!):\n", "\n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", "> \n", ">
primaldualoptimalinfaisablenon born\u00e9
optimalpossibleimpossibleimpossible
infaisableimpossiblepossiblepossible
non born\u00e9impossiblepossibleimpossible
\n", ">\n", "#### Notations matricielles\n", "\n", "#### Conditions de compl\u00e9mentarit\u00e9 des variables d'\u00e9cart\n", "\n", "**Probl\u00e8me**\n", "\n", "Supposons que l'on connaisse la solution optimale $(x_1^*,\\ldots,x_n^*)$ du probl\u00e8me, mais pas le tableau final dans l'algorithme du simplexe. Peut-on retrouver la solution optimale $(y_1^*,\\ldots,y_m^*)$ du probl\u00e8me dual de fa\u00e7on \u00e0 obtenir un certificat ?\n", "\n", "Pour voir cela, on va raffiner l'in\u00e9galit\u00e9 $w\\geq z$ sur des solutions $x_j$ et $y_i$ faisables en utilisant les variables d'\u00e9cart pour mesurer la diff\u00e9rence $w-z$.\n", "\n", "**Exercice**\n", "\n", "On veut introduire des variables d'\u00e9cart $t_i$ pour le probl\u00e8me dual:\n", "\n", "Donner une formule raisonable pour $t_i$.\n", "\n", "Exprimer $w-z$ en fonction des $x_i,\\ y_i,\\ s_i,\\ t_i$.\n", "\n", "**Solution**\n", "\n", "Par d\u00e9finition des variables d'\u00e9cart $s_i$, on a\n", "\n", "$$s_i=b_i-\\sum_{j=1}^na_{ij}x_j,$$\n", "\n", "et donc\n", "\n", "$$b_i=s_i+\\sum_{j=1}^na_{ij}x_j.$$\n", "\n", "De m\u00eame, par d\u00e9finition des variables d'\u00e9cart $t_j$ pour le probl\u00e8me dual, on a\n", "\n", "$$t_j=\\sum_{i=1}^ma_{ij}y_i-c_j,$$\n", "\n", "que l'on utilise pour exprimer $c_j$\n", "\n", "$$c_j=\\sum_{i=1}^ma_{ij}y_i-t_j.$$\n", "\n", "En rempla\u00e7ant dans l'expression de $w-z$, on obtient\n", "\n", "$$w-z=\\sum_{i=1}^mb_iy_i-\\sum_{j=1}^nc_jx_j=\\sum_{i=1}^ms_iy_i+\\sum_{i=1}^m\\left(\\sum_{j=1}^na_{ij}x_j\\right)y_i-\\sum_{j=1}^n\\left(\\sum_{i=1}^ma_{ij}y_i\\right)x_j+\\sum_{j=1}^nt_jx_j$$\n", "\n", "Qui se simplifie en:\n", "\n", "$$w-z=\\sum_{i=1}^ms_iy_i+\\sum_{j=1}^nt_jx_j.$$\n", "\n", "**Probl\u00e8me**\n", "\n", "Que peut-on d\u00e9duire de cette \u00e9galit\u00e9 ?\n", "\n", "**Th\u00e9or\u00e8me (Compl\u00e9mentarit\u00e9 des variables d'\u00e9cart)**\n", "\n", "Si $(x_1^*,\\ldots,x_n^*)$ est solution optimale du probl\u00e8me primal et $(y_1^*,\\ldots,y_m^*)$ est solution optimale du probl\u00e8me dual, alors:\n", "\n", "$$y_i^*=0\\textrm{ ou }s_i^*=0,\\textrm{ pour tout }i=1,\\ldots,m;$$\n", "\n", "$$x_j^*=0\\textrm{ ou }t_j^*=0,\\textrm{ pour tout }j=1,\\ldots,n.$$\n", "\n", "**Probl\u00e8me**\n", "\n", "Et maintenant ? Comment utiliser ce th\u00e9or\u00e8me pour trouver $(y_1^*,\\ldots,y_m^*)$?\n", "\n", "**Exercice (\\[Chvatal\\_LP\\]\\_ p. 64-65)**\n", "\n", "Si $(x_1^*,\\ldots,x_n^*)$ est une solution basique non d\u00e9g\u00e9n\u00e9r\u00e9e, alors les \u00e9quations que l'on tire du th\u00e9or\u00e8me de compl\u00e9mentarit\u00e9 ont une unique solution.\n", "\n", "Donc, lorsque la solution optimale du probl\u00e8me est non d\u00e9g\u00e9n\u00e9r\u00e9e, la technique que l'on a utilis\u00e9e dans les exercices permet toujours d'obtenir un certificat, pour le prix de la r\u00e9solution d'un syst\u00e8me de $m$ \u00e9quations lin\u00e9aires en $m$ variables.\n", "\n", "#### Interpr\u00e9tation g\u00e9om\u00e9trique de la dualit\u00e9\n", "\n", "**Exercice**\n", "\n", "Maximiser $x_1+x_2$\n", "\n", "Sous les contraintes\n", "\n", "$2x_1+x_2\\leq14$\n", "\n", "$-x_1+x_2\\leq8$\n", "\n", "$2x_1-x_2\\leq10$\n", "\n", "$x_1,x_2\\geq0.$\n", "\n", "1. Faire une figure dans le plan de la r\u00e9gion des solutions faisables.\n", "2. Donner le probl\u00e8me dual.\n", "3. Prendre $y_1=y_2=1,y_3=0$. Donner l'in\u00e9galit\u00e9 sur les $x_i$ correspondante, et repr\u00e9senter la r\u00e9gion qu'elle d\u00e9limite dans le plan.\n", "4. Donner quelques solutions faisables du probl\u00e8me dual.\n", "5. Tracer sur la figure les r\u00e9gions d\u00e9limit\u00e9es par les in\u00e9galit\u00e9s correspondantes.\n", "6. Calculer la solution optimale du primal et du dual.\n", "7. Les tracer sur la figure.\n", "8. Essayer d'interpr\u00e9ter g\u00e9om\u00e9triquement les th\u00e9or\u00e8mes que l'on a rencontr\u00e9s.\n", "\n", "#### Interpr\u00e9tation \u00e9conomique des variables duales\n", "\n", "**Probl\u00e8me**\n", "\n", "Mod\u00e8le \u00e9conomique d'une usine dont on veut maximiser le profit.\n", "\n", "Une papetterie produit et vend diff\u00e9rents types de papier: du papier kraft vendu au rouleau, du papier recycl\u00e9 vendu \u00e0 la ramette et du papier velin vendu \u00e0 la feuille. Pour cel\u00e0, elle dispose en d\u00e9but de mois d'un certain stock de mati\u00e8re premi\u00e8re: de l'eau (\u00e0 l'hectolitre), du chlore (au litre) du bois (\u00e0 la tonne), du vieux papier (au kilo), des fibres textiles (au ballot). Remplacer les stocks en fin de mois \u00e0 un certain co\u00fbt. Chaque type de papier n\u00e9cessite une certaine proportion de chaque mati\u00e8re premi\u00e8re. Par exemple, le chlore sert \u00e0 blanchir le papier; il n'y en a pas besoin pour le papier kraft; le papier velin est essentiellement produit \u00e0 partir de bois et de fibres textiles, etc. Le but est de pr\u00e9voir, pour le mois qui vient, quelle quantit\u00e9 de chaque papier il faut produire pour maximiser le profit de la papetterie.\n", "\n", "1. Mod\u00e9liser ce probl\u00e8me sous forme de programme lin\u00e9aire sous forme standard.\n", "\n", "> $x_j$ : quantit\u00e9 de produit $j$ fabriqu\u00e9e\n", ">\n", "> $c_j$ : prix de vente unitaire du produit $j$\n", ">\n", "> $a_{ij}$ : quantit\u00e9 de ressource $i$ consomm\u00e9e par unit\u00e9 de produit $j$ fabriqu\u00e9e\n", ">\n", "> $b_i$ : limites sur la disponibilit\u00e9 de la ressource $i$\n", ">\n", "> Maximiser:\n", ">\n", "> $$z=\\sum_{j=1}^nc_jx_j$$\n", ">\n", "> Sous les contraintes:\n", ">\n", "> $$\\sum_{j=1}^na_{ij}x_j\\leq b_i,\\textrm{ pour }i=1,\\ldots,m;$$\n", ">\n", "> $$x_j\\geq0,\\textrm{ pour }j=1,\\ldots,n.$$\n", "\n", "1. Quelle dimension (au sens physique) ont les variables $x_j$ , $b_i$ , $c_j$ , $a_{ij}$?\n", "2. On voudrait trouver une interpr\u00e9tation pour les variables $y_i$ dans le probl\u00e8me dual. Quelle dimension physique ont-elles? Qu'est-ce que cela sugg\u00e8re ?\n", "\n", "Cela sugg\u00e8re que $y_i$ mesure la valeur intrins\u00e8que de la ressource $i$ pour l'usine.\n", "\n", "**Th\u00e9or\u00e8me**\n", "\n", "S'il y a au moins une solution optimale $(x_1^*,\\ldots,x_m^*)$ non d\u00e9g\u00e9n\u00e9r\u00e9e, alors il existe $\\varepsilon$ strictement positif tel que lorsque $|t_i|\\leq\\varepsilon$ pour tout $i$, le programme lin\u00e9aire relax\u00e9:\n", "\n", "Maximiser:\n", "\n", "$$z=\\sum_{j=1}^nc_jx_j$$\n", "\n", "Sous les contraintes:\n", "\n", "$$\\sum_{j=1}^na_{ij}x_j\\leq b_i+t_i,\\textrm{ pour }i=1,\\ldots,m;$$\n", "\n", "$$x_j\\geq0,\\textrm{ pour }j=1,\\ldots,n.$$\n", "\n", "a une solution optimale, et la valeur optimale est\n", "\n", "$$z^*+\\sum_{i=1}^my_i^*t_i$$\n", "\n", "o\u00f9 $z^*$ est la valeur optimale du probl\u00e8me original et $(y_1^*,\\ldots,y_m^*)$ est la solution optimale du dual.\n", "\n", "Autrement dit, on peut mesurer l'esp\u00e9rance de gain au voisinage d'une solution optimale lorsque l'on relaxe certaines des contraintes: $y_i^*$ d\u00e9crit le gain que l'usine peut esp\u00e9rer en augmentant la quantit\u00e9 de ressource $i$ disponible.\n", "\n", "#### Probl\u00e8mes\n", "\n", "**Exercice**\n", "\n", "Utiliser le th\u00e9or\u00e8me de dualit\u00e9 pour v\u00e9rifier les solutions des probl\u00e8mes de programmation lin\u00e9aire que vous avez r\u00e9solu jusqu'ici.\n", "\n", "**Exercice**\n", "\n", "Un b\u00fbcheron a 100 hectares de bois de feuillus. Couper un hectare de bois et laisser la zone se r\u00e9g\u00e9n\u00e9rer naturellement co\u00fbte 10 kF par hectares, et rapporte 50 kF. Alternativement, couper un hectare de bois, et replanter avec des pins co\u00fbte 50 kF par hectares, et rapporte \u00e0 terme 120 kF. Sachant que le b\u00fbcheron n'a que 4000 kF en caisse au d\u00e9but de l'op\u00e9ration, d\u00e9terminer la meilleure strat\u00e9gie \u00e0 adopter et le profit escomptable.\n", "\n", "Maintenant, le b\u00fbcheron a aussi l'option d'emprunter pour augmenter son capital initial, et ce pour un taux d'int\u00e9r\u00eat total de $S$% sur la dur\u00e9e de l'op\u00e9ration. Alternativement, il peut d\u00e9cider d'investir son capital dans une autre activit\u00e9 rapportant $T$% sur la dur\u00e9e de l'op\u00e9ration. D\u00e9terminer, selon les valeurs de $S$ et $T$, la meilleure strat\u00e9gie \u00e0 adopter.\n", "\n", "**Exercice**\n", "\n", "Pouvez vous interpr\u00e9ter les conditions de compl\u00e9mentarit\u00e9 des variables d'\u00e9cart en termes \u00e9conomiques ?\n", "\n", "**Exercice**\n", "\n", "L'objectif est de d\u00e9montrer l'un des sens du th\u00e9or\u00e8me d'interpr\u00e9tation \u00e9conomique des variables duales. L'autre sens est plus technique, et ne sera pas abord\u00e9 ici; voir les r\u00e9f\u00e9rences pour les d\u00e9tails.\n", "\n", "Soit $z^*$ la valeur optimale du probl\u00e8me primal et $(y_1^*,\\ldots,y_m^*)$ une solution optimale quelconque du probl\u00e8me dual. Montrer que pour toute solution faisable $(x_1,\\ldots,x_n)$ du probl\u00e8me primal o\u00f9 l'on a relax\u00e9 chaque contrainte $i$ de la quantit\u00e9 $t_i$, on a\n", "\n", "$$\\sum_{j=1}^nc_jx_j\\leq z^*+\\sum_{i=1}^my_i^*t_i$$\n", "\n", "**Solution**\n", "\n", "Exprimons le fait que $(x_1,\\ldots,x_n)$ est solution faisable du probl\u00e8me avec les contraintes relax\u00e9es:\n", "\n", "$$\\sum_{j=1}^na_{ij}x_j\\leq b_i+t_i$$\n", "\n", "Donc:\n", "\n", "$$\\sum_{i=1}^my_i^*\\left(\\sum_{j=1}^na_{ij}x_j\\right)\\leq\\sum_{i=1}^my_i^*b_i+\\sum_{i=1}^my_i^*t_i=w^*+\\sum_{i=1}^my_i^*t_i=z^*+\\sum_{i=1}^my_i^*t_i$$\n", "\n", "On a trouv\u00e9 le terme de droite voulu.\n", "\n", "> Reste \u00e0 trouver le terme de gauche, ce que l'on fait avec une inversion de somme similaire \u00e0 celle qui a \u00e9t\u00e9 utilis\u00e9e dans les d\u00e9monstrations pr\u00e9c\u00e9dentes.\n", ">\n", "> $$\\sum_{i=1}^my_i^*\\left(\\sum_{j=1}^na_{ij}x_j\\right)=\\sum_{j=1}^n\\left(\\sum_{i=1}^ma_{ij}y_i^*\\right)x_j\\geq\\sum_{j=1}^nc_jx_j$$\n", "\n", "**Exercice**\n", "\n", "Construire un exemple montrant que la conclusion du th\u00e9or\u00e8me est fausse si l'hypoth\u00e8se de non d\u00e9g\u00e9n\u00e9rescence de la solution optimale est omise.\n", "\n", "## Applications de la programmation lin\u00e9aire\n", "\n", "## Combinatoire Polyh\u00e9drale\n", "\n", "## Synth\u00e8se\n", "\n", "On a vu plusieurs mod\u00e8les g\u00e9n\u00e9raux pour faire de l'optimisation:\n", "\n", "1. Programmation lin\u00e9aire\n", " 1. Algorithme du simplexe\n", " Efficace en pratique (quasiment lin\u00e9aire), non polynomial en th\u00e9orie" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " 2. Algorithme de l'ellipso\u00efde\n", " Polynomial, mais non efficace en pratique\n", "\n", " 3. M\u00e9thode des points int\u00e9rieurs\n", " Plus ou moins efficace que le simplexe selon les cas\n", "\n", " 4. Th\u00e9or\u00e8me de dualit\u00e9 $\\Longrightarrow$ Certification, optimisation, co\u00fbts marginaux, \u2026\n", " 5. Mais: solutions dans $\\mathbb{Q}$\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "2. Probl\u00e8mes de flots\n", " 1. Algorithme de Ford-Fulkerson\n", " Polynomial $O(n^3)$. Plus efficace que le simplexe." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " 2. Th\u00e9or\u00e8me de dualit\u00e9 (flots/coupes)\n", " 3. Th\u00e9or\u00e8me d'int\u00e9gralit\u00e9\n", " $\\Longrightarrow$ Algorithmes et th\u00e9or\u00e8mes min-max sur des probl\u00e8mes discrets.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "3. R\u00e9seaux de transports\n", " 1. Algorithme du simplexe pour les r\u00e9seaux\n", " 2. Th\u00e9or\u00e8me de dualit\u00e9 (co\u00fbts marginaux)\n", " 3. Th\u00e9or\u00e8me d'int\u00e9gralit\u00e9\n", "\n", "## TP\n", "\n", "### Programmation lin\u00e9aire\n", "\n", "**Exercice: Algorithme du simplexe**\n", "\n", "1. T\u00e9l\u00e9charger le [fichier annexe](../_images/programmation_lineaire.py) contenant les utilitaires et exemples du cours.\n", "2. Effectuer avec Sage les exercices marqu\u00e9s \"TP\" ci-dessus.\n", "\n", "**Exercice: Complexit\u00e9 au pire de l'algorithme du simplexe**\n", "\n", "Exp\u00e9rimentez avec le programme lin\u00e9aire de Klee Minty\n", "<Klee\u2013Minty\\_cube>. Pour la description pr\u00e9cise du programme lin\u00e9aire, voir par exemple la r\u00e9f\u00e9rence externe de Greenberg, Harvey J.\n", "\n", "Ajouter une fonction construisant ce programme lin\u00e9aire serait un bon mini-projet pour une premi\u00e8re contribution \u00e0 Sage.\n", "\n", "**Programmes lin\u00e9aires mixtes et probl\u00e8mes SAT**\n", "\n", "On consid\u00e8re une formule bool\u00e9enne, comme par exemple:\n", "\n", "$$F = \\left(A\\vee B\\right)\\wedge\\left(\\neg\\left(C\\wedge D\\right)\\vee A\\vee\\neg D\\right)$$\n", "\n", "On voudrait savoir si $F$ est satisfiable (c'est-\u00e0-dire si l'on peut choisir des valeurs Vrai/Faux pour A, B, C, D telles que la formule devienne vraie).\n", "\n", "\\#. Peut-on se ramener \u00e0 la r\u00e9solution d'un programme lin\u00e9aire? D'un programme lin\u00e9aire mixte?\n", "\n", "1. Quelle est la complexit\u00e9?\n", "\n", "\\#. Tester la satisfiabilit\u00e9 de $F$ au moyen de \n", "MixedIntegerLinearProgram. On pourra voir \\[CMS\\_LP\\]\\_ pour\n", "\n", "des exemples d'utilisation.\n", "\n", "Note: pour r\u00e9soudre de tel syst\u00e8me, le plus naturel est d'utiliser depuis Sage des solveurs sp\u00e9cialis\u00e9s de formules bool\u00e9ennes. Voir la section [SAT Solvers](http://www.sagemath.org/doc/reference/sat/) du manuel de r\u00e9f\u00e9rence.\n", "\n", "### Combinatoire polyh\u00e9drale\n", "\n", "#### Application aux graphes\n", "\n", "**Exercice: flot maximal**\n", "\n", "Mod\u00e9lisation: on consid\u00e8re le probl\u00e8me (dit de flot) suivant:\n", "\n", "On a un r\u00e9seau de canalisations d'eau entre les noeuds $a, b,\n", "\\ldots{}, i$, o\u00f9 le nombre sur chaque ar\u00eate indique le d\u00e9bit maximal pouvant passer par cette canalisation. L'eau rentre par le sommet $a$ et ressort par le sommet $i$, sans perte ni cr\u00e9ation dans les noeuds interm\u00e9diaires. Quel d\u00e9bit d'eau maximal peut on faire passer entre $a$ et $i$?\n", "\n", "![](media/flot.svg)\n", "\n", "Indication: utiliser la fonction Digraph.flow.\n", "\n", "**Exercice: couplage maximal dans les graphes bipartis**\n", "\n", "Un *couplage* d'un graphe est un ensemble d'ar\u00eates de ce graphe deux \u00e0 deux disjointes. On recherche un couplage de taille maximale du graphe biparti suivant:\n", "\n", "![](media/biparti2.svg)\n", "\n", "\\#. Mod\u00e9liser ce probl\u00e8me sous la forme d'un programme lin\u00e9aire et le r\u00e9soudre. Quelle est la complexit\u00e9 de cette m\u00e9thode?\n", "\n", "\\#. Mod\u00e9liser ce probl\u00e8me sous la forme d'un probl\u00e8me de flot et le r\u00e9soudre. Quelle est la complexit\u00e9 de cette m\u00e9thode?\n", "\n", "**Exercice: couplage maximal dans les graphes**\n", "\n", "On recherche maintenant un couplage dans un graphe quelconque, comme:\n", "\n", "![](media/graphe.svg)\n", "\n", "Mod\u00e9liser ce probl\u00e8me sous la forme d'un programme lin\u00e9aire et le r\u00e9soudre. Quelle est la complexit\u00e9 de cette m\u00e9thode?\n", "\n", "Comme dans l'exemple pr\u00e9c\u00e9dent, de tr\u00e8s nombreux probl\u00e8mes (durs) sur les graphes (coloration, recherche de clique, ...) se mod\u00e9lisent naturellement sous forme de programmes lin\u00e9aires (en entiers). Cela fait de la programmation lin\u00e9aire un outil de choix en th\u00e9orie des graphes, que ce soit en th\u00e9orie qu'en pratique. Pour explorer plus ce th\u00e8me, voir \\[CMS\\_LP\\]\\_.\n", "\n", "#### Matrices bistochastiques et th\u00e9or\u00e8me de Birkhoff-Von Neumann\n", "\n", "Une matrice $X=[x_{ij}]$ de taille $n\\times n$ est *bistochastique* si les coefficients $x_{ij}$ sont positifs et si la somme des coefficients sur chaque ligne et chaque colonne vaut $1$ :\n", "\n", "$$\\left[\\begin{array}{ccc}\n", "0,5 & 0,2 & 0,3\\\\\n", "0,01 & 0,7 & 0,29\\\\\n", "0,49 & 0,1 & 0,41\n", "\\end{array}\\right].$$\n", "\n", "$X$ est une *matrice de permutation* si sur chaque ligne et chaque colonne il y a exactement un $1$ et $n-1$ z\u00e9ros:\n", "\n", "$$\\left[\\begin{array}{ccc}\n", "0 & 1 & 0\\\\\n", "0 & 0 & 1\\\\\n", "1 & 0 & 0\n", "\\end{array}\\right].$$\n", "\n", "La matrice pr\u00e9c\u00e9dente correspond \u00e0 la permutation $(3,1,2)$.\n", "\n", "Clairement une matrice de permutation est une matrice bistochastique. R\u00e9ciproquement, les matrices de permutations sont les matrices bistochastiques \u00e0 coefficients entiers.\n", "\n", "**Exemple**\n", "\n", "En dimension $n=2$, quelles sont les matrices bistochastiques? quelles sont les matrices de permutations?\n", "\n", "**Th\u00e9or\u00e8me (Birkhoff-Von Neumann)**\n", "\n", "Toute matrice bistochastique est une combinaison lin\u00e9aire convexe de matrices de permutations.\n", "\n", "**Exercice**\n", "\n", "1. \u00c9crire la matrice bistochastique ci-dessus comme combinaison lin\u00e9aire convexe de matrices de permutations.\n", "2. D\u00e9montrer le lemme suivant en utilisant un r\u00e9seau de transport ad\u00e9quat:" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " Pour toute matrice $X=(x_{ij})$ bistochastique, on peut trouver une matrice de permutation $Y=(y_{ij})$ de fa\u00e7on \u00e0 ce que si $x_{ij}=0$ alors $y_{ij}=0$.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\\#. En d\u00e9duire une d\u00e9monstration constructive du th\u00e9or\u00e8me de Birkhoff-Von Neumann, que vous \u00e9crirez sous la forme d'un programme.\n", "\n", "\\#. Tester votre programme sur des matrices bistochastiques al\u00e9atoires de grande taille (comment en fabriquer?)\n", "\n", "#### Dualit\u00e9s cha\u00eenes/anticha\u00eenes dans les ordres partiels; th\u00e9or\u00e8me de Dilworth\n", "\n", "**Probl\u00e8me des visites guid\u00e9es.**\n", "\n", "Une compagnie propose $7$ visites guid\u00e9es dans la journ\u00e9e, not\u00e9es $a,b,c,d,e,f,g$, dont les horaires et dur\u00e9es sont fix\u00e9es. Si une visite (par ex. $a$) termine suffisament avant une autre (par exemple $c$), le guide de la premi\u00e8re visite peut encha\u00eener sur la deuxi\u00e8me; on notera alors $a\\rightarrow c$. En l\u2019occurence, voici tous les encha\u00eenements possibles:\n", "\n", "$a\\rightarrow c, a\\rightarrow d, a\\rightarrow f, a\\rightarrow g, b\\rightarrow c, b\\rightarrow g, d\\rightarrow g, e\\rightarrow f, e\\rightarrow g$.\n", "\n", "- Combien faut-il de guides au minimum dans cet exemple ?\n", "- Comment trouver le nombre minimum de guides n\u00e9cessaires dans le cas g\u00e9n\u00e9ral ?\n", "\n", "**D\u00e9finitions**\n", "\n", "Soit $P=(E,<)$ un ordre partiel.\n", "\n", "Une *cha\u00eene* $C$ de $P$ est un ensemble de sommets de $P$ deux-\u00e0-deux comparables:\n", "\n", "$$\\forall x,y\\in C, \\ x