Ricerca operativa - Programmazione lineare intera

PROGRAMMAZIONE LINEARE INTERA

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

min cXAx > bX > 0X ∈ ℤ

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

Possiamo distinguere tra problemi di:

• PLI pura
• PL 0-1 (o binaria)
• PLI mista

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 possono 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 variabili possono assumere anche valori non interi, altre no.

Esempio (PL 0-1)

Le variabili binarie di solito rappresentano valori di tipo sì/no; ad esempio, se in un incrocio c'è un poliziotto oppure no. 1 significa 'sì' 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 (8,2 automobili?)

Risciuviamo il nostro problema di PLI:

min cXAx > bX > 0X ∈ ℤ intere

I vincoli Ax > b individuano un poliedro, e il fatto X ∈ ℤ indica che

PROGRAMMAZIONE LINEARE INTERA

Un problema di PLI è un problema di PL in cui c’è un ulteriore vincolo: le

variabili _j di un problema nella forma

min c^T x

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 fra alternative).

Il valore ottimo della funzione obiettivo di un problema di PLI viene

chiamato Z_int.

Possiamo distinguere tra problemi di:

• PLI pura
• PL 0-1 (o binaria)
• PLI mista

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 variabi-

li possono assumere anche valori non interi, altre no.

Esempio (PL 0-1)

Le variabili binarie di solito rappresentano valori di tipo sì/no, ad

esempio se in un incrocio c’è un poliziotto oppure no. L’1 significa ‘sì’

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 possono essere

solo intere (82,3 automobili?)

Riscriviamo il nostro problema di PLI:

min c^Tx

Ax ≥ b

x ≥ 0 intere

I vincoli Ax ≥ b individuano un poliedro, e il fatto x ∈ _Z indica che

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 di valore migliore della funzione obiettivo. Nella pratica, questo non si può fare, vediamo perché. Consideriamo un problema di P.L. 0-1:

x ∈ ∗0,1&highast;ⁿ

enumeriamoli:

X⁽¹⁾ = [0,0,…,0]^T

X⁽²⁾ = [0,0,…,1]^T

X⁽³⁾ = […,1,0]^T

In tutto sono 2ⁿ vettori, per ciascuno di questi vettori devo valutare l'ammissibilità della funzione obiettivo. Il problema è proprio quel 2ⁿ. Supponiamo di avere un PC che in un secondo riesce a valutare l'ammissibilità di ~10⁹ vettori (~2³⁰).

| n | t (sec) |

| -- | ------- |

| 20 | 1 |

| 30 | 2¹⁰ ~ 17 min. |

| 40 | 2²⁰ ~ 12 h |

| 50 | 2³⁰ ~ 12 gg |

| 60 | 2⁴⁰ ~ 35 anni |

| 70 | 2⁵⁰ ~ 36 mila di miliardi di anni |

È 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!

| n | t (sec) |

| -- | ------- |

| 20 | 1 |

| 30 | 2¹⁰ ~ 5 giorni |

| 40 | 2²⁰ ~ (429 giorni) |

| 50 | 2³⁰ ~