Programmation linéaire

La programmation linéaire est la branche de la programmation mathématique qui est

Conçu pour résoudre des problèmes d'optimisation où toutes les contraintes comme volonté que les objectifs sont exprimés en fonction linéaire. Il a été développé par George B. Denting en 1947. Son  application antérieure était uniquement liée aux activités de la seconde guerre mondiale. Toutefois  son importance a été reconnue et il est venu occuper une place proéminente dans le l'industrie et le commerce.

La programmation linéaire est une technique permettant de prendre des décisions sous certitude, c'est-à-dire; quand tous les cours d'options disponibles pour une organisation sont connus et l'objectif de l'entreprise et ses contraintes sont quantifiées. Cette ligne de conduite est choisie toutes les alternatives possibles qui donnent les résultats optimaux. La programmation linéaire peut également être utilisé comme mécanisme de vérification et de contrôle pour vérifier l'exactitude et la fiabilité des décisions qui sont prises uniquement sur la base de l'expérience du gestionnaire à l'aide d'un modèle mathématique.

Un problème de programmation linéaire peut être défini comme le problème de maximiser ou de minimiser une fonction linéaire soumise à des contraintes linéaires. Les contraintes peuvent être des égalités ou des inégalités. Voici un exemple simple.

Trouver les nombres x1 et x2 qui maximisent la somme x1 + x2 sous réserve des contraintes ;

x1 ≥ 0, x2 ≥ 0, and    x1 + 2x2 ≤ 4

                                   4x1 + 2x2 ≤ 12

−x1 + x2 ≤ 1

Dans ce problème il ya deux inconnues, et cinq contraintes. Toutes les contraintes sont

Inégalités et elles sont tous linéaires en ce sens que chacune implique une inégalité dans la fonction linéaire des variables. Les deux premières contraintes, x1 ≥ 0 et x2 ≥ 0, sont spéciales.

Ceux-ci sont appelés contraintes de non-négativité et sont souvent trouvés dans les problèmes de la programmation linéaire.

Les autres contraintes sont alors appelées les contraintes principales. La fonction à

Maximisée (ou minimisée) est appelée fonction objective. Ici, la fonction objective est

x1 + x2.

Puisqu'il n'y a que deux variables, nous pouvons résoudre ce problème en dessinant l'ensemble des points dans le plan qui satisfait toutes les contraintes (appelées ensemble de contraintes) et puis trouver quel point de cet ensemble maximise la valeur de la fonction objective.

Chaque contrainte d'inégalité est satisfaite par un demi-plan de points, et l'ensemble des contraintes est l’intersection de tous les demi-plans. Dans le présent exemple, l'ensemble de contraintes est la figure ombrée dans la figure 1.

Nous cherchons le point (x1, x2), qui atteint le maximum de x1 + x2 comme (x1, x2) gammes

Sur cet ensemble de contraintes.

La fonction x1 + x2 est constante sur les lignes de pente -1, pour exemple la ligne x1 + x2 = 1, et comme nous déplaçons cette ligne plus loin de l'origine vers le haut et vers le droit, la valeur de x1 + x2 augmente. Par conséquent, nous cherchons la ligne de pente -1 qui est

Le plus éloigné de l'origine et touche toujours la contrainte fixée. Cela se produit à l'intersection des lignes x1 + 2x2 = 4 et 4x1 + 2x2 = 12, à savoir, (x1, x2) = (8/3, 2/3).

 La valeur de la fonction objective y est (8/3) + (2/3) = 10/3.

Il est facile de voir en général que la fonction objective, étant linéaire, prend toujours sa valeur maximale (ou minimale) à un point d'angle de la contrainte, à condition que l’ensemble des contraintes est limité. Parfois, le maximum se produit le long d'un bord ou un visage entier de la contrainte fixée, mais le maximum se produit également à un point d'angle.

Tous les problèmes de programmation linéaire ne sont pas résolus si facilement. Il peut y avoir beaucoup de variables et de nombreuses contraintes. Certaines variables peuvent être contraintes à être non négatives et d'autres sans contrainte. Certaines des principales contraintes peuvent être des égalités et d'autres inégalités.

Cependant, deux classes de problèmes, appelés ici le problème maximum standard et le problème minimum standard, jouent un rôle particulier. Dans ces problèmes, toutes les variables sont des contraintes à être non négatives, et toutes les contraintes principales sont les inégalités.

On donne un vecteur m, b = (b1, ..., bm) ^T, un vecteur n, c = (c1, ..., cn) ^T et un vecteur

m × n matrice,

des nombres réels.

Le problème maximum standard: Trouver un n-vecteur, x = (x1,...,xn)^T ,  à maximiser

c^Tx = c₁x₁ + ··· + c_nx_n

Sous réserve des contraintes :

Exemple 1 : EXEMPLE D'UNE SOLUTION GRAPHIQUE  DE LA PROGRAMMATION LINEAIRE

La méthode simplexe :
Lorsque nous sommes en présence de plus de deux produits , la méthode de simplexe est la seule méthode permettant de trouver la combinaison  de produits qui rend optimal la fonction économique .
le principe de résolution nécessite un certain nombre d'étapes contenu au travers de l’algorithme du simplexe:   
exemple d'une résolution en ligne : L'algorithme du simplexe de George Dantzig
L'algorithme du simplexe de George Dantzig est une technique à la fois fondamentale et très populaire pour les problèmes de programmation linéaire. Ainsi, étant donné un ensemble d'inégalités linéaires sur n variables réelles, l'algorithme permet de trouver la solution optimale pour une fonction objectif, qui est elle aussi linéaire (l'algorithme fonctionne encore quand la fonction est croissante en chacune de n variables).
Essayer en ligne  l'algorithme du simplexe de George Dantzig