viernes, 27 de diciembre de 2013

Programación Lineal

La programación lineal es una parte de las matemáticas que resuelve infinitos problemas de las aplicaciones en la industria, la economía, y la estrategia (programar mezclas de productos, distribución en factoría etc...). La programación lineal consiste en maximizar o minimizar una función (llamada función objetivo) sujeta a unas condiciones (llamadas restricciones) que es, en realidad, resolver  sistemas de inecuaciones lineales.




En esta entrada, se trata de resolver sistemas de inecuaciones lineales. La solución de una inecuación lineal (de dos incógnitos) es uno de los semi planos respecto a la inecuación dada. Un sistema de inecuaciones lineales tiene una sola solución cuando pertenece a uno de los vértices del polígono (la región factible) formado por las inecuaciones dadas. Un sistema de inecuaciones tiene infinitas soluciones cuando pertenecen a uno de los lados del polígono, paraleloal vector v=(-b,a) de la función objetivo z=ax+by. Un sistema no tiene solución cuando la región factible no esta acotada (ni interiormente y ni superiormente).


¿Como encontrar el semi plano solución? Se hace un ejemplo para verlo mas claro:

¿Cuál es la región factible de la siguiente inecuación  (restricción) 2x+3y>12?

-primero, se dibuja la recta:  2x+3y=12, haciendo una tabla de valores convenientes:
                               x  |  y
                               0  | 4
                               6  | 0
-y luego, se escoge un punto cualquiera, por ejemplo el punto P(4,4), en uno de los semi plano y se comprueba en la inecuación, y resulta cierto que 2.4+3.4=20>12. Entonces la región factible es la que contiene el punto escogido, según marca las flechas en la siguiente gráfica. Así,  se hace igual para cada restricción de cualquier  sistema propuesto.



_______________________________________________

Con el siguiente ejemplo, se va a maximizar la función objetivo z=2x+3z según las restricciones siguientes:  y<4;   4x+y>8;  4x-y<16;  x>0,  y>0.

Antes de todo, hay que averiguar la región factible, representando las inecuaciones o restricciones. Con:  x>0 y y>0 se trata del primer cuadrante;  y<4 es el semi plano por debajo de la recta horizontal en y=4.

tabla de valores                      tabla de valores
4x+y>8                                  4x-y<16     
  x |  y                                        x | y           
  2 | 0                                        4 | 0
  1 | 4                                        5 | 4 
Para maximizar o calcular el valor máximo de la función objetivo, se sustituye los valores de los puntos de la región factible (vértices del polígono ABCD) en z=2x+3y:
A(2,0)  z=2.2+3.0=4   B(4,0)  z=2.4+3.0=8   C(5,4)  z=2.5+3.4=22   D(1,4)  z=2.1+3.4=14 
el valor máximo de la función objetivo es: z=22 y la solución del problema es el punto C(5,4).                                                   





___________________________________________

Con el siguiente ejemplo, se va a minimizar la función objetivo z=x+2y según las restricciones siguientes.  x>0;  y>0;  y<4;  2x-y>-4;  2x+y<12.

si x>0 y >0, la región factible se sitúa en el primer cuadrante. e y<4 esta por debajo la recta y=4;  se dibuja las rectas siguientes y así se obtiene la región factible:
tabla de valores:        tabla de valores:

   2x-y>-4                     2x+y<12
     x | y                          x | y
     2 | 0                         6 | 0
     4 | 4                         4 | 4
Para averiguar la solución, se sustituye los tres vértices del triángulo en la función objetivo: z=x+2y y como se va a minimizar, se busca el menor resultado.
A(2,0)   z(2,0)=2+2.0=2;      B(6,0)  z(6,0)= 6+2.0=6;     C(4,4)  z(4,4)=4+2.4=12.
Entonces, la solución es el punto A(2,0) que da z=2. 






__________________________________

Ahora, se resolver un problema con conceptos reales:


Un orfebre fabrica dos tipos de joyas. Con 1 gramo de oro (Au) y 2 gramos de plata (Ag) para el tipo A, y lo vende a 20€. Con 2 gramos de oro y 1 gramo de plata para el tipo B, y lo vende a 30€. Tiene 600 gramos de cada metal. Cuántas joyas de cada tipo, debe vender para maximizar el beneficio. 

Se plantea el problema de la siguiente forma:
                    A (x)    |   B (y)                            la función objetivo queda así
      __________________________                 z(x,y)=20x+30y
       Au     |      1      |      2     |   600                 las restricciones  son:
      __________________________                 x>0,          y>0
       Ag     |      2      |      1     |   600                 (1)   x+2y<600    (2)   2x+y<600
      __________________________
                |      20    |      30   |

tabla de valores                   tabla de valores
x+2y=600                            2x+y=600
     x   |  y                                x  |  y
  _________                          ________
      0  | 300                             0  | 600
   600 |    0                           300 |    0  

para averiguar la región factible, se escoge el punto P(100,100) y se sustituye en las dos inecuaciones: (1)  y (2) y se cumplen: en (1)  100+2.100=300<600  y en (2) 2.100+100=300<600; la región factible es el polígono OABC; para calcular el punto B, se resuelve el sistema formado por las ecuciones:  x+2y=600 y 2x+y=600, y se obtiene el punto B(200,200).
los valores de la función objetivo para cada punto son: 
O(0,0) z(0,0)=0€;          A(300,0) z(300,0)=300€;       B(200,200) z(200,200)=10.000€
C(0,300)  z(0,300)=9.000€. y todo esto aparece en la siguiente gráfica:





Espero sus comentarios>>>