Programació lineal i dualitat: vèrtexs, simplex i certificats d'optimalitat

La programació lineal és el cas on tot funciona: la teoria és completa, els algorismes són eficients i, sobretot, hi ha certificats. Pots demostrar que una solució és òptima sense confiar en cap dibuix ni en cap programa, i aquesta és la part que val la pena entendre bé.

El model i la regió factible

Un programa lineal té objectiu i restriccions afins. Una forma estàndard de maximització és

$$\max\ c^{T}x \qquad\text{subjecte a}\qquad Ax\leq b,\quad x\geq 0.$$

La regió factible és un poliedre: una intersecció de semiespais. Hi ha exactament tres possibilitats i cal saber-les distingir: el problema pot ser inviable (la regió és buida), pot tenir valor no acotat, o pot assolir un òptim.

El resultat geomètric central és que, si la regió és un politop (acotat) no buit, una funció lineal hi assoleix el màxim en algun vèrtex. Això no vol dir que l'òptim sigui únic: pot ser tota una aresta o tota una cara, i llavors qualsevol punt d'aquesta cara és òptim. El que garanteix és que buscar entre els vèrtexs és suficient.

En forma d'igualtats amb variables no negatives, una solució bàsica fixa a zero tantes variables com calgui i resol amb columnes independents. Si totes les variables bàsiques resulten no negatives, és bàsica factible, i correspon a un vèrtex. Quan alguna variable bàsica val zero hi ha degeneració, que és la font de la majoria de patologies algorísmiques.

Símplex i punts interiors

El símplex recorre solucions bàsiques factibles millorant l'objectiu a cada pas, seguint arestes del poliedre. La degeneració pot provocar passos sense millora i, sense una regla anticicle, fins i tot cicles infinits. A la pràctica és molt ràpid, encara que el seu cas pitjor teòric sigui exponencial.

Els mètodes de punt interior segueixen trajectòries per dins de la regió, amb funcions barrera que penalitzen acostar-se a la frontera. Tenen garanties polinòmiques i solen guanyar en problemes molt grans.

Val la pena separar dues coses: formular bé el problema és anterior i independent de quin algorisme faràs servir per resoldre'l.

El dual

Del problema de maximització anterior en surt el dual:

$$\min\ b^{T}y \qquad\text{subjecte a}\qquad A^{T}y\geq c,\quad y\geq 0.$$

La relació bàsica es demostra en una línia. Per a qualsevol parella de punts factibles,

$$c^{T}x \leq y^{T}Ax \leq y^{T}b,$$

on la primera desigualtat surt de les restriccions duals i la no-negativitat de $x$, i la segona de les primals i la no-negativitat de $y$. Això és la dualitat feble: qualsevol solució factible del dual dona una cota superior al primal.

La dualitat forta per a programes lineals diu més: si el primal té òptim finit, el dual també, i els dos valors coincideixen. Això és el que converteix el dual en un certificat.

La complementarietat és la caracterització equivalent: a l'òptim, cada restricció primal no saturada obliga el seu multiplicador dual a ser zero, i cada variable primal positiva obliga la seva restricció dual a ser activa. En paraules: o la restricció és justa, o el seu preu és zero.

Modelitzar amb cura

Tres coses que es donen per fetes i no ho són:

• La no-negativitat és una hipòtesi del model, no una propietat de les variables. Si una variable pot ser negativa, escriu-la com a diferència de dues no negatives.
• Una igualtat es pot substituir per dues desigualtats, tot i que sovint és més eficient tractar-la directament.
• Si les decisions són indivisibles (quantes màquines, quins projectes), afegir integritat canvia el problema de manera essencial. Arrodonir la solució contínua pot violar restriccions o allunyar-se molt de l'òptim.

Exercici resolt: detectar un problema no acotat

És acotat el problema de maximitzar $x+y$ amb $x - y\leq 1$ i les dues variables no negatives?

No. Els punts de la diagonal $(t,t)$ compleixen totes les restriccions per a qualsevol $t\geq 0$: la diferència val zero, que no passa d'$1$, i les dues coordenades són no negatives. I l'objectiu val $2t$, que creix sense límit.

El que diu el dual. Quan el primal és no acotat, el dual ha de ser inviable: si tingués algun punt factible, la dualitat feble donaria una cota superior finita. Comprovem-ho: el dual seria minimitzar $u$ amb les condicions $u\geq 1$ i $-u\geq 1$, que exigeixen $u\geq 1$ i $u\leq -1$ alhora. Efectivament, no hi ha cap punt factible.

La moral. Les patologies del primal i del dual estan lligades, i mirar-se el dual sovint explica què està passant al primal.

Exercici resolt: verificar amb complementarietat

Al problema de l'exemple, comprova la complementarietat entre la solució primal $(2,2)$ i la dual $(2,1)$.

Restriccions primals. La primera, $x+y\leq 4$, es compleix amb igualtat ($4 = 4$): està saturada, i per tant el seu multiplicador pot ser positiu. Efectivament, $u = 2 > 0$. La segona, $x\leq 2$, també està saturada, i $v = 1 > 0$. Cap contradicció.

Variables primals. Totes dues són positives, o sigui que les dues restriccions duals han d'estar saturades. La primera, $u+v\geq 3$, val exactament $3$. La segona, $u\geq 2$, val exactament $2$. Correcte.

Conclusió. Totes les condicions de complementarietat es compleixen, cosa que confirma que la parella és òptima. Aquesta comprovació és equivalent a la igualtat de valors, però és més informativa: et diu quines restriccions manen i quines sobren.