El dual de un problema de programación lineal y su relación con el problema primal.

Dualidad en Programación Lineal

Consideremos nuevamente el ejemplo utilizado para presentar el tutorial de Solver:

Supongamos que deseamos conocer una cota superior del valor óptimo de este problema sin la necesidad de resolver dicho problema. Por ejemplo, si multiplicamos la restricción 3 por 200 obtenemos: 200X + 200Y + 200Z <= 10.000. Claramente el lado izquierdo de esta restricción amplificada es mayor o igual a la expresión que define la función objetivo, por tanto podemos afimar que el valor óptimo de este problema es menor o igual a 10.000 ( V(P)<=10.000 ). Por supuesto se puede buscar otras combinaciones de modo de definir una mejor cota superior a la que se utiliza como ejemplo.

En este sentido si consideramos A, B y C como multiplicadores asociados a cada una de las restricciones, la forma de encontrar la mejor cota superior para el problema original (que llamaremos en adelante Primal) se obtiene resolviendo el siguiente problema (denominado Dual):

Este problema puede ser resuelto a través del método simplex dual como se explica en detalle en dicha sección. Se obtiene de esta forma la siguiente solución óptima: A=8, B=10, C=60, con valor óptimo de 6.620. Si multiplicamos las restricciones del problema dual por estos multiplicadores logramos la mejor cota superior:

8(15X + 7,5Y + 5Z) + 10(2X + 3Y + 2Z) + 60(X + Y + Z) <= 8*315 + 10*110 + 60*50

200X + 150Y + 120Z <= 6.620

Se puede verificar adicionalmente que el precio sombra de las respectivas restricciones del problema primal (ver informe de sensibilidad en la sección de solver de excel) corresponde a las variables duales óptimas o solución óptima del problema dual, con valor óptimo equivalente.

En general las relaciones de dualidad se pueden resumir en la siguiente tabla:

Teoremas de Dualidad

La dualidad en programación lineal provee de resultados teóricos interesantes que justifican su uso como herramienta alternativa y complementaria de resolución.

TEOREMA DE DUALIDAD DÉBIL: En general, el valor de cualquier solución factible del problema de minimización, provee una cota superior del valor óptimo del problema de maximización. Análogamente, el valor de la función objetivo de cualquier solución factible del problema de maximización es una cota inferior del valor óptimo del problema de minimización.

TEOREMA DE DUALIDAD FUERTE: En el óptimo el valor de la función objetivo del problema primal será igual al valor de la función objetivo del problema dual evaluada en la solución dual óptima. Si el problema primal es no acotado, entonces el dual es infactible. Alternativamente si el problema primal es infactible, entonces el dual es no acotado.

TEOREMA DE HOLGURAS COMPLEMENTARIAS:Una variable en el primal esta asociada a una restricción en el dual (y viceversa). En este sentido si en el primal existe una variable no básica (valor igual a cero), en el dual la restricción asociado no está activa, es decir, no se cumple en igualdad. Análogamente, si la variable es básica en el primal, la restricción asociada en el dual se cumple en igualdad. Este resultado teórico es útil toda vez que simplifica la forma de obtener la solución óptima dado que como en un problema lineal la solución óptima (en caso de existir) esta en un vértice, esto implica resolver un sistema de ecuaciones (con restricciones de igualdad).

Maximización y minimización

Vamos a aprender a crear y resolver un ejercicio del siguiente tipo (más complicados que este sin duda que también):

Un carpintero tiene que construir mesas rectangulares cuyos lados no sobrepasen $$2$$ metros y tales que la suma de su lado mayor y el doble de la menor no sobrepase $$4$$ metros. ¿Cuál es el máximo valor del perímetro de dichas mesas?

En este tipo de problemas, aparece cierta cantidad que se ha de maximizar (también podría ser minimizar, pero no es este el caso). En este ejemplo es el perímetro de las mesas, que está sujeto a ciertas restricciones. La función a maximizar ( minimizar ) se lama función objetivo. El valor máximo (o mínimo) de la función objetivo se halla en los bordes de la zona factible delimitada por las restricciones del problema. A este valor se le llama el valor óptimo.

Veamos cómo expresar el problema del ejemplo matemáticamente:

Igual que en el primer nivel, lo primero a identificar son las variables o incógnitas. En este caso serán el lado largo de la mesa (al que llamaremos $$x$$) y el lado corto de la mesa (al que llamaremos $$y$$).

Identificamos la función objetivo. ¿Qué se nos pide maximizar/minimizar? y ¿Cómo se expresa esta cantidad en función de las variables del problema?

En nuestro caso se nos pide maximizar el perímetro (al que llamaremos $$P$$) de las mesas. El perímetro se puede expresar como función de las variables del problema (lado largo y lado corto), ya que es directamente la suma del doble de cada lado. Matemáticamente: $$$P(x,y)=2x+2y$$$

Escribimos las restricciones como inecuaciones. Estas restricciones son:

• Los lados no pueden ser de más de dos metros (ni de menos de cero, ya que no tendría sentido): $$$ x\geqslant 0 \qquad x\leqslant 2 \qquad y\geqslant 0 \qquad y\leqslant 2 $$$
• La suma del lado mayor y el doble de la menor no ha de sobrepasar los $$4$$ metros: $$$ x+ 2y\leqslant 4$$$

Identificamos la región de validez definida por las restricciones y calculamos los vértices de dicha región. Las rectas asociadas a las restricciones son:

• $$x=0$$ y $$x=2$$, que son rectas paralelas al eje $$y$$, que pasan por $$x=0$$ y $$x=2$$ respectivamente. Las desigualdades de que provienen definen una franjade soluciones factibles entre $$x=0$$ y $$x=2$$.
• $$y=0$$ y $$y=2$$, que son rectas paralelas al eje $$x$$, que pasan por $$y=0$$ y $$y=2$$ respectivamente. Las desigualdades de que provienen definen una franjade soluciones factibles entre $$y=0$$ y $$y=2$$.
• $$y=-\dfrac{1}{2}x+2$$, cuya zona de validez está por debajo de la recta (se puede ver comprobando que el punto $$(0,0)$$, que está por debajo de la recta, cumple la inecuación $$x+2y\leqslant 4$$).

Los vértices de la región de validez se calculan como en el nivel anterior: viendo en qué puntos se cortan las rectas definidas por las restricciones y luego seleccionar de estos puntos los que cumplen todas las inecuaciones. Haciendo esto vemos que los vertices de la región de validez tienen por coordenadas:

• $$(0,0)$$ donde cortan $$x=0$$ e $$y=0$$.
• $$(2,0)$$ donde cortan $$x=2$$ e $$y=0$$.
• $$(2,1)$$ donde cortan $$x=2$$ e $$y=-\dfrac{1}{2}x+2$$.
• $$(0,2)$$ donde cortan $$x=0$$ e $$y=-\dfrac{1}{2}x+2$$.

El último paso es calcular el valor de la función objetivo en los vértices de la región de validez, para ver cual de los puntos maximiza el perímetro de las mesas.

• $$P(0,0)=2\cdot 0+2\cdot 0=0$$
• $$P(2,0)=2\cdot 2+2\cdot 0=4$$
• $$P(2,1)=2\cdot 2+2\cdot 1=6$$
• $$P(0,2)=2\cdot 0+2\cdot 2=4$$

Vemos que el perímetro se maximiza en el punto $$(2,0)$$. La función perímetro toma allí su valor óptimo, que es $$6$$ metros. Las coordenadas del punto nos están diciendo que maximizará el perímetro haciendo mesas de lado largo ($$x$$) de $$2$$ metros y lado corto ($$y$$) de $$1$$ metro. Ya hemos resuelto el primer problema completo de programación lineal.

Otros ejemplos:

Los $$400$$ alumnos de un colegio van a ir de excursión. Para ello se contrata el viaje a una empresa que dispone de $$8$$ autobuses del tipo A con $$40$$ plazas y $$10$$ del tipo B con $$50$$ plazas, pero sólo de $$9$$ conductores para ese día. Dada la diferente capacidad y calidad, el alquiler de cada autobús de los grandes (tipo B) cuesta $$80$$ € y el de cada uno de los pequeños (tipo A), $$60$$ €. ¿Cuántos autobuses de cada clase convendrá alquilar para que el viaje resulte lo más económico posible?

Primero identificamos las variables. En este caso serán el número de autobuses del tipo A (al que llamaremos $$x$$) y el número de autobuses del tipo B (al que llamaremos $$y$$). La función objetivo es el precio y se ha de minimizar. El precio en función de las variables del problema será la suma de lo que vale un autobús del tipo A (a $$60$$€) multiplicado por el número de autobuses del tipo A que se alquilan más lo mismo, pero de los autobuses tipo B (a $$80$$€). Es decir, el precio será: $$$P(x,y)=60\cdot x+80\cdot y$$$

Las restricciones del problema en forma de inecuaciones:

• $$x\geqslant 0$$, $$y\geqslant 0$$ (por lógica, no podemos alquilar un número negativo de autobuses).
• $$x\leqslant 8$$ (sólo hay $$8$$ autobuses del tipo A).
• $$y\leqslant 10$$ (sólo hay $$10$$ autobuses del tipo B).
• $$x+y\leqslant 9$$ (sólo hay $$9$$ conductores).
• $$40\cdot x +50\cdot y\geqslant 400$$ (queremos que el número total de plazas de autobús sea disponibles sea como mínimo igual al número de alumnos).

Buscamos las rectas asociadas a las inecuaciones, las zonas de validez de cada inecuación y la zona factible común a todas las restricciones.

Y la zona factible queda:

El siguiente paso es calcular los vértices de la región de validez. En este caso son: $$$ (0,8) \qquad (0,9) \qquad (5,4)$$$

La función objetivo (el precio) toma los siguientes valores en los vértices de la región de soluciones factibles:

• $$P(0,8)=60\cdot 0+80\cdot 8=640$$ €
• $$P(0,9)=60\cdot 0+80\cdot 9=720$$ €
• $$P(5,4)=60\cdot 5+80\cdot 4=620$$ €

como queremos minimizar el precio, el punto que queremos es el $$(5,4)$$ y el precio toma el valor de $$620$$ €. Por lo tanto, minimizaremos el precio si se alquilan $$5$$ autobuses del tipo A ($$x$$) y $$4$$ autobuses del tipo B ($$y$$) y todo saldrá por $$620$$ €.

En resumen, en todo problema de programación lineal tendremos que seguir los mismos pasos:

1. Elegir las variables del problema.
2. Escribir la función objetivo en función de los datos del problema.
3. Escribir las restricciones en forma de inecuaciones.
4. Determinar la región factible que indican las restricciones.
5. Calcular las coordenadas de los vértices de la región de soluciones factibles.
6. Calcular el valor de la función objetivo en cada uno de los vértices para ver en cuál de ellos presenta el malor máximo o mínimo, según nos pida el problema.

Método Simplex de Programación Lineal 

El Método Simplex publicado por George Dantzig en 1947 consiste en un algoritmo iterativo que secuencial mente a través de iteraciones se va aproximando al óptimo del problema de Programación Lineal en caso de existir esta última.

La primera implementación computacional del Método Simplex es el ano 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.

El Método Simplex hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar el cual definiremos a continuación.

FORMA ESTÁNDAR DE UN MODELO DE PROGRAMACIÓN LINEAL

Consideremos un modelo de Programación Lineal en su forma estandar, que denotaremos en lo que sigue por:

• Min          c1x1  + c2x2  + ... + cnxn
• sa            a11x1 + a12x2 + ... + a1nxn = b1
•                 a21x1 + a22x2 + ... + a2nxn = b2
•                 ...          ...                  ...
•                 am1x1 + am2x2 + ... + amnxn = bm
•                 xi >=  0,   i = 1, 2, ..., n    y    m <= n
Matricialmente escrito como:
Min    cTx
s.a      Ax = b
           x >=  0
No existe pérdida de generalidad en asumir que un modelo de PL viene dado en su forma estándar:

• EJEMPLO
• P)            Max        9u + 2v + 5z
•                 sa            4u + 3v + 6z <=  50
•                                 u + 2v - 3z >=  8
•                                2u - 4v + z = 5
•                                u,v >=  0
•                                z e IR

1. Siempre es posible llevar un problema de maximización a uno de minimización. Si f(x) es la función objetivo a maximizar y x* es la solución óptima f(x*) >= f(x), para todo x factible. -f(x*) <= - f(x), para todo x factible. En consecuencia:  x* es también mínimo de  -f(x)
2. Cada restricción del tipo <= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de holgura no negativa, con coeficiente nulo en la función objetivo.
3. Cada restricción del tipo >= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de exceso no negativa, con coeficiente nulo en la función objetivo.
4. Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no negativas.

Considerando la siguiente notación: u = x1, v = x2, z = x3 - x4, s1 = x5 (holgura), s2 = x6 (exceso), el problema P) puede ser escrito en forma equivalente como:

• Min         - 9x1 - 2x2 - 5x3 + 5x4 + 0x5 + 0x6
• sa:              4x1 + 3x2 + 6x3 - 6x4 +    x5          = 50
•                      x1 + 2x2 - 3x3 + 3x4             - x6  =  8
•                    2x1 - 4x2 +  x3   -   x4                     =  5
•                    xi >=  0,    i=1,2,3,4,5,6.  

EJEMPLO:
Resolver el siguiente problema de Programación Lineal utilizando el Método Simplex:

• Max     40*X1 + 60*X2
• s.a.     2*X1 + 1*X2 <= 70
•             1*X1 + 1*X2 <= 40
•             1*X1 + 3*X2 <= 90
•              X1 >= 0  X2 >= 0
Para poder aplicar el Método Simplex, es necesario llevar el modelo a su formato estándar, para lo cual definimos X3, X4, X5 >= 0 como las respectivas variables de holgura para la restricción 1, 2 y 3. De esta forma queda definida la tabla inicial del método de la siguiente forma:


X1	X2	X3	X4	X5
2	1	1	0	0	70
1	1	0	1	0	40
1	3	0	0	1	90
-40	-60	0	0	0	0

En esta situación, las variables de holgura definen una solución básica factible inicial, condición necesaria para la aplicación del método. Luego, se verifican los costos reducidos de las variables no básicas (X1 y X2 en la tabla inicial) y se escoge como variable que entra a la base aquella con el costo reducido "más negativo". En este caso, X2.

Luego, para escoger que variable básica deja la base debemos buscar el mínimo cuociente entre el lado derecho y los coeficientes asociados a la variable entrante en cada fila (para aquellos coeficientes > 0 marcados en rojo en la tabla anterior). El mínimo se alcanza en Min {70/1, 40/1, 90/3} = 30 asociado a la tercera fila, el cual corresponde a la variable básica actual X5, en consecuencia, X5 deja la base. En la posición que se alcanza el mínimo cuociente lo llamaremos "Pivote" (marcado con rojo) el cual nos servirá para realizar las respectivas operaciones filas, logrando la siguiente tabla al cabo de una iteración:

X1	X2	X3	X4	X5
5/3	0	1	0	-1/3	40
2/3	0	0	1	-1/3	10
1/3	1	0	0	1/3	30
-20	0	0	0	20	1800

El valor de la función objetivo luego de una iteración ha pasado de 0 a 1.800. Se recomienda al lector hacer una representación gráfica del problema y notar como las soluciones factibles del método corresponden a vértices del dominio de puntos factibles.

La actual tabla no corresponde a la solución óptima del problema P) debido a que existe una variable no básica con costo reducido negativo, por tanto X1 entra a la base. Posteriormente, mediante el criterio del mínimo cuociente calculamos la variable que debe dejar la base: Min {40/(5/3), 10/(2/3), 30/(1/3)} = 15, asociado a la fila 2 (variable básica actual X4), por tanto X4 deja la base. Obtenido lo anterior se aplica una iteración del método:

X1	X2	X3	X4	X5
0	0	1	-5/2	1/2	15
1	0	0	3/2	-1/2	15
0	1	0	-1/2	1/2	25
0	0	0	30	10	2100

Finalmente se alcanza la solución óptima del problema P) y se verifica que los costos reducidos asociados a las variables no básicas (X4 y X5 son mayores o iguals que cero). Notése que la existencia de un costo reducido igual a cero para una variable no básica en esta etapa define un problema con "infinitas soluciones".

La solución alcanzada es X1* = 15, X2* = 25 con V(P*) = 2.100. Adicionalmente, los costos reducidos asociados a las variables no básicas definen el precio sombra asociado a las restricciones 1, 2 y 3, respectivamente, lo cual es equivalente a la obtención del precio sombra mediante el método gráfico. Dejaremos para una posterior presentación, la forma de calcular el intervalo de variación para el lado derecho que permite la validez del precio sombra, utilizando la tabla final del Método Simplex.

MÉTODO SIMPLEX DE 2 FASES

Esta estrategia se utiliza cuando no es inmediata una solución básica factible inicial en las variables originales del modelo.

FASE 1: Se considera un problema auxiliar que resulta de agregar tantas variables auxiliares a las restricciones del problema, de modo de obtener una solución básica factible. Resolver por Simplex un problema que considera como función objetivo la suma de las variables auxiliares. Si el valor óptimo es cero, seguir a la Fase II, en caso contrario, no existe solución factible.
FASE 2: Resolver por Simplex el problema original a partir de la solución básica factible inicial hallada en la Fase I.

• P)            Max        2X1 + X2
•                 sa           10X1 + 10X2 <=  9
•                                10X1 + 5X2  >=  1
•                                X1, X2 >=  0

Se debe agregar X3 como variable de holgura de la restricción 1, X4 como variable de exceso de la restricción 2 y X5 variable auxiliar para poder comenzar la Fase 1. (Nótese que solo agregando X3 como variable de holgura a la restricción 1 y X4 como variable de exceso a las segunda restricción no se obtiene una solución básica factible inicial, en particular X4<0).

• F1)            Min        X5
  sa             ...............10X1 + 10X2 + X3              =  9
•                                 10X1 + 5X2         - X4 + X5 =  1
•                                 X1, X2, X3, X4, X5 >=  0

La tabla inicial asociada a la Fase I queda en consecuencia definida de la siguiente forma:

X1	X2	X3	X4	X5
10	10	1	0	0	9
10	5	0	-1	1	1
0	0	0	0	1	0

Luego, se debe hacer 0 el costo reducido de X5, obteniendo la siguiente tabla inicial para hacer el uso de Simplex:

X1	X2	X3	X4	X5
10	10	1	0	0	9
10	5	0	-1	1	1
-10	-5	0	1	0	-1

Se escoge X1 como variable que entra a la base al tener el costo reducido más negativo. Posteriormente, mediante el criterio del mínimo cuociente se selecciona la variable que sale de la base: Min {9/10; 1/10} = 1/10, X5 sale de la base:

X1	X2	X3	X4	X5
0	5	1	1	-1	8
1	1/2	0	-1/10	1/10	1/10
0	0	0	0	1	0

Se obtiene la solución óptima de la Fase I, con valor óptimo cero. Luego iniciamos la Fase II del método tomando X1 y X3 como variables básicas iniciales.
FASE 2: Resolver por Simplex el problema original a partir de la solución básica factible inicial hallada en la Fase I.

X1	X2	X3	X4
0	5	1	1	8
1	1/2	0	-1/10	1/10
-2	-1	0	0	0

Hacemos cero los costos reducidos de las variables básicas:

X1	X2	X3	X4
0	5	1	1	8
1	1/2	0	-1/10	1/10
0	0	0	-1/5	1/5

X4 entra a la base. Por el criterio del mínimo cuociente, el pivote se encuentra en la fila 1, por tanto X3 sale de la base:

X1	X2	X3	X4
0	5	1	1	8
1	1	1/10	0	9/10
0	1	1/5	0	9/5

Donde la solución óptima es: X1=9/10    X2=0    Con valor óptimo V(P) = 9/5.

Solución Algebraica de un Problema de Programación Lineal

PROGRAMACIÓN LINEAL

Es un enfoque de solución de problemas elaborado para ayudar a tomar decisiones. Es un modelo matemático con una función objetivo lineal, un conjunto de restricciones lineales variables no negativas. En el ambiente de negocios actual, pueden encontrarse gran cantidad de aplicaciones.

La función objetivo define la cantidad que se va a maximizar o minimizar en un modelo de programación lineal. Las restricciones limitan o reducen el grado en que puede perseguirse el objetivo. Las variables son las entradas controlables en el problema.

Para resolver un problema de programación lineal es recomendable seguir ciertos pasos que son: 1. Entender el problema a fondo. 2. Describir el objetivo. 3. Describir cada restricción. 4. Definir las variables de decisión. 5. Escribir el objetivo en función de las variables de decisión. 6. Escribir las restricciones en función de las variables de decisión. 7. Agregar las restricciones de no negatividad.

TÉRMINOS CLAVE

Modelo Matemático Representación de un problema donde el objetivo y todas las condiciones de restricción se describen con expresiones matemáticas. Restricciones de no negatividad Conjunto de restricciones que requiere que todas las variables sean no negativas. Solución Factible Solución que satisface simultáneamente todas las restricciones. Región Factible Conjunto de todas las soluciones factibles. Variable de holgura Variable agregada al lado izquierdo de una restricción de "menos o igual que" para convertir la restricción en una igualdad. El valor de esta variable comúnmente puede interpretarse como la cantidad de recurso no usado. Forma Estándar Programación lineal en el que todas las restricciones están escritas como igualdades. La solución óptima de la forma estándar de un programa lineal es la misma que la solución óptima de la formulación original del programa lineal. Punto Extremo Desde el punto de vista gráfico, los puntos extremos son los puntos de solución factible que ocurren en los vértices o "esquinas" de la región factible. Con problemas de dos variables, los puntos extremos están determinados por la intersección de las líneas de restricción. Variable de Excedente Variable restada del lado izquierdo de una restricción de "mayor o igual que" para convertir dicha restricción en una igualdad. Generalmente el valor de esta variable puede interpretarse como la cantidad por encima de algún nivel mínimo requerido.

EJEMPLO DE UN PROBLEMA DE MAXIMIZACIÓN MÉTODO GRÁFICO Y ALGEBRAICO

RMC es una pequeña empresa que fabrica una variedad de productos basados en sustancias químicas. En un proceso de producción particular, se emplean tres materias primas para producir dos productos: un aditivo para combustible y una base para solvente. El aditivo para combustible se vende a compañías petroleras y se usa en la producción de gasolina y combustibles relacionados. La base para solvente se vende a una variedad de empresas químicas y se emplea en productos para limpieza en el hogar e industriales. Las tres materias primas se mezclan para fabricar el aditivo para combustible y la base para el solvente, tal como se muestra a continuación:

Ésta nos muestra que una tonelada de aditivo para combustible es una mezcla de 0.4 toneladas del material 1 y 0.6 toneladas del material 3. Una tonelada de la base para solvente es una mezcla de 0.5 toneladas del material 1, 0.2 toneladas del material 2 y 0.3 toneladas del material 3. La producción de RMC esta restringida por una disponibilidad limitada de las tres materias primas. Para el periodo de producción actual,RMC tiene disponibles las siguientes cantidades de materia prima:

Debido a los desechos y a la naturaleza del proceso de producción, los materiales que no se lleguen a usar en una corrida de producción no se pueden almacenar para las subsiguientes, son inútiles y deben desecharse. El departamento de contabilidad analizó las cifras de producción, asignó todos los costos relevantes y llegó a precios que, para ambos productos, producirían una contribución a la utilidad de $ 40 por cada tonelada de aditivo para combustible producida y $ 30 para cada tonelada producida de base para solvente. Ahora usaremos la programación lineal para determinar la cantidad de aditivo para combustible y la cantidad de base para solvente para producir a fin de maximizar la contribución a la ganancia total.

MÉTODO GRÁFICO

PASOS 1. Trasladar la información relevante del problema a una tabla

2. Describir el objetivo del problema, formular las restricciones y nombrar las variables Objetivo: Maximizar la contribución total a la ganancia. Restricciones: Material 1 <= 20 Material 2 <= 5 Material 3 <= 21 F = Cantidad de toneladas para aditivo para combustible por producir. S = Cantidad de toneladas para aditivo para solvente por producir 3. Formular la función objetivo MAX = 40F + 30S 4. Realizar el modelo matemático MAX = 40F +30S sujeto a: 0.4F+0.5S <= 20 Ecuación 1 0.2S <= 5 Ecuación 2 0.6F+0.3S <= 21 Ecuación 3 F,S >= 0 5. Reemplazar por 0 los valores de F y S en cada una de las ecuaciones En ecuación 1 Si F=0 entonces: 0.5S = 20 S = 20/0.5 S = 40 (F=0,S=40) Si S=0 entonces 0.4F = 20 F = 20/0.4 F = 50 (F=50,S=0) En ecuación 2 S = 5/0.2 S = 25 (F=0,S=25) En ecuación 3 Si F=0 entonces 0.3S = 21 S = 21/0.3 S = 70 (F=0,S=70) Si S=0 entonces 0.6F = 21 F = 21/0.6 F = 35 (F=35,S=0) 6. Graficar los puntos encontrados Para realizar la gráfica es necesario tomar en cuenta las siguientes recomendaciones: 1.Preparar una gráfica para cada restricción que muestre las soluciones que satisfagan la restricción. 2.Determinar la región factible identificando las soluciones que satisfacen simultáneamente todas las restricciones. 3.Trazar líneas de función objetivo que muestren los valores de las variables de decisión que producen valores especificados para la misma. 4.Mover líneas de función objetivo paralelas hacia valores mayores de la función objetivo hasta que un mayor movimiento sacaría a la línea por completo de la región factible. 5.Cualquier solución factible en la línea de función objetivo con el valor máximo encontrado por el procedimiento anterior es una solución óptima.

Del anterior gráfico podemos deducir que las lineas celestes representan cada una de las restricciones del problema, la línea roja es la función objetivo, la parte de la gráfica sombreada con puntos rojos respresenta el área factible y el punto blanco la solución óptima, a continuación veremos como llegamos a cada una de dichas conclusiones.

MÉTODO ALGEBRAICO

1. Obtener la solución óptima a. Se usan las ecuaciones 1 y 3 del problema: 0.4F+0.5S = 20 Ecuación 4 0.6F+0.3S = 21 Ecuación 5 b. Se despeja F de la ecuación 4 0.4F+0.5S = 20 0.4F = 20-0.5S F = 50-1.25S Ecaución 6 c. Se sustituye F en la ecuación 5 0.6F+0.3S = 21 0.6(50-1.25S)+0.3S = 21 30-0.75S+0.3S = 21 -0.45S = 21-30 -0.45S = -9 S = -9/-0.45 S = 20 d. Se sustituye S en la ecuación 6 F = 50-1.25S F = 50-1.25(20) F = 50-25 F = 25 Se puede observar en la gráfica que estos dos valores están representados por el punto blanco, lo cual quiere decir que esta es la solución óptima del problema. e. Sustituir los valores en la función objetivo MAX = 40F+30S MAX = 40(25)+30(20) MAX = 1,000 + 600 MAX = $ 1,600 En conclusión se deben producir 25 toneladas de combustible y 20 toneladas de base para aditivo para obtener una utilidad máxima de $ 1,600 Para encontrar la línea que atraviesa la solución factible (punto blanco) se iguala a 0 F y S en la función objetivo y se encuentran los valores: 40F+30S = 1,600 Si F es 0 entonces: 30S = 1,600 S = 1,600/30 S = 53.33 (F=0,S=53.33) SI S es 0 entonces: 40F = 1,600 F = 1,600/40 F = 40 (F=40,S=0) Como se puede observar estos puntos estan representados por la línea celeste C3 y es la que atraviesa la solución óptima.

MÉTODO SIMPLEX

El algoritmo simplex está diseñado para localizar la solución óptima concentrándose en un número seleccionado de las soluciones básicas factibles del problema. Siempre empieza en una solución básica factible y después trata de encontrar otra solución básica factible que mejorará el valor del objetivo. Los cálculos para producir la nueva solución básica incluyen dos tipos: 1. Renglón pivote: Nuevo renglón pivote = renglón pivote actual / elemento pivote 2. Todos los demás renglones, incluyendo z: Nuevo renglón = (renglón actual) – (su coeficiente de la columna pivote) x (nuevo renglón pivote)

EJEMPLO DE MAXIMIZACIÓN UTILIZANDO EL MÉTODO SIMPLEX

Continuando con el problema anterior los pasos para resolver el problema por el método simplex son: 1. Expresar el problema en forma estándar Max 40F + 30S + S1 + S2 + S3 0.4F +0.5S + S1 = 20 0.2S + S2 = 5 0.6F +0.3S +S3 = 21 F,S,S1,S2,S3 >= 0 2. Obtener el renglón z que consiste en convertir al función objetivo en valores negativos. Max z = 40F+30S+S1+S2+S3 z = -40F-30S = O 3. Resumir la forma estándar en una tabla simplex

4. Se encuentran las intersecciones de la primera variable (la más negativa) para determinar el renglón pivote. En este caso se toma la columna donde se encuentra el -40 y cada uno de los valores de la solución se divide dentro de los valores de dicha columna, escogiendo el menor valor y toda esa fila se convertirá en la fila pivote como se puede observar en la siguiente tabla:

5. Se hacen los cálculos correspondientes a. La nueva fila pivote es la S3 el objetivo es convertir el valor de 0.6 en 1 para lo cual se divide toda la fila dentro de 0.6 y se coloca en la nueva tabla. b. El resto de valores que se encuentran arriba o abajo de 0.6 deben convertirse en 0. Para este caso se desea convertir el 0.4 en 0 por lo cual se convierte el 0.4 en negativo se multiplica por el valor correspondiente en la nueva fila pivote que es 1 y se le suma el valor de esa posición en la tabla antigua que en este caso es 0.4 en resumen (-0.4*1+0.4 = 0) y asi sucesivamente con cada una de las filas:

6. Como no se tienen todavía las variables de z en positivo, entonces hay que repetir los pasos 4 y 5 hasta que todos los valores de z sean positivos:

Como se puede observar en la tabla anterior todos los valores de z son positivos, lo cual quiere decir se ha llegado a encontrar la solución óptima del problema que es producir 20 toneladas de aditivo para combustible y 25 toneladas de base para solvente para obtener una ganancia máxima de $ 1,600*. * Si observa se obtuvieron los mismos resultados que el método gráfico y algebraico anteriormente descritos

EJEMPLO DE UN PROBLEMA DE MINIMIZACIÓN

M & D Chemicals produce dos productos que se venden como materias primas a compañías que fabrican jabones para baño y detergentes para ropa. Basado en un análisis de los niveles de inventario actuales y la demanda potencial para el mes siguiente, la gerencia de M & D ha especificado que la producción combinada para los productos A y B debe ser en total al menos 350 galoes. Por separado, también debe satisfacerse un pedido de un cliente importante de 125 galones del producto A. El producto A requiere dos horas de procesamiento por galón, mientras el producto B requiere una hora de procesamiento por galón, y para el siguiente mes se dispone de 600 horas de tiempo de procesamiento. El objetivo de M & D es satisfacer estos requerimientos con un costo total de producción mínimo. Los costos de producción son $2 por galón para el producto A y $3 por galón para el producto B. Para encontrar el calendario de producción de costo mínimo, formularemos el problema de M & D Chemicals como un programa lineal. Siguiendo un procedimiento parecido al usado para el problema RMC, primero definimos las variables de decisión y la función objetivo para el problema. Sea A = Cantidad de galones del producto A B = Cantidad de galones del producto B Debido a que los costos de producción son $ 2 por galón para el producto A y $ 3 por galón para el producto B, la función objetivo que corresponde a la minimización del costo total de producción puede escribirse como: Min 2A+3B A continuación consideramos las restricciones impuestas al problema de M & D Chemicals. Para satisfacer la demanda del cliente importante de 125 galones del producto A, sabemos que A debe ser al menos 125, Por tanto, escribimos la restricción 1A >= 125 Debido a que la producción combinada para ambos productos debe ser el total al menos 350 galones, podemos escribir la restricción 1A+1B >= 350 Por último, la limitación en el tiempo de procesamiento disponible de 600 horas significa que necesitamos agregar la restricción: 2A+1B <= 600 Después de agregar las restricciones de no negatividad, tenemos el siguiente programa lineal para el problema de M & D Chemicals: Min 2A+3B Sujeto a: 1A >= 125 1A + 1B >= 350 2A + 1B <= 600 A,B >= 0 Debido a que el modelo de programación lineal sólo tiene dos variables de decisión puede usarse el procedimiento de solución gráfica para encontrar las cantidades de producción óptimas. El método gráfico para este problema, como en el problema de RMC, requiere que primero tracemos la gráfica de las líneas de restricción para encontrar la región factible. Al trazar cada línea de restricción por separado y luego verificar los puntos en cada lado de la línea, pueden identificarse las soluciones que satisfacen cada restricción. Al combinar las soluciones que satisfacen cada restricción en la misma gráfica obtenemos la región factible.

MÉTODO GRÁFICO

PASOS 1. Trasladar la información relevante del problema a una tabla

2. Describir el objetivo del problema, formular las restricciones y nombrar las variables Objetivo: Satisfacer los requerimientos con un costo mínimo. Restricciones: 1. Producir para el cliente 125 gal. de A 2. Producción combinada 350 gal. 3. 2 horas para producir A por cada B contando en total con 600 horas A = Cantidad de galones del producto A. B = Cantidad de galones del producto B. 3. Formular la función objetivo MIN = 2A + 3B 4. Realizar el modelo matemático MIN = 2A + 3B sujeto a: 1A >= 125 Ecuación 1 1A+1B >= 350 Ecuación 2 2A+1B <= 600 Ecuación 3 A,B >= 0 5. Reemplazar por 0 los valores de A y B en cada una de las ecuaciones En ecuación 1 Si B=0 entonces: (A=125,B=0) En ecuación 2 Si A es 0 1B = 350 (A=0,B=350) Si B es 0 1A = 350 (A=350,B=0) En ecuación 3 Si A=0 entonces 1B = 600 (A=0,B=600) Si B=0 entonces 2A = 600 A = 600/2 A = 300 (A=300,B=0) 6. Graficar los puntos encontrados Para realizar la gráfica es necesario tomar en cuenta las siguientes recomendaciones: 1.Preparar una gráfica para cada restricción que muestre las soluciones que satisfagan la restricción. 2.Determinar la región factible identificando las soluciones que satisfacen simultáneamente todas las restricciones. 3.Trazar líneas de función objetivo que muestren los valores de las variables de decisión que producen valores especificados para la misma. 4.Mover líneas de función objetivo paralelas hacia valores más pequeños de la función objetivo hasta que un movimiento mayor a la línea por completo de la región factible. 5.Cualquier solución factible en la línea de función objetivo con el valor más pequeño es una solución óptima.

Del anterior gráfico podemos deducir que las lineas celestes representan cada una de las restricciones del problema, la línea roja es la función objetivo, la parte de la gráfica sombreada con puntos rojos respresenta el área factible y el punto blanco la solución óptima, a continuación veremos como llegamos a cada una de dichas conclusiones.

MÉTODO ALGEBRAICO

1. Obtener la solución óptima a. Se usan las ecuaciones 2 y 3 del problema: 1A+1B = 350 Ecuación 4 2A+1B = 600 Ecuación 5 b. Se despeja A de la ecuación 4 1A=350-1B A=350-1B Ecuación 6 c. Se sustituye A en la ecuación 5 2(350-1B)+1B=600 700-2B+1B=600 -2B+1B=600-700 -1B=-100 B=-100/-1 B=100 d. Se sustituye B en la ecuación 6 A=350-1B A=350-1(100) A=350-100 A=250 Se puede observar en la gráfica que estos dos valores están representados por el punto blanco, lo cual quiere decir que esta es la solución óptima del problema. e. Sustituir los valores en la función objetivo MIN = 2A+3B MIN = 2(250)+3(100) MIN = 500+300 MIN = $800 En conclusión Se deben producir 250 galones del producto A y 100 galones del producto B para obtener un costo mínimo de $ 800 Para encontrar la línea que atraviesa la solución factible (punto blanco) se iguala a 0 A y B en la función objetivo y se encuentran los valores: 2A+3B = 800 Si A es 0 entonces: 3B=800 B=800/3 B=266.67 SI B es 0 entonces: 2A=800 A=800/2 A=400 Como se puede observar estos puntos estan representados por la línea celeste C3 y es la que atraviesa la solución óptima.

MÉTODO SIMPLEX

Se puede dividir el procedimiento del método simplex en dos fases: FASE I: Se expresa el problema en forma estándar y se añaden las variables artificiales necesarias a las restricciones. En seguida se encuentra una solución básica de las ecuaciones resultantes , por medio del método simplex, que minimice la suma de las variables artificiales. FASE II: Se utiliza la solución factible obtenida en la fase I como una solución factible inicial para el problema original, por medio del método simplex. Nuevo renglón Z= renglón Z anterior + A * Renglón A + B * Renglón B PASOS 1. Escribir el problema en forma estándar Si la restricción es mayor o igual los valores de S seran negativos por el contrario si la restricción es menor o igual serán positivos y por cada variable S se agrega una variable R positiva excepto en la tercera ecuación para este caso. Min 2A+3B+S1+S2+S3 1A -S1+R1 =125 1A+1B -S2+R2=350 2A+1B +S3=600 A,B,S1,S2,S3 >=0 2. Escribir el problema en una tabla simplex, usando el renglón r y no el z

3. Obtener el nuevo renglón r Nuevo renglón r = renglón actual + (+R1) * Renglón S1 + (+R2) * Renglón S2

4. Continuar con el simplex hasta obtener nuevamente el primer renglón r

5. Quitar las columnas R1 y R2 y agregar la función objetivo

6. Obtener el nuevo renglón z Nuevo renglón z = renglón anterior z +(+A) * renglón S1 +(+B)*renglón S2

7. Continuar con el simplex hasta que todos sean negativos

En conclusión se deben producir 250 galones del producto A y 100 galones del producto B para obtener un costo mínimo de $ 800*. Nótese que se llegaron a los mismos resultados que el método algebraico

Solución Gráfica de un Problema de Programación Lineal

El análisis gráfico es una alternativa eficiente para enfrentar la resolución de modelos de Programación Lineal en 2 variables, donde el dominio de puntos factibles (en caso de existir) se encontrará en el primer cuadrante, como producto de la intersección de las distintas restricciones del problema lineal.

Una de las propiedades básicas de un modelo de Programación Lineal que admite solución, es que ésta se encontrará en el vértice o frontera (tramo) del dominio de puntos factibles. Es decir, si luego de gráficar el dominio y evaluar los distintos vértices de modo de elegir "el mejor" candidato según sea nuestro caso (el valor de la función objetivo será la que nos permitirá discriminar cual es el mejor candidato dependiendo si estamos maximizando o minimizando).

Consideremos un Ejemplo Introductorio en 2 variables:

• D) MIN 8X + 6Y
• S.A. 2X + Y >= 10
• ...... .2X + 2Y >= 16
• ..... ..X>= 0, Y>= 0

Comentario: Nótese que corresponde al Problema Dual de P) cuya resolución se presenta en nuestro sitio como ejemplo introductorio en la utilización de Solver de MS Excel. Para ver el detalle de la resolución gráfica de P) se recomienda al usuario ingresar AQUI.

Para resolver el problema D) graficamos el dominio de puntos factibles y las curvas de nivel asociadas a la función objetivo:

El área achurada en color verde representa el dominio de puntos factibles del problema D), es decir, son las distintas combinaciones de valores que pueden adoptar las variables de decisión que satisfacen las restricciones del problema. Cabe destacar que esto corresponde a un dominio no acotado, lo que no implica que el problema no tenga solución.

Por otra parte sabemos que el óptimo de un problema lineal se encuentra en un vértice o frontera del dominio de puntos factibles. En este caso tenemos 3 vértices candidatos al óptimo los cuales se señalan con flecha blanca y azul. El vértice (X,Y)= (0,10) con V(P)=60; (X,Y)=(2,6) con V(P)=52 y (X,Y)=(8,0) con V(P)=64. El mínimo valor para la función objetivo se alcanza en (X,Y)=(2,6) con V(P)=52, el cual resulta ser la Solución Óptima de D). Sin embargo, una forma más eficiente para obtener el óptimo que no implique evaluar cada vértice en la función objetivo, es desplazando las curvas de nivel de la función objetivo en la dirección del máximo decrecimiento (en el caso de un problema de minimización). Para un problema de minimización, el mayor decrecimiento se alcanza en la dirección del vector " - Gradiente F(X,Y)", en nuestro caso el vector con dirección (-8,-6) (dirección representada por flecha roja). Luego, el óptimo se alcanza en el último punto donde las curvas de nivel intersectan al dominio de puntos factibles en la dirección del máximo decrecimiento, cuya solución obviamente corresponde a (X,Y)=(2,6) con V(P)=52.

ANÁLISIS DE SENSIBILIDAD GRÁFICO PARA 2 RESTRICCIONES

Una vez resuelto un modelo de Programación Lineal resulta útil hacer un análisis de sensibilidad que permita identificar cómo afecta en los resultados del problema variaciaciones en los parametros de éste, sin que esto pase por resolver el problema nuevamente. Nuestro sitio considera una sección aparte llamada "Sensibilidad" cuyos resultados principales se pueden consultar AQUI.

1. Variación en los Coeficientes de la Función Objetivo: La pregunta que buscamos responder es cuál es el intervalo de variación para los coeficientes de la función objetivo (cada coeficiente se analiza por separado) que mantiene la actual Solución Óptima.

Un primer acercamiento es considerar las pendientes de las restricciones activas en el óptimo, es decir, aquellas restricciones que se cumplen en igualdad (en nuestro caso restricción 1 y 2). La restricción 1 (2X + Y >=10) tiene pendiente -2. La restricción 2 (2X + 2Y >=16) tiene pendiente -1. Por otra parte la pendiente de la función objetivo dado C1=8 y C2=6 es -4/3.

En consecuencia, se mantiene la actual Solución Óptima si la pendiente de la función objetivo (curvas de nivel) varían en el intervalo de las pendientes de las actuales restricciones activas. Esto es:

-2 <= -C1/C2 <= -1 (Multiplicamos por -1)

2 >= C1/C2 >= 1

Si fijamos C2=6.

2 >= C1/6 >= 1

12 >= C1 >= 6 (Garantiza la actual Solución Óptima con C2 fijo)

Si fijamos C1=8.

2 >= 8/C2 >= 1

8 >= C2 >= 4 (Garantiza la actual Solución Óptima con C1 fijo)

Nótese que en los extremos de los intervalos además de incluir la actual Solución Óptima se consideran nuevas combinaciones del dominio que mantienen el Valor Óptimo y también son Solución Óptima de D). Esta situación determina que el problema tiene infinitas soluciones óptimas

2. Variación en los lados derechos de las restricciones (cálculo del "precio sombra"): Una pregunta común en el análisis de sensibilidad resulta ver el impacto que tiene en el valor óptimo una variación marginal del lado derecho de alguna de sus restricciones (tanto aumento o decrecimiento). El impacto en el valor óptimo por unidad de variación del lado derecho de una restricción (manteniendo el resto constante) es el precio sombra asociado a dicha restricción. En nuestro ejemplo, considere que el lado derecho de la restricción 1 (actualmente b1=10) corresponde a un recurso escaso (ejemplo: horas hombre, dinero, tiempo, etc). Si sabemos que el actual valor óptimo V(P)=52, quisieramos saber por ejemplo, cuánto aumentaría el valor óptimo se dispusiéramos de una unidad adicional del recurso escaso (es decir, pasando a b1*=11). En forma equivalente frecuentemente se plantea esta inquietud como ¿Cuánto es lo máximo que se estaría dispuesto a pagar por unidad adicional del recurso asociado a la primera restricción?. Este valor corresponde al precio sombra.

Precio Sombra Restricción 1: Primero se considera el desplazamiento paralelo de la Restricción 1 (tanto en el sentido de crecimiento o decrecimiento del lado derecho), de modo que la Solución Óptima se siga encontrando con las actuales restricciones activas (en nuestro caso R1 y R2). Por ejemplo, desplazando R1 en la dirección de su decrecimiento, el último punto donde se intersecta R1 con R2 sería en el par ordenado (X,Y)=(0,8). Se propone al usuario el cálculo de la máxima variación para R1 que se produce en (X,Y)=(8,0).

En consecuencia, el Precio Sombra asociado a la Restricción 1 queda dado por:

Un Precio Sombra igual a 2 indica por ejemplo que si el lado derecho aumenta en 1 unidad, el beneficio adicional (incremento en el Valor Óptimo) es de 2 unidades. Adicionalmente, una pregunta frecuente resulta en identificar el intervalo de variación donde el precio sombra calculado es válido. El máximo valor al que puede adoptar el lado derecho de R1 es b1*, de modo que la nueva solución se siga encontrando con R1 y R2 activas. El valor de b1* se obtiene al evaluar (X,Y)=(8,0) en la Restricción 1: 2*(8) + 1*(0)=16. Siguiendo similar razonamiento el mínimo valor que puede alcanzar el lado derecho de R1 es b1, que evaluado en (X,Y)=(0,8) en R1 se obtiene: 2*(0) + 1*(8)=8.

Se recomienda al usuario hacer el cálculo del Precio Sombra para la Restricción 2, el cual corresponde a 2. Si desea consultar un nuevo ejemplo ingrese a Resolución Gráfica en Programación Lineal. (Sitio: Investigación Operativa)

ANÁLISIS DE SENSIBILIDAD GRÁFICO PARA 3 RESTRICCIONES

La metodología y conceptos presentados para el caso de 2 restricciones no difiere, sin embargo, hay que tener especial cuidado cómo la inclusión de una tercera restricción afecta el análisis. Veamos el siguiente ejemplo:

• P) MAX 4X + 3Y
• S.A. 6X + 2Y <= 120
• ...... .1X + 4Y <= 100
• ........5X + 5Y <= 150
• ..... ..X>= 0, Y>= 0

La resolución gráfica de este ejemplo permite obtener la solución óptima X=15, Y=15 con valor óptimo V(P)=105, tal como se observa en el gráfico a continuación:

Antes de proceder con el análisis de sensibilidad es conveniente verificar si las actuales restricciones del problema estan activas en el óptimo, es decir, si se cumplen en igualdad:

• R1: 6*(15) + 2*(15) = 120 => R1 es una restricción activa
• R2: 1*(15) + 4*(15) < 100 => R2 no es una restricción activa
• R3: 5*(15) + 5*(15) = 150 => R3 es una restricción activa

En el caso que el lado derecho de la restricción sea un recurso, resulta lógico tener una disposición a pagar por unidad adicional en la medida que dicho recurso se este ocupando a máxima capacidad. En consecuencia, una restricción no activa tiene por definición un precio sombra igual a cero (caso de R2) ya que un aumento del lado derecho no aumentará el valor óptimo actual V(P)=150. Sin embargo, sólo en casos muy particulares podemos encontrar restricciones activas con precio sombra (o costo reducido) igual a cero, lo que es más la excepción que la regla.

Luego de esta introducción veamos el cálculo del precio sombra o costo reducido para la restricción 1 (R1). Primero, debemos desplazar en forma paralela la restricción 1 hasta el punto máximo donde la solución óptima se siga encontrando con las actuales restricciones activas R1 y R3. Dicho punto es (X,Y)=(30,0). Posteriormente, desplazamos en forma paralela la restricción 1 (R1) hasta el punto mínimo donde la solución óptima se siga encontrando con las actuales restricciones activas R1 y R3. Nótese que este desplazamiento queda acotado hasta el punto donde la restricción 2 (R2) se vuelve activa, que corresponde al punto (X,Y)=(6,666, 23,333) como se muestra en la siguiente gráfica:

Por consiguiente, el precio sombra asociado a la restricción 1 queda dado por:

Siguiendo un procedimiento similar se pueden obtener los precios sombras asociadas a las restantes restricciones. A continuación se presenta una tabla resumen del análisis de sensibilidad obtenido con Solver de Excel: