Forma canonica, problema ausiliario e simplesso

[FELPONE]

Salve,
qualcuno potrebbe chiarire i miei enormi dubbi??

problema)
$ max cx$
$ Ax=b$
$ x \geq 0 $

problema ausiliario)

$min sum_(i = 1)^( n) Zi $
$Ax+Iz=b$
$x,z \geq 0$

nella pratica,quando dovrei utilizzare questa funzione ausiliaria?
se ho capito bene devo aggiungere ad ogni riga una variabile Z giusto?

posto un esempio dove però non aggiunge la Z a tutte le righe,e lascia il problema ausiliario in fomra di minimo senza portarlo in forma di massimo.perchè?


$min – x1 + 3x2 + 4x3 – 2x4$
$5x1 + x2 + 2x4 = 15$
$x1 + 3x3 + x4 = 20$
$5x1 + 8x2 = 40$
$x1, x2, x3, x4 > 0$

Per trovare una soluzione ammissibile scriviamo il problema ausiliario:

$min z1 + z2$
$5x1 + x2 + 2x4 + z1 = 15$
$x1 + 3x3 + x4 = 20$
$5x1 + 8x2 + z2 = 40$
$x1, x2, x3, x4, z1, z2 > 0$

[Sk_Anonymous]

nella pratica si usano quando hai bisogno di trasformare una disuguaglianza in un'uguaglianza, come ad esempio se hai a che fare con una iterazione per il calcolo di soluzioni ammissibili

[Fioravante Patrone1]

No, non si tratta di variabili di slack/surplus. Nè riguarda le iterazioni.

E' il "metodo a due fasi", che si usa per trovare una soluzione ammissibile di base da cui far partire il metodo del simplesso.
Lo si trova descritto su "ogni" testo di PL.
Un breve cenno è qui:
http://www.diptem.unige.it/patrone/RO_I ... 009_10.pdf
pag. 16

[FELPONE]

Confermo quanto dice Fioravante. é un metodo che consiste di trovare una forma canonica minimizzando le "z" e da cui far partire il simplesso.

[Fioravante Patrone1]

Nell'esempio che presenti, penso sia una semplice svista non aver messo la "z" nella seconda riga.

Sul fatto di conversione min/max, non mi è chiaro cosa intendi. Presumo che tu ti ponga la domanda per il problema originario, non per quello ausiliaro. Se ho inteso bene, tieni presente che il problema ausiliario si pone di vedere se per i vincoli del problema originario ci sono soluzioni ammissibili di base: la funzione obiettivo del problema originario è irrilevante (non solo che si massimizzi o si minimizzi, ma proprio non ci interessa chi sia).

[hamming_burst]

non è che con "problema ausiliario" e conversione max con min si intenda scrivere il problema duale?

[Fioravante Patrone1]

"ham_burst":non è che con "problema ausiliario" e conversione max con min si intenda scrivere il problema duale?

Risposta chiara: no.
E' tutta un'altra cosa, come ha già detto FELPONE stesso.
Faccio notare anche a te che nel problema ausiliario la funzione obiettivo del problema dato sparisce. Non che si trasformi in altro, proprio se ne va, evapora. Quindi niente a che fare con il problema duale.

[hamming_burst]

"Fioravante Patrone":[quote="ham_burst"]non è che con "problema ausiliario" e conversione max con min si intenda scrivere il problema duale?

Risposta chiara: no.
E' tutta un'altra cosa, come ha già detto FELPONE stesso.
Faccio notare anche a te che nel problema ausiliario la funzione obiettivo del problema dato sparisce. Non che si trasformi in altro, proprio se ne va, evapora. Quindi niente a che fare con il problema duale.[/quote]

perfetto, grazie della risposta. Era un dubbio da chiarire