Formulazioni dei problemi di lot sizing

Parte 2 · Formulazioni dei problemi e loro proprietà · Capitolo 15 · Dispensa, volume 2 (PDF) · Slide · Esercizi: Problemi di lot sizing

Prerequisiti

• Dal modulo Programmazione lineare intera, Capitolo 1 «Programmazione lineare intera» e Capitolo 2 «Bound primali e duali»: problemi ILP, rilassamenti lineari e lower bound.

• Da questo modulo, Capitolo 8 «Problemi di lot sizing»: il problema, le sue ipotesi, i piani e l'istanza di riferimento.

Obiettivi

Alla fine di questo capitolo saremo in grado di:

• scrivere la formulazione big-M del problema di lot sizing capacitato e calcolare un valore debole e un valore forte di big-M;

• scrivere la formulazione a cammino minimo e interpretarne le variabili come gli archi di una rete;

• rappresentare un piano di produzione come combinazione di cammini della rete;

• confrontare i bound LP delle formulazioni sull'istanza di riferimento;

• scrivere il modello PLI del problema di lot sizing senza capacità;

• estendere la formulazione big-M a più prodotti con tempi di setup, alla scorta iniziale, agli straordinari e alla domanda non soddisfatta, e calcolare i valori forti di big-M di ogni modello.

15.1 Panoramica della famiglia

• I modelli big-\(M\) dei problemi di lot sizing usano, per ogni periodo \(t \in T\), una variabile di produzione intera \(x_t\), una variabile di scorta intera \(s_t\) e una variabile di setup binaria \(y_t\).

• I vincoli di bilanciamento del flusso collegano le scorte di periodi consecutivi alla produzione e alla domanda; le variabili di setup sono collegate alla produzione da vincoli big-\(M\).

• La funzione obiettivo minimizza il costo totale di setup, di produzione e di mantenimento a scorta. La formulazione a cammino minimo del CLS sostituisce le variabili di produzione e di scorta con gli archi di una rete.

I modelli di lot sizing sono modelli di flusso sui periodi, con variabili di setup binarie che attivano la produzione. I membri della famiglia aggiungono prodotti, tempi di setup, una scorta iniziale, straordinari o domanda non soddisfatta agli stessi vincoli di bilanciamento e big-\(M\).

• La tabella elenca i membri della famiglia, con i nomi dei loro modelli e le sezioni che li scrivono.

Problema	Modelli	Formulazione	Sezione
CLS	\(\mathrm{ILP}_{\mathrm{CLSP}}\)	formulazione big-\(M\)	15.3
CLS	\(\mathrm{MIP}^{\mathrm{SP}}_{\mathrm{CLSP}}\)	formulazione a cammino minimo	15.5
ULS	\(\mathrm{ILP}_{\mathrm{ULS}}\)	big-\(M\), senza capacità	15.7
MLS	\(\mathrm{ILP}_{\mathrm{CLSP}}^{P}\)	big-\(M\), tempi di setup	15.7
LS-SI	\(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{SI}}\)	big-\(M\), variabili di scorta iniziale	15.7
LS-OT	\(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{OT}}\)	big-\(M\), variabili di straordinario	15.7
LS-UD	\(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{UD}}\)	big-\(M\), variabili di domanda non soddisfatta	15.7

• Panoramica

  Panoramica della famiglia

  Apri

• 15.2 Modelli PLI per il problema di lot sizing capacitato

  Valori deboli e forti di big-M

  Apri

• 15.7 Modelli PLI per le varianti

  Più prodotti e tempi di setup · Scorta iniziale · Straordinari · Domanda non soddisfatta · Errori tipici

  Apri

---

Avanti: 15.2 Modelli PLI per il problema di lot sizing capacitato

---

Esercizi su questo capitolo: Problemi di lot sizing