Trabajo de Investigación: Teoría de Colas

La idea principal del trabajo de investigación es aplicar a la vida real la teoría de colas aprendida en clase (junto a elementos que deben investigar en la literatura).

Las situaciones de la vida real a estudiar son:

• Un McDonald
• Un Subway
• Una estación de Metro
• Un Autolavado
• Un banco
• Un cine
• Una panadería
• Una oficina de pago CANTV
• Una oficina de pago Hidrocapital
  
• Una farmacia
• Una estación de gasolina

Sobre estas situaciones de la vida real se debe estudiar:

1. Situación actual: Levantamiento de información y adaptación a un modelo de colas
2. Prueba del modelo: cosiste en determinar si las predicciones del modelo de cola se cumple
3. Determinación de costo de la cola actual: Basado en el modelo, determinar el costo de la cola.
4. Modificación del modelo: modificación pequeña y facil de aplicar que busque mejorar la situación de la cola (disminuir los costos).
5. Determinación del nuevo modelo de colas y sus costos: con al cambio, el modelo de cola puede cambiar, tanto en forma como en costos.
6. Comparación: determinar si el cambio es o no favorable.

Para llevar acabo este trabajo de investigación cada grupo deberá:

1. Seleccionar una situación de la vida real a estudiar: Puede ser cualquiera de las enumeradas anteriormente, solo tienen que determinar un lugar (Ej: Subway Plaza las Américas). Si hay repetidos no se deben estudiar el mismo lugar (ejemplo, dos grupos estudiando un banco, deben estudiar distintas agencias, como Mercantil UCAB y Banesco Chacaito).
2. Deben estudiar la situación seleccionada en condiciones interesantes: Los restaurantes de comida al medio dia. El metro en la mañana o en la tarde. Así como tambien deben tener en cuenta que el lugar seleccionado para el estudio debe tener un concurrencia de clientes alta.
3. Deben tomar fotos de la situación estudiada: Fotos donde se ejemplifique la situación que se determine a través del levantamiento de información.
4. Deben hacer referencias bibliográfias: Todo elemento teórico involucrado en el trabajo debe tener un sustento bibliográfico. No se limiten a los libros (Liberman y Taha).

FECHA DE ENTREGA DEL TRABAJO: 19 de diciembre de 2008. En formato word (doc o docx) listo para imprimir (bien formateado). En la portada del trabajo deben indicar la situación a estudar, el lugar estudiado y los miembros del grupo con nombre completo y cédula.

Simplex: Método de resolución de problemas de programación lineal

Para resolver problemas de programación lineal mucho más complejos, que obviamente, son los más comunes en la realidad, se necesita un algoritmo o método algebráico (ya que es más sencillo representar N cantidad de variables de forma abstracta).

Simplex es uno de estos métodos, que aunque es algebráico tiene raices gráficas (vease el método gráfico). Igualmente vamos a enumerar ciertos conceptos gráficos importantes para entender el método simplex:

1. Las restricciones son lineas rectas: enteder esto es de vital importancia. Las lineas rectas tienen la particularidad de que son predecibles (realmente proporcionales) asi que si hay una relación sencilla entre todos los puntos que conforman la recta.
2. La solución óptima está sobre una de las restricciones: Esto se debe a que los puntos que están sobre las restricciones son los últimos en respetarlas. Más especificamente se puede decir que la solución optima está en la intersección de dos o más restricciones. A estas intersecciones se les llama soluciones factibles en el vértice.
3. Soluciones factibles en el vértice vecinas: son todas aquellas intersecciones unidas por la recta que representa a una restricción.
   

El método simplex es un algoritmo algebráico que reza asi:

Parado en una solución factible en el vertice, voy a buscar soluciones factibles en el vertice vecinas mejores a la actual, recorriendo las restricciones que se intersectan en dicho punto.

NOTA: Aquí se puede leer como el principio del método simplex es completamente gráfico, aunque su implementeación sea algebráica.

Pasos del método SIMPLEX - Versión UNO:

1. Se busca una Solución Factible en el Vértice (SFV) donde comenzar
   
2. Prueba de optimalidad: La SFV actual es óptima si y solo si ninguno de sus vecinos es mejor.
3. Si la SFV actual no es óptima, me muevo al mejor vecino y vuelvo al paso 2.
   
4. Termina el algoritmo.

Aquí tenemos parafraseado el algoritmo algebráico de SIMPLEX. El cuál es un poco más complejo cuando se trata de implementar en computadora.

Pero criticando un poco: para poder correr el algoritmo anterior tenemos que conocer todas las soluciones factibles en el vértice, lo cual implica intersectar todas las restricciones. Esto tiene un costo computacional grande, dependiendo del tamaño del problema, pero al final es un costo. ¿Por qué no aprovechamos un poco el hecho de que las SFV se unen por una recta (restricción)? Basandonos en los conceptos de proporcionalidad de la recta: ¿Por qué no simplemente determinamos cuanto ganamos (o perdemos) al desplazarnos por una de las restrcciones, en vez de tener que determinar la SFV vecina?

Pasos del método SIMPLEX - Versión DOS:

1. Se busca una Solución Factible en el Vértice (SFV) donde comenzar
   
2. Prueba de optimalidad: La SFV actual es óptima si y solo si al desplazarnos por alguna de las restricciones solamente perdemos (desmejoramos el resultado de la función objetivo). Esto es igual a decir que no tiene vecinos mejores.
   
3. Si la SFV actual no es óptima, me muevo por la restricción que me de más ganancia, y determino la SFV vecina adyacente a esa recta.
   
4. Termina el algoritmo.

Lo más importante de resaltar en esta "versión" es que ya no necesitamos saber todas las SFV, sino solamente la actual, y la SFV vecina que esta al otro extremo de la restricción que le de más ganancias a la función objetivo.

En este momento, mi recomendación es ejecutar el algoritmo de SIMPLEX parados en el gráfico de un problema. Si se entiende de este modo, es una garantía el entendimiento de la forma tabular del SIMPLEX (que en definitiva es el que usualmente se implementa en computadoras - aunque esto es una mentirita blanca porque el que se implementa en computadora es el SIMPLEX Revisado)

Precondiciones para la aplicación de SIMPLEX

Ahora, para poder aplicar SIMPLEX, el método debe estar expresado de una forma particular, que enumeramos aquí:

1. La optimización de la función objetivo debe ser para máximizar (MAX Z). Esto hace que la forma de recorrer las SFV siempre sea para aumentar el valor de Z.
   
2. Las restricciones deben estar expresadas en forma de igualdad ( = ). Para poder recorrer las restricciones se deben tener rectas, no inecuaciones.
   
3. El punto inicial debe ser el origen. Eso hace que la SFV inicial sea facil de estimar o detectar, y asi poder comenzar el algoritmo sin cálculos complejos que determinen el punto inicial de búsqueda.

Para poder expresar un problema de PL en esta forma, tenemos que saber transformar los problemas de programación lineal para conseguir una representación equivalente que siga apegado al problema original pero que respete las pre-condiciones de SIMPLEX.

Trasnformando el problema original

1. Transformando un problema de Minimizar en Maximizar. Matemáticamente hablando: Min Z = Max -Z. Esto significa que si multiplicamos ambos lados de la igualdad de la función objetivo cambiamos el sentido de la optimización.
2. Tranformando las restricciones de tipo <= en = . Esto se hace sumando una variable de holgura a la restricción.
3. Trasnformando las restricciones de tipo >= en = . Esto se hace restando una variable de superávit.
4. Haciendo el origen una SFV inicial. Esto ocurre "siempre" cuando las restricciones se expresan de forma de igualdad (=) o desigualdad de mayor e igual que (>=) ya que al hacer las variables de desición cero, las igualdades no se cumplen. Esto se arregla sumando variables artificiales al problema. Esto también es conocido como "aumentando el problema".

NOTA: es importante destacar que cuando se transforma una restricción del tipo (>=) a( =) o ya tenemos simplemente una restricción de igualdad (=), siempre hay que resolver el problema del punto 4 (agregar variables artificiales).

Ejemplo:
Si tenemos un problema original expresado de la forma

Min Z = 4 X1 + 5 X2

Sujeto a:
3 X1 + X2 <= 27
5 X1 + 5 X2 = 6
6 X1 + 4 X2 >= 6

X1 >=0; X2 >=0

Quedaria como:

Max -Z = - 4 X1 - 5 X2 - M X4 - M X6

Sujeto a:
3 X1 + X2 + X3 = 27
5 X1 + 5 X2 + X4 = 6
6 X1 + 4 X2 - X5 + X6 = 6

X1 >=0; X2 >=0 ;X3 >=0; X4 >=0; X5 >=0; X6 >=0

Las variables resaltadas con verde son "variables de holgura", las azules son "variables de superavit" mientras que las rojas son "variables artificiales". Notese que a diferencia de las variables de holgura y superavit, las variables artificiales si afectan a la función objetivo, y se multiplican por una M.

Las variables de holgura y superavit no son mas que un artificio matemático para representar la inecuación, pero al final estas variables son representan una ecuación matemática que depende directamente de las variables de decisión. Mientras que las variables artificiales son elementos que agregamos para que el origen fuera factible, asi que esto si impacta a la función objetivo. Ahora ... ¿como lo impacta? La idea es que el problema original quede intacto por lo cual, convenientemente, tenemos que hacer que en la solución final estas variables artificiales tengan valores iguales a cero, y esto se logra penanlizandolas en la función objetivo (esto se ve a más detalle en el método de la gran M y el método de las dos fases).

SIMPLEX en forma tabular

Obviamente, de lo anterior se pueden derivar varios algoritmos, pero evidentemente esto ya fue realizado, y bastante, hasta que se llegó a una forma tabular del problema (que tampoco es la última versión de este algoritmo).

Para expresar un problema de programación lineal para ser resuelto con SIMPLEX en su forma tabular debemos igualar la función objetivo a cero y armar una tabla como se ve en la primera imágen.

La forma tabular de simplex introduce dos definiciones importantes (en este artículo, más por referencia que conceptualmente):

1. Variables básicas: Son las variables a las cuales el algoritmo le tiene asignado un valor.
2. Variables no básicas: Son las variables que el algoritmo no les asigna ningún valor, pero su valor por defecto es cero (0)
   

NOTA: Esta definición es a fines de explicar el algoritmo, no esta comprendida de conceptos de ningún tipo.

Esta definición nos permitirá separar las variables que son candidatas a entrar (variables no básicas) y cuales son candidatas a salir (variables básicas) en el método.

Pasos para el SIMPLEX en su forma tabular:

1. Prueba de optimalidad: Si en el renglón (0) hay algún valor negativo, tenemos que iterar.
2. Tomamos el valor más negativo del renglón (0) y la columna a la cual pertenece la marcamos como variblen que entra. Esto es lo mismo que decir "variable no básica a ser transformada en variable básica". A esta columna se le llama columna pivote.
   
3. Estudio del conciente mínimo: Estudiamos de la columna pivote a las filas que tengan valores extrictamente positivos. Dividimos su correspondiente en B de la misma fila entre el número de la columna pivote. La fila que genere el cociente mínimo, se considera la variable que sale (También llamada fila pivote)
4. Dividimos la fila pivote entre el número pivote (intersección entre la fila y columna pivote) y generamos la fila para la proxima iteración.
5. A través de eliminación gaussiana, hacemos que todos los elementos de la nueva columna se hagan cero.
6. Volvemos al paso 1.

Resolver problemas de Programacion Lineal gráficamente

Los problemas de la vida real planteados en forma matemática con ecuaciones lineales puede ser resuleto de varias formas, pero una de las mas intuitivas es a través de rectas en un sistema cartesiano. El hecho de que todas las ecuaciones representen una linea recta nos hace ver que el método gráfico es un acercamiento sencillo a la busqueda de soluciones de este tipo, y como veremos mas adelante, es la base de otros métodos mucho mas eficientes y menos limitados.

El Método Gráfico

Tomando en cuenta el problema prototipo, imagínese que dibujamos un plano cartesiano de dos dimensiones donde el eje de las abcisas representa la variable de decisión X1 (lotes de producto uno) y el eje de las ordenadas representa la variable de decision X2 (lotes de producto dos). Con esto tenemos un plano donde un punto representa una combinación de lotes de producto uno y dos. Asi con lo hecho hasta ahora, podemos dibujar un punto en cualquier lado del plano ya que cualquier punto es válido, ya que no hay restricciones.

Pero el problema prototipo si tiene restricciones, y lo bueno (y obligatorio) es que son inecuaciones lineales cuya representación gráfica es una recta limítrofe de la cual el punto no puede pasar. Ahora con esta nueva consideración tenemos que no todos los puntos del plano son válidos, sino son considerados soluciones factibles solo aquellos que respeten las fronteras impuestas por las restricciones. Veamos como quedarian expresadas de forma grafica las restricciones del problema prototipo (Ver gráfico).

Como lo ven, la intersección de las restricciones y el área que limitan han formado una región totalmente limitada, donde se encuentran todos los puntos (combinaciones de productos uno y dos) que respetan todas las restricciones, lo que se conoce como soluciones factibles. Al conjunto de soluciones factibles, que forman un área en el plano cartesiano (amarilla) se le conoce como región factible. Es dentro de esta region factible donde se encuentra la solución optima a nuestro problema (la combinación de lotes de productos uno y dos que no violen las restricciones de capacidad productiva de las tres plantas). Pero intuitivamente ¿dónde puede estar la solución óptima?

Razonando un poco, se puede notar que los puntos óptimos son los mas extremos, lo que están mas cercas de romper las reglas, los que están al borde de violar las restricciones: Si lo vemos en el caso de la fabrica de vidrios, es obvio pensar que la combinación de lotes óptimo estará utilizando al máximo la capacidad de las fábricas ¿cierto? No tiene mucho sentido que lleguemos a una conclusión donde se desperdicie capacidad productiva.

Aunque aqui parafraseamos una conclusión, esto esta demostrado: Las soluciones óptimas a un problema de programacion lineal se encuentra SOBRE alguna de las rectas que representan a las restricciones.

Entonces, ahora lo que se necesita saber es CÓMO se comporta la función objetivo a los cambios de X1 y X2. Para esto tenemos que dibujar una recta que represente a la función objetivo dandole un valor arbitrario a Z. En el gráfico, se puede ver dibujada la recta de la función objetivo para Z = 10. Luego, siempre paralelo a la recta que acabamos de dibujar, nos alejamos de la función objetivo hasta toparnos con el punto más extremo de la región factible. Con este método, encontramos el punto (2,6) que da como resultado un Z = 36.

¿Qué significa lo que acabamos de hacer?

La función objetivo es una linea recta que a medida que cambian los valores de sus variables (X1 y X2) se desplaza en el mapa, manteniendo siempre la misma pendiente (rectas paralelas). Esta condición hace que se respete las relaciones establecidas en la función objetivo. Para el ejemplo prototipo, la función objetivo representa las reglas en las cuales se combinan los productos 1 y 2 para generar ganancias.

Ahora, si tomamos cualquier punto sobre la recta que representa a la función objetivo vamos a conseguir una combinacion de X1 y X2 válida, pero que quizá no respete las restricciones, o quizá las respete demasiado. Es aqui donde tenemos que conseguir el punto de la región factible más alejado del origen (porque estamos maximizando) que se cruze con una paralela de la función objetivo.

Mezclando estos dos conceptos obtendremos la combinacion de X1 y X2 (productos) que combinados producen una ganancia como lo indica la función objetivo y además respeta las restricciones.

Conclusión

Este es un método sencillo de resolución de problemas de programacion lineal (PL), pero también es el más limitado. La limitación más importante es la cantidad de variables de decisión: ya que no se puede representar gráficamente ningún elemento que tenga más de tres dimenciones, los problemas de programacion lineal con cuatro (4) o más variables de decisión no se pueden resolver ccon este metodo.

Calendario actualizado!

Hola a todos ...

Viendo como han avanzado las clases durante este inicio de semestre, he actualizado el calendario de actividades del mismo. En este nuevo calendario podran observar los cambios que explico a continuacion:

• Se aplazo el primer parcial: Anteriormente el parcial estaba tan adelantado motivado por mi ausencia durante el mes de diciembre, pero como no quiero desmotivarlos con un examen apresurado he resuelto algo para el mes de diciembre.


• El segundo parcial fue sustituido por un trabajo: La idea es que en sustitucion de un segundo parcial, hagan un trabajo de investigacion, en grupos pequenos. Igual dictare las clases de diciembre (que estan resaltadas con verde en el calendario) a traves del Blog. La fecha de entrega del trabajo esta en el calendario y es inaplazable. El metodo de entrega lo discutiremos luego.

Entre otras cosas, pueden ver que el primer parcial esta bastante cargado en contenido. Les comento que todo ese contenido se relaciona, pero sigue siendo bastante. Les recomiendo no dejar para el final el estudio de los temas. No acumulen.

Saludos

PD: Disculpen la acentuacion pero estoy escribiendo en un teclado bien particular.

Ejemplo prototipo: Fábrica de artículos de vidrio

Enunciado:

Una fábrica de artefactos de vidrio elabora varios tipos de productos en sus tres plantas. La planta UNO elabora todo los elementos de aluminio, la planta DOS elabora todo lo de madera, mientras la planta TRES elabora el vidrio y ensambla los artefactos.

Debido a una reducción en las ganancias, la gerencia ha decidido reorganizar la linea de producción de la fábrica. Se descontinuaran varios productos no rentables y se dejara libre una parte de la capacidad de producción para emprender la fabricación de dos nuevos productos que tienen ventas potenciales grandes:

1. Producto UNO: una puerta de vidrio de 8 pies, con marco de aluminio.
2. Producto DOS: una ventana corrediza con marco de madera de 4 x 6 pies.

Para elaborar estos productos, se requiere que cada planta dedica parte de su capacidad de producción para elaborar los elementos que requieren y ensamblarlos. Por la constitución de cada producto se puede ver que:

• El producto UNO requiere capacidad productiva de la planta UNO y TRES, nada de la planta DOS porque no tiene madera.
• El producto DOS requiere capacidad productiva de la planta DOS y TRES, nada de la planta UNO porque no tiene aluminio.

Como el departamento de ventas considera que se pueden vender todos las unidades elaboradas de estos dos productos, la gerencia quiere producir todas las cantidades que se puedan. Pero como se ve, estos dos productos, UNO y DOS, compiten por la capacidad productiva de la planta TRES, por lo cual la gerencia no tiene claro cual es la combinación mas rentable.

Asi que el problema queda definido asi:

Determinar que tasas de producción deben tener los dos productos con el fin de maximizar las utilidades totales, sujetas a las restricciones impuestas por las capacidades de producción limitadas disponibles en las tres plantas. Entiendase como tasa de producción como el número de lotes que se producen a la semana. Se permite cualquier combinación de los productos, incluso NO fabricar uno de los productos y elaborar todo lo que sea posible del otro.

Ahora, con el problema definido, faltan datos para poder modelar el problema (EJ: cuanto es la ganancia por lote del producto UNO y DOS). Suponiendo que se hizo este levantamiento se llegó a las siguientes informaciones:

1. Número de horas disponibles semanales en cada planta para la producción de estos nuevos productos: Se determinó que la planta UNO tiene disponibles cuatro (4) horas, la planta DOS tiene disponible doce (12) horas, miemtras que la planta TRES tiene dieciocho horas (18) disponibles.
2. Número de horas de frabicación que emplea cada lote producido de cada artículo nuevo en cada una de las plantas: El producto UNO consume una (1) hora semanal en la planta UNO y tres (3) horas en la planta TRES. El producto DOS, en cambio, consume dos (2) horas en la planta DOS, y dos (2) horas en la planta TRES.
3. La ganancia (venta - costos) por lote: Se estimó que cada lote del porducto UNO dejará una ganancia de 3000 $ mientras que cada lote del producto DOS dejará 5000 $.

Formulación:

Usualmente los problemas teoricos/académicos de IO siempre tendrán bien definido el problema y los datos, pero esto está muy lejos de parecerse al mundo real. Recordando los 5 pasos que usualmente se aplican en IO, en los "problemas de libro" no podrán desarrollar habilidades para ejecutar el paso 1 (Definición del problema y recolección de datos).

Sabiendo eso, pasemos directamente a ejecutar el paso 2: Formulación del problema de forma matemática. Para eso deben tener claro primero que los problemas de optimización modelados matemáticamente tienen estas características:

1. Función objetivo: representa el comportamiento de lo que queremos optimizar cuando cambian las variables del problema. En este caso, la función objetivo deberia decirnos como se comportan las ganancias cuando cambiamos la cantidad de lotes producidos de los productos nuevos.
2. Variables de decisión: representan los elementos que afectan a la función objetivo, y por ende hay que conseguir los valores de estas variables que la optimizen. Se les llaman variables "de decisión" porque es la gerencia de las empresas las que usualmente "deciden" el valor de estas variables. El uso de las IO es hacer que esos valores sean óptimos y no meras intuiciones. En el problema prototipo, hay dos variables de decisión, que representan la cantidad de lotes semanales a elaborar del producto UNO y DOS.
   
3. Restricciones: representan límites a los que están sujetos los valores que pueden tomar las variables de decisión. Usualmente son más de una y estan representadoas como un sistemas de inecuaciones. En el ejemplo actual, la cantidad de lotes de los nuevos artículos a producir están limitados por la capacidad productiva de las plantas.

Sabiendo esto, podemos decir que la formulación matemática del problema es:

MAX F(x,y) = 3000 x + 5000 y
sujeto a:
(1) x <= 4
(2) 2 y <= 12
(3) 3 x + 2 y <= 18

Se ve, que la función objetivo representan las ganancias semanales de la fábrica por la producción de los nuevos artículos, ya que como se vió en la recolección de datos, la fábrica ganará 3000 $ por cada lote del producto UNO ( 3000 x) y 5000 $ por cada lote del producto DOS (5000 y). Entonces es obvio que las variables de decisión son la cantidad de lotes a producir semanalmente de ambos productos ( x, y).

Ahora, la producción de estos artículos esta limitada por la capacidad productiva de las plantas, y de alli vinieron las restricciones. Veamos:

1. Como el producto UNO consume una (1) hora semanal en la planta UNO por cada lote, y en la planta UNO solo hay cuatro (4) horas disponibles, tenemos que la cantidad de lotes del producto UNO no puede exceder de cuatro (x <= 4).
2. Como el producto DOS consume dos (2) horas semanales en la planta DOS por cada lote, y en la planta DOS solo hay doce (12) horas disponibles, tenemos que la cantidad de lotes del producto DOS no puede exceder la cantidad de horas disponibles ( 2 y <= 12)
3. Como en la planta TRES se presenta la competencia por los recursos, tenemos que ver que la combinación (usualmente representado como una suma) no exceda las dieciocho horas (18) disponibles. Tomando en cuenta que el producto UNO consume tres (3) horas semanales en la planta TRES y el producto DOS consume dos (2) horas semanales en la planta TRES, tenemos que esta porducción combinada no puede exceder las dieciocho horas disponibles ( 3 x + 2 y <= 18)

Ahora, recuerden que siempre hay ciertas restricciones que son conceptuales o que usualmente la persona que tiene el problema no las considera por ser muy obvias. En el caso actual ¿se podrá producir -1 lote del producto UNO o DOS? Lo que si sabemos es que la gerencia esta dispuesta a NO producir alguno de los productos (variable de decisión igual a cero), con lo que tenemos estas dos nuevas restricciones:

x >= 0 y >= 0

NOTA: problema prototipo basado en el libro "Introducción a la Investigación de Operaciones". Octava edición. Hiller-Lieberman.

Mañana 15 de Octubre de 2008 no habrá clases

Hola a todos ...

Les comunico que mañana miercoles 15 de Octubre de 2008 se me es imposible asistir a la clase de investigación de operaciones en la UCAB por razones laborales. Disculpen las molestias causadas.

Además, por favor comuniquen a sus compañeros de clases que quizá no lean este mensaje.

Con respecto a lo que haremos, hoy en la noche igualmente creare un entrada con el contenido de la clase que tocaría para mañana, asi que por favor no dejen de leerla para asi avanzar mas rápido el dia viernes y así no atrasarnos en el cronograma (que ya llevamos un dia de atraso).

Trataré hoy mismo, sino mañana, de montar el problema prototipo que vimos en clase, asi como otros dos para que ejerciten un poco.

Saludos y gracias por su entendimiento

Introducción a la Programación Lineal (PL)

La programación lineal (PL) es "el procedimiento mediante el cual, se obtienen los máximos y mínimos de un problema expresado como una función lineal, cuya solución esta restrigida por un sistema de inecuaciones lineales".

En otras palabras, son procedimientos de optimización de funciones matemáticas lineales. Ahora, la idea es que esas "funciones matemáticas lineales" representen un problema de la vida real, como las compras de materiales para la contrucción de una casa. Para esto tenemos que hacer la "formulación" del problema en un modelo matemático, y si este modelo resulta ser una función lineal, puede ser resuleto con algoritmos de PL.

NOTA: recuerda que una función lineas es aquella cuyas variables tienen exponente uno (1) . Ej: f(x,y,z) = x + 2y + 2z + 3


¿Qué NO es programación lineal?

Muchos principiantes confunden la palabra "programación" con muchas otras actividades (como codificación) asi que aquí listo algunos de estos errores de interpretación que he apreciado.

• Codificación o implementación de software. En Investigación de Operaciones, cuando se refiere a "Programación Lineal", debe interpretarse como "Planificación Lineal". Esto se debe a que la naturaleza de la mayoria de los problemas de PL son de toma de desiciones para planificar actividades.
• Resolución secuencial de un problema. El termino "Lineal" se refiere a la forma de la función matemática a optimizar, no a una secuencia de pasos o tareas.
• Modelación matemática de un problema. La modelación matematica (formulación) es un paso previo a la resolución de problemas de PL. Recuerda que es posible que la modelación matemática del problema te de una función matemática NO lineal.

¿Cuándo un problema es de Programación Lineal?

Puedes guiarte con estas dos sencillas caractrísticas:

1. El objetivo del estudio es maximizar o minimizar (optimizar)
2. Si el modelo matemático que representa el problema solo tiene expresiones lineales

Si un modelo matemático cumple con estas dos características, es un candidato para ser optimizado mediante algoritmos de PL. Ahora, es posible que el modelo matematico sea de PL, pero por su particularidad, exista otro tipo de técnicas para su resolución (EJ: Modelo de Asignación, que es un caso particular de PL)

Forma general de un problema de Programación Lineal (PL)

Los problemas de optimización siempre tienen algo que maximizar o minimizar (función objetivo) y un grupo de limitantes (restricciones) que enmarcan la optimización. Esto es necesario, porque si no se limita el problema, no habrá soluciones factibles.

Ejemplo: Si defines como un problema de PL tus compras del mercado, quieres minimizar tus gastos y no pones ninguna limitación, la respuesta al problema sera que no compres NADA, ya que asi tu gasto será mínimo ... pero ¿eso tiene sentido? Obviamente no, ya que si vas al mercado es porque tienes unas necesidades mínimas que cubrir, como por ejemplo, tu dieta diaria debe tener como mínimo 2000 calorias. Esta ultima parte del problema, es una restricción.

Asi que un problema de PL esta expresado como:

1. Función objetivo. Expresión matemática lineal a optimizar.
2. Restricciones. Conjunto de inecuaciones lineales que limitan la optimización.

Supuestos de Programación Lineal (PL)

Las "suposiciones" deben ser entendidas por la persona que trabaje sobre un problema de PL, ya que son estas la que definen formalmente a un problema de este tipo. Si alguno de estos supuestos no tienen sentido en el problema a solucionar, no puede ser resuelto por PL, o va a requerir un post-procesamiento y análisis para que el resultado tenga sentido.

NOTA: En mi opinión, la idea de usar IO es obtener resultados deterministicos. Así que debe ser meta de todo investigador de operaciones, tratar de evitar situaciones que requieran interpretaciones adicionales, mientras las circuntacias lo permitan (El mundo real es bien complicado, y modelarlo matemáticamente es muy difícil).

Vamos a enumerar aquí los tres (3) supuestos mas importantes de la programación lineal.

1. Suposición de proporción. La contribución al objetivo de cualquier variable de desición "X" es proporcional al valor de "X".
2. Suposición de adición. La contribución al objetivo de cualquier variable de desición "X" es independiente a la contribución de cualquier otra variable "Y".
3. Suposición de divisibilidad. Los valores numéricos de las variable de desición deben tener sentido incluso con valores fraccionados (Ej: X = 2,3).

NOTA: Hay más suposiciones, pero estas son las tres más resaltantes en mi opinión.