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
Formulazione Generale
u(x) € x = ∑ ci • xi
s.t. Ax ≤ b
x ≥ 0 1. intero
c=(cl, ..., cu)
A=[mxu]
Soluzione
Soluzione ammissibile se rispetta tutti i vincoli.
Soluzione ottima se tra tutte le soluzioni ammissibili massimizza la funzione obiettivo.
Fa parte della programmazione lineare intera la programmazione lineare binaria.
Tutte le volte che dobbiamo e possiamo scegliere variabili binarie
xi = { 1 se prendo l’oggetto i 0 altrimenti }
Per indicare la presenza di variabili binarie uso le seguenti notazioni :
x ∈ {0,1}n
oppure
x ≥ 0 e x ≤ 1 intero
Knapsack (zaino) Problema P2B
Dato
n oggetti caratterizzati da un peso wω i ∀i = 1,... , n e un utilità ui;
esiste una capacità B ≥ 0
Trovare una soluzione di oggetti in modo tale che il peso totale degli
oggetti scelti non superi B e l’utilità totale sia massima.
J obiettivo
Formulazione
max Σi=1n ui xi
s.t. Σi=1n wi xi ≤ B
xi ≥ 0
xi ≤ 1
xi ∈ {0,1}
Knapsack multidimensionale
- peso tot oggetti ∈ S ≤ B
- volume tot oggetti ∈ S ≤ V
Independent Set
Dato grafo G = (V, E)
Trovare un sottoinsieme S ⊂ V
Tale che nessuna coppia di nodi di S sia connessa da un arco.
|S| sia il max
xi = 1 se vi ∈ S
xi = 0 se vi ∉ S ∀ vi ∈ V
Formulazione
max z = ∑ xi
S.T.
- x1 + x2 ≤ 1
- x1 + x3 ≤ 1
- x2 + x3 ≤ 1
- x4 + x5 ≤ 1
- x3 + x4 ≤ 1
- x1 + x5 ≤ 1 n = 5
- x ∈ {0, 1}
Se la versione cardinalità è quella posta basta aggiungere i pesi wi
- yi = 1 se vi ∉ S
- x scalzo yi = 1 se vi ∈ S
(1 - y1) + (1 - y2) + (1 - y3) + (1 - y4) + (1 - y5) + (1 - y6) =
Formulazione
max w = ∑ (1 - yi)
(1 - yi) + (1 - yj) ≤ 1 ∀ (vi, vj) ∈ E
- yi ∈ {0, 1} i = 1,...,n
Si semplifica con
yi + yj ≥ 1
Problemi 82.5
Knapsack Intero
Dati u tipi oggetti ciascuno in molteplicità uj ≥ 0 j = 1,...,u e di peso wj ≥ 0 j = 1,...,u e di utilità uj ≥ 0 j = 1,...,u
Capacità B ≥ 0
Trovan: quanti tipi di oggetti prendere e quanti
Tale che:
- il peso complessivo non mai ecceda B
- l'utilità complessiva sia massima
Formulazione
max z = Σ yj xj
s.t.
- Σ wj xj ≤ B
- xj ≥ 0 e intera j = 1,...,u
- xj ≤ uj j = 1,...,u
Es.
u = 3
(μ1, μ2, μ3) = (2, 5, 3)
(w1, w2, w3) = (1.5, 2.3, 1.4)
B = 15.8
(u1, u2, u3) = (2, 3, 3)
max z = 2x₁ + 5x₂ + 3x₃
s.t.
- 1.5x₁ + 2.3x₂ + 1.4x₃ < 15.8
- x₁ ≥ 0
- x₂ ≤ 2
- x₂ ≤ 3
- x₃ ≤ 3
Se dai calcolo # max di oggetti di tipo s lo xj quello
Xj = ⌊ B / ... ⌋
Immaginiamo di avere un problema con le seguenti formulazioni
max z = c
X = A ∪ B ∪ C
FORMULAZIONE
A
ya =
B
C
χ1, χ2 ≥ 0
ya, yb, yc ∈ {0, 1}
ya yb yc
unica configurazione problema
∈
ya + yb + (1 - yc) = 3
Per questo motivo aggiungo il seguente vincolo
(1 - ya) + yb + (1 - yc) ≤ 3
max z = c
X
A
B
C
VINCOLI DI PRECEDENZA
1) Fra due esecuzioni j3 > j3
2) Fra due procedimenti j3 > j3
Si associa un grafo orientato con n nodi e un arco orientato (Ve, Vc) se ji -> jk
W=4
t3 + ß3 < t4
Ogni vincolo di precedenza ci autorizza ad eliminare la corrispondente coppia di vincoli di non sovrapposizione
Altri vincoli particolari di precedenza
3) Il lavoro j2 deve iniziare non appena j1 ha terminatot3----------t1, t1 + p1Vincolo: t3 = t1 + p1
-> nello schedulatore ci autorizza ad eliminare la coppia di vincoli di non sovrapposizione di (1,3)
• j3 deve iniziare almeno 5 unità dopo la fine di j2
t3 = t2 + p2 + 5
Problemi di Ottimizzazione Combinatoria
Formulazione Generale
max
min cT x
s.t. Ax ≤ b
xi ∈ {0, 1}
Definizione Generale
Dati:
- un insieme A = {a1, a2, ..., an} di n elementi
- un vettore c = {c1, c2, ..., cn} di costi
- una famiglia ℱ di soluzioni ammissibili di A
Trovare un sottinsieme X ∈ ℱ
f in modo tale che venga ottimizzata la f. o. (dato)
Famiglia di un insieme di soluzioni di A
ℱ = { {a1, a5, a7}, {a2, a9}, {a3, a5, a7}, ... }
x vettore incidenza
xi ∈ {0, 1}
Vincoli
ℱ1 = {sottinsiemi di A composti da 3 elementi}
max z = ∑i=1n ci xi
s.t. ∑i=1n xi = 3
xi ∈ {0, 1}, i = 1, ..., n
ℱ2 = {sottinsiemi di A con esattamente 4 elementi}
∑i=1n (1-xi) = 4
∑i=1u xi = n - 4
N = 6
Il matching è un set packing ma non vale il viceversa, se a ha 1 con b "ij" per colonna allora il set packing è un matching
Es di Set Partitioning
min z = C1X1 + ... + C8X8
- X1 + X4 + X5 = 1
- X2 + X5 + X6 + X8 = 1
- X1 + X3 + X6 + X7 = 1
- X3 + X4 + X7 = 1
- X4 + X6 = 1
- X2 + X5 = 1
Xi ≥ 0 i = 1,...,8
Min node cover su G
Dec G
Trovare un sottoinsieme X di nodi
tale che in ogni arco venga scelto > 1
|X| da min
Xi = 1 se Ni ∈ X i = 1,...,8
0 se Ni ∉ X
min z = ∑ Xi -> conta quanti X
s.t. (a1) X1 + X2 + X3 ≥ 1
(a2) X2 + X3 ≥ 1
(a3) X1 + X4 + X5 ≥ 1
(a4) X1 + X6 + X7 ≥ 1
(a5) X3 + X6 + X7 ≥ 1
(a6) X4 + X6 = 1
(a7) X2 + X5 = 1
X ∈ {0,1}
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
