Temario · Matemàtiques
OPOSGRATISOPOSGRATISTemario · Matemàtiques
📋 RESUM: Programació lineal • **Objectiu**: max/min una funció lineal $z=c^Tx$ sotmesa a restriccions lineals. • **Model**: variables de decisió, funció objectiu, restriccions ($\le,\ge,=$) i $x\ge0$. • **Regió factible**: intersecció de semiplans; és un conjunt **convex** (polígon/poliedre). • **Teorema fonamental**: si hi ha òptim i la regió és no buida i acotada, l’òptim s’assoleix en un **vèrtex**. • **Mètode gràfic (2 variables)**: dibuixar restriccions, trobar vèrtexs, avaluar $z$ o desplaçar rectes d’isobenefici/isocost. • **Casos**: solució única, múltiples (segment òptim), infactible (sense solucions), no acotat (sense màxim/mínim). • **Forma estàndard**: $\max c^Tx$ s.a. $Ax\le b$, $x\ge0$; amb **holgures** per passar a igualtats. • **Símplex**: algoritme que recorre vèrtexs millorant $z$ fins a òptim o detectant patologies. • **Dualitat**: a un primal li correspon un dual; dualitat feble ($c^Tx\le b^Ty$) i forta ($z^*=w^*$). • **Aplicacions**: producció, transport, dietes, mescles, planificació.
# PROGRAMACIÓ LINEAL
## 1. Introducció
La **programació lineal (PL)** és una tècnica d'optimització que permet maximitzar o minimitzar una funció lineal (funció objectiu) sotmesa a restriccions també lineals. Va néixer en el context de la logística i la planificació (Dantzig, anys 40) i actualment és essencial en gestió d'empreses, enginyeria, economia, transport i presa de decisions.
Una PL típica respon a preguntes del tipus: *com distribuir recursos limitats (temps, diners, matèries primeres) per obtenir el màxim benefici o el mínim cost?*
## 2. Modelització d'un problema de programació lineal
### 2.1 Elements del model
1. **Variables de decisió:** $x_1, x_2, \ldots, x_n$ (quantitats desconegudes a determinar). 2. **Funció objectiu:** maximitzar o minimitzar una expressió lineal: $$\text{max/min } z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$ 3. **Restriccions:** sistema d'inequacions lineals (i, sovint, igualtats): $$a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{in}x_n \le,\ge,=\ b_i\quad (i=1,\ldots,m)$$ 4. **Condicions de no negativitat:** $$x_j \ge 0\quad (j=1,\ldots,n)$$
### 2.2 Exemple (producció)
Una empresa fabrica dos productes A i B. Beneficis: 30€ i 20€ per unitat. Recursos: màquina (40 h) i mà d'obra (60 h). Cada A consumeix 1 h de màquina i 3 h de mà d'obra; cada B consumeix 2 h de màquina i 2 h de mà d'obra.
Variables: $x$ (unitats A), $y$ (unitats B).
Funció objectiu: $$\max z = 30x + 20y$$
Restriccions: $$\begin{cases} x + 2y \le 40 \\ 3x + 2y \le 60 \\ x \ge 0,\ y \ge 0 \end{cases}$$
## 3. Conjunts convexos i regió factible
### 3.1 Regió factible
El conjunt de solucions que compleixen totes les restriccions s'anomena **regió factible** o **polígon factible** (en 2 variables) i, en general, **poliedre convex**.
En dues variables, cada inequació defineix un semiplà i la regió factible és la intersecció de semiplans.
### 3.2 Convexitat
Un conjunt $C \subseteq \mathbb{R}^n$ és **convex** si: $$\forall x,y\in C,\ \forall \lambda\in[0,1],\ \lambda x + (1-\lambda)y \in C$$
La regió factible d'un sistema d'inequacions lineals és sempre convexa.
### 3.3 Vèrtexs o punts extrems
Un **punt extrem** (o vèrtex) és un punt que no es pot expressar com combinació convexa estricta de dos punts diferents del conjunt.
En PL, els candidats a òptim (si existeix) es troben als vèrtexs.
## 4. Teorema fonamental de la programació lineal
**Teorema:** Si un problema de programació lineal té solució òptima i la regió factible és no buida i acotada, llavors existeix almenys un vèrtex de la regió factible on la funció objectiu assoleix el seu màxim (o mínim).
Conseqüència: en 2 variables podem resoldre el problema **avaluant la funció objectiu als vèrtexs**.
## 5. Resolució gràfica (cas de dues variables)
### 5.1 Passos
1. Plantejar variables, funció objectiu i restriccions. 2. Dibuixar cada recta frontera (en igualtat) i determinar el semiplà corresponent. 3. Intersecar semiplans per obtenir la regió factible. 4. Trobar vèrtexs resolent sistemes de dues rectes i considerant eixos. 5. Calcular $z$ a cada vèrtex i triar el valor òptim.
### 5.2 Rectes d'isobenefici / isocost
La funció objectiu $z=c_1x+c_2y$ defineix rectes paral·leles: $$c_1x+c_2y=z$$
En maximització, es desplaça la recta en la direcció de creixement de $z$ fins tocar la regió factible.
### 5.3 Casos possibles
- **Solució única:** el contacte és en un únic vèrtex. - **Solucions múltiples:** la recta objectiu és paral·lela a un costat de la regió factible; qualsevol punt del segment és òptim. - **Problema infactible:** la regió factible és buida. - **Problema no acotat:** la funció objectiu pot créixer indefinidament (no hi ha màxim).
## 6. Formes estàndard i canònica
### 6.1 Forma estàndard (maximització)
$$\max z = c^T x\quad \text{s.a. } Ax \le b,\ x \ge 0$$
On $A$ és una matriu $m\times n$.
### 6.2 Variables d'holgura
Per convertir restriccions $\le$ en igualtats s'afegeixen **variables d'holgura** $s_i\ge 0$: $$a_{i1}x_1+\cdots+a_{in}x_n + s_i = b_i$$
Per restriccions $\ge$ s'usen variables d'excés i, en el mètode símplex, sovint variables artificials.
## 7. Mètode símplex (idea general)
Encara que a l'ensenyament preuniversitari sovint es treballa amb resolució gràfica, és important entendre la idea del **mètode símplex**:
- Comença en una **solució bàsica factible** (un vèrtex). - Itera movent-se per arestes del poliedre cap a vèrtexs que milloren la funció objectiu. - Acaba quan no hi ha millora possible (òptim) o detecta no acotació/infactibilitat.
Algebraicament, una solució bàsica s'obté seleccionant $m$ variables bàsiques (en un sistema de $m$ equacions) i fixant la resta a 0.
## 8. Dualitat
### 8.1 Concepte
A cada problema primal se li associa un **problema dual**. La dualitat proporciona: - Interpretació econòmica (preus ombra) - Criteris d'òptim - Eines de sensibilitat
### 8.2 Forma primal i dual (cas típic)
**Primal (max):** $$\max c^T x\ \text{s.a. } Ax \le b,\ x\ge 0$$
**Dual (min):** $$\min b^T y\ \text{s.a. } A^T y \ge c,\ y\ge 0$$
### 8.3 Teoremes de dualitat
- **Dualitat feble:** per a qualsevol $x$ factible i $y$ factible, $$c^T x \le b^T y$$ - **Dualitat forta:** si existeixen òptims, llavors els valors òptims coincideixen: $$z^*_{primal} = z^*_{dual}$$ - **Complementarietat:** $$y_i (b_i - (Ax)_i)=0\quad \text{i}\quad x_j ((A^T y)_j - c_j)=0$$
## 9. Sensibilitat (nocions)
En problemes reals, els coeficients $b$ (recursos) i $c$ (beneficis/costos) poden variar.
- **Preu ombra:** increment del valor òptim per unitat addicional d'un recurs (relacionat amb variables duals). - **Estabilitat de la base:** rangs de variació on la solució òptima no canvia de vèrtex.
## 10. Programació lineal enter (apunt)
Si s'exigeix que algunes variables siguin enteres, el problema esdevé **programació lineal enter**, molt més complex (NP-dur). Sovint es resol amb mètodes de tall (cuts) o branch and bound.
## 11. Aplicacions
- **Transport i assignació:** minimitzar costos de distribució. - **Mescles (blending):** maximitzar qualitat o benefici d'una combinació. - **Planificació:** horaris, producció, gestió d'estocs. - **Dieta:** minimitzar cost garantint nutrients mínims.
## 12. Aplicacions didàctiques
- Contextos reals (pressupost d'un viatge, producció d'un taller, combinació d'aliments). - Ús de GeoGebra per dibuixar semiplans i vèrtexs. - Interpretació de solucions: què significa una solució fraccionària? Quan cal enteritat? - Treball competencial: formular el model és sovint la part més important.
## 13. Conclusions
La programació lineal és un llenguatge matemàtic per optimitzar decisions sota restriccions. La convexitat de la regió factible i el teorema fonamental garanteixen que l'òptim (si existeix i és acotat) es troba en vèrtexs. La dualitat aporta interpretació i potència teòrica. És una eina clau en el pensament modelitzador i en l'educació matemàtica aplicada.
Has leído el desarrollo del tema. Para consolidar tu aprendizaje, estudia las flashcards asociadas con repetición espaciada (algoritmo SM-2), realiza simulacros de examen, y practica el supuesto práctico. Todo gratis y sin registro previo.