Teoremi e dimostrazioni, Ricerca operativa

PLI

1. Teorema

   Se la soluzione ottima x* del rilassamento lineare è intera, allora è ottima anche per il relativo problema intero.

   Dimostrazione:

   1. Cx* = z_PL ≤ z_PI
   2. Cx* ≥ z_PI
   3. x* ∈ X ⇒ z_PL ≤ Cx*
   4. Cx* = z_PL

2. Definizione

   Il rilassamento lineare di un PLI è un problema lineare (PL) uguale al relativo PLI ma senza il vincolo di interezza.

Tagli

1. Definizione

   Un taglio è una disequazione che verifica le seguenti proprietà:

   1. x ∈ X, 2x ≤ d₀ (cioè ∀x ∈ P, è valido per x)
   2. x ∉ P_L ⇒ 2x > d₀ (cioè x ∉ x ≤ d₀. Non vale per x_PL)

2. Tagli Chvatal

   Il taglio di Chvatal è definito come:

   1. uA x ≤ ub ⇒ ⌊uA⌋ x ≤ ⌊ub⌋ ⇒ A^((k)ʹ) x ≤ b^((k)ʹ)
   2. La chiusura di Chvatal P_k = P₀|{A^((k)ʹ) x ≤ b^((k)ʹ)} dove P ⊂ codice ←

   Il secondo taglio può essere: {uA + uA^((k)ʹ)} x ≤ {ub + ub^((k))}

   3. Da qui P₂, P_i f^((i)ʹ) ≥ b
      • P₀ → P₂ → P_n
      • P_n = conv(X) incluso connesso con raggio di Chvatal

   x^PL = x^Pin

3. Tagli di Gomory

   1. La formula per i tagli di Gomory è X_B = B^-1 F_X = b
   2. Formulazione intera: X₁ = Σ ^F_ij/_aσ, X₃ = b_n+1
   3. Formulazione frazionaria: ^{(a_ns - t_3n)} x₃ ≤ b_σ - ⌊bn⌋

Unim

1. Definizione UM

   Una matrice A di interi di dimensione m x n (m ≤ n) si dice unimodulare se ogni sottomatrice B^{m x m} ha det(B) ∈ {0,1,-1}

2. Teorema UM

   Se A è una matrice unimodulare e b è intero, allora il Poliedro P : {x ≥ 0 | Ax = b} ha vertici interi (non tutti).

PLI

1. Teorema

   Se la soluzione ottima x* del rilassamento lineare è intera, allora è ottima anche per il relativo problema intero.

   c^T x = z_PL ≤ z_PLI >= c^T x* = z_PLI

   x* ∈ X ⇒ z_PL ≥ c^T x*

2. Definizione

   Il rilassamento lineare di un PLI è un problema lineare (PL) uguale al relativo PLI ma senza il vincolo d'integrità.

Tagli

1. Definizione

   Un taglio è una disuguaglianza che verifica le seguenti proprietà:

   • x ∈ X, 2x = d_o (cioè ∀ x ∈ X, taglio per x)
   • a^T x ≥ α (cioè ∃ x: a^T x = d_o) Non vale per X_PL

2. Tagli Chvatal

   Il taglio di Chvatal è definito come:

   • ⟨uA⟩ x ≤ ⟨ub⟩ ⇔ uA x ≤ ⟨ub⟩
   • A^(k) x ≤ b^(k)
   • La chiusura di Chvatal
   • P₁ = P₀ \ A^(k) x ≤ b^(k) dove P è ridotta
   • Il secondo taglio può essere: ⟨uA ^(k) x ≤ ⟨ub + u^(k)
   • Di qui P₂ ⊆ P₀
   • A⁽¹²⁾ x ≤ ⟨a^(p)
   • P_n = conv(X) insieme convesso con raggio di CHVATAL solidale
   • X_PL = X_Pin

3. Tagli di Gomory

   Le formule per i tagli di Gomory sono:

   X_B = B^-1 F x_➜ = b

   • Formulazione intera: x₁ = ⌊∑_{s : asj > aij}⌋ x_s + ⌊b_n1⌋
   • Formulazione frazionaria: x_3j = ∑_j (a_ns - ⌊a_ns⌋) x_s > a_n - ⌊b_n1⌋

UM e TUM

1. Definizione UM

   Una matrice A di interi di dimensione m × n (m ≤ n) si dice unimodulare se ogni sottomatrice B m x m ha det(B) ∈ {0, ±1, ±3}

2. Teorema UM

   Se A è una matrice unimodulare e b è intero, allora il poliedro P: {x ≥ 0 | A x = b} ha vertici interi (non vuoti).

• Definizione TUM:

  Una matrice intera A di dimensioni m x n si dice TOTALMENTE UNIMODULARE se det(B) ∈ {0,1,-1} se per ogni sotto matrice quadrata B di qualsiasi ordine.

• Teorema TUM V in Zⁿ:

  Se A è una matrice intera TUM, b intero allora il politopo P: {x >= 0 / Ax >= b} ha solo vertici interi.

• Dimostrazione TUM V in Zⁿ:

  Sia x un vertice di P, dobbiamo dimostrare che è intero.

  Mostriamo che (x^s), dove s: A_I = b, è un vertice del politopo P: {x, s >= 0 / Ax - s = b_I) (si veda tabella di SLAQ)

  Supponiamo che (x^s) non sia un vertice (per assurdo) =>

  Ci sono due punti distinti (y, s₁), (z, s₂) del politopo che (x^s)

  ∀ (t), loro combinazione lineare, (x^s) = λ (y, s₁) + (1-λ)(z, s₁) con λ ∈ [0,1]

  Si osserva che (x, s₁), (z, s₁) sono interni al percorso per definizione.

  • s₁ + Δx₁ = b => s₁ = A_I = b
  • {x₁, s₁) sono distinti in x₁∀ x_I ma x >> x₁, (1/x) per cui λ è interno al politopo ma x* non può essere un vertice => Assurdo

  Poiché A è TUM:

  • {A,I} = A_IT b = A_IT b). b, tutti i vertici di P sono interi => x* ꝏ (intero)

• Teorema TUM condizione sufficienti:

  • Sia A matrice con a_ij ∈ {0,1}, ∀ i, j, voless A = TUM se:
  • Ogni colonna di A ha al massimo 2 elementi non nulli,
  • Esiste una partizione delle righe d μ.

• Dimostrazione:

  Dobbiamo dimostrare che det(Q) ∈ {0,1,-1} (det perché se è ≤ 0, |- a -|)

  • Q di qualsiasi ordine k con 1≤ k ≤ 1, m
  1. Dimostrare per induzione su k
  2. Passo base k=1. a_ij . a_ij d ∈ {0,1}
  3. Passo induttivo k > 1, no 3. CASI
  1. Q ha una colonna di 0 ——> det(Q) = 0
  2. Q ha una colonna con un solo elemento non nulli.
  • - (h trasversale) —> det Q = 1 det(1)

1) DEFINIZIONE: Un'insieme D di oggetti dell'knapsack è detto cover se la somma dei pesi di questi oggetti è strettamente maggiore di B.

2) DEFINIZIONE: Il cover è detto minimale se togliendo solo qualsiasi elemento del cover, esso non è più tale.

GRAFI

1) DEFINIZIONE: C è un ciclo euleriano in G(N,E) se passa per tutti gli archi una e una sola volta.

2) DEFINIZIONE: Se G ammette un ciclo euleriano allora è un grafo euleriano.

3) TEOREMA G EULERIANI

Dato G(V,E) valgono le seguenti espressioni: a) G è euleriano b) ∀v ∈ V d_G(v) ≥ 2 e pari c) C=_i{C_i: tutti disgiunti sugli archi}

4) DIMOSTRAZIONE

A ➝ B • Se G è euleriano esiste un ciclo euleriano che copre G • Se C passa una e una sola volta ogni v ∈ V è evidente che il grado di v è esattamente 2 • Se C passa più di una volta per almeno un nodo, quel nodo compare due volte in C come minimo, e sappiamo che esisto 2k modo archi incidenti con k visite del nodo • Perché per il tipo G è euleriano ➝ il grado rimane pari

B ➝ C • Se per ogni nodo v ∈ V d_G(v) ≥ 2 allora C non è un albero • Se G non è un albero ➝ almeno un ciclo in G lo chiamiamo C_i • Costruisco G_i+1 togliendo gli archi del ciclo C_i ➝ G_i(V,E) tE_i V• ∀v ∈ V se d_G(v) - 2 o E isocarto o -• d_G(v) - d_G(v) = 2 se • G_i rimane ancora un non albero ➝ ripeto il volto. Trovendo k C_i: G G_i = V_i C_i

C ➝ A • Sappiamo che G è connesso ➝ Ci, C_i ≠ 2 disgiunti • Possiamo concatenare i cicli creando un ciclo che passer due volte per il nodo in comune • Ripeto il volto fino alla esistenza di G ➝ G è euleriano

DEFINIZIONE Dato un grafo G(V,E), P è un cammino euleriano se passa per tutti gli archi una e una volta sola. Se G ammette un cammino euleriano esso non è un grafo euleriano.

TEOREMA Dato G connesso e non orientato, se G ha 2k nodi di grado dispari, allora G può essere scritto come unione di k cammini disgiunti sugli archi. Esclusione dei singoli nodi

DIMOSTRAZIONE di costruzione:

• Rendo G euleriano Creo G' tale che ad ogni coppia di nodi (s_i,t_i) associo un nodo fittizio connesso a s_i e a t_i, attraverso due archi fittizi w_i (nodo fittizio) e w_i t_i.
• G' è sicuramente euleriano ⟹ il nodo fittizio ha grado due quindi i nodi dispari a cui abbiamo aggiunto un arco sono diventati pari.
• Eseguo ciclo euleriano e elimino nodi e archi fittizi.
• Il risultato sono k cammini disgiunti per 2k nodi di grado dispari.

PROBLEMA SEPARAZIONE

1. DEFINIZIONE Il problema di separazione è un problema di Knapsack intero.

1. min Σ_i y_i x_i | Σ_i v_j x_i = Σ_j v_j y_j
2. { x_i ∈ B } = B | { y_i ∈ 0,1 }
3. ⟹ { x_i ∈ 0,1 }

MATCHING

DEFINIZIONE Sia dato un grafo G(N,A) ma orientato, un matching è un sottinsieme di A tale che ogni nodo è toccato al più una volta.

PARTIZIONE

DEFINIZIONE Un grafo è bipartitico e ammette una partizione (N₁,N₂) di N tale che ogni arco a∈A connette un nodo di N₁ e un nodo di N₂. Cioè ∀(i,j)∈A, i∈N₁ e s∈N₂ ⟹ A ⊇ N₁ x N₂.Se A = N₁ x N₂, il grafo si dice bipartito e completo.

Teorema

Se G-(N,A) un grafo non orientato, allora vale:

A) G è bipartito ↔ / cicli dispari

Dimostrazione

A →

Dato G bipartito esistono (N₁,N₂) partizioni . Se C un ciclo di G che parte da r ∈ N₂ allora: O ----- O ----- O --N₂ N₁ N₂ N₁ N₂ | O

Tutti nodi di N₂ verranno visitato dopo aver visitato un numero di archi dispari, e quelli di N₁ un numero di archi pari. → Si può quindi tornare in r ∈ N₂ solo dopo aver percorso un numero pari di archi →

B → A Supponiamo che G sia connesso e che non esistano cicli dispari. Prendiamo in nodo r qualsiasi del grafo e calcoliamo (u) (distanza d(r,u)) a ogni nodo v da   V₁: {u ∈ N| ≠ v | = d(v,u) ≡ pari} ⊕ v {v}   V₂: {v ∈ N| u ≡ v = d(v,v) ≡ dispari}

Potato che bipartizione e devo mostrare che l'archi che collegano i nodiN₂, e non esistono archi che collegano i nodi di N . Dimostro per N₁ ? (N₂)Se A(N₁) = insieme degli archi che come estremi ha entrambi nodi in N₁ →devo dimostrare che A(N₁) = Ø. Supponiamo per assurdo che t, (s,t) ∈A(N₁) . Sono A e B = i cammi . (7se) (f,t) ≠ sia X l'ultimo nodoin comune fra i due cammini A,&lo.

  6 → 6       b  6

 →↔→↔

e calcoliamo (a) lunghezza di (t) = |(P, x-s)|) . |(Pc, x-pc)| + 1 ? (t_s)=.4.

S marco Pb = Pc :

l(Pt, v-b)        (|P|) = (Ps, v+X) →     (Pv, t?s)    |(v, +/ox)|(Pc, v -+x)               (|Pt, tdX)|            (Pb,-bs) = → (Po,-tx)          i primi termin e visto che ⊃ = N₃ → B = T sono comnmi por;         ⇓[···]          (Pb, x -bs) Yes Anchlast? Pu - con ble d) (P,c)ASSURDO → CVD (per N₂ del)(H')

Teorema KÖNIG:

In un grafo bip. Sia max |M| = min |C|.

Dimostrazione

1. Costruiamo sul grafo bipartivo, il grafo orientato per il calcolo del flusso: (un lato) E(G) => G orientato.

Dobbiamo dimostrare: (1) >|S| = |Matching M t.c.| |[U| >= (3) S| = |S| = 1

• (2) => S| > |Flow| (3) => Nodo Cover| C| ₇ flusso | = capacità |C| = |C1|.
2. (A =>) Pongo ad l get arch del Matching e l flusso degli archi (s, i) e (s, j) dove s sono nodi accoppiati in M. => il flusso e ammIsibile e pari alla cardinalità del Matching.
3. (A q arcgi originari siano attraversati da flusso e — z è ammissibile.

   quindi il Matching è di cardinali.

4. (B =>) Si consideri un insieme C, (d archi tra do Dire nodo e i C 1 iG 1 ciI (i,j)∈C&cap:N2 (i,j)&cap:C

G è un regio e fl simmonscano alcuno di r in cammino ∈ S!

Ogni cammino da s ∈ S deve attraverso uno degli archi originari, poichè questi arche dunno acamo. uno dei stronni di. egizia cd anima altro = no= duecli ∈ volle oigeae ∩ C le ∈ Capachtà di n = |Ci|

5. (B A) D. G ° C Costruisci un nodo covere nel seguente modo: se (s₁, t₂ ∈ C) se (l, t) the C =c = c la Nested Cover

Conclusione

Con teorema D KÖNIG - FLOW MATCHING CUT

Con teorema MAX FLOW MIN CUT FLOW ⇔ CUT ⇔ Cover ⇔

- Matching ⇔ FLOW ⇔ CUT ⇔ D Cover CVD

Definizione

Sia dato un grafo non orientato G e sia dato un Matching M. Si definisce CAMMINO ALTERNANTE il cammino costruito intervenamente da archi accoppiati e archi liberi.

Definizione

Sia dato un cammino alternante. Esso e aumentante se il primo e l'ultimo di sono esposti.

Teorema:

Se M un Matching su un grafo e se P un cammino aumentante. Allora N ⇔(G P è un Matching di cardinàltà |M| + 1

Dimostrazione

1. Archi di P che non appartignano a P restano sotto
2. Archi di Pche non appartignano a restano in M
3. Archi di P che appertenzano a M vengono estesi in M

Il cisit in Matching pèiene intoccato se gv non combinna. Ecco sostiture q dei nodi intensi a P prime inciaden con Ncio d e i nodi di unco l piV.

I nodi esterni a P sono esposti in ciascico accoppiati secicko V