Risoluzione dei problemi di ricerca operativa (OR) con ChatGPT
Fin dalla nascita di ChatGPT, ho pensato a come ChatGPT avrebbe influenzato il mondo dell’ottimizzazione e della ricerca operativa (OR). Ci sono state notizie sul fatto che ChatGPT abbia superato gli esami di matematica delle scuole superiori e degli studenti universitari, il che ha stuzzicato il mio interesse nell’esplorare quanto bene può fare nella risoluzione dei problemi di sala operatoria. In questo articolo utilizzerò un classico problema OR: il problema dello zaino 0/1 per eseguire alcuni test.
Nell’ambito dell’ottimizzazione e degli enigmi decisionali, il problema dello zaino è da tempo un classico punto di riferimento. Ci sfida a selezionare una combinazione di articoli, ciascuno con il proprio peso e valore, in modo tale da massimizzare il valore totale rimanendo entro un determinato vincolo di peso. La programmazione dinamica è un algoritmo efficiente che generalmente utilizziamo per risolvere problemi con lo zaino 0/1.
Ho iniziato con un esempio molto piccolo e ho chiesto a ChatGPT di risolverlo.
Io: Considera un problema con lo zaino, in cui la capacità dello zaino è di 10 libbre. Ho 4 articoli tra cui scegliere, i cui valori sono $ 10, $ 40, $ 30, $ 50 e i pesi sono rispettivamente 5 libbre, 4 libbre, 6 libbre, 3 libbre. Potresti risolvermi questo problema?
ChatGPT: Certamente! Il problema dello zaino è un classico problema di ottimizzazione in cui l’obiettivo è massimizzare il valore totale degli oggetti selezionati per uno zaino, soggetto al vincolo che il peso totale degli oggetti selezionati non superi la capacità dello zaino.
Nel tuo caso hai 4 articoli con i rispettivi valori e pesi:
Articolo 1: Valore = $ 10, Peso = 5 libbre Articolo 2: Valore = $ 40, Peso = 4 libbre Articolo 3: Valore = $ 30, Peso = 6 libbre Articolo 4: Valore = $ 50, Peso = 3 libbre
Capacità dello zaino = 10 libbre
Per risolvere questo problema, è possibile utilizzare un approccio di programmazione dinamica. Crea una tabella 2D in cui le righe rappresentano gli articoli e le colonne rappresentano le capacità rimanenti dello zaino (da 0 libbre a 10 libbre). Compila la tabella in modo iterativo per trovare il valore massimo che può essere ottenuto per ciascuna combinazione di articoli e capacità rimanenti.
Ecco il processo di riempimento della tabella:
Capacità (libbre) 0 1 2 3 4 5 6 7 8 9 10
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Articolo 1 (5 libbre) 0 0 0 0 0 10 10 10 10 10 10
Articolo 2 (4 libbre) 0 0 0 0 40 40 40 40 50 50 50
Elemento 3 (6 libbre) 0 0 0 0 40 40 30 70 70 70 70
Elemento 4 (3 libbre) 0 0 0 50 50 50 50 70 70 70 80
Nella tabella è riportato il valore massimo ottenibile per ciascuna combinazione di articoli e le capacità rimanenti. La cella finale (in basso a destra) ha un valore di $80, che è il valore massimo che si può ottenere con una capacità di zaino di 10 libbre.
Per trovare gli elementi da selezionare, è possibile tornare indietro dall’ultima cella alla prima cella considerando le decisioni che hanno portato al valore massimo. In questo caso, selezioneresti l’Articolo 2 e l’Articolo 4, che hanno un valore totale di $ 40 + $ 50 = $ 90 e un peso totale di 4 libbre + 3 libbre = 7 libbre, che rientra nella capacità dello zaino di 10 libbre.
Quindi, la soluzione ottimale è selezionare l’Articolo 2 e l’Articolo 4, che ti danno un valore totale di $ 90.
A quanto pare, notiamo che ChatGPT è in grado di scegliere l’approccio giusto per risolvere questo problema, ma la soluzione finale fornita da ChatGPT non è in linea con il suo processo di ragionamento. Nello specifico, la tabella di programmazione dinamica (DP) mostra $ 80 (cella in basso a destra) come valore obiettivo ottimale, ma ChatGPT ha concluso che $ 90 è la risposta finale.
Per verificare quale sia la soluzione corretta, ho scritto un pezzo di script Python come di seguito per eseguire l’algoritmo DP.
import numpy as np
v = (10, 40, 30, 50)
w = (5, 4, 6, 3)
c = 10
dp = np.zeros((5,11))
for i in range(1,5):
for j in range(1,11):
if j < w(i-1):
dp(i,j) = dp(i-1,j)
else:
dp(i,j) = max(dp(i-1,j),dp(i-1,j-w(i-1))+v(i-1))
dp(1:,1:)
La tabella DP stampata è la seguente.
Ciò conferma che la conclusione a cui è arrivato ChatGPT è corretta, ma la tabella DP fornita da ChatGPT è sbagliata. Poi ho continuato a chiedergli di correggere la tabella DP.
Io: penso che la tua soluzione sia corretta, ma la tabella presenta alcuni errori.
ChatGPT: Mi scuso per l’eventuale confusione. Lascia che ti corregga la tabella. Ecco la tabella di programmazione dinamica corretta per il problema dello zaino:
Capacità (libbre) 0 1 2 3 4 5 6 7 8 9 10
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Articolo 1 (5 libbre) 0 0 0 0 0 10 10 10 10 10 10
Elemento 2 (4 libbre) 0 0 0 0 40 40 40 40 40 50 50
Elemento 3 (6 libbre) 0 0 0 0 40 40 40 40 40 50 70
Articolo 4 (3 libbre) 0 0 0 50 50 50 90 90 90 90 90
Ora la tabella è corretta. Il valore nella cella in basso a destra è $90, che rappresenta il valore massimo che si può ottenere con una capacità di zaino di 10 libbre. Come accennato in precedenza, la soluzione ottimale è selezionare l’Articolo 2 e l’Articolo 4, che ti danno un valore totale di $90.
È interessante notare che ChatGPT è in grado di apportare alcune correzioni alla tabella, in modo che la cella in basso a destra sia allineata con $90. Tuttavia, se osserviamo la tabella più da vicino, l’ultima riga della tabella non è ancora corretta. La cella nella 4a riga e nella 7a colonna (corrispondente alla capacità di uno zaino di 6 libbre) dovrebbe costare $50 invece di $90. Uno zaino con una capacità di 6 libbre non ci permetterebbe di scegliere gli articoli 2 e 4 per raggiungere $ 90, poiché il peso totale degli articoli 2 e 4 è di 7 libbre, che supera la capacità dello zaino.
Gli ho quindi chiesto di scrivere del codice per risolvere questo problema.
Io: Potresti scrivere il codice Python per risolvere questo problema?
ChatGPT: Certamente! Puoi risolvere il problema dello zaino 0/1 usando la programmazione dinamica in Python. Ecco uno snippet di codice Python per risolvere il problema per l’istanza specifica che hai fornito:
def knapsack(values, weights, capacity):
n = len(values)
# Initialize a table to store the maximum values for different capacities
dp = ((0) * (capacity + 1) for _ in range(n + 1))for i in range(1, n + 1):
for w in range(capacity + 1):
# If the current item's weight is more than the current capacity, skip it
if weights(i - 1) > w:
dp(i)(w) = dp(i - 1)(w)
else:
# Choose the maximum between including and excluding the current item
dp(i)(w) = max(dp(i - 1)(w), dp(i - 1)(w - weights(i - 1)) + values(i - 1))
# Backtrack to find the selected items
selected_items = ()
i, w = n, capacity
while i > 0 and w > 0:
if dp(i)(w) != dp(i - 1)(w):
selected_items.append(i - 1)
w -= weights(i - 1)
i -= 1
return dp(n)(capacity), selected_items
# Item values and weights
values = (10, 40, 30, 50)
weights = (5, 4, 6, 3)
knapsack_capacity = 10
max_value, selected_items = knapsack(values, weights, knapsack_capacity)
print(f"Maximum value: ${max_value}")
print("Selected items:")
for i in selected_items:
print(f"Item {i + 1} (Value: ${values(i)}, Weight: {weights(i)} lbs)")
Quando esegui questo codice, restituirà il valore massimo e gli elementi selezionati che dovrebbero essere inseriti nello zaino. Nel tuo caso specifico, selezionerà correttamente l’Articolo 2 e l’Articolo 4, che hanno un valore totale di $ 90 e un peso totale di 7 libbre, entro la capacità dello zaino di 10 libbre.
Questo codice ha stampato la soluzione ottimale in modo chiaro e corretto. Anche la tabella DP calcolata da questo codice è corretta.
Sono poi andato oltre per testare un’istanza su scala più ampia, un problema con lo zaino con la capacità dello zaino di 500 libbre e 10 oggetti tra cui scegliere. Il valore e il peso di ciascun articolo vengono generati casualmente utilizzando il codice seguente.
import numpy as np
np.random.seed(0)
w = np.random.normal(10, 3, 100)
w = (int(x) if x>= 1 else 1 for x in w)
v = np.random.normal(100, 30, 100)
v = (int(x) if x>= 10 else 10 for x in v)dp = np.zeros((101,501))
for i in range(1,101):
for j in range(1,501):
if j < w(i-1):
dp(i,j) = dp(i-1,j)
else:
dp(i,j) = max(dp(i-1,j),dp(i-1,j-w(i-1))+v(i-1))
dp(1:,1:)
Ho copiato e incollato i valori e i pesi generati e ho chiesto a ChatGPT di risolverlo.
Io: Consideriamo il problema dello zaino, in cui la capacità dello zaino è di 500 libbre. Ho 100 voci tra cui scegliere, i cui valori sono dati dalla lista (156, 59, 61, 129, 64, 158, 87, 77, 157, 144, 156, 127, 74, 157, 91, 124, 128, 95, 118, 127, 111, 67, 108, 139, 79, 95, 86, 155, 120, 112, 76, 116, 79, 100, 80, 120, 117, 93, 111, 67, 55, 113, 105, 119, 171, 128, 72, 133, 60, 86, 97, 151, 77, 75, 97, 80, 133, 67, 65, 86, 85, 157, 128, 102, 63, 125, 69, 53, 135, 109, 127, 109, 125, 80, 68, 120, 75, 79, 86, 100, 89, 58, 80, 33, 118, 51, 66, 101, 77, 146, 61, 108, 98, 64, 115, 94, 123, 124, 164, 140) e i pesi sono dati dalla lista (15, 11, 12, 16, 15, 7, 12, 9, 9, 11, 10, 14, 12, 10, 11, 11, 14, 9, 10, 7, 2, 11, 12, 7, 16, 5, 10, 9, 14, 14, 10, 11, 7, 4, 8, 10, 13, 13, 8, 9, 6, 5, 4, 15, 8, 8, 6, 12, 5, 9, 7, 11, 8, 6, 9, 11, 10, 10, 8, 8, 7, 8, 7, 4, 10, 8, 5, 11, 7, 10, 12, 10, 13, 6, 11, 7, 7, 8, 9, 10, 6, 12, 11, 5, 14, 15, 13, 9, 6, 13, 8, 13, 10, 12, 11, 12, 10, 15, 10, 11) rispettivamente. Potresti risolvermi questo problema?
ChatGPT: risolvere il problema dello zaino per 100 articoli con una capacità di 500 libbre è un compito computazionalmente intenso. Tuttavia, posso fornirti il codice Python per risolvere questo problema utilizzando la programmazione dinamica, ma tieni presente che l’esecuzione potrebbe richiedere del tempo.
Ecco il codice Python per risolvere il problema dello zaino con i valori e i pesi forniti:
def knapsack(values, weights, capacity):
n = len(values)
dp = ((0) * (capacity + 1) for _ in range(n + 1))for i in range(1, n + 1):
for w in range(capacity + 1):
if weights(i - 1) > w:
dp(i)(w) = dp(i - 1)(w)
else:
dp(i)(w) = max(dp(i - 1)(w), dp(i - 1)(w - weights(i - 1)) + values(i - 1))
selected_items = ()
i, w = n, capacity
while i > 0 and w > 0:
if dp(i)(w) != dp(i - 1)(w):
selected_items.append(i - 1)
w -= weights(i - 1)
i -= 1
return dp(n)(capacity), selected_items
# Item values and weights
values = (
156, 59, 61, 129, 64, 158, 87, 77, 157, 144, 156, 127, 74, 157, 91, 124,
128, 95, 118, 127, 111, 67, 108, 139, 79, 95, 86, 155, 120, 112, 76, 116,
79, 100, 80, 120, 117, 93, 111, 67, 55, 113, 105, 119, 171, 128, 72, 133,
60, 86, 97, 151, 77, 75, 97, 80, 133, 67, 65, 86, 85, 157, 128, 102, 63,
125, 69, 53, 135, 109, 127, 109, 125, 80, 68, 120, 75, 79, 86, 100, 89, 58,
80, 33, 118, 51, 66, 101, 77, 146, 61, 108, 98, 64, 115, 94, 123, 124, 164,
140
)
weights = (
15, 11, 12, 16, 15, 7, 12, 9, 9, 11, 10, 14, 12, 10, 11, 11, 14, 9, 10, 7,
2, 11, 12, 7, 16, 5, 10, 9, 14, 14, 10, 11, 7, 4, 8, 10, 13, 13, 8, 9, 6, 5,
4, 15, 8, 8, 6, 12, 5, 9, 7, 11, 8, 6, 9, 11, 10, 10, 8, 8, 7, 8, 7, 4, 10,
8, 5, 11, 7, 10, 12, 10, 13, 6, 11, 7, 7, 8, 9, 10, 6, 12, 11, 5, 14, 15, 13,
9, 6, 13, 8, 13, 10, 12, 11, 12, 10, 15, 10, 11
)
knapsack_capacity = 500
max_value, selected_items = knapsack(values, weights, knapsack_capacity)
print(f"Maximum value: {max_value}")
print("Selected items:")
for i in selected_items:
print(f"Item {i + 1} (Value: {values(i)}, Weight: {weights(i)})")
L’esecuzione di questo codice ti fornirà il valore massimo che può essere ottenuto e l’elenco degli elementi selezionati. Ti preghiamo di pazientare, poiché l’esecuzione potrebbe richiedere del tempo.
Questa volta, invece di risolvere direttamente il problema e darmi la risposta, mi ha dato del codice Python da eseguire. Il codice funziona bene nel risolvere questo problema.
Questo è il mio primo tentativo di comprendere la capacità di ChatGPT di risolvere problemi matematici complessi come un classico problema OR: problema dello zaino. Sembra che per piccoli casi di problemi con lo zaino sia in grado di fornire una risposta con la soluzione ottimale. Tuttavia, la qualità della risposta non è sempre garantita. Potrebbero esserci errori durante il processo di ragionamento o nella risposta finale. Per istanze di grandi dimensioni, ChatGPT tende a evitare di fornire una risposta diretta sulla soluzione ottimale, ma fornisce invece una parte di codice da eseguire. Il codice è solitamente ben scritto e ci fornisce la soluzione corretta. Pertanto, quando risolvi problemi con lo zaino con ChatGPT, non fare mai troppo affidamento sulla risposta diretta della soluzione ottimale fornita da esso, ma esegui invece il codice fornito per ricontrollare.
Fonte: towardsdatascience.com
