Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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 primale


Soluzione del problema primale


Soluzione del problema duale


Soluzione del problema duale


Soluzione del problema duale


Soluzione del problema duale


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


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 xj ≤ 0. Si definisce una variabile x’j =  xj x’j0;
  • b) Variabile xk n.r.s. Si pone xk = x’k – x”k (x’k0, 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


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 ui e con rj 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:

ui*yi* = 0 ……… ( i = 1, m)

xj*rj* = 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:

z1 = 6, z2 = 10, z3 = 13.75 , z4 = 20.05 , z5 = 21.06 (soluzione ottima).

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

v1 = 65, v2 =21.44, v3 = 21.06 (soluzione ottima).

La soluzione basica ammissibile ottima del primale è:

x1 = 2.39, x2 = 0.56, x3 = 2.33, y4 = 3.3, x4 = y1 = y2 = y3 = 0.

La soluzione basica ammissibile ottima del duale è:

u1 = 0.61, u2 = 0.83, u3 = 0.44, r4 = 0.5, u4 = r1 = r2 = r3 = 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*).


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion