APLICACIONES DE LA PROGRAMACIÓN LINEAL

Los modelos de Programación Lineal son ampliamente utilizados como herramienta de apoyo a la toma de decisiones tanto por sus propiedades que facilitan su resolución, como así también su pertinencia a distintos problemas de naturaleza real. A continuación se presentan algunos ejemplos resumidos en complejidad con el objetivo de mostrar algunas aplicaciones típicas.

Los modelos de Programación Lineal son ampliamente utilizados como herramienta de apoyo a la toma de decisiones tanto por sus propiedades que facilitan su resolución, como así también su pertinencia a distintos problemas de naturaleza real. A continuación se presentan algunos ejemplos resumidos en complejidad con el objetivo de mostrar algunas aplicaciones típicas.

Problema de Inversión: Considere que usted dispone de un capital de 21.000 dólares para invertir en la bolsa de valores. Un amigo le recomienda 2 acciones que en el último tiempo han estado al alza: Acción A y Acción B. La Acción A tiene una rentabilidad del 10% anual y la Acción B del 8% anual. Su amigo le aconseja tener una cartera equilibrada y diversa y por tanto le recomienda invertir un máximo de 13.000 dólares en la Acción A y como mínimo 6.000 dólares en la Acción B. Además la inversión en la Acción A debe ser menor o igual que el doble de la inversión destinada a la Acción B. Usted quiere formular y resolver un modelo de Programación Lineal que permita obtener la política de inversión que permita obtener la máxima rentabilidad (interés) anual.

Variables de Decisión:
x = dólares invertidos en Acción A.
y = dólares invertidos en Acción B.

Función Objetivo: Se busca maximizar la rentabilidad anual que resulta de invertir en los 2 tipos de acciones.
Maximizar 0.1x + 0.08y

x + y ≤ 21.000	Se puede invertir como máximo 21.000 dólares en total
x ≤ 13.000	Invertir como máximo 13.000 dólares en Acción A
y ≥ 6.000	Invertir como mínimo 6.000 dólares en Acción B
x - 2y ≤ 0	Inversión en A debe ser menor o igual que el doble de la inversión en B
x≥0, y≥0	No Negatividad

Sólución Óptima: X = 13.000 Y = 8.000. Valor Óptimo V(P) = 1.940 dólares. Se recomienda verificar estos resultados a través de la resolución gráfica y/o utilizando Solver de Excel.

Problema de Proceso Productivo: Una empresa produce tres tipos de muebles (A, B y C), cada uno de los cuales se vende a $200, $150 y $120 respectivamente. Para la producción de estos muebles la empresa cuenta con 315 horas disponibles en un taller de corte de madera, 110 horas disponibles en un taller de lijado y 50 horas en un taller de pintado. Se ha estimado que el mueble A requiere por unidad 15 horas de trabajo en el taller de corte, 2 horas en el taller de lijado y 1 hora en el taller de pintado (estos mismos valores para los muebles B y C son 7,5:3:1 y 5:2:1, respectivamente). Se requiere formular y resolver un modelo de Programación Lineal que permita encontrar la cantidad a elaborar y vender de estos muebles de modo que la empresa obtenga el mayor beneficio.

Variables de Decisión:
X = Unidades a elaborar y vender del mueble A.
Y = Unidades a elaborar y vender del mueble B.
Z = Unidades a elaborar y vender del mueble C.

De esta forma el modelo de optimización que permite encontrar el plan óptimo de producción es el siguiente:

Este es el modelo utilizado para ejemplificar el uso de Solver de Excel en donde se pueden encontrar los resultados.

Variables de Decisión:
X = Unidades a elaborar y vender del mueble A.
Y = Unidades a elaborar y vender del mueble B.
Z = Unidades a elaborar y vender del mueble C.

De esta forma el modelo de optimización que permite encontrar el plan óptimo de producción es el siguiente:

Este es el modelo utilizado para ejemplificar el uso de Solver de Excel en donde se pueden encontrar los resultados.

Un modelo de programación lineal en 2 variables resulta ser la forma más sencilla que puede adoptar un modelo de optimización y generalmente son utilizados para introducir los conceptos básicos de la investigación de operaciones y particularmente la programación lineal. Básicamente las propiedas de un modelo lineal en 2 variables son extendibles a problemas lineales con un número mayor de variables y en este sentido la resolución gráfica resulta de gran ayuda para entender estos conceptos.

Ejemplo Resolución Gráfica

Resuelva el siguiente modelo de programación lineal a través de la resolución gráfica.

En primera instancia se asigna un eje a cada una de las variables de decisión, por ejemplo X1 corresponde al eje horizontal y X2 corresponde al eje vertical. Luego se grafican las restricciones. La primera restricción intercepta el eje X1 en 3 (cuando X2=0) y el eje X2 en 6 (cuando X1=0). Dado que la restricción es del tipo "<=" ésta determina el área que esta bajo la recta que une las coordenadas (X1,X2)=(3,0) y (X1,X2)=(0,6). En caso de tener dudas sobre el área que determina cada restricción se recomienda considerar un punto cualquiera fácil de evaluar en la restricción. Por ejemplo la coordenada (X1,X2)=(0,0) al evaluar en la restricción 1 la cumple (2*0+0<=6) y por tanto esta coordenada será parte del dominio de dicha inecuación. De forma similar se gráfica la segunda restricción que corta X1 en (28/7,0) y corta X2 en (0,7/2).

La intersección de los dominios que determinan las restricciones del problema definirán el dominio de soluciones factibles. Este dominio esta en verde en la imagen a continuación.

Una vez que ha identificado el dominio se debe buscar la solución óptima. Una propiedad de los problemas de programación lineal es que cuando admiten solución, ésta se encontrará siempre en un vértice del dominio de soluciones factibles y en caso muy especiales en la frontera de dicho dominio. Por tanto una forma de resolver será enumerando todos los vértices del dominio y evaluando éstos en la función objetivo. En este caso como el problema consiste en maximizar el valor de la función objetivo, el vértice que tenga un valor mayor corresponderá a la solución óptima. En el ejemplo se disponen de 4 vértices de fácil identificación, sin embargo, esta forma de resolución claramente queda limitada a problemas de tamaño menor.

Otra forma de resolución es a través de las curvas de nivel de la función objetivo que corresponden en el ejemplo a rectas paralelas que crecen en la dirección del gradiente de dicha función. Es decir, si desplazamos la función objetivo en la dirección del vector (X1,X2)=(120,80) el valor de la función objetivo crecerá a su mayor tasa.

En consecuencia para encontrar la solución óptima se desplazan las curvas de nivel en la dirección del gradiente hasta que se intercepte por última vez el dominio de puntos factibles. La linea punteada en rojo de la imagen anterior corresponde a dicha curva de nivel y el último punto donde esta curva intercepta el dominio corresponde al vértice con coordenadas (X1,X2)=(20/9,14/9) (Solución Óptima) con Valor Óptimo V(P)=391,1.

EXTENSIONES: Se recomienda revisar en detalle la resolución gráfica de modelos de Programación Lineal y su correspondiente análisis de sensibilidad en Programación Lineal - Resolución Gráfica.

Los modelos de Programación Entera son aquellos donde la totalidad o un subconjunto de las variables de decisión toman valores enteros. En este sentido la forma estandar de un modelo de Programación Entera queda definido de la siguiente forma:

Existen múltiples aplicaciones de modelos de Programación Entera como apoyo a la toma de decisiones. Algunas aplicaciones típicas son problemas de localización de instalaciones, inclusión de costos fijos, problemas de asignación, problemas de ruteo vehicular, etc.

Modelos de Programación Entera

Problema Asignación: Una universidad está programando las clases para el próximo semestre académico y requiere buscar la mejor asignación posible de profesores a los distintos cursos que se deben dictar. Considere que existen 5 profesores: A, B, C, D, E y 5 cursos (asignaturas): C1, C2, C3, C4, C5. Adicionalmente, los profesores han manifestado sus preferencias por dictar los distintos cursos en una escala de 1 a 10, donde 10 es la máxima puntuación y 1 la mínima puntuación o preferencia. Se asume que cada profesor es apto para dictar cualquier curso, independiente del puntaje de su preferencia. La siguiente tabla resume las puntuaciones que asigna cada profesor a cada curso:

	PROFESORES
CURSOS	A	B	C	D	E
C1	5	8	5	9	7
C2	7	2	3	6	8
C3	9	10	8	9	8
C4	8	7	9	7	8
C5	6	9	9	10	5

Se ha establecido como criterio que cada profesor debe dictar sólo un curso y a la vez que cada curso obviamente debe tener un profesor. En base a lo anterior se desea encontrar la asignación de profesores que maximize el total de las preferencias.

Variables de Decisión:

Donde P(i,j) corresponde a una forma sintética de resumir los parámetros del modelo, es decir, P(i,j) es la preferencia del profesor i (en una escala de 1 a 10) por dictar el curso j. Por ejemplo, P(D,C3)=9.

Restricciones:

Verifique utilizando Solver de Excel que la solución óptima de este problema es asignar el profesor A a C3, B a C5, C a C4, D a C1 y E a C2. Valor Óptimo = 44.

Problema Inclusión Costos Fijos: Usted ha sido designado por el gerente de su empresa para decidir cómo distribuirá su tráfico telefónico en el próximo mes, seleccionando entre 3 proveedores posibles y asignando la cantidad de tráfico (minutos) que desee en cada caso, es decir, puede repartir el tráfico en 1, 2 o 3 proveedores a su antojo y su decisión sólo dependerá de los costos de cada alternativa.

El proveedor 1 cobra un cargo fijo mensual de US$50 y el costo por minuto a red fija es de US$0,02 y a celular de US$0,12. El proveedor 2 tiene un cargo fijo mensual de US$60, con un costo por minuto de US$0,015 y US$0,15 a red fija y celular respectivamente. Finalmente el proveedor 3 tiene un cargo fijo mensual de US$40 con un costo por minuto a red fija de US$0,03 y a celular de US$0,14. Si usted llama por uno de estos proveedores (aunque hable sólo un minuto) deberá pagar el cargo fijo. Asuma que la cantidad de minutos que la empresa consume mensualmente es de 30.000 para red fija y 18.000 para celular. Formule y resuelva un modelo de Programación Entera que permita decidir cómo distribuir el tráfico telefónico mensual de la forma más económica para la empresa.

Un modelo de Programación No Lineal (PNL) es aquel donde las variables de decisión se expresan como funciones no lineales ya sea en la función objetivo y/o restricciones de un modelo de optimización. Esta característica particular de los modelos no lineales permite abordar problemas donde existen economías o deseconomías de escala o en general donde los supuestos asociados a la proporcionalidad no se cumplen.

Ejemplos de Programación No Lineal

Localización de Instalaciones: Considere que una empresa distribuidora de productos farmaceuticos requiere determinar la localización de una bodega que funcionará como centro de distribución y abastecimiento para sus locales en el país. En especial se busca estar a la menor distancia de los 3 principales locales de venta al público denominados A, B y C, respectivamente. Las coordenadas geográficas de dichos locales se presentan en el siguiente gráfico:

Formule y resuelva un modelo de optimización que permita determinar la localización óptima de la bodega y que minimize la distancia a los distintos locales de la empresa. Asuma que la bodega puede ser ubicada en cualquier coordenada o punto del mapa.

Respuesta: Si consideramos como variables de decisión X e Y que correspondan a las respectivas coordenadas de la bodega a instalar, se puede definir el siguiente modelo de optimización no lineal sin restricciones, donde la siguiente función objetivo de minimización de distancia (Min f(x,y)) queda definido por:

Se recomienda resolver este problema utilizando Solver de Excel y verificar que la solución óptima corresponde a X=33,45 e Y=40,88.

Método del Gradiente

Un modelo de Programación Lineal (PNL) es aquel donde las variables de decisión se expresan como funciones no lineales ya sea en la función objetivo y/o restricciones de un modelo de optimización. Esta característica particular de los modelos no lineales permite abordar problemas donde existen economías o deseconomías de escala o en general donde los supuestos asociados a la proporcionalidad no se cumplen.

En este sentido el método del gradiente (conocido también como método de Cauchy o del descenso más pronunciado) consiste en un algortimo específico para la resolución de modelos de PNL sin restricciones, perteneciente a la categoría de algoritmos generales de descenso, donde la búsqueda de un mínimo está asociado a la resolución secuencial de una serie de problemas unidimensionales.

Los pasos asociados a la utilización del método del gradiente o descenso más pronunciado consiste en:

Un proceso estocástico en tiempo discreto es una Cadena de Markov en la medida que se verifiquen las siguientes propiedades:

Propiedad Markoviana:

Donde i0, i1, ..., in-1, i, j son posibles “ estados” o valores que puede tomar el proceso estocástico en las distintas etapas. Esto consiste básicamente en afirmar que el futuro (t=n+1) es independiente del pasado dado el presente (t=n).

Propiedad Estacionaria: La probabilidad

No depende de la etapa n. Por ejemplo, la probabilidad de pasar del estado i al estado j será siempre la misma no importando el número de la etapa.

Si consideramos que la variable aleatoria asociado a este proceso markoviano toma un número finito de estados (digamos M) las probabilidades de transición de un estado a otro se pueden resumir en una matriz P denominada matriz de transición de probabilidades en una etapa. Adicionalmente si conocemos la distribución de probabilidad para la etapa inicial (que denotamos por f0) estamos en condiciones de conocer el proceso estocástico, que consiste en determinar la distribución de probabilidad en cada etapa.

Ejemplo Cadena de Markov en Tiempo Discreto

Suponga que en un juego existen 2 jugadores, cada uno de los cuales dispone inicialmente de 2 monedas. En cada jugada se gana una moneda con probabilidad ½ o se pierde una moneda con probabilidad ½. El juego termina cuando un jugador tiene 4 monedas o se queda con ninguna. Modele como una Cadena de Markov la situación descrita.

Desarrollo: El primer caso consiste en identificar la variable aleatoria la cuál debe representar el problema planteado, en este caso la evolución del juego al cabo de cada etapa o jugada. Se define la variable aleatoria en tiempo discreto Xn : Cantidad de monedas que tiene uno de los jugadores (digamos el jugador A) al cabo de la enésima jugada.

Luego se debe identificar los posibles valores o estados que puede tomar esta variable aleatoria para una etapa n cualquiera. Sabemos que el jugador A comienza el juego con 2 monedas y el juego termina cuando pierde todo (y por tanto el jugador B gana) o cuando gana todo (y por tanto el jugador B pierde). En consecuencia, los valores posibles para Xn son {0,1,2,3,4}.

A continuación se debe determinar las probabilidades de transición (en una etapa). Por ejemplo, si actualmente el jugador A tiene 2 monedas, la probabilidad que tenga 3 monedas al cabo de una jugada es ½ (probabilidad de ganar) y la probabilidad de que tenga 1 moneda es ½ (probabilidad de perder). De esta forma se identifican las distintas combinaciones o probabilidades de que comenzando en un estado "i" se pueda pasar a un estado "j" al cabo de una etapa. Notar que si el jugador A tiene 0 monedas la probabilidad que continue en ese estado es 1 (o 100%) dado que no tiene monedas para seguir jugando. De la misma forma si el jugador A tiene 4 monedas el jugador B tiene 0 y por tanto la probabilidad de que el jugador A se mantenga en ese estado es de 1 (o 100%).

Las probabilidades de transición en una etapa se pueden representar haciendo uso de un grafo o en forma resumida a través de la matriz de transición de probabilidades.

Cabe destacar que la suma de las probabilidades para cada fila en la matriz de transición P es de un 100%.

Podemos responder preguntas adicionales cómo por ejemplo ¿Cuál es la probabilidad de que el jugador A tenga 2 monedas al cabo de 2 jugadas?

Haciendo uso del grafo y dado que actualmente el jugador A tiene 2 monedas, se busca identificar las combinaciones que permitan a este jugador mantener esta cantidad de monedas al cabo de 2 etapas. Esto se logra ganando la próxima jugada (con probabilidad ½) y perdiendo la jugada que sigue (con probabilidad ½). También se llega al mismo resultado perdiendo la próxima jugada pero luego ganando en la jugada que sigue. Por tanto la probabilidad de tener 2 monedas al cabo de 2 etapas es P(X2=2/X0=2) = ½*½ + ½*½ = ½.

Un modelo de Programación No Lineal (PNL) es aquel donde las variables de decisión se expresan como funciones no lineales ya sea en la función objetivo y/o restricciones de un modelo de optimización. Esta característica particular de los modelos no lineales permite abordar problemas donde existen economías o deseconomías de escala o en general donde los supuestos asociados a la proporcionalidad no se cumplen.

Las condiciones que establecen las condiciones de optimalidad de KKT permiten resolver modelos de PNL con restricciones mediante la activación progresivas de las restricciones del modelo. Una restricción activa es aquella que se cumple en igualdad.

Ejemplo Karush Kuhn Tucker (KKT)

No existe una única forma de abordar la resolución de un problema de programación no lineal utilizando el teorema de KKT. Consideraremos la aplicación de este teorema en este caso para problemas sólo con restricciones "<=" (menor o igual). Si el problema tiene restricciones ">=" éstas se pueden transformar por "<=" multiplicando por -1.

Básicamente el procedimiento consiste en resolver el problema no lineal como uno sin restricciones, luego si la solución óptima de dicho problema no cumple la totalidad o parte de las restricciones del problema se activan dichas restricciones (en conjunto y/o secuencialmente) y se resuelve nuevamente. Esto se repite hasta llegar a un conjunto de restricciones activas cuya solución también satisface las restricciones omitidas. Notar que si se han activado la totalidad de restricciones sin encontrar una solución factible, entonces el problema es infactible.

EJEMPLO: Considere el siguiente problema de programación no lineal restringida. Utilizando las condiciones de optimalidad de KKT encuentre la solución óptima de dicho problema.