Skip to main content

PL - Notes TD 2

Exercice 1​

Rappel du problème initial en forme standard

max⁡zsc    z=7I+9IIs1=8−I−IIs2=19−2I−3IIs3=4−II\begin{align*} \max z \\ sc \; \; z&= 7I+9II \\ s_1 &= 8-I-II\\ s_2&=19-2I-3II \\ s_3 &= 4-II \end{align*}

On choisit de faire rentrer IIII en base, on peut donc annuler II puisqu'il reste hors base.

s1=8−II≥0s2=19−3II≥0s3=4−II≥0⇒{II≤8II≤19/3II≤4\begin{align*} s_1 &=8-II \geq 0 \\ s_2 &= 19-3II \geq 0 \\ s_3 &= 4-II \geq 0 \end{align*} \Rightarrow \begin{cases} II \leq 8 \\ II \leq 19/3 \\ II \leq 4 \end{cases}

On fait donc sortir s3s_3 de la base puis on récrit le problème dans cette nouvelle base

z−9II=7Is1+II=8−Is2+3II=19−2Is3+II=4\begin{align*} z-9II&=7I \\ s_1 + II &= 8-I \\ s_2 + 3II &=19-2I \\ s_3 + II &= 4 \end{align*}

On veut maintenant exprimer les variables de la base selon les variables hors base (s3,I)(s_3, I).

z−9(4−s3)=7Is1+4−s3=8−Is2+3(4−s3)=19−2III=4−s3⇒z=36−s3+7Is1=4−I+s3s2=7−2I+3s3II=4−s3\begin{align*} z - 9(4-s_3) &= 7I \\ s_1+4-s_3 &= 8-I \\ s_2 + 3(4-s_3) &= 19-2I \\ II&=4-s_3 \end{align*} \Rightarrow \begin{align*} z&=36-s_3+7I \\ s_1&=4-I+s_3 \\ s_2 &=7-2I+3s_3 \\ II &= 4-s_3 \end{align*}

En maximisant IIII on obtient s3=0s_3=0 ainsi

s1=4−Is2=7−2III=4⇒{I≤4I≤7/2\begin{align*} s_1 &=4-I \\ s_2 &= 7-2I \\ II&=4 \end{align*} \Rightarrow \begin{cases} I \leq 4 \\ I \leq 7/2 \end{cases}

La prochaine étape sera donc de sortir s2s_2 de la base.

z=492+212s3−7s2+36−9s3s1=4+s3−72−32s3+s2I=72+32s3−s2II=4−s3⇒z=1212−7s2+32s3s1=12+s2−12s3I=72−s2+32s3II=4−s3\begin{align*} z&=\dfrac{49}{2} + \dfrac{21}{2} s_3 - 7 s_2 + 36 - 9 s_3 \\ s_1 &=4+s_3-\dfrac{7}{2}-\dfrac{3}{2}s_3+s_2 \\ I &=\dfrac{7}{2} + \dfrac{3}{2}s_3 - s_2 \\ II &= 4 -s_3 \end{align*} \Rightarrow \begin{align*} z &= \dfrac{121}{2} - 7s_2+\dfrac{3}{2}s_3 \\ s_1 &=\dfrac{1}{2}+s_2-\dfrac{1}{2}s_3 \\ I&=\dfrac{7}{2}-s_2+\dfrac{3}{2}s_3 \\ II&=4-s_3 \end{align*}

On fait rentrer s3s_3 dans la base puisque c‾s3>0\overline{c}_{s_3} > 0

s1=12s3+12≥0I=72+32s3≥0II=4−s3≥0⇒{s3≤1s3≥−7/3s3≤4\begin{align*} s_1 = \dfrac{1}{2}s_3 + \dfrac{1}{2} \geq 0 \\ I&=\dfrac{7}{2} + \dfrac{3}{2} s_3 \geq 0 \\ II &= 4 -s_3 \geq 0 \end{align*} \Rightarrow \begin{cases} s_3 \leq 1 \\ s_3 \geq -7/3 \\ s_3 \leq 4 \end{cases}

On fait donc sortir s1s_1 de la base. On exprime donc les variables de la base (I,II,s3)(I,II,s_3) en fonction des variables hors base (s1,s2)(s_1,s_2)

z−32s3=1212−7s2s1+12s3=12+s2I−32s3=72−s2II+s3=4\begin{align*} z-\dfrac{3}{2}s_3&= \dfrac{121}{2}-7s_2 \\ s_1 + \dfrac{1}{2} s_3 &= \dfrac{1}{2}+s_2 \\ I-\dfrac{3}{2}s_3 &=\dfrac{7}{2}-s_2 \\ II+s_3 &= 4 \end{align*}

Et donc au final {z=62−3s1−4s2s3=1−2s1+2s2I=5−3s1+2s2II=3−2s1+2s2\begin{cases} z=62-3s_1-4s_2 \\ s_3=1-2s_1+2s_2 \\ I=5-3s_1+2s_2 \\ II=3-2s_1+2s_2 \end{cases} Tous les coûts réduits sont négatif nous avons donc une solution.

0%