Το Πρόβλημα του Σακιδίου (Knapsack Problem): Μαθηματική Βελτιστοποίηση στην Πράξη

Το Πρόβλημα του Σακιδίου (Knapsack Problem)

Φαντάσου έναν ορειβάτη που ετοιμάζει το σακίδιό του. Μπορεί να κουβαλήσει έως 40 κιλά, αλλά έχει στη διάθεσή του έξι αντικείμενα, το καθένα με διαφορετικό βάρος και αξία. Ποια από αυτά πρέπει να πάρει, ώστε το συνολικό όφελος να είναι το μέγιστο δυνατό;

Αυτό είναι το περίφημο Πρόβλημα του Σακιδίου (Knapsack Problem) — μία από τις πιο κλασικές περιπτώσεις μαθηματικής βελτιστοποίησης.

Ο στόχος είναι να επιλεγεί ο ιδανικός συνδυασμός αντικειμένων, έτσι ώστε να επιτυγχάνεται η μέγιστη συνολική αξία, χωρίς να ξεπερνιέται το επιτρεπτό βάρος.

Αν συμβολίσουμε:

• v_i: την αξία του αντικειμένου i
• w_i: το βάρος του αντικειμένου i
• x_i: αν το αντικείμενο i επιλέγεται (0 ή 1)

τότε το συνολικό όφελος δίνεται από τη σχέση:

$$V = \sum_{i=1}^{n} v_i x_i$$

με τον περιορισμό:

$$\sum_{i=1}^{n} w_i x_i \le W$$

όπου W είναι το μέγιστο επιτρεπτό βάρος.

Αυτό το απλό στην περιγραφή, αλλά σύνθετο στη λύση πρόβλημα, αποτελεί θεμελιώδες εργαλείο στη μαθηματική μοντελοποίηση, με εφαρμογές στην οικονομία, τη διοίκηση επιχειρήσεων, την ανάλυση δεδομένων και τον προγραμματισμό υπολογιστών.

---

🔹 Εφαρμογή: Επιλογή αντικειμένων για μέγιστο όφελος

Ο ορειβάτης έχει στη διάθεσή του τα παρακάτω αντικείμενα:

Αντικείμενο	Αξία (vi)	Βάρος (wi)
1	$76	16 kg
2	$40	10 kg
3	$20	6 kg
4	$30	6 kg
5	$24	8 kg
6	$96	16 kg

Το σακίδιο μπορεί να αντέξει έως 40 κιλά.

Στόχος:

Να επιλεγεί ο συνδυασμός αντικειμένων που μεγιστοποιεί την αξία χωρίς να υπερβαίνει το συνολικό βάρος των 40 kg.

Υπολογισμός

Με χρήση μεθόδων βελτιστοποίησης (ή ακόμα και εξαντλητικής δοκιμής), προκύπτει ότι ο βέλτιστος συνδυασμός είναι:

Αντικείμενα 2, 4 και 6

• Συνολικό βάρος: 10 + 6 + 16 = 32 kg
• Συνολική αξία: 40 + 30 + 96 = $166

Εναλλακτικοί συνδυασμοί

Συνδυασμός	Βάρος (kg)	Αξία ($)
1, 2, 5	34	140
2, 4, 5	24	94
1, 4, 6	38	202 ❌
2, 4, 6	32	166 ✅