Logica e Programmazione Lineare
5 Questions
1 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

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?

<p>x1 ∨ x2 =⇒ y</p> Signup and view all the answers

A cosa corrisponde il vincolo x1 + x2 ≤ 2y?

<p>Questo vincolo indica che la somma delle variabili binarie x1 e x2 è al massimo doppia della variabile intera y.</p> 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.

Quiz Team

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à.

More Like This

Use Quizgecko on...
Browser
Browser