Ricerca operativa

Formattazione del testo con tag HTML

Bx (n - m) è un vettore colonna n-dimensionale.

N - 1B x = B · b x = 0

Se è invertibile, si ha che e .B N ( )x = b → (B, N) = bxN → Bx + Nx = bB N

Soluzione di base( )x = B n - m x, in cui le componenti di x sono nulle, è detta soluzione di base se N0-1x = B · b x. Le variabili in x sono dette variabili di base.

Nota: Quando sono fissate le variabili di base, cioè quando sono fissate le colonne di B che formano N, la soluzione di base associata è univocamente determinata da x = B · b, assumendo det B ≠ 0.

Soluzione di base ammissibile( )x ≥ 0

Una soluzione di base è ammissibile se x ≥ 0.

Soluzione di base degenerex > 0

Se ogni componente di x > 0, la soluzione non è degenere; altrimenti è detta degenere.

Esempio di determinazione delle soluzioni di base in un problema di programmazione lineare forma standard.

Soluzione di base vertice ↝ ↝ A x = b

Quindi, serve ricondursi alla forma standard .max x1x ≤ 223x -

x ≤ 31 2x , x ≥ 01 22ℝ

Due incognite di partenza, siamo in ℝ, quindi l'intersezione di due vincoli fornisce un vertice.

Però, aggiungendo le slack, passiamo in ℝ⁴. È importante sottolineare che, da un punto di vista algebrico, avere una soluzione di base implica avere le slack, altrimenti non si può trovare la soluzione. I vincoli a disposizione sono due. Ciò indica che abbiamo un sistema, in cui

26èè fi è è è fi è

Martina Contestabile Ingegneria Informatica - II Anno A.A. 2021/2022

A B N B Nscomponiamo in e , dove è la matrice di base e si ottiene risolvendo il sistema, mentre B m × m mè quella non di base, contenente tutti zeri. Rimane solo , avente dimensione , dove è il forma standard numero di vincoli. Problema in min - x1 [ ]0 1 1 0x + x = 2 A =2 3 3 -1 0 13x - x + x = 31 2 4x , x , x , x ≥ 01 2 3 4Attenzione Se prendo la matrice con colonne le variabili di slack, ottengo una

soluzione di base associata a è soluzione di base1 2 3 43ammissibile, non degenere. [ ]0 1 1 0A =min - x 3 -1 0 11x + x = 22 33x - x + x = 3 [ ]1 2 4 0 1B =x , x , x , x ≥ 0 3 01 2 3 4 27fi ffiMartina Contestabile Ingegneria Informatica - II Anno A.A. 2021/2022x , x A BVariabili di base , corrispondenti alle colonne di che sono in .1 3 [ ] [ ]1( ) [ ]x 0 2 11 -1x = = B b = =3B 3 2x 1 03 ( )x 2x = = (0,0)N x4B x = 1 x = 2 x = x = 0La soluzione di base associata a è soluzione di base1 3 2 4ammissibile, non degenere.Due variabili che vanno a zero due slack che vanno a zero. Anche gli assi hanno le loro slack.↝Quindi, per ogni vertice, due slack vanno a zero, quindi c'è l'intersezione di due vincoli.[ ]0 1 1 0A =min - x 3 -1 0 11x + x = 22 3 [ ]3x - x + x = 3 0 01 2 4 B =x , x , x , x ≥ 0 3 11 2 3 4x , xVariabili di base: .1 4-1det(B) = 0 → ∄B → ∄ .soluzione di base associata [ ]0 1 1 0A

una e una sola soluzione. Tipico esercizio di teoria ⇒ A, B, C, D

Punto soluzione ammissibile: i vertici sono esempi di soluzione di base ammissibile. ⇒ E

Punto di soluzione non di base ammissibile: il vertice. ⇒ Punto non di base non ammissibile: un qualsiasi punto fuori dalla regione ammissibile.

Ragionando:

Se mi trovo su un vertice, due variabili sono a zero.

Se mi trovo sulla frontiera, almeno una variabile è a zero.

Se mi trovo su un lato del poliedro, solo una variabile è pari a zero.

Se prendo un punto interno, non mi trovo sulla frontiera, quindi nessuna variabile è a zero.

BC

Se mi chiedono un punto di, trovo la combinazione convessa degli estremi del segmento.

29Martina Contestabile Ingegneria Informatica - II Anno A.A. 2021/2022

A x = 0 ∈ x ⟹ x > 0 ∈ x

Spostarsi da al vertice sopra, .2 N 2 B

Quando si passa da un vertice a quello adiacente, chi è in base va fuori base e chi è fuori base va in base. C'è uno scambio,

Misura il passaggio fra un vertice e quello adiacente.

30Martina Contestabile Ingegneria Informatica - II Anno A.A. 2021/2022

POLITOPI CONVESSI E TEOREMI

Politopi convessi

Definizione — Iperpiano n - 1

Un iperpiano è un sottospazio lineare di dimensioni rispetto allo spazio che lo contiene. αx = α

Dato un vettore di coefficienti α, un vettore di variabili x e uno scalare α, l'iperpiano è un insieme T|H = {x ∈ ℝ αx = α} determinato da α. 0 ≤ α ∈ ℝ

Nota: La definizione di iperpiano generalizza la nozione di retta in ℝ.

Definizione — Semispazi

T n T| {x ∈ ℝ αx ≥ α} {x ∈ ℝ αx ≤ α}

Definizione — punto estremo

Un punto P di un insieme convesso è un punto estremo di P se in P non esistono due punti (distinti) x, y tali che x, y ∈ P e x = λx + (1 - λ)y, 0 < λ < 1.

Definizione — poliedro

Si dice poliedro (convesso) l'intersezione di un numero

Il tuo compito è formattare il testo fornito utilizzando tag html.

ATTENZIONE: non modificare il testo in altro modo, NON aggiungere commenti, NON utilizzare tag h1;

nito di semispazi e di iperpiani.

De nizione — politopo

Si dice politopo (convesso) un poliedro limitato e non vuoto.

{ n |P := {x ∈ ℝ A x = b x ≥ 0}è limitato se ∃M > 0 : x ≤ M ∀x ∈ POgni poliedro ha un numero nito di vertici (punti estremi).

2 3ℝ ℝ

Esempio di politopo in Esempio di politopo in

Teorema di Minkowski-Weyl

Ogni punto di un politopo si pu ottenere come combinazioneconvessa dei suoi vertici.

n |x , . . . , x ∈ ℝ P := {x ≥ 0 A x = b}

Siano i vertici di ,1 k k k∑ ∑|λ = 1 y = λ xy ∈ P ⇒ λ , λ , . . . , λ ≥ 0

Se 1 2 k i i ii=1 i=1

Qualsiasi sia il numero di soluzioni del politopo, i vertici bastano Interpretazione geometricaper generare la soluzione ammissibile e tutti i punti appartenenti aquest’ultima.

Nota Vale solo per politopi. Se la regione non è limitata, non posso usare questo teorema.

31fififififi fi ffi fi ò è fi

Martina Contestabile Ingegneria

Informatica - II Anno A.A. 2021/2022

Teorema P := {x ≥ 0 : A x = b}

L'insieme convesso.

Dimostrazione Se contiene un solo punto, un punto è un insieme convesso, allora il teorema è dimostrato. Altrimenti, dobbiamo provare che ∀x, y ∈ P, ∀λ : 0 < λ < 1, λ x + (1 − λ)y ∈ P z, cioè il vettore ,