Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
vuoi
o PayPal
tutte le volte che vuoi
Analisi delle disuguaglianze logiche
Le due disuguaglianze contrassegnate dal pallino rosso sono le seguenti:
Se x2 = 0, allora anche x3 = 0, altrimenti la prima disuguaglianza non sarebbe vera.
Considerando i vincoli 2) e 3) e sostituendo x2 = 1, possiamo dedurre che:
- Se x1 = 1 e x3 = 0, o viceversa, il vincolo 2) è soddisfatto.
- Entrambe le variabili possono essere 1, ma non contemporaneamente secondo il vincolo 3).
Considerando le disuguaglianze contrassegnate dal pallino arancione, otteniamo un sistema di vincoli che dipende solo da x1 o da x3. Possiamo quindi operare una sostituzione di una delle due variabili.
Risolutivi:
Algoritmi e classificazione
Algoritmo di Cutting Planes
Ad ogni iterazione si restringe l'area no a quando la soluzione del rilassamento continuo non diventa intera, in presenza della quale abbiamo l'ottimo del problema di PLI.
Convergere all'ottimo globale significa introdurre un numero esponenziale di tagli.
E se la regione ammissibile non contiene punti interi??
L'algoritmo di Cutting Planes inizierà ad introdurre dei tagli e inizieranno a limitare la regione ammissibile del problema continuo no a quando vuota, un vincolo introdotto renderà la regione ammissibile del rilassamento senza aver determinato nessun vertice intero. Il taglio introdotto renderà il problema impossibile. Noi dovremo essere in grado, dal punto di vista algebrico, di determinare questa situazione.
Geometria dell'algoritmo di Cutting Planes - Tipi di tagli
Taglio profondo: butta via, oltre alla soluzione ottima del rilassamento continuo, anche
altresoluzioni frazionarie (esempio: il primo taglio ingura). PLIdiqualsiasiproblemaperValgono ilsoloper che considerandostiamoproblemaValgono ilanalisi chepoliedrale stianpoliedroparticolareperstudiandoHalfZeroTagli I vincoli hanno tutti coe cienti interi e quindi saranno soddisfatti pervalori interi delle variabili.Si porta a combinare i vincoli per ottenere un nuovo vincolo.Il vincolo ottenuto è ottenuto dalla somma, ma avremmo anchefrazionari IÉ potuto fare una qualunque combinazione lineare dei due.Si ha un vincolo con coe cienti tutti pari e termine noto dispari.Dividendo tutto per 2 otteniamo ancora che a primo membroabbiamo tutti coe cienti interi, come vogliamo che sia.Ora se una quantità intera deve essere minore o uguale di un valorefrazionario => questo può essere troncato per difetto.Sostanzialmente, arrotondando, abbiamo introdotto un vincolo piùstringente dei precedenti.NB: l'aggiunta di vincoli che nascono dalla combinazione
lineare dialtri vincoli non cambia la soluzione ottima del problema.di Taglio Gomory Risulta essere una tecnica molto più sofisticata rispetto alla precedente. Risolve prima il rilassato all'ottimo e si sfruttano le informazioni del tableau per generare il taglio. In questo caso, a differenza del tipo precedente, si ha bisogno di risolvere il rilassamento continuo. Taglio di Gomory: formulazione KnKBi se_terminevincoloti ati direxp ottimoiiidicolonna sen indicidenevariabilifuorile1 atrevariabili da è l'unica coefficienricien nacoemaemesnaunaeoteraquengache dibase.suarigatvaiga quaaggiungayamaga Lifunzione casoconintera siinparte questol'interoconsidera piùpiccoloappena all'argomento Sui termini noti si opera allo stesso modo un troncamento, per iragionamenti fatti per lo Zero Half Cut. Sostanzialmente, in poche parole, per il taglio di Gomory si considera il vincolo relativo alla variabile in base frazionaria e se ne troncano tutti i coe cienti e termini.noti. Una volta fatto si deve riportare il vincolo all'interno del
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
