1. Donat el següent model: Max Z = 20X1+30X2+10X3 s.a . 4X1+2X2+X3 ≤ 240 3X1+2X2+2X3 ≤ 300 X1 ≥ 20 Determina la taula SIMPLEX ÒPTIMA si coneixem que B-1 òptima és igual a: ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ − − = − 1 0 0 1 1 1 2 0 5 ,0 1 B Solució: 1. Passem les restriccions a igualtats 4X1+2X2+X3+H1 = 240 3X1+2X2+2X3+H2 = 300 X1-E3+A3 = 20 2. Obtenim Matriu A ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ − = 1 1 0 0 0 0 1 0 0 1 0 2 2 3 0 0 0 1 1 2 4 A 3. Operem [ ] b X X I A b AX P NP NP = ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ = Per solucionar Multipliquem per B-1 [ ] b B X X I A B P NP NP 1 1 − − = ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ [ ] I A B NP 1 − = ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ − − 1 0 0 1 1 1 2 0 5 ,0 * ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ − 1 1 0 0 0 0 1 0 0 1 0 2 2 3 0 0 0 1 1 2 4 [ ] I A B NP 1 − = ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ − − − − 1 1 0 0 0 0 1 1 1 1 1 1 0 0 2 2 0 5 ,0 5 , 0 1 0 = − b B 1 ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ − − 1 0 0 1 1 1 2 0 5 ,0 ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ = ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ 20 80 80 20 300 240 4. Construïm Taula SIMPLEX 20 30 10 0 0 0 -M X1 X2 X3 H1 H2 E3 A3 X2 30 80 0 1 0,5 0,5 0 2 -2 H2 0 80 0 0 1 -1 1 -1 1 X1 20 20 1 0 0 0 0 -1 1 20 30 15 15 0 40 -40 0 0 5 15 0 40 M-40 Z0= 2.800 VARIABLES XP VARIABLES BÀSIQUES DE LA SOL. ÒPTIMA 2. Reconstrueix el Model de Programació Lineal a partir de la següent taula i sabent que XP= (X5 X6 X7) (Cj) X1 X2 X3 X4 X5 X6 X7 X1 3 5 1 0 -0,5 0 0 -0,5 0,5 X2 -1 5 0 1 0,25 0 0 0,25 0,25 X4 0 5 0 0 2,25 1 -1 -0,75 1,25 3 -1 -1,75 0 0 -1,75 1,25 (Zj) 0 0 -6,75 0 -M -1,75 1,25-M (Zj-Cj) Z0= 2.800 1. Càlcul coeficients de la funció objectiu X1 X2 X3 X4 X5 X6 X7 (+) 3 -1 -1,75 0 0 -1,75 1,25 (Zj) (-) 0 0 -6,75 0 -M -1,75 1,25-M (Zj-Cj) 3 -1 5 0 M 0 M (Cj) Coeficients M positius significa Funció Objectiu a MINIMITZAR Min Z = 3X1-X2+5X3+0X4+MX5+0X6+MX7 Sabem doncs que a) Les variables de decisió són: X1, X2i X3 (ja que prenen coef. Positius) b) Hi ha dos variables artificials: X5 i X7 (ja que prenen coef. M) c) X4 i X6 podran ser variables folgança (Hi) o variables excedent en funció del signe de les restriccions 2. Càlcul restriccions De la taula que ens faciliten podem extreure quina és la matriu B-1 ja que aquesta està associada a les Variables XP que ens han facilitat (XP= (X5 X6 X7)) X5 X6 X7 0 -0,5 0,5 0 0,25 0,25 -1 -0,75 1,25 ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ − − − = − 25 ,1 75 ,0 1 25 ,0 25 ,0 0 5 ,0 5 , 0 0 1 B Ara vull obtindre la Matriu A i el vector B. Per contra normalment el procediment que fem per obtindre la taula simplex (i solucionar el valor de les variables bàsiques) és: [ ] b B X X I A B P NP NP 1 1 − − = ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ Ara hem de fer el procediment contrari i per tant hem de multiplicar per B [ ] [ ] b AX b X X I A b BB X X I A BB P NP NP P NP NP = = ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ = ⎥ ⎦ ⎤ ⎢ ⎣ ⎡ − − 1 1 B es calcula fent la inversa de B-1 ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ − − = = − − 0 2 1 0 2 1 1 1 2 ) ( 1 1 B B [ ] I A B NP 1 − Són els coeficients de la taula Simplex X1 X2 X3 X4 X5 X6 X7 1 0 -0,5 0 0 -0,5 0,5 0 1 0,25 0 0 0,25 0,25 0 0 2,25 1 -1 -0,75 1,25 Així: [ ] I A BB NP 1 − = ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ − − − = ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ − − − − ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ − − 1 0 0 0 0 2 1 0 1 0 0 1 2 1 0 0 1 1 3 1 2 25 ,1 75 ,0 1 1 25 ,2 0 0 25 ,0 25 ,0 0 0 25 ,0 1 0 5 ,0 5 , 0 0 0 5 ,0 0 1 * 0 2 1 0 2 1 1 1 2 = − b BB 1 ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ − − 0 2 1 0 2 1 1 1 2 * ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ 5 5 5 = ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ 15 5 10 = b 3. Ja podem reescriure el sistema original Primer reescriurem el modificat (inclou Hi Ei i Ai); el de les igualtats, ja que ens permetrà identificar la direcció de les desigualtats en el sistema original, per aixi poder- lo reescriure correctament. MATRIU A (Restriccions)