Caricare documenti e articoli online 
INFtub.com è un sito progettato per cercare i documenti in vari tipi di file e il caricamento di articoli online.
Meneame
 
Non ricordi la password?  ››  Iscriviti gratis
 

PROGRAMMAZIONE LINEARE INTERA (PLI)

informatica




Inviare l'articolo a Facebook Inviala documento ad un amico Appunto e analisi gratis - tweeter Scheda libro l'a WhatsApp - corso di

Programmazione Lineare Intera (PLI)


Molto spesso il modello matematico di un problema di pianificazione assume la forma di un problema di ottimizzazione lineare nel quale le variabili sono vincolate ad assumere solo valori interi (PLI). In altri casi si hanno sia variabili intere che no e si parla di Programmazione Lineare Mista-Intera (PLMI). Quando le variabili possono prendere solo 222e41c i valori 0 o 1, si parla di Programmazione Lineare Binaria (PL0-1). Quest’ ultimo caso è tipico dei problemi di Ottimizzazione Combinatoria (POC) dove si ha un insieme finito di elementi ciascuno con un suo peso e una famiglia (di solito definita implicitamente da un algoritmo di appartenenza) di sottoinsiemi ammissibili e se ne vuole trovare uno che abbia peso totale minimo.




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 ci il costo nel caso si scelga di utilizzare la località i. Sia pi il profitto atteso se una centrale è localizzata in i. Sia C il capitale totale destinato alla costruzione delle centrali e indichiamo con xi 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 xi la quantità offerta del servizio i e sia ci il costo unitario di tale servizio. Sia pi il profitto unitario corrispondente. Sia poi ki 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 yi uguali a 1 se xi>0 e uguali a 0 se xi=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

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

Cj 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=[aij] e aij=1 se i Mj , 0 altrimenti ed e=(1,1,…,1)T.


Esempio 4: localizzazione ottima


N, M e cj come nell’esempio precedente. Inoltre:


hij        costo per soddisfare il cliente i da j

yij         frazione della domanda del cliente i soddisfatta da j


min     ; yij 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; xij = 1 se il nodo j segue il nodo i immediatamente, 0 altrimenti; cij costo dell’ arco (i,j).


Min    

S(i,j) A:i U,j N\U xij 1," U N tali che 2 U n-2


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


S(i,j) A:i,j U xij U - 1, " U N tali che 2 U n-2


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






Privacy




Articolo informazione


Hits: 114
Apprezzato: scheda appunto

Commentare questo articolo:

Non sei registrato
Devi essere registrato per commentare

ISCRIVITI

E 'stato utile?



Copiare il codice

nella pagina web del tuo sito.


Copyright InfTub.com 2021