Caricare documenti e articoli online 
INFtub.com è un sito progettato per cercare i documenti in vari tipi di file e il caricamento di articoli online.
Meneame
 
Non ricordi la password?  ››  Iscriviti gratis
 

PIANI DI TAGLIO

informatica




Inviare l'articolo a Facebook Inviala documento ad un amico Appunto e analisi gratis - tweeter Scheda libro l'a WhatsApp - corso di

PIANI DI TAGLIO



Problema di Programmazione Lineare Intera (PLI):


min


Regione di ammissibilità del rilassamento continuo del problema di PLI:


P =


DEFINIZIONE 1 - Dato x* P, un (piano di) taglio è una disuguaglianza ax ao tale che


  1. ax ao per tutti i vettori x di P interi (cioè X=P Zn)

  1. ax* > ao

PROBLEMA DI SEPARAZIONE:




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 ao
  4. aggiungere il vincolo ax + xn+1 = ao 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 zPL dato da


x* =


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


x1 + x2 + x3 + x4/2 + x5/2 + x6/2 = 3/2


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


x1 + x2 + x3 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

x1 + x2 + x3 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 Rm arbitrario e si consideri l’equazione



uAx = ub

Si ponga quindi a uA ottenendo la disuguaglianza ax ub dove

aj Si=1,…,m ui aij j = 1,…,n

valida per P e per X. Infine si ponga ao ub ottenendo la disuguaglianza ax ao 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 A1x b1 la famiglia di tutte le disuguaglianze ottenibili come sopra al variare del vettore u in Rm.


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 xh* una variabile di base frazionaria corrispondente alla riga t del tableau ottimo (detta riga generatrice del taglio)

xh + Sj N atjxj = bt (= xh*)                                 (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

xh + Sj N atj xj bt (2)

detta taglio di Gomory in formulazione intera.


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

(xh + Sj N atj xj )x=x* = xh* = bt > bt

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

Sj N (atj - atj )xj bt - bt

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

Sj N j(atj)xj j(bt)            

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

Sj N j(atj)xj + s = -j(bt)        (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.






Privacy




Articolo informazione


Hits: 126
Apprezzato: scheda appunto

Commentare questo articolo:

Non sei registrato
Devi essere registrato per commentare

ISCRIVITI

E 'stato utile?



Copiare il codice

nella pagina web del tuo sito.


Copyright InfTub.com 2021