Il metodo del tableau non lo conosco, io faccio con vettori e matrici.
Spero di non aver sbagliato qualche conto:
Allora, come detto c'è bisogno della Fase1 perché nelle equazioni dei vincoli non è ricavabile la matrice identità (tra i coefficienti delle variabili), quindi si introducono le variabili alfa, ne servono 2.
codice:
min alfa1 + alfa2
x1 + 3x2 + x3 - x4 + alfa1 = 5
2x1 + 3x2 + x3 + alfa2 = 6
xi>=0 alfai>=0
Ora la matrice identità è ricavabile dalle alfa
Il problema sotto forma matriciale è
codice:
|alfa1| |x1|
min (1 1) | | + (0 0 0 0) |x2|
|alfa2| |x3|
|x4|
|alfa1| |1 3 1 -1| |x1| |5|
| | + | | |x2| = | |
|alfa2| |2 3 1 0| |x3| |6|
|x4|
Passami che queste sono matrici e vettori e non determinanti, le parentesi tonde non posso farle.
Do un nome ai vettori e matrici importanti in modo che sia più facile identificarle:
codice:
- dalla Funzione min -
il vettore dei coefficienti delle variabili in base
Cb(T) = (1 1)
il vettore dei coefficienti delle variabili fuori base
Cn(T) = (0 0 0 0) è sempre nullo alla prima iterazione della fase1
(T) = trasposto
userò anche in seguito la stessa notazione per identificare matrici e vettori trasposti
- dai vincoli -
la matrice dei coefficienti delle variabili fuori base
|1 3 1 -1|
| | = (B^-1)N
|2 3 1 0|
è questa alla prima iterazione solo perché si parte dalla matrice identità
come matrice dei coefficienti in base (le alfa)
Ora devo verificare il criterio di ottimalità, non so se tu fai allo stesso modo, ma io faccio con il vettore dei costi ridotti gamma(T)
codice:
gamma(T) = Cn(T) - Cb(T)(B^-1)N
|1 3 1 -1|
gamma(T) = (0 0 0 0) - (1 1)| | = - (3 6 2 -1) = (-3 -6 -2 1)
|2 3 1 0|
Il criterio di ottimalità non è soddisfatto, ci sono coefficienti negativi.
Il criterio di illimitatezza si può non verificare, durante la fase1 il problema, per costruzione, non può essere illimitato.
Ora si calcola il pivot.
h sarà l'indice della variabile entrante in base e k quello della variabile uscente.
h è la posizione del coefficiente minimo in assoluto, non in valore assoluto.
Il valore minimo è -6 che si trova in posizione 2, quindi h=2
k è la posizione del minimo dei coefficienti del vettore dei termini noti divisi per i rispettivi coefficienti della colonna che entrerà in base, ovvero, in questo caso, la 2.
codice:
min {5/3 , 6/3} = 5/3
dunque k=1
Entra in base x2 esce alfa1
I nuovi vettori sono
codice:
Cb(T) = (0 1)
il primo coefficiente è ora stato sostituito dal secondo di Cn(T) (il Cn(T) precedente)
Cn(T) = (0 1 0 0 0)
il secondo coefficiente è stato sostituito dal primo di Cb(T) (il Cb(T) precedente)
Ora bisogna calcolare la nuova (B^-1)N
codice:
|3 # 1 1 1 -1 # 5|
M = | # # |
|3 # 2 0 1 0 # 6|
questa è una matrice è formata da:
- prima colonna -> è la colonna che esce da (B^-1)N del passo precedente (in questo caso la seconda)
- matrice (B^-1)N del passo precedente al quale si è sostituita la colonna uscente con quella entrante
- ultima colonna -> i termini noti dei vincoli
i # sono solo per separare le varie parti della matrice
I passi da fare ora sono questi:
la prima colonna deve diventare la colonna della matrice identità corrispondente all'indice k, quindi (1 0)(T)
per fare questo come prima cosa si divide la prima riga in modo da far diventare il 3 un 1, quindi divido per 3
codice:
|1 # 1/3 1/3 1/3 -1/3 # 5/3|
M = | # # |
|3 # 2 0 1 0 # 6 |
ora il 3 della seconda riga deve diventare uno 0
per fare questo si applica la riduzione di Gauss
faccio seconda riga meno nuova prima riga moltiplicata per 3 (sembra stupido, ma è perché nella prima colonna c'erano numeri uguali)
codice:
|1 # 1/3 1/3 1/3 -1/3 # 5/3|
M = | # # |
|0 # 1 -1 0 1 # 1 |
La prima colonna non è più importante
il blocco centrale è la nuova (B^-1)N
l'ultima colonna è il nuovo valore dei termini noti
Bene, adesso abbiamo tutto per scrivere il problema che darà il via alla seconda iterazione della fase1
codice:
| x2 | | x1 |
min (0 1)| | + (0 1 0 0)|alfa1|
|alfa2| | x3 |
| x4 |
| x2 | |1/3 1/3 1/3 -1/3|| x1 | |5/3|
| | + | ||alfa1| = | |
|alfa2| | 1 -1 0 1 || x3 | | 1 |
| x4 |
xi>=0 alfai>=0
:
)
Rispondi quotando
