Lezione n°5: Esercitazione

(1)

R. Cerulli – F. Carrabs

Lezioni di Ricerca Operativa

Corso di Laurea in Informatica ed Informatica Applicata Università di Salerno

Lezione n

°

5: Esercitazione

- Vettori linearmente dipendenti e indipendenti - Combinazioni lineari, coniche e convesse - Formulazioni

(2)

Vettori linearmente dipendenti e indipendenti

Verificare se i seguenti vettori:

x₁T_{=(4, 1, 2), x}

2T=(7, 3, 1) e x3T = (3, 2, 0)

sono linearmente indipendenti o dipendenti.

I vettori x₁, x₂, … , x_nsono LINEARMENTE INDIPENDENTI se l₁x₁+ l₂x₂+…+ l_nx_n= 0 implica che l₁= 0, l₂= 0, … , l_n= 0

÷

ø

ö

ç

è

æ

=

÷

ø

ö

ç

è

æ

+

÷

ø

ö

ç

è

æ

+

÷

ø

ö

ç

è

æ

0

2

3 λ

1

3

7 λ

2

1

4 λ

₁ ₂ ₃ 4ll₁+ 3l1 + 7l₂+ 2l2 + 3l₃ = 03 = 0 2l₁ + l₂ = 0

(3)

Vettori linearmente dipendenti e indipendenti

x₁T_{=(4, 1, 2), x}

2T=(7, 3, 1) e x3T = (3, 2, 0)

4l₁+ 7l₂+ 3l₃ = 0 l₁_{+ 3l}₂_{+ 2l}₃ _{= 0} 2l₁ + l₂= 0 4l₁+ 7l₂+ 3l₃= 0 l₁+ 3l₂+ 2l₃= 0 l₂ _{= -2l}₁ 4l₁- 14l₁+ 3l₃= 0 l₁- 6l₁+ 2l₃= 0 l₂ = -2l₁ - 10l₁+ 3l₃= 0 - 5l₁+ 2l₃= 0 l₂ _{= -2l}₁

(4)

Vettori linearmente dipendenti e indipendenti

x₁T_{=(4, 1, 2), x}

2T=(7, 3, 1) e x3T = (3, 2, 0)

- 10 (2/5 l₃) + 3l₃= 0 l₁= 2/5 l₃ l₂ _{= -2l}₁ - 4l₃ + 3l₃= 0 l₁= 2/5 l₃ l₂ = -2l₁ l₃ = 0 l₁_{= 0} l₂ = 0 Sono linearmente indipendenti - l₃= 0 l₁= 2/5 l₃ l₂ _{= -2l}₁ - 10l₁+ 3l₃= 0 l₁_{= 2/5 l}₃ l₂ = -2l₁

(5)

Vettori linearmente dipendenti e indipendenti

Metodo alternativo

Costruiamo la matrice A=(x

_1,

, x

₂

, x

₃

)

1. A è invertibile sse le sue righe (le sue colonne) sono linearmente indipendenti 2. A è invertibile sse il suo determinante è diverso da zero.

Se det(A)≠0 le righe (le colonne) di A sono linearmente Verificare se i seguenti vettori:

x₁T_{=(4, 1, 2), x}

2T=(7, 3, 1) e x3T = (3, 2, 0)

(6)

Vettori linearmente dipendenti e indipendenti

Metodo alternativo

Verificare se i seguenti vettori: x₁T_{=(4, 1, 2), x}

2T=(7, 3, 1) e x3T = (3, 2, 0)

Sono linearmente indipendenti

det(A) = 2 _{· det}  7 3 3 2 1 · det  4 3 1 2 + 0 · det  4 7 1 3

(7)

Vettori linearmente dipendenti e indipendenti

Cambiare, ora, il vettore x

₁T

_{= (4, 1, 2) con x}

1T

= (4, 1, 1) e

verifichiamo se:

x

₁T

_{=(4, 1, 1), x}

2T

=(7, 3, 1) e

x

3T

= (3, 2, 0)

sono linearmente indipendenti o dipendenti.

÷

ø

ö

ç

è

æ

=

÷

ø

ö

ç

è

æ

+

÷

ø

ö

ç

è

æ

+

÷

ø

ö

ç

è

æ

0

2

3 λ

1

3

7 λ

1

4 λ

₁ ₂ ₃ 4ll₁+ 3l1 + 7l₂+ 2l2 + 3l₃3 = 0= 0 l₁ _{+ l}₂_{= 0} 4l₁+ 7l₂+ 3l₃= 0 l₁+ 3l₂+ 2l₃= 0 l₁ = -l₂ -4l₂+ 7l₂+ 3l₃= 0 -l₂+ 3l₂+ 2l₃= 0 l₁ _{= -l}₂

(8)

Vettori linearmente dipendenti e indipendenti

-4l₂+ 7l₂+ 3l₃= 0 -l₂+ 3l₂+ 2l₃= 0 l₁ = -l₂ 0= 0 l₂= -l₃ l₁ _{= -l}₂ 3l₂+ 3l₃= 0 2l₂+ 2l₃= 0 l₁ = -l₂

Fissiamo

l₃ =1 ottenendo l₂ =-1 e l₁ = 1.

÷

ø

ö

ç

è

æ

=

÷

ø

ö

ç

è

æ

+

÷

ø

ö

ç

è

æ

+

÷

ø

ö

ç

è

æ

=

÷

ø

ö

ç

è

æ

+

÷

ø

ö

ç

è

æ

-÷

÷

ø

ö

ç

è

æ

0

2

3

1 -3

-7

-1

1

4

0

2

3

1

3

7

1

4

1

Poichè la combinazione lineare dei tre vettori con questi coefficienti restituisce il vettore nullo, x₁T_{, x}

2T, x3T non sono

(9)

Vettori linearmente dipendenti e indipendenti

Verificare che I tre vettori sono linearmente dipendenti con il metodo alternativo.

(10)

Vettori linearmente dipendenti e indipendenti

1) Fornire un esempio di vettori in R3 _{linearmente indipendenti}

e linearmente dipendenti.

2) Verificare se i seguenti vettori: x₁T_{=(4, 1, 2) e x}

2T=(7, 3, 1)

e

x₃T_{=(4, 1), x}

4T=(7/2, 5) e x5T = (3, 2)

sono linearmente indipendenti o dipendenti. 3) I vettori x₁T _{e x}

2T formano una base di R3?

4) I vettori x₃T_{, x}

4T e x5T formano una base di R2?

5) I vettori x₃T_{, e x}

(11)

Combinazioni lineari, coniche e convesse

● Un vettore y è combinazione LINEARE dei vettori x₁, x₂, …, x_nse esistono l₁, l₂,

… , l_n numeri reali tali che: y= l₁x₁+ l₂ x₂+…+ l_nx_n

● Un vettore y è combinazione CONICA dei vettori x₁, x₂, … , x_nse esistono l₁, l₂,

… , l_n numeri reali tali che: l₁, l₂,…, l_n ³ 0 e y= l₁ x₁+ l₂x₂+…+ l_n x_n

● Un vettore y è combinazione CONVESSA dei vettori x₁, x₂, … , x_n se esistono l₁,

l₂, … , l_n numeri reali tali che: l₁, l₂,…, l_n ³ 0 e l₁+ l₂+…+l_n = 1 e y= l₁x₁+ l₂x₂+…+ l_nx_n

Esercizi:

Determinare geometricamente se:

1)il vettore yT_{=(8/3, 1) è combinazione} _conica _{dei vettori x}

1T=(1, 1) e x2T = (2,

(12)

Combinazioni lineari, coniche e convesse

Determinare che tipo di combinazione (lineare, conica o convessa) è il vettore yT _{= (5/3, 2/3, 4) rispetto ai vettori:}

x₁T_{=(2, 1, 8), x} 2T=(1, 0, 3) e x3T = (2, 1, 1)

÷

ø

ö

ç

è

æ

=

÷

ø

ö

ç

è

æ

+

÷

ø

ö

ç

è

æ

+

÷

ø

ö

ç

è

æ

4 2/3

5/3

1

2 λ

3

0

1 λ

8

1

2 λ

₁ ₂ ₃ 2ll₁+ l1 + l2 ₃+ 2l= 2/33 = 5/3 8l₁ + 3l₂+ l₃ = 4 2l₁+ l₂+ 2l₃ = 5/3 l₁= 2/3 - l₃ 8l₁ + 3l₂+ l₃ = 4 2(2/3 - l₃) + l₂+ 2l₃ = 5/3 l₁= 2/3 - l₃ 8(2/3 - l₃) + 3l₂+ l₃ = 4

(13)

Combinazioni lineari, coniche e convesse

x₁T_{=(2, 1, 8), x} 2T=(1, 0, 3) e x3T = (2, 1, 1) 2(2/3 - l₃) + l₂+ 2l₃ = 5/3 l₁= 2/3 - l₃ 8(2/3 - l₃) + 3l₂+ l₃ = 4 4/3 - 2l₃+ l₂+ 2l₃ = 5/3 l₁= 2/3 - l₃ 16/3 - 8l₃ + 3l₂+ l₃ = 4 l₂ = 5/3 - 4/3 = 1/3 l₁= 2/3 - l₃ - 7l₃ + 3l₂ = 4 - 16/3 = -4/3 l₂ = 1/3 l₁= 2/3 - l₃ - 7l₃ + 1 = - 4/3

(14)

Combinazioni lineari, coniche e convesse

x₁T_{=(2, 1, 8), x} 2T=(1, 0, 3) e x3T = (2, 1, 1) l₂ = 1/3 l₁_{= 2/3 - l}₃ - 7l₃ + 1 = - 4/3 l₂ = 1/3 l₁= 2/3 - l₃ - 7l₃ = - 1 - 4/3 = -7/3 l₂ = 1/3 l₁_{= 2/3 - l}₃ l₃ = 1/3 l₂ = 1/3 l₁= 1/3 l₃ = 1/3

(15)

Combinazioni lineari, coniche e convesse

x₁T_{=(2, 1, 8), x} 2T=(1, 0, 3) e x3T = (2, 1, 1)

÷

ø

ö

ç

è

æ

=

÷

ø

ö

ç

è

æ

+

÷

ø

ö

ç

è

æ

+

÷

ø

ö

ç

è

æ

4 2/3

5/3

1

2

3

1

3

0

1

3

1

8

1

2

3

1

● Un vettore y è combinazione LINEARE dei vettori x₁, x₂, …, x_n se esistono l₁,

l₂, … , l_n numeri reali tali che: y= l₁x₁+ l₂ x₂+…+ l_nx_n

● Un vettore y è combinazione CONICA dei vettori x₁, x₂, … , x_n se esistono l₁,

l₂, … , l_n numeri reali tali che: l₁, l₂,…, l_n ³ 0 e y= l₁ x₁+ l₂x₂+…+ l_n x_n

● Un vettore y è combinazione CONVESSA dei vettori x₁, x₂, … , x_n se esistono

l₁, l₂, … , l_n numeri reali tali che: l₁, l₂,…, l_n³ 0 e l₁+ l₂+…+l_n = 1 e y= l x + l x +…+ l x

Combinazione

convessa

(16)

Combinazioni lineari, coniche e convesse

Si determini un vettore che sia combinazione conica dei seguenti tre vettori:

x₁T_{=(3, 0, 1), x} 2T=(5, 4, 1) e x3T = (1, 3, 8)

÷

ø

ö

ç

è

æ

=

÷

ø

ö

ç

è

æ

+

÷

ø

ö

ç

è

æ

+

÷

ø

ö

ç

è

æ

3 2 1 3 2 1

y

8

3

1 λ

1

4

5 λ

1

0

3 λ

Combinazione conica implica che

l₁, l₂,…, l_n³ 0

÷

ø

ö

ç

è

æ

=

÷

ø

ö

ç

è

æ

+

÷

ø

ö

ç

è

æ

+

÷

ø

ö

ç

è

æ

3 2 1

y

8

3

1

0

1

4

5

1

0

3

1

1+5 = y_{4 = y} 1 2 1/3 + 1 = y₃ 6 = y₁ 4 = y₂ 4/3 = y₃

(17)

3x₁ x₂ + x₃ <= 3 2x1 3x₂ 2x₃ >= 4 x₁ x₃ = 2 x₁ > = 0 x₂ <= 0 x₃ n.v. max z = x₁ x₂ x₃

Esercizio

Scrivere la forma canonica e la forma standard per il seguente problema di programmazione lineare.

(18)

Esempio: Pianificazione della produzione (formulazione)

Un’industria fabbrica 4 tipi di prodotti, P1, P2, P3, P4, la cui lavorazione è affidata a due reparti dell’industria: il reparto produzione e il reparto

confezionamento. Per ottenere i prodotti pronti per la vendita è necessaria naturalmente la lavorazione in entrambi i reparti. La tabella che segue riporta, per ciascun tipo di prodotto i tempi (in ore) necessari di lavorazione in ciascuno dei reparti per avere una tonnellata di prodotto pronto per la vendita.

P1 P2 P3 P4

Reparto produzione 2 1.5 0.5 2.5

Reparto confezionamento 0.5 0.25 0.25 1

ciascuna tonnellata di prodotto dà i seguenti profitti (prezzi espressi in Euro per tonnellata)

P1 P2 P3 P4

Profitto 250 230 110 350

Determinare le quantità che si devono produrre settimanalmente di ciascun tipo di prodotto in modo da massimizzare il profitto complessivo, sapendo che ogni settimana, il reparto produzione e il reparto confezionamento hanno una

(19)

Variabili di decisione.

E’ naturale introdurre le variabili reali x₁, x₂, x₃ e x₄ rappresentanti

rispettivamente le quantità di prodotto P1, P2, P3, P4 da fabbricare in una settimana.

Funzione Obiettivo.

Ciascuna tonnellata di prodotto contribuisce al profitto totale secondo la tabella data. Quindi il profitto totale sarà:

Max 250x₁ + 230x₂ + 110x₃ + 350x₄ Vincoli.

Ovviamente la capacità produttiva della fabbrica (risorsa «scarsa») limita i valori che possono assumere le variabili; infatti si ha una capacità massima lavorativa in ore settimanali di ciascun reparto. In particolare per il reparto produzione si hanno a disposizione al più 100 ore settimanali e poiché ogni

tonnellata di prodotto P1 utilizza il reparto produzione per 2 ore, ogni tonnellata di prodotto P2 utilizza il reparto produzione per 1.5 ore e così via per gli altri tipi di prodotti si dovrà avere:

(20)

Ragionando in modo analogo per il reparto confezionamento si ottiene:

0.5x₁ + 0.25x₂ + 0.25x₃ + x₄ ≤ 50

Vincolo di non negatività delle variabili:

x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0

La formulazione finale quindi può essere scritta in questa forma: max 250x₁ + 230x₂ + 110x₃ + 350x₄

2x₁ + 1.5x₂ + 0.5x₃ + 2.5x₄ ≤ 100 (utilizzo reparto produzione) 0.5x₁ + 0.25x₂ + 0.25x₃ + x₄ ≤ 50 (utilizzo reparto confezion.) x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0

(21)

Consideriamo ulteriori richieste (vincoli):

1.P1 non può utilizzare per più di 20 ore settimanali il reparto di produzione.

2.La produzione di P2 non può superare quella di P3.

3.P4 può utilizzare complessivamente 30 ore settimanali di lavorazione (tra il

reparto di produzione e quello di confezionamento).

4.La produzione di P1 non può superare il doppio della produzione di P2 e P3. 1. P1 non può utilizzare per più di 20 ore settimanali il reparto di produzione:

2x₁ ≤ 20 ⇔ x₁ ≤ 10 2. La produzione di P2 non può superare quella di P3:

x₂ ≤ x₃

3. P4 può utilizzare complessivamente 30 ore settimanali di lavorazione: 2.5x₄ + x₄≤ 30 ⇔ 3.5x₄ ≤ 30

(22)

Supponiamo che ci siano tre lavori da svolgere: stuccare, imbiancare e levigare. Abbiamo a disposizione tre persone Mario, Luca ed Andrea che sanno svolgere questi tre lavori ma con differenti tempistiche come indicato nella seguente tabella (i valori rappresentano le ore necessarie ad ogni persona per portare a termine il rispettivo lavoro).

Esempio 2

STUCCA IMBIANCA LEVIGA

MARIO 3 1 2

LUCA 2 1.5 1.5

ANDREA 3 1.5 3

Il nostro obiettivo è quello di assegnare ad ogni persona un lavoro e ad ogni lavoro una persona al fine di minimizzare le ore totali necessarie per svolgere i tre lavori.

(23)

X₁₁+ X₁₂+ X₁₃= 1 X₂₁+ X₂₂+ X₂₃= 1 X₃₁+ X₃₂+ X₃₃= 1 (Mario) (Luca) (Andrea) X₁₁+ X₂₁+ X₃₁= 1 X₁₂+ X₂₂+ X₃₂= 1 X₁₃+ X₂₃+ X₃₃= 1 (Levigare) (Stuccare) (Imbiancare) Min 3X₁₁+1X₁₂+2X₁₃+ 3X₂₁+1.5X₂₂+1.5X₂₃+3X₃₁+1.5X₃₂+3X₃₃

Esempio 2

xij = (

1 se assegnamo alla persona i il lavoro j 0 altrimenti

(24)

X₁₁+ X₁₂+ X₁₃= 1 X₂₁+ X₂₂+ X₂₃= 1 X₃₁+ X₃₂+ X₃₃= 1 X₁₁+ X₂₁+ X₃₁= 1 X₁₂+ X₂₂+ X₃₂= 1 X₁₃+ X₂₃+ X₃₃= 1 Min 3X₁₁+1X₁₂+2X₁₃+ 3X₂₁+1.5X₂₂+1.5X₂₃+3X₃₁+1.5X₃₂+3X₃₃

3

2

1 ogni

per

1

3 1

,

i

x

j ij

=

å

=

3

2

1 ogni

per

1

3 1

,

j

x

i ij

=

å

=

Esempio 2

(25)

Min 3X₁₁+1X₁₂+2X₁₃+ 3X₂₁+1.5X₂₂+1.5X₂₃+3X₃₁+1.5X₃₂+3X₃₃