Mathematical Engineering - Fondamenti di Ricerca Operativa

Programmazione Lineare e Dualità

Divided by topic

Fondamenti di Ricerca Operativa Esercizi proposti Programmazione Lineare e Dualita AA. 2019/2020 Fondamenti di Ricerca Operativa pagina 1 Esercizio 1 Simplesso Risolvere il seguente problema di Programmazione Lineare con il metodo del simplesso, usando come base ammissibile iniziale quella formata dalle variabili di scartox 4; x 5: min 5x 1 2x 2 3x 3 s.t.x 1+ 4 x 2 2x 3 8 x1+ x 2+ 2 x 3 12 x1; x 2; x 3 0: (La soluzione ottima e:x 2= 4 ; x 3= 4 ; f :ob:=20) Esercizio 2Simplesso Risolvere il seguente problema di Programmazione Lineare con il metodo del simplesso, usando come base ammissibile iniziale quella formata dalle variabili di scartox 4; x 5: minx 1+ 2 x 2 3x 3 s.t.x 1 2x 2+ x 3 2 3x 1 x 2+ 2 x 3 6 x1; x 2; x 3 0: (La soluzione ottima e:x 2=23 ; x 3=103 ; f :ob: =263 ) Esercizio 3Simplesso Risolvere il seguente problema di Programmazione Lineare con il metodo del simplesso, usando come base ammissibile iniziale quella formata dalle variabili di scartox 4; x 5: min2x 1 x 2 3x 3 s.t.x 1+ x 2+ x 3 2 2x 1+ 3 x 2+ 8 x 3 12 x1; x 2; x 3 0: (La soluzione ottima e:x 1=23 ; x 3=43 ; f :ob: =163 ) Esercizio 4Simplesso Risolvere il seguente programma lineare con il metodo del simplesso, usando come base ammis- sibile iniziale quella formata dalle variabili di scartox 4; x 5: min2x 1+ 2 x 2 2x 3 s.t. 2x 1 2x 2 x 3 2 3x 1+ 3 x 2+ 2 x 3 3 x1; x 2; x 3 0:Programmazione Lineare e Dualita Prof. Giuliana Carello Fondamenti di Ricerca Operativa pagina 2 Esercizio 5 Simplesso Calcolare la soluzione ottima del seguente problema di Programmazione Lineare. minx 1 2x 2+ x 3 s.t.x 1 x 2+ 3 x 3= 5 2x 1+ x 2+ x 3= 4 x1; x 2; x 3 0: Esercizio 6Simplesso Risolvere il seguente problema di Programmazione Lineare: min 2x 1+ x 2+ 3 x 3+ 2 x 4+ 10 x 5 s.t.x 1+ x 3 x 4+ 2 x 5= 5 x2+ 2 x 3+ 2 x 4+ x 5= 9 x1; x 2; x 3; x 4 0: Esercizio 7Simplesso Risolvere partendo dalla basefx 1; x 4g il seguente problema di Programmazione Lineare: max 3x 1+ 2 x 2+ x 3+ x 4 s.t.x 1+ 2 x 2+ x 3+ 3 x 4= 2 2x 1+ x 2+ 3 x 3+ 2 x 4= 3 xi 08i Esercizio 8Simplesso Risolvere partendo dalla basefx 1; x 2g il seguente problema di Programmazione Lineare: min2x 1+ 4 x 2+ 2 x 3 4x 4 s.t.x 1+ 4 x 2 x 3 2x 4= 8 2x 1+ 3 x 2+ 2 x 3+ x 4= 6 xi 08iProgrammazione Lineare e Dualita Prof. Giuliana Carello Fondamenti di Ricerca Operativa pagina 3 Esercizio 9 Duale e complementarita Si consideri il seguente problema in Programmazione Lineare: max 2x 1+ x 2 2x 1 x 2 1 x1 x 2 3 4x 1+ x 2 17 x2 5 x 1+ x 2 4 conx 1; x 2 0. a)Scrivere il problema duale del problema dato. b)Scrivere le equazioni delle condizioni di complementarita per il problema dato (si osserviche il problema e il suo duale sono in forma simmetrica). c)Applicando le condizioni di complementarita dire se i punti (3,5) e (4,1) sono ottimi. Esercizio 10Duale e complementarita Si consideri il seguente problema di Programmazione Lineare max 3x 1 x1 32 x2 32 x1+ x 2 7 x1 x 2 6 1.Scrivere il duale del problema dato. 2.Applicando le condizioni di complementarita vericare se i seguenti punti sono ottimi:  132 ; 12   32 ; 172 Programmazione Lineare e Dualita Prof. Giuliana Carello Fondamenti di Ricerca Operativa pagina 4 Esercizio 11 Duale e complementarieta Si consideri il seguente problema di Programmazione Lineare. maxx 1+ 2 x 2 3x 1+ x 2 4 x2 5 x1 x 2 1 2x 1+ x 2 4 1.Scrivere il problema duale del problema dato. 2.Applicando le proprieta di complementarita dire se i seguenti punti sono soluzioni ottimedel problema: (6,5) (0,4)Programmazione Lineare e Dualita Prof. Giuliana Carello