Ricerca operativa - problema dello zaino

Homework 1

L’homework in esame consiste nello scegliere un oggetto da ciascuna categoria, facendo attenzione a non

superare la capienza massima dello zaino di 25 Kg.

Si deve fare attenzione ad ottenere i massimi punti di survival senza eccedere la capacità massima dello

zaino.

POSSIBILE RISOLUZIONE DEL PROBLEMA :

Innanzitutto, indichiamo con W la capacità massima dello zaino e con N il numero degli n oggetti che

compongono il problema.

A ciascun oggetto, si assegna un peso w ed un survival s .

j j

Il problema, consiste quindi nell’individuare un sottoinsieme di oggetti da inserire nello zaino tale da

massimizzare il survival totale senza eccedere la capacità W dello zaino.

Nella risoluzione dell’esercizio, sono state introdotte t variabili di decisine x , x , … , x , dove per ogni j =

1 2 n

1,2, … , n

1, se l’oggetto j è inserito nello zaino;

xj = 0, altrimenti.

Si è scelto di svolgere il problema di PLI utilizzando il programma Excel :

Sono state create delle tabelle in cui sono stati immessi valori relativi (weight, survival, var.decisione) a

ciascun oggetto da portare (Food, Water, Shelter, Defense).

Sotto ad ognuna di esse, è stata posta una cella in cui, l’apposito risolutore immetterà un valore binario.

Il risolutore (conseguentemente all’impostazione di specifici vincoli, che verranno illustrati in seguito)

sceglierà, per ogni categoria, il “miglior” oggetto da portare, settando ad 1 l’apposita cella.

VINCOLI IMPOSTATI NEL RISOLUTORE DEL PROGRAMMA EXCEL :

1) Le celle utilizzate come “variabili decisionali” sono state poste come “binarie” ( in modo da essere settate

ad 1 nel caso in cui si decidesse di mettere l’oggetto nello zaino e 0 nel caso in cui l’oggetto non viene posto

nello zaino).

2) Le celle contenenti la somma delle variabii decisionali, per fare in modo di prendere solamente un

oggetto, per ciascuna categoria sono vincolate ad essere ad 1.

3) L’ultimo vincolo impostato, riguarda nel porre il massimo peso consentito minore (o uguale) a 25.