Metodo del Simplesso

noipo
Ciao,
devo risolvere questo esercizio con il metodo del Simplesso ed ho qualche problema a fare ciò, vi scrivo cosa sono riuscita a fare e dove mi blocco:

[tex]max[/tex] [tex]3x_1 + 2x_2 - 5x_3[/tex]
soggetto a
[tex]4x_1 - 2x_2 + 2x_3 \le 4[/tex]
[tex]2x_1 + x_2 + x_3 \le 1[/tex]
[tex]x_1, x_2, x_3 \geq 0[/tex]

Trasformo il problema in forma standard aggiungendo le variabili slack [tex]x_4[/tex] e [tex]x_5[/tex]:
[tex]max[/tex] [tex]3x_1 + 2x_2 - 5x_3[/tex]
soggetto a
[tex]4x_1 - 2x_2 + 2x_3 + x_4 = 4[/tex]
[tex]2x_1 + x_2 + x_3 + x_5 = 1[/tex]
[tex]x_1, x_2, x_3, x_4, x_5 \geq 0[/tex]

Faccio la base [tex]B^0 = (x_4, x_5)[/tex] (scelgo questa base perchè sono le due variabili di slack o c'è un altro motivo?)
Faccio la matrice dei coeff dei vincoli

[tex]T(B^0) =[/tex] $((4,-2,2,1,0,|,4),(2,1,1,0,1,|,1))$

e ottengo il sistema:

{[tex]x_4 = 4 - 4x_1 + 2x_2 - 2x_3[/tex]
{[tex]x_5 = 1 - 2x_1 - x_2 - x_3[/tex]

[tex]z = 0 + 3x_1 + 2x_2 - 5x_3[/tex] (è fondamentale mettere lo 0?)

[tex]x_1, ..., x_5 \geq 0[/tex]

L'esame dei costi ridotti (cioè i coeff degli elementi di z, giusto?) indica che questa soluzione non è ottima poichè [tex]r_1, r_2 > 0[/tex]. (Questo passaggio non l'ho capito. Cosa indicano le r?)
Si sceglie [tex]x_1[/tex] come variabile entrante (per il criterio del massimo costo ridotto) nella prossima base. (Scelgo x_1 perchè guardando la funz obiettivo vedo che il massimo coeff positivo è quello di x_1, giusto? prendo il massimo perchè devo trovare il max della funzione? e se dovessi trovare il min prenderei il più piccolo positivo o cerco i negativi?)
Ora devo scegliere il pivot e prendo il 2 in seconda riga (Prendo lui perchè devo vedere qual'è il minimo rapporto tra il termine noto e il pivot, è corretto? il rapporto è minimo perchè la funz è max o non c'entra niente?)
e quindi la variabile uscente sarà [tex]x_5[/tex] (perchè è x_5?).

Ora so che devo scrivere un'altra matrice, un altro sistema ed un'altra z simili a quello precedenti ma come? qual'è il metodo da seguire? Quando mi fermo col metodo del Simplesso?
Qualcuno potrebbe scrivermi la fine dell'esercizio così posso capire bene tutti i passaggi?

Grazie mille...

Risposte
noipo
Le r sono i coefficienti della funzione obbiettivo e vado avanti col metodo del simplesso finchè:
- se ho una funz di massimo --> i coeff non sono tutti negativi
- se ho una funz di minimo --> i coeff non sono tutti positivi
giusto? ci sono altri casi?

La seconda matrice che devo scrivere la devo creare dalla prima in modo tale da avere in corrispondenza delle colonne dei termini in base una "matrice" identica..
quindi dovrà essere una cosa del tipo (essendo [tex]B^1 = (x_4, x_1)[/tex]):
[tex]T(B^1) =[/tex] $((0,...,...,1,...,|,...),(1,...,...,0,...,|,...))$

Ma non so come completarla..
Secondo me devo modificare la prima matrice attraverso le solite operazioni (invertire due righe/colonne, sommare a una riga un multiplo di un'altra ecc) fino a quando non arrivo a una matrice come sopra però non riesco..
Io scriverei (sicuramente sbagliata):
$((0,-4,0,1,-2,|,-2),(1,1/2,1/2,0,1/2,|,1/2))$

e poi non capisco come prendere le variabili, come sceglierle..

hamming_burst
"vfldj":
Le r sono i coefficienti della funzione obbiettivo e vado avanti col metodo del simplesso finchè:
- se ho una funz di massimo --> i coeff non sono tutti negativi
- se ho una funz di minimo --> i coeff non sono tutti positivi
giusto? ci sono altri casi?

Esatto, sono i fattori di terminazione per dire che l'algoritmo ha trovato la soluzione ottima (altri casi si trovano durante l'iterazione non li leggi nella funzione obbiettivo, ma mentre compi le operazioni tipo di pivoting).

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.