Programació lineal

📋 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ó.