Precisazioni e appunti vari per i PL
Salve,
Nello studio di un problema di Programmazione Lineare , spesso si chiede di analizzare alcuni punti dati e di effettuare specifiche richieste. A tal proposito volevo conferma sui seguenti punti, ringraziandovi anticipatamente
Per esempio, sia dato il seguente problema di PL:
\(\displaystyle min Z(x)= 18x1 +4x2 -6x3 +2x4 \)
con i seguenti vincoli:
\(\displaystyle 2x1 -x3 -x4 = -1 \)
\(\displaystyle 3x1 +x2 -4x3 >=0 \)
\(\displaystyle x1,x2,x3,x4>=0 \)
e siano dati i punti:
\(\displaystyle xa=(1/2,0,0,2)^T \)
\(\displaystyle xb=(0,4,1,0)^T \)
Per verificare l'ammissibilità dovrei sostituire i punti nei vincoli e vedere se soddisfa le relazioni, il mio dubbio era se questa verifica bisogna effettuarla nel problema in forma standard ?
Duqnue,
porto P in Forma Standard: (moltiplico poi per -1 il primo vincolo)
\(\displaystyle min Z(x)= 18x1 +4x2 -6x3 +2x4 \)
\(\displaystyle -2x1 +x3 +x4 = +1 \)
\(\displaystyle 3x1 +x2 -4x3 -x5 =0 \)
\(\displaystyle x1,x2,x3,x4,x5>=0 \)
sostutuisco i punti xa e xb nei vincoli per ricavarne poi le seguenti forme standard:
\(\displaystyle XAfs=(1/2,0,0,2,3/2) \) che avendo 3 componenti non nulle ed essendo m=2 il numero di vincoli risulta NON ammissibile
\(\displaystyle XBfs=(0,4,1,0,0) \) risulta invece ammissibile in quanto soddisfa le uguaglianze dei vincoli, ha al più due componenti non nulle e le colonne in corrispondenza delle componenti non nulle sono linearmente indipendenti
...spero fin qua sia giusto....
nel caso trovo che qualche punto sia ammissibile, proseguo nel verificare se è soluzione ammissibile di base verificando che le componenti non nulle siano linearmente indipendenti e deve avere al più m variabili diverse da 0 (con m= numero di vincoili)
per verificare infine l'ottimalità di tale punto calcolo i coefficienti di costo ridotto mediante formula \(\displaystyle Cn-CbAb^-1An \)
altro mio forte dubbio è il perchè si ricorre al metodo delle due fasi se è già evidente una base di partenza?
(la base individuata con cui inizializzare il simplesso non potrebbe essere individuata dalla colonna 2 e colonna 4 del problema in forma standard?)
aspetto e spero nelle vostre risposte
Nello studio di un problema di Programmazione Lineare , spesso si chiede di analizzare alcuni punti dati e di effettuare specifiche richieste. A tal proposito volevo conferma sui seguenti punti, ringraziandovi anticipatamente
Per esempio, sia dato il seguente problema di PL:
\(\displaystyle min Z(x)= 18x1 +4x2 -6x3 +2x4 \)
con i seguenti vincoli:
\(\displaystyle 2x1 -x3 -x4 = -1 \)
\(\displaystyle 3x1 +x2 -4x3 >=0 \)
\(\displaystyle x1,x2,x3,x4>=0 \)
e siano dati i punti:
\(\displaystyle xa=(1/2,0,0,2)^T \)
\(\displaystyle xb=(0,4,1,0)^T \)
Per verificare l'ammissibilità dovrei sostituire i punti nei vincoli e vedere se soddisfa le relazioni, il mio dubbio era se questa verifica bisogna effettuarla nel problema in forma standard ?Duqnue,
porto P in Forma Standard: (moltiplico poi per -1 il primo vincolo)
\(\displaystyle min Z(x)= 18x1 +4x2 -6x3 +2x4 \)
\(\displaystyle -2x1 +x3 +x4 = +1 \)
\(\displaystyle 3x1 +x2 -4x3 -x5 =0 \)
\(\displaystyle x1,x2,x3,x4,x5>=0 \)
sostutuisco i punti xa e xb nei vincoli per ricavarne poi le seguenti forme standard:
\(\displaystyle XAfs=(1/2,0,0,2,3/2) \) che avendo 3 componenti non nulle ed essendo m=2 il numero di vincoli risulta NON ammissibile
\(\displaystyle XBfs=(0,4,1,0,0) \) risulta invece ammissibile in quanto soddisfa le uguaglianze dei vincoli, ha al più due componenti non nulle e le colonne in corrispondenza delle componenti non nulle sono linearmente indipendenti
...spero fin qua sia giusto....
nel caso trovo che qualche punto sia ammissibile, proseguo nel verificare se è soluzione ammissibile di base verificando che le componenti non nulle siano linearmente indipendenti e deve avere al più m variabili diverse da 0 (con m= numero di vincoili) per verificare infine l'ottimalità di tale punto calcolo i coefficienti di costo ridotto mediante formula \(\displaystyle Cn-CbAb^-1An \) altro mio forte dubbio è il perchè si ricorre al metodo delle due fasi se è già evidente una base di partenza?(la base individuata con cui inizializzare il simplesso non potrebbe essere individuata dalla colonna 2 e colonna 4 del problema in forma standard?)
aspetto e spero nelle vostre risposte
Risposte
Nessuno può aiutarmi? 
Dato che nessuno ti ha risposto ci provo io. Anche se il simplesso l'ho studiato almeno un anno fa e poi non l'ho più usato, quindi non è proprio fresco nella mia memoria!
Puoi verificare che la soluzione è ammissibile anche nella forma iniziale, senza portarlo in forma standard. Il fatto è che per applicare il simplesso devi avere un punto che si trovi sulla poligonale, ovvero deve verificare tutte le uguaglianze della forma standard. Quindi, se vuoi vedere semplicemente se una sol. è ammissibile basta verificare i vincoli, per vedere se è una soluzione buona per applicare il simplesso devi prima avere il problema nella forma standard.
Spero che la memoria non mi stia ingannando...
Puoi verificare che la soluzione è ammissibile anche nella forma iniziale, senza portarlo in forma standard. Il fatto è che per applicare il simplesso devi avere un punto che si trovi sulla poligonale, ovvero deve verificare tutte le uguaglianze della forma standard. Quindi, se vuoi vedere semplicemente se una sol. è ammissibile basta verificare i vincoli, per vedere se è una soluzione buona per applicare il simplesso devi prima avere il problema nella forma standard.
Spero che la memoria non mi stia ingannando...
Ti ringrazio infinitamente per la tua risposta...quello che dici tu mi è chiaro, non capisco però perchè si applica le due fasi se cmq una base di partenza già c'è, non mi è chiaro quando dici che si deve trovare sulla poligonale, solitamente nel tableau in questo caso la base sarebbe y1=(1,0) e y2=(0,1) ma questa base che noi creamo con la seconda fase , e quindi con il problema artificiale, nella forma standard del problema originale non è forse data dalle variabili x4 e x2?
Ho riguardato al volo il simplesso. Semplicemente tu, se non hai una soluzione di base con le tue variabili originarie in base, devi fare in modo che ci entrino. Di conseguenza, per prima cosa, aggiungi le variabili nuove (di slack o di surplus). Dato che le inserisci tu e nella f.o obiettivo non hanno peso le metti in base. Dato che sono variabili "inventate" le devi fare uscire di base e fare entrare le variabili originarie. Una volta fatte uscire le variabili di slack o surplus hai una soluzione di base ammissbile per il tuo problema originario. A questo punto hai la soluzione di base per applicare il simplesso al problema dato e non a quello "ampliato" con le variabili che hai inserito.
Non sono sicuro di essermi spiegato.
Il succo è che se hai già una base buona (con le variabili di slack e surplus fuori base) allora hai risolto. Altrimenti consideri in base le variabili che hai aggiunto e cerchi di "buttarle fuori" facendo entrare le tue variabili originarie.
Nel caso che hai postato, se non ho sbagliato i conti, applicando l'eliminazione di gauss ottieni che $x_2$ e $x_3$ sono in base. In questo caso hai già una soluzione di base ammissibile per applicare il simplesso ed infatti la soluzione $x=[0,1,1,0]^T$ verifica all'uguaglianza i due vincoli e rispetta il vincolo $x_i in RR^+ AAi$ ovvero si trova sulla poligonale descritta dai vincoli dati. Questo vuol dire che il punto è un punto buono per applicare il simplesso.
Non sono sicuro di essermi spiegato.
Il succo è che se hai già una base buona (con le variabili di slack e surplus fuori base) allora hai risolto. Altrimenti consideri in base le variabili che hai aggiunto e cerchi di "buttarle fuori" facendo entrare le tue variabili originarie.
Nel caso che hai postato, se non ho sbagliato i conti, applicando l'eliminazione di gauss ottieni che $x_2$ e $x_3$ sono in base. In questo caso hai già una soluzione di base ammissibile per applicare il simplesso ed infatti la soluzione $x=[0,1,1,0]^T$ verifica all'uguaglianza i due vincoli e rispetta il vincolo $x_i in RR^+ AAi$ ovvero si trova sulla poligonale descritta dai vincoli dati. Questo vuol dire che il punto è un punto buono per applicare il simplesso.
Ciao , e grazia ancora per la tua risposta.
é tuto chiaro quello che hai scritto eccetto il punto di base x2 e x3, queste variabili non dovrebbero costituire una base...altro dubbio è che quando quando applichiamo una sola variabile di surpluss (x5 al secondo vincolo)= questa insieme a x2 non costituisce una base da cui inizializzare il simplesso? evitando di ricorrere al problema artificiale per il metodo a due fasi per l'appunto...
é tuto chiaro quello che hai scritto eccetto il punto di base x2 e x3, queste variabili non dovrebbero costituire una base...altro dubbio è che quando quando applichiamo una sola variabile di surpluss (x5 al secondo vincolo)= questa insieme a x2 non costituisce una base da cui inizializzare il simplesso? evitando di ricorrere al problema artificiale per il metodo a due fasi per l'appunto...
Ho scritto male il vettore in base era $x=[0,4,1,0]$. Avevo fatto i conti giusti però poi quando sono andato a scrivere mi è venuto di ragionare in binario come l'ultimo corso che ho fatto su questi argomenti...in pratica nella mia mente avevo scritto $x_2$ si e $x_3$si. Una distrazione... 
Sono una base solo per iniziare il simplesso del problema ampliato. Per trovare una soluzione che ti vada bene e che ti minimizzi o massimizzi la f.o. data devi sempre fare uscire dalla base le variabili di slack e surplus. Quindi finche $x_5$ è in base non hai una base del problema iniziale. Questo lo vedi dal fatto che non considerando $x_5$ (dato cha questo fa parte solo del problema ampliato) non soddisfi i vincoli all'uguaglianza ovvero non ti trovi sulla poligonale data dalla regione ammissibile del problema iniziale. Invece sei sulla poligonale della regione ammissibile del problema ampliato (hai una dimensione in più prima eri in $RR^4$ ora sei in $RR^5$).
Spero di essermi fatto capire...non avendo freschi questi argomeni l'esposizione ne risente...
"Luca.mat":
altro dubbio è che quando quando applichiamo una sola variabile di surpluss (x5 al secondo vincolo)= questa insieme a x2 non costituisce una base da cui inizializzare il simplesso? evitando di ricorrere al problema artificiale per il metodo a due fasi per l'appunto...
Sono una base solo per iniziare il simplesso del problema ampliato. Per trovare una soluzione che ti vada bene e che ti minimizzi o massimizzi la f.o. data devi sempre fare uscire dalla base le variabili di slack e surplus. Quindi finche $x_5$ è in base non hai una base del problema iniziale. Questo lo vedi dal fatto che non considerando $x_5$ (dato cha questo fa parte solo del problema ampliato) non soddisfi i vincoli all'uguaglianza ovvero non ti trovi sulla poligonale data dalla regione ammissibile del problema iniziale. Invece sei sulla poligonale della regione ammissibile del problema ampliato (hai una dimensione in più prima eri in $RR^4$ ora sei in $RR^5$).
Spero di essermi fatto capire...non avendo freschi questi argomeni l'esposizione ne risente...
ah...quindi se utilizziamo variabili di slack o di surplus siamo comunque costretti ad usare le due fasi, questo mi sfuggiva, se invece i vincoli erano posti all'uguaglianza, allora non c'era bisogno delle due fasi. grazie mille per il chiarimento
"Luca.mat":
ah...quindi se utilizziamo variabili di slack o di surplus siamo comunque costretti ad usare le due fasi, questo mi sfuggiva, se invece i vincoli erano posti all'uguaglianza, allora non c'era bisogno delle due fasi. grazie mille per il chiarimento
Il problema lo hai solo se le variabili di slack e surplus sono in base. Se tu avessi introdotto tali variabili ma la soluzione all'uguaglianza l'avessi trovata con quelle variabili fuori dalla base allora non sarebbe necessario fare niente. Applicheresti solamente la seconda fase. Il che è logico dato che la prima fase consiste nel mettere le variabili di slack per poi forzarle all'uscita.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo