Algebra 1

Programación Lineal Utilizando Matrices   La programación lineal es un área recipiente de las matemáticas aplicadas, desarrollada a finales de los años cuarenta para resolver una serie de problemas. En particular, es una herramienta vital de las ciencias de administración y de la investigación de operaciones, que ha permitido ahorrar considerables sumas de dinero.   Para resolver problemas de programación lineal mediante matrices utilizaremos el método símplex.   METODO SIMPLEX   El método símplex para resolver problemas de programación lineal fue desarrollado en 1947 por George B. Dantzig para facilitar su trabajo de resolución de problemas de plantación para el gobierno de los Estados Unidos. En este trabajo se presentara las características esenciales del método, ilustrándolas con un ejemplo.   Notación Matricial Como antes, nuestra discusión estará restringida al problema estándar de programación lineal: maximizar

Sujeto a

c1 x1 + c 2 x 2 + ....... + c n x n

(1)

a11 x1 + a12 x 2 +  + a1n x n ≤ b1  a 21 x 2 + a 22 x 2 +  + a 2 n x n ≤ b2       a m1 x1 + a m 2 x 2 +  + a mn x n ≤ bm 

(2)

xj ≥ 0

(1 ≤

j ≤ n)

(3)

Si hacemos

 a11 a 21 A=    a m1

a12 a 22  am 2

 a1n   a 2 n  ,    a mn 

 x1   b1  x  b  2 2 x=  , b=          x  n bm 

y

 c1  c  c =  2      cn 

Entonces el problema dado se puede enunciar como sigue, R nvector determinar un x en la función objetivo que maximice

(4) Sujeto a (5) (6)   Donde significa que cada entrada de x es no negativa y significa que cada entrada de es menor o igual a la entrada correspondiente en b Donde significa que cada entrada de x es no negativa y significa que cada entrada de es menor o igual a la entrada correspondiente en b n que satisface (5) y (6) es una solución factible del problema R factible que maximiza la función objetivo (4) es una solución Un vector x en dado y una solución optima La utilización de variables de holgura permite escribir el nuevo problema en forma matricial, así: determinar un vector x que maximice Sujeto a

(7) (8) (9)

Donde

Un vector x que satisface (8) y (9) es una solución factible del nuevo problema, y una solución factible que maximiza la función objetivo (7) es una solución optima. En esta trabajo haremos la hipótesis adicional de que en cada problema estándar de programación lineal, se cumplen estas condiciones,

Para explicar el método a simplex utilizaremos el siguiente problema de programación lineal Problema Ilustrativo Un pequeño fabricante de productos de fotografía prepara diariamente dos tipos de reveladores de película: fino y extrafino, para ello utiliza como materia prima dos soluciones, A y B. Supongamos que cada cuarto de revelador fino contiene dos onzas de solución A y una onza de solución B, mientras que cada cuarto de revelador extrafino contiene una onza de solución A y dos onzas de solución B. Supongamos también que la ganancia por cada cuarto de fino es 8 centavos y que la de extrafino es de 10 centavos por cada cuarto. Si la empresa dispone diariamente de 50 onzas de solución A y de 70 onzas de solución B, ¿ cuántos cuartos de revelado fino y cuantos de extrafino debe producir para maximizar su ganancia ( suponiendo que la tienda puede vender todo lo que fabrica )? PROCEDIMIENTO 1.-Analizar el problema e identificar las restricciones y la función objetivo

(10) Sujetos a:

(11) (12)

2.-Convertir las restricciones en igualdades con variables de holgura (13) Sujetos a: (14) (15) 3.-Seleccionar la solución básica factible inicial Definición es una solución básica para el nuevo Un vector x en problema si se obtiene haciendo n de las variables de (8) iguales a cero, y despejando las m variables restantes.

Las m variables despejadas son las variables básicas y las n variables igualadas a cero son las variables no básicas. El vector x es una solución básica factible si es una solución básica que además satisface la condición (9). El siguiente teorema explica porque son importantes las soluciones básicas factibles Teorema Si un problema de programación lineal tiene una solución optima, entonces tiene una solución básica factible que es optima. De acuerdo con este teorema, para resolver un problema de programación lineal, solamente es necesario encontrar las soluciones básicas factibles. En nuestro ejemplo podemos elegir dos de las cuatro x, y, u y v como variables no básicas - igualándolas a cero - y despejar las otras dos, es decir, las dos variables básicas. Por lo tanto si Selección de una solución básica factible inicial Si x y u fuesen elegidas como variables no básicas ( x = u = 0), entonces y = 50 y v = -30. El Vector

Lo que es una solución básica no factible debido a que es negativa y no cumple con la restricción (15) Por lo tanto x=y=0 y despejamos u = 50, v = 70. El vector = Es una solución básica, que da lugar a la solución factible 4.-Es conveniente desarrollar un método de tabular para desplegar el problema dado y la solución factible inicial. En primer lugar, escribimos (13) como la ecuación (13´)

.-Trasladas las ecuaciones necesarias al tablero inicial de la siguiente forma

u v

x

y

u

v

z

2

1

1

0

0

50

1

2

0

1

0

70

0

0

1

0

-8

-10 6.-Aplicar: Criterio de optimalidad.-si en la fila objetivo de un tablero no aparecen entradas negativas bajo las columnas etiquetadas con variables, entonces la solución indicada es optima. (En consecuencia suspendemos los cálculos ) Por lo tanto en este problema hay que seguir operando 7.- Elegir la columna pivote Se llamara columna pivote a la columna que tenga la entrada mas negativa en la fila objetivo. A la variable de esta columna la llamaremos variable de entrada, porque en la siguiente interacción se convertirá en una variable básica, es decir, entra al conjunto de las variables básicas.

Si no existe alguna entrada positiva en la columna pivote, por encima de la fila objetivo entonces no existe solución óptima finita En el tablero inicial se identificara la variable de entrada poniendo una flecha hacia dentro sobre dicha variable 8.- Determinar la fila pivote Se llamara fila pivote a la fila etiquetada con la variable de salida Para obtener la variable de salida: Primero : se despeja las variable básicas (16)

Segundo: El valor de x = 0 se mantiene por lo que solo incrementamos y, Entonces

De modo que cuando y aumenta, u y v disminuyen. Las ecuaciones (16) también permiten establecer que tanto podemos incrementar y . En efecto, como u y v deben ser no negativas, entonces

, Se deduce entonces que el incremento posible de y no puede ser mayor que la menor de las razones . Si y es igual a 35, obtenemos la nueva solución básica factible

Por lo tanto v se convierte en la nueva variable de salida En el tablero inicial se identificara la variable de salida poniendo una flecha hacia fuera sobre dicha variable 9.- Al elemento de donde se ínter seccionan la fila y la columna pivote se lo llamara pivote y se lo marcara en el tablero inicial con un circulo u v

x

y

u

v

z

2 1 -8

1 2

1 0 0

0 1 0

0 0 1

-10

50 70 0

10.- Una vez señalado el pivote se reduce por filas a la columna pivote siendo la unidad el pivote x

-3

y

u

v

0

1

0

15

1

0

0

35

0

0

1

350

5

z

11.- Una vez obtenida esta tabla se realiza el mismo procedimiento des de el paso 6 Desarrollo: En este caso la variable de entrada será x debido a que su entrada en la fila objetivo es -3 Para determinar la variable de salida, formamos las razones de las entradas de la columna derecha (sin incluir la fila objetivo) entre las entradas correspondientes de la columna pivote, y elegimos la menor de estas razones.

Si alguna entrada de la columna pivote es negativa, entonces la razón correspondiente también será negativa, por lo que la ecuación asociada no impondrá restricciones En este caso la razones son:

,

Por lo que la variable de salida será u A este desarrollo se lo denomina eliminación con pivotes, y se obtiene x

-3

y

u

v

0

1

0

15

1

0

0

35

0

0

1

350

5

z

La eliminación con pivotes del tablero anterior da el siguiente x y u v z

x

1

0

0

10

y

0

1

0

30

0

0

1

380

2

4

Ahora la fila objetivo no tiene entradas negativas en las columnas etiquetadas con variables. El criterio de optimalidad permite concluir, que hemos terminado el proceso, y que la solución indicada es optima. Esta solución es optima Con un Z Máximo de:

Z = 380

A continuación el siguiente diagrama muestra el flujo del método simplex

Configurar el tablero inicial

¿Existe alguna entrada negativa en la fila del objetivo, bajo las columnas etiquetadas?

La solución indicada es optima

Alto

Determinar una columna pivote

¿Existe alguna entrada positiva en la columna pivote, por encima de la fila objetivo?

Determine una fila pivote

Calcular un nuevo tablero por medio de la eliminación con pivotes

No existe solución óptima finita

Alto

gracias por su atención