Trasporto e assegnamento¶
Parte 3 · Flussi · Capitolo 7 · Dispensa, volume 3 (PDF) · Esercizi: Trasporto e assegnamento
-
7.1 Il problema dei trasporti
Istanze non bilanciate · Trasbordo come problema di trasporto
-
7.2 Soluzioni di base
-
7.3 Soluzioni iniziali di base fattibili
La regola del costo minimo
-
7.4 Il metodo potenziale
Il metodo potenziale sull'istanza di trasporto · Degeneracy
-
7.5 Il problema dell'assegnazione
Degenerazione del metodo potenziale · Riduzioni e potenziali · Zeri indipendenti e righe · L'algoritmo ungherese · L'algoritmo ungherese nell'esempio
Prerequisiti
-
Da questo modulo, Capitolo 1 «Grafi»: alberi, foglie, cicli fondamentali e rango della matrice di incidenza nodo-arco.
-
Da questo modulo, Capitolo 3 «Percorsi più brevi»: distanze e Capitolo 4 «Modelli di flusso di rete»: il modello di flusso a costo minimo, il nodo dummy, vertici interi, potenziali e costi ridotti.
-
Dal modulo Programmazione lineare, Capitolo 9 «Teoria della dualità»: il duale di un modello LP e i teoremi della dualità debole e forte.
Obiettivi
Alla fine di questo capitolo sarai in grado di:
-
formulare il problema di trasporto e rappresentarlo in tabella, bilanciare un'istanza aggiungendo un'origine o una destinazione fittizia e ridurre un problema di trasbordo senza capacità a un problema di trasporto;
-
interpretare le basi del modello di trasporto come alberi ricoprenti di una rete bipartita, calcolare una soluzione di base e riconoscerne la degenerazione;
-
costruire una soluzione ammissibile di base iniziale con la regola dell'angolo nord-ovest o quella del costo minimo;
-
applicare il metodo dei potenziali, calcolare i costi ridotti e i cicli di pivot e certificare l'ottimalità con il modello duale;
-
formulare il problema di assegnamento, dimostrare il teorema di König–Egerváry ed eseguire l'algoritmo ungherese, interpretando i potenziali come una soluzione duale ottimale.
Avanti: 7.1 Il problema dei trasporti
Esercizi su questo capitolo: Trasporto e assegnamento