Introduzione alla Programmazione Lineare Intera

Introduzione alla Programmazione Lineare Intera
Andrea Scozzari
a.a. 2013-2014
April 8, 2014
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
1 / 23
Programmazione Lineare Intera
Un problema di Programmazione Lineare Intera `e scritto nel modo
seguente:
zPLI = max c T x
Ax ≤ b
x ≥0
(1)
intero
dove zPLI rappresenta il valore ottimo della funzione obiettivo. Il problema
non `e pi`
u di programmazione lineare in quanto il vincolo di interezza pu`o
essere riscritto come:
sin(πxj ) = 0
Andrea Scozzari (a.a. 2013-2014)
j = 1, . . . , n
Introduzione alla Programmazione Lineare Intera
April 8, 2014
2 / 23
Programmazione Lineare Intera
L’insieme delle soluzioni ammissibili `e rappresentabile in R2 nel seguente
modo
I vertici del poliedro (tramme quello in corrispondenza dell’origine degli
assi) non sono a coordinate intere.
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
3 / 23
Programmazione Lineare Intera
Indichiamo con
P = {x ∈ Rn |Ax ≤ b, x ≥ 0}
il poliedro descritto dalle disequazioni del sistema del problema di PLI e
con Z n l’nsieme dei numeri interi, la regione ammissibile (discreta) del
problema `e indicata con:
X = P ∩ Zn
Ipotizziamo che P sia limitato e non vuoto.
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
4 / 23
Programmazione Lineare Intera
` possibile eliminare il vincolo di interezza rilassando il problema
E
zPL = max c T x
Ax ≤ b
(2)
x ≥0
Rilassamento Continuo del problema originale eliminando il vincolo di
interezza
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
5 / 23
Programmazione Lineare Intera
` dunque possibile risolvere il problema rilassato con l’algoritmo del
E
simplesso. Dall’ipotesi su P, si possono avere due casi:
1. la soluzione ottima di (2) `e a componenti intere, pertanto la soluzione
ottima zPL = zPLI
2. la soluzione ottima di (2) ha qualche componente frazionaria,
pertanto:
zPL = max{c T x : x ∈ P} ≥ max{c T x : x ∈ X }
zPL `e una limitazione superiore (upper bound) per il valore ottimo del
problema (1).
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
6 / 23
Programmazione Lineare Intera
L’idea di arrotondare opportunamente la soluzione ottima del problema
rilasciato non `e sempre buona!
Pu`
o capitare che arrotondando la soluzione ottima del rilassamento
continuo si ottenga una soluzione intera lontana da quella ottima
(addirittura non ammissibile, vedi Figura per un problema di massimo).
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
7 / 23
Programmazione Lineare Intera
Con riferimento ai problemi di PLI, il rilassamento continuo non garantisce
di ottenere soluzioni intere. Questo dipende dall’inclinazione della funzione
obiettivo e della direzione del gradiente.
` possibile ottenere una formulazione dove tutti i vertici siano interi?
E
Assumiamo esista un poliedro
ˆ = {x ∈ Rn |Ax
ˆ ≤ b,
ˆ x ≥ 0}
P
Tale che il suo rilassamento abbia tutti i vertici interi
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
8 / 23
Programmazione Lineare Intera
ˆ = {x ∈ Rn |Ax
ˆ ≤ b,
ˆ x ≥ 0} `e migliore della
La formulazione P
formulazione P perch´e risulta pi`
u stringente.
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
9 / 23
Programmazione Lineare Intera
ˆ = {x ∈ Rn |Ax
ˆ ≤ b,
ˆ x ≥ 0} `e una formulazione ideale
La formulazione P
se il suo rilassamento ha tutti vertici interi.
Definizione
Dato un insieme S ∈ Rn , si chiama involucro convesso (convex hull) di S il
pi`
u piccolo insieme convesso che contiene S e si indica con
conv (S)
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
10 / 23
Programmazione Lineare Intera
ˆ chiuso e limitato
L’involucro convesso di X `e dunque un poliedro P
(politopo) tale che
ˆ = {x ∈ Rn |Ax
ˆ ≤ b,
ˆ x ≥ 0} = conv (X )
P
e per il quale si ha
ˆ
max{c T x : x ∈ X } = max{c T x : x ∈ P}
ˆ e bˆ sono molto difficili
per qualsiasi vettore dei costi c. Le componenti A
da determinare e ci sono poche classi di problemi per cui la loro
formulazione lineare coincide con la formulazione ideale.
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
11 / 23
Programmazione Lineare Intera: Metodo dei Piani di Taglio
Il metodo consiste nel generare una serie di vincoli aggiuntivi detti Tagli
che abbiano la caratteristica di restringere la regione ammissibile senza
escludere soluzioni ammissibili intere.
Definizione
Dato un insieme di m vettori in Rn , v1 , . . . , vm , un vettore v `e combinazione lineare
dell’insieme dei vettori {v1 , . . . , vm }, se esistono m coefficienti reali λ1 , . . . , λm tali che
v = λ1 v1 + . . . + λm vm
Una combinazione lineare con coefficienti λi ≥ 0, i = 1, . . . , m, si dice combinazione
conica.
Una combinazione lineare con coefficienti λi , i = 1, . . . , m, tali che
m
P
λi = 1 si dice
i=1
combinazione affine.
Una combinazione lineare con coefficienti λi ≥ 0, i = 1, . . . , m, e tali che
m
P
λi = 1, si
i=1
dice combinazione covessa.
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
12 / 23
Programmazione Lineare Intera: Metodo dei Piani di Taglio
Sia dato un poliedro P = {x ∈ Rn |Ax ≤ b} ed una disequazione aT x ≤ α
Definizione
Una disequazione aT x ≤ α `e valida per P se e solo se
P ⊆ {x ∈ Rn |aT x ≤ α}
ossia se e solo se la disequazione `e soddisfatta da tutti i punti di P (i.e.,
da tutte le soluzioni ammissibili del problema).
Si dice anche che la disequazione aT x ≤ α `e implicata dal sistema Ax ≤ b.
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
13 / 23
Programmazione Lineare Intera: Metodo dei Piani di Taglio
Definizione
Una disequazione aT x ≤ α valida per P definisce una faccia F di P se
F = P ∩ {x ∈ Rn |aT x = α}
L’insieme {x ∈ Rn |aT x = α} `e detto iperpiano di supporto di F
Ogni faccia F di un poliedro P `e essa stessa un poliedro
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
14 / 23
Programmazione Lineare Intera: Metodo dei Piani di Taglio
Definizione
La dimensione dim(P) di un poliedro P `e data dal massimo numero di
vettori affinemente indipendenti appartenenti a P meno uno.
Definizione
Una faccia F tale che
dim(F ) = dim(P) − 1
`e detta faccia massimale o faccetta di P. Se dim(F ) = 0 allora la faccia F
`e un vertice di P.
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
15 / 23
Programmazione Lineare Intera: Metodo dei Piani di Taglio
Definizione
Date due disequazioni aT x ≤ α e q T x ≤ γ la prima disequazione domina
la seconda disequazione se esiste λ > 0 tale che
a = λq
e
α = λγ
Per cui
{x ∈ Rn |aT x ≤ α} ⊆ {x ∈ Rn |q T x ≤ γ}
Ossia l’insieme delle soluzioni della prima disequazione `e contenuto
nell’insieme delle soluzioni della seconda disequazione. Se vale
l’uguaglianza, allora i due insiemi sono equivalenti.
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
16 / 23
Programmazione Lineare Intera: Metodo dei Piani di Taglio
Dato un poliedro P = {x ∈ Rn |Ax ≤ b} una disequazione valida aT x ≤ α
pu`
o essere ottenuta come combinazione conica delle disequazioni del
sistema Ax ≤ b, ovvero:
u T Ax ≤ u T b
u≥0
Tale disequazione se aggiunta al sistema Ax ≤ b non modifica l’insieme
delle soluzioni ammissibili del problema.
Definizione
Una rapprsentazione del poliedro P attraverso un sistema di disequazioni
Ax ≤ b `e minimale se la rimozione di una qualsiasi disequazione del
¯ ≤ b¯ tale che
sistema produce un nuovo sistema Ax
ˆ ≤ b}
ˆ
P ⊂ {x ∈ Rn |Ax
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
17 / 23
Programmazione Lineare Intera: Metodo dei Piani di Taglio
Le definizioni precedenti evidenziano il fatto che la rappresentazione di un
poliedro P con disequazioni Ax ≤ b non `e univocamente determinata.
Tuttavia, nessuna disequazione di una rappresentazione minimale di P pu`o
essere dominata da una combinazione conica delle altre.
Teorema
Una rappresentazione del poliedro P ⊆ Rn con disequazioni Ax ≤ b di
dimensione n `e minimale se e solo se ciascuna disequazione del sistema
definisce una faccia massimale (faccetta) di P. Inoltre, ogni faccia
massimale F di P `e definita da una disequazione del sistema Ax ≤ b.
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
18 / 23
Esercizio
Bisogna gestire 3 fattorie la cui produzione `e limitata sia dalla superficie
utilizzabile che dalla quantit`a di litri di acqua per la irrigazione
Fattoria
1
2
3
Terreno utilizzabile in acri
400
600
300
Andrea Scozzari (a.a. 2013-2014)
Acqua disponibile per acro
1500
2000
900
Introduzione alla Programmazione Lineare Intera
April 8, 2014
19 / 23
Esercizio
Si vogliono piantare 3 raccolti A, B, C per i quali si hanno le seguenti
informazioni
Raccolto
A
B
C
Acri da utilizzare
700
800
300
Acqua per acro
5
4
3
Profitto atteso per acro
400
300
100
Si vuole inoltre che la percentuale della superficie utilizzabile in ogni
fattoria sia la stessa (carico di lavoro uniforme)
Problema: Quanto di ciascun raccolto deve essere piantato per
massimizzare il profitto
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
20 / 23
Modello
xij = numero di acri da coltivare della fattoria i riservati al raccolto j
Profitto totale
z = 400(x1A + x2A + x3A ) + 300(x1B + x2B + x3B ) + 100(x1C + x2C + x3C )
Limitazioni sulla disponibilit`a della superficie di ogni fattoria
x1A + x1B + x1C ≤ 400
x2A + x2B + x2C ≤ 600
x3A + x3B + x3C ≤ 300
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
21 / 23
Modello
Limitazioni sull’uso dell’acqua per ogni fattoria
5x1A + 4x1B + 3x1C ≤ 1500
5x2A + 4x2B + 3x2C ≤ 2000
5x3A + 4x3B + 3x3C ≤ 900
Limitazioni sull’utilizzo della superficie coltivabile per ciascun raccolto
x1A + x2A + x3A ≤ 700
x1B + x2B + x3B ≤ 800
x1C + x2C + x3C ≤ 300
Andrea Scozzari (a.a. 2013-2014)
Introduzione alla Programmazione Lineare Intera
April 8, 2014
22 / 23
Modello
Vincoli sul carico di lavoro
x1A +x1B +x1C
400
=
x2A +x2B +x2C
600
x2A +x2B +x2C
600
=
x3A +x3B +x3C
300
x1A +x1B +x1C
400
=
x3A +x3B +x3C
300
Dato che le prime due equazioni implicano la terza, questa si pu`o eliminare
dato che diventa ridondante.
Vincoli di non negativit`a
xij ≥ 0
Andrea Scozzari (a.a. 2013-2014)
i = A, B, C
j = 1, 2, 3
Introduzione alla Programmazione Lineare Intera
April 8, 2014
23 / 23

Download Report