Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Paola Festa » 10.Soluzione di Problemi di PL tramite Algoritmo del Simplesso


Esercizio n. 1

Dato il seguente problema di PL

\[ \begin{array}{rrrrrrrr} \mbox{{\rm min}} & x_1 & - & 2x_2\\ \mbox{{\rm s.a}} \\ & 2x_1  & + &  x_2    & \leq & 10 \\ & - x_1  & + & 2x_2 & \leq & 3 \\ &       & x_1, & x_2 & \geq & 0 \end{array} \]

  1. disegnarne la regione ammissibile P;
  2. per ogni vertice di P indicare quali vincoli esso attiva;
  3. se esiste, indicare la soluzione ottima;
  4. verificare tramite Algoritmo del Simplesso la risposta al punto 3.

Esercizio n. 3

Si risolva tramite Algoritmo del Simplesso il seguente problema di PL:

\[\begin{array}{rrrrrrrr}\mbox{{\rm max}}&10x_1&+&20x_2&+&5x_3\\\mbox{{\rm s.a}}\\&x_1&+&x_2&+&x_3&\leq&200\\&10x_1&+&8x_2&+&5x_3&\leq&2000\\&2x_1&+&x_2&&&\leq&100\\&&&x_1,&x_2&x_3&\geq&0\end{array}\]

Esercizio n. 4

Dato il seguente problema di PL

\[\begin{array}{rrrrrrrr}\mbox{{\rm max}}&x_1&+&x_2\\\mbox{{\rm s.a}}\\&x_1&&&\leq&6\\&&&x_2&\leq&4\\&2x_1&+&5x_2&\geq&10\\&4x_1&+&2x_2&\geq&8\\&&x_1,&x_2&\geq&0\end{array}\]

  1. disegnarne la regione ammissibile P;
  2. per ogni vertice di P indicare quali vincoli esso attiva;
  3. se esiste, indicare la soluzione ottima;
  4. verificare tramite Algoritmo del Simplesso la risposta al punto 3.

Esercizio n. 5

Un impianto di riciclaggio di materiale plastico produce due prodotti, A e B, il cui costo di produzione giornaliero per quintale è pari rispettivamente a 200 e 300 euro.
Ogni giorno devono essere prodotti in totale, tra A e B, al massimo 8 quintali di prodotto, di cui almeno 2 di prodotto A e al massimo 5 di prodotto B. Inoltre, il rapporto tra le produzioni di A e B deve essere al massimo pari a 3.
Si vuol conoscere quali sono le produzioni giornaliere, espresse in quintali, di A e B, che rendano minimo il costo totale di produzione.
Con riferimento al problema descritto:

  1. disegnarne la regione ammissibile P;
  2. per ogni vertice di P indicare quali vincoli esso attiva;
  3. se esiste, indicare la soluzione ottima;
  4. verificare tramite Algoritmo del Simplesso la risposta al punto 3.

Esercizio n. 6

Una fabbrica produce pacchi da 2 kg. di patatine, sia a bastoncino (A) che in sfoglie (B).
La produzione di ogni pacco di patatine di tipo A richiede 4 ore di preparazione ed 1 ora di impacchettamento.
La produzione di ogni pacco di patatine di tipo B richiede 3 ore di preparazione e 3 di impacchettamento.
I macchinari addetti alla preparazione sono disponibili per non più di 40 ore giornaliere, mentre quelli addetti all’impacchettamento per non più di 30 ore.
Il profitto delle vendite delle patatine di tipo B è 2 volte quello del tipo A.

Determinare i quantitativi giornalieri di patatine di tipo A e B da produrre per massimizzare il profitto.
Con riferimento al problema descritto:

  1. disegnarne la regione ammissibile P;
  2. per ogni vertice di P indicare quali vincoli esso attiva;
  3. se esiste, indicare la soluzione ottima;
  4. verificare tramite Algoritmo del Simplesso la risposta al punto 3.

Esercizio n. 7

Si risolva il seguente problema di PL:

\[ \begin{array}{rrrrrrrr} \mbox{{\rm min}} &x_1 &+&x_2&+ &10x_3\\\mbox{{\rm s.a}}\\&&&x_2&+&4x_3&=&2\\& -2x_1&+&x_2 & - & 6x_3 & = & 2\\&&&x_1,&x_2&x_3 &\geq &0\end{array} \]

I materiali di supporto della lezione

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.

M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.

S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.

S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.

Dispense del Corso di Ricerca Operativa presso l'Università degli Studi di Pisa.

Dispense ed Appunti del Corso prodotte da Paola Festa.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion