Algebra della programmazione lineare

Cerchiamo di esprimere il concetto di vertice in modo algebrico, sfruttando la struttura di vincolo.

Forma Standard

Si dice Forma Standard di un problema di PL, il problema scritto nella forma:

con

Caratteristiche:

1. Problema di minimo;
2. Vincoli di uguaglianza;
3. Termini noti
4. Variabili

Ogni problema di PL può essere scritto in FS.

Regole di conversione

• Un problema di max si scrive come problema di min:
• Vincolo di si trasforma in vincolo di aggiungendo una variabile di SCARTO (SLACK)
• Vincolo di si trasforma in vincolo di sottraendo una variabile di SURPLUS
• Variabile , Si moltiplica per -1 e si rinomina:
  • si sostituisce in tutti i vincoli e nella f.o.
• Variabile libera in segno, si introducono due variabili , e si pone , e poi si sostituisce la variabile.

Forma Standard e Vertici

Partendo da un esempio, consideriamo il poliedro:

Se poniamo Troviamo la soluzione , le componenti sono è un vertice.

Generalizzando l’esempio, consideriamo: 

con:

E richiediamo che .

Perché?

• Se vuol dire che il sistema ha un’unica soluzione, cioè nella regione ammissibile c’è un solo punto, e quindi non c’è alcuna ottimizzazione da effettuare, non avendo alcuna altra scelta.
• Se vuol dire che ci sono dei vincoli in eccesso, ridondanti.

Per trovare i vertici…

• Annulliamo n-m variabili;
• Risolviamo il sistema nelle rimanenti variabili;
• Se le variabili sono tutte , abbiamo un vertice.

Dobbiamo però capire come scegliere le variabili da annullare.

Base Vettoriale

Data una matrice una base è una sottomatrice di formata da colonne linearmente indipendenti.

Se .

Individuata una base B, la matrice si partiziona:

Supponiamo che la matrice B sia fatta con le prime colonne di . 

Difatti, è quadrata: , le altre colonne di formano la matrice non di base . 

La matrice si partiziona quindi in e , ed anche il vettore si partiziona in: :

• componenti associate alla colonna di ;
• componenti associate alla colonna di

Il sistema allora si scrive:

La matrice B è invertibile, perché composta da colonne linearmente indipendenti. Per questo possiamo moltiplicare a sinistra per

Per trovare un vertice la scelta naturale è porre , cioè porre a zero le variabili fuori base. 

Soluzione di Base

Dato il sistema si dice soluzione di base il vettore , cioè e (Componenti di base sono date da e quelle fuori base sono nulle).

• Se la soluzione di base si dice ammissibile.
• Se qualche componente di base è nulla, si dice degenere

Teorema 1

Dato il poliedro è un vertice se e solo se è una soluzione di base ammissibile

• Per il Teorema Fondamentale della PL bisogna cercare l’ottimo tra i vertici;
• Per il Teorema 1 appena definito bisogna cerca l’ottimo tra le soluzioni di base ammissibile.

Quante soluzioni di base ammissibile ci sono?

Il numero di sol di base è legato al numero di basi B. Possiamo estrarre da A sottomatrici di ordine m. Fra queste sottomatrici, ve ne sono alcune non invertibili, e alcune che generano soluzioni di base non ammissibile. Quindi, il numero di soluzioni di base è al più

Questa è la base del Metodo del Simplesso