Errori tipici · In sintesi¶

25.3 Errori tipici¶

Attenzione

Applicare la proprietà zero-inventory ordering con le capacità. La dimostrazione sposta la produzione fra due periodi senza limiti: con le capacità un periodo può produrre mentre ci sono unità a scorta.
Calcolare da zero il costo di un lotto. Calcolare ogni \(c_{j,t}\) dalla sua definizione costa \(O(m^3)\) passi dentro l'algoritmo di PD; il calcolo incrementale di CostMatrix mantiene \(\Theta(m^2)\).
Dimenticare la scorta finale vuota. La sottoistanza con i periodi \(\{1,\dots,t\}\) termina con la scorta vuota: per questo il lotto nel periodo \(j\) produce esattamente \(D_{j,t}\) unità.
Prendere un piano ottimo per l'unico. L'Esempio 25.1 ha due piani ottimi: l'algoritmo di PD restituisce quello con il periodo \(j\) minimo, perché aggiorna solo con un valore strettamente minore.

In sintesi

Se tutti i costi sono non negativi, il problema senza capacità ha un piano ottimo in cui un periodo produce solo quando la scorta è nulla (Wagner e Whitin), quindi \(x_j=D_{j,t}\) per ogni lotto di produzione.
Il costo \(c_{j,t}\) di ogni lotto si calcola in \(\Theta(m^2)\) passi, e la ricorrenza \(v(t)=\min_j\{v(j-1)+c_{j,t}\}\) dà il valore ottimo in \(\Theta(m^2)\) passi; è un cammino minimo.
La proprietà zero-inventory ordering si basa su una produzione senza limiti: con le capacità non vale.

Quadro riassuntivo dell'esempio.

Istanza	Lower bound	Upper bound	Origine
Esempio 25.1 (senza capacità, \(m=5\))	\(170\)	\(170\)	algoritmo di PD di Wagner e Whitin

Esercizi su questo capitolo: Lot sizing senza capacità (ULS)