Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
vuoi
o PayPal
tutte le volte che vuoi
Ricerca operativa
2017/2018
(Prof. Mastroeni Giandomenico)
I'm sorry, I can't help with this request.Ipotesi 1:
∑i=1m oi = ∑j=1m dj
→ Le origini non hanno più materiale, le destinazioni "sono piene"
min ∑i=1m ∑j=1m cij xij
- ∑j=1m xij = oi ; i=1,...,m
- ∑i=1m xij = dj ; j=1,...,m
- xij ≥ 0 ; i=1,...,m ; j=1,...,m
Se cambiamo l'ipotesi?
Ipotesi 2:
∑i=1m oi < ∑j=1m dj
⇒
min ∑i=1m ∑j=1m cij xij
- ∑j=1m xij = oi ; i=1,...,m
- ∑i=1m xij ≤ dj ; j=1,...,m
- xij ≥ 0 ; i=1,...,m ; j=1,...,m
21/09/2023
Problema di programmazione lineare in forma standard
max ∑j=1m cj xj
- ∑j=1m aij xj ≤ bj
max cT x
Ax ≤ b
cT = (c1,...,cm) ∈ ℝm
bT = (b1,...,bm) ∈ ℝm
A = [aij j=1,...,m i=1,...,m] (m x m)
xT = (x1,...,xm)
La regione ammissibile del problema è
P = {x ∈ ℝm | Ax ≤ b}
g(x) = 0 ⇒
g(x) ≤ 0
g(x) ≥ 0 (-g(x) ≤ 0)
P = { x ∈ ℝ2 : x2 ≥ 3 }
V = { (0,0)3 }
E = { (-1,0) ; (0,-1) ; (0,1) }
V = { (0,0)3 }
E = { (1,0) ; (0,1) }
V = { v1 , v2 , v3 , v4 }
E = ∅
( x1 + x2 ≥ 2
x1 ≥ 0
x2 ≥ 0
V = { (0,2) ; (2,0) }
E = { (0,1) ; (1,0) }
P = ( -x1 + x2 ≤ 1
x1 + 3x2 ≥ 3
x2 ≥ 1
Teorema Fondamentale Della Programmazione Lineare
max x ∈ P cT x
Sia P = conv V (V) + cono (E), V = { v1,...,vm3 } ∈ P, E = { e1,...,em3 } ∈ ℝm, e supponiamo cT x ≤ M ∀x ∈ P, allora esiste k ∈ {1,...,m3} t.c. cT vk = max (cT x) x ∈ P
Teorema (Dualità Forte):
Se (P) ammette ottimo finito allora anche (D) ammette ottimo finito e risulta
max (cTx) = min (yTb)
x ∈ P y ∈ D
Corollario 3:
Se P ≠ ∅ e D = ∅ allora P è illimitato superiormente
Osservazione:
È possibile che P = ∅ ed anche D = ∅
Esercizio: Scrivere il Duale
(P)
- max (3x1 + 2x2)
- x1 + x2 ≤ 0
- -x1 + x2 ≤ -2
A = (1, 1) &sup>(-1, 1)
cT = (3, 2) b = (0) &sup>(-2)
yTA = (y1, y2) yTb = (y1, y2) (0) &sup>(-2) = -2y2
(D)
- min (-2y2)
- y1 - y2 = 3
- y1 - y2 = 2
- y1, y2 ≥ 0
Esercizio: Avrete l’Ottimo Finito?
(D)
- min (y1 + 2y4)
- y4 + y2 - y3 = 2
- y4 - y2 - y1 = 1
- yi ≥ 0 i= 1, ..., 4
y4 + y2 - 2 = y3 ≥ 0 y1 + y4 - 2 ≥ 0 yi - y2 - 1 = 1 ≥ 0 y4 ≥ 0 y3 ≥ 0 y2 ≥ 0
05/10/2017
(P)
- max cTx
- Ax ≤ b
(D)
- min cTx
- xTA = cT
- y ≥ 0
D: { y ∈ ℜm: yTA = cT, y ≥ 0 }
Definizione (Soluzione di base duale):
Datata una base B (B è tale che AB sia invertibile) si definisce soluzione di base duale:
yt = (yB, yN) ∈ ℜm ove yB = cTb-1bT, yn = 0
bB = (8)/(x) x = AB-1bB = (15/4)/(3/2)
x*B = CTAB-1 = 5/4/3/4 → SOL. OTTIMA "PERCHÉ TUTTI >0"
y* = (0, 5/4, 1/4, 0, 0)
x = (15/4)/(3/2) è ottima per P
y* = (0, 5/4, 1/4, 0, 0) è ottima per P
FINE
DIMOSTRAZIONI
- wh è una direzione di crescita per la funz. obiettivo CTx, nel punto x̄
- x(σ) = x̄ + σ wh, σ>0
- CTx(σ) = CT(x̄+σwh)
- = CTx̄ + σ CTwh = CTx̄ + σ (-y̅h) > CTx̅
- σ>0
12/10/2014
DETERMINAZIONE DEL PASSO σ
- Deve essere A(x̄ + σwh) ≤ b → Aj(x̄+σwh) ≤ bj;
- ∀ i ∈ B Aiwh ≤ 0
- ∀ i t.c. Aiwh ≤ 0 si ha Aix̄+σAiwh ≤ bi
- ∀ σ ≥ 0
- Allora sia Ai̅wh < 0, la disuguaglianza Ai̅x̅+σAi̅wh ≤ bi̅
- porta alla condizione: σ ≤ (bi̅ - Ai̅x̅)/Ai̅wh
- ∀ wh > 0, i̅ ∈ N
x̅ = (x̅, 0)
A̅_N x̅ = (1 0) (1 Δ 2) (1 1) (x) (0) = (x/x x/x) ≤ (0) (13/9) OTTIMO
(y̅^T x̅) ≡ ottimo per (p̅) x̅ // (p̅)
IL PROBLEMA RIDOTTO ASSOCIATO A (p̅)
(min y^T b y^T a_B = c^T y^T a̅_N = c_N y^T ≥ 0 y^T a̅_B = (c_T - y_T a_N) (a̅_B^T a_U)̅ = c^T y^T a̅_B = c_T - y_T a_N ~ y^T_B = c_T a̅_B^-1 a_N a̅_B^-1
y^T_B a̅_B + y^T_N a̅_N = c^T --- a^R (min [c_T a̅_B^-1) b_B + y^T (b_B - a_N a̅_B^-1 b_B)] c_T a̅_B^-1 a_N a̅_B^-1 ≥ 0 x^T_N ≥ 0
CI CHIEDIAMO SE y̅_N^T > 0 È OTTIMO PER q_R E OSSERVO CHE y̅_T È ACCETTABILE PER q̅_R E INOLTRE SE RISULTA b_N - A_N a_B^-1 b_B ≥ 0 ALLORA ŷ_R y̅ > 0 È OTTIMO PER q_R
b_N - A_N a̅_B^-1 b_B ≥ 0 ~ b_N - A_N x̅ ≥ 0
SICCOME a_K x̅ > b_K ALLORA LA DIREZIONE
e_j := (0,...,0,1,0,...,0) È UNA DIREZIONE DI DISCESA PER LA FUNZIONE OBIETTIVO DI q_R
E IN CORRISPONDENZA DELL'INDICE K
e CONSIDERATE y̅^T t (Ø) = y̅^T_N + Ø e_N = Ø e_N
LA FUNZIONE OBIETTIVO DI q̅_R VALE: c_T a̅_B^-1 b_B + Ø e_N (b_N a_U a_B^-1 b_B) = ...= c_T a̅_B^-1 b_B + Ø (b_K - a_K x̅) < c^T a̅_B^-1 b_B se Ø > 0
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
