Modéliser un programme linéaire

Un programme linéaire à $n$ variables et à $m$ contraintes est de la forme suivante :

$$\left \lbrace \begin{array}{l l l l l l l l l l l l} max & c... ... + & \ldots & + & a_{mn}x_n & \leq & b_m\\ \end{array}\right.$$

Soient $x$ le vecteur à $n$ lignes et $1$ colonne

$$\left[ \begin{array}{l} x_1\\ \vdots\\ x_n \end{array}\right]$$

$c$ le vecteur à $n$ lignes et $1$ colonne

$$\left[ \begin{array}{l} c_1\\ \vdots\\ c_n \end{array}\right]$$

Alors on exprime la valeur de la fonction objectif avec le produit scalaire $c^tx$. Soit $A$ la matrice à $m$ lignes et $n$ colonnes

$$\left( \begin{array}{l l l l l} a_{11} & \ldots & a_{1i} & \... ...{m1} & \ldots & a_{mi} & \ldots & a_{mn}\\ \end{array}\right)$$

et $b$ le vecteur à $m$ lignes et $1$ colonne

$$\left[ \begin{array}{l} b_1\\ \vdots\\ b_m \end{array}\right]$$

Alors les contraintes s'écrivent

$$Ax \leq b$$

Finalement, un programme linéaire est de la forme

$$\left \lbrace \begin{array}{l l l l} max & c^tx\\ s.c. & Ax & \leq & b\\ \end{array}\right.$$