Lezione n°8

Lezione n

°

8

- Matrice di base.

- Soluzioni di base ammissibili.

- Relazione tra vertici di un poliedro e soluzioni basiche.

- Teorema fondamentale della PL.

Lezioni di Ricerca Operativa

Università degli Studi di Salerno

Soluzione Algebrica dei problemi di PL

Consideriamo un problema di PL in

Forma Standard

min z = c

T

x

Ax = b (1)

x ≥ 0 (2)

x ∈ R

n

Poiché m=rango(A) ed m<n, si può partizionare A come

A=[ A

_B

| A

_N

]

dove:

!

A

_B

è una matrice non singolare mxm ( det(A

_B

) ¹ 0 )

!

A

_N

è una matrice mx(n-m)

La matrice A

_B

è composta da m colonne linearmente indipendenti

di A. Tali colonne (viste come vettori) sono quindi una base nello

spazio vettoriale ad m dimensioni delle colonne di A.

La matrice A

_B

è detta

Matrice di Base (Base)

In corrispondenza di una scelta di A

_B

ed A

_N

si può partizionare

anche il vettore delle x:

x

_B

è detto

Vettore delle Variabili in Base (Vettore di Base)

Un esempio:

Il sistema di equazioni lineari Ax=b si può riscrivere come:

Una soluzione del sistema di equazioni (1) corrisponde a

determinare il valore per m variabili (x

_B

) avendo fissato

arbitrariamente il valore per le restanti n-m variabili (x

_N

)

min z = c

T

x

Ax = b (1)

x ≥ 0 (2)

x ∈ R

n

⟹ 𝐴

_!

"#

𝐴

_!

𝑥

_!

+ 𝐴

"#

_!

𝐴

_$

𝑥

_$

= 𝐴

"#

_!

𝑏

𝐴

_!

𝑥

_!

+ 𝐴

_$

𝑥

_$

= 𝑏

⟹ 𝑥

_!

= 𝐴

"#

_!

𝑏 - 𝐴

_!

"#

𝐴

_$

𝑥

_$

Una scelta particolarmente importante è porre x

_N

=0 da cui si

ottiene:

Soluzione di Base

Se x

_𝐵

= A

_B

-1

_{b ≥ 0}

si ottiene una

Soluzione di Base Ammissibile

.

min z = c

T

x

Ax = b (1)

x ≥ 0 (2)

x ∈ R

n

Le soluzioni di base sono importanti poichè vale il

seguente teorema:

3. Teorema

Dato X={x: Ax=b, x³0} insieme convesso, dove A è

una matrice mxn di rango m con m<n,

x

_e

è un

punto estremo

di X se e solo se x

_e

è una

soluzione di base ammissibile.

1 2 3 4 5

5

4

3

2

1

x

₁

x

₂

(1)

(2)

(3)

X

P

₁

P

₂

P

₃

P

₄

Z =0

Z =7.75

Ottimo

P

₁

=

0

0

!

"

#

$

%

&

P

₂

=

5

2

5

2

!

"

#

#

$

%

&

&

P

₃

=

11

4

9

4

!

"

#

#

$

%

&

&

P

₄

=

7

2

0

!

"

#

#

$

%

&

&

Il problema trasformato

in forma standard

"

Il massimo numero di possibili basi corrisponde al numero di

possibili estrazioni di m colonne su n colonne di A:

Nell’esempio

"

In generale, non tutte le possibili sottomatrici mxm sono

non-singolari (quindi invertibili). Inoltre, non tutte le matrici di base

danno luogo a soluzioni ammissibili (ossia, con tutte le

componenti positive).

"

Per questo motivo il numero delle possibili combinazioni

Nell’esempio precedente solo 6 combinazioni danno

luogo a basi ammissibili, vediamo quali:

P

₁

P

₂

P

₃

P

₄

_x

₁

x

₂

X

(3)

(2)

(1)

−min z = -2x

₁

− x

₂

x

₁

+ x

₂

+ x

₃

= 5 (1)

−x

₁

+ x

₂

+ x

₄

= 0 (2)

6x

₁

+ 2x

₂

+ x

₅

= 21 (3)

x

_i

≥ 0

P

₁

P

₂

P

₃

P

₄

_x

₁

x

₂

X

(3)

(2)

(1)

soluzione

degenere

−min z = -2x

₁

− x

₂

x

₁

+ x

₂

+ x

₃

= 5 (1)

−x

₁

+ x

₂

+ x

₄

= 0 (2)

6x

₁

+ 2x

₂

+ x

₅

= 21 (3)

x

_i

≥ 0

P

₁

P

₂

P

₃

P

₄

_x

₁

x

₂

X

(3)

(2)

(1)

x

_B

₇

=

2

4

x

x

3

4

x

5

3

5 = A

1

B

7

b =

2

4

1 0 0

0 1 0

0 0 1

3

5

2

4

5

0

21

3

5 =

2

4

5

0

21

3

5 =) P

1

x

_B

₅

=

2

4

x

x

1

3

x

5

3

5 = A

1

B

5

b =

2

4

0

1

1

1 0

0

0

6

1

3

5

2

4

5

0

21

3

5 =

2

4

0

5

21

3

5 =) P

1

<latexit sha1_base64="Bmpzdsu34hT7pigmcQaU12eqUGc=">AAAEJHicbVLLbtQwFM10eJTyaAtLNhf6EIvpKJlqgE2lUjYsWBRBH1IzjBznNnM1jh3ZTmmJ8hd8Ax/BFpbsEAs2/RbsdESZab2wjs89917b9ySFIGPD8E9rrn3j5q3b83cW7t67/2BxafnhvlGl5rjHlVD6MGEGBUncs2QFHhYaWZ4IPEjGr3384AS1ISU/2LMCBznLJB0TZ9ZRw+XWxmpcyhS1LwAVnEI9rHaG/Rq2IE4wI1klObOaTms4HVYQQQ1x3MDNS9j3EGV6qd2CV47fmcTqjxVsuNSpVglc1ySEdS9dd8AV9+DfwYeeN8RUr9kK/Qut23rR7K2udnOy/rXa+K2SmaZsZJnW6hPA7jBaHS6thN2wWXAVRBOwEkzWrvvg8zhVvMxRWi6YMUdRWNhBxbQlLrBeiEuDBeNjluGRg5LlaAZVM9ga1krDrIICNZCAhsT/MyqWG3OWJ07prj0yszFPXhc7Ku3xy0FFsigtSu4bWRLYNDJck3MMQkoarWX+5ggkgTPNrEVNwDh3ZOkstLAGBAaz0p0JXHU+cjmOUlKBsU4BLMuo9NGUQKNPxC68R+DOpk5UaOW8mhM4C+ckmaAnU6+wNP588UseCUo002dVoQx5A5PMOs14TIczwTtmxAo03QxVjm6MfPp/dSkw7Zx4/6UdvxtZ5ol7a+oGIjKlyY7y3vRQqkSpsWWJmWbzUlhyfWvniGh2/lfBfq8bbXZ773or2+HEG/PB4+Bp8CyIghfBdvAm2A32At760vrW+t760f7a/tn+1f59IZ1rTXIeBVOrff4XbJBY8w==</latexit>

x

_B

₆

=

2

4

x

x

2

3

x

5

3

5 = A

1

B

6

b =

2

4

0

1

1

1 0

0

0

2 1

3

5

2

4

5

0

21

3

5 =

2

4

0

5

21

3

5 =) P

1

<latexit sha1_base64="+cS/JU15dEM4qmMtyU5Z5HyUSVc=">AAAEInicbVLNbhMxEN5t+Cnlr4Ujl4G2CIk02qRq4VKplAsHDkXQH6kJkdc73YzitVe2t7Ss9iV4Bh6CKxy5IU5IiGdhNo0KSWPJ1ueZb2Y8ni/OFTkfRb/CucaVq9euz99YuHnr9p27i0v39p0prMQ9aZSxh7FwqEjjniev8DC3KLJY4UE8fFn7D07QOjL6nT/LsZeJVNMxSeHZ1F8Kn650C52grRNACadQ9cud/mYFW90YU9JlnAlv6bSC034JHaig2x3B9X9wo4aokwvu1gu27vDeZE/1voS1NlQTdWKYUSGCx9DmHdWJa7B2catda52Rf6LSdIqNczIfnSnmjGrM2phF7b42OrWUDryw1nyAXe6EG1jpLy5HrWi04DJoj8FyMF67/L1/uomRRYbaSyWcO2pHue+VwnqSCquFbuEwF3IoUjxiqEWGrleOxlrBauGEN5CjBVIwMuL/EaXInDvLYmbywwdu2lcbZ/mOCn/8vFeSzguPWtaFPCkcFXLSEusFISGL3ov65QikQQorvEdLIKRkY8ECWlgFAodpwXcCzi4HHMMmow04zwwQaUpF7U0ILNaB2IK3CJJFyqTcGlZqRsACzkgLRQ8nuvA0/Hj+SzVSFFthz8rcOKrlSzptjibkmlIo2XQDkaNrpWgy5EHKyf+1hcKkeVILMGnWp9NFFnOvCQ9EpcaSH2SdyaGUsTFDL2I3ac0K5YnrVqyI9vT8L4P9Tqu93uq86SxvR2NtzAcPgkfBk6AdPAu2g1fBbrAXyPBT+CX8Gn5rfG58b/xo/DynzoXjmPvBxGr8/gtZ9Flj</latexit>

x =

2

6

6

6

6

4

0

0

5

0

21

3

7

7

7

7

5

x

₁

x

₂

x

₃

x

₄

x

₅

<latexit sha1_base64="/pdKqi2WPSp1cqZFVV6T3wQPxVc=">AAADeXicbVJLb9NAEN40PEp4tIULiMuUtlKFoshOqeCCVIkLxyLoQ6qjaL2eOqPsw9pHSbBy4ldy4c5v4MI6CRVpmcPOeOb7PLvzTV5Jcj5JfrTW2nfu3ru//qDz8NHjJxubW09PnQlW4Ikw0tjznDuUpPHEk5d4XlnkKpd4lo8/NPWzK7SOjP7ipxUOFC81XZLgPqaGm993s6ALtA0fapjADN5nOZak61xxb2kygwSybHEcXkf9FDLUxTVoyflLgckwjajJsA9zd7BwbxbucMFdgneHmztJL5kb3A7SZbDDlnY83Gr9zAojgkLtheTOXaRJ5Qc1t56ExFknCw4rLsa8xIsYaq7QDer5tGawFxz3Biq0QBLmSfyXUXPl3FTlERlvOHI3a03yf7WL4C/fDWrSVfCoRdPIk8R5IycsRRkQCrLoPW9ujkAaBLfce7QEXIiYDFGXzh4QOCxD/CaIfxejyIkpow04HxHAy5JCUy0ILDZE7MFnBBG1j6DKmrgAiiDuhSLNJW2vvMLT+NtiSk0kKbfcTuvKOGq2gnTZ5daar64ruBRdN+IVul6JRmFUTKzO1waJRfeqWaCi25xOB5XHtxZREFkaS36k+qui1LkxY89zt5pVQXqKfWdxI9Kb+t8OTvu99KDX/9TfOUqWu7HOXrJXbJ+l7C07Yh/ZMTthgv1qbbSet16s/W5vt/fbrxfQtdaS84ytWPvgDzQEH0Q=</latexit>

"

A ciascuna matrice di base B (ammissibile) corrisponde una

sola soluzione di base (ammissibile).

"

Viceversa, ad una soluzione di base (ammissibile) possono

corrispondere più matrici di base. Questi casi sono associati a

soluzioni dette

degeneri

, ovvero soluzioni per cui qualche

componente del vettore di base x

_B

risulta nullo.

"

In caso di soluzioni degeneri, al vertice del poliedro sono

Dalla corrispondenza delle soluzioni di base ammissibili con i

punti estremi del poliedro X deriva il seguente teorema.

4. Teorema Fondamentale della PL

Dato un problema di PL in forma standard:

dove A è una matrice mxn con rango(A)=m ed m<n, allora:

1. esiste una soluzione ammissibile

⇔ esiste una soluzione

ammissibile di base

2. esiste una soluzione ottima finita

⇔ esiste una soluzione

ottima finita che è anche di base

min z = c

T

x

Ax = b

x ≥ 0

"

La ricerca delle soluzioni di un problema di PL si può

effettuare esaminando solamente un numero finito di

soluzioni corrispondenti alle soluzioni di base associate al

poliedro dei vincoli.

"

Poiché il massimo numero di possibili basi di un problema di

PL è finito, tali problemi hanno una struttura discreta.

"

I problemi di ottimizzazione corrispondenti alla selezione tra

un numero finito di alternative si dicono problemi

"

Un possibile algoritmo per determinare la soluzione ottima

potrebbe consistere nella generazione esplicita di tutte le

soluzioni ammissibili di base, quindi nella scelta di quella

soluzione che rende massimo l’obiettivo.

"

Tale strategia non è conveniente poiché il numero massimo

delle possibili basi cresce in maniera esponenziale col

crescere delle dimensioni del problema (numero di variabili e

vincoli).

"

Algoritmi che richiedono in generale un numero di passi che

cresce in maniera esponenziale con le dimensioni del

problema non sono efficienti.