La programació lineal és una tècnica d'optimització matemàtica que s'utilitza per maximitzar o minimitzar una funció objectiu subjecta a un conjunt de restriccions lineals. Aquesta tècnica és àmpliament utilitzada en àrees com la investigació operativa, l'economia, l'enginyeria i la gestió.

1. Funció Objectiu: La funció que es vol maximitzar o minimitzar.
2. Variables de Decisió: Les variables que afecten la funció objectiu.
3. Restriccions: Les limitacions o condicions que les variables de decisió han de complir.
4. Regió Feasible: L'espai de solucions que compleixen totes les restriccions.

Un problema de programació lineal es pot expressar de la següent manera:

\[ \text{Maximitzar o Minimitzar } Z = c_1x_1 + c_2x_2 + \cdots + c_nx_n \]

Subjecte a:

\[ a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \leq b_1 \] \[ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \leq b_2 \] \[ \vdots \] \[ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n \leq b_m \]

\[ x_1, x_2, \ldots, x_n \geq 0 \]

Suposem que una empresa fabrica dos productes, A i B. Cada producte A genera un benefici de 3 unitats i cada producte B genera un benefici de 5 unitats. La producció de cada producte està limitada per les següents restriccions:

• Cada producte A requereix 1 unitat de matèria primera i 2 hores de mà d'obra.
• Cada producte B requereix 2 unitats de matèria primera i 1 hora de mà d'obra.
• La disponibilitat de matèria primera és de 8 unitats.
• La disponibilitat de mà d'obra és de 10 hores.

Formularem aquest problema com un problema de programació lineal.

\[ \text{Maximitzar } Z = 3x_1 + 5x_2 \]

\[ x_1 + 2x_2 \leq 8 \] (matèria primera) \[ 2x_1 + x_2 \leq 10 \] (mà d'obra) \[ x_1, x_2 \geq 0 \]

El mètode gràfic és útil per a problemes amb dues variables de decisió. Consisteix en:

1. Dibuixar les restriccions en un pla cartesià.
2. Identificar la regió feasible.
3. Determinar la funció objectiu i trobar el punt que maximitza o minimitza aquesta funció dins de la regió feasible.

El mètode Simplex és un algorisme iteratiu que es fa servir per resoldre problemes de programació lineal amb més de dues variables. Els passos bàsics són:

1. Convertir les desigualtats en igualtats afegint variables de slack.
2. Construir una taula Simplex inicial.
3. Iterar fins que es trobi la solució òptima.

Exemple de Mètode Simplex

Considerem el problema anterior. Convertim les desigualtats en igualtats afegint variables de slack \(s_1\) i \(s_2\):

\[ x_1 + 2x_2 + s_1 = 8 \] \[ 2x_1 + x_2 + s_2 = 10 \]

La taula Simplex inicial seria:

Iterem fins trobar la solució òptima.

Formuleu i resolgueu el següent problema de programació lineal utilitzant el mètode gràfic:

Una empresa fabrica dos tipus de joguines, X i Y. Cada joguina X genera un benefici de 4 unitats i cada joguina Y genera un benefici de 3 unitats. Les restriccions són:

• Cada joguina X requereix 2 unitats de material i 1 hora de mà d'obra.
• Cada joguina Y requereix 1 unitat de material i 2 hores de mà d'obra.
• La disponibilitat de material és de 10 unitats.
• La disponibilitat de mà d'obra és de 8 hores.

1. Funció Objectiu: Maximitzar \( Z = 4x_1 + 3x_2 \)
2. Restriccions: \[ 2x_1 + x_2 \leq 10 \] \[ x_1 + 2x_2 \leq 8 \] \[ x_1, x_2 \geq 0 \]

Dibuixeu les restriccions en un pla cartesià, identifiqueu la regió feasible i determineu el punt que maximitza la funció objectiu.

En aquesta secció, hem après els conceptes bàsics de la programació lineal, com formular un problema de programació lineal, i els mètodes per resoldre aquests problemes, incloent el mètode gràfic i el mètode Simplex. També hem vist un exemple pràctic i hem proposat un exercici per reforçar els conceptes apresos.