Ricerca di una soluzione di base ammissibile
Ovviamente si parla di Ricerca Operativa...
Ipotizziamo di avere un problema di programmazione lineare con funzione obiettivo a massimizzare avente tutti coefficienti di costo positivi. Supponiamo che i vincoli del problema siano in parte di tipo $<=$ e in parte di tipo $>=$ (ed esista almeno un vincolo di tipo $>=$ con termine noto diverso da $0$).
In tali ipotesi, il vertice origine non è soluzione di base ammissibile del problema, sicché non si ha a disposizione un punto di innesco per l'algoritmo del simplesso nella sua forma standard. Procedura comune in tali casi è l'introduzione della cosiddetta "funzione di inammissibilità" e delle variabili artificiali... si risolve il problema tentando di minimizzare la funzione di inammissibilità, in modo da ottenere una soluzione di base ammissibile da cui partire per la risoluzione del problema originario.
Mi chiedevo se fosse possibile operare diversamente, nella speranza di velocizzare la procedura. Cercherò di spiegare brevemente come ho ragionato...
Nelle stesse ipotesi iniziali, consideriamo la funzione obiettivo come se fosse a minimizzare (non cambia nulla nel dominio di ammissibilità del resto). Trasformiamo inoltre i vincoli del tipo $>=$ in vincoli del tipo $<=$ cambiando segno ad ambo i membri delle relazioni. A questo punto l'origine non è soluzione di base ammissibile del problema diretto (in quanto c'è almeno un termine noto negativo), tuttavia rispetta l'ammissibilità del duale ed è possibile partire da essa per condurre i passi dell'algoritmo del simplesso duale (quello di C.E. Lemke, per capirci) che procede per soluzioni di base che non rispettano l'ammissibilità del diretto ma rispettano quella del duale. Al termine della procedura si sarà trovato il minimo della funzione obiettivo... è vero dunque che il problema iniziale non sarà risolto (in quanto si vuole cercare il massimo), tuttavia si ha a disposizione una soluzione di base ammissibile per il diretto da cui innescare il simplesso standard per la ricerca del massimo. Questo tipo di procedura mi sembrava conveniente, in quanto consente di evitare l'introduzione delle variabili artificiali.
Può essere conveniente procedere secondo la via che ho esposto?
Attendo commenti.
Ipotizziamo di avere un problema di programmazione lineare con funzione obiettivo a massimizzare avente tutti coefficienti di costo positivi. Supponiamo che i vincoli del problema siano in parte di tipo $<=$ e in parte di tipo $>=$ (ed esista almeno un vincolo di tipo $>=$ con termine noto diverso da $0$).
In tali ipotesi, il vertice origine non è soluzione di base ammissibile del problema, sicché non si ha a disposizione un punto di innesco per l'algoritmo del simplesso nella sua forma standard. Procedura comune in tali casi è l'introduzione della cosiddetta "funzione di inammissibilità" e delle variabili artificiali... si risolve il problema tentando di minimizzare la funzione di inammissibilità, in modo da ottenere una soluzione di base ammissibile da cui partire per la risoluzione del problema originario.
Mi chiedevo se fosse possibile operare diversamente, nella speranza di velocizzare la procedura. Cercherò di spiegare brevemente come ho ragionato...
Nelle stesse ipotesi iniziali, consideriamo la funzione obiettivo come se fosse a minimizzare (non cambia nulla nel dominio di ammissibilità del resto). Trasformiamo inoltre i vincoli del tipo $>=$ in vincoli del tipo $<=$ cambiando segno ad ambo i membri delle relazioni. A questo punto l'origine non è soluzione di base ammissibile del problema diretto (in quanto c'è almeno un termine noto negativo), tuttavia rispetta l'ammissibilità del duale ed è possibile partire da essa per condurre i passi dell'algoritmo del simplesso duale (quello di C.E. Lemke, per capirci) che procede per soluzioni di base che non rispettano l'ammissibilità del diretto ma rispettano quella del duale. Al termine della procedura si sarà trovato il minimo della funzione obiettivo... è vero dunque che il problema iniziale non sarà risolto (in quanto si vuole cercare il massimo), tuttavia si ha a disposizione una soluzione di base ammissibile per il diretto da cui innescare il simplesso standard per la ricerca del massimo. Questo tipo di procedura mi sembrava conveniente, in quanto consente di evitare l'introduzione delle variabili artificiali.
Può essere conveniente procedere secondo la via che ho esposto?
Attendo commenti.
Risposte
Rispondo a nome dell'utente FrancoTopo, che è appollaiato alle mie spalle e mi sta suggerendo la risposta.
Sì, va benissimo il sig. Lemke. Proprio per il fatto che hai i coefficienti di costo tutti positivi.
Si possono usare altri approcci di tipo "euristico" (tradotto in italiano comune: alla "sperindio"), ma Lemke è ok
Sì, va benissimo il sig. Lemke. Proprio per il fatto che hai i coefficienti di costo tutti positivi.
Si possono usare altri approcci di tipo "euristico" (tradotto in italiano comune: alla "sperindio"), ma Lemke è ok
Vi ringrazio molto per l'attenzione!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo