Problema di assegnazione nella programmazione lineare: modello di introduzione e assegnazione

Il problema di assegnazione è un tipo speciale di problema di programmazione lineare che riguarda l'allocazione delle varie risorse alle varie attività su base individuale. Lo fa in modo tale che il costo o il tempo coinvolti nel processo sia minimo e il profitto o la vendita sia massimo. Sebbene i problemi possano essere risolti con il metodo simplex o con il metodo di trasporto, il modello di assegnazione fornisce un approccio più semplice per questi problemi.

In una fabbrica, un supervisore può avere sei lavoratori disponibili e sei posti di lavoro da licenziare. Dovrà prendere una decisione riguardo a quale lavoro dovrebbe essere assegnato a quale lavoratore. Il problema si forma uno a uno. Questo è un problema di assegnazione.

1. Modello di assegnazione:

Supponiamo che ci siano n facilitazioni e n lavori sia chiaro che in questo caso, ci saranno n incarichi. Ogni struttura o dire lavoratore può eseguire ogni lavoro, uno alla volta. Ma ci dovrebbe essere una certa procedura in base alla quale si dovrebbe eseguire l'assegnazione in modo che il profitto sia massimizzato o il costo o il tempo sia ridotto al minimo.

Nella tabella, Coij è definito come il costo quando il lavoro viene assegnato al lavoratore. Forse ha notato qui che questo è un caso speciale di problema di trasporto quando il numero di righe è uguale al numero di colonne.

Formulazione matematica:

Qualsiasi soluzione fattibile di base di un problema di assegnazione consiste in variabili (2n - 1) di cui le variabili (n - 1) sono pari a zero, n è il numero di lavori o il numero di strutture. A causa di questa elevata degenerazione, se risolviamo il problema con il solito metodo di trasporto, sarà un lavoro complesso e dispendioso in termini di tempo. Quindi una tecnica separata è derivata per questo. Prima di passare al metodo assoluto è molto importante formulare il problema.

Supponiamo che xj sia una variabile definita come

1 se il lavoro è assegnato a J macchina o impianto

0 se il primo lavoro non è assegnato a j th machine o facility.

Ora, dato che il problema forma uno a uno, o un lavoro deve essere assegnato a una struttura o a una macchina.

Il costo totale di assegnazione sarà dato da

La definizione di cui sopra può essere sviluppata in modello matematico come segue:

Determina x ij > 0 (i, j = 1, 2, 3 ... n) per

Sottoposto a vincoli

e x ij è zero o uno.

Metodo per risolvere il problema (tecnica ungherese):

Considerare la funzione obiettivo del tipo di minimizzazione. I seguenti passaggi sono coinvolti nella risoluzione di questo problema di assegnazione,

1. Individuare l'elemento di costo più piccolo in ogni riga della tabella dei costi specificata iniziando dalla prima riga. Ora, questo elemento più piccolo viene sottratto da ogni elemento di quella riga. Quindi, otterremo almeno uno zero in ogni riga di questa nuova tabella.

2. Dopo aver costruito la tabella (come dal punto 1), prendi le colonne della tabella. A partire dalla prima colonna individuare l'elemento di costo più piccolo in ogni colonna. Ora sottrai questo elemento più piccolo da ogni elemento di quella colonna. Avendo eseguito il passaggio 1 e il passaggio 2, otterremo almeno uno zero in ciascuna colonna nella tabella dei costi ridotti.

3. Ora, i compiti sono fatti per la tabella ridotta nel modo seguente.

(i) Le righe vengono esaminate successivamente, finché non viene trovata la riga con esattamente uno (uno) zero. Si assegna a questo singolo zero mettendo quadrato □ attorno ad esso e nella colonna corrispondente, tutti gli altri zero sono cancellati (x) perché questi non saranno usati per fare nessun altro incarico in questa colonna. Il passaggio è condotto per ogni riga.

(ii) Fase 3 (i) ora eseguita sulle colonne come segue: - le colonne vengono esaminate successivamente finché non viene trovata una colonna con esattamente uno zero. Ora, si assegna a questo singolo zero il quadrato attorno ad esso e allo stesso tempo, tutti gli altri zeri nelle righe corrispondenti vengono cancellati (x) il passo viene eseguito per ogni colonna.

(iii) I punti 3, (i) e 3 (ii) sono ripetuti finché tutti gli zeri non sono segnati o cancellati. Ora, se il numero di zeri segnati o le assegnazioni effettuate sono uguali al numero di righe o colonne, è stata raggiunta la soluzione ottimale. Ci sarà esattamente un singolo incarico in ciascuna o colonne senza alcun incarico. In questo caso, andremo al passaggio 4.

4. In questa fase, traccia il numero minimo di linee (orizzontali e verticali) necessarie per coprire tutti gli zeri nella matrice ottenuta nel passaggio 3, viene adottata la seguente procedura:

(i) Segno di spunta (

) tutte le righe che non hanno alcun incarico.

(ii) Ora segno di spunta (

) tutte queste colonne che hanno zero nelle righe contrassegnate con il segno di spunta.

(iii) Ora seleziona tutte le righe che non sono già marcate e che hanno assegnazioni nelle colonne contrassegnate.

(iv) Tutti i passaggi cioè (4 (i), 4 (ii), 4 (iii) vengono ripetuti fino a quando non è possibile contrassegnare più righe o colonne.

(v) Ora disegnare linee rette che passano attraverso tutte le righe non contrassegnate e colonne contrassegnate. Si può anche notare che in una matrice nxn, sempre meno di 'n' linee copriranno tutti gli zeri se non ci sono soluzioni tra loro.

5. Al punto 4, se il numero di linee tracciate è uguale a n o il numero di righe, allora è la soluzione ottimale in caso contrario, quindi andare al passaggio 6.

6. Seleziona l'elemento più piccolo tra tutti gli elementi scoperti. Ora, questo elemento viene sottratto da tutti gli elementi scoperti e aggiunto all'elemento che si trova all'intersezione di due linee. Questa è la matrice per i nuovi compiti.

7. Ripetere la procedura dal punto (3) fino a quando il numero di assegnazioni diventa uguale al numero di righe o al numero di colonne.