Ricerca operativa 2 e metodi e modelli per il supporto alle decisioni

GIOCHI STRATEGICI

I giochi strategici sono modelli matematici che descrivono situazioni in cui due o più giocatori prendono decisioni strategiche, tenendo conto delle azioni degli altri giocatori, al fine di massimizzare il proprio guadagno. Inoltre, ogni giocatore ha un insieme di strategie tra cui scegliere, e il risultato del gioco dipende dalle scelte di tutti i giocatori. Ogni giocatore ha un obiettivo che cerca di raggiungere, che può essere massimizzare il proprio guadagno, minimizzare le proprie perdite o perseguire un risultato specifico. Inoltre, il gioco non è ripetuto ovvero ogni giocatore agisce una sola volta e le scelte dei vari giocatori vengono effettuate simultaneamente senza accordarsi tra loro.

Payoff:

Una matrice di payoff rappresenta le ricompense o i guadagni che i giocatori ottengono in base alle diverse combinazioni delle loro scelte strategiche. Ogni giocatore ha una riga nella matrice di payoff che indica le sue ricompense in base

alle sue scelte e alle scelte degli altri giocatori.)

ELEMENTI DEI GIOCHI STRATEGICI:

• Numero giocatori (N), ognuno dei quali dispone di un insieme di azioni o strategie possibili.
• • u (s)i di unità (PAYOFF) che descrive il suo profito rispetoE agisce in base a una funzioneall’esito del gioco

ESITO

Un (o profito) del gioco in cui è la strategia scelta dal• giocatore i-esimo RISULTATO

Ad ogni esito corrisponde un del gioco.

EQUILBRIO DI NASHEquilibrio di Nash può essere rappresentato come segue:

Sia N = (S, u) un gioco, dove:

• S = {S1, S2, ..., Sn} rappresenta l'insieme delle strategie disponibili per i giocatori.
• • u = (u1, u2, ..., un) rappresenta il vetore delle funzioni di u�lità per i giocatori, che assegna• una pay-off a ciascun giocatore per ogni combinazione di scelte strategiche.

Un profilo di strategia S* = (S1*, S2*, ..., Sn*) rappresenta un equilibrio di Nash se soddisfa leseguen� condizioni per ogni giocatore i:

1. ...

Giocatore i non ha l'incenzo a deviare unilateralmente dalla sua strategia corrente: u_i(S_i, S_-i) ≥ u_i(S_i, S*_-i) per ogni S_i ≠ S_i, dove S_-i rappresenta il profilo di strategia di tutti i giocatori tranne il giocatore i.

Data la strategia degli altri giocatori, giocatore i ha scelto la strategia che massimizza la sua pay-off: u_i(S_i, S_-i) ≥ u_i(S*_i, S'_-i) per ogni S'_-i, dove S'_i rappresenta una possibile strategia alternativa per il giocatore i.

Queste condizioni indicano che nessun giocatore ha un guadagno unilaterale deviando dalla sua strategia corrente, e quindi nessuno ha l'incenzo a cambiare la sua scelta nel contesto delle scelte degli altri giocatori. Un equilibrio di Nash rappresenta quindi uno stato di stabilità nel gioco, in cui tutte le strategie dei giocatori sono coerenti tra loro.

CONSIDERAZIONI:

• Un gioco può ammetere più di un equilibrio di Nash
• Non tutti i giochi hanno strategie pure

Ammetono un equilibrio di Nash• Se un gioco ammete almeno un equilibrio di Nash, allora esiste almeno un esito in cui ogni• giocatore ha a disposizione una strategia dominante. Contrariamente ad altre situazioni, in un equilibrio di Nash i giocatori possono ottenere• un vantaggio.

PROGRAMMAZIONE MATEMATICA

La programmazione matematica è una disciplina che si occupa di risolvere problemi di ottimizzazione matematica. Si tratta di un approccio che utilizza modelli matematici per determinare la migliore soluzione possibile a un dato problema, considerando vincoli e obiettivi specifici.

3 passi fondamentali per costruire un modello di programmazione matematica senza utilizzare esempi specifici:

Determinazione delle variabili decisionali:

1. Nel primo passo, si identificano le variabili che rappresentano le quantità o le decisioni che devono essere determinate per risolvere il problema. Si assegna un nome a ciascuna variabile e si definisce il loro dominio,

1. Definizione delle variabili decisionali: l'insieme di valori ammissibili che possono assumere.

2. Definizione della funzione obiettivo: la funzione obiettivo specifica l'obiettivo del problema di ottimizzazione. Può essere un obiettivo di massimizzazione o minimizzazione, a seconda di ciò che si desidera raggiungere. La funzione obiettivo dipende dalle variabili decisionali e rappresenta la quantità che si vuole ottimizzare.

3. Definizione dei vincoli: i vincoli rappresentano le restrizioni o le relazioni che devono essere soddisfatte nel problema. Questi vincoli definiscono le relazioni logiche tra le variabili decisionali e possono limitare le loro combinazioni o imporre requisiti specifici. I vincoli aiutano a definire lo spazio delle soluzioni ammissibili e guidano la ricerca della soluzione ottimale.

Una volta definiti questi 3 elementi (variabili decisionali, funzione obiettivo e vincoli), si può procedere alla risoluzione del modello utilizzando algoritmi e metodi di ottimizzazione.

L'obiettivo finale è trovare la migliore soluzione possibile che massimizzi o minimizzi la funzione obiettivo, rispettando tutti i vincoli specificati nel problema di programmazione matematica.

VARIABILI DECISIONALI

Rappresentano le quantità o le decisioni che devono essere determinate per risolvere il problema. Esistono diverse tipologie di variabili decisionali, a seconda delle caratteristiche del problema e dei vincoli applicabili. Ecco alcune delle tipologie comuni di variabili decisionali:

1. Variabili continue: Le variabili continue possono assumere valori in un intervallo continuo. Non ci sono restrizioni sulla natura dei valori che possono assumere. Ad esempio, possono rappresentare quantità di prodotti, risorse o decisioni con una gamma continua di possibilità.
2. Variabili binarie: Le variabili binarie possono assumere solo due valori, solitamente 0 o 1. Le variabili binarie possono essere suddivise in due categorie principali:

Le variabili indicatrici, anche chiamate variabili di selezione, sono utilizzate per indicare la presenza o l'assenza di determinate condizioni o opzioni. Assumono un valore di 1 se una certa condizione è soddisfatta e 0 altrimenti. Queste variabili sono spesso utilizzate per modellare decisioni di attivazione o disattivazione di una determinata opzione. (utilizzare per indicare l'appartenenza di un elemento a un determinato insieme)

Variabili logiche:

• Le variabili logiche, o variabili booleane, sono utilizzate per rappresentare decisioni. Queste variabili vengono utilizzate per modellare scelte tra due opzioni o per rappresentare la verità o la falsità di una condizione.

Variabili intere:

Le variabili intere possono assumere solo valori interi. Sono utilizzate quando le soluzioni ammissibili richiedono valori discreti o rappresentano quantità contabili.

Variabili miste:

Le variabili miste combinano caratteristiche delle variabili continue,

binarie e intere. Alcune variabili possono assumere valori continui, mentre altre sono limitate a valori interi o binari. La scelta della tipologia di variabili decisionali dipende dalle caratteristiche specifiche del problema e dalle restrizioni applicabili. È importante selezionare la tipologia di variabili che meglio rappresenta il contesto del problema e permette di modellare efficacemente le decisioni da prendere. Questa scelta influenzerà la selezione degli algoritmi o dei metodi di ottimizzazione utilizzati per risolvere il problema.

VARIABILI INDICATRICI:

• SELEZIONE
• ASSOCIAZIONE
• VARIABILI INDICATRICI

VARIABILI INDICATRICI DI SELEZIONE

Dato un insieme X discreto e finito (insieme base), la selezione di un sottoinsieme Y di elementi di X può essere descritta da un vettore di incidenza di Y. X può essere descritta da un vettore y ∈ {0,1} |X|.

PROBLEMI DI OTTIMIZZAZIONE COMBINATORIA

Un problema di ottimizzazione combinatoria in genere cerca tra elementi

La ottimizzazione combinatoria spesso consiste nella selezione di elementi di Q che formano una COVERING, PACKING o PARTITIONING dell'insieme X.

COVERING

Il concetto di "covering" si riferisce all'azione di selezionare un insieme di elementi in modo che essi coprano completamente un altro insieme di elementi. L'obiettivo del covering è garantire che ogni elemento dell'insieme da coprire sia incluso almeno una volta nell'insieme di elementi selezionati. Ad esempio, se hai un insieme di città da visitare, il covering può implicare la scelta di percorsi che coprono tutte le città, in modo che ogni città sia visitata almeno una volta.

Quindi: ..., Q) di elementi di Q (cioè di sottoinsiemi di X) tale che:

un COVERING è una selezione (Q 1 pMATRICE DI INCIDENZA COVERING

PACKING

Il concetto di "packing" si riferisce alla disposizione o organizzazione di oggetti o elementi in modo da occupare lo

spazio in modo efficiente. In termini di ottimizzazione, il packing riguarda la selezione di un insieme di elementi in modo da massimizzare l'utilizzo dello spazio disponibile. (Ad esempio, nel problema del packing dei bagagli, l'obiettivo è selezionare oggetti di diverse dimensioni e disporli nel modo più efficiente all'interno di una valigia, in modo da sfruttare al massimo lo spazio disponibile.)

Quindi, un PACKING è una soluzione (Q1, ..., Qn) di elementi di Q tale che:

1. MATRICE DI INCIDENZA PACKING
2. PARTITIONING

Il concetto di "partitioning" si riferisce alla divisione di un insieme di elementi in sottoinsiemi disgiunti o gruppi in base a determinate proprietà o criteri. Nel contesto dell'ottimizzazione, il partitioning implica la suddivisione di un insieme di elementi in sottoinsiemi.