Anteprima
Vedrai una selezione di 4 pagine su 12
Riassunto programma di metodi e modelli per le decisioni Pag. 1 Riassunto programma di metodi e modelli per le decisioni Pag. 2
Anteprima di 4 pagg. su 12.
Scarica il documento per vederlo tutto.
Riassunto programma di metodi e modelli per le decisioni Pag. 6
Anteprima di 4 pagg. su 12.
Scarica il documento per vederlo tutto.
Riassunto programma di metodi e modelli per le decisioni Pag. 11
1 su 12
D/illustrazione/soddisfatti o rimborsati
Disdici quando
vuoi
Acquista con carta
o PayPal
Scarica i documenti
tutte le volte che vuoi
Estratto del documento

ESPLORAZIONE NODI GRAFO

  • VENTAGLIO (BFS) LARGHEZZA → TUTTI I NODI VICINI A S (la) HANNO LIVELLO LA - DIST. DA S
  • SCANDAGLIO (DFS) PROFONDITÀ → S = 1 POI 2, 3, ... X VICINANZA

CAMMINI MINIMI

  • NO CIRCUITI → ESISTE CAMMINO MIN
  • NO CIRCUITI → LUNGHEZZE MIN = UNICHE SOL. EQ. BELLMAN
  • BELLMAN
    1. Ms = 0 (NO CIRCUITI NEGATIVI)
    2. (i, j) ∈ A → Mj ≤ Mi + lij
    3. ∀ j ≠ s → LUNGO CAMMINO MIN DA S A j; ESISTE NODO k PREDECESSORE DI j, CIOÈ (k, j) ∈ A. X OTTIMALITÀ: Mj = Mk + lkj
    4. Da 2) e 3) → Mj = min {Mi + lij | (i, j) ∈ A}, ∀j ≠ s
  • DIJKSTRA
    • SOLO SE TUTTI GLI ARCHI lij > 0!
    • INIZIO: λ = 0, p0, p...
    • P = 0, 0, 0, 0...
  • FLOYD - WARSHALL
    • CAMMINI MIN TRA TUTTE LE COPPIE DI NODI!
    • MATRICI D e P → [NO ARCO: ∞
    • i ≠ j : 0
    • AGGIORNAMENTI: lij SUDIAGONALE: CIRCUITI NEGATIVI

ALBERO INCOGNENTE MIN (MST)

  • G CONNESSO e |A| = |V| - 1
  • G PRIVO DI CICLI e |A| = |V| - 1
  • OGNI COPPIA DI NODI CONNESSA DA UNICO CAMMINO
  • G PRIVO DI CICLI e UNENDO 2 NODI NON ADIACENTI SI HA CICLO

CONSIDERO SOLO CERTI ARCHI DEL GRAFO → ARCO DI E MIN USCENTE DA UN NODO QUALSIASI È UN ARCO DEL MST (ARCHI DA NODI COLLEGATI A NODI NON COLLEGATI)

PBM ZAINO 0-1

max z(x) = Σj=1m Cj Xj → guadagno atteso

Σj=1m aj Xj ≤ b → non posso superare budget

Xj ∈ {0,1} ; j=1,...m → variabili binarie

|U| = insieme ambiente = 2m

se b - Σj=1m aj Xj/2 → almeno metà dei sottoinsiemi di N sono ammissibili cioè X ha almeno 2m-1 elementi.

PBM ASSEGNAZIONE

min z(x) = Σi=1m Σj=1m Cij Xij → costo assegnazione

Σj=1m Xij = 1 (i=1,...,m) → ogni Persona (i) → 1 uomo

Σi=1m Xij = 1 (j=1,...,m) → ogni Lavoro (j) → 1 persona

Xij ∈ {0,1}; j=1,...,m → variabili binarie

X = insieme ammissibile = permutazioni su {1,...,n} → |X| = m!

PBM COPERTURA

min z(x) = Σj=1m Cj Xj → costo salari pagati a medi.

Σj=1m aijXj≥1 (∀i ∈ M) → almeno 1 medico fa interv. i

Xj ∈ {0,1}; j=1,...,m → variabili binarie

N = {1,...,m,n} insieme finito medici (j)

M = {1,...,m,n} insieme finito interventi (i) → Mj ⊂ M ∀j ∈ N

Copertura di M tramite N → ⊂N t.c.

∪ Mj = M

PBM IMPACCAMENTO

Σj=1m aijXj≤1 (∀i ∈ M) → al più 1 medico fa interv. i

Impaccamento di M tramite N → ⊂N t.c.

Mj ∩ Mk = ∅ ∀j,k ∈ T j≠k

PBM PARTIZIONE

(max o min)

Σj=1m aijXj=1 (∀i ∈ M) → esattamente 1 medico fa int. j

Partizione di M tramite N → ⊂N t.c.

∪ Mj = M e Mj ∩ Mk = ∅

(PL) AMMETTE SBA OTTIME INTERNE?

SE det B = ±1 ➔ SBA {X:B^-1b,O} E A COMPONENTI INTERNE.

INFATTI BcB SEMPRE A COMPONENTI INTERNE.

B^-1 = A/det((I-A)T)s det Bi,j , MATRICE B SENZA j-ESIMA RIGA e i-ESIMA COLONNA

SE X SBA OTTIMA DI (PL) ➔

PROPRIETÀ 3 INVALIDAMENTI

X s.o. DI (PI)

MATRICI TOTALMENTE UNIMODULARI (TU)

COEFFICIENTI INTERI e det = ±1, 0, 1 PER OGNI SOTTOMATRICE QUADRATA,

SE A ∈ TU ➔ (PL) AMMETTE SBA OTTIMA INTERNA INTERNO B

PER IL QUALE AMMETTE UNA SOLUZIONE OTTIMA.

  • CONDIZ. NECESSARIA E SUFFICIENTI:
  • A, AT, -A , [A,A], [A,I], [A,-A], [AI], [-AI] ... SONO TU
  • CONDIZ. SUFFICIENTI: ➔ MATRICE TU PUÒ (NON) SODDISFARE
  • 1) COEFFICIENTI = 0, -1, 1
  • 2) OGNI COLONNA MA 2 COEFF. ≠0
  • 3) RIGHE RIPARTITE IN 2 SOTTOINSIEMI T.C.

• COLONNA HA 2 COEFF. = ±1 ⇔ G-A ➔ SOTTOINSIEMI DI RIGHE ≠

• COLONNA HA UN COEFF. = 1 e UNO = -1 ➔ STESSO SOTTOINSIEME

MATRICE INCIDENZA NODI-ARCHI

  • • GRAFO ORIENTATO ➔ TU ➔ MA=M e M2=∅
  • • GRAFO NON ORIENTATO ➔ IN GENERALE NO TU
  • • GRAFO NON ORIENTATO BIPARTITO ➔ TU ➔ MA=V1 e M2=V2

TEOREMA DI INTEREZZA

{ x ∈ ℝm: Ax=b, x⪰0 }

  • • FORMA STANDARD
  • 1)SE A ∈ TU ➔ VERTICI DI P(A,b) SONO INTERI ∀ b∈ℤm PER CUI
  • P(A,b) ≠∅

  • 2)SE A ∈ TU ➔ (PL) max ℕ{x: Ax=b, x⪰0} AMMETTE SBA OTTIMA
  • INTERNA ∀ b (VETTORI INTERNI) PER CUI IL PBL AMMETTE S.O.

  • 3)SE A ∈ TU ➔ (PL) minbℕ {y: AT y⪯c, y∈ℝm} AMMETTE SBA OTTIMA
  • INTERNA ∀ c (VETTORE INTERNO) PER CUI IL PBL AMMETTE S.O.

    N.B. A É TU ➔ P(A,b) HA VERTICI INTERNI

    DUALE LAGRANGIANO VS RILASSAMENTO LINEARE

    v.o. (DL) = W+DL = max {cTx: Dx ≤ d, x ∈ CONV(X)} ⊂ ℝm Program. Lineare

    NB:

    CONV(x) = CONV{x ∈ ℤm+: Ax ≤ b } ⊃ {x ∈ ℤm+: Ax ≤ b } ⊂ ℝm+

    (PL) Z+PL = max{zPL = cTx: Dx ≤ d, Ax ≤ b, x ∈ ℝm+^}R.A. DI (P*) CONV(X) ∩ {x ∈ ℝm+: 0x ≤ d }R.A. DI (PL) = {x ∈ ℝm+: Ax ≤ b } ∩ { x ∈ ℝm+: Dx ≤ d }

    SICCOME L.A. DI (P*) ⊂ R.A. DI (PL) Z+PLW+DL ≤ ZPL

    DUALE LAGRANGIANO DA STIME MIGLIORI DI RILASSAM. LINEARE

    CASI PARTICOLARI:

    • 1 Z+PL = W+DL CONV(X ∩ {x ∈ ℝm+: Dx ≤ d }) = CONV(X) ∩ {x ∈ ℝm+: Dx ≤ d }
    • 2 W+DL = ZPL CONV(X) = { x ∈ ℝm+: Ax ≤ b }

    Pbm Zaino (0-1 6 INTERO): W+DL = 2PL (stima duale Lagr. = rilassam. lineare)

    Valore/Ingombr e ordine da Maggiore a MinoreLM = Zpi + M(b - ax) → raccolgo le x

    Vincolo budget

    • M > 0
    • 0 = 1
    • 0 -1

    *

    4-2M

    4-3M

    wDL(m) := L* {12-3m 0 ≤ m ≤ 1/211-m 1/2 ≤ m ≤ 1

    trovo min → S.O. = M* = 1 (M che da min)V.O. = M sostituito nella sua eq.

    SO (PL) → A per valore/ingombro ↑ poi frazioni (vincolo budget)VO (PL) → metto le x nella funz. obiettivo

    INTERNI:

    A Uguale

    wDL(m): = L* {+∞, 0 ≤ m < 2 → Dove ho almeno un{+m, M > 2

    trovo min → M* ≥ 2 → S.O.7 - 2 = 14 = V.O.

    SO (PL) → valore max dove valore/ingombro ↑ (vincolo budget)VO (PL) → metto le x nella funz. obiettivo

Dettagli
Publisher
A.A. 2020-2021
12 pagine
SSD Scienze economiche e statistiche SECS-P/08 Economia e gestione delle imprese

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher smfp di informazioni apprese con la frequenza delle lezioni di Metodi e modelli per le decisioni e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Università degli Studi di Parma o del prof Nicolodi Lorenzo.