Glossario · approach
Regola dell'Angolo Nord-Ovest
L'euristica classica più semplice per generare una soluzione iniziale di base ammissibile del problema di trasporto: partire dall'angolo in alto a sinistra della matrice dei costi, assegnare il più possibile alla cella corrente e spostarsi a destra o in basso fino a esaurire offerta e domanda.
Northwest Corner RuleNWCRegola del Vertice Nord-Ovest
La Regola dell'Angolo Nord-Ovest è l'euristica classica più semplice per produrre una soluzione iniziale di base ammissibile del problema di trasporto: parti dall'angolo in alto a sinistra (nord-ovest) della matrice dei costi, assegna alla cella corrente il massimo possibile (il minimo tra l'offerta residua e la domanda residua), poi spostati a destra (se l'offerta è residua) o in basso (se la domanda è residua) e ripeti finché tutte le somme di riga e colonna siano soddisfatte. La soluzione ottenuta è ammissibile ma in genere lontana dall'ottimo — ignora del tutto la matrice dei costi e lavora solo per posizione. L'ottimo si raggiunge con MODI / Stepping-Stone o direttamente con il Simplesso. Valore didattico: mostra il concetto di 'partenza di base ammissibile' alla base del Simplesso ed è un trampolino verso partenze più intelligenti come il Metodo di Approssimazione di Vogel (VAM). Approfondito in Bazaraa-Jarvis-Sherali (2010).
Örnek
3 stabilimenti (capacità 20, 30, 25 tonnellate) × 4 clienti (domande 15, 20, 18, 22 tonnellate). NWC parte dall'angolo in alto a sinistra: cella (1,1) riceve min(20,15)=15 t; poi (1,2) min(5,20)=5 t; (2,2) min(30,15)=15 t; (2,3) min(15,18)=15 t; (3,3) min(25,3)=3 t; (3,4) min(22,22)=22 t. Totale 75 t assegnate; la soluzione iniziale è pronta, poi viene ottimizzata con MODI o simplesso.