Metodo del Sibleso

Introduzione

• Il metodo del Sibleso è un algoritmo per risolvere problemi di programmazione lineare.
• Inizia con una soluzione ammissibile di base e cerca di massimizzare la funzione obiettivo.
• Procede iterativamente fino a trovare la soluzione ottimale o determinare che il problema è illimitato.

Algoritmo del Sibleso

• Applicabile a problemi in forma standard:
  • Massimizzare una funzione lineare con vincoli di uguaglianza.
  • Le variabili devono essere positive o nulle.

Input

• Matrice A: dimensione m x n (vertici).
• Matrice B: termini noti, dimensione uguale alle righe di A.
• Costi ridotti: funzione obiettivo dimensione n.
• Base ammissibile: insieme di variabili di base.

Output

• Soluzione ottima di base per il programma lineare.
• Raggio che indica se il problema è illimitato.

Esempio di Applicazione

Descrizione del Problema

• Un'azienda produce due fragranze, X1 e X2, a partire da tre essenze: rosa, mucchietto e viola.
• Richieste per la production:
  • Fragranza 1: 1,5L di rosa, 1L di mucchietto, 0,3L di viola.
  • Fragranza 2: 1L di rosa, 1L di mucchietto, 0,5L di viola.
• Disponibilità magazzino:
  • Rosa: 7L, Mucchietto: 1L, Viola: 9L.
• Profitti: 130€ per X1 e 100€ per X2.

Funzione Obiettivo

• Massimizzare: 0,3X1 + 0,2X2
• Condizioni: X1, X2 >= 0

Forma Standard

1. Convertire la funzione obiettivo massimizzante in minimizzante:
   • Moltiplicare per -1.
2. Scrivere vincoli in forma di uguaglianza:
   • Aggiungere variabili di slack.
   • Esempio:
     • 1,5X1 + X2 + S1 = 7
     • X1 + X2 + S2 = 1
     • 0,3X1 + 0,5X2 + S3 = 9
3. Condizioni: X1, X2, S1, S2, S3 >= 0

Creazione del Tablò

• Iniziare con la funzione obiettivo e i vincoli:
  • Includere tutti i valori nella tabella iniziale.
• Trovare l'elemento pivot:
  • Selezionare la colonna con il costo più basso.
  • Eseguire calcoli per determinare il pivot.

Iterazioni

• Annullare gli elementi sopra e sotto il pivot usando l'eliminazione di Gauss.
• Ripetere l'iterazione fino a quando non ci sono più valori negativi nella funzione obiettivo.

Soluzione Ottimale

• Alla fine dell'algoritmo:
  • Se tutti i valori della funzione obiettivo sono non negativi, si è trovata la soluzione ottimale.
  • Esempio finale:
    • X1 = 12, X2 = 9, profitto totale Z = 2460€.

Conclusione

• Il metodo del Sibleso offre una soluzione ottimale per problemi di programmazione lineare.
• Importanza di seguire i passi dell'algoritmo per garantire correttezza e efficienza.

Ringraziamenti

• Se il video è stato utile, mettere mi piace e seguire per altri contenuti.