Ricerca operativa - Programmazione lineare intera

PROGRAMMAZIONE LINEARE INTERA

Un problema di PLI è un problema di PL in cui c'è un ulteriore vincolo le variabili _i di un problema nella forma

min c^Tx Ax ≥ b x ≥ 0 x ∈ Z ⁿ

devono essere intere. Con questo vincolo si possono modellare problemi che con la PL non si possono modellare (ad esempio la scelta (tra alternative)). Il valore ottimo della funzione obiettivo di un problema di PLI viene chiamato Z_ILI.

Possiamo distinguere tra problemi di

• PLI puri
• PL 0-1 (o binari)
• PLI misti

Esempio (PLI mista) Supponiamo di avere una compagnia di trasporti e che questa compagnia abbia veicoli di vario genere, ogni veicolo richiede delle risorse, che pos sono essere di tipo materiale (olio, carburante), ma anche risorse umane (autisti). Un problema potrebbe essere quello di soddisfare le richieste di tutti i clienti ottimizzando i costi. In questo problema, alcune variab li possono assumere anche valori non interi, altre no.

Esempio (PLI 0-1) Le variabili binarie di solito rappresentano valori di tipo 'SI/NO', ad esempio se in un incrocio c'è un semaforo acceso, no. Lo 1 significa 'Si' lo 0 'No'.

Esempio (PLI pura) Un esempio di PLI pura è quello in cui dobbiamo produrre certe quantità di un certo prodotto (ad esempio automobili), quantità che possano essere solo intere (82,3 automobili?). Riscriviamo il nostro problema di PLT: min c^Tx Ax ≥ b x ≥ 0 intere I vincoli Ax ≥ b individuano un poliedro...

Le soluzioni possono essere solo:

Il numero delle soluzioni ammissibili è finito, quindi per trovare una soluzione ottima potremmo semplicemente enumerare tutte le soluzioni e scegliere quella col valore migliore della funzione obiettivo. Nella pratica questo non si può fare, vediamo perché. Consideriamo un problema di PL 0-1:

x ∈ {0,1}ⁿ

enumeriamoli:

• x⁽¹⁾ = [0,0,...,0]^T
• x⁽²⁾ = [1,0,...,0]^T
• x⁽ⁿ⁾ = [1,0,...,1]^T

In tutto sono 2ⁿ vettori; per ciascuno di questi vettori devo valutare l'ammissibilità e della funzione obiettivo. Il problema è proprio quel 2ⁿ. Supponiamo di avere un x per che in un secondo riesca a valutare l'ammissibilità di n=10⁶ vettori (2²⁰).

È assolutamente inaccettabile spendere tutto questo tempo per le enumerazioni. Anche avendo a disposizione una potenza di calcolo maggiore, il discorso non cambia. Possiamo esaminare 2³⁰ vettori in un secondo:

Questo approccio è assolutamente impraticabile per problemi di dimensioni realistiche.

12.10.2020

Lezione 2

Esempi di formulazioni

Il primo esempio è il problema noto come Knapsack. Com' è definito?

Abbiamo un contenitore con una certa capacità B. n oggetti. Per ogni oggetto sono noti 2 valori: un profitto p_i ed un peso w_i. Il problema consiste nel selezionare quegli sottoinsiemi di oggetti da inserire nel contenitore che non ne violi la capacità e che abbia massimo profitto. Di solito si assume che Σp_i= B (altrimenti non avremmo niente da ottimizzare) e si assume anche che w_i ≤ B. Vi: come formuliamo il nostro problema? La prima cosa da fare è capire qual è la decisione da prendere, e scegliere quindi le variabili decisionali. Quando c'è qualcosa da selezionare le variabili sono binarie:

• 1 se l'oggetto e selezionato
• 0 altrimenti

i=1,...,n

Quanto alla funzione obbiettivo, vogliamo un profitto massimo:

ⁿΣ_i=1 P_ix

con p_i profitto dell'oggetto i-esimo. Vogliamo anche che:

ⁿΣ_i=1 W_ix_i≤B

x_i∈{0,1}

Come cambia la formulazione se invece di avere un oggetto di ogni tipo ne ho tanti? Supponiamo di dover caricare un camion e di avere tre tipi di oggetti:

1. r₁ ... w₁
2. r₂ ... w₂
3. r_n ... w_n

#n copie di ogni oggetto illimitato

Non devo stabilire se un oggetto viene selezionato o meno, ma quante copie prendere di ciascun oggetto. Questo problema viene chiamato Knapsack intero, e l'unica cosa che cambia sono le variabili:

x_i# copie selezionate di ciascun oggetto

La formulazione è identica

ⁿΣ_i=1 P_ix_i (massimizzare il profitto) ⁿΣ_i=1 W_ix_i (restrizione sulla capacità)

x_i≥0, x_i intero

Modellazione PLI — casi standard

Limitazioni inferiori/superiori

Supponiamo di avere una variabile x che rappresenti una quantità da produrre e che i vincoli del problema mi impongano che x non si produca affatto o che sia compresa in un certo intervallo [N_min, N_max]. Quindi:

x ∈ {0} ∪ [N_min, N_max]

Dobbiamo trovare un modo per scrivere questa relazione con vincoli lineari. Per fare questo utilizziamo una variabile ausiliaria (la utilizziamo solo per rappresentare quel vincolo, e non sarà parte del problema) binaria:

cioè:

y = {    0   se x ∈ [N_min, N_max]    1   altrimenti

Per ogni vincolo ne scriviamo due:

x ≤ N_maxy x ≥ N_miny

Questi due vincoli dicono che se y = 0 allora x = 0, e se y = 1 allora N_min ≤ x ≤ N_max

Questo caso è molto simile a quello dei costi fissi di attivazione.

Costi fissi di attivazione

Supponiamo di voler produrre un certo bene, e come prima o non lo produciamo o ne produciamo una certa quantità. Per iniziare la produzione supponiamo di avere un costo fisso, c_f, che x rappresenti la quantità di questo bene che deve essere prodotto. Oltre al costo fisso abbiamo un costo unitario pari a c. Possiamo quindi assumere di avere una funzione di costo che ha questo aspetto:

{ 0                   se x=0(f(x) = {(c_f + cx    se x>0

Graficamente le funzioni di costo |f(x) Supponiamo di voler minimizzare f₁(x), ma aggiungiamo una variabile d da minimizzare. f₁(x) può essere tutta la funzione obiettivo o solo una parte. Introduciamo una variabile ausiliaria y che vale:

y = { 1          se x > 0        0          altrimenti (x = 0)

19.10.2010

Lezione 4

Formulato come problema di PL:

1. min f( c(x) )
2. max f( c(x) )

Sia f( c(x) ) una funzione lineare.

Dobbiamo minimizzare il modulo di f( c(x) ), e possiamo osservare che:

• |f( c(x) )| = max { f( c(x) ), -f( c(x) ) }

Per modellare la minimizzazione del modulo introduciamo una variabile ausiliaria z, e dobbiamo fare in modo che:

• z ≥ f( c(x) )
• z ≥ -f( c(x) )

In generale se vogliamo minimizzare il massimo tra più scelte usiamo z e chiediamo che z sia ≥ di ciascuna di queste scelte.

max { |f( c(x) )|

• f( c(x) ) = max { g( c(x) ), r( c(x) ) }

con: z ≥ g( c(x) ) z ≥ r( c(x) )

con g non rappresenterebbe il modulo.

Possiamo scrivere:

• f( c(x) ) se x ≥ 0
• z |f( c(x) )| = {-f( c(x)) se x