Ricerca Operativa

university

Programmi Lineari

max z = c1x1 + c2x1

soggetto a:

ai1x1 + ai2x2 <\=\> bi con i = 1,2,…,m

due variabili di decisione risolvibile graficamente

rappresentare in R^2 la regione ammissibile Sa
studiare le rette isocosto/isoprofitto z = c1x1 + c2x2

Forma standard

massimizzazione
- min –> max cambiando il segno
variabili tutte positive
- si crea la corrispondente variabile xj = -xj, xj >= 0
vincoli sono equivalenze
- variabili di slack e surplus

Insiemi convessi

u,v appartenenti a R^n con a appartenente a [0,1] x = v + a(u-v) = a*u + (1-a)v

x combinazione lineare convessa di u e v

Insieme S sottoinsieme di R^n e' convesso se per ogni coppia u,v appartenenti a S tutte le combinazioni lineari convesse sono elementi di S

S convesso, x appartente a S e' vertice se non esistono u,v appartenenti a S tali che u!=v e x e' combinazione lineare convessa di u,v x vertice se non esistono u,v t.c x = 1/2u + 1/2v

se un programma lineare ammette soluzioni ottime almeno una di esse e vertice di Sa: Teorema Fondamentale della Programmazione Lineare

x e' vertice di Sa se e solo se le colonne di A in { Aj: xj > 0 } sono linermente indipendenti

Una Base e' un insieme { xj1,xj2,…,xjm } dette variabili di base tali che: le colonne Aj1,…,Ajm formano una base dello spazio generato dalle colonne di A

Soluzioni di Base

del sistema Ax = b unica soluzione x = x(B) che ha xn = 0

Teorema Fondamentale della Programmazione Lineare

se il programma lineare -max{ z = c^Tx : Ax = b, x >= 0 } ammette soluzioni ottime, allora almeno una di esse e' vertice di Sa

Algoritmo del Simplesso

B base ammissibile x(B) soluzione ammissibile di base associata a B

se almeno una delle componenti di xj(B) e' nulla la base B e' detta degenere

Criteri
- di ottimalita'
- costo ridotto
- condizione sufficiente affinche x(B) sia ottima e' che risulti che rj <=0 per ogni variabile xj fuori base
di illimitatezza
- la riformulazione dei parametri della x fuori base entrante (r > 0) e' una colonna negativa

Politopi

Sa, regione ammissibile e' in generale intersezione di iperpiani e semispazi

Iperpiano: definito da un punto x0 e un vettore v costituito dai punti x t.c. il vettore (x - x0) e' ortogonale a v (equazioni: vx = a)
Semispazio: definito a partire da un iperpiano e da un vettore costituito dai punti x t.c (x - x0) non forma un angolo superiore ai 90gradi con v (disequazioni: vx > a)
un insieme convesso
- in particolare un Poliedro convesso
- se limitato e' chiamato Politopo
- un Politopo avra' sempre almeno una soluzione che sara' un vertice

Combinazioni Lineari

S = { v1, v2, … vk } sottoinsieme di R^n detto insieme libero Vale che
- il vettore nullo non appartiene a S
- se S' sottoinsieme di S allora S' e insieme libero
- se S1 e S2 liberi la loro intersezione e' un insieme libero
Equivalentemente
- x1v1 + … + xkvk = 0 ==> x1 = … = xk = 0
- vettore0 non appartiene a S e nessun vj risulta appartenere a L(S\vj)
- ogni w appartenente a L(S) si esprime come unica combinazione lineare con coefficienti xj unicamente determinati
w appartenente ad R^n e' combinazione lineare dei vettori di S se

esistono x1,x2,xk t.c.

w = x1v1 + x2v2 + … + xkvk

I vettori di S sono detti linearmente indipendenti se x1v1 + x2v2 … = 0 ==> x1 = x2 = … = 0
- l’unico modo per combinare linermente i vettori di S nel vettore nullo e' di usare coefficienti tutti nulli

Gauss Jordan

Matrice: As
- L(S) e' lo spazio delle colonne di As la sua dimensione e' detta rango di A: p(A)
- corrisponde al numero di equazioni non ridondanti/contraddittorie di ogni sistema Ax=b

Proprieta'

le soluzioni non cambiano se
- due equazioni vengono permutate: Ep <-> Eq
- una equazione Ep e' sostituita: Ep <– k*Ep
- una equazione Eq e' sostituita: Eq <– Eq + k*Ep

Sottospazi

V = L(S)
somma vettoriale e prodotto di numero-vettore sono interne a V
L(S) e' un sottospazio di R^n
S e' detto insieme generatore di V
elementi di S detti generatori

Uno spazio ha infiniti possibili generatori

S = { v1,v2, … ,vk } S' = { v2, … ,vk }
- L(S') sottoinsieme di L(S)
- se v1 e' combinazione lineare di S' allora L(S)=L(S')

Basi

Un insieme generatore di un sottospazio v e' detto base se e solo se e' anche un insieme libero

tutte le infinite basi di V hanno la stessa cardinalita'
- detta dimensione di V
  
  dimostrabile per il metodo degli scarti successivi