Ottimizzazione sulla divisione di un carico.

[Acquario84]

Suppongo di avere:

- 59 colli,
- ognuno con un suo volume v,
- che io devo spedire tramite 19 camion
- ognuno dei quali può caricare fino a q centimetri cubici.

Per essere economico, ogni carico non può essere inferiore ad un volume m = (volume totale dei colli / 19).

Come procedo?

[vict85]

Se non mi sbaglio stai lavorando con un problema NP-completo...

Se non ricordo male il metodo migliore che si conosce è quello di ordinare i colli in base al volume dal maggiore al minore e poi metterli in modo da equilibrare i carichi. Nel senso che al passo $n$-esimo metti l'$n$-esimo collo nel camion più vuoto.

[vict85]

"Acquario84":
Per essere economico, ogni carico non può essere inferiore ad un volume m = (volume totale dei colli / 19).

Non è detto che anche la miglior disposizione sia secondo il tuo principio economico...

Te lo dimostro con il seguente esempio:

$6$ elementi di volume rispettivamente $1$ $2$ $3$ $4$ $5$ $6$ (per facilità)

Devi metterli in $2$ camion.

Una disposizione ottimale è la seguente:
$A: 1$ $2$ $3$ $4$
$B: 5$ $6$

Volume totale: $21$
$m = 21//2 = 10.5$

Il camion $B$ ha quindi un carico minore di $m$ ma, d'altra parte, nessuna disposizione può fare di meglio.

Quindi la tua condizione è assolutamente irrealistica. Inoltre per ogni carico che eccede quella soglia ce ne deve essere un'altro che non ci arriva. L'ottimale sarebbe che ogni carico avesse esattamente quel volume. Ma ci sono casi, la maggior parte, in cui questo è semplicemente impossibile.

Inoltre dato che questo è un problema $NP$-completo non vedo come tu possa sperare di trovare un buon metodo per arrivare a questo risultato.

P.S: il mio metodo li metterebbe nel seguente modo:
$A: 6$ $3$ $1$
$B: 5$ $4$ $2$
Il fatto che sia equivalente alla disposizione migliore è un caso... Spesso non è così. Ma se ne conosce l'errore massimo.

[Umby2]

"vict85":

Te lo dimostro con il seguente esempio:

Anche il tuo metodo potrebbe avere dei problemi. Tutto dipende da come sono distribuiti i volumi.
Ad esempio, se hai 10-8-7-6-5 il tuo sistema porta alla soluzione:
10-6=16
8-7-5=20

quando la soluzione:
10-8=18
7-6-5=18
è sicuramente migliore.