Controllo dell'ottimalità
Il test dell'ottimalità può essere eseguito se sono soddisfatte due condizioni, ad es
1. Ci sono m + n - 1 allocazioni, il cui m è il numero di righe, n è il numero di colonne. Qui m + n - 1 = 6. Ma il numero di assegnazione è cinque.
2. Queste assegnazioni di m + n - 1 dovrebbero essere in posizioni indipendenti. Vale a dire non dovrebbe essere possibile aumentare o diminuire alcuna allocazione senza modificare la posizione delle allocazioni o violare le restrizioni di riga o colonna.
Una semplice regola per le allocazioni di essere in posizioni indipendenti è che è impossibile viaggiare da qualsiasi allocazione, tornando a se stesso da una serie di passaggi orizzontali e verticali da una cella occupata a un'altra, senza un'inversione diretta della rotta. Si può vedere che nel presente esempio, l'allocazione è in posizioni indipendenti in quanto non è possibile formare un anello chiuso alle celle allocate.
Quindi la prima condizione non è soddisfatta e quindi per soddisfare la prima condizione, dovremo allocare una piccola quantità E alle celle vuote che hanno il più basso costo di trasporto. Si può vedere che t può essere assegnato alla cella (2, 2) avendo un costo di 7 unità e tuttavia le allocazioni rimarranno in posizione indipendente come descritto di seguito:
Ora il numero di allocazione è m + n- = 6 e sono in posizioni indipendenti.
Annotare la matrice dei costi nelle celle allocate.
Matrice costi iniziali per celle allocate.
Scrivi anche i valori di u i e v j come spiegato in precedenza.
Matrice di valutazione cellulare
Dalla tabella 5 si può vedere che la valutazione delle cellule nella cella (1, 4) è negativa, vale a dire -4, quindi allocando a cella (1, 4) i costi di trasporto possono essere ulteriormente ridotti. Scriviamo le allocazioni originali e la nuova allocazione proposta.
Dalla tabella 6 si può vedere che se assegniamo alla cella (1, 4) un loop è formato come mostrato e allociamo 10 unità in modo che l'allocazione alla cella (2, 4) svanisca come mostrato di seguito nella tabella 7.
La nuova tabella di allocazione diventerà
Costi di trasporto = 5X 2 + 10X 1 1 + 10X 7 + 15X9 + 5X 4 + 18 + 5 = 435 unità. Ad esempio, il costo del trasporto è sceso da 475 unità a 435 unità.
Controlla per ottimismo:
Vediamo se questa soluzione è optima! o no? Per questo ancora due condizioni devono essere controllate cioè
Numero di assegnazione = m + n - 1 = 6 (soddisfatto)
Assegnazione a posizione indipendente (soddisfatta dal momento che il circuito chiuso per le celle allocate non è formato)
Scrivi il costo ai valori all assegnati e ai valori di u i e v j
Esempio 2:
(Offerta e domanda squilibrata). Risolvi il seguente problema di trasporto
Rifornimento totale = 200 unità, domanda = 185 unità.
Soluzione:
Poiché offerta e domanda non sono uguali, il problema è squilibrato. Per bilanciare il problema, è necessario aggiungere una colonna fittizia come mostrato di seguito. La domanda in quella colonna fittizia (negozio) sarà di 15 unità.
Soluzione fattibile di base:
Useremo il metodo di approssimazione di Vogel per trovare la soluzione fattibile iniziale.
La soluzione fattibile iniziale è data dalla seguente matrice:
Test di ottimizzazione:
Dalla matrice precedente troviamo che:
(a) Numero di assegnazioni = m + n - 1 = 4 + 5-1 = 8
(b) Queste assegnazioni di m + n - 1 sono in posizioni indipendenti.
Pertanto è possibile eseguire il test di ottimalità. Questo è costituito dai passaggi secondari spiegati in precedenza, come mostrato nelle tabelle seguenti:
Poiché i valori delle celle sono + ve, la prima soluzione possibile è ottimale. Poiché la tabella 6 contiene voci zero, esistono soluzioni alternative alternative. Il significato pratico della domanda di 15 unità in meno rispetto alla fornitura è che la società può ridurre la produzione di 15 unità presso la fabbrica dove non è economicamente conveniente.
Il trasporto ottimale (minimo) più i costi di produzione.
Z = Rs. (4 x 25 + 6 x 5 + 8 x 20 + 10 x 70 + 4 x 30 + 13 x 15 + 8 x 20 + 0 x 15)
= Rs. (100 + 30 + 160 + 170 + 120 + 195 + 160 + 0) = Rs. 1.465.
Esempio 3:
Risolvi il seguente problema di trasporto per massimizzare il profitto. A causa della differenza nel costo delle materie prime e dei costi di trasporto, differisce l'utile per unità in rupie che è indicato nella tabella seguente:
Risolvi il problema per massimizzare il profitto.
Soluzione:
Il problema è sbilanciato e quindi è necessario aggiungere una fila fittizia per renderla equilibrata.
Trova soluzione iniziale di base fattibile:
Useremo il metodo di approssimazione di vogel per determinare la soluzione fattibile iniziale.
Nota che abbiamo a che fare con il problema della massimizzazione. Quindi inseriremo la differenza tra il più alto e il secondo elemento più alto in ciascuna riga a destra della riga e la differenza tra il più alto e il secondo elemento più alto in ogni colonna sotto la colonna corrispondente.
Ognuna di queste differenze rappresenta il profitto unitario perso per non allocare alla cella di profitto più alta. Quindi, mentre si effettuano assegnazioni, dapprima selezioniamo la cella (2, 3) con la voce più alta nella riga 2 che corrisponde alla differenza più alta di [45].
Test di ottimizzazione:
Numero richiesto di assegnazioni = m + n - 1 = 3 + 4 - 1 = 6
Numero effettivo di allocazione = 5.
Pertanto assegniamo un piccolo numero positivo € a cella (1, 3) (cella con il massimo profitto da celle vuote) in modo che il numero di allocazioni diventi 6. Queste 6 allocazioni sono in posizioni indipendenti. Pertanto è possibile eseguire il test di ottimalità.
Poiché tutti i valori delle celle sono negativi o pari a zero (problema di massimizzazione), la soluzione fattibile di base iniziale è ottimale. La richiesta alla prima destinazione è 'lasciata insoddisfatta da 5 unità. Il profitto è
Z max = Rs. [90 x 70 + 90 x 100 + 110 x 30 + 130 x 100 + 0 x 5]
= Rs. 31.600.
