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.
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
Alloc. Risorse Scarse
Disponiamo di alcuni dati, ci viene chiesto di massimizzare il rendimento, ovvero, il nostro obiettivo.
Ad esempio:
- Prodotti:
- A venduto a 2,5 €/l
- B " 1,8 €/l
- Consorge:
- Mix frutta 350 kg
- Ricalcolo 420 kg
- Il volume 80 l
Matrice Disponibilità
-
M
- (A) (LR) 3 kg 2,2 kg
- f 0,2 kg 0,3 kg
- l 0,03 l 0,01 l
Occorre poi introdurre delle variabili di decisione per indicare quanto di A e quanto di B viene prodotto. I valori delle variabili rappresentano i punti ammissibili di Ω
- x = xA/xB > 0
lo f.o. → max 2,5 xA + 1,8 xB
Vincoli per Risorse
- 3 xA + 2,2 xB ≤ 350
- 0,2 xA + 0,3 xB ≤ 420
Tutto ciò si può anche 0,03 xA + 0,01 xB ≤ 80
mass pTx H × x ≤ D x ≥ 0
oppure
unit (-pTx) H × x ≥ D x ≥ 0
m = # di variabili di decisione che si devono introdurre
Problema di KNAPSACK
Detti:
- capacità: b ∈ R
- oggetti: 1, 2, 3, ..., m
- ingombro: a1, a2, a3, ..., am
- valore: c1, c2, c3, ..., cm
Occorre usare delle variabili di decisione binarie:
- xj ∈ {0, 1}
- 1 ≡ "Inserisco l'oggetto j"
- 0 ≡ "Non inserisco l'oggetto j"
Oggetti che inserisco → ∑j=1n ajxj ≤ b
e il loro ingombro
Esempio: b=10
Per fari ciò si impostano delle variabili binarie:
- 1 se (u,v) ∈ P ?
- 0 se (u,v) ∉ P
f.o. min ∑ Cuv xuv(uv)∈A
Inoltre, ogni arco che esce da S va bene purché del tipo (s,u)
∑ x(s,u) = 1
(s,u)∈A
Il che equivale che ENTRA in t va pure purché del tipo (u,t)
∑ x(u,t) = 1
(u,t)∈A
Inoltre, per un generico vertice, la caratteristica che ci permette di essere scelto come eventuale parte del percorso è quella che il numero di archi che vi entrano deve essere uguale al numero di archi che vi escono.
∑ xuv = ∑ xvu ∀ v ∈ V\{s,t}
(uv)∈A (vu)∈A
Pigeonhole principle
Se abbiamo n oggetti e k scatole in cui inserirli, con n > k, si ha che una scatola conterrà almeno ⌈n/k⌉ oggetti
Per esempio, se ho 150 persone e 12 mesi in cui potrebbero essere nate, ci sono almeno 13 persone nate nello stesso mese ⇒ ⌈150/12⌉ = ⌈12,50⌉ = 13
Dimostrazione (per assurdo) Si supponga di avere n oggetti e k scatole, mettendo in ognuna di più ⌈n/k⌉-1 oggetti. Dato che ⌈n/k⌉ < n/k+1 vale sempre si ha:
Dunque: Possiamo costruire tutte e sole le r-permutazioni di X a partire dalle r-combinazioni con come segue: per ogni r-combinazione che dobbiamo considerare le permutazioni in tutti i modi possibili gli elementi che la formano. In questo modo ogni r-combinazione verrà usata r! r-permute volte dunque:
P(n,r) = r! . C(n,r)
Se no C(n,n-r) ciò è uguale a C(n,n,r) perchè il numero diverso di combinazioni di elementi è uguale al numero di quelle degli (n-r) oggetti da scartare. Poi si ha, per definizione,
C(0,0) = 1
Identità di Pascal
Siano n e r due interi con n ≥ r. Vale la relazione:
C(n+1, r) = C(n, r-1) + C(n, r)
Dunque: Sia “a” un elemento di X e continuiamo sempre a mantenere la r-combinazione che lo contemgono quelle che non le contengano. Se posso scivi in numero poi nei diversi modi per scegliere per r-1 elementi da X{a} e le accordo suco quel essi in numero poi nello scegliere il più v elementi di X{a}
Soglia
4
- 12, 6 1/4, 1/3
- -2
- 1/2, -1/3, x3
→9=2+6-1/3x1, 1/3x, 6+1/3x3 →7 - 2, 2/3x + 2+ 3/12x →7=2- 1/3 x1+ 1/a x3
u⁺ = (a, 6, 1) = (-1/a, 9)
ci = 1 - (-(1/a) 9) = 1 - (-31/3) = 1/2
- C3 = 0 - (-1/a 0) = 0 - (-1/a) = 1/a )
Dualità di Programmazione Lineare
Se un problema "primitivo" ha bene o al minimo corrisposto
un problema "duale" in forma di massimo ed entram
lo stesso valore ottimo devono la d.o.
Ad esempio, potremmo avere un min
→
min cT x xe F =? = max fo} cT x ≤ c se ∀ x ∈ F?
Def
Dati un intervallo X, fin una dirigienza generaleso
CT x ≤ c definizione da quei e x ∈ X
si dira volerda per X
definire è la coppia (Co, C1) ∈ R25 che k co che la se de e
ripiagagna cT x ≤ c, velut valido per P. { x > 0}
definizione un sempre :
- Per esempio :
- 3x1 + 2x3 - x3
- = -5
- Ax = b, x> 0
- x3+ 2x2 + x3
- x/a
- =6
Si evoli ottenere una coppia (co , c1) per cui:
cT x - c2 x + c2 + (c3 x) + co veltrà valido per P per
pello scrimuendo la dire e e Cliente prelievemo
di due valari constanti u1 e u2 elementu:
(3q1 - a,2) x1 x2 ((a12 f2) +
= 5Aa1 + 6U2
è lussanato e ee u2 voglio e . 1 e 2 ottenmeno
in gestionomi del tipo . . .
Dualità
Per la risoluzione del duale
a) PRIMALE
- z = min ctx
- Ax ≥ b
- x ≥ 0
DUALE
- ω = max utb
- utA ≤ ct
- u ≥ 0
z ≥ ω dualità debole
b) PRIMALE (f.s.)
- z = min ctx
- Ax = b
- x ≥ 0
DUALE
- ω = max utb
- utA = ct
- u libero
z = ω dualità forte
Se...
PRIMALE
- ottimo finito
- valore di z
- illimitato
- vuoto
DUALE
- ottimo finito
- valore di ω = z
- vuoto
- illimitato
c) PRIMALE
- z' = max ctx
- Ax ≤ b
- x ≥ 0
DUALE
- ω' = min utb
- utA ≥ ct
- u ≥ 0
- ω = -ω'; ω = utb
- ω' = max ut(-b)
- ut(A) ≥ ct
- u > 0
z' = z
z ≥ ω , ω' ≥ z'
Seguito 5 bis
Knapsack problem
primate:
- u.a.x 21x1 + 16x2 + 15x3 + 2x4
- a1x1 + 4x2 + 5x3 + 7x4 ≤ 10
- 0 ≤ xj ≤ d j = 1...n
x* = (1, 1, 2/5, 0)
x1 + x2 / 10 elementi che entrano nello zaino
il 3º elemento posso prenderlo solo
per i 2/5 elementi eccedenti dello zaino
q.1 + a.1 + 5x2 + 7x4 = 10 => f.o. ottimo = 43
[21.1 + 16.1 + 15. 2/5 + 2.0]
duale : uso vj exf => u duale
min (10 21
xi* > 0 porta il primo uncaco col essere coll’ottimo verificato
che ip fumetto quello il secondo per il zenpunzo:
ta divisione mi riempiego stiamo, v2 è già nuova devo
un su zella mullo per essere impodi co ten > uia
(cai ottimo)
5u1 = 15 => u1* = 3
Per ogni uncaco > I) 4.3 + v1' - 21 => v1'* = 9
II) 4.3 + u2' = 16 => u2'* = 4 III) 5u1* = 15 => u1* = 3 => v3* = 0
IV) 7u1 + v4 = 2 => 7.3 + v4 = 2 => v4* = 0?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
