viernes, 28 de septiembre de 2012

Modelos de programación lineal - Investigación de Operaciones

Se llama programación lineal al conjunto de técnicas matemáticas que pretenden resolver la situación siguiente:

"Optimizar (maximizar o minimizar) una función objetivo, función lineal de varias variables, sujeta a una serie de restricciones, expresadas por inecuaciones lineales"

Así un modelo de Programación Lineal (PL) considera que las variables de decisión tienen un comportamiento lineal, tanto en la función objetivo como restricciones del problema. En este sentido, la Programación Lineal es una de las herramientas más utilizadas en la Investigación Operativa debido a que por su naturaleza se facilitan los cálculos y en general permite una buena aproximación de la realidad.

La formulación del problema a ser solucionado por programación lineal sigue algunos pasos
básicos:
  • Debe ser definido el objetivo básico del problema, es decir la optimización a ser alcanzada. Por ejemplo maximizar ganancias, desempeños o bienestar social; minimizar costos, perdidas, tiempo. Tal objetivo será representado por una función objetivo, a ser maximizada o minimizada.
  • Para que esta función objetivo sea matemáticamente especificada, deben ser definidas las variables de decisión involucradas. Por ejemplo, número de máquinas, área a ser explorada, etc. Normalmente se asume que todas estas variables poseen solamente valores positivos.
  • Estas variables están sujetas a una serie de restricciones, normalmente representadas por inecuaciones. Por ejemplo, cantidad de equipos disponibles, tamaño del área a ser explorada, etc.
Todas las expresiones, deben estar de acuerdo con la hipótesis principal de la programación
lineal, es decir todas las relaciones entre las variables deben ser lineales. Esto implica
proporcionalidad de las cantidades envueltas.

A continuación desarrollamos algunos ejemplos que nos permitirá conocer un poco más
acerca de los problemas de programación lineal.

Problema 1.1.

Yemito es un aficionado de los juguetes electrónicos y planeando construir dos tipos de juguetes electrónicos (Ben10 y DinoRey). Él sabe que para construir un juguete Ben10 debe utilizar 9 sensores electrónicos y 3 horas de trabajo. Mientras que para construir un DinoRey utiliza 1 sensor electrónico y 1 hora de trabajo. Yemito pidió a su papá comprar los sensores electrónicos, pero éste sólo compro 18 sensores electrónicos. A la vez Yemito suele despertar a las 8:00 am y dormir a las 8:00 pm, por tal motivo dispone de 12 horas para trabajar en la construcción de los juguetes. Yemito tiene planeado vender estos juguetes en su escuela, obteniendo una utilidad de 4 dólares por cada juguete Ben10 y un dólar por cada juguete DinoRey. Por otro lado, sabiendo que Yemito logra vender todos los juguetes construidos se debe elaborar un modelo de programación lineal para optimizar sus utilidades.

Solución:

Para elaborar el modelo de programación lineal seguimos los siguientes pasos:

1. Definición de las variables de decisión:

En este caso estamos interesados en saber cuántos juguetes Ben10 y DinoRey debe construir, por tal motivo declaramos las variables de decisión de la siguiente forma:

x1 : Cantidad de juguetes Ben10 construidos
x2 : Cantidad de juguetes DinoRey construidos

Una vez declaradas las variables de decisión, debemos expresar la función objetivo utilizando dichas variables.

2. Elaboración de la función objetivo:

Dado que nuestro propósito es maximizar la utilidad total y sabemos que por la fabricación de un Ben10 tenemos una utilidad de 4 dólares, entonces la utilidad total generada por el modelo ben10 es de $ 4x1 , de igual forma el modelo DinoRey genera una utilidad de $1 x2 .
Por tanto si queremos obtener la utilidad total generada por la fabricación de los dos
juguetes tendremos z = 4x1 + x2 .
Como nuestro objetivo es maximizar la utilidad, tenemos la siguiente función objetivo:

Max z = 4x1 + x2 . 

3. Formulación de las restricciones tecnológicas:

Antes de construir las restricciones del problema, debemos tener presente las siguientes
observaciones:
  • No se puede utilizar lo que no se tiene. 
  • La cantidad utilizada debe ser menor o igual a la cantidad disponible


  • Restricción de sensores electrónicos
Sabemos que disponemos de 18 sensores electrónicos y que para fabricar un Ben10, se
necesita de 9 sensores electrónicos y para un DinoRey se necesita 1 sensor electrónico. Por tanto podemos decir que 9x1 + x2 <= 18 .


  • Restricción de horas de trabajo
De igual modo, se dispone de 12 horas de trabajo, pero para fabricar un Ben10 se
necesita 3 horas de trabajo y para un DinoRey se necesita 1 hora de trabajo. Por tanto
podemos decir que 3x1 + x2 <= 12 .


  • Restricciones de no negatividad
Dado que las variables de decisión sólo pueden tomar valores no negativos, es decir,
mayores o iguales a cero tenemos que x1 >= 0 y x2 >= 0 .

4. Modelo final:

Finalmente podemos expresar el modelo de programación lineal de la forma siguiente

Max z = 4x1 + x2

sujeto a:

9x1 + x2 <= 18

3x1 + x2 <= 12

x1, x2 >= 0


Observaciones:

Para determinar la función objetivo debe tomarse en cuenta lo siguiente:

  1. Si tenemos como datos solo costos ya sean de materia prima, mano de obra, uso de máquina, transporte, depreciación, etc. Nos indica indudablemente que la Función Objetivo (F.O.) será de MINIMIZACIÓN.
  2. Si el enunciado solo tiene datos económicos de ganancia, precio de venta o dinero a recibir por unidad producida la F.O. será de MAXIMIZACIÓN. 
  3. Si el enunciado tiene datos de costos y ganancias, entonces construimos la F.O. de la siguiente manera: GANANCIAS - COSTOS =UTILIDAD, la que tendrá como F.O. MAXIMIZAR.
  4. Si no se tiene ningún dato económico y solo se tienen tiempos, el tiempo se minimiza, si nos da solo producción, la producción se ha de maximizar, si el modelo corresponde a contratar personal, la función objetivo se debe minimizar.
  • Las restricciones o limitaciones en los modelos lineales se representan por desigualdades o igualdades: <= , >= , =
Muchos problemas tienen expresiones características que nos pueden anunciar que tipo de restricción debemos usar, por ejemplo:
Usar              |                      Para expresiones como:


<=                                        Cómo máximo, a lo más, disponibilidad, demanda máxima.

>=                                        Cómo mínimo, por lo menos, al menos, demanda mínima.
=                                           Total, proporción


  • Las restricciones deben tener las mismas unidades en tanto en su lado izquierdo como derecho. 
  • La no negatividad de algunas variables es muy importante para definir la solución de algunos modelos, por lo tanto se dice que todas las variables son >= 0.
A partir de ahora mostraremos una gran variedad de aplicaciones de modelos lineales con la finalidad de que se familiarice con los modelos de programación lineal. Para este fin se ha etiquetado a los problemas según su nivel de dificultad, por tal motivo al lado derecho de cada problema colocamos un icono que identificará el nivel de dificultad.  En la siguiente tabla se muestran los niveles de los problemas y sus respectivos iconos de  identificación.



Espero haber ayudado en algo. Hasta la próxima oportunidad!


2 comentarios:

  1. Respuestas
    1. Hola tapia patron, gracias por la visita y el aporte de tu comentario...
      Es muy grato el calificativo que le das a la página!!!...

      Mis mejores deseos!! Hasta cualquier momento!!!

      Eliminar