Limiti dimensionali del metodo del simplesso
Salve!
Ho iniziato da poco ad occuparmi del metodo del simplesso e non ho capito bene se esiste una relazione tra il numero di variabili ed il numero di vincoli necessari perchè il sistema converga. Mi spiego con un esempio: ho un problema con 10 variabili e 4 vincoli più una funzione obiettivo da minimizzare, è possibile incrementare il numero di incognite ( si pensi ad una discretizzazione più fine di un problema continuo) ma non aumentare il numero di vincoli e sperare che il sistema converga ancora? (si tenga presente che in quei 4 vincoli( e nella funzione obiettivo) compaiono comunque tutte le incognite) Mi chiedo quindi se c'è un limite al numero di incognite del problema fissato il numero di vincoli?
Grazie per l'attenzione
Ho iniziato da poco ad occuparmi del metodo del simplesso e non ho capito bene se esiste una relazione tra il numero di variabili ed il numero di vincoli necessari perchè il sistema converga. Mi spiego con un esempio: ho un problema con 10 variabili e 4 vincoli più una funzione obiettivo da minimizzare, è possibile incrementare il numero di incognite ( si pensi ad una discretizzazione più fine di un problema continuo) ma non aumentare il numero di vincoli e sperare che il sistema converga ancora? (si tenga presente che in quei 4 vincoli( e nella funzione obiettivo) compaiono comunque tutte le incognite) Mi chiedo quindi se c'è un limite al numero di incognite del problema fissato il numero di vincoli?
Grazie per l'attenzione
Risposte
Non ho capito esattamente cosa vuoi dire tuttavia rifletto:
- aumentare il numero di vincoli significa <> il simplesso. Se il metodo converge su un simplesso più grande ci si aspetta che converga su un simplesso più piccolo.
- aumentare il numero di variabili... a che fine? Dovrai necessariamente inserire qualcosa (vincoli) che le leghino al programma di partenza. Altrimenti sono mute nel problema e dunque non credo diano alcun fastidio, ossia in altre parole il problema si svolge in un sottospazio del nuovo spazio e quindi è totalmente equivalente a quello iniziale.
Ma molto probabilmente non ho capito io cosa vuolevi dire.
Più in generale la risposta a questa domanda:
"non ho capito bene se esiste una relazione tra il numero di variabili ed il numero di vincoli necessari perchè il sistema converga" si potrebbe evincere dalla forma del duale del problema.
Ovviamente tutto ciò sottintendendo che stessi parlando di algoritmo del simplesso per un PL.
- aumentare il numero di vincoli significa <
- aumentare il numero di variabili... a che fine? Dovrai necessariamente inserire qualcosa (vincoli) che le leghino al programma di partenza. Altrimenti sono mute nel problema e dunque non credo diano alcun fastidio, ossia in altre parole il problema si svolge in un sottospazio del nuovo spazio e quindi è totalmente equivalente a quello iniziale.
Ma molto probabilmente non ho capito io cosa vuolevi dire.
Più in generale la risposta a questa domanda:
"non ho capito bene se esiste una relazione tra il numero di variabili ed il numero di vincoli necessari perchè il sistema converga" si potrebbe evincere dalla forma del duale del problema.
Ovviamente tutto ciò sottintendendo che stessi parlando di algoritmo del simplesso per un PL.
Grazie a Megan00b per le osservazioni, mi scuso perchè effettivamente non sono stato molto chiaro.. allora provo a spiegarmi con un esempio: supponiamo di dover discretizzare il continuo, ad esempio dividendolo in elementi finiti, supponiamo che sia associata una variabile a ciascuno di questi elementi (non so una temperatura, uno spostamento ecc). Inizialmente scelgo 20 elementi discreti con 20 incognite, i vincoli sono 4 condizioni che riguardano tutte le variabili in gioco così come nella funzione obiettivo sono presenti tutte le 20 incognite. Uso il simplesso e trovo la soluzione.
Voglio aumentare il grado di precisione e aumento il numero di elementi discreti, ad esempio 50 . Avremo allora 50 incognite,ma i vincoli sono sempre 4. In questi ultimi e nella funzione obiettivo però stavolta compaiono tutte e 50 le incognite che non sono mute. Il problema è che aumentando ancora le incognite (ad es 200) i vincoli sono sempre 4 e capita che il simplesso non converga più.
Per questo mi chiedo se esista una relazione tra numero massimo di incognite e numero di vincoli.... del tipo: è possibile sapere a priori di quanto posso spingere la discretizzazione per avere una soluzione più precisa con quei 4 vincoli?
Voglio aumentare il grado di precisione e aumento il numero di elementi discreti, ad esempio 50 . Avremo allora 50 incognite,ma i vincoli sono sempre 4. In questi ultimi e nella funzione obiettivo però stavolta compaiono tutte e 50 le incognite che non sono mute. Il problema è che aumentando ancora le incognite (ad es 200) i vincoli sono sempre 4 e capita che il simplesso non converga più.
Per questo mi chiedo se esista una relazione tra numero massimo di incognite e numero di vincoli.... del tipo: è possibile sapere a priori di quanto posso spingere la discretizzazione per avere una soluzione più precisa con quei 4 vincoli?