Appunti Optimization and data science for management (primo parziale, parte 2)

Metodo del costo minimo nel problema di trasporto

Si prende il valore minimo del costo di trasporto, si confrontano i corrispettivi valori in rosso della riga e colonna corrispondente, si seleziona il minimo. A questo punto si sostituisce, come valore nel costo di trasporto, questo valore, mentre al posto del valore in rosso mettiamo zero.

Modalità iterativa di applicazione: tra i valori in nero (costi di trasporto, matrice 3×3) selezioniamo il minimo, poi assegniamo a quella cella il minimo tra le due capacità in rosso nella riga e nella colonna corrispondenti. Dopo aver fatto questo, dobbiamo aggiornare i valori della capacità dell’agrumeto e dell’impianto.

Non può uscire più flusso dalla sorgente 3, quindi le altre 2 variabili relative alla terza sorgente sono uguali a 0. Ripetiamo il processo come prima, ma ora consideriamo una matrice 2×3, dato che la terza sorgente è saturata.

Il processo termina quando tutte le disponibilità sono esaurite e tutte le destinazioni sono soddisfatte.

La soluzione finale

Questo è un approccio “cieco” perché l’algoritmo prende la decisione ottimale nel momento, ma in questo modo potrebbe evitare soluzioni più economiche.

Si spostano semplicemente queste 75 unità di flusso lungo questo ciclo verde.

La capacità totale degli impianti è maggiore di quella degli agrumeti, quindi questo sbilanciamento è corretto.

La soluzione ottima può essere trovata partendo da quella euristica inviando 75 unità di flusso lungo il ciclo verde. Qui l’algoritmo greedy non garantisce che la soluzione ottenuta sia esattamente quella ottima, ma fornisce solo un metodo rapido per ottenere una soluzione ammissibile.

Si utilizza lo stesso approccio applicato alla risoluzione del problema di flusso a costo minimo (MCF): partendo da una soluzione greedy, si costruisce la rete residua (in verde) e si spostano alcune unità di flusso per trovare la soluzione ottima. In questo modo si corregge l’errore “cieco” del metodo greedy.

Algoritmo ungherese: è uno dei più famosi tra i problemi di trasporto.

Un problema di produzione multiperiodo

Questo tipo di problema ci mostra che è possibile rappresentare e modellare il tempo come una rete. Invece di spostare beni da un impianto a un altro, qui decidiamo per ogni mese quanto produrre e quanto immagazzinare, trasferendo la produzione da un mese all’altro.

La Upton Corporation produce compressori d’aria ad alte prestazioni per il mercato domestico e per quello industriale leggero. Attualmente Upton sta cercando di pianificare i livelli di produzione e di inventario per i prossimi sei mesi.

A causa delle fluttuazioni stagionali nei costi delle utenze e delle materie prime, il costo unitario di produzione dei compressori varia da mese a mese, così come varia la domanda di compressori.

Anche la capacità produttiva varia di mese in mese a causa delle differenze nel numero di giorni lavorativi, delle ferie e delle attività programmate di manutenzione e formazione.

Vincoli e obiettivo

• Data la dimensione del magazzino di Upton, è possibile mantenere al massimo 6.000 unità in inventario alla fine di ogni mese (vincoli di capacità).
• Il proprietario dell’azienda preferisce mantenere almeno 1.500 unità in magazzino come scorta di sicurezza per far fronte a eventuali variazioni impreviste della domanda (livello minimo di scorta).
• Per mantenere una forza lavoro stabile, l’azienda vuole produrre almeno la metà della propria capacità produttiva massima ogni mese (stabilità della produzione). Ogni mese si deve produrre almeno metà della capacità massima di produzione di quel mese (questo rappresenta il limite inferiore della produzione).
• Il responsabile finanziario di Upton stima che il costo di mantenimento di un’unità in un dato mese sia circa pari all’1,5% del costo unitario di produzione nello stesso mese (costi di magazzino).
• Upton stima il numero di unità mantenute in inventario ogni mese facendo la media tra l’inventario iniziale e quello finale di ciascun mese (stima dello stock). Il costo di magazzino viene quindi calcolato su questo valore medio: media tra inventario all’inizio e alla fine del mese.
• Attualmente sono presenti 2.750 unità in magazzino (livello iniziale di scorta).
• Upton vuole determinare il piano di produzione e di inventario per i prossimi sei mesi che soddisfi la domanda prevista ogni mese minimizzando i costi di produzione e di magazzino.

Vincoli di conservazione del flusso

Vincoli di conservazione del flusso + − = Bilancio delle scorte → # # # #-% ( )

Lo stock con cui inizio il mese successivo è uguale allo stock con cui ho iniziato questo #-%( ), ( ), ( ). mese più ciò che ho prodotto meno ciò che ho venduto # # #

Per risolvere il problema, si costruisce un grafo in cui ogni nodo rappresenta un mese.

Un problema di produzione multiperiodo: il modello matematico

Estensione di questo problema: considerare un problema multicommodity, quindi si gestiscono più prodotti invece di uno solo.

Modello di flusso di cassa multiperiodo (parametri in blu, variabili in rosso)

Paradosso di Braess

Un utente introduce un nuovo percorso per raggiungere il nodo 4, quindi ora abbiamo 3 possibili percorsi.

L’opzione migliore si ottiene quando troviamo un equilibrio tra tutti i percorsi possibili che portano alla destinazione.

L’apertura di una nuova strada in una rete di strade non porta sempre a un miglioramento nel traffico.

Matching and assignments

Finora abbiamo considerato costi lineari, ma nella realtà questo non è molto frequente, perché è più comune che il costo dipenda dalla quantità di flusso che si invia nel grafo.

I matching sono sottografi con la proprietà che ogni nodo del sottografo ha grado 0 o 1, cioè nessun nodo è incidente a più di un arco nel sottografo.

Il problema di assignment è un caso particolare del matching.

I mattoni fondamentali

• Cammino minimo e massimo
• Flusso a costo minimo
• Flusso massimo
• Matching e assegnamento
• Albero ricoprente

E la loro integrazione in problemi complessi:

• Problema del commesso viaggiatore
• Problema di instradamento dei veicoli
• Problema di progettazione delle reti

Integrare questi elementi per creare problemi più complessi.

Matching

Gli archi non sono orientati in questo caso; un sottografo è un insieme di archi in cui ogni nodo coinvolto ha grado pari a 0 oppure 1.

Se aggiungiamo l’arco rosso, perdiamo il matching. Il matching sono gli archi verdi.

Un matching è un sottografo in cui ogni nodo ha grado (numero di archi incidenti) pari a 0 oppure a 1. Nessuna coppia di archi condivide lo stesso nodo.

Che tipo di grafo?

La complessità del problema dipende dalla struttura del grafo sottostante. Possiamo avere:

1. Un grafo bipartito: gli algoritmi sono specializzazioni degli algoritmi generali per il flusso a costo minimo.
2. Un grafo non bipartito: sono necessari algoritmi ad hoc e i problemi risultanti sono più difficili da risolvere.

Problemi tipici di matching

La differenza è tra la cardinalità massima (si cerca il numero massimo di archi nel grafo di matching) e il costo minimo (si seleziona il giusto numero di archi, rispettando il matching, in modo da minimizzare il costo).

Grafo bipartito:

3. Problema di matching a cardinalità massima
4. Problema di assegnamento a costo minimo (matching perfetto)
5. Problema di assegnamento bottleneck
6. Matching stabile

Grafo non bipartito:

Problema di matching a cardinalità massima – alcuni cenni sull’idea algoritmica (cardinalità=numero di archi).

Grafo bipartito: assegnazione del personale

Il matching su grafo bipartito è un caso in cui gli oggetti sono suddivisi in due gruppi e vogliamo abbinare gli oggetti dei due gruppi in modo ottimale.

Nell’assegnazione dei compiti ai nuovi assunti: la cardinalità è la stessa tra i due gruppi di nodi, a ogni lavoratore viene assegnato un turno.

Nella selezione dei migliori nuotatori per una squadra, la cardinalità è diversa; questo dipende dalla specifica applicazione.

Assegnazione dei turni ai lavoratori (esempio)

Per ogni lavoratore esiste una preferenza che il lavoratore assegna al turno.

Qual è il modo migliore per abbinare lavoratori e turni in modo da minimizzare il punteggio totale dell’assegnamento?

• Il punteggio totale è 10, valore ottimo
• In rosso è riportata la soluzione ottima

La variabile è ed è una variabile binaria; quindi, il valore associato a questa variabile è 1 se #! assegniamo il turno e 0 altrimenti. ∈ ∈ .

P insieme del personale, S insieme dei turni, preferenza di assegnare a #! ⋅ - Minimizzare la somma su tutti i possibili e di #! #! ∈ di = 1 ∈ - Sommatoria rispetto a per ogni #! ∈ di = 1 ∈ - Sommatoria rispetto a per ogni #! ∈ {0,1} e - per ogni (definizione del dominio). #!

Ottimizzazione delle tariffe di viaggio (esempio)

Cerchiamo di costruire un problema di matching a partire dal problema precedente.

Possiamo partire da Londra o da Firenze.

Una soluzione ammissibile qui si ottiene abbinando ogni nodo con uno solo dell’altro gruppo.

Si parte dall’arco più conveniente, quindi da quelli verdi, e poiché tra gli ultimi archi abbiamo più di 21 giorni, otteniamo 2 archi verdi. Successivamente si passa all’arco giallo e a quello rosso, se necessario.

Se si parte in modo greedy ma alla fine si entra in un nodo già connesso, non si ottiene una soluzione ammissibile.

Soluzione ottima

• Stimare velocità e direzione del movimento di n oggetti in movimento
• 2 immagini consecutive per ciascun oggetto
• Matching della posizione degli oggetti nelle 2 immagini

Si considerino 2 immagini con n oggetti ciascuna. 5 5{( , )}.

Le coordinate dell’oggetto j nel frame f sono note ! !

Il problema è il seguente: quale oggetto nel frame A corrisponde a quale nel frame B? È un problema di matching con costi.

Notazione usata = (, ) = ∪ - con = {1, … , } - insieme dei nodi di origine = { + 1, … ,2} - insieme dei nodi di destinazione ∣ ∣= - insieme degli archi, con (cardinalità) (, ) ∈ - per ogni arco (costi arbitrari) < 0#!

Assunzioni ∣ ∣=∣ ∣ - Assunzione 1: senza perdita di generalità (w.l.o.g.) possiamo assumere (usando nodi fittizi se non è così). - As