Piani di taglio di Gomory

[Zephyro1]

Si consideri il seguente problema di programmazione lineare intera:

$\{(min 6x_1 + 6x_2), (13x_1 + 11x_2 >= 66), (13x_1 + 6x_2 >= 43), (x_1>=0), (x_2>=0):}$

a) Calcolare una valutazione inferiore risolvendo il rilassamento continuo.

Soluzione ottima del rilassamento continuo = $(66/13, 0)$
$v_I(P)$=31

b) Calcolare una valutazione superiore del valore ottimo arrotondando la soluzione ottima del rilassamento.

sol. ammissibile = (6,0)
$v_s(P)=36$

E fin qui ci sono.. non riesco però a risolvere il punto c.

c) Calcolare un taglio di Gomory:

Io l'ho risolto così:

$\{(min -6x_1-6x_2), (13x_1 + 11x_2 + x_3=66), (18x_1 + 6x_2 + x_4=43):}$

dove $x_3$ e $x_4$ sono le variabili di scarto che ho ricavato ottenendo
$x_3=0$
$x_4=-629/13$

dunque $x=(66/13, 0, 0, -629/13)$

prendo come base quella costituita dagli indici 1,4 perchè è quella che ha generato la sol. ottima del rilassamento.
Scrivo la matrice di base
$A_B=((13, 0),(18, 1))$

e la matrice non di base
$A_N=((11,1),(6,0))$

Inverto la matrice di base
$A_B^-1=((1/13, -18/13),(0,1))$

Calcolo la matrice
$B=A_B^-1 * A_N=((-97/13, 1/13),(6,0))$

prendo r=1 l'indice della prima componente di x non intera e trovo la disuguaglianza di taglio:

$\sum_{j in N} {b_{r,j}}x_j >= {x_r}

(Con le parentesi graffe indico la parte frazionaria di quello che è al loro interno)

e mi è venuto $7/13 x_2 + 1/13 x_3 >= 1/13$

ricavo $x_3=66 - 13x_1 - 11x_2$ e lo sostituisco nella diseguaglianza che ho trovato in precedenza e dovrebbe venire

$13x_1 + 4x_2<=65$

La soluzione invece mi dà:
$r=1$ -> $12x_1 + 11x_2>=61$

$r=4$ -> $8x_1 + 7x_2>41$

Potete dirmi dove sbaglio? Grazie!!

[edge1]

Ricerca Operativa col Pappalardo?

Pensa che direbbe il Longo se vedesse come hai invertito $A_b$

[Zephyro1]

E' vero, ho sbagliato l'inversa che dovrebbe allora essere $((1/13, 0), (-18/13, 1))$ ma lo stesso non mi torna il piano di taglio.. l'algoritmo è corretto?

[edge1]

L'algoritmo è giusto però...
Essendo questo un problema di minimo,quando vai ad inserire le variabili di scarto devi aggiungere $-x_3$ e $-x_4$ ,a quel punto il resto mutatis mutandis va bene.
Se risvolgi i calcoli il risultato torna corretto con quello del Pappa.
In bocca al lupo per Lunedì.

Ma non è che sai sulla parte PLI cosa chiede,devo fare l'orale settimana prox ma non so cosa vuole,devo solo integrare quella parte.

[Zephyro1]

Ora mi torna perfettamente, grazie mille
Per quanto riguarda la PLI forse può chiedere i modelli matematici del TSP, il rilassamento continuo e Lagrangiano e il teorema di equivalenza tra un problema di PLI e uno di PL (ma non sono sicuro, è quello che ho sugli appunti riguardante la PLI).
In bocca al lupo anche a te per l'orale