{"id":138,"date":"2009-07-24T13:44:50","date_gmt":"2009-07-24T11:44:50","guid":{"rendered":"http:\/\/wp1.fredptitgars.net\/index.php\/2009\/07\/24\/le-simplex\/"},"modified":"2009-07-24T13:44:50","modified_gmt":"2009-07-24T11:44:50","slug":"le-simplex","status":"publish","type":"post","link":"https:\/\/fredptitgars.ovh\/?p=138","title":{"rendered":"Le Simplex"},"content":{"rendered":"

M\u00e9thode graphique<\/h2>\n

Le probl\u00e8me:<\/strong><\/p>\n

Entreprise fabrique des voitures de type A et B. Il y a trois ateliers:
\n– Atelier 1 fabrique les moteurs.
\n– Atelier 2 fabrique les carrosseries.
\n– Atelier 3 effectue les assemblages.<\/p>\n

Les capacit\u00e9s de travail des trois ateliers sont:
\n– 450 heures par mois pour l’atelier 1.
\n– 350 heures par mois pour l’atelier 2.
\n– 200 heures par mois pour l’atelier 3.<\/p>\n

B\u00e9n\u00e9fices unitaires d\u00e9gag\u00e9s par l’entreprise sont::
\n– 4000 francs pour les voitures de type A.
\n– 8000 francs pour les voitures de type B.<\/p>\n

Le tableau ci-apr\u00e8s indique les temps unitaires de chaque op\u00e9ration pour chaque type de voitures
\n
Utilisation des ressources pour fabriquer les voitures<\/p>\n\n\n\n\n\n\n
<\/td>\nVoiture type A<\/td>\nVoiture type B<\/td>\n<\/tr>\n
Atelier Moteur<\/td>\n1<\/td>\n3<\/td>\n<\/tr>\n
Atelier Carrosserie<\/td>\n2<\/td>\n1<\/td>\n<\/tr>\n
Atelier assemblages<\/td>\n1<\/td>\n1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Question: Optimiser la production de fa\u00e7on \u00e0 obtenir le b\u00e9n\u00e9fice le
\nplus \u00e9lev\u00e9 possible
\n<\/em><\/p>\n

Mise en \u00e9quation<\/strong><\/p>\n

Soit:
\n– x1 production mensuelle de voitures de type A.
\n– x2 production mensuelle de voitures de type B.<\/p>\n

Programme lin\u00e9aire d\u00e9crivant le probl\u00e8me:
\n– les contraintes de disponibilit\u00e9 d’heures de travail de chaque atelier (contraintes explicites)
\n– la fonction \u00e9conomique z que l’on veut maximiser.<\/p>\n

Exemple de l’atelier 1<\/p>\n

    \n
  1. il faut 1h par voiture A et 3h par voiture B : 1*x1+3*x2<\/li>\n
  2. maximum 450h
    \nce qui donne : <\/li>\n<\/ol>\n

    \n$1 \\cdot x_1<\/em> +3 \\cdot x_2<\/em> \\le 450$\n
    $x_1<\/em>+3x_2<\/em> \\le 450$\n
    $2x_1<\/em> + x_2<\/em> \\le 350$\n
    $x_1<\/em> + x_2<\/em> \\le 200$\n
    $x_1<\/em> \\Rightarrow 0, x_2<\/em> \\Rightarrow 0$<\/p>\n

    Pour maximiser le b\u00e9n\u00e9fice<\/p>\n

    $Max(z)=4000x_1<\/em>+8000x_2<\/em>$\n<\/math><\/p>\n

    Principe
    \n
    probl\u00e8me peut \u00eatre \u00e9tudi\u00e9 dans R2:
    \n
    2 variables x1, x2
    \n
    Point M du plan : production qcq r\u00e9alisable ou non.
    \n
    R\u00e9alisable si : int\u00e9rieur au polygone des contraintes<\/p>\n

    \n$x_1<\/em>+3x_2<\/em> \\le 450$\n
    $2x_1<\/em> + x_2<\/em> \\le 350$\n
    $x_1<\/em> + x_2<\/em> \\le 200$\n
    $x_1<\/em> \\Rightarrow 0, x_2<\/em> \\Rightarrow 0$\n<\/math><\/p>\n

    \"graph1-7.png\"<\/p>\n

    sur ce graph:
    \n– x1 en abscisse
    \n– x2 en ordonn\u00e9e<\/p>\n

    On trace les \u00e9quations:
    \n
    2×1+x2<350, cette \u00e9quation est modifi\u00e9 en rempla\u00e7ant le signe < par =. Il suffira de prendre toutes les valeurs en dessous de la droite\n\n\nPour tracer on met x1=0 et on calcul x2 et inversement. Cela nous donne 2 points qui suffit pour tracer une droite.\n
    On raie les points au dessus de cette droite car ils ne satisfont pas ma premi\u00e8re contrainte. Pour rayer les points, on hachure
    \n
    on fait pareil pour les trois in\u00e9quations, donc pour les trois contraintes
    \nmaintenant, ce qui reste en non hachur\u00e9, ce sont tous les points solutions
    \ncet ensemble de points repr\u00e9sente une figure g\u00e9om\u00e9trique qui est un polyedre ici 0, A, B, C, D
    \n
    Tous les points dans la zone blanche (y compris sur les traits) sont solutions
    \n
    Calcul du b\u00e9nef max:
    \n– le b\u00e9n\u00e9fice vaut z = 4000 x1 + 8000 x2 on divise par 4000 pour simplifier.
    \n– le b\u00e9n\u00e9fice vaut z (z’) = x1 + 2 x2<\/p>\n

    Cette droite passe par 0, en effet si je produit 0 voiture A et 0 voiture B, le b\u00e9n\u00e9fice sera de 0,
    \n
    on fixe 2 variables x1=0, x2=0 => calcul de z qui est \u00e9gale \u00e0 0.
    \n
    Pour tracer cette droite, il nous faut un autre point avec z toujours=0.
    \n
    Exemple : x1=200
    \n
    0=200+2×2, => x2=-100
    \n
    Ensuite, on cherche une droite parall\u00e8le a cette droite initiale qui soit la plus haute possible. Il suffit de monter pour \u00eatre parall\u00e8le \u00e0 cette droite et cela tant que vous restez dans le polyedre et le dernier point est le point B(75;125) qui est la meilleur solution.
    \n
    On produira 75 voiture A et 125 voiture B, le b\u00e9n\u00e9fice est de <\/p>\n

    M\u00e9thode des tableaux<\/h2>\n

    \u00c9tape 1<\/p>\n

    On reprend les \u00e9quations de d\u00e9part:<\/p>\n

    \n$x_1<\/em>+3x_2<\/em> \\le 450$\n
    $2x_1<\/em> + x_2<\/em> \\le 350$\n
    $x_1<\/em> + x_2<\/em> \\le 200$\n
    $Max(z)=4000x_1<\/em>+8000x_2<\/em>$\n
    $x_1<\/em> \\Rightarrow 0, x_2<\/em> \\Rightarrow 0$<\/p>\n

    \u00c9tape 2<\/p>\n

    Pour ne pas avoir d’in\u00e9quation on pose:\n– $x_1<\/em>+3x_2<\/em>+x_3<\/em>=450$ avec $x_3<\/em>$>0 c’est identique \u00e0 $x_1<\/em>+3x_2<\/em> \\le 450$\n– x3 repr\u00e9sente ici le temps disponible pour l’atelier moteur <\/p>\n

    Ce qui nous donne pour toutes les \u00e9quations:<\/p>\n

    $x_1<\/em>+3x_2<\/em> +x_3<\/em>= 450$\n
    $2x_1<\/em> + x_2<\/em> +x_4<\/em>=350$\n
    $x_1<\/em> + x_2<\/em> +x_5<\/em>= 200$\n
    $Max(z)=x_1<\/em>+2x_2<\/em>$<\/p>\n

    Sous la forme matriciel<\/p>\n

    $\\left[ \\beginarray<\/em>rrrrr<\/em>\n1 & 3 & 1 & 0 & 0 \\\\\n2 & 1 & 0 & 1 & 0 \\\\\n1 & 1 & 0 & 0 & 1 \\endarray<\/em> \\right] \\cdot \n\\left[ \\beginarray<\/em>r<\/em>\nx_1<\/em> \\\\\nx_2<\/em> \\\\\nx_3<\/em> \\\\\nx_4<\/em> \\\\\nx_5<\/em> \\endarray<\/em> \\right] =\n\\left[ \\beginarray<\/em>r<\/em>\n450 \\\\\n350 \\\\\n200 \\endarray<\/em> \\right]$<\/p>\n

    $Max (z)= \\left[ \\beginarray<\/em>rrrrrr<\/em>\n1 & 2 & 1 & 0 & 0 & 0 \\endarray<\/em> \\right] \\cdot\n\\left[ \\beginarray<\/em>r<\/em>\nx_1<\/em> \\\\\nx_2<\/em> \\\\\nx_3<\/em> \\\\\nx_4<\/em> \\\\\nx_5<\/em> \\endarray<\/em> \\right]$<\/p>\n

    <\/math><\/p>\n

    \u00c9tape 2<\/p>\n

    \"graph2-7.png\"
    \nAu d\u00e9part on initialise avec un b\u00e9n\u00e9fice de 0 donc z=0
    \n
    D\u00e9roulement de l’algorithme
    \n
    On regarde la plus grande valeur dans la ligne delta j (\u2206j) donc tout en bas. Ici c’est 2.
    \n
    La colonne 2 vas entrer en base.<\/p>\n

    Chercher la ligne du pivot
    \n
    Pour cela, on divise chaque Bi par la valeur de la ligne pivot, ici la colonne 2 (qu’on vient de choisir) <\/p>\n

    \n$450<\/em> \\over 3<\/em>$ $=150$,\n$350<\/em> \\over 1<\/em>$ $= 350$,\n$200<\/em> \\over 1<\/em>$ $= 200$\n<\/math><\/p>\n

    On retient le plus petit ici 150, la ligne 1.<\/p>\n

    Le pivot est la colonne 2 ligne 1.
    \n
    Pour la suite on \u00e9crit i=2 \u00e0 gauche, l\u00e0 ou on avait i=3.<\/p>\n

    La colonne 2 sort, donc elle passe en ligne \u00e0 la place de la ligne que l’on traite.
    \n
    Pour la ligne du pivot, on divise la ligne par la valeur du pivot:<\/strong>
    \n
    Nouvelle valeur= ancienne valeur \/ Valeur du pivot<\/em><\/p>\n

    La ligne du pivot: 1,3,1,0,0,0,450
    \n
    Le pivot 3 (colonne 2)
    \n
    Ce qui donne 1\/3;1;1\/3;0;0;150 <\/p>\n\n\n\n\n\n
    L1 (origine)<\/td>\n1<\/td>\n3<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n450<\/td>\n<\/tr>\n
    L1 (calcul)<\/td>\n1\/3<\/td>\n3\/3<\/td>\n1\/3<\/td>\n0\/3<\/td>\n0\/3<\/td>\n450\/3<\/td>\n<\/tr>\n
    L1 (r\u00e9sultat)<\/td>\n1\/3<\/td>\n1<\/td>\n1\/3<\/td>\n0<\/td>\n0<\/td>\n150<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    Pour les lignes suivantes<\/strong>:
    \n
    nouvelle valeur = ancienne valeur moins 1\/3 de la ligne 1
    \n
    nouvelle valeur = ancienne valeur – \u03b1 * par l\u2019ancienne valeur de la ligne pivot
    \n
    Le coefficient alpha se calcule sur la colonne du pivot\u00a0:
    \n
    \u03b1 = ancienne ligne \/ ancienne ligne du pivot<\/em><\/p>\n

    La deuxi\u00e8me ligne:
    \n
    \u03b1 = 1\/3<\/p>\n\n\n\n\n\n
    L2 (origine)<\/td>\n2<\/td>\n1<\/td>\n0<\/td>\n1<\/td>\n0<\/td>\n350<\/td>\n<\/tr>\n
    L2 (calcul)<\/td>\n2 -1\/3*1<\/td>\n1 -1\/3*3<\/td>\n0 – 1\/3*1<\/td>\n1 -1\/3*0<\/td>\n0 -1\/3*0<\/td>\n350-1\/3*450<\/td>\n<\/tr>\n
    L2 (r\u00e9sultat)<\/td>\n5\/3<\/td>\n0<\/td>\n-1\/3<\/td>\n1<\/td>\n0<\/td>\n200<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    La troisi\u00e8me ligne
    \n
    \u03b1 = 1\/3<\/p>\n\n\n\n\n\n
    L3 (origine)<\/td>\n1<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n200<\/td>\n<\/tr>\n
    L3 (calcul)<\/td>\n1 \u20131* (1\/3)<\/td>\n1 \u2013 1*1<\/td>\n0 \u2013 1*(1\/3)<\/td>\n0 \u2013 1\/3*0<\/td>\n1 \u2013 1\/3*0<\/td>\n200 \u2013 1\/3*450<\/td>\n<\/tr>\n
    L3 (r\u00e9sultat)<\/td>\n2\/3<\/td>\n0<\/td>\n-1\/3<\/td>\n0<\/td>\n1<\/td>\n50<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    Les deltat (r)
    \n
    \u03b1 = 2\/3<\/p>\n\n\n\n\n\n
    rj (origine)<\/td>\n1<\/td>\n2<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n0<\/td>\n<\/tr>\n
    rj (calcul)<\/td>\n1 \u2013 2\/3*1<\/td>\n2 \u2013 2\/3*0<\/td>\n0 \u2013 (2\/3)*1<\/td>\n0 \u2013 2\/3*0<\/td>\n0 \u2013\u00a02\/3*1<\/td>\n0 \u2013\u00a02\/3*450<\/td>\n<\/tr>\n
    rj (r\u00e9sultat)<\/td>\n1\/3<\/td>\n0<\/td>\n-2\/3<\/td>\n0\u00a0<\/td>\n0\u00a0<\/td>\n300<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    ce qui nous donne:
    \n<\/p>\n\n\n\n\n\n\n\n\n\n
    <\/td>\nj=1<\/td>\nj=2<\/td>\nj=3<\/td>\nj=4<\/td>\nj=5<\/td>\n <\/td>\nBi<\/td>\n<\/tr>\n
    i=2<\/td>\n1\/3<\/td>\n1<\/td>\n1\/3<\/td>\n0<\/td>\n0<\/td>\n <\/td>\n150<\/td>\n<\/tr>\n
    i=4<\/td>\n5\/3<\/td>\n0<\/td>\n-1\/3<\/td>\n1<\/td>\n0<\/td>\n <\/td>\n200<\/td>\n<\/tr>\n
    i=5<\/td>\n2\/3<\/td>\n0<\/td>\n-1\/3<\/td>\n0<\/td>\n1<\/td>\n <\/td>\n50<\/td>\n<\/tr>\n
    <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n<\/tr>\n
    $\\Delta$j<\/td>\n1\/3<\/td>\n0<\/td>\n-2\/3<\/td>\n0<\/td>\n0<\/td>\n <\/td>\n-300<\/td>\n<\/tr>\n
    <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\n <\/td>\nz=-300<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    <\/math>
    \nOn recommence l’algorithme<\/p>\n

    La plus grande valeur dans les delta est la colonne 1 de valeur 1\/3.
    \n\nOn recalcule les $\\Delta$<\/p>\n

    $150<\/em> \\over 1<\/em> \\over 3<\/strong>$ $=150$, \n$200<\/em> \\over 5<\/em> \\over 3<\/strong>$ $= 120$, \n$200<\/em> \\over 2<\/em> \\over 3<\/strong>$ $= 75$<\/p>\n

    <\/math>
    \nLe plus petit 75<\/p>\n

    Notre pivot est la ligne 3 colonne 1: (2\/3).
    \nPour la suite on \u00e9crit i=1 \u00e0 gauche, l\u00e0 ou on avait i=5<\/p>\n

    La ligne Pivot (Ligne 3)<\/p>\n

    On divise la ligne 3 par le pivot soit 2\/3:
    \nLigne de pivot : 2\/3;0;-1\/3;0;1;50
    \nLe pivot 2\/3
    \nce qui donne: 1; 0; -0.5; 0; 1.5; 75 <\/p>\n\n\n\n\n\n
    L3 (origine)<\/td>\n2\/3<\/td>\n0<\/td>\n-1\/3<\/td>\n0<\/td>\n1<\/td>\n50<\/td>\n<\/tr>\n
    L3 (calcul)<\/td>\n(2\/3)\/(2\/3)<\/td>\n0\/(2\/3)<\/td>\n(-1\/3)\/(2\/3)<\/td>\n0\/(2\/3)<\/td>\n1\/(2\/3)<\/td>\n50\/(2\/3)<\/td>\n<\/tr>\n
    L3 (r\u00e9sultat)<\/td>\n1<\/td>\n0<\/td>\n-1\/2<\/td>\n0<\/td>\n3\/2<\/td>\n75<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    Calcul de la ligne 1
    \n\u03b1 = (1\/3)\/(2\/3)=1\/2<\/p>\n\n\n\n\n\n
    L1 (origine)<\/td>\n1\/3<\/td>\n1<\/td>\n1\/3<\/td>\n0<\/td>\n0<\/td>\n150<\/td>\n<\/tr>\n
    L1 (calcul)<\/td>\n1\/3-(1\/2)*(2\/3)<\/td>\n1-(1\/2)*0<\/td>\n1\/3-(1\/2)*0<\/td>\n0-(1\/2)*0<\/td>\n0-(1\/2)*0<\/td>\n150-(1\/2)*50<\/td>\n<\/tr>\n
    L1 (r\u00e9sultat)<\/td>\n0<\/td>\n1<\/td>\n1\/2<\/td>\n0<\/td>\n-1\/2<\/td>\n125<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    Calcul de la ligne 2
    \n\u03b1 = (5\/3)\/(2\/3)=5\/2<\/p>\n\n\n\n\n\n
    L1 (origine)<\/td>\n5\/3<\/td>\n0<\/td>\n-1\/3<\/td>\n1<\/td>\n0<\/td>\n200<\/td>\n<\/tr>\n
    L1 (calcul)<\/td>\n5\/3-(5\/3)*(2\/3)<\/td>\n0-(5\/2)*0<\/td>\n-1\/3-(5\/2)*(1\/3)<\/td>\n1-(5\/2)*0<\/td>\n0-(5\/2)*1<\/td>\n200-(5\/2)*50<\/td>\n<\/tr>\n
    L1 (r\u00e9sultat)<\/td>\n0<\/td>\n0<\/td>\n1\/2<\/td>\n1<\/td>\n-5\/2<\/td>\n75<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    \nLes $\\Delta$\n\u03b1 = (1\/3)\/(2\/3)=(1\/2)<\/p>\n\n\n\n\n\n
    $\\Delta$j (origine)<\/td>\n1\/3<\/td>\n0<\/td>\n-2\/3<\/td>\n0<\/td>\n0<\/td>\n-300<\/td>\n<\/tr>\n
    $\\Delta$j (calcul)<\/td>\n1\/3-(1\/3)*(2\/3)<\/td>\n0-(1\/2)*0<\/td>\n-2\/3-(1\/2)*(-1\/3)<\/td>\n0-(1\/2)*1<\/td>\n0-(1\/2)*1<\/td>\n-300-(1\/2)*50<\/td>\n<\/tr>\n
    $\\Delta$j (r\u00e9sultat)<\/td>\n0<\/td>\n0<\/td>\n-1\/2<\/td>\n0<\/td>\n-1\/2<\/td>\n-325<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

    <\/math><\/p>\n

    Tous les deltas sont n\u00e9gatifs ou nuls, donc l’algorithme s’arr\u00eate.
    \n\"graph3-5.png\"<\/p>\n

    x1=75, x2=125,x3=0, x4=75, x5=0, z=325
    \nLes ateliers 1 et 2 sont utilis\u00e9s au maximum, l’atelier 3 dispose d’une r\u00e9serve de 75<\/p>\n

    On peut finir en reprenant les \u00e9quations de d\u00e9part et surtout le b\u00e9n\u00e9fice max:<\/p>\n

    \n$x_1<\/em>+3x_2<\/em> \\le 450$ (atelier 1)\n
    $2x_1<\/em> + x_2<\/em> \\le 350$ (atelier 2)\n
    $x_1<\/em> + x_2<\/em> \\le 200$ (atelier 3)\n
    $Max(z)=4000x_1<\/em>+8000x_2<\/em>$\n
    $x_1<\/em> \\ge 0, x_2<\/em> \\ge 0$<\/p>\n

    $x_1<\/em>=75` x_2<\/em>=125$\n
    $75+3 \\cdot 125 = 450$ (atelier 1, au max)\n
    $2 \\cdot 75 + 125 = 275$ (atelier 2, pas au max)\n
    $75 + 125 = 200$ (atelier 3, au max)\n
    $1300000 = 4000 \\cdot 75 + 8000 \\cdot 125$<\/p>\n

    <\/math><\/p>\n","protected":false},"excerpt":{"rendered":"

    M\u00e9thode graphique Le probl\u00e8me: Entreprise fabrique des voitures de type A et B. Il y a trois ateliers: – Atelier 1 fabrique les moteurs. – Atelier 2 fabrique les carrosseries. – Atelier 3 effectue les assemblages. Les capacit\u00e9s de travail des trois ateliers sont: – 450 heures par mois pour l’atelier 1. – 350 heures […]<\/p>\n","protected":false},"author":2,"featured_media":135,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[],"class_list":["post-138","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-rcp101-recherche-operationnelle-et-aide-a-la-decision"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts\/138","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=138"}],"version-history":[{"count":0,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/posts\/138\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=\/wp\/v2\/media\/135"}],"wp:attachment":[{"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=138"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=138"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fredptitgars.ovh\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=138"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}