Piani di taglio di Gomory

[Zephyro]

Si consideri il seguente problema di programmazione lineare intera:

\( \displaystyle {\left\lbrace\matrix{\min{6}{x}_{{1}}+{6}{x}_{{2}}\\{13}{x}_{{1}}+{11}{x}_{{2}}\ge{66}\\{13}{x}_{{1}}+{6}{x}_{{2}}\ge{43}\\{x}_{{1}}\ge{0}\\{x}_{{2}}\ge{0}}\right.} \)

a) Calcolare una valutazione inferiore risolvendo il rilassamento continuo.

Soluzione ottima del rilassamento continuo = \( \displaystyle {\left(\frac{{66}}{{13}},{0}\right)} \)
\( \displaystyle {v}_{{I}}{\left({P}\right)} \)=31

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

sol. ammissibile = (6,0)
\( \displaystyle {v}_{{s}}{\left({P}\right)}={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ì:

\( \displaystyle {\left\lbrace\matrix{\min-{6}{x}_{{1}}-{6}{x}_{{2}}\\{13}{x}_{{1}}+{11}{x}_{{2}}+{x}_{{3}}={66}\\{18}{x}_{{1}}+{6}{x}_{{2}}+{x}_{{4}}={43}}\right.} \)

dove \( \displaystyle {x}_{{3}} \) e \( \displaystyle {x}_{{4}} \) sono le variabili di scarto che ho ricavato ottenendo
\( \displaystyle {x}_{{3}}={0} \)
\( \displaystyle {x}_{{4}}=-\frac{{629}}{{13}} \)

dunque \( \displaystyle {x}={\left(\frac{{66}}{{13}},{0},{0},-\frac{{629}}{{13}}\right)} \)

prendo come base quella costituita dagli indici 1,4 perchè è quella che ha generato la sol. ottima del rilassamento.
Scrivo la matrice di base
\( \displaystyle {A}_{{B}}={\left(\matrix{{13}&{0}\\{18}&{1}}\right)} \)

e la matrice non di base
\( \displaystyle {A}_{{N}}={\left(\matrix{{11}&{1}\\{6}&{0}}\right)} \)

Inverto la matrice di base
\( \displaystyle {{A}_{{B}}^{{-{{1}}}}}={\left(\matrix{\frac{{1}}{{13}}&-\frac{{18}}{{13}}\\{0}&{1}}\right)} \)

Calcolo la matrice
\( \displaystyle {B}={{A}_{{B}}^{{-{{1}}}}}\cdot{A}_{{N}}={\left(\matrix{-\frac{{97}}{{13}}&\frac{{1}}{{13}}\\{6}&{0}}\right)} \)

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

\( \displaystyle \sum_{{{j}\in{N}}}{\left\lbrace{b}_{{{r},{j}}}\right\rbrace}{x}_{{j}}\ge{\left\lbrace{x}_{{r}}\right\rbrace}\lt{b}\frac{{r}}{\gt}\lt{b}\frac{{r}}{\gt}{\left({C}{o}{n}\le{p}{a}{r}{e}{n}{t}{e}{s}{i}{g{{r}}}{a}{f{{f{{e}}}}}\in{d}{i}{c}{o}{l}{a}{p}{a}{r}{t}{e}{\mathfrak{{a}}}{z}{i}{o}{n}{a}{r}{i}{a}{d}{i}{q}{u}{e}{l}{l}{o}{c}{h}{e}è{a}{l}{l}{\quad\text{or}\quad}{o}\int{e}{r}{n}{o}\right)}\lt{b}\frac{{r}}{\gt}\lt{b}\frac{{r}}{\gt}{e}{m}{i}è{v}{e}\nu\to \)7/13 x_2 + 1/13 x_3 >= 1/13\( \displaystyle \lt{b}\frac{{r}}{\gt}\lt{b}\frac{{r}}{\gt}{r}{i}{c}{a}{v}{o} \)x_3=66 - 13x_1 - 11x_2\( \displaystyle {e}{l}{o}{s}{o}{s}{t}{i}{t}{u}{i}{s}{c}{o}\ne{l}{l}{a}{d}{i}{s}{e}{g{{u}}}{a}{g{{l}}}{i}{a}{n}{z}{a}{c}{h}{e}{h}{o}{t}{r}{o}{v}{a}\to\in\prec{e}{d}{e}{n}{z}{a}{e}{d}{o}{v}{r}{e}{\mathbf{{e}}}{v}{e}{n}{i}{r}{e}\lt{b}\frac{{r}}{\gt}\lt{b}\frac{{r}}{\gt} \)13x_1 + 4x_2<=65\( \displaystyle \lt{b}\frac{{r}}{\gt}\lt{b}\frac{{r}}{\gt}{L}{a}{s}{o}{l}{u}{z}{i}{o}\ne\in{\vec{{e}}}{m}{i}{d}à:\lt{b}\frac{{r}}{\gt} \)r=1\( \displaystyle \to \)12x_1 + 11x_2>=61\( \displaystyle \lt{b}\frac{{r}}{\gt}\lt{b}\frac{{r}}{\gt} \)r=4\( \displaystyle \to \)8x_1 + 7x_2>41$

Potete dirmi dove sbaglio? Grazie!!

[edge]

Ricerca Operativa col Pappalardo?

Pensa che direbbe il Longo se vedesse come hai invertito \( \displaystyle {A}_{{b}} \)

[Zephyro]

E' vero, ho sbagliato l'inversa che dovrebbe allora essere \( \displaystyle {\left(\matrix{\frac{{1}}{{13}}&{0}\\-\frac{{18}}{{13}}&{1}}\right)} \) ma lo stesso non mi torna il piano di taglio.. l'algoritmo è corretto?

[edge]

L'algoritmo è giusto però...
Essendo questo un problema di minimo,quando vai ad inserire le variabili di scarto devi aggiungere \( \displaystyle -{x}_{{3}} \) e \( \displaystyle -{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.

[Zephyro]

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