Podcast Beta
Questions and Answers
Definire il vincolo che rappresenta la disgiunzione logica tra due variabili binarie x1 e x2.
x1 ∨ x2
Qual è il vincolo che esprime la congiunzione logica tra due variabili binarie x1 e x2 quando è vero che x1 e x2 implicano y?
x1 ∧ x2 =⇒ y
Spiegare il significato del vincolo x1 ∧ x2 ∧ ... ∧ xk =⇒ y.
Il vincolo indica che se tutte le variabili binarie x1, x2, ..., xk sono vere, allora y deve essere vera.
Quale vincolo rappresenta che almeno una delle due variabili binarie x1 e x2 è vera e implica y?
Signup and view all the answers
A cosa corrisponde il vincolo x1 + x2 ≤ 2y?
Signup and view all the answers
Study Notes
Vincoli Logici
- Il rilassamento lineare del nodo produce una soluzione a variabili intere (ottimalità).
- Il rilassamento lineare del nodo è privo di soluzioni ammissibili (inammissibilità).
- Il rilassamento lineare del nodo produce una soluzione a variabili continue che è peggiore della miglior soluzione intera finora trovata (bound).
Criteri di Chiusura dei Nodi (B&B)
- Condizione: x1 ∨ x2 → x1 + x2 ≥ 1
- Condizione: x =⇒ y → x ≤ y
- Condizione: x1 ∧ x2 =⇒ y → x1 + x2 − 1 ≤ y
- Condizione: x1 ∧ x2 ∧ ... ∧ xk =⇒ y → ∑i=1k xi − (k − 1) ≤ y
- Condizione: x1 ∨ x2 ∨ ... ∨ xk =⇒ y → ∑i=1k xi ≤ ky
- Condizione: x1 ∨ x2 =⇒ y → x1 + x2 ≤ 2y
Regole di Pivoting (Cambio di Base)
- Si consideri un programma lineare in forma standard riformulato rispetto a una base B ⊆ {x1, x2, ..., xn}
- N = {xi : xi ∉ B} è l'insieme di variabili fuori base
- max z = z(B) + ∑j∈N rj xj
- xi = βi + ∑j∈N αij xj ∀xi ∈ B
Dualità
- Il duale di un programma lineare è min{w = u b : u A ≥ c}
- Condizioni di complementarietà primale-duale: x∗ e u∗ sono soluzioni ottime, v∗ T x∗ = 0
Simplesso
- Si sceglie la variabile entrante xq ∈ N tale che rq = max{rk : xk ∈ N } > 0
- Si sceglie la variabile uscente xp ∈ B tale che βp = min{βi : xi ∈ B} < 0
Condizioni di Bellman (SPT)
- La soluzione ammissibile per il problema SPT su un grafo orientato e pesato G = (N, A) individuata dal generico albero di copertura T è ottima se e solo se:
- du + cuv = dv ∀(u, v) ∈ T
- du + cuv ≥ dv ∀(u, v) ∉ T
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
Questo quiz riguarda i vincoli logici e i criteri di chiusura dei nodi utilizzati nella programmazione lineare. Verifica la tua comprensione delle condizioni di ottimalità e inammissibilità.
