quando x* X, trovare un taglio.

ALGORITMO DEI PIANI DI TAGLIO

1. risolvere il problema di PL risultante dal rilassamento continuo min = cx* ;
2. while x* non intero do
3. risolvere il problema di separazione di x* da X trovando un taglio ax a_o
4. aggiungere il vincolo ax + x_n+1 = a_o al rilassamento continuo corrente ;
5. n := n+1 ;

6.   risolvere il rilassamento continuo col metodo del SIMPLESSO DUALE ottenendo un nuovo x*

endwhile

return x*

ESEMPIO

z = min

N.B. la matrice dei vincoli non è TUM

P =

ottimo del rilassamento continuo z_PL dato da

x* =

Moltiplichiamo i tre vincoli ciascuno per .5 e sommiamoli. Otteniamo l' equazione

x₁ + x₂ + x₃ + x₄/2 + x₅/2 + x₆/2 = 3/2

valida per P e quindi anche per X. Arrotondando ogni coefficiente all' intero immediatamente inferiore otteniamo la disuguaglianza

x₁ + x₂ + x₃ 3/2

valida per P dato che x 0 e quindi anche per X.

Adesso ricordiamoci che le variabili debbono essere intere e che quindi la disuguaglianza

x₁ + x₂ + x₃ 3/2 = 1

deve valere per X (ma non per P). Abbiamo così ottenuto un piano di taglio per x*. Questa procedura si può generalizzare ottenendo la famiglia di disuguaglianze dette di Chvátal-Gomory.

Dato il sistema Ax = b, x 0, si scelga un vettore u R^m arbitrario e si consideri l'equazione

uAx = ub

Si ponga quindi a uA ottenendo la disuguaglianza ax ub dove

a_j S_i=1,.,m u_i a_ij j = 1,.,n

valida per P e per X. Infine si ponga a_o ub ottenendo la disuguaglianza ax a_o valida per X (ma non necessariamente per P).

TEOREMA (Chvátal) - Dato un qualunque vertice a coordinate non tutte intere x* di P, esiste sempre un vettore u tale che la disuguaglianza ottenuta con la procedura riportata sopra viene violata da x*, ma è valida per X.

N.B. Esistono disuguaglianze valide per X che non possono ottenersi con la procedura sopra illustrata a partire dal sistema Ax = b.

Indichiamo con A¹x b¹ la famiglia di tutte le disuguaglianze ottenibili come sopra al variare del vettore u in R^m.

In effetti quanto visto nelle ultime due trasparenze è di interesse soprattutto teorico, dato che non abbiamo bisogno di trovare una formulazione lineare (che sappiamo esistere) completa per conv(X). Cosa vorremmo è identificare una famiglia di tagli, possibilmente poco numerosa, che, aggiunta ai vincoli originali, facesse in modo che la soluzione del rilassamento continuo del problema di PLI originale avesse coordinate intere.

8.1-TAGLI DI GOMORY

IDEA: generare tagli utilizzando l' informazione data dalla base ottima B corrispondente alla soluzione di base ottima x* del rilassamento corrente del problema di PLI originale.

Sia x_h* una variabile di base frazionaria corrispondente alla riga t del tableau ottimo (detta riga generatrice del taglio)

x_h + S_{j N} a_tjx_j = b_t (= x_h*) (1)

dove N è l' insieme delle variabili non in base. (N.B. I coefficienti di A come pure i valori di b sono già stati moltiplicati a sinistra per B^-1.)

L' equazione (1) corrisponde ad una scelta particolare per il vettore u della relazione generale uAx = ub vista prima, più precisamente si prende u uguale alla riga t-esima di B^-1.

Applichiamo alla (1) la procedura di Chvátal e otteniamo la disuguaglianza

x_h + S_{j N} a_tj x_j b_t (2)

detta taglio di Gomory in formulazione intera.

N.B. Per costruzione la (2) è valida per X, ma violata da x*: infatti dato che x_j* = 0 per j N e che x_h* = b_t è frazionaria, abbiamo

(x_h + S_{j N} a_tj x_j )_x=x* = x_h* = b_t > b_t

Sottraendo (2) da (1) otteniamo la formulazione frazionaria del taglio di Gomory

S_{j N} (a_tj - a_tj )x_j b_t - b_t

Indichiamo con j(y) la funzione y - y (sempre non negativa) che fornisce la parte frazionaria del numero y, possiamo scrivere la disuguaglianza di Gomory in forma frazionaria come

S_{j N} j(a_tj)x_j j(b_t)

Cambiando di segno ed introducendo una variabile ausiliaria s, non negativa ed intera, possiamo scrivere il taglio di Gomory nella forma

S_{j N} j(a_tj)x_j + s = -j(b_t)    (3)

Questa forma del taglio può essere aggiunta al tableau corrente mantenendo l' ammissibilità duale e facilitando così l' applicazione del Simplesso Duale al passo 6 dell' algoritmo di taglio.