Pianificazione della produzione giornaliera

Programmazione Lineare

• Il profitto unitario di ogni modello è di 30, 20 e 50 euro, rispettivamente.
• Il problema di massimizzazione del profitto giornaliero viene modellato con tre variabili x1, x2, x3, che rappresentano il numero di unità di tipo i prodotte.
• Il problema è soggetto a tre vincoli:
  • La disponibilità di materie prime è limitata a 4000, 6000 e 700 unità.
  • La forza lavoro disponibile è limitata a 2x1 + 3x2 + 5x3 ≤ 4000.
  • I requisiti minimi di produzione stabiliti dal marketing sono x1 ≥ 200, x2 ≥ 200, x3 ≥ 150.

Il problema del distributore di giornali

• La casa editrice ANALFABETA pubblica un quotidiano che viene distribuito da quattro centri di smistamento S1, S2, S3, S4.
• I centri di smistamento richiedono almeno 100000, 150000, 50000 e 75000 copie del quotidiano.
• Il giornale viene stampato in tre tipografie T1, T2, T3 che producono rispettivamente al massimo 125000, 180000 e 70000 copie.

Modello di Programmazione Lineare

• Il modello di programmazione lineare è una descrizione di un problema che richiede di massimizzare o minimizzare una funzione di costo o profitto su un certo dominio.
• La scrittura usuale è: max z = f(x) (oppure min z = f(x)) soggetto a gi(x) ≤ bi, i = 1,..., m, x = (x1,..., xn) ∈ X ⊆ Rn.
• In un modello sono presenti:
  • Variabili di controllo in funzione delle quali viene formulato ogni altro elemento del modello.
  • Una funzione obiettivo f(x) che determina un costo o profitto legato alla soluzione.
  • Una o più serie di vincoli, che correlano tra loro i valori delle variabili, imponendo condizioni di fisica realizzabilità e/o requisiti particolari richiesti alla soluzione.

Algoritmi e Complessità

• Il senso di definire un problema di ottimizzazione è, almeno per le applicazioni pratiche, direttamente collegato alla possibilità di sviluppare procedure di calcolo o algoritmi in grado di risolverne efficientemente le istanze.
• Un algoritmo che risolve il problema P è una procedura che prende in input una qualsiasi istanza I di P e fornisce in output una soluzione ottima x* per quell'istanza I.
• La funzione T(n) conta il numero di operazioni elementari necessarie all'algoritmo per risolvere l'istanza I.