[Ricerca Operativa] Metodo grafico PL e Simplesso

[MatematiNO]

Ciao a tutti! Necessito due chiarimenti:

Metodo grafico in due variabili - programmazione lineare e dualità

Dopo aver disegnato il grafico, l'esercizio mi dice di trovare il vertice ottimo. Se non ho capito male, il vertice ottimo corrisponde al valore massimo (o minimo) ricavato sostituendo i miei vertici nella funzione obiettivo.

Il problema è: min z =$x_1 + 4x_2$

subject to
$x_1 +2x_2 <= 6$
$2x_1 +x_2 <= 8$
$x_1 +2x_2 >=3$
$x_1, x_2  >= 0.$

1) Lui dice: Le basi corrispondono ai punti $A (x_2, x_3, x_4), B(x_2, x_4, x_5), C(x_1, x_2, x_5), D(x_1, x_3, x_5), E(x_1, x_3, x_4)$ Perché?? Come le ricavo??

2)Calcolando il vertice ottimo come detto sopra, a me risulta essere $ z(F) = 0$ con $F(x_1 = 6, x_2 = -3/2)$ mentre la soluzione del problema mi dice che è $E(x_1 = 3, x_2 = 0)$. Addirittura lui trova solo i vertici $A,B,C,D,E$ ... $F$ Non lo considera.

Cosa sbaglio??

Soluzioni ammissibili di base

Ho il programma in forma standard:

$max z = 8x_1+3x_2$

soggetto a:

$4x_1+5x_2+x_3=10$
$4x_1+10x_2+x_4=15$
$x_2+x_5=1$
$x_1,......,x_5>=0$

Non riesco a capire come calcolare le basi ammissibili, dalla teoria mi è sembrato di capire che per farlo devo:

1)Scrivere la matrice di base $A_B$
2)Scrivere la sua inversa $(A_B)^-1$
3)Scrivere $x_B = (A_B)^-1 * b$

Però se provo a calcolare per esempio ${A_2,A_3,A_4}$

[tex]A_B=\left(\begin{array}{ccccc}
5&1&0\\
10&0&1\\
1&0&0\\
\end{array}\right)[/tex]
il testo dice che la base ammissibile corrispondente è:
[tex]x_B=\left(\begin{array}{ccccc}
1\\
5\\
5\\
\end{array}\right)[/tex]

Ma eseguendo i calcoli a me risulta che:
[tex](A_B)^-1=\left(\begin{array}{ccccc}
0&1/9&-1/9\\
1&-5/9&5/9\\
0&-1/9&10/9\\
\end{array}\right)[/tex]

Che moltiplicata per b, che dovrebbe essere [tex]b=\left(\begin{array}{ccccc}
10\\
15\\
1\\
\end{array}\right)[/tex]

è uguale a un risultato completamente diverso da quello delle soluzioni del problema.
Cosa mi sono perso?!

[ZorroM]

Ciao, per il primo esercizio ti dice esplicitamente di disegnare il grafico, allora disegna il grafico (è semplice, sono rette!), otterrai lo spazio ammissibile che è un poliedro con 5 vertici (esattamente quelli che ti ha elencato il prof). A quel punto sostituisci i punti corrispondenti nella tua funzione obiettivo e il valore più basso sarà il valore ottimo del tuo problema. Non so come tu abbia trovato F, ma è evidente sia dal grafico, sia direttamente dai vincoli algebrici (il quinto vincolo, ovvero x2>0 non è rispettato) che il tuo punto F non è una soluzione ammissibile, e automaticamente non può essere una soluzione ottima (e dunque essendo la soluzione ottima sui vertici, non può essere un vertice del poliedro, anche perchè in tal caso sarebbe una soluzione ammissibile).


Per il secondo, ti escono valori diversi perchè tu calcoli la soluzione di base per il problema detto "primale", ma il tuo problema è scritto nella forma del duale della coppia asimmetrica. Dunque puoi fare in due modi: ti scrivi il primale, calcoli le varie soluzioni di base come hai detto tu, oppure risolvi direttamente sul duale con i tre calcoli che si fanno sulla forma del duale (cerca sul tuo libro o sugli appunti, cambia giusto qualcosina).
La differenza sostanziale è che calcolando algebricamente la soluzione del "primale" sulla forma "duale" non hai la certezza di ottenere basi ammissibili e dunque soluzioni di base ammissibili. Al contrario calcolando la soluzione "duale" sul tuo problema scritto in forma "duale" hai sicuramente una base ammissibile e una soluzione ammissibile di base (a eccezione del caso in cui il duale sia vuoto)

[SenIker96]

Ciao, allora come detto da ZorroM, devi disegnarti il grafico, disegnando delle semplici rette. Successivamente, nomina tutti i vertici del tuo poliedro. Per le coordinate di alcuni vertici, le vedrai ad occhio, per altri, dovrai calcolarti il vertice con i calcoli (devi vedere solo le intersezioni tra le rette interessate, mettendo a sistema i vincoli delle rette interessate). Una volta trovato tutti i vertici, sostituisci le coordinate di quel vertice, nella funzione obiettivo, e vedi quale ti esce superiore (se il tuo fosse un problema di max) o inferiore (se il tuo fosse un problema di minimo). Per trovare le basi ammissibili relative ai vertici, trasforma il problema in forma standard, sostituisci le coordinate dei vertici interessati, nel problema di forma standard (per capirci le basi del vertice A, andrai a sostituire nella forma standard le coordinate di A all'interno dei vincoli).