Appunti di Metodi e modelli di ottimizzazione discreta 1 - parte 2

Poliedri e formulazioni

Poliedro P ⊂ ℝ^k è l'insieme dei punti che soddisfano un numero finito di disequazioni lineari, ossia P = {x ⊂ ℝⁿ : Ax ≤ b} con A ⊂ ℝ^m,n, x ⊂ ℝⁿ, b ⊂ ℝ^m.

Un poliedro è sicuramente una regione connessa, individuato dai vincoli che sono iperpiani in n dimensioni.

Dividono Rⁿ in iperioni ammissibili e non, che individuano uno spazio connesso.

Esempi poliedri e formulazioni

Dimensione dello spazio degli interi k=1 e dei reali h=1.

Z^k ⊂ R^h, x = (x₁, x₂), x₂ ⊂ x ⊂ ℝ -> la prima componente deve essere intera, la seconda reale.

I valori (x₁, x₂) ammissibili giacciono sulle rette x₁ = k, k ⊂ Z individuate.

Dimensione dello spazio degli interi k=2 e dei reali h=0 - Z^k = R^h -> spazio delle soluzioni ammissibili, individuato da punti che hanno entrambe le coordinate intere: (x₁, x₂) ⊂ Z^h.

Consideriamo dette soluzioni ammissibili in Z¹ e dei vincoli che circoscrivono la regione connessa di tali punti:

• V: x₂ ≥ 0,5
• W: x₁ ≤ 4,8
• P: x₁ ≤ 6; 3, x₂ ≤ 0,5 definiscono il poliedro P = {x ⊂ ℝ²: x₂ ≥ 0,5; x₁ ≤ 4,8; x₁ ≤ 6; 3, x₂ ≤ 0,5}

Il segmento definito da queste condizioni contiene tutti i punti ammissibili.

Poliedri e formulazioni

Poliedro P ⊆ ℝⁿ è l’insieme dei punti che soddisfano un numero finito di disequazioni lineari, ossia: P = { x ∈ ℝⁿ : Ax ≤ b} con A ∈ ℝ^{m × n}, x ∈ ℝⁿ, b ∈ ℝ^m.

Un poliedro è sicuramente una regione connessa, individuata dai vincoli che sono iperpiani in n dimensioni. Divide ℝⁿ in iperpoliedri ammissibili e non, che individuano uno spazio connesso.

Definizione

Per un poliedro P ⊂ ℝ^k è una formulazione per un insieme x ⊆ x'⊆ ℝ^k se e solo se x = P ∩ (Z^k × ℝ^l), dove Z^l è l’insieme delle soluzioni ammissibili del problema e l’insieme dei vincoli del problema è un insieme finito di disequazioni lineari che definiscono un poliedro P.

Se P contiene tutte e sole le soluzioni ammissibili e l’insieme dei vincoli è una formulazione.

Esempi poliedri e formulazioni

Dimensione dello spazio degli interi k = 1 e dei reali h = 1.

Zᵏ × Rˡ , x = (x₁,x₂) x₁ ∈ Z x₂ ∈ ℝ → la prima componente deve essere intera, la seconda reale. I valori (x₁,x₂) ammissibili giacciono sulle rette x₁ = k, k ∈ Z individuate.

Punti che soddisfano x₁ ∈ Z e x₂ ∈ ℝ.

Dimensione dello spazio degli interi k = 2 e dei reali h = 0 - Zᵏ × Rˡ - spazio delle soluzioni ammissibili, individuato dai punti che hanno entrambe le coordinate intere: (x₁,x₂) ∈ Zᵏ.

Consideriamo dette soluzioni ammissibili in Zᵏ e dei vincoli che circoscrivono la regione connessa di tali punti:

• X₂ ≥ 0,5
• X₂ ≤ 4,0
• X₁ ≤ 4,9
• X₁ ≥ 0,5 definiscono il poliedro P = { x ∈ ℝ²: x₂ ≥ 0,5; x₁ ≤ 4,9; x₁ ≥ 0,5; x₂ ≤ 4,8} x₁ ≥ 0 intero x₂ ≥ 0 intera → NB. x₁ è più stringente di x₂,0, quindi il primo implica il secondo, ma non viceversa

Allora: P è formulazione per xᵢ × ℤᵏ e solo se x ≠ P ∩ (Zᵏ × ℝˡ) x P è formulazione e i vincoli contengono tutte le soluzioni ammissibili, e non solo altri vincoli xm cercati e contenute in P.

σ è considerazione xᵢ ⊆ ℝ^k: x ∈ xᵢ s.t., x₁, x₂ ≤ 5; x₁, x₂ ≥ 0.5.

P è P che non contiene x.

Sia xm anche interi Z^l ={ x₁,x₂: x₁ ≥ 5 } se Siano punti P non è formulazione.

31 consideriamo le seguenti soluzioni ammissibili:

_v1 x₂ ∈ Z^l e P := { x ∈ R² : x verifica u₁,u₂,u₄ }

P ∩ Z^l esclude delle soluzioni ammissibili di x : P ∩ Z^l ≠ X quindi P non è formulazione per x dato.

Definizione

DEF Dato x ∈ z^R le due formulazioni P₁ e P₂ per X, allora P₂ è migliore di P₂ se P₂ ⊂ P₁.

x * { _{j ∈ l} } ⊂ Z^l → P₂ è migliore perché è più stringente di P₁ : P₂ ⊂ P₁.

Presupposto necessario: P₁ e P₂ devono essere formulazioni.

P indica la formulazione migliore possibile.

Combinazione convessa

Combinazione convessa insieme di punti, che è possibile ottenere da una combinazione convessa di altri punti dati.

P → è il segmento che congiunge i due punti P = (x_P