Appunti di Ottimizzazione

Riassunto gerarchico delle nozioni del corso 2005-2006 di ottimizzazione del Prof. Marco Gaviano - Università degli Studi di Cagliari, Facoltà di Scienze Matematiche Fisiche Naturali, Dipartimento di Matematica ed Informatica, Corso di Laurea in Informatica

• scopo della Ricerca Operativa
  • Fornire strumenti matematici di supporto alle attività decisionali in cui occorre gestire e coordinare attività e risorse al fine di effettuare le scelte migliori per raggiungere un determinato obiettivo
• fasi per la risoluzione di un problema
  • esame della situazione reale e raccolta delle informazioni;
  • formulazione del problema (individuazione delle variabili e scelta della funzione obbiettivo da massimizzare o minimizzare);
  • costruzione del modello matematico che rispecchi il più possibile il problema reale;
  • soluzione e verifica del modello matematico;
  • verifica delle soluzioni ottenute in rapporto al problema reale (si verifica se la funzione obbiettivo offre vantaggi e si verifica la rappresentatività del modello).
• criteri di modellizzazione
  • raccogliere il maggior numero di elementi che descrivono la situazione reale.
  • costruire un modello il più vicino possibile alla realtà.
  • condurre rigorosamente la fase di costruzione del modello.
  • non costruire un modello sofisticato quando uno semplice è sufficiente.
  • non dimenticare che un modello è un'astrazione della realtà.
• problema generale della Programmazione Lineare (PL o LP)
  • consiste nella ricerca dell'ottimo (minimo o massimo) di una funzione lineare di variabili soggette a vincoli lineari (equazioni o disequazioni) chiamate vincoli.
  • funzione obbiettivo
    • è la funzione da ottimizzare
• formulazione generale del problema PL
  • min (max) z = ∑_j=1,n (c_jx_j)
  • soggetta a:
    • ∑_j=1,n (a_ijx_j) = d_i , per i = 1, ..., m₁
    • ∑_j=1,n (a_ijx_j) ≥ d_i , per i = m₁ + 1, ..., m₁ + m₂
    • ∑_j=1,n (a_ijx_j) ≤ d_i , per i = m₁ + m₂ + 1, ..., m₁ + m₂ + m₃
    • x_j ≥ 0 , j = 1, ..., n
  • dove:
    • M={1,2,...,m}: insieme degli indici dei vincoli;
    • N={1,2,...,n}: insieme degli indici delle variabili;
    • M_i sottoinsieme di M;
    • N_i sottoinsieme di N;
    • A=(a_ij), i ∈ M, j ∈ N: matrice m x n di numeri reali;
    • a_j: la j-ma colonna di A;
    • a_i: l'i-ma riga di A;
    • x = [x₁,...,x_n]^T variabili decisionali
    • c = [x₁,...,x_n]^T coefficienti della funzione obiettivo
    • d = [x₁,...,x_m]^T termini noti dei vincoli
  • il problema di massimo è equivalente al problema di minimo perché:
    • minimo di f(x) = - massimo di -f(x)
    • possiamo ricondurre tutte le disequazioni allo stesso tipo moltiplicando per -1 quelle di tipo diverso
    • questo ci consente di ricondurre i problemi PL ad una forma standard
• formulazione canonica del problema PL
  • min z = ∑_j=1,n (c_jx_j)
  • soggetta a:
    • ∑_j=1,n (a_ijx_j) ≥ d_i , per i = 1, ..., m
    • x_j ≥ 0 , j = 1, ..., n
• formulazione standard del problema PL
  • min z = ∑_j=1,n (c_jx_j)
  • soggetta a:
    • ∑_j=1,n (a_ijx_j) = d_i , per i = 1, ..., m
    • x_j ≥ 0 , j = 1, ..., n
• formulazione canonica compatta del problema PL
  • min z = c^Tx
  • soggetta a:
    • Ax ≥ d
    • x ≥ 0
• formulazione standard compatta del problema PL
  • min z = c^Tx
  • soggetta a:
    • Ax = d
    • x ≥ 0
• PL dalla forma generale alla forma canonica e viceversa:
  • α) ∑_j=1,n (a_ijx_j) ≤ d_i ⇔ ∑_j=1,n (-a_ijx_j) ≥ -d_i
  • β) ∑_j=1,n (a_ijx_j) = d_i ⇔ { ∑_j=1,n (a_ijx_j) ≥ d_i ; ∑_j=1,n (-a_ijx_j) ≥ -d_i }
  • γ) x_j libera ⇔ { x_j = x_j⁺ - x_j^- ; x_j⁺, x_j^- ≥ 0}
    • una variabile è libera se non è vincolata in segno
• PL dalla forma generale alla forma standard e viceversa:
  • γ) x_j libera ⇔ { x_j = x_j⁺ - x_j^- ; x_j⁺, x_j^- ≥ 0}
    • una variabile è libera se non è vincolata in segno
  • δ) ∑_j=1,n (a_ijx_j) ≤ d_i ⇔ { ∑_j=1,n (a_ijx_j) + s_i = d_i , s_i ≥ 0 }
  • φ) ∑_j=1,n (a_ijx_j) ≥ d_i ⇔ { ∑_j=1,n (a_ijx_j) - t_i = d_i , t_i ≥ 0 }
• variabili di scarto (slack variable) s_i
  • variabili x_i^s che vengono introdotte per poter trasformare un problema PL dalla forma canonica a quella standard
  • non devono influenzare la funzione da ottimizzare, pertanto avranno coefficiente nullo nella z=c^Tx
• variabili di surplus t_i
  • variabili x_i^s che vengono introdotte per poter trasformare un problema PL dalla forma canonica a quella standard
  • non devono influenzare la funzione da ottimizzare, pertanto avranno coefficiente nullo nella z=c^Tx
• programma, soluzione ammissibile, feasible solution
  • una n-pla di valori che soddisfa tutti i vincoli compresi quelli di non-negatività
• soluzione non ammissibile
  • una n-pla di valori che soddisfa tutti i vincoli eccetto quelli di non negatività
• soluzione ottimale (programma ottimale)
  • un programma finito (tutte le variabili sono finite) che minimizza la funzione obiettivo z
  • c^Tx ≤ c^Ty , ∀y ∈ Rⁿ : Ay = d,y ≥ 0
• ipotesi su un problema PL
  • Il sistema di equazioni Ax = d è supposto composto di equazioni linearmente indipendenti (m<n, rango di A uguale ad m) ed avente più di una soluzione.
• base di un problema PL
  • Dato il sistema Ax = d dove A è una matrice mxn di rango m e m < n si dice base di A una collezione di m colonne di A linearmente indipendenti.
  • il sistema Ax = d può essere riscritto come [B|N]·[x_B|x_N]^T = d
    • x_B : variabili in base (m variabili associate con le colonne della base B)
    • x_N : variabili fuori base (non in base, secondarie)
• soluzione di base (programma di base)
  • la soluzione di base associata a B è il vettore [x_B|x_N] soluzione del sistema Ax = Bx_B + Nx_N = d ottenuta ponendo x_B = B⁻¹d e x_N = 0.
• soluzione di base ammissibile (SBA)
  • soluzione di base per la quale vale: x_B = B⁻¹d ≥ 0
• soluzione ottimale di base
  • per il teorema fondamentale della PL, corrisponde alla soluzione ottimale
• soluzione di base degenere
  • una base alla quale corrisponde una soluzione di base con almeno una variabile in base nulla
• teorema fondamentale della PL
  • dato un problema PL in forma standard:
    • se esiste almeno un programma finito, esso ha almeno una programma di base
    • se ha almeno un programma ottimale finito, allora ha almeno un programma ottimale di base
• numero massimo delle soluzioni di base in un problema PL
  • numero di basi = programmi di base = (ⁿ _m) = n! / m!(n-m)!
  • a causa della grande quantità di calcoli necessari anche per problemi di dimensione modesta si sono sviluppate apposite tecniche risolutive
• come si distinguono i vincoli di un problema PL
  • sono funzioni lineari (equazioni o disequazioni) che delimitano piani (o iperpiani) la cui intersezione delimita la regione di ammissibilità delle soluzioni
• passaggi con cui si riscrive un problema PL utilizzando la conoscenza di una base B
  • si parte dal problema PL in forma standard
  • Ax = [B|N]·[x_B|x_N]^T = Bx_B + Nx_N = d
  • x_B = B^-1d - B^-1Nx_N = B^-1d - Yx_N
  • Y = B^-1N = [y₁ y₂ ... y_n-m]
  • z = c^Tx = [c_B|c_N]·[x_B|x_N]^T = c_Bx_B + c_Nx_N = c_BB^-1d - (c_BY - c_N)x_N
  • x_B = B^-1d , z = c_BB^-1d
  • x_B = x_B - Yx_N , z = z - (c_BY - c_N)x_N
  • x_B = x_B - ∑_j∈NN x_jy_j, z = z - (c_B∑_j∈NN x_jy_j - ∑_j∈NN c_jx_j)
  • z_j = c_By_j , j ∈ N_N
  • min z = z - ∑_j∈NN (z_j - c_j)x_j
• formulazione del problema PL in forma standard utilizzando la conoscenza di una soluzione di base B
  • min z = z - ∑_j∈NN (z_j - c_j)x_j
  • x_B = x_B - ∑_j∈NN x_jy_j
  • x ≥ 0
• condizioni affinché una soluzione di base sia ottimale
  • dato un programma di base ammissibile associato con un base B, una condizione necessaria e sufficiente perché esso sia ottimale è che: z_j - c_j ≤ 0 per ogni j ∈ N_N
• condizione necessaria e sufficiente affinché un programma di base ottimale sia unico
  • z_j - c_j < 0 per ogni j ∈ N_N
• condizioni affinché una soluzione di un problema PL non abbia una soluzione finita
  • i vincoli del problema sono tra loro incompatibili e di conseguenza la regione di ammissibilità è vuota
• idea generale dell'algoritmo di simplesso
  • è una procedura iterativa che genera una successione di programmi di base in cui la funzione obbiettivo decresce
  • geometricamente cerca le soluzioni nei vertici della regione di ammissibilità determinata dai vincoli
• relazioni su cui si basa l'algoritmo del simplesso
  • si riformula il problema PL in forma standard utilizzando la conoscenza di una soluzione di base B:
    • min z = z - ∑_j∈NN (z_j - c_j)x_j
    • x_B = x_B - ∑_j∈NN x_jy_j
    • x ≥ 0
  • si considerano i seguenti teoremi:
    • 1) dato un programma ammissibile di base associato ad una base B, se z_k - c_k > 0 e y_k ≤ 0 per qualche k ∈ N_N, non esiste alcun programma ottimale
    • 2) dato un programma ammissibile di base associato ad una base B, se per k ∈ N_N, z_k - c_k > 0 e y_sk ≤ 0 per almeno un s ∈ N_B, allora un nuovo programma di base ammissibile può essere ottenuto dando a z un nuovo valore z' ≤ z
    • 3) dato un programma ammissibile di base associato ad una base B, una condizione necessaria e sufficiente perché esso sia ottimale è che z_j - c_j ≤ 0 per ogni j ∈ N_N
  • dato un programma di base x_B e calcolati gli elementi di Y (=B^-1N) e i valori di z_j-c_j, questi tre teoremi permettono di stabilire:
    • se è necessario calcolare un nuovo programma di base
    • se è necessario fermare il calcolo o perché un programma ottimale è stato trovato o perché non esiste alcun programma ottimale finito
    il calcolo di una nuovo programma di base è soltanto il passaggio da una vecchia base B ad una nuova base B' imponendo che una variabile secondaria entri nella base e nello stesso tempo una variabile di base venga eliminata dalla base
• criterio di uscita nell'algoritmo del simplesso
  • il criterio di uscita è dato dalla relazione x_h / y_hk = min_ysk>0 (x_s / y_sk) , s ∈ N_B che ci permette di individuare la variabile principale x_h che dovrà diventare secondaria nel cambiamento di base.
• criterio di entrata nell'algoritmo del simplesso
  • il criterio di entrata è dato dalla relazione z_k - c_k = max_j∈NN (z_j - c_j) > 0 che permette di scegliere k in modo da massimizzare il decremento della z ( δz = z' - z = (z_k - c_k)(x_h / y_hk) ) quando la base viene cambiata perché la relazione z_j - c_j > 0 è generalmente soddisfatta da un sottoinsieme di N_N
  • questa scelta di k non produce la massima variazione della funzione obiettivo z ma fornisce un semplice criterio di entrata che funziona bene nella pratica
• convergenza dell'algoritmo del simplesso
  • il metodo del simplesso garantisce il passaggio da una soluzione di base x ad una nuova soluzione di base x' con z' ≤ z
  • convergenza
    • nel caso di soluzioni di base non degeneri (x_B>0) vale il segno < e l'algoritmo converge
  • non convergenza
    • se vale il segno =, la funzione obbiettivo non è decrementata
    • può avvenire che una variabile di base esca dalla base e poi vi rientri in una iterazione successiva lasciando invariato il valore di z (ciclo infinito)
      • nella pratica su problemi reali non si è mai verificato
      • esistono tecniche come il metoto lessicografico del simplesso che evitano questo fenomeno
• cambiamento di base nel metodo del simplesso.
  • il criterio di entrata e di uscita ci forniscono gli indici k ed h delle variabili che devono ripettivamente entrare ed uscire nella base. Lo scambio di queste due variabili genera una nuova base che, posto p l'indice di colonna di x_h in B, si può calcolare come segue:
    • v_p = [-y_1,k/y_p,k, -y_2,k/y_p,k, ... y_p-1,k/y_p,k, 1/y_p,k, -y_p+1,k/y_p,k, ... y_m/y_p,k]
    • J_p = [e₁ e₂ ... e_p-1 v_p e_p+1 ... e_m]
    • Y' = (B')^-1N' , (B')^-1 = J_pB^-1 , x^B' = (B')^-1d
    • N' ≡ colonne di A che non appartengono a B'
• tabella del simplesso
  • la tabella del simplesso (simplex tableau) è una tabella che viene costruita per ogni iterazione fatta dall'algoritmo del simplesso che riporta in maniera ordinata tutti i dati necessari per effettuare i calcoli, ovvero per trovare una base che ottimizzi la funzione obiettivo. Generalmente ha la struttura seguente:
    

    # iterazione			z1-c1	z2-c2	z3-c3	...
    cB	xB	xB	y1	y2	y3	...	xsk/ysk

    dove:
    • c_B: vettore colonna dei coefficienti
    • x_B: variabili di base
    • x_B: vettore delle soluzioni
    • y_i: elementi del vettore Y = B^-1N = [y₁ y₂ ... y_n-m] = (y_ij)
    • z_k-c_k: utilizzato per il criterio di entrata (scelta della variabile d'entrata)
    • x_sk/y_sk: utilizzato per il criterio di uscita (scelta della variabile d'uscita)
• base iniziale nel metodo del simplesso (problema artificiale PL)
  • l'algoritmo del simplesso necessita di un programma di base iniziale ammissibile che se non è disponibile lo si deve calcolare:
    • moltiplicando, se necessario certe equazioni dei vincoli in forma standard per -1, così da avere d ≥ 0
    • aggiungendo alla matrice A un numero necessario e sufficiente di vettori colonna unitari associati con variabili artificiali u₁, u₂, ..., u_p (p ≤ n), che insieme ad eventuali variabili di scarto o variabili isolate forniscono un programma iniziale ammissibile
    i vincoli possono essere ridefiniti in modo tale che A = [N I] fornisca la base iniziale B = I
• problema artificiale associato ad un problema PL in forma standard
  • alla matrice A si aggiunge un numero necessario e sufficiente di vettori colonna unitari associati con variabili artificiali u₁, u₂, ..., u_p (p ≤ n), che insieme ad eventuali variabili di scarto o variabili isolate forniscono un programma iniziale ammissibile
  • il nuovo problema PL' ammette il programma di base u₁=d₁, u₂=d₂, ..., u_m=d_m x₁=x₂=...=x_n=0
  • i vincoli lineari hanno la seguente forma esplicita:
    • a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n + u₁ = d₁
    • a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n + u₂ = d₂
    • ...
    • a_m1x₁ + a_m2x₂ + ... + a_mnx_n + u_m = d_m
• variabili artificiali in un problema PL
  • variabili u₁, u₂, ..., u_p (p ≤ n) artificialmente introdotte che, insieme ad eventuali variabili di scarto o variabili isolate, forniscono un programma iniziale ammissibile da utilizzare nell'algoritmo del simplesso
• metodo delle due fasi
  • affinché un programma del problema PL' sia una soluzione del problema PL iniziale, è necessario che nessuna variabile artificiale appaia nel risultato finale con valori strettamente positivi
  • metodo che si utilizza per trovare una base iniziale per l'algoritmo del simplesso utilizzando le variabili artificiali
  • questo metodo evita che le variabili artificiali appaiano nel risultato finale con valori strettamente positivi
  • fase 1
    • la funzione obiettivo iniziale è sostituita da: min ξ = ∑_i u_i
    • si possono avere i seguenti casi:
      • a) per il programma ottimale si ha ξ=0 e nessuna variabile artificiale è parte della base corrente
      • b) per il programma ottimale si ha ξ=0 e almeno una variabile artificiale è parte della base corrente
      • c) per il programma ottimale ξ>0 (in questo caso il programma PL non ha soluzione)
  • fase 2
    • nel caso (a) il programma ottimale del problema artificiale è un programma iniziale per il problema iniziale PL; si applica di nuovo l'algoritmo del simplesso
    • nel caso (b) il programma ottimale del problema artificiale è un programma iniziale per il problema iniziale PL ma le variabili artificiali presenti nella base devono restare nulle; si applica nuovamente l'algoritmo del simplesso imponendo che nessuna delle variabili secondarie per le quali z_j-c_j<0 alla fine della fase 1 possano entrare nella base
• si trova sempre una base al termine della prima fase?
  • se per il programma ottimale ξ = ∑_i u_i >0 il programma PL non ha soluzione
• algoritmo del simplesso rivisto
  • quando un programma di base ammissibile è conosciuto il problema PL iniziale può essere scritto come sistema (m+1)×(n+1) aumentando i vincoli con la funzione obiettivo
  • si passa da { min z = c^Tx , Ax = d , x ≥ 0 } a { min z: z - c^Tx = 0 , Ax = d , x ≥ 0 }
  • A = [1 -c ; 0 A] = [a₀ a₁ ... a_n] = [a_j] , j ∈ N = N ∪ {0}
  • B = [1 -c_B ; 0 B] = [a_i] , i ∈ N_B = N_B ∪ {0}
  • B^-1 = [1 -c_BB^-1 ; 0 B^-1]
  • d = [0 d]^T
  • B^-1(A,d) = [1 z₁-c₁ z₂-c₂ ... z_n-c_n z ; 0 y₁ y₂ ... y_n x_B]
  • quindi nel metodo rivisto del gradiente le quantità (z_j-c_j) sono ottenute moltiplicando la prima riga di B^-1 per a_j, ed il valore y_k della variabile x_k che entra nella base è ottenuto moltiplicando le ultime m rige di B^-1 per a_k
  • la funzione obiettivo z è considerata come una variabile speciale che non è soggetta al vincolo di non negatività e non lascerà mai la base (vale a dire che il criterio di uscita non si applica a z)
• tabella nel metodo del simplesso rivisto

  • cB	xB	xB	y1	y2	y3	...	xsk/ysk

• simplesso rivisto con base di partenza artificiale
  • si assume di usare un insieme completo di variabili artificiali u₁, u₂, ..., u_m
  • Con aⁱ si indica la riga i-ma di A
  • il sistema aggiunto dei vincoli includerà sia la funzione obiettivo sia la funzione delle variabili artificiali, consiterà quindi di (m+2)×(n+m+2) variabili x₁, x₂, ..., x_n, u₁, u₂, ..., u_m, z, ξ
  • il problema PL è quello di minimizzare:
    • z - c^Tx = 0
    • ξ - ... - γx = d₀
    • u₁ + a¹x = d₁
    • u₂ + a²x = d₂
    • ...
    • u_m + a^mx = d_m
  • con:
    • γ = ∑_i=1,m aⁱ
    • d₀ = ∑_i=1,m d_i
  • A = [1 0 ... -c ; 0 1 ... -γ ; ... ... ... A]
  • B = [1 0 ... -c_B ; 0 1 ... -γ_B ; ... ... ... B]
  • B^-1 = [1 0 ... -c_BB^-1 ; 0 1 ... -γ_BB^-1 ; ... ... ... B^-1]
  • d = [0 d₀ d]^T
  • B^-1A^-1 = [1 0 ... -c_BB^-1 z₁-c₁ z₂-c₂ ... z_n-c_n; 0 1 ... -γ_BB^-1 ξ₁-γ₁ ξ₂-γ₂ ... ξ_n-γ_n; ... ... ... B^-1 y₁ y₂ ... y_n]
• simplesso rivisto in due fasi
  • fase 1
    • calcola ξ_j-γ_j, j∈N_N, moltiplicando la seconda riga di B^-1 per le colonne secondarie di A;
    • determina k mediante il criterio di entrata ξ_k-γ_k = max_j∈NN (ξ_j-γ_j) > 0
    • calcola y_k moltiplicando B^-1 per la corrispondente colonna di A
    • applica il criterio di uscita per tutte le variabili di base eccetto z e ξ
    • esegui il cambio di variabili
  • fase 2
    • calcola z_j-c_j, j∈N_N, moltiplicando la prima riga di B^-1 per le colonne secondarie di A;
    • determina k mediante il criterio di entrata z_k-c_k = max_j∈NN (z_j-c_j) > 0
    • calcola y_k moltiplicando per B^-1 la corrispondente colonna di A;
    • applica il criterio di uscita per tutte le variabili di base ad eccezione di z e ξ
    • esegui il cambio di variabili
  • durante la prima fase non è necessario eseguire le operazioni con la prima riga di B^-1, durante la seconda fase con la seconda riga di B^-1
• problema PL da canonico a duale
  • {min z = c^Tx , Ax ≥ d , x ≥ 0} ⇒ {max w = ub , uA ≤ c , u ≥ 0}
• problema PL da standard a duale
  • {min z = c^Tx , Ax = d , x ≥ 0} ⇒ {max w = ub , uA ≤ c , u qualsiasi}
• trasformazione di un problema di PL nel suo duale
  • ad ogni vincolo di diseguaglianza (≥) corrisponde una variabile duale (u_i) soggetta a vincolo di non negativita(≥0)
  • ad ogni vincolo di uguaglianza (=) corrisponde una variabile duale (u_i) non soggetta ad alcun vincolo
  • le matrici dei coefficienti dei vincoli "veri" nei due problemi sono una la trasposta dell'altra
  • i valori a secondo membro dei vincoli veri di ciascun problema sono gli opposti dei coefficienti della funzione obbiettivo da minimizzare nell'altro problema
  • il duale di un problema duale da il problema di partenza
  • formulazione:
    • {min z = ∑_j=1,n (c_jx_j)} ⇒ {max w = ∑_i=1,m -(d_iu_i)}
    • {∑_j=1,n (a_ijx_j) ≥ d_i, i ∈ M₁} ⇒ {u_i ≥ 0 , u_i ∈ M₁}
    • {∑_j=1,n (a_ijx_j) = d_i, i ∈ M₁} ⇒ {u_i qualsiasi , u_i ∈ M₁}
    • {x_j ≥ 0 , j ∈ N₁} ⇒ {∑_i=1,m -(a_iju_i) ≥ -c_j, j ∈ N₁}
    • {x_j qualsiasi, j ∈ N₁} ⇒ {∑_i=1,m -(a_iju_i) = -c_j, j ∈ N₁}
    • M₁ = M - M₁ , N₁ = N - N₁ , u vettore riga
• variabili duali
  • sono le variabili u_i che nel passaggio dalla forma primale a quella duale corrispondono ai vincoli di disuguaglianza e di uguaglianza del problema primale
  • i vincoli a_ix ≥ d_i e u_i ≥ 0 oppure ua_j ≤ c_j e x_j ≥ 0 sono chiamati vincoli duali
  • u_i è la variabile duale del vincolo di indice j
• relazione tra due soluzioni duali
  • se x ed u sono una coppia di soluzioni ammissibili di due problemi duali: cx ≥ ud
    • se cx = ud , allora x ed u sono soluzioni ottimali
• teorema di esistenza della dualità
  • data una coppia di problemi duali, una ed una sola delle tre proposizioni è vera:
    • 1. nessuno dei due problemi ha una soluzione ammissibile;
    • 2. se un problema non ammette una soluzione, l'altro ha almeno una soluzione ma non ha soluzioni ottimali;
    • 3. i due problemi hanno soluzioni ottimali.
• teorema della dualità
  • data una coppia di problemi duali una condizione necessaria e sufficiente affinché una soluzione x (o u) di uno dei due problemi sia ottimale eche esista un u (o x) dell'altro problema tale che cx = ud
  • la soluzione u è essa stessa una soluzione ottimale e la relazione è verificata per ogni coppia di soluzioni ottimali
• teorema debole degli scarti complementari
  • data una coppia di problemi duali, una condizione necessaria e sufficiente affinché due soluzioni x e u siano ottimali è che siano verificate le seguenti relazioni: u(Ax - d) = 0 , (c - uA)x = 0
• teorema forte degli scarti complementari
  • data una coppia di problemi duali aventi entrambi delle soluzioni, allora esiste almeno una coppia di programmi ottimali x ed u: (Ax - d) + u > 0 , (c - uA) + x > 0
• importanza della dualità
  • la soluzione ottimale del problema duale permette di calcolare la soluzione del primale
  • in certe situazioni è più facile risolvere il problema duale, si risolve quindi questo ottenendo allo stesso tempo la soluzione del problema primale
• interpretazione economica di un problema di PL e del suo duale
  • problema primale
    • data una domanda (disponibilità) di m beni i ed un costo (profitto) unitario c_j per ciascuna delle n attività j quale deve essere il livello di funzionamento di ciascuna attività affinché la quantità totale dei beni i prodotti (utilizzati) sia maggiore o uguale (minore o uguale) alla domanda (disponibilità) d_i e che il costo (profitto) totale sia minimo (massimo)
    • schema
      • ∑_j (livello dell'attività j)×(produzione da j al livello 1 del bene i) ≥ (domanda di i)
      • (livello di j) ≥ 0
      • min (costo totale) = ∑_j (costo unitario di j)×(livello di j)
  • problema duale
    • dato un costo unitario c_j per ciascuna delle m attività j ed una domanda (disponibilità) d_i per ciascuno degli m beni i, quale deve essere il prezzo unitario di ciascun bene affinché il valore totale dei beni prodotti (utilizzati), a livello 1, sia inferiore o uguale (superiore o uguale) al costo (profitto) c_j e che il valore totale dei beni prodotti (utilizzati) sia massimo (minimo).
    • schema
      • ∑_i u_i×(produzione da j al livello 1 del bene i) ≤ (costo unitario di j)
      • u_i ≥ 0
      • max w = ∑_j (domanda di i)×(u_i)
• prezzi ombra
  • sono le variabili u_i che compaiono nell'interpretazione economica del problema duale
  • rappresentano il prezzo unitario del bene i e misurano l'incremento del profitto nel problema primale quando si incrementa di una unità la disponibilità delle ore di lavoro, delle attrezzature e delle materie prime
• analisi della sensibilità nella PL
  • è una tecnica di post-ottimizzazione che consiste nell'analisi degli effetti prodotti sulla soluzione ottimale dalle modifiche di A, c, d, e dall'introduzione di vincoli e variabili
• importanza dei prezzi ombra nell'analisi della sensibilità nella PL
  • la loro variazione misura l'incremento del profitto nel problema primale a seguito della modifica dei dati
  • i prezzi ombra con valori grandi sono detti "sensibili"
• modifica del vettore c della funzione obiettivo
  • equivale alla modifica della funzione obiettivo, si passa da c a c + δc
  • Se B è la base che fornisce la soluzione di base ottimale del problema originale, la soluzione di base ottimale x_B è ancora una soluzione di base ma non è necessariamente ottimale per il nuovo programma
  • posto:
    • z'_j = (c + δc)_By_j = z_j + δc_By_j , j ∈ J
    • z' = (c + δc)_Bx_B = z + δc_Bx_B
  • si hanno due casi:
    • se z'_j - c_j ≤ 0 (j ∈ J), u>x_B è ancora un programma di base ottimale; il nuovo valore della funzione obiettivo è: z + δc_Bx_B
    • se z'_j - c_j > 0 (per almeno un j ∈ J), x_B è ancora un programma di base ma non è ottimale; le formule precedenti permettono di continuare l'applicazione del metodo del simplesso a partire dalla tabella finale ottenuta nella soluzione del problema originale
  • 
• modifica del vettore d dei vincoli
  • si passa da d a d + δd
  • la soluzione di base corrispondente alla base ottimale B del problema originale soddisfa i criteri di ottimalità ma potrebbe non essere una soluzione ammissibile
  • posto:
    • x'_B = B^-1(d + δd) = x_B + B^-1δd
  • si hanno due casi:
    • x'_B = B^-1(d + δd) = x_B + B^-1 ≥ 0 , allora x'_B è la nuova soluzione ottimale
    • x'_B = B^-1(d + δd) = x_B + B^-1 < 0 , per qualche componente di x'
      • se il numero delle componenti minori di zero è grande, conviene applicare da capo il metodo del simplesso altrimenti esistono dei metodi che permettono di utilizzare i dati della tavola del simplesso ottenuta con la risoluzione del problema originale
  • 
• introduzione di una nuova variabile
  • l'introduzione di una nuova variabile x_n+1 porta ad aggiungere una nuova colonna a_n+1 alla matrice A ed un nuovo elemento c_n+1 al vettore c. Al termine della applicazione dell'algoritmo al problema originale (per es, con l'algoritmo del simplesso rivisto) si dispone sia di B^-1sia di c_BB^-1. Allora:
    • (c_BB^-1a_n+1-c_n+1) ≥ 0 , la soluzione di base ottimale del problema originale è anche soluzione di base ottimale del nuovo problema
    • (c_BB^-1a_n+1-c_n+1) > 0 , si continua l'applicazione del simplesso a partire dalla tabella finale ottenuta nella soluzione del problema originale
• modifica dei coefficienti a_j della variabile x_j
  • nel caso in cui x_j è una variabile secondaria si procede come nel caso dell'introduzione di una nuova variabile. Se x_j è una variabile di base, si passa dalla base B ad una nuova base B' ottenuta modificando la colonna relativa a x_j. Nel caso B' sia ancora una base e x_B=(B')^-1d ≥ 0 allora si è in presenza di una nuova soluzione di base. Questa potrà essere ottimale oppure no. Nel secondo caso si continua con l'algoritmo del simplesso a partire dalla tabella finale ottenuta nella soluzione del problema originale. Le altre situazioni (B' non euna base) sono risolte con tecniche specifiche. Può essere necessario applicare il simplesso da capo
• introduzione di un nuovo vincolo
  • questo caso è comune perché si vuole sperimentare come varia la funzione obiettivo z in rapporto ai vincoli. L'introduzione di un vincolo può ridurre l'insieme delle soluzioni ammissibili e pertanto non può migliorare il valore della funzione z. Il contrario avviene se un vincolo viene eliminato. Nel caso che la soluzione di base ottimale del problema originale soddisfi il nuovo vincolo allora essa è una soluzione ottimale (non necessariamente di base) anche per il nuovo problema. Anche ora gli altri casi sono risolti con tecniche specifiche e può essere necessario applicare il simplesso da capo.
• programmazione parametrica nella PL
  • è una tecnica di post-ottimizzazione che permette di studiare il problema originario nel caso in cui i dati vengano fatti variare con continuità, ovvero siano modificati con quantità che variano in maniera continua
• parametrizzazione del vettore d
  • sia d₀ il vettore della domanda (o disponibilità), posto d = d₀ + θδ , δ vettore fisso e θ ≥ 0
  • supponiamo che x_0B = B^-1d₀ sia una soluzione di base ottimale con base B
  • facciamo variare θ assegnandole valori positivi crescenti
  • il valore della soluzione di base varia secondo x_B = B^-1d₀ + θB^-1δ
  • il criterio di ottimalità x_B continua ad essere soddisfatto poiché non interviene nel calcolo di z_j-c_j ma il vettore potrebbe ad un certo punto non essere ammissibile
  • posto ξ = B^-1δ si ha:
    • se ξ ≥ 0 allora x_B continua ad essere un programma ottimale per ogni valore di θ ≥ 0
    • se ξ_j < 0 (ξ_j qualche componente di ξ) esiste un valore θ₁ di θ, oltre il quale x_B non è una soluzione ammissibile poiché una sua componente diventa negativa
      • θ₁ = - x_o1/ξ₁ = min_s/ξs<0 (- x_os/ξ_s) , s ∈ I
    • volendo ancora studiare il problema per valori di θ>θ₁ si calcola la soluzione ottimale per θ=θ₁ e poi si procede con varie tecniche che dipendono dal risultato ottenuto
• parametrizzazione del vettore c
  • sia c₀ il vettore dei costi, posto c = c₀ + θγ , γ vettore fisso e θ ≥ 0
  • supponiamo che x_B = B^-1d₀ sia una soluzione di base ottimale con base B
  • variando θ, x_B continua ad essere una soluzione di base ma non necessariamente ottimale
  • z_j-c_j = c_By_j - c_j = (c_0B + θγ_B)yj - (c_0j + θγ_j) = c_0By_j - c_0j + θ(γ_By_j - γ_j) = z_0j - c_0j + θ(ζ_j - γ_j) , con ζ_j = γ_By_j
    • se γ_BY-γ ≤ 0 la base B resta ottimale per ogni valore di θ ≥ 0
    • ζ_j-γ_j (almeno una j di J) esiste un valore θ₁ di θ oltre il quale B non è una base ottimale poiché almeno un z_j-c_j diventa positivo
      • θ₁ = - (z_0k -c_0k) / (ξ_k - γ_k) = min_{j/(ξj - γj)>0} [- (z_0j -c_0j) / (ξ_j - γ_j)]
    • volendo ancora studiare il problema per valori di θ>θ₁ si calcola la soluzione ottimale per θ=θ₁ e poi si procede con varie tecniche che dipendono dal risultato ottenuto
• complessità computazionale del metodo del simplesso
  • teoricamente ha una complessità esponenziale
  • nei problemi pratici derivanti dal mondo reale la complessità è dell'ordine di O(m)
  • è stato dimostrato che scegliendo A, c e d con una opportuna distribuzione di probabilità, la complessità del metodo del simplesso è di tipo polinomiale O(min(m²,n²))
• gradiente di una funzione di una o più variabili
  • il gradiente di una funzione di n variabili, f(x), x ∈ Rⁿ si indica con ∇f(x) ed è il vettore delle derivate parziali di f(x): ∇f(x) = [f_x1(x) f_x2(x) ... f_x3(x)]^T
  • moltiplicando il gradiente per -1, otteniamo la direzione massima di discesa della funzione
• algoritmo degli ellissoidi nella PL
  • è stato sviluppato per funzioni convesse anche non differenziabili, a partire dal metodo "delle sezioni centrali" e dal metodo del "gradiente generalizzato"
  • è stato dimostrato che la complessità nel caso venga applicato a problemi di programmazione lineare è polinomiale
  • in pratica si è rivelato inefficiente
• algoritmo di Karmarkar
  • è un algoritmo di complessità polinomiale per la risoluzione di problemi PL
  • nella risoluzione di problemi classici ha una complessità comparabile con quella del metodo del simplesso
  • è applicabile ad un problema PL nella forma:
    • min z = c^Tx , Ax = 0 , x ∈ Δ
    • con Δ = {x∈Rⁿ | e^Tx=1, x≥0} , e^T=(1,1,...,1)∈Rⁿ
    • si considerano valide le seguenti ipotesi:
      • A è una matrice m×n di rango m
      • Ae=0 , implica che x₀=e/n é un punto ammissibile
      • il minimo di z=c^Tx è zero
  • complessità computazionale
    • l'algoritmo di Karmarkar risolve un problema di PL standard con n variabii ed m vincoli in circa O(p⁴L²) operazioni tra bit
      • p = n + m
      • L = ∑_i=0,m∑_j=0,n (log₂(|a_ij|+1)+1) lunghezza dell'input

• ---

• problema dei trasporti
  • è un problema di programmazione lineare
  • si devono trasportare degli oggetti da m punti di origine (O₁, O₂, ..., O_m) a n-1 punti di destinazione (D₁, D₂, ..., D_n-1)
  • ad ogni linea di comunicazione tra un punto di origine O_i ed uno di destinazione D_j, è associato un costo c_ij
  • si vogliono determinare le quantità di oggetti da trasportare in ogni cammino soddisfando le richieste e minimizzando i costi
• formulazione matematica del problema dei trasporti
  • formulazione tipica per m nodi di partenza ed n-1 destinazioni
    • min z = ∑_i=1,m∑_j=1,n-1 c_ijx_ij
    • ∑_j=1,n-1 x_ij ≤ a_i ; i = 1, ..., m
    • ∑_j=1,m x_ij ≥ b_j ; j = 1, ..., n-1
    • x_ij ≥ 0 ; i = 1, ..., m ; j = 1, ..., n-1
    • ∑ a_i ≥ ∑ b_j , a_i ≥ 0 , b_j ≥ 0 , c_ij ≥ 0
    • 
  • formulazione standard
    • min z = ∑_i=1,m∑_j=1,n c_ijx_ij
    • ∑_j=1,n x_ij = a_i ; i = 1, ..., m
    • ∑_j=1,m x_ij = b_j ; j = 1, ..., n
    • x_ij ≥ 0 ; i = 1, ..., m ; j = 1, ..., n
    • ∑ a_i = ∑ b_j , a_i ≥ 0 , b_j ≥ 0 , c_ij ≥ 0, c_in = 0
• caratteristica della formulazione del problema del trasporto come problema PL
  • il problema del trasporto è rappresentabile con un grafo
• risultati teorici del problema del trasporto
  • il problema del trasporto ammette sempre una soluzione ammissibile ed ogni soluzione è limitata
  • dimostrazione
    • i valori x_ij = a_ib_j / ∑ a_i costituiscono una soluzione, inoltre x_ij ≤ min(a_i,b_j)
  • se i valori a_i e b_j sono numeri interi, i valori delle soluzioni di base sono anch'essi interi. Esiste pertanto un programma di base con valori interi
• grafi G e T
  • al grafo G si fa corrispondere il grafo T
  • ad un arco di G si associa un nodo di T
  • ad un nodo p di G si associano gli archi di T che collegano due nodi in T i cui archi corrispondenti in G incidono p
  • ad un arco nel grafo G corrisponde un solo nodo in T
  • ad un nodo in G possono corrispondere nessuno, uno o più archi nel grafo T
  • ai nodi origine nel grafo G corrispondono archi orizzontali
  • ai nodi di destinazione corrispondono archi verticali
  • ad ogni nodo del grafo T corrisponde una variabile del problema del trasporto (c_ij è il costo associato)
  • ad ogni nodo del grafo T è associata una colonna della matrice A dei vincoli
  • un m-ciclo è un sottografo di T che ha al più un arco in ciascuna riga e ciascuna colonna
• importanza del grafo T nel problema del trasporto
  • il grafo T permette di semplificare i calcoli rappresentando il grafo G sotto forma di tabella
  • un sottografo di T è un sottoinsieme dei nodi ed archi di T che collegano nodi vicini del sottografo
• il più importante risultato derivante dall'associare al problema dei trasporti la teoria dei grafi
  • i grafi modellizzano bene questo tipo di problemi perchè hanno una natura geometrica (punti di partenza, punti di arrivo e collegamenti), danno cioè un'immediata rappresentazione visiva del problema reale
  • inoltre rappresentare il problema con la teoria dei grafi permette di utilizzare più semplici strategie risolutive
• semplificazioni di un problema del trasporto rispetto ad un generico problema PL
  • la matrice completa del sistema diventa: (A,d) = (a₁, a₂, ..., a_j, ..., a_m·n)
  • sottomatrice di (A,d) in cui si elimina una riga: (A¹,d¹) = (a¹₁, a¹₂, ..., a¹_j, ..., a¹_m·n, d¹)a¹₁
  • sottomatrice di A composta da (m+n-1) vettori colonna linearmente indipendenti: B' = (a_j1, a_j2, ..., a_jm+n-1)
  • poiché ogni sottomatrice estratta da B' di ordine (m+n-1) ha determinante diverso da 0, la matrice B ottenuta da B' eliminando una sua riga forma una base che si indica con B = (a¹_j1, a¹_j2, ..., a¹_jm+n-1) , le (m+n-1) variabili associate alle colonne di B' sono le corrispondenti variabili di base
  • ogni colonna a_j si può esprimere in funzione delle colonne di B', ossia: a_j = B'y_j = ∑_s=j1,jm+n-1 y_sja_s , y_j = B^-1a¹_j , j = 1, ..., m·n
  • la soluzione di base associata a B è: x_B = B^-1d¹
  • c_B = (c_j1, c_j2, ..., c_jm+n-1)
  • il valore di z in una base è: z = c_Bx_B
  • z_j = c_By_j = ∑_s=j1,jm+n-1 y_sjc_s
  • calcolo di (z_j-c_j)
    • un vettore a_j che non appartiene alla base può esprimersi come combinazione lineare delle colonne di base che sono associate ad un m-ciclo: a_j = a_s1 - a_s2 - ... + (-1)^p+1a_sp + ... + a_s2q-1
    • da cui: z_j - c_j = c_s1 - c_s2 - ... + (-1)^p+1c_sp + ... + c_s2q-1
    • si determina l'indice k del vettore che entra nella base mediante: z_k - c_k = max_j (z_j - c_j)
  • calcolo di x_sk/y_sk per tutti gli s tali che y_sk > 0
    • se y_sk > 0 esso ha valore +1 ed s è un indice dispari, pertanto x₁ = min_p (x_s2p-1) , p = 1, 2, ..., q
  • calcolo delle nuove variabili di base
    • x'_s = x_s - x₁(y_sk/y_1k) , con y_sk = 1
    • poiché cambiano solo le variabili associate ai nodi dell'm-ciclo (che interviene nel determinare la nuova base) si ha:
      • x'_2p = x_2p + x₁
      • x'_2p-1 = x_2p-1 - x₁
  • Calcolo dei nuovi valori y_j
    • La conoscenza dell'm-ciclo fornisce immediatamente i valori di y_j
• algoritmo del trasporto (formulazione generica)
  • a) si parte dalla tabella del trasporto, si trova un programma di base e si scrivono i valori nella stessa tabella
  • b) si considerano successivamente tutte le caselle che corrispondono a variabili non di base; per ciascuna di esse si trova l'm-ciclo composto da questa casella e dalle caselle delle variabili di base. Si calcola (z_j-c_j). Se (z_j-c_j)≤0 allora la soluzione corrente è ottimale, altrimenti si calcola l'indice k del vettore che entra nella base z_k-c_k=max(z_j-c_i) ed il corrispondente m* m-ciclo
  • c) marcare le caselle pari nella successione dei nodi di m* ponendo uguale ad uno la prima casella del ciclo.Tra queste caselle trovare la variabile col valore minimo; sia x₁ il suo valore
  • d) diminuire di x₁ i valori delle variabili nelle caselle marcate ed aumentare di x₁i valori delle altre caselle di m* (compreso x_k che assume il valore x₁). L'insieme composto da x_k e dalle variabili di base precedenti, eccetto x_l, sono le nuove variabili di base
  • e) ripetere i punti b), c) e d) finché il criterio di ottimalità è soddisfatto
• ricerca di una soluzione di base iniziale (nord-ovest)
  • ad una qualsiasi variabile x_ij (che sarà di base) si assegna il valore: x_ij = min(a_i, b_j)
  • si sostituisce a_i e b_j con a_i-x_ij e b_j-x_ij
  • si elimina la riga i se x_ij=a_i oppure la colonna se x_ij=b_j
  • nel metodo chiamato nord-ovest si sceglie ad ogni passo la variabile situata nella prima riga e prima colonna non eliminate

• ---

• grafo orientato
  • un grafo (P,U) è dato da un insieme finito P di nodi p_i (o vertici) e da un insieme U di coppie (p_i,p_j) ordinate di nodi, chiamate archi (o spigoli)
  • i nodi p_i e p_j di un arco (p_i,p_j) sono detti adiacenti
  • l'arco (p_i,p_j) ed il nodo p_i (o p_j) sono detti incidenti
• grafo non orientato
  • un grafo (P,U) è dato da un insieme finito P di nodi p_i (o vertici) e da un insieme U di coppie (p_i,p_j) non ordinate di nodi, chiamate archi (o spigoli)
  • i nodi p_i e p_j di un arco (p_i,p_j) sono detti adiacenti
  • l'arco (p_i,p_j) ed il nodo p_i (o p_j) sono detti incidenti
  • un arco può essere percorso in entrambe le direzioni
  • si hanno le definizioni di grafo connesso, catena e ciclo
• sottografo
  • un sotto-grafo del grafo (P,U) è dato dal grafo (P_s,U_s) tale che:
    • P_s ⊂ P
    • (p_i,p_j) ∈ U_s ⇔ p_i ∈ P_s , p_j ∈ P_s e (p_i,p_j) ∈ U
• grafo parziale
  • dato il grafo (P,U), un grafo si dice grafo parziale di (P,U) se l'insieme dei suoi nodi coincide con P e l'insieme dei suoi archi è un sottoinsieme di U
• grafo simmetrico
  • un grafo (P,U) si dice simmetrico se (p,q) ∈ U ⇔ (q,p) ∈ U
• grafo completo
  • un grafo (P,U) si dice completo se ogni coppia di nodi definisce almeno un arco
• cappio
  • è un arco i cui nodi coincidono
• cammino
  • dato un grafo (P,U), un cammino è una successione di archi u_i, i=1,...,p, tali che il secondo nodo di ciascun arco coincide con il primo nodo dell'arco successivo (posto u_k=(p_i,p_j) si ha u_k+1=(p_j,p_h))
• circuito
  • è un particolare cammino nel quale il primo nodo del primo arco coincide con il secondo nodo dell'ultimo arco
• cammino composto
  • lo è se utilizza due volte o più volte lo stesso arco
  • è il contrario del cammino semplice
• cammino semplice
  • lo è se non utilizza mai lo stesso arco
  • è il contrario del cammino composto
• cammino elementare
  • lo è se non incontra due o più volte lo stesso nodo
• grafo fortemente connesso
  • un grafo (P,U) si dice fortemente connesso se per ogni coppia di nodi p e q di P esiste un cammino che ha come primo nodo p ed ultimo nodo q
• albero
  • un grafo non orientato è un albero se è connesso e senza cicli
• differenza tra un grafo orientato parziale ed un suo sottografo
  • il grafo orientato parziale contiene tutti i nodi del grafo (P,U) originale, mentre il sottografo contiene solo un sottoinsieme di nodi P_s ⊂ P
• archi di un grafo completo con 4 nodi
  • se il grafo è orientato, ogni nodo è connesso con tutti gli altri, ci sono quindi n(n-1) archi dove n è il numero dei nodi; con 4 nodi: 4(4-1) = 12 archi
  • se il grafo è non orientato, l'arco (p_i,p_j) coincide con l'arco (p_j,p_i) ci sono quindi n(n-1)/2 archi; con 4 nodi: 4(4-1)/2 = 6 archi
• rappresentazione di un grafo orientato
  • un grafo può rappresentarsi mediante una matrice A=(a_ij) detta matrice d'adiacenza
  • l'indice i si riferisci ai nodi e l'indice j agli archi
  • la matrice è composta da 0 (assenza di arco) ed 1 (presenza di un arco tra il nodo i ed il nodo j)
• rete di trasporto
  • una rete è un grafo orientato (P,U) senza alcun cappio tale che
    • a) a ciascun arco (p_i,p_j) p_i∈U sono associati
      • una capacità k_ij ≥ 0 (per esempio se si tratta di una strada il massimo numero di autoveicoli che la possono percorrere in un'ora)
      • una lunghezza u_ij ≥ 0 (per esempio se si tratta di una strada la sua lunghezza o il tempo necessario per percorrerla)
    • b)a ciascun nodo p_i ∈ P è associata una domanda d(p_i) che può essere positiva, negativa o nulla
    • se d(p_i) > 0, il nodo p_i e detto una destinazione (o uscita)
    • se d(p_i) < 0 il nodo p_i e detto origine (o entrata)
    • se d(p_i) = 0 il nodo p_i e detto punto di transito
• rete di trasporto semplice
  • è una rete di trasporto in cui i nodi possono essere ripartiti in due insiemi disgiunti P₁ e P₂ tali che:
    • (p_i,q_i) ∈ U ⇒ p_i ∈ P₁ , q_j ∈ P₂
    • d(q_i) > 0 ⇔ q_j ∈ P₂
    • d(i_i) > 0 ⇔ p_i ∈ P₁
• rete di trasporto ridotta
  • rete di trasporto che ha una sola origine p₀ ed una sola destinazione p_n
  • non esiste alcun arco che ha p₀ come secondo nodo (arco incidente interiormente) ed alcun arco che ha p_n come primo nodo (arco incidente esteriormente).
  • spesso si definisce una rete ridotta a partire da una rete primitiva aggiungendo due nodi fittizi p₀ e p_n all'insieme P e creando gli archi (p₀,p_e) e (p_s,p₁) con p_e ogni nodo origine (che diventa di transito) e p_n ogni nodo destinazione (che diventa di transito)
• flusso aritmetico in una rete di trasporto
  • è una qualsiasi funzione x(·) che associa ad ogni arco (p_i,p_j) della rete un numero positivo: p_i,p_j → x(p_i,p_j) (o semplicemente x_ij) tale che
    • il flusso in un arco non può superare la sua capacità
      • 0 ≤ x(p_i,p_j) ≤ k_ij , (i,j) ∈ U
    • in un nodo di transito il flusso in entrata deve essere uguale al flusso in uscita
      • x(p_i,P) - x(P,p_i) = 0 , p_i ∈ P-E-S
    • in un qualsiasi nodo di entrata il flusso deve essere > 0
      • x(p_e,P) - x(P,p_e) ≥ 0 , p_e ∈ E
    • in un qualsiasi nodo di uscita il flusso deve essere ≤ 0
      • x(p_s,P) - x(P,p_s) ≤ 0 , p_s ∈ S
    E = insieme di tutti i nodi di entrata, S = insieme di tutti i nodi di uscita
  • x(p_k,P) = ∑_p∈P x(p_k,p) , x(P,p_k) = ∑_p∈P x(p,p_k) , k = i, e, s
  • la funzione x(p_i,p_j)=x_ij può essere considerata come il valore della circolazione nell'arco (i,j) da p_i a p_j e sarà chiamato il flusso nell'arco (i,j)
  • esempi di flusso
    • se la rete è una rete stradale, x_ij può essere il numero di automobili che vanno da p_i a p_j e x_ji il numero di automobili che vanno in senso contrario
    • se la rete è un cavo ottico, il flusso può essere la quantità di bit che vengono trasmessi lungo il cavo
• flusso algebrico in una rete di trasporto
  • è dato dalla differenza del flusso aritmetico nei due sensi
  • f(p_i,p_j) = x_ij - x_ji
  • proprietà:
    • il flusso algebrico in un arco da p_i a p_j è l'opposto del flusso da p_j a p_i
      • f(p_i,p_j) = - f(p_j,p_i)
    • il flusso algebrico può assumere valori >0, <0 e =0 ma sempre entro la capacità fissata
      • -k_ij ≤ f(p_i,p_j) ≤ k_ij
    • il flusso algebrico è uguale zero per i nodi di transito
      • f(p_i,P) = 0 , p ∈ P-E-S
    • il flusso algebrico è positivo per i nodi d'entrata (nodi di origine)
      • f(p_e,P) ≥ 0 , p ∈ E
    • il flusso algebrico è negativo per i nodi d'uscita (nodi di destinazione)
      • f(p_s,P) ≤ 0 , p ∈ S
  • f(p_k,P) = ∑_p∈P f(p_k,p) , f(P,p_k) = ∑_p∈P f(p,p_k) , k = i, e, s
  • la definizione di flusso algebrico produce delle semplificazioni nello studio dei problemi sulle reti
    • aumentare di k unità il flusso algebrico negativo f(p_i,p_j) in un arco (p_i,p_j) significa diminuire la circolazione da p_j a p_i di k unità
• flusso della rete
  • φ = φ_e = φ_s
  • φ_e = f(E,P) flusso totale che dai nodi di entrata va in rete
  • φ_s = f(P,S) flusso totale che dai nodi di uscita esce dalla rete
• capacità residua di una rete di trasporto
  • ad ogni arco tra i nodi p_i e p_j si associano due capacità residue:
    • r_ij = k_ij - f(p_i,p_j)
    • r_ji = k_ji - f(p_j,p_i)
  • vale la relazione: r_ij + r_ji = k_ij + k_ji
• taglio in una rete di trasporto
  • in una rete di trasporto ridotta, è ogni sottoinsieme W di U tale che ogni cammino da p₀ a p_n ha un arco in W
  • eliminando gli archi del taglio non sarà più possibile raggiungere p_n da p₀
• teorema di Ford-Fulkerson
  • sia G un grafo orientato (P,U) ridotto con capacita k_ij≥0 finita (k_ij capacità dell'arco (p_i,p_j) e p₀ e p_n i nodi di entrata ed uscita senza alcun cappio, allora:
    • a) per ogni flusso f su G ed ogni taglio C di G il valore del flusso è minore o uguale alla capacità di C
    • b) per il flusso massimo f₀ su G esiste un taglio C₀ su G tale che il valore del flusso è uguale alla capacità di C₀; il taglio ha capacità minima
• teorema di Gale
  • data una rete di trasporto (P,U) in cui è definita una domanda, questa può essere soddisfatta se e solo se k(A,A) ≥ d(A) , ∀A⊂P con (A,A) un insieme qualsiasi di archi incidenti su un nodo v di A (con direzione verso v) e k(A,A) la somma delle capacità degli archi (A,A)
• teorema di Gale per reti ridotte
  • data una rete di trasporto ridotta (P,U), la condizione necessaria e sufficiente affinché esista un flusso che saturi gli archi incidenti il nodo di uscita p_n è che: k(A,A) ≥ k(A,p_n) , ∀A⊂P-{p₀,p_n}
  • corollario
    • data una rete di trasporto ridotta (P,U) in cui S è l'insieme dei nodi adiacenti a p_n(S⊂P), la condizione necessaria e sufficiente affinchè esista un flusso che saturi gli archi incidenti il nodo di uscita p_n è che esista un flusso aritmetico x tale che: x(A,A) ≥ k(A,p_n) , ∀A⊂P
• problema del cammino minimo (o Shortest Paths, SP)
  • dato un grafo orientato (P,U), siano p_s e p_v due nodi qualsiasi, trovare il cammino di lunghezza minima tra p_s e p_v
• algoritmo di Dijkstra
  • trova il cammino minimo tra un nodo p_s e tutti gli altri nodi
  • l'algoritmo può essere utilizzato parzialmente per trovare il cammino minimo che unisce due nodi del grafo, totalmente per trovare quelli che uniscono un nodo d'origine a tutti gli altri nodi o più volte per trovare tutti i cammini minimi da ogni nodo ad ogni altro nodo
  • è considerato uno degli algoritmi più efficienti per risolvere il problema del cammino minimo
  • la complessità computazionale dell'algoritmo di Dijkstra "naif" è di O(n²) ma ottimizzando il processo si arriva a O(m + n log(n)) con m numero di archi
  • algoritmo
    • Supponiamo di avere un grafo con n vertici contraddistinti da numeri interi {1,2,...,n} e che 1 sia scelto come nodo di partenza. Il peso sull'arco che congiunge i nodi j e k è indicato con p(j,k). Ad ogni nodo, al termine dell'analisi, devono essere associate due etichette, f(i) che indica il peso totale del cammino (la somma dei pesi sugli archi percorsi per arrivare al nodo i-esimo) e J(i) che riporta il nodo sul cammino minimo che porta al nodo i-esimo subito precedente questo ultimo. Inoltre definiamo due insiemi S e T che contengono rispettivamente i nodi a cui sono già state assegnate le etichette e quelli ancora da scandire.
    • 1. Inizializzazione.
      • Poniamo S={1}, T={2,3,...,n}, f(1)=0, J(1)=0.
      • Poniamo f(i)=p(1,i), J(i)=1 per tutti i nodi adiacenti ad 1.
      • Poniamo f(i)= ?, per tutti gli altri nodi.
    • 2. Assegnazione etichetta permanente
      • Se f(i)= ? per ogni i in T STOP
      • Troviamo j in T tale che f(j)=min f(i) con i appartenente a T
      • Poniamo T=T-{j} e S=S?{j}
      • Se T=Ø STOP
    • 3. Assegnazione etichetta provvisoria
      • Per ogni i in T, adiacente a j e tale che f(i)>f(j)+p(j,i) poniamo:
        • f(i)=f(j)+p(j,i)
        • J(i)=j
      • Andiamo al passo 2
• albero di supporto
  • dato un grafo G non orientato (P,U), un albero di supporto è un qualunque grafo parziale che ha la struttura di un albero
  • lunghezza di un albero di supporto è data dalla somma delle lunghezze degli archi che lo compongono
• problema del minimo albero di supporto
  • dato un grafo non orientato trovare l'albero di supporto di lunghezza minima
  • lemma: sia X un sottoinsieme dei vertici di G ed a sia l'arco di lunghezza minima che connette X a P-X, allora a fa parte del minimo albero di supporto
• algoritmo di Prim
  • trova il minimo albero di supporto
  • ad ogni iterazione si aggiunge a T l'arco di lunghezza minima (che connette direttamente X a P-X), che secondo il lemma (vedi punto precedente) deve far parte dell'albero minimo
  • utilizzando la struttura dati "heap" si ottiene la complessità computazione di O(m + n log n)
  • algoritmo
    • 1. Si parte con una matrice che descrive la distanza da un punto ad un altro punto.
    • 2. Si utilizza una lista (V_t) che contiene tutti i nodi già presi in considerazione. All'inizio la scelta del nodo è arbitraria.
    • 3. E_t contiene invece le connessioni fatte e all'inizio è vuoto.
    • 4. ζ(V) invece contiene tutte le connessioni che partono dai nodi contenuti in V_t.
    • 5. Metto dentro V_t il nodo di partenza.
    • 6. E_t è vuoto, ζ(V) contiene ora gli archi uscenti dal nodo di partenza.
    • 7. Prendo la connessione con peso (o distanza) minore in ζ(V) e inserisco il nodo correlato nella lista V_t, l'arco nella lista E_t e dopo aggiorno ζ(V) mettendo tutte le connessioni che ora si possono fare sia col nodo di partenza, che col nuovo arco inserito nella lista V_t.
    • 8. Ovviamente tolgo da ζ(V) la connessione appena inserita in E_t.
    • 9. Si prosegue tenendo in considerazione che non bisogna prendere connessioni della lista ζ(V) tra due nodi già presenti in V_t, altrimenti creo un ciclo.
    • 10. Finisco quando tutte le connessioni possibili in ζ(V) creerebbero cicli.
• problema del flusso massimo
  • trovare il flusso massimo in una rete ridotta (P,U) con nodo di ingresso p₀ e nodo di uscita p_n
  • la ricerca del un flusso massimo in una rete di trasporto qualsiasi equivale alla ricerca del flusso massimo in una rete ridotta ottenuta aggiungendo alla rete iniziale gli archi(p₀,p_e) di capacità c(p₀,p_e)≥c(p_e,P) p_e∈E ,(p_s,p_n) di capacità c(p_s,p_n)≥c(P,p_s) p_n∈S con E = insieme di tutti i nodi di entrata, S = insieme di tutti i nodi di uscita, P = insieme di tutte i nodi di transito
  • si suppone che:
    • la disponibilità in p₀ e la domanda in p_n sono infinite
    • non esiste un cammino da p₀ a p_n in cui tutti gli archi hanno capacità infinita
  • formalizzazione come problema PL
    • max ∑_j=0,n x_0j ≡ ∑_j=0,n x_jn ≡ φ
    • 0 ≤ x_ij ≤ c_ij , (i,j) ∈ U
    • ∑_j=0,n (x_ij - x_ji) = 0 , i = 1, ..., n-1
    • x_ij è il flusso aritmetico dell'arco (i,j)
• algoritmo di Ford-Fulkerson
  • trova il flusso massimo in una rete di trasporto
  • l'algoritmo è composto da due parti chiamate da Ford e Fulkerson rispettivamente Routine A e Routine B. La prima è un processo di etichettatura che cerca l'augmenting path (percorso con capacità disponibile, ovvero un percorso da s a t in cui il flusso > capacità lungo tutti gli archi orientati da s a t e flusso > 0 per tutti gli archi orientati da t ad s). Se la Routine A trova un augmenting path, la Routine B modifica corrispondentemente il flusso. Altrimenti, non esiste alcun augmenting path e l'ottimalità del flusso corrente è assicurata dal seguente teorema: un flusso f è massimo se e solo se non ci sono altri flussi di augmenting path rispetto ad f
• problema del flusso di costo minimo
  • sia data una rete di trasporto semplice (P₁,P₂,U₀) per la quale in ciascun nodo di entrata p_i è definita una disponibilità positiva a_i(o una domanda negativa -a_i) ed in ciascun nodo d'uscita q_j è definita una domanda positiva b_j e su ciascun arco (p_i,q_j)∈U è definito un costo unitario c_ij, del flusso. Si vuole trovare un flusso aritmetico x che soddisfi la domanda in ciascun nodo e che il costo del trasporti sia minimo
  • formulazione matematica (standard)
    • min z = ∑_(i,j)∈MN c_ijx_ij
    • ∑_j∈N = a_i , i ∈ M
    • ∑_i∈M = b_j , j ∈ N
    • 0 ≤ x_ij ≤ k_ij , (i,j) ∈ MN
    • ∑ a_i = ∑ b_j , a_i > 0 , b_j > 0 , c_ij ≥ 0
    • nota:
      • si suppone che per ogni coppia di nodi p_i,p_j esista l'arco (p_i,p_j), eventualmente creando archi fittizi con capacità nulla
      • M={1,..,m} è l'insieme degli indici dei nodi d'entrata
      • N= {1, ..., n} è l'insieme degli indici dei nodi d'uscita
        • si aggiunge una destinazione fittizia q_n di capacità k_in=+∞ verso cui si indirizza la disponibilità eccedente la domanda; ossia: b_n = ∑_i∈M a_i - ∑_j∈N b_j
        • in un flusso ottimale per i vincoli relativi alle uscite deve valere l'uguaglianza, il segno "=" può sostituirsi al segno di "≥"
        • la rete (P1,P2,U) che è semplice la si trasforma in una rete ridotta aggiungendo un nodo q₀ e gli archi (q₀,p_i), i∈M,di capacità k_oi, i=a_i ed un nodo p_v e gli archi (q_j,p_v), j∈N di capacità k_jv=b_j
        • ad ogni soluzione ottimale corrisponde un flusso che satura gli archi estremi e viceversa
    • il problema si risolve con un algoritmo chiamato algoritmo del simplesso per le reti di trasporto che combina l'algoritmo del simplesso e l'algoritmo di Ford-Fulkerson
• differenza tra il problema del trasporto ed il problema di flusso di costo minimo in una rete
  • nel problema dei trasporti non si tiene conto della capacità di ciascun cammino (arco)