CAPITULO 3 METODOS DE SOLUCION

02.02.2016 06:09

CAPITULO 3

 

METODOS DE SOLUCION

 

INTRODUCCION

 

Para encontrar una solución al modelo deben existir unos valores que satisfagan todas las restricciones que conforman el sistema de inecuaciones.  El método gráfico no genera un completo compendio de resultados como otros métodos de solución pero es una buena alternativa pedagógica inicial para comprender la solución y la interpretación de problemas de programación lineal.  El método simplex es un método algebraico que proporciona respuestas diversas sobre valor variables reales, de holgura y de superávit. 

 

La programación lineal genera un modelo matemático a partir de la realidad de la empresa.  Éste modelo matemático debe ser solucionado a través de cualquier método, existiendo entre otros:

 

·         Método gráfico

·         Métodos algebraicos

·         Método símplex y Método dual

·         Método informático

 

Las soluciones símplex y dual además del análisis de sensibilidad generan múltiples resultados logísticos y financieros para una adecuada toma de decisiones, sin duda estas herramientas proporcionan mayor información a nivel de resultados útiles para la toma de decisiones técnicas.  El método gráfico se desarrollará en el texto para que haya mejor comprensión en la solución de modelos y en la interpretación de los tipos de solución, luego se desarrollarán los modelos de manera informática con apoyo del paquete WINQSB en su parte de programación lineal. 

 

TIPOS DE SOLUCION

 

Se tienen varios tipos de solución que en el texto se relacionan con la parte gráfica ya que es de más fácil interpretación; las soluciones más importantes son:

 

·         Solución infactible: Matemáticamente el modelo no tiene solución por que las restricciones graficadas no hacen intersección y presentan un conjunto vacío.  Un modelo infactible puede convertirse en factible siempre y cuando se retire una o varias restricciones.

 

·         Solución factible: Es la obtenida de un modelo cuyas restricciones hacen intersección y posibilitan un conjunto solución que las satisface a todas estas restricciones.  En el ejemplo cualquiera de los puntos del área sombreada o conjunto convexo son una solución factible.

 

·         Solución múltiple: Cuando un modelo tiene diferentes soluciones que satisfacen todas las restricciones se está en presencia de una solución múltiple.  Todos los vértices del polígono que genere el conjunto solución pueden ser respuesta o solución múltiple del modelo,  sin embargo una solución siempre es mejor que otras.

 

·         Solución óptima: Es el único punto del conjunto solución que además de satisfacer todas las restricciones potencializa la función objetivo, es decir es la solución que más optimiza el sistema y se encuentra en un vértice del conjunto solución o conjunto convexo.  Sustituyendo cada uno de los valores de los vértices para X₁ y X₂ se van a presentar diferentes valores en la función objetivo, la mayor  de ellas es la solución óptima.  En el ejemplo que se presenta con la gráfica anterior, el vértice que maximiza la utilidad es el indicado en la misma, X₁=204 y X₂ = 30.  Se interpreta como los valores que sustituidos en la función objetivo generan la máxima ganancia, no existe matemáticamente otra combinación mejor para X₁ y X₂.  

 

·         Solución acotada: Es la que representa la restricción que tiene dominio hacia dentro del cuadrante No.1 partiendo de la cota o límite superior.  En el ejemplo este caso se representa con las restricciones No.1, No.2, No.3 y No. 4.  Se interpreta como un sistema donde el límite permitido por la restricción es la cantidad disponible y a la vez proporciona el máximo beneficio.

 

·         Solución no acotada: Es la que representa la restricción que tiene dominio hacia fuera del cuadrante No.1 y no tiene una cota o límite superior.  En el ejemplo este caso se representa con las restricciones No. 5 y No. 6.  Se interpreta como la posibilidad de encontrar una solución indeterminada a partir de las soluciones que da la línea de restricción en caso de maximizar  y de encontrar una solución factible cumpliendo con estas exigencias o condiciones mínimas de las restricciones en caso de minimizar la función objetivo.

 

METODO DE SOLUCION GRAFICA

 

El método gráfico no genera un completo compendio de resultados como otros métodos de solución pero es una buena alternativa pedagógica inicial para comprender la solución de problemas de programación lineal.  Utilizando el ejercicio 2.1. se va a resolver el modelo mediante el método gráfico.

 

Tomando cada restricción se prueban valores ceros para X₁ y luego para X₂, así se determinarán los puntos para X₁ y para X₂ complementarios a los términos ceros probados, de la siguiente manera:

 

Restricción No. 1) 2,8X₁ + 3X₂ < 1.600.  Cuando X₁ toma el valor de cero 0, el valor para X₂ será menor o igual que 1600/3, es decir X₂ es menor o igual que 533,34, así el primer punto de la restricción número 1 en el plano cartesiano es (0 ; 533,34).  Cuando X₂ toma el valor de cero 0, el valor para X₁ será menor o igual que 1600/2,8, es decir X₁ es menor o igual que 571,43, así el segundo punto de la restricción número 1en el plano cartesiano es (571,43 ; 0).

 

Restricción No. 2) 7X₁ + 19X₂ < 2.000.  Cuando X₁ toma el valor de cero 0, el valor para X₂ será menor o igual que 2000/19, es decir X₂ es menor o igual que 105,2, así el primer punto de la restricción número 2 en el plano cartesiano es (0 ; 105,2).  Cuando X₂ toma el valor de cero 0, el valor para X₁ será menor o igual que 2.000/7, es decir X₁ es menor o igual que 285,7, así el segundo punto de la restricción número 2 en el plano cartesiano es (285,7 ; 0).

 

Restricción No. 3) 5X₁ + 2X₂ < 4.000.  Cuando X₁ toma el valor de cero 0, el valor para X₂ será menor o igual que 4.000/2, es decir X₂ es menor o igual que 2.000, así el primer punto de la restricción número 3 en el plano cartesiano es (0 ; 2.000).  Cuando X₂ toma el valor de cero 0, el valor para X₁ será menor o igual que 4.000/5, es decir X₁ es menor o igual que 800, así el segundo punto de la restricción número 3 en el plano cartesiano es (800 ; 0).

 

Restricción No. 4) 0,9X₁ + 0.5X₂ < 1.400.  Cuando X₁ toma el valor de cero 0, el valor para X₂ será menor o igual que 1.400/0,5, es decir X₂ es menor o igual que 2.880, así el primer punto de la restricción número 4 en el plano cartesiano es (0 ; 2.880).  Cuando X₂ toma el valor de cero 0, el valor para X₁ será menor o igual que 1.400/0,9, es decir X₁ es menor o igual que 1.555,5, así el segundo punto de la restricción número 4 en el plano cartesiano es (1.555,5 ; 0).

 

Restricción No. 5) X₁ > 1.600.  Como no se tiene ningún valor en X₂ se considera una desigualdad lineal, por tanto en la gráfica se expresa a X₁ con valor de 30 en línea punteada.  

 

Restricción No. 6) X₂ > 40.  Como no se tiene ningún valor en X₁ se considera una desigualdad lineal, por tanto en la gráfica se expresa a X₂ con valor de 40 en línea punteada.

 

La gráfica siguiente corresponde a la solución del modelo, en ella se han trazado las restricciones de acuerdo a los puntos que las conforman.

 

En esta gráfica uno de los vértices es el punto óptimo, la extensión de este punto hacia los ejes X₁ y X₂ dan a conocer el valor de estas variables, de tal forma que X₁ = 204 y X₂ = 30.  Deben fabricarse 204 juegos de sala y 30 juegos de comedor para obtener una utilidad óptima de $34’200.000, la cual se ha obtenido sustituyendo los valores de X₁ y X₂ en la función objetivo.  Esta respuesta demuestra que el paquete WINQSB es confiable ya que la respuesta en forma gráfica es la misma que en forma informática.

 

METODO SIMPLEX

 

Es la solución de un sistema de inecuaciones fundamentada en procesos de programación lineal.  Como es importante conocer el fundamento matemático que da soporte al método simplex se recomienda consultar este proceso en Moskowitz[1].  De forma práctica es Importante la aplicación, la solución y la interpretación de los resultados,

 

A continuación se presentan los pasos para solucionar sistemas de inecuaciones utilizando el método Simplex:.

 

1.     Estandarice el sistema de ecuaciones.

 

2.     En un tablero como el siguiente consigne los coeficientes de la forma estándar que acompañan a cada variable en el sistema ahora de ecuaciones:

 

Variable Básica	Vector independiente bj	Variable X1	Variable X2	Variable X3	Variable X4

          

                 

 

 

 

 

3.     En la última fila elija el número más negativo, seleccione y señale la columna a la que este pertenece como la columna “pivote” o columna de trabajo.

 

4.     Ejecute la operación siguiente b_j / X_i, el menor resultado positivo determina la fila de trabajo o fila “pivote”, seleccione y señale esta fila.  A la intersección de la fila y la columna “pivotes” se le llamará “pivote”.

 

5.     Divida todos los elementos de la fila pivote entre el pivote y consígnelos en un nuevo cuadro.

 

6.      Convierta en ceros todos los elementos de la columna pivote a excepción del pivote que debe convertirlo en 1.

 

7.     Obtenga los demás elementos con la siguiente fórmula Xij-((Xi*Xj)/pivote) y consígnelos en el nuevo cuadro.

 

8.     Habrá terminado el procedimiento si el nuevo cuadro presenta valores positivos o ceros en su última fila y los resultados serán los coeficientes de la segunda columna para cada variable básica.  Deberá continuar si en los valores de la última fila se encuentra uno o varios negativos.

 

Ejemplo No.2.

 

Una empresa metalmecánica puede fabricar en una máquina que está en servicio efectivo 44 horas semanales tres productos diferentes: cilindros, pistones y crucetas.  Cada cilindro deja una ganancia de $4.000, cada pistón  $2.900 y cada cruceta $4.850.  Los rendimientos por hora de la máquina son respectivamente para cada uno de los tres productos en su orden de 50, 55 y 45 unidades.  Las ventas mensuales pronosticadas son limitadas:  500 cilindros, 850 pistones y 750 crucetas.  Como repartir la producción para hacer máximas las ganancias de la empresa?

 

Solución:

 

X₁: Número de cilindros a producir para hacer máxima la ganancia.

X₂: Número de pistones a producir para hacer máxima la ganancia.

X₃: Número de crucetas a producir para hacer máxima la ganancia.

 

Maximizar (Utilidad) Z = 4.000X₁ + 2.900X₂ + 4.85X₃

 

Sujeto a:

 

1)         X₁ / 50    +         X₂ / 55   +  X₃ / 45                  <          44 horas de capacidad semanal.

2)            X₁                                                        <          500 cilindros.

3)                                    X₂                                <          850 pistones.

4)                                                           X₃         <          750 crucetas.

5)            X₁                    X₂,                   X₃         >          0 (condición de no negatividad).            

 

Desarrollando el método simplex se tiene:

 

• Paso No. 1.  Forma estándar:

 

1)   X₁/50 + X₂/55 + X₃/45 + X₄                                                                            =          44 horas de capacidad semanal.

2)  X₁                                        + X₅                             =          500 cilindros.

3)                     X₂                               + X₆                 =          850 pistones.

4)                                            X₃                     +X₇       =          750 crucetas.

5) -4.000X₁ - 2.900X₂ - 4.850X_{3                                                                            =}                     0

 

En este paso se han incluido X₄, X₅, X₆ y X₇ que representan matemáticamente la cantidad que falta para llegar al límite en cada restricción convirtiéndola en una igualdad.  Estas variables se llaman VARIABLES DE HOLGURA, se interpretan en el ejemplo como la cantidad no utilizada en horas de maquinaria en la primera restricción y como la cantidad no fabricada de cada tipo de productos teniendo en cuenta la exigencia máxima de fabricación en las demás restricciones.

 

·         Pasos Números 1, 2, 3 y 4.  Matriz de coeficientes y señalamiento de columna y fila pivotes.

·         Pasos Números 5 y 6: División de elementos de la fila entre el pivote y conversión en ceros de elementos de la columna pivote.

 

·         Pasos No.7: Obtención de los demás elementos o coeficientes.

Como en el cuadro anterior se presentan números negativos se debe continuar el proceso hasta que se de esta condición.  Los siguientes cuadros son el desarrollo de este procedimiento hasta terminar el ejercicio.

La solución del modelo presenta los siguientes resultados: X₁=500, X₂=850, X₃=750, X₄=2, X₅=0, X₆=0, Z=$7’337.500, es decir se deben fabricar 500 cilindros, 850 pistones y 750 crucetas para obtener una ganancia de $7’337.500 ya que si otra combinación cumple con las restricciones no generará mayor utilidad que la obtenida.  También puede interpretarse que no se emplearán 2 horas de máquina de las 44 horas de las que se dispone.

 

EJERCICIO DE APLICACIÓN INFORMATICA

 

En el paquete informático WINQSB compruebe que el anterior problema ha sido resuelto satisfactoriamente.

 

MODELO DUAL

 

Algebraicamente es la matriz transpuesta del modelo original o primal.  Sirve para tomar e interpretar otro tipo de información asociada con el sistema que representa el modelo.  El modelo dual es la “otra cara de la moneda” ya que realmente es el mismo sistema que representa el modelo primal y que indica otra información).

 

Ejemplo No. 3.

 

Un granjero desea destinar su finca de 10 hectáreas a 3 actividades que le generan ingresos. Sembrar fríjol, sembrar arveja y criar cerdos reproductores.  40 cerdos ocupan media hectárea de tierra.  El ingreso neto anual es de $35’000.000 por cada hectárea de fríjol, $25’000.000 por cada hectárea de arveja y $500.000 por cada cerdo reproductor.  El granjero dispone de 250 horas de mano de obra en cada mes entre mayo y octubre y 200 horas entre noviembre y abril.  Las actividades requieren de las siguientes horas de trabajo:

 

El modelo primal del problema propuesto es el siguiente:

 

X_!: Cantidad de hectáreas que deben sembrarse de fríjol.

X₂: Cantidad de hectáreas que deben destinarse a la siembra de arveja.

X₃: Cantidad de hectáreas destinadas a la cría de cerdos reproductores.

 

Maximizar (Ingreso) Z = 35’000.000X₁ + 25’000.000X₂ + 40’000.000X₃  

 

S.A.     1)  X₁ + 0.5X₂ + 7X₃       <          1.500 Horas de máquina entre mayo y octubre

            2) 3X₁+ 5X₂    + 8X₃       <          1.200 Horas de máquina entre noviembre y abril

            3) X₁ +      X₂ +  X₃        <          10 Hectáreas

                X₁,   X₂,  X₃               <          0

 

La solución de este problema generada informáticamente es la siguiente: X1=0, X2=0, X3=10, X4=0, X5=0, X6=0, Z=400’000.000.  Esto quiere decir que para hacer máximo el ingreso por el mejor aprovechamiento de las hectáreas de tierra se deben dedicar los esfuerzos a la cría de cerdos reproductores ya que genera mejores ingresos, aunque esto implique utilizar más horas de mano de obra, además se deben emplear todas las horas de la fuerza de trabajo.    

 

El modelo DUAL de este ejercicio es:

 

Y₁: Valor implícito que tiene cada hora de mano de obra en los meses de mayo a octubre.

Y₂: Valor implícito que tiene cada hora de mano de obra en los meses de noviembre a abril.

 

Minimizar (Horas empleadas) Z = 1.500Y1 + 1.200Y2 + 10Y3

S.A.     1)      Y₁ + 3Y₂   + Y₃       >          35’000.000

            2) 0.5Y₁ + 5Y₂   + Y₃       >          25’000.000

            3)    7Y₁ + 8Y₂   + Y₃       >          40’000.000

                        Y₁, Y₂, Y₃          <          0

 

Al solucionar este modelo por la forma informática o por el “método de la doble fase” se obtendrán valores agregados que representan el aporte de la mano de obra en términos financieros de acuerdo al ingreso que se espera recibir.  El “método de la doble fase” se trabaja mediante el mismo esquema del método simplex pero la estandarización se efectúa de acuerdo a sistemas de inecuaciones con signo mayor o igual >.  La respuesta informática de este modelo dual es Y₁=0, Y₂=0, Y₃=40’000.000, quiere decir que el valor agregado que tiene la mano de obra en el producto es de $40’000.000 o $4’000.000 por hectárea criando cerdos.  Si se decidiera emplear en otra actividad o negocio a la fuerza de trabajo, esta debe generar en el valor agregado más de $40’000.000.

 

EJERCICIO DE APLICACIÓN TEORICA E INFORMATICA

 

1. En un sistema real (por ejemplo una planta de producción o servicios) determine que subsistema y que variables de ese subsistema deben tenerse en cuenta para medir el grado de productividad.
2. En grupos de 3 personas y guiado por su profesor, efectúe el levantamiento de un sistema real de operaciones y plásmelo como un modelo.
3. Solucione el modelo mediante cualquier método, se recomienda utilizar el método informático WINQSB.
4. Proponga alternativas de solución o mejoramiento de la productividad.