La formulazione di un problema in una di queste forme è una pratica che si apprende via via che la si applica. Una distinzione molto netta deve esistere fra i dati del problema e le variabili di decisione impiegate. Di solito è bene attenersi alla successione di passi seguente:

(i) definire quelle che appaiono come le variabili di decisione da impiegare;

(ii)   con tali variabili definire un insieme di vincoli in modo che i punti che li soddisfano corrispondano a soluzioni ammissibili del problema in esame;

(iii)   con le stesse variabili definire la funzione obbiettivo;

(iv)   se nascono delle difficoltà, definire un insieme di variabili diverso o aggiungere variabili e iterare il procedimento.

Esempio 1: impiego di un capitale (problema di Zaino Binario)

Un' azienda deve costruire delle centrali. Sono disponibili N possibili località. Sia c_i il costo nel caso si scelga di utilizzare la località i. Sia p_i il profitto atteso se una centrale è localizzata in i. Sia C il capitale totale destinato alla costruzione delle centrali e indichiamo con x_i la i-esima variabile di decisione, che varrà 1 se si sceglie di costruire in i, 0 altrimenti. Il problema di massimizzare il profitto derivante dall' impiego del capitale C, si formula quindi come segue:

max

NOTA - Tale problema viene genericamente indicato come problema di Zaino Binario (C è la capacità dello zaino nel quale si vogliono inserire gli oggetti di maggiore importanza).

Esempio 2: problema con costi fissi (e no)

Una ditta vuole espandere la sua offerta di servizi ai suoi clienti. Sia x_i la quantità offerta del servizio i e sia c_i il costo unitario di tale servizio. Sia p_i il profitto unitario corrispondente. Sia poi k_i il costo fisso che la ditta deve comunque sostenere se desidera offrire il servizio i indipendentemente dalla sua domanda. Risulta naturale introdurre variabili di decisione y_i uguali a 1 se x_i>0 e uguali a 0 se x_i=0. Il modello matematico è allora un modello di PLMI (dove M è un numero molto grande):

max

Esempio 3: copertura di un insieme

Sia N= insieme di possibili localizzazioni

M= insieme di clienti

M_j insieme di clienti serviti adeguatamente se un servizio è localizzato in j (M_j M)

C_j costo di localizzare il servizio in j

Problema: individuare dove localizzare servizi in modo da soddisfare (= coprire) tutti i clienti a costo minimo.

min , j=1,.,n

dove A=[a_ij] e a_ij=1 se i M_j , 0 altrimenti ed e=(1,1,.,1)^T.

Esempio 4: localizzazione ottima

N, M e c_j come nell'esempio precedente. Inoltre:

h_ij    costo per soddisfare il cliente i da j

y_ij frazione della domanda del cliente i soddisfatta da j

min ; y_ij 0

N.B. Si tratta di un problema PLMI.

Esempio 5: problema del commesso viaggiatore (Asymmetric Traveling Salesman Problem)

Digrafo (N,A) con N= insieme dei nodi e A insieme degli archi del digrafo; x_ij = 1 se il nodo j segue il nodo i immediatamente, 0 altrimenti; c_ij costo dell' arco (i,j).

Min

S_{(i,j) A:i U,j N\U} x_ij 1," U N tali che 2 U n-2

N.B. L' ultimo vincolo è equivalente a:

S_{(i,j) A:i,j U} x_ij U - 1, " U N tali che 2 U n-2

detti vincoli di eliminazione dei sottocicli. ATSP è un tipico problema di instradamen