La programmazione lineareLa programmazione lineare

E’ una tecnica matematica usata E’ una tecnica matematica usata nella pianificazione amministrativa nella pianificazione amministrativa

ed economica per trovare il ed economica per trovare il massimo o il minimo di funzioni massimo o il minimo di funzioni

lineari soggette a “vincoli” lineari soggette a “vincoli”

Il ricavo (o il costo) assume la forma di Il ricavo (o il costo) assume la forma di

funzione, che viene indicata spesso funzione, che viene indicata spesso

con con zz e viene detta e viene detta

“ “funzione obiettivofunzione obiettivo”.”.

E s e m p i o:E s e m p i o:

Un’ azienda produce Un’ azienda produce

quotidianamente una quantità quotidianamente una quantità xx di di

divani e una quantità divani e una quantità yy di poltrone di poltrone

x

y

N° di divani prodotti

N° di poltrone prodotte

L’ azienda ricava L’ azienda ricava € € 600600 per ogni per ogni

divano venduto e divano venduto e € € 400400 per ogni per ogni

poltrona venduta.poltrona venduta.

Il Il ricavoricavo assume la forma di assume la forma di

funzione:funzione:

ZZ = 600 X + 400 y = 600 X + 400 y

Il Il ricavoricavo assume la forma di assume la forma di

funzione:funzione:

ZZ = 600 X + 400 y = 600 X + 400 y

Quanto vale il massimo ricavo per l’ azienda ?

Al variare di Al variare di xx e di e di yy, ovvero del , ovvero del numero di articoli prodotti dell’ numero di articoli prodotti dell’ uno e dell’ altro tipo, varia il uno e dell’ altro tipo, varia il ricavo giornaliero. ricavo giornaliero.

La funzione La funzione zz = 600 = 600 xx + 400 + 400 yy nello spazio viene rappresentata nello spazio viene rappresentata con un piano. con un piano.

Da un punto di vista matematico, Da un punto di vista matematico, questa funzione ricavo non ha questa funzione ricavo non ha limitazioni …limitazioni …

Da un punto di vista pratico ci rendiamo conto che x ed y non possono assumere valori qualsiasi, ma devono obbedire a dei “vincoli”

I vincoli (di produzione) possono I vincoli (di produzione) possono essere dovuti a:essere dovuti a:

Disponibilità di materialeDisponibilità di materialeOre lavorativeOre lavorativeCapienza del magazzinoCapienza del magazzino

L’ obiettivo del problema è trovare il valore di produzione che rende massimo il ricavo, tenendo conto dei vincoli.

L’ obiettivo del problema è trovare il valore di produzione che rende massimo il ricavo, tenendo conto dei vincoli.

Aggiungiamo dei Aggiungiamo dei vincoli al problema …vincoli al problema …

1° VINCOLO:1° VINCOLO:

Ogni divano richiede 2 Ogni divano richiede 2 ore di lavoro, mentre ogni ore di lavoro, mentre ogni poltrona richiede 1 ora. poltrona richiede 1 ora.

In azienda le ore In azienda le ore lavorative sono 8 al lavorative sono 8 al

giorno.giorno.

2° VINCOLO:2° VINCOLO:

Il salottificio può produrre Il salottificio può produrre giornalmente al massimo giornalmente al massimo

6 oggetti6 oggetti

I vincoli si traducono I vincoli si traducono in in DISEQUAZIONIDISEQUAZIONI

ore lavorative ore lavorative ≤≤ 8 8

Bisogna esprimere le ore Bisogna esprimere le ore lavorative in funzione di lavorative in funzione di xx e e yy

ore lavorative ore lavorative ≤≤ 8 8

ore lavorative ore lavorative ≤≤ 8 8

2 2 xx + + y y ≤≤ 88

n° di oggetti prodotti n° di oggetti prodotti ≤≤ 66

n° di oggetti prodotti n° di oggetti prodotti ≤≤ 66

Bisogna esprimere anche Bisogna esprimere anche questo vincolo in funzione questo vincolo in funzione

di di xx e e yy

n° di oggetti prodotti n° di oggetti prodotti ≤≤ 66

xx + + y y ≤≤ 6 6

Oltre ai vincoli di produzione Oltre ai vincoli di produzione esistono i esistono i vincoli di segnovincoli di segno::

Le quantità prodotte Le quantità prodotte xx ed ed yy non non possono essere negative:possono essere negative:

xx ≥ 0≥ 0

yy ≥ 0 ≥ 0

Oltre ai vincoli di produzione Oltre ai vincoli di produzione esistono i esistono i vincoli di segnovincoli di segno::

Le quantità prodotte Le quantità prodotte xx ed ed yy non non possono essere negative:possono essere negative:

xx ≥ 0≥ 0

yy ≥ 0 ≥ 03° VINCOLO

R I E P I L O G A N D O:Il problema consiste nel trovare il massimo della funzione lineare:

R I E P I L O G A N D O:Il problema consiste nel trovare il massimo della funzione lineare:

zz = 600 = 600 xx + 400 + 400 yy

R I E P I L O G A N D O:Il problema consiste nel trovare il massimo della funzione lineare:

zz = 600 = 600 xx + 400 + 400 yy

Soggetta al sistema di vincoli:

R I E P I L O G A N D O:Il problema consiste nel trovare il massimo della funzione lineare:

zz = 600 = 600 xx + 400 + 400 yy

Soggetta al sistema di vincoli:

xx ≥ 0 ≥ 0yy ≥ 0 ≥ 0

2 2 xx + + y y ≤≤ 8 8 xx + + y y ≤≤ 6 6

G E N E R A L I Z Z A N D O …G E N E R A L I Z Z A N D O …

Si parla di Si parla di PROGRAMMAZIONE LINEAREPROGRAMMAZIONE LINEARE quando quando si e' in presenza di:si e' in presenza di:

  

G E N E R A L I Z Z A N D O …G E N E R A L I Z Z A N D O …

Si parla di Si parla di PROGRAMMAZIONE LINEAREPROGRAMMAZIONE LINEARE quando quando si e' in presenza di:si e' in presenza di:

  a)a) una FUNZIONE LINEARE di 2 o più VARIABILI una FUNZIONE LINEARE di 2 o più VARIABILI INDIPENDENTI che si deve MASSIMIZZARE (se si INDIPENDENTI che si deve MASSIMIZZARE (se si tratta di FUNZIONE RICAVO o PROFITTO) oppure tratta di FUNZIONE RICAVO o PROFITTO) oppure MINIMIZZARE (se si tratta di FUNZIONE COSTI);MINIMIZZARE (se si tratta di FUNZIONE COSTI);

  

G E N E R A L I Z Z A N D O …G E N E R A L I Z Z A N D O …

Si parla di Si parla di PROGRAMMAZIONE LINEAREPROGRAMMAZIONE LINEARE quando quando si e' in presenza di:si e' in presenza di:

  a)a) una FUNZIONE LINEARE di 2 o più VARIABILI una FUNZIONE LINEARE di 2 o più VARIABILI INDIPENDENTI che si deve MASSIMIZZARE (se si INDIPENDENTI che si deve MASSIMIZZARE (se si tratta di FUNZIONE RICAVO o PROFITTO) oppure tratta di FUNZIONE RICAVO o PROFITTO) oppure MINIMIZZARE (se si tratta di FUNZIONE COSTI);MINIMIZZARE (se si tratta di FUNZIONE COSTI);

    b)b) un INSIEME DI VINCOLI dati da EQUAZIONI o un INSIEME DI VINCOLI dati da EQUAZIONI o DISEQUAZIONI LINEARI A 2 O PIU' VARIABILI;DISEQUAZIONI LINEARI A 2 O PIU' VARIABILI;

  

G E N E R A L I Z Z A N D O …G E N E R A L I Z Z A N D O …

Si parla di Si parla di PROGRAMMAZIONE LINEAREPROGRAMMAZIONE LINEARE quando quando si e' in presenza di:si e' in presenza di:

  a)a) una FUNZIONE LINEARE di 2 o più VARIABILI una FUNZIONE LINEARE di 2 o più VARIABILI INDIPENDENTI che si deve MASSIMIZZARE (se si INDIPENDENTI che si deve MASSIMIZZARE (se si tratta di FUNZIONE RICAVO o PROFITTO) oppure tratta di FUNZIONE RICAVO o PROFITTO) oppure MINIMIZZARE (se si tratta di FUNZIONE COSTI);MINIMIZZARE (se si tratta di FUNZIONE COSTI);

    b)b) un INSIEME DI VINCOLI dati da EQUAZIONI o un INSIEME DI VINCOLI dati da EQUAZIONI o DISEQUAZIONI LINEARI A 2 O PIU' VARIABILI;DISEQUAZIONI LINEARI A 2 O PIU' VARIABILI;

  c)c) un INSIEME DI VINCOLI DI SEGNO, di norma un INSIEME DI VINCOLI DI SEGNO, di norma POSITIVO, che esprimono la NON-NEGATIVITA' POSITIVO, che esprimono la NON-NEGATIVITA'

delle VARIABILI presenti, essendo esse delle VARIABILI presenti, essendo esse GRANDEZZE ECONOMICHE.GRANDEZZE ECONOMICHE.

Risoluzione del problemaRisoluzione del problema

Si parte con la risoluzione per via grafica del Si parte con la risoluzione per via grafica del sistema di disequazioni:sistema di disequazioni:

xx ≥ 0 ≥ 0yy ≥ 0 ≥ 0

2 2 xx + + y y ≤≤ 8 8 xx + + y y ≤≤ 6 6

Risoluzione del problemaRisoluzione del problema

Si parte con la risoluzione per via grafica del Si parte con la risoluzione per via grafica del sistema di disequazioni:sistema di disequazioni:

xx ≥ 0 ≥ 0yy ≥ 0 ≥ 0

2 2 xx + + y y ≤≤ 8 8 xx + + y y ≤≤ 6 6

xx ≥ 0 ≥ 0yy ≥ 0 ≥ 0

y y ≤≤ - 2 - 2 xx + 8 + 8 y y ≤≤ - - xx + 6 + 6

Risoluzione del problemaRisoluzione del problema

Si rappresentano le rette corrispondenti alle Si rappresentano le rette corrispondenti alle equazioni associate:equazioni associate:

xx ≥ 0 ≥ 0yy ≥ 0 ≥ 0

y y ≤≤ - 2 - 2 xx + 8 + 8 y y ≤≤ - - xx + 6 + 6

xx = 0 = 0yy = 0 = 0

y y = - 2 = - 2 xx + 8 + 8 y y == - - xx + 6 + 6

0 1 2 3 4 5 6 7 8 9

8

7

6

5

4

3

2

1

0x

y

0 1 2 3 4 5 6 7 8 9

8

7

6

5

4

3

2

1

0x

y

y y = - 2 = - 2 xx + 8 + 8

0 1 2 3 4 5 6 7 8 9

8

7

6

5

4

3

2

1

0x

y

y y = - 2 = - 2 xx + 8 + 8

y y == - - xx + 6 + 6

0 1 2 3 4 5 6 7 8 9

8

7

6

5

4

3

2

1

0x

y

y y = - 2 = - 2 xx + 8 + 8

y y == - - xx + 6 + 6

xx = 0 = 0

0 1 2 3 4 5 6 7 8 9

8

7

6

5

4

3

2

1

0x

y

y y = - 2 = - 2 xx + 8 + 8

y y == - - xx + 6 + 6

yy = 0 = 0

xx = 0 = 0

0 1 2 3 4 5 6 7 8 9

8

7

6

5

4

3

2

1

0x

y

y y ≤≤ - 2 - 2 xx + 8 + 8

y y ≤≤ - - xx + 6 + 6

yy ≥≥ 0 0

xx ≥ ≥ 00

0 1 2 3 4 5 6 7 8 9

8

7

6

5

4

3

2

1

0x

y

y y ≤≤ - 2 - 2 xx + 8 + 8

y y ≤≤ - - xx + 6 + 6

yy ≥≥ 0 0

xx ≥≥ 0 0 REGIONE

AMMISSIBILE

0 1 2 3 4 5 6 7 8 9

8

7

6

5

4

3

2

1

0x

y

y y ≤≤ - 2 - 2 xx + 8 + 8

y y ≤≤ - - xx + 6 + 6

yy ≥≥ 0 0

xx ≥≥ 0 0 Il massimo della funzione z si trova su uno dei vertici del poligono

0 1 2 3 4 5 6 7 8 9

8

7

6

5

4

3

2

1

0x

y In questo caso il poligono è un quadrilatero

C(4; 0)

B(2; 4)

A(0; 6)

O(0; 0)

0 1 2 3 4 5 6 7 8 9

8

7

6

5

4

3

2

1

0x

y

A(0; 6)

B(2; 4)

C(4; 0)O(0; 0)

Teorema della programmazione lineare

0 1 2 3 4 5 6 7 8 9

8

7

6

5

4

3

2

1

0x

y

A(0; 6)

B(2; 4)

C(4; 0)O(0; 0)

ZA = 600 * 0 + 400 * 6 = 2.400

0 1 2 3 4 5 6 7 8 9

8

7

6

5

4

3

2

1

0x

y

A(0; 6)

B(2; 4)

C(4; 0)O(0; 0)

ZA = 600 * 0 + 400 * 6 = 2.400

ZB = 600 * 2 + 400 * 4 = 2.800

0 1 2 3 4 5 6 7 8 9

8

7

6

5

4

3

2

1

0x

y

A(0; 6)

B(2; 4)

C(4; 0)O(0; 0)

ZA = 600 * 0 + 400 * 6 = 2.400

ZB = 600 * 2 + 400 * 4 = 2.800

ZC = 600 * 4 + 400 * 0 = 2.400

0 1 2 3 4 5 6 7 8 9

8

7

6

5

4

3

2

1

0x

y

A(0; 6)

B(2; 4)

C(4; 0)O(0; 0)

ZA = 600 * 0 + 400 * 6 = 2.400

ZB = 600 * 2 + 400 * 4 = 2.800

ZC = 600 * 4 + 400 * 0 = 2.400

ZO = 600 * 0 + 400 * 0 = 0

0 1 2 3 4 5 6 7 8 9

8

7

6

5

4

3

2

1

0x

y

A(0; 6)

B(2; 4)

C(4; 0)O(0; 0)

ZA = 600 * 0 + 400 * 6 = 2.400

ZB = 600 * 2 + 400 * 4 = 2.800

ZC = 600 * 4 + 400 * 0 = 2.400

ZO = 600 * 0 + 400 * 0 = 0

0 1 2 3 4 5 6 7 8 9

8

7

6

5

4

3

2

1

0x

y

A(0; 6)

B(2; 4)

C(4; 0)O(0; 0)

ZA = 600 * 0 + 400 * 6 = 2.400

ZB = 600 * 2 + 400 * 4 = 2.800

ZC = 600 * 4 + 400 * 0 = 2.400

ZO = 600 * 0 + 400 * 0 = 0

Il massimo ricavo (€ 2.800) si ha con una produzione giornaliera di 2 divani e 4 poltrone.

Teorema della programmazione Teorema della programmazione linearelineare

Quando l’ insieme delle soluzioni Quando l’ insieme delle soluzioni ammissibili di un problema di ammissibili di un problema di programmazione lineare è un poligono programmazione lineare è un poligono convesso, allora la soluzione ottimale convesso, allora la soluzione ottimale (ossia il punto di massimo o di minimo (ossia il punto di massimo o di minimo della della funzione obiettivofunzione obiettivo), esiste sempre e ), esiste sempre e si trova in uno dei si trova in uno dei verticivertici del poligono. del poligono.