Home

Federica EU

1/20

Antonio Sforza » 13.Ottimizzazione lineare: il modello duale

Schema della lezione

In questa lezione si illustra il modello duale che assume una grande importanza nella teoria della programmazione matematica.

I modelli primale e duale vengono introdotti partendo da un noto problema di ottimizzazione (il problema della dieta alimentare) che consente di costruire i due modelli in modo comparato e comprenderne agevolmente il rapporto.

Viene presentata quindi la corrispondenza tra modello primale e modello duale, con la relativa trasformazione, in forma standard e non standard, e vengono descritti i principali teoremi del modello duale.

Il modello duale

Il modello duale e la teoria della dualità assumono una grande importanza nella teoria della programmazione matematica.

In questo testo i modelli primale e duale vengono introdotti partendo da un problema di ottimizzazione che consente di costruire i due modelli in modo comparato e comprenderne agevolmente il rapporto. A questo scopo si presta il classico problema della dieta che consiste nella determinazione della composizione di un insieme di componenti alimentari che ottimizzi una prefissata funzione obiettivo. Il problema viene presentato sia dal punto di vista di un cliente del mercato, sia da quello di un consulente farmaceutico che propone l’acquisto di pillole.

Il problema della dieta

Problema primale e problema duale

Problema primale

$\text{Max }z=9x_1+19x_2$

s.a.

$\left\begin{array}{rrrrrr}x_1\leq 3.5\\x_2\leq 3\\2x_1+3x_2\leq 6\\2x_1+x_2\leq 5\\x_1+3x_2\leq 2.7\\2x_1+2x_2\leq 2.2\end{array}$

$x_j\geq 0\hspace{1,5cm}j=1,...,2$

Problema duale

$\text{Min } v=3.5u_1+3u_2+6u_3+5u_4+2.7u_5+2.2u_6$

$\left\begin{array}{rr}u_1\hspace{1,cm}+2u_3+2u_4-u_5-2u_6\geq 9\\ u_2+3u_3+u_4+3u_5+2u_6\geq 19\end{array}$

$u_j\geq 0\hspace{1cm}j=1, ..., 6$

Soluzione del problema primale

Soluzione del problema duale

Corrispondenze Primale (max) – Duale (min) in forma standard

Trasformazione primale – duale non in forma standard

Se ci sono vincoli di qualunque tipo (≤, =, ≥) e variabili di qualunque tipo (≥ 0, non ristrette nel segno segno, ≤ 0 ) il sistema non è in forma standard. Con opportune operazioni algebriche sui vincoli e sulle variabili il sistema può essere trasformato in forma standard.

Vincoli:

a) Un vincolo ≥ diventa ≤ cambiando di segno a tutti gli elementi;
b) Un vincolo di = si sdoppia in 2 vincoli ( uno di ≤ e uno di ≥); il vincolo di ≥ viene trattato come al punto a).

Variabili:

a) Variabile x_j ≤ 0. Si definisce una variabile x’_j = x_j → x’_j ≥ 0;
b) Variabile x_k n.r.s. Si pone x_k = x’_k – x”_k (x’_k ≥ 0, x”_k ≥ 0).

Dal modello primale così ottenuto in forma standard si ottiene un modello duale in forma standard, che non è però duale del modello originario. Su di esso si possono effettuare operazioni algebriche “opposte” a quelle effettuate sul primale per generare un modello non in forma standard, duale dell’originario primale non in forma standard. Queste operazioni sono descritte nel testo di riferimento.

Corrispondenze Primale (max) – Duale (min) non in forma standard

Teoremi del duale

Teorema del duale in forma debole

Si dimostra che, assegnata una coppia di problemi l’uno duale dell’altro, un qualunque valore di funzione obiettivo v del modello primale (max) è sempre non maggiore di un qualunque valore di funzione obiettivo z del modello duale (min) (z ≤ v).

Teorema del duale in forma forte

Si dimostra che, assegnata una coppia di problemi l’uno duale dell’altro, il valore ottimo di funzione obiettivo z* del primale è uguale al valore di funzione obiettivo v* del duale (z* = v*).

Teorema dello scarto complementare

È possibile dimostrare che, assegnata una coppia di problemi l’uno duale dell’altro, indicando con u_i e con r_j le variabili slack rispettivamente del primale e del duale, vale all’ottimo la seguente relazione, detta dello scarto complementare, tra le variabili del modello primale e del modello duale:

u_i*y_i* = 0 ……… ( i = 1, m)

x_j*r_j* = 0 ……… ( j = 1, n)

Un esempio di modelli primale – duale

$\text{Max }z=3x_1+4x_2+5x_3 + x_4$

$\left\begin{array}{lrrrrr}2x_1+x_2+2x_3+x_4\leq 10\\\hspace{1cm}3x_2+4x_3\hspace{1cm}\leq 11\\4x_1+2x_2+x_3+2x_4\leq 13\\x_1+x_2+x_3+x_4\hspace{1cm}\geq 0\\ \hspace{1,5cm} x_1,x_2,x_3,x_4\geq 0\end{array}$

$\text{Min }v=10u_1+11u_2+13u_3+2u_4$

$\left\begin{array}{rrrrr}2u_1\hspace{1cm}+4u_3+u_4\geq 3\\ u_1+3u_2+2u_3+u_4\geq 4\\2u_1+4u_2+u_3+u_4\geq 5\\u_1\hspace{1,5cm}2u_3+u_4\geq 1\\u_1,u_2,u_3\geq 0, u_4\leq 0\end{array}$

Soluzioni del primale e del duale

Le soluzioni del primale generate dall’algoritmo del Simplesso hanno i seguenti valori:

z₁ = 6, z₂ = 10, z₃ = 13.75 , z₄ = 20.05 , z₅ = 21.06 (soluzione ottima).

Le soluzioni del duale generate dall’algoritmo del simplesso hanno i seguenti valori:

v₁ = 65, v₂ =21.44, v₃ = 21.06 (soluzione ottima).

La soluzione basica ammissibile ottima del primale è:

x₁ = 2.39, x₂ = 0.56, x₃ = 2.33, y₄ = 3.3, x₄ = y₁ = y₂ = y₃ = 0.

La soluzione basica ammissibile ottima del duale è:

u₁ = 0.61, u₂ = 0.83, u₃ = 0.44, r₄ = 0.5, u₄ = r₁ = r₂ = r₃ = 0.

Nella slide successiva questi valori sono diagrammati al fine di dare una visualizzazione grafica dei teoremi del duale.

Andamento dei valori di v e z nelle iterazioni dell’algoritmo del Simplesso

Teorema del duale in forma debole

Si può vedere dal grafico che un qualunque valore di funzione obiettivo v del modello primale è sempre non maggiore di un qualunque valore di funzione obiettivo z del modello duale (z ≤ v).

Teorema del duale in forma forte

Si può vedere dal grafico che il valore ottimo di funzione obiettivo z* del primale è uguale al valore di funzione obiettivo v* del duale (z* = v*).