Programa llineal dual

El dual d'un programa llineal (PL) donat és un atre PL que es deriva de el PL original (el primal) de la següent forma:

• Cada variable en el PL primal es convertix en una restricció en el PL dual;
• Cada restricció en el PL primal es convertix en una variable PL dual;
• La funció objectiu s'invertix – maximizar en el PL primal es convertix en minimisar en el PL dual i viceversa.

Construint el PL dual

Donat un PL primal, el següent algoritme pot ser utilisat per a construir el seu PL dual. El PL primal està definit per:

• Un conjunt de $n$ variables: $x_1,\dots ,x_n$
• Per a cada variable $x_i$, li correspon un signe de restricció – té que ser no negatiu ($x_i\ge 0$), no positiu ($x_i\le 0$) o irrestrica $x_i\in ℝ$.
• Una funció objectiu:$\text{maximizar}{c}_1{x}_1+\cdots +c_n{x}_n$
• Una llista de $m$ restriccions. Cada restricció $j$ és: $a_{j1}{x}_1+\cdots +a_{jn}{x}_n⪋b_j$ a on el símbol abans de $b_j$ pot ser $\ge$ o $\le$ o $=$.

El PL dual es construïx com seguix:

• Cada restricció en el primal es convertix en una variable en el dual, per lo que hi ha $m$ variables: $y_1,\dots ,y_m$.
• El constrenyiment de senyal de cada variable dual és "opost" al signe del seu primal constrenyiment. Per lo que “$\ge b_j$” es convertix en $y_j\le 0$, “$\le b_j$” es convertix en $y_j\ge 0$ i “$=b_j$” es convertix en $y_j\in ℝ$.
• La funció objectiva dual és$\text{minimizar }{b}_1{y}_1+\cdots +b_m{y}_m$
• Cada variable primal es convertix en una restricció dual, per lo que hi ha $n$ restriccions. El coeficient d'una variable dual en la restricció dual és el coeficient de la seua variable primal en la seua restricció primal, per lo que cada restricció $i$ és: $a_{1i}{y}_1+\cdots +a_{mi}{y}_m⪋c_i$ a on el símbol abans de $c_i$ és similar a la restricció en variable $i$ en el PL primal, per lo que $x_i\le 0$ es convertix en “$\le c_i$”, $x_i\ge 0$ es convertix en “$\ge c_i$” i $x_i\in ℝ$ es convertix en “$=c_i$”.

D'este algoritme, és fàcil de vore que el dual del dual és el primal.

Formulació vectorial

Si totes les restriccions tenen el mateix signe, és possible representar l'algoritme de dalt en una manera més curta utilisant matrius i vectores. La següent taula mostra la relació entre varis tipos de PL primales i duals.

Primal	Dual	Nota
Maximizar ${𝐜}^T𝐱$ subjecte a $A𝐱\ge 𝐛,𝐱\ge \mathrm{𝟎}$	Minimisar ${𝐛}^T𝐲$ subjecte a $A^T𝐲\ge 𝐜,𝐲\ge \mathrm{𝟎}$	És cridat problema dual "simètric"
Maximizar ${𝐜}^T𝐱$ subjecte a $A^T𝐲\le 𝐛$	Minimisar ${𝐛}^T𝐲$ subjecte a $A^T𝐲=𝐜,𝐲\ge \mathrm{𝟎}$	És cridat problema dual “asimètric”
Maximizar ${𝐜}^T𝐱$ subjecte a $A𝐛=𝐛,𝐱\ge \mathrm{𝟎}$	Minimisar ${𝐛}^T𝐲$ subjecte a $A^T𝐲\ge 𝐜$

Vore també

• Programació llineal
• Investigació d'operacions