Dinamica dei sistemi aziendali

Risoluzione algebrica della Programmazione Lineare

Possiamo riscrivere l'insieme dei vincoli del problema come:

Ãx̃ b = xBB D Bx Dx b[ ] = + =B DxD -1 -1-

Grazie all'invertibilità della matrice B, possiamo ottenere la soluzione dell'equazione matriciale:

Ãx̃ b=-1 -1 -1 -1 - -Bx B b B Dx B b DB Dx̃ x= = = + Dx x 0 ID D

La scelta delle componenti x è del tutto arbitraria, cioè sono in accordo con i parametri liberi. Con la teoria dei sistemi lineari, una soluzione dell'equazione matriciale si può ottenere assegnando valori qualsiasi alle n componenti del vettore x.

In particolare, ponendo x=0, si ottiene una soluzione di base:

D -1 x B bBx̃ = =0

0−1cioè le componenti di si dicono mentreB b variabili di base,mle restanti componenti sono nulle.

Una si dice se tutte le componentisoluzione di base ammissibile−1del vettore sono non negative (devono rispettare ilx B b=Bvincolo di non negatività imposto dal problema di PL (2)).

Una si dice se anchesoluzione di base ammissibile degenere−1qualche componente del vettore è nulla: nel complesso,x B b=Bil vettore ha più di componenti nulle.

x̃ nDinamica dei Sistemi Aziendali 2019/2020 Programmazione lineare: risoluzione algebrica

Teorema 1.5Dato un problema di PL, ogni soluzione di base ammissibile x̃corrisponde a un vertice della regione di ammissibilità .

Sa xBTraccia della dimostrazione. Sia , conx̃ = 0−1 m∈ , una soluzione di base ammissibile per il sistemax B b R=Bdei vincoli del problema di PL.

Ãx̃ b=Per dimostrare che corrisponde a un vertice di , occorre provarex̃ Sa6(per assurdo) non vi sono due vettori conu, v, u

v,= −corrispondenti a punti di e tali che sia perx̃S = αu + (1 α)v,aqualche 0 1 (i vertici del politopo non possono esprimersi< α <come combinazioni lineari convesse di due punti di )S aDinamica dei Sistemi Aziendali 2019/2020 Programmazione lineare: risoluzione algebrica

Teorema 1.6 (fondamentale della programmazione lineare)
Se un problema di PL ha una soluzione ammissibile, allora esisteuna soluzione di base ammissibile; se esiste una soluzione ottimale,allora esiste una soluzione ammissibile di base ottimale.

Dimostrazione. È diretta conseguenza del teorema di esistenza(1.4) e del teorema (1.5).

Dato che ogni soluzione di base ammissibile corrisponde a un verticedella regione ammissibile , dal punto di vista operativo sarebbeSasufficiente trovare tutte le basi ammissibili, calcolare per ognuna diesse il valore della funzione obiettivo e quindi scegliere l’ottimo.

Dinamica dei Sistemi Aziendali 2019/2020 Programmazione lineare: risoluzione

algebrica

Osservazioni

Dato il sistema dei vincoli vi sono tante basi quante

1) Ãx̃ ≤ b,

sono le possibili scomposizioni della matrice nella forma

A = [I | 0].

Il numero massimo di soluzioni di base è

det(B) = (m + n)!n + m,

cioè il numero di differenti modi di combinare colonne tra le presenti nella matrice Ã.

Il numero di soluzioni di base ammissibili cresce in modo esponenziale con il numero delle variabili e dei vincoli del problema;

di conseguenza, un algoritmo basato sull'enumerazione esplicita di tutte le soluzioni di base non risulta efficiente per la determinazione della soluzione ottimale.

Dinamica dei Sistemi Aziendali 2019/2020 Programmazione lineare: risoluzione algebrica

Ogni base

2) (Corrispondenza tra basi e soluzioni di base). B⁻¹x̃B = bB

determina un'unica soluzione di base, x̃ = 0,

quindi due soluzioni di base distinte e necessariamente

x̃₁ ≠ x̃₂

corrispondono a due basi distinte, B₁ ≠ B₂.

In generale

non è vera l'affermazione inversa: può accadere che incerti problemi due basi distinte conducano alla medesima soluzione di base quindi, dal punto di vista geometrico, al medesimo vertice del poliedro ammissibile: in questo caso la corrispondente soluzione di base ammissibile è degenere.

Geometricamente, la degenerazione si presenta quando per un vertice di passano più di iperpiani (rette nel caso di 2S n n = a variabili decisionali) di vincolo.

Dinamica dei Sistemi Aziendali 2019/2020 Programmazione lineare: risoluzione algebrica

Ad esempio, modifichiamo il problema del mix produttivo aggiungendo un quarto vincolo riguardante la capacità di occupazione di spazio unitario da parte dei prodotti magazzino: 3e sia, rispettivamente, uguale a 1.6 e 2 per quintale. Se lo spazio totale disponibile è di 76 , si deve aggiungere il vincolo m(blu): 16F 20S 760. Il vertice 30) corrisponde alla soluzione di base

degenere 30 0 32 0 0] .[10S4020 Sa F0 10 20 30 40 50 60Dinamica dei Sistemi Aziendali 2019/2020 Programmazione lineare: risoluzione algebricaEsempio: risoluzione algebrica del problema del mix produttivoRiscriviamo il problema nella introducendo 3forma standardvariabili slack, tante quanti sono i vincoli del problema: s , s , sM P C· · ·24F 18S 0 0 0max + + s + s + sM P C· · ·1 0 0 40s. a F + S + s + s + s = (I )M P C· · ·4F 2S 0 1 0 132+ + s + s + s = (II )M P C· · ·2F 4S 0 0 1 140+ + s + s + s = (III )M P C0F , S, s , s , s >M P CIn forma matriciale: T (4)c xmax Ax bs. a =x 0>Dinamica dei Sistemi Aziendali 2019/2020 Programmazione lineare: risoluzione algebricaponendo  F. ..1 1 1 0 0  40 S ..   132A b x s= , = , =4 2 . 0 1 0 M       140. s.. P 2 4 0 0 1 s C(colonne da combinare 3 a 3)F S s s sM P C 2418 

0ce =   0 0Dinamica dei Sistemi Aziendali 2019/2020 Programmazione lineare: risoluzione algebrica

5 !5× 10 eLe possibili sottomatrici 3 3 sono in tutto ==3 3 2! !sono ottenibili combinando semplicemente (cioè senza ripetizione)le colonne di 3 alla volta.

A 1 1 1 ⇒ 64 2 0 (colonne ) 12 0B = F , S, s ) = =det(B1 1M 2 4 0

   −1/60 1/3 62/3−1 −1−1/6 ⇒0 1/3 74/3B x B b= = =B   1 1−1/6 −1/6 −16/31soluzione non ammissibile perchè ha una componente negativa.

Dinamica dei Sistemi Aziendali 2019/2020 Programmazione lineare: risoluzione algebrica

 1 1 0 ⇒ −2 64 2 1 (colonne ) 0B = F , S, s ) = =det(B2 2P 2 4 0

   −1/22 0 10−1 −1−1 ⇒0 1/2 30B x B b= = =B   2 2−6 1 1 32soluzione di base corrispondente al vertice 30).ammissibile, (10,Poiché 0, i vincoli (I) e (III) sono cioè

lesaturati,s = s =M Ccorrispondenti risorse sono utilizzate appieno.

Dinamica dei Sistemi Aziendali 2019/2020 Programmazione lineare: risoluzione algebrica

B = F , S, s ) = det(B3 3C

soluzione di base corrispondente al vertice 14).ammissibile, (26,Poiché 0, i vincoli (I) e (II) sono saturati.

s = s =M P

Dinamica dei Sistemi Aziendali 2019/2020 Programmazione lineare: risoluzione algebrica

B = F , s , s ) = det(B4 4M P

soluzione di base non ammissibile.

Dinamica dei Sistemi Aziendali 2019/2020 Programmazione lineare: risoluzione algebrica

B = F , s , s ) = det(B5 5M C

 0 1/4 0 33−1 −1−1/4 ⇒1 0 7B x B b= = =B   5 5−1/20 1 74soluzione di base corrispondente al vertice 0).ammissibile, (33,Poiché 0, il vincolo (II) è saturato.S = s =PDinamica dei Sistemi Aziendali 2019/2020 Programmazione lineare: risoluzione algebrica 1 0 0 ⇒ 64 1 0 (colonne ) 1 0B = F , s , s ) = =det(B6 6P C 2 0 1   1 0 0 40−1 −1−4 −28⇒1 0B x B b= = =B   6 6−2 0 1 60soluzione di base non ammissibile.Dinamica dei Sistemi Aziendali 2019/2020 Programmazione lineare: risoluzione algebrica 1 0 0 ⇒ 60 1 0 (colonne ) 1 0B I= = s , s , s ) = =det(B7 7M P C 0 0 1  40−1 −1⇒ 132B B I x B b Ib b= = = = = =7 B  7 7 140soluzione di b