Min costo calcolo combinatorio

[tora]

Buon giorno a tutti, sono alla ricerca di un algoritmo che mi permetta di fare il seguente mestiere:
Date N imprese ed L lotti di lavorazione (non omogenei) assegnabili, trovare il minor costo complessivo totale assegnando tutti i lotti considerato che:
- i lotti non sono omogenei nelle dimensioni e quindi negli importi;
- ogni impresa può aggiudicarsi un certo numero di lotti k<L, diverso da impresa ad impresa;
- ogni impresa formula delle percentuali di sconto su un importo base differenziate a seconda del numero di lotti che le saranno assegnati. Per ex, se l'impresa A ha la potenzialità per lavorare k=3 lotti allora può formulare degli sconti così fatti:
1 lotto assegnato 3% di sconto
2 lotti assegnati 5% di sconto;
3 lotti assegnati 6% di sconto.

Qualcuno mi saprebbe suggerire un algoritmo di calcolo combinatorio per trovare il minimo costo complessivo?
Grazie
Grazie e saluti a tutti

[delfo52]

forse manca qualche dato; da quale punto di vista ci si deve porre?
Esiste un minimo e un massimo di sconto accettabile?
Il numero di lotti da attribuire DEVE essere diverso tra impresa e impresa, o PUO' esserlo?
E se arriva Bill Gates che da bravo mecenate si offre di fare tutti i lavori con lo sconto del 100 % ?
E come la mettiamo con le bustarelle? L'algoritmo che cerchi, le considera?

Divagazione semiseria sulle bustarelle e sulla corruzione negli appalti (senza nessuna valutazione politica).
Quando nella Francia del Re Sole fu dato l'appalto per costruire Versailles, molto probabilmente il geometra che dirigeva il cantiere, rubacchiando un po' qua e facendosi ungere un po' là, riuscì a farci venire fuori una bella villetta bifamiliare ad Arma di Taggia, per passare la vecchaia in Riviera.
Ma ha costruito e lasciato ai posteri la reggia di Versailles...!!!...
La differenza con i geometri, i faccendieri, e i politicastri nostrani è che si sono fatti la villa al mare, ma...Versailles dov'è ?

[tora]

Grazie innanzitutto per l'attenzione. Mi rendo conto che porre un quesito per motivi di lavoro su un forum di matematica ricreativa non sia il massimo, comunque suppongo che la soluzione, anche se per un matematico può essere semplice o banale, potrebbe essere interessante per molti.
Rispondendo:
- ogni impresa è qualificata per un suo numero di lotti (che può essere uguale o diverso da quello di altre imprese), e quindi le possono essere assegnati al max un numero di lotti pari a quello per cui è qualificata, ammesso che la sua offerta sia competitiva;
- non esiste uno sconto min o max, ma se serve a semplificare l'algoritmo si può fissare un tetto del 50% e un minimo dello 0%, ammesso che essendo dei parametri si possano poi modificare;
- le bustarelle non sono ammesse, come è giusto (non ovvio) che sia.
Per quanto mi riguarda non punto alla Villa in Riviera, in quanto mi sono da poco comperato una buona tenda canadese.
Buona giollata a tutti (come direbbe Luca Giurato)

[giobimbo]

Negli anni '40 dello scorso secolo, gli eventi bellici fanno mobilitare enormi risorse materiali e umane la cui gestione darà sviluppo a un nuovo ramo della matematica applicata, chiamato Ricerca Operativa. Notevole impulso avrà soprattuto negli Stati Uniti, che anche a guerra finita si trovano nel ruolo di superpotenza mondiale e devono agire in tutto il globo. La R.O. si occupa di probabilità, statistica, teoria delle code, delle catene markoviane, grafi, teoria dei giochi, simulazione, programmazione lineare...
E' a quest'ultimo ramo della R.O. che bisogna ricorrere per trovare un algoritmo, non nel calcolo combinatorio. Anzi esiste già, si chiama metodo del simplesso.
Prima di continuare preciso che sto citando a memoria per cui probabilmente ci saranno delle imprecisioni, ma la matematica necessaria secondo me è la Programmazione Lineare.
A grandi linee, si costruisce un sistema di equazioni trasformando le diseguaglianze in uguaglianze tramite l'introduzione di incognite f i t t i z i e, ci sono dei vincoli da rispettare, bisogna massimizzare (o minimizzare) i risultati del sistema di equazioni. Queste delimitano una figura geometrica multidimensionale, una specie di poliedro, il simplesso, e la soluzione si trova in uno dei vertici. Ad essa si giunge partendo da un vertice, riscrivendo il sistema in modo da ottenere una soluzione migliore, toccando altri vertici fino ad arrivare a quello ottimale. Avevo letto di recenti progressi, un metodo che parte dal centro del simplesso invece che da un vertice, mi pare, per cui si arriva più in fretta alla soluzione.

[tora]

Grazie, proverò ad approfondire l'argomento, del quale sinceramente non conosco nulla.
Buona giornata a tutti e buona festa a tutti i tifosi.
t

[vulneraria]

boh....ma scusa, forse non ho capito il problema.

diciamo che ho 10 lotti.

se gli assegno tutti ad una avro' degli sconti da questa azienda, invece se li assegno a 10 diverse non ci sara' alcuno sconto.

viene da se che il meglio e' darle tutte ad una o comunque tenere il numero di aziende totali basso e il numero di lotti per azienda massimo.

[tora]

il fatto stà che la singola azienda può non avere potenzialità per tutti i lotti.
il fatto di assegnare i lotti al minor numero di imprese possibile rientra in un contesto di minimizzazione di costi indiretti di gestione di più rapporti, ma esula dal contesto del problema posto.
In un caso estremamente semplificato se avessi 2 lotti e 2 ditte A e B, e la ditta A mi facesse un ribasso del 5% in caso di assegnazione di un lotto e del 20% in caso di assegnazione di 2 lotti, mentre la ditta B mi facesse uno sconto del 25% sull'unico lotto che potrebbe gestire, è chiaro che mi conviene dare i 2 lotti alla A (a parità di dimensione dei lotti) ed avere quindi un ribasso complessivo del 20% piuttosto che assegnarne uno alla B (con il 25%) e il rimanente ad A ma questa volta al 5%, con un ribasso complessivo del 15% (media dei due ribassi).

Aumentando il numero di imprese, di lotti, e rendendo questi ultimi non omogenei la faccenda si complica
Buona serata

[vulneraria]

boh...a me pare che l'unica variabile che puoi gestire in questo problema e' lo sconto, e lo sconto sale se le aziende hanno piu' lotti.
percio' l'unica cosa che puoi fare e' dare piu' lotti possibili alle aziende che possono gestirne tanti.

visto che tutti i restanti numeri sono casuali (nr lotti, grandezza lotti, nr aziende ) e' l'unico ragionamento sensato che puoi fare.

altrimenti manca qualche dato.

[giobimbo]

Se non ci sono vincoli, un modello del problema potrebbe essere quello di un grafo in cui si deve trovare il percorso minimo. Faccio un esempio.
Un grosso lavoro viene diviso in 5 lotti a, b, c, d, e; all'appalto partecipano 4 imprese A, B, C e D. Scrivo X={x, y, xy} a indicare che l'impresa X fa un'offerta di un certo prezzo per il lotto x, fa un'offerta di un certo prezzo per il lotto y, fa un'offerta per i due lotti x e y insieme, a un prezzo che è inferiore alla somma dei singoli prezzi di x e di y.
Le varie offerte siano dunque:

A = {a, c, ac}
B = {a, b, bc, e}
C = {bde, c, d}
D = {b, bd, cd, d}

I percorsi sono dunque, indicativamente:

ac - bd - e
ac - bde
a - bc - d - e
a - b - cd - e

da cui ricaviamo il grafo sotto, a sinistra. Ma non è detto che l'offerta cumulativa xy della ditta X sia migliore della somma delle singole offerte x della ditta Y e y della ditta Z, per cui il grafo finale sarà quello a destra. La strada più breve per andare da 0 a 1 nel grafo a destra ci darà le assegnazioni dei lotti il cui totale è minimo. Nella teoria dei grafi ci sono due algoritmi per trovare il percorso minimo, quelli di Dijkstra e di Bellman-Ford.

[giobimbo]

La strada più breve per andare da 0 a 1 nel grafo a destra ci darà le assegnazioni dei lotti il cui totale è minimo.

La frase è mal formulata, per chiarire faccio un esempio numerico.

Con riferimento al mio intervento precedente, supponiamo che le offerte siano state, in migliaia di euro:

A = {a=2, c=3, ac=4}
B = {a=1, b=1, bc=3, e=5}
C = {bde=10, c=4, d=6}
D = {b=2, bd=5, cd=8, d=4}

Per i lavori al lotto a ci sono due offerte, prendiamo la più piccola e nel grafo scriviamo 1 al posto di a; lo stesso per il lotto b e nel grafo scriviamo 1 al posto di b; la più piccola offerta per il lotto c vale 3, scriviamo 3 al posto di c; eccetera. Il risultato finale è il grafo sotto, dove le linee in rosso indicano il percorso minimo il cui valore è dato dalla somma dei singoli tratti. L'ente appaltatore spenderà un minimo di 1+3+4+5=13 mila euro, mentre i lotti vengono così assegnati:

a -> impresa B
bc -> impresa B
d -> impresa D
e -> impresa B