3 importanti strumenti di ricerca operativa

Questo articolo getta luce sui tre importanti strumenti della ricerca operativa. Gli strumenti sono: 1. Programmazione lineare 2. Problemi di trasporto 3. Problema di assegnazione.

Ricerca operativa: Tool # 1. Programmazione lineare:

La programmazione lineare è una tecnica matematica che ha applicazione a quasi tutte le classi di problemi decisionali. Questa tecnica viene applicata per scegliere come la migliore alternativa da una serie di alternative praticabili.

Nella funzione obiettivo LPP così come i vincoli possono essere espressi come funzione matematica lineare, che può essere utilizzata per risolvere i problemi di programmazione pratica. È un metodo utilizzato per studiare il comportamento dei sistemi.

LP si occupa principalmente di descrivere l'interrelazione dei componenti di un sistema. Questa tecnica è progettata per aiutare i manager a pianificare, prendere decisioni e allocare le risorse. La direzione ha sempre la tendenza a fare l'uso più efficace di una risorsa dell'organizzazione. Le risorse includono macchinari, materie prime, manodopera, magazzino, tempo e denaro.

Queste risorse possono essere utilizzate per produrre prodotti di vario tipo che possono essere macchine, parti / componenti, mobili e prodotti alimentari, ecc. Allo stesso modo, le risorse possono essere utilizzate per fornire servizi quali pianificazione per la spedizione, politiche pubblicitarie e decisioni di investimento.

Tutte le organizzazioni devono prendere decisioni sull'allocazione delle loro risorse limitate. Quindi le direzioni sono tenute a stanziare continuamente risorse scarse per raggiungere gli obiettivi / gli obiettivi / gli obiettivi dell'organizzazione.

L'aggettivo lineare è stato usato per descrivere una relazione tra due o più variabili. La programmazione riguarda l'uso di alcune equazioni matematiche utilizzate per ottenere la migliore soluzione possibile a un problema che coinvolge risorse limitate / scarse.

Pertanto, la programmazione lineare viene utilizzata per problemi di ottimizzazione che soddisfano la seguente condizione:

(i) La funzione obiettivo che deve essere ottimizzata dovrebbe essere ben definita ed espressa come una funzione lineare delle variabili.

(ii) La limitazione, se del caso, riguardo al raggiungimento di questi obiettivi è espressa anche come qualità / disuguaglianza lineare della variabile.

(iii) Sono disponibili anche alcune azioni alternative.

(iv) Le variabili decisionali sono interrelate e non negative.

(v) Le risorse sono limitate.

Applicazione della programmazione lineare ai problemi industriali:

(i) Sviluppare una programmazione per le industrie alimentari e per le raffinerie di petrolio, ecc.

(ii) Nelle industrie di lavorazione dei metalli viene utilizzato per il carico nei negozi e per determinare la scelta tra l'acquisto e la produzione di varie parti.

(iii) Viene utilizzato per valutare vari minerali di ferro nelle industrie siderurgiche.

(iv) Viene utilizzato per ridurre la quantità di perdite di finitura nelle cartiere.

(v) Viene utilizzato per trovare il routing ottimale dei messaggi nella rete di comunicazione.

Definizione della programmazione lineare:

La programmazione lineare è uno strumento / tecnica matematica per determinare il miglior utilizzo delle risorse di un'organizzazione. La programmazione lineare è progettata per aiutare i manager a pianificare e prendere decisioni. Come strumento decisionale, ha mostrato il suo valore in diverse aree come la produzione; finanza di marketing, ricerca e incarichi di personale.

Determinazione del mix ottimale del prodotto, assegnazione della macchina di selezione del portafoglio dei programmi di trasporto; posizione dell'impianto e allocazione del lavoro ecc. sono i pochi tipi di problemi che possono essere risolti con l'aiuto della programmazione lineare.

"L'analisi dei problemi in cui una funzione lineare di un numero di variabili deve essere massimizzata (o minimizzata) quando queste variabili sono soggette a un numero di restrizioni sotto forma di linearità nelle uguaglianze." Samuelson e Slow

Secondo Loomba, "la programmazione lineare è solo un aspetto di ciò che è stato definito un approccio sistemico alla gestione in cui in tutti i programmi sono progettati e valutati in termini dei loro effetti finali nella realizzazione degli obiettivi aziendali".

Problemi di programmazione lineare-Metodo grafico:

I passaggi del metodo grafico possono essere riassunti come segue:

1. Formulare il problema di programmazione lineare.

2. Tracciare le linee di vincolo date considerandole come equazioni.

3. Dal grafico sopra identificato la regione della soluzione ammissibile.

4. Individuare i punti di arrivo della regione della soluzione ammissibile.

5. Calcola il valore della funzione obiettivo sui punti d'arrivo.

6. Ora scegli il punto in cui la funzione obiettivo ha un valore ottimale.

Problemi di programmazione lineare-Soluzione matematica:

Sebbene il metodo grafico di risoluzione di LPP sia un valido aiuto per comprendere la sua struttura di base. Il metodo è di utilità limitata in caso di problemi industriali poiché il numero di variabili presenti è considerevole, quindi un'altra soluzione matematica chiamata come metodo simplex è idonea a risolvere LPP con un gran numero di variabili.

È una procedura iterativa che risolve l'LPP in un numero finito di passi o donatore e indica che esiste una soluzione illimitata a L.PR Il metodo Simplex è una procedura algebrica per risolvere problemi di programmazione lineare o è composto da una serie di passaggi ripetitivi per raggiungere una soluzione ottimale.

È un algoritmo di programmazione ampiamente utilizzato e generalmente utilizzato. In teoria questa procedura può risolvere qualsiasi problema costituito da un numero qualsiasi di variabili e vincoli. Se il problema è costituito da più di tre variabili e tre vincoli, è necessario l'uso del computer. La Fig. 31.9 mostra la rappresentazione schematica dell'algoritmo simplex.

Vari passaggi nella procedura Simplex:

I passaggi di questa procedura sono elencati di seguito:

1. Formulare il problema determinando la funzione e i vincoli oggettivi.

2. Converti le disuguaglianze in uguaglianze per ottenere la forma standard introducendo il surplus inutilizzato e le variabili artificiali nella funzione obiettivo.

3. Preparare la tabella simplex iniziale.

4. Calcolare il valore di z j (perdita netta per unità) e c j - z j (contributo netto) per questa soluzione.

5. Determinare la variabile in entrata (colonna chiave) selezionando la colonna con il più negativo

(z j - c j ).

6. Determina la variabile in partenza (riga chiave) calcolando la colonna del rapporto dalla regola 5 e scegliendo il valore non negativo più piccolo.

7. Calcola la riga sostitutiva della tabella simplex migliorata dalla regola 6.

8. Calcola le restanti righe della nuova tabella con la regola 7.

9. Calcola il valore cj e z j per questa soluzione.

10. Se è presente un valore non negativo (c j - z j ), tornare al punto 5.

11. Se non sono presenti valori non negativi (c j - z j ), è stata ottenuta la soluzione ottimale.

Esempio 1:

Un contadino ha 1000 acri di terra su cui può prendere il grano, il grano o la soia, ogni ettaro di mais costa Rs. 100 per la preparazione, richiede 7 giorni di lavoro e produce un profitto di Rs. 30 Un acro di grano costa Rs. 120 per preparare, richiedono 10 giorni uomo di lavoro e produrre un profitto di Rs. 40.

Un acro di soia costa Rs70 per preparare richiede 8 giorni di lavoro e produce un profitto di Rs. 20 Se l'agricoltore ha Rs. 100.000 per la preparazione e contare su 8000 giorni di lavoro. Quanti ettari dovrebbero essere assegnati a ogni coltura per massimizzare i profitti? (Gujarat MBA, 1989)

Soluzione:

Lasciare che x acro di terra venga assegnato per il mais

l'acro di terra viene assegnato per il grano

z acro di terra essere assegnato per la soia

Dal momento che ogni acro di terra per mais produce un profitto di Rs. 30, per le rese di grano Rs. 40 e per soia Rs. 20. La formulazione matematica del LLP è

Max Z = 30x + 40y + 20z + 0S 1, + OS 2, + 0S 3

Soggetto a

100 x + 120y + 70z ≤ 100000

7x + 10y + 8z ≤ 8000

x + y + z ≤ 1000

x, y, z ≥ 0

Cerchiamo di convertire le disuguaglianze in equazioni introducendo le variabili di gioco S 1, S 2 e S 3 . La funzione obiettivo e il vincolo possono essere scritti come

Nella colonna delle variabili di base i vettori sono per la variabile S 1, (1, 0, 0), S 2, (1, 0, 1) e S 3 (0, 0, 1) la soluzione fattibile iniziale è data dalle variabili S 1, S 2 e S 3 entrambi profitto totale = 0

Ora Zj e Cj - Zj, sono calcolati dalle regole 1, 2 e 3. La colonna chiave viene determinata con la colonna contrassegnata come inizia e la Tabella II semplice viene preparata come segue.

La tabella II non fornisce una soluzione ottimale. Procediamo ulteriormente per preparare la tabella III semplice e migliorare la soluzione come segue:

Problema di minimizzazione di Big M. Metodo:

Nell'industria può esserci un luogo in cui l'obiettivo può essere quello di minimizzare il costo di produzione o la durata della produzione, ovvero la funzione obiettivo deve essere minimizzata in tali casi possiamo procedere nello stesso modo di un problema di massimizzazione semplicemente moltiplicando per entrambi i lati della funzione obiettivo di-1 In tali situazioni la minimizzazione di Z sarà la massimizzazione di (-Z).

In tali casi, poiché le variabili in eccesso assumono un valore negativo che viola la restrizione della non negatività, per superare questa difficoltà introduciamo una nuova variabile come variabili artificiali.

Ora assegniamo 3000 coefficienti alle variabili in eccesso e + M alle variabili artificiali, Per rendere la fonte che le variabili artificiali non sono le variabili di base nella soluzione ottimale, assegniamo loro un costo molto elevato, quindi M è definito come un numero molto grande cioè Big M o penalità.

Questo metodo è illustrato con l'aiuto di quanto segue:

Esempio 2:

Ricerca operativa: strumento n. 2. Problemi di trasporto:

I problemi di trasporto sono uno dei tipi di LPP in cui l'obiettivo è quello di trasportare merci / prodotti in varie quantità di un singolo articolo / merce omogeneo verso destinazioni diverse in modo da ridurre al minimo i costi di trasporto nella vita quotidiana delle varie organizzazioni produttive o altri stabilimenti dovuti a varie considerazioni memorizzare i loro prodotti finali o articoli in vari luoghi definiti come origini o articoli, casa quando la fornitura deve essere effettuata agli utenti, quindi gli articoli sono trasportati da origini a una o più destinazioni lo scopo generale di questo processo è decidere una politica di distribuzione tale che il costo totale del trasporto sia minimo o il tempo consumato nel trasbordo sia minimo.

Dopo aver terminato nativamente i prodotti dall'impianto per essere trasportati nei magazzini in modo più economico in problemi di trasporto, si possono osservare varie caratteristiche della programmazione lineare, la disponibilità così come le esigenze dei vari centri sono limitate e costituiscono le risorse limitate problemi di trasporto casi particolari del metodo simplex.

Applicazione in valvole il trasporto di prodotti da più fonti a vari punti di destinazione come:

(i) Trasporto di unità distrutte destinazione. L'obiettivo è ridurre al minimo i costi di trasporto.

(ii) Massimizzare il profitto nel trasporto delle unità a destinazione.

I principali passaggi coinvolti sono :

Passo 1:

Formulare il problema e impostare sotto forma di matrice di trasporto.

Passo 2:

Ottenere la soluzione fattibile di base.

Passaggio 3:

Test per l'ottimalità della soluzione.

Passaggio 4:

Aggiornare la soluzione attraverso miglioramenti di successo fino a quando non è possibile ridurre ulteriormente i costi di trasporto.

I metodi comunemente usati sono:

1. Metodo dell'angolo nord-ovest.

2. Metodo del costo minimo.

3. Metodo di avvicinamento di Vogel.

Passaggi coinvolti nel metodo North West Corner:

Passo 1:

Costruisci una matrice massima vuota completata con righe e colonne.

Passo 2:

Indicare i totali delle righe e i totali delle colonne alla fine.

Passaggio 3:

A partire dalla cella (11) all'angolo nord-ovest della matrice è possibile allocare la quantità / numero massimo possibile tenendo conto che l'assegnazione non può essere superiore alla quantità richiesta dai rispettivi magazzini o superiore alla quantità disponibile presso i centri di fornitura.

Passaggio 4:

Dopo aver regolato i numeri della domanda e dell'offerta nelle rispettive allocazioni di righe e colonne, spostati in basso nella prima cella di e ripeti il ​​passaggio 3.

Passaggio 5:

Dopo che la richiesta della prima colonna è soddisfatta, passare alla cella successiva nella seconda colonna e nella prima riga e andare al passaggio 3.

Passaggio 6:

Se per qualsiasi fornitura di celle è uguale a richiesta, l'allocazione successiva può essere in modalità nelle celle nelle righe e nelle colonne successive.

Step 7:

Continuare il processo fino a quando la quantità totale disponibile è completamente assegnata alle celle secondo i requisiti

Esempio 3:

Risolvi il seguente problema con NWCM per calcolare il costo minimo di trasporto:

Passaggi nel metodo di iscrizione a costo minimo:

Questo metodo prende in considerazione il costo più basso e quindi richiede meno tempo per risolvere il problema. I vari passaggi sono i seguenti:

Passo 1:

Seleziona la cella con il costo di trasporto più basso tra tutte le righe e le colonne della matrice. Assegna il più possibile per eliminare quella riga o colonna che esaurisce la fonte o riempie il requisito. Se entrambi sono soddisfatti, elimina entrambi. Se la cella di costo più piccola non è univoca, seleziona arbitrariamente qualsiasi cella con il costo più basso.

Passo 2:

Ripeti la procedura per tutte le righe e le colonne non incrociate con la cella di costo successiva più piccola. Passaggio 3: ripetere la procedura fino a quando tutte le fonti sono esaurite o la domanda di tutte le destinazioni è piena.

Esempio 4:

Risolvi il seguente problema con il metodo meno costoso:

Metodo di avvicinamento Vogel:

Questo metodo è un metodo di penalità o rimpianto ed è preferito rispetto agli altri due metodi la soluzione iniziale di base ottenibile ottimale o molto vicina alla soluzione ottimale, quindi il tempo necessario per calcolare la soluzione ottimale è ridotto.

In questo metodo, la base di allocazione è la penalità del costo unitario, ovvero quella riga o colonna che indica la penalità del costo unitario più alto / la differenza tra il costo più basso e il costo più alto successivo viene selezionato per primo ai fini dell'assegnazione. In questo modo anche le successive allocazioni nelle altre celle vengono effettuate tenendo in considerazione la più alta penalità di costo unitario.

L'allocazione viene effettuata per minimizzare il costo delle penalità. I ​​vari passaggi coinvolti sono i seguenti:

Passo 1:

Calcola la penalità per ogni riga e colonna effettuata facendo semplicemente la differenza tra il costo di trasporto più piccolo e il più piccolo successivo nella stessa riga e colonna, ovvero la differenza indica la penalità da pagare se l'allocazione non viene effettuata al costo minimo criterio.

Passo 2:

Seleziona una riga o una colonna con la penalità maggiore e assegna il più possibile alla cella meno costosa. In caso di parità, viene scelta prima una cella di massima allocazione possibile

Passaggio 3:

Cancellare la riga o la colonna dopo aver soddisfatto la domanda o esaurire la fornitura la riga o la colonna rimanenti viene assegnata a una fornitura oa una domanda pari a zero. Qualsiasi riga o colonna con fornitura o richiesta pari a zero non può essere utilizzata per ulteriori calcoli.

Passaggi 4:

Ripeti i passaggi 1 e 3 finché tutte le fonti sono esaurite o tutti i requisiti sono soddisfatti.

Esempio 5:

Una manifattura vuole spedire 8 carichi del suo prodotto dai centri di produzione X, Y e Z ai centri di distribuzione A, B e C la matrice dall'origine 0 alla destinazione D è la seguente matrice.

Esempio 6:

Trova la soluzione ottimale del seguente problema di trasporto ottenendo la soluzione iniziale con il metodo di approssimazione dei vogets:

Soluzione:

Applichiamo il metodo di approssimazione di vogel. Problemi bilanciati come offerta = domanda = 50 unità. Applichiamo il metodo di vogel come indicato nella tabella seguente.

Costi di trasporto = 2 x 15 + 9 x 15 + 20 x 10 + 4 x 5 + 18 x 5 x 475 unità.

Verifica in modo ottimale:

Il test dell'ottimalità può essere eseguito se sono soddisfatte due condizioni, ad es

1. Ci sono m + n - 1 allocazione, il cui m è il numero di righe, n è il numero di colonne. Qui m + n - = 6. Ma il numero di allocazione è cinque.

2. Queste allocazioni m + n-1 dovrebbero essere a posizioni indipendenti, ovvero 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 assegnazioni di essere in posizioni indipendenti è che è impossibile viaggiare da qualsiasi allocazione, a sua volta una serie di passaggi orizzontali e verticali formano 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 nella Tabella 2.

Ora il numero di allocazioni è m + n - 6 = 6 e sono in posizioni indipendenti. Annotare la matrice dei costi nelle celle allocate. (Tabella 3)

Matrice costi iniziali per celle allocate. Scrivi anche i valori di u i e v j .

Dalla tabella 5 si può vedere che la valutazione delle cellule nella cellula (1, 4) è negativa, cioè -4, pertanto 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ò notare 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. Nuovo la tabella di assegnazione diventerà

Costi di trasporto = 5X 2 + 10X 1 1 + 10X 7 + 15X 9 + 5X 4 + 18 + 5 = 435 unità.

Ad esempio, il costo del trasporto è sceso da 475 unità a 435 unità.

Verifica in modo ottimale:

Vediamo se questa soluzione è ottimale o no? Per questo ancora due condizioni devono essere controllate cioè

Numero di allocazione = m + n- 1 = 6 (soddisfatto)

Assegnazione in posizione indipendente (soddisfatta dal momento che il circuito chiuso per le celle allocate non è formato) Scrive il costo ai valori allocati di tutti i valori di i e v j .

Ricerca operativa: strumento n. 3. Problema di 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 il problema possa essere risolto 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.

Modello di assegnazione:

Supponiamo che ci siano n facilitazioni e n lavori. È chiaro che in questo caso, ci saranno n incarichi. Ogni struttura o dire lavoratore può eseguire ogni lavoro, uno alla volta. Ma dovrebbe esserci una certa procedura con la quale si dovrebbe eseguire l'incarico in modo che il profitto sia massimizzato o il costo o i tempi siano ridotti al minimo.

Nella tabella, Coij è definito come il costo quando il lavoro viene assegnato al lavoratore. Si può notare qui che questo è un caso particolare 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 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 X ij sia una variabile definita come

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 ciascun 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) prende 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, le assegnazioni sono fatte 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) Le fasi 3 (i) e 3 (ii) sono ripetute 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, disegnare il numero minimo di linee (orizzontali e verticali) necessarie per coprire tutti gli zeri nella matrice ottenuta nel passaggio 3.

La seguente procedura è adottata:

(i) Segno di spunta (V) tutte le righe che non hanno alcun incarico.

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

(iii) Ora il segno di spunta contrassegna tutte le righe che non sono già marcate e che hanno assegnazioni nelle colonne contrassegnate.

(iv) Tutti i passaggi, ad esempio 4 (1), 4 (2), 4 (3) vengono ripetuti fino a quando non è possibile contrassegnare più righe o colonne,

(v) Ora disegnare linee rette che attraversano tutte le righe non contrassegnate e le 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.