Problema di ottimizzazione da dove iniziare, quali algoritmi usare? [chiuso]

Question

Problema di ottimizzazione da dove iniziare, quali algoritmi usare? [chiuso]

#1 da (3 voti)
#2 da (1 voti)

0

Ho un problema di ottimizzazione e mi chiedevo da dove iniziare per poterlo risolvere. Penso che possa essere risolto con un algoritmo NP-completo ma non sono sicuro da dove iniziare. Il problema è il seguente:

Ci sono N tipi di rettangoli colorati dello stesso formato che devono essere stampati.
Per ogni tipo c'è un conteggio minimo che deve essere stampato.
Organizzarli su una placca da stampa costa X quantità di denaro, ogni pezzo di carta stampata costa Y ammontare di denaro.
Sono tutte della stessa dimensione, quindi la quantità massima di rettangoli su un foglio di carta viene fornita come input, ovviamente puoi organizzarne una quantità inferiore all'importo massimo.
Potrebbero esserci più pezzi stampati rispetto all'importo minimo richiesto.

Qual è il modo migliore per combinare i rettangoli con l'input dato di tipi e conteggio e prezzi per l'organizzazione e la stampa, quindi la quantità di X + Y deve essere la più bassa?

Dove dovrei iniziare con questo, suona davvero come un problema di NP dove provo tutte le combinazioni di pezzi di carta e registra il miglior risultato.

algorithms optimization np-complete

posta ziGi 15.01.2016 - 15:03

fonte

2 risposte

Leggi altre domande sui tag algorithms optimization np-complete

ID nel diagramma delle classi il mio modello di software ha una sorta di dipendenza ciclica

score 3 · Answer 1

Quello che stai cercando di fare è la variazione di un problema di imballaggio del contenitore . Effettivamente stai mettendo gli oggetti in bidoni (placche) e cercando di minimizzare lo spazio sprecato, dal momento che nel tuo esempio lo spazio sprecato corrisponde direttamente ai soldi persi. L'articolo di Wikipedia mostra come questo può essere risolto / risolto.

Potresti finire con un problema di ottimizzazione, perché hai anche un numero variabile di elementi da inserire. In questo caso si avrebbe un problema di imballaggio del contenitore incorporato in un ciclo di ottimizzazione, che eseguiva più problemi di imballaggio del contenitore tentando di trovare il profitto ottimale che soddisfa i propri vincoli.

score 1 · Answer 2

Ho fatto un periodo in una grande azienda tipografica. Credo che ci siamo imbattuti nello stesso problema. Fammi riformulare. I vincoli:

Una lastra da stampa industriale costa X dollari per il layout e la fabbricazione. Non è un importo insignificante.
Ogni foglio stampato costa Y dollari. È un numero più piccolo ma può essere aggiunto.
Ci sono N "rettangoli" unici da stampare. Per motivi di spiegazione, possiamo dire che sono colori diversi, ma in realtà sono solo pagine diverse di una rivista, lettere diverse, poster diversi o altro.
Puoi disporre questi rettangoli su qualsiasi numero di piastre in qualsiasi configurazione desideri. Tieni presente che le lastre costano denaro ed è complicato tenere traccia dei numeri di rettangoli stampati quando sono su più di un piatto.
Hai bisogno di un certo numero di ciascun rettangolo. Date le complicazioni della posa di lastre, probabilmente ne stamperete alcune troppe. Ma non puoi mai stampare troppo poco.

Non è ovvio, ma questi dati forniscono un sistema di equazioni lineari:

(# of plates * plate cost) + (# of sheets * sheet cost) = total cost
# of red rectangles >= min red
# of blue rectangles >= min blue
# of yellow rectangles >= min yellow

# of red rectangles = sum(
    # of red rectangles on plate p * # sheets printed from plate p)
# of blue rectangles = sum(
    # of blue rectangles on plate p * # sheets printed from plate p)

etc...

Quindi ... tutto ciò che devi fare è risolvere il sistema di equazioni lineari per minimizzare total cost . Facile, giusto? Non proprio. La risoluzione dei sistemi lineari è un grande argomento e non meno NP-hard di qualsiasi altra ottimizzazione. Per darti un'idea di quanto sia grande:

Per essere onesti, l'argomento è troppo grande per un Q & A. La mia speranza è che vederlo come un sistema lineare potrebbe darti un punto di ingresso, ma la verità è che è roba piuttosto complicata. Senza alcune competenze interne, potrebbe essere necessario accontentarsi di "abbastanza buono". Se il tuo progetto ha un po 'di soldi a disposizione, prendi in considerazione di portare un consulente per un breve periodo.