Algorithme

Soit un programme linéaire est donnée par un tableau canonique. L’algorithme simplex produit en effectuant des opérations de pivot successives qui donnent à chaque une meilleure solution de base; le choix de l’élément de pivot au niveau de chaque étape est largement déterminée par la condition que ce pivot améliorer la solution.

 

Exemple

Considérons le programme linéaire

Réduire

Z=-2 x - 3 y - 4 z\,

Subject à

\begin{align}<br /><br /><br />
  3 x + 2 y + z &\le 10\\<br /><br /><br />
  2 x + 5 y + 3 z &\le 15\\<br /><br /><br />
  x,\,y,\,z &\ge 0<br /><br /><br />
\end{align} » src= »https://lh6.googleusercontent.com/iHRlcmuwJp0eDKgIM7xFmwYmDBvp0AAzz3QZXtXD-0P-IQLkK-YVWFKLrQgb39N7KF3PNX0gxvCsNGYc-ZjrKmwYSK2N_AwtN42EG_Q-Ryp5CJTrALqjX2n6r_3QqtDLfLl6T5Rb » width= »154″ height= »76″ /></p>
<p dir=Avec l’addition de variables d’écart s et t, ceci est représenté par le tableau canonique

<br /><br /><br />
  \begin{bmatrix}<br /><br /><br />
    1 & 2 & 3 & 4 & 0 & 0 &  0 \\<br /><br /><br />
    0 & 3 & 2 & 1 & 1 & 0 & 10 \\<br /><br /><br />
    0 & 2 & 5 & 3 & 0 & 1 & 15<br /><br /><br />
  \end{bmatrix}<br /><br /><br />
 » src= »https://lh3.googleusercontent.com/9WzWJtXH8HfOvrtVVzSolqp1JI5S9A7lDhHNrYWqRUbpPFNk-QXuU0mdkJVKOy-zjHKDQ-f1yYfr_B3OnwxHgAorQqAWtuU1A8sf7DnI7zXqU7l2ogEVzq6XB5jZRk-vcTRmPqxi » width= »192″ height= »73″ /></p>
<p dir=où les colonnes 5 et 6 représentent les variables de base s et t et la solution de base correspondant est

x=y=z=0,\,s=10,\,t=15.

Les colonnes 2, 3 et 4 peuvent être sélectionnés en tant que colonnes de pivotement, pour cet exemple, la colonne 4 est sélectionné. Les valeurs de z résultant du choix des lignes 2 et 3 en tant que lignes de pivotement sont 10/1 et 15/3 = 10 = 5 respectivement. Parmi ceux-ci le minimum est de 5, de sorte que la ligne 3 doit être la ligne de pivot. Effectuer le pivot produit

<br /><br /><br />
  \begin{bmatrix}<br /><br /><br />
    1 & -\tfrac{2}{3} & -\tfrac{11}{3} & 0 & 0 & -\tfrac{4}{3} & -20 \\<br /><br /><br />
    0 &  \tfrac{7}{3} &   \tfrac{1}{3} & 0 & 1 & -\tfrac{1}{3} &  5  \\<br /><br /><br />
    0 &  \tfrac{2}{3} &   \tfrac{5}{3} & 1 & 0 &  \tfrac{1}{3} &  5<br /><br /><br />
  \end{bmatrix}<br /><br /><br />
 » src= »https://lh6.googleusercontent.com/zHTTb9B_i-yBNa4yhoP1OndGPi8CMpeoyxITRB2dWDIBIxFBW0aWW3jMz2Bsjci3Ie13K0GKFJV3sYb1gmmi6H1EbMyurxvYtgZ8_m-y2C9a1D3f9EpDVtyncm25-X0CZrUfcT88″ width= »265″ height= »73″ /></p>
<p dir=Maintenant, les colonnes 4 et 5 représentent les variables de base z et s et de la solution de base correspondant est

x=y=t=0,\,z=5,\,s=5.

Pour la prochaine étape, il n’y a aucune entrée positifs dans la ligne objectif et, en fait,

Z=-20 + \tfrac{2}{3} x + \tfrac{11}{3} y + \tfrac{4}{3} t

donc la valeur minimale de Z est de -20.

 

Pas encore de commentaire.

Laisser un commentaire

Techno95 |
MANJ |
TOUT SUR LE MAC |
Unblog.fr | Annuaire | Signaler un abus | Informatique11
| Cartiertechno
| Supermarketlady