Programación lineal

La Programación Lineal es un procedimiento
o algoritmo matemático mediante el cual se resuelve un
problema indeterminado, formulado a través de ecuaciones
lineales, optimizando la función objetivo, también
lineal.

Consiste en optimizar (minimizar o maximizar) una
función lineal, denominada función objetivo, de tal
forma que las variables de dicha función estén
sujetas a una serie de restricciones que expresamos mediante un
sistema de inecuaciones lineales.

Historia de la
programación lineal

El problema de la resolución de un sistema lineal
de inecuaciones se remonta, al menos, a Joseph Fourier,
después de quien nace el método de
eliminación de Fourier-Motzkin. La programación
lineal se plantea como un modelo matemático desarrollado
durante la Segunda Guerra Mundial para planificar los gastos y
los retornos, a fin de reducir los costos al ejército y
aumentar las pérdidas del enemigo. Se mantuvo en secreto
hasta 1947. En la posguerra, muchas industrias lo usaron en su
planificación diaria.

Los fundadores de la técnica son George Dantzig,
quien publicó el algoritmo simplex, en 1947, John von
Neumann, que desarrolló la teoría de la dualidad en
el mismo año, y Leonid Kantoróvich, un
matemático ruso, que utiliza técnicas similares en
la economía antes de Dantzig y ganó el premio Nobel
en economía en 1975. En 1979, otro matemático ruso,
Leonid Khachiyan, diseñó el llamado Algoritmo del
elipsoide, a través del cual demostró que el
problema de la programación lineal es resoluble de manera
eficiente, es decir, en tiempo polinomial.2 Más tarde, en
1984, Narendra Karmarkar introduce un nuevo método del
punto interior para resolver problemas de programación
lineal, lo que constituiría un enorme avance en los
principios teóricos y prácticos en el
área.

El ejemplo original de Dantzig de la búsqueda de
la mejor asignación de 70 personas a 70 puestos de trabajo
es un ejemplo de la utilidad de la programación lineal. La
potencia de computación necesaria para examinar todas las
permutaciones a fin de seleccionar la mejor asignación es
inmensa (factorial de 70, 70!) ; el número de
posibles configuraciones excede al número de
partículas en el universo. Sin embargo, toma sólo
un momento encontrar la solución óptima mediante el
planteamiento del problema como una programación lineal y
la aplicación del algoritmo simplex. La teoría de
la programación lineal reduce drásticamente el
número de posibles soluciones óptimas que deben ser
revisadas.

Variables

Las variables son números reales mayores o
iguales a cero.

En caso que se requiera que el valor resultante de las
variables sea un número entero, el procedimiento de
resolución se denomina Programación
entera.

Restricciones

Las restricciones pueden ser de la forma:

Donde:

• A = valor conocido a ser respetado
  estrictamente;

• B = valor conocido que debe ser respetado o
  puede ser superado;

• C = valor conocido que no debe ser
  superado;

• j = número de la ecuación, variable de
  1 a M (número total de restricciones);

• a; b; y, c = coeficientes
  técnicos conocidos;

• X = Incógnitas, de 1 a N;

• i = número de la incógnita, variable
  de 1 a N.

En general no hay restricciones en cuanto a los valores
de N y M. Puede ser N = M; N > M;
ó, N < M.

Sin embargo si las restricciones del Tipo 1 son
N, el problema puede ser determinado, y puede no tener
sentido una optimización.

Los tres tipos de restricciones pueden darse
simultáneamente en el mismo problema.

Función
Objetivo

La función objetivo puede ser:

Programación entera

En algunos casos se requiere que la solución
óptima se componga de valores enteros para algunas de las
variables. La resolución de este problema se obtiene
analizando las posibles alternativas de valores enteros de esas
variables en un entorno alrededor de la solución obtenida
considerando las variables reales. Muchas veces la
solución del programa lineal truncado esta lejos de ser el
óptimo entero, por lo que se hace necesario usar
algún algoritmo para hallar esta solución de forma
exacta. El más famoso es el método de 'Ramificar y
Acotar' o Branch and Bound por su nombre en inglés. El
método de Ramificar y Acotar parte de la adición de
nuevas restricciones para cada variable de decisión
(acotar) que al ser evaluado independientemente (ramificar) lleva
al óptimo entero.

Aplicaciones

La programación lineal constituye un importante
campo de la optimización por varias razones, muchos
problemas prácticos de la investigación de
operaciones pueden plantearse como problemas de
programación lineal. Algunos casos especiales de
programación lineal, tales como los problemas de flujo de
redes y problemas de flujo de mercancías se consideraron
en el desarrollo de las matemáticas lo suficientemente
importantes como para generar por si mismos mucha
investigación sobre algoritmos especializados en su
solución. Una serie de algoritmos diseñados para
resolver otros tipos de problemas de optimización
constituyen casos particulares de la más amplia
técnica de la programación lineal.
Históricamente, las ideas de programación lineal
han inspirado muchos de los conceptos centrales de la
teoría de optimización tales como la dualidad, la
descomposición y la importancia de la convexidad y sus
generalizaciones. Del mismo modo, la programación lineal
es muy usada en la microeconomía y la
administración de empresas, ya sea para aumentar al
máximo los ingresos o reducir al mínimo los costos
de un sistema de producción. Algunos ejemplos son la
mezcla de alimentos, la gestión de inventarios, la cartera
y la gestión de las finanzas, la asignación de
recursos humanos y recursos de máquinas, la
planificación de campañas de publicidad,
etc.

Otros son:

• Optimización de la combinación de
  cifras comerciales en una red lineal de distribución
  de agua.

• Aprovechamiento óptimo de los recursos de una
  cuenca hidrográfica, para un año con afluencias
  caracterizadas por corresponder a una determinada
  frecuencia.

• Soporte para toma de decisión en tiempo real,
  para operación de un sistema de obras
  hidráulicas;

• Solución de problemas de
  transporte.

• Ejemplo

Éste es un caso curioso, con solo 6 variables (un
caso real de problema de transporte puede tener fácilmente
más de 1.000 variables) en el cual se aprecia la utilidad
de este procedimiento de cálculo.

Existen tres minas de carbón cuya
producción diaria es:

• La mina "a" produce 40 toneladas de
  carbón por día;

• La mina "b" otras 40 t/día;
  y,

• La Mina "c" produce 20
  t/día.

En la zona hay dos centrales termoeléctricas que
consumen:

• La central "d" consume 40 t/día de
  carbón; y,

• La central "e" consume 60
  t/día

Los costos de mercado, de transporte por tonelada
son:

• De "a" a "d" = 2 monedas

• De "a" a "e" = 11 monedas

• De "b" a "d" = 12 monedas

• De "b" a "e" = 24 monedas

• De "c" a "d" = 13 monedas

• De "c" a "e" = 18 monedas

Si se preguntase a los pobladores de la zona cómo
organizar el transporte, tal vez la mayoría
opinaría que debe aprovecharse el precio ofrecido por el
transportista que va de "a" a "d", porque es
más conveniente que los otros, debido a que es el de
más bajo precio.

En este caso, el costo total del transporte
es:

• Transporte de 40 t de "a" a "d" = 80
  monedas

• Transporte de 20 t de "c" a "e" = 360
  monedas

• Transporte de 40 t de "b" a "e" = 960
  monedas

• Total 1.400 monedas.

Sin embargo, formulando el problema para ser resuelto
por la programación lineal se tienen las siguientes
ecuaciones:

Un ejemplo de
producción en una planta de generación de
energía

La gerencia de una planta termoeléctrica de
generación de energía, que emplea carbón
como combustible, está estudiando la configuración
operativa de la planta a fin de cumplir las nuevas leyes de
control de la contaminación medio ambiental. Para la
planta en cuestión, las tasas máximas de
emisión son:

• Máxima emisión de óxido de
  azufre: 3000 partes por millón (PPM)

• Máxima emisión de partículas
  (humo): 12 kilogramos/hora (kg/h)

El carbón se traslada a la planta por ferrocarril
y se descarga en depósitos cercanos a la misma. De
aquí se lleva con una cinta transportadora a la unidad
pulverizadora, en donde se pulveriza y alimenta directamente a la
cámara de combustión, a la velocidad conveniente.
El calor producido en la cámara de combustión se
emplea para crear vapor que impulse las turbinas.

Se emplean dos tipos de carbón: tipo A, que es un
carbón duro y de quema limpia con un-bajo contenido en
azufre (bastante caro); y tipo 8, que es un carbón barato,
relativamente suave, que produce humo y tiene un alto contenido
en azufre, tal y como se puede observar en fa tabla 2. 1. El
valor térmico en términos de vapor producido es
mayor para el carbón A que para el carbón 3, siendo
de 24000 y 20000 Ib por ton respectivamente.

Como el carbón A es duro, la unidad pulverizadora
puede manejar a lo sumo 16 ton de carbón A por hora; sin
embargo puede pulverizar hasta 24 Ion de carbón B por
hora. El sistema de carga de La cinta transportadora tiene una
capacidad de 20 ton por hora y es independiente del tipo de
carbón.

Uno de los muchos interrogantes que la gerencia puede
plantearse es el siguiente: dados los límites de
emisión de los agentes contaminantes y los tipos
disponibles de carbón, ¿Cuál es la
máxima producción posible de electricidad de la
planta? La respuesta permitirá a la gerencia determinar el
margen de seguridad disponible para cubrir las demandas punta de
energía.

Tabla 2.1. Emisión de agentes
contaminantes

Elementos básicos

El modelo de Programación Lineal está
formado por tes elementos básicos: a) Variables de
decisión que tratamos de determinar, b) Objetivo (meta)
que tratamos de optimizar y c) Restricciones que necesitamos
satisfacer.

a) Variables

A corto plazo, las instalaciones de la planta son fijas.
El único aspecto del problema que es controlable y que
puede utilizarse para modificar la producción de la planta
es la cantidad de cada tipo de carbón que se queme.
Entonces, las variables de decisión del problema
son:

X1 = La cantidad de carbón A utilizada por hora
(ton/h)

X2 = La cantidad de carbón B utilizada por hora
(ton/h)

En programación lineal a menudo se hace
referencia a los aspectos controlables de un problema de
decisión como actividades. Por lo tanto, las variables X1
y X2 representan los niveles de actividad de la quema de
carbón A y carbón B, respectivamente.

HIPTESIS 1 DE PROGRAMACIÓN
LINEAL:

DIVISISILIDAD: Todas las variables pueden asumir
cualquier valor real.

Si las variables solo tienen sentido en el caso de
tomar valores discretos pero tomar un valor real elevado
(superior a 10) en la solución óptima, es aceptable
considerarlas como continuas y redondear su valor

Muchas actividades en el mundo real pueden variar de
forma continua, es decir son divisibles infinitamente. Por
ejemplo, la cantidad de carbón quemado por hora puede
ajustarse a cualquier valor dentro de unos límites
razonables. Sin embargo, hay actividades reales que sólo
pueden tomar valores enteros, por ejemplo el número de
viajes de carbón necesarios para trasladar cierta carga de
un lugar a otro o el número de equipos informáticos
que debe adquirir una empresa.

Si la actividad real no es divisible de forma infinita;
pero el nivel normal de actividad es un número grande, las
condiciones de divisibilidad pueden servir como una
aproximación conveniente. En general, esto significa que
el valor de la solución es de decenas o mayor. Los valores
fraccionarios tan sólo se redondean al entero más
cercano. Por el contrario, si el nivel normal de actividad es
relativamente pequeño, digamos menor que 10, se necesita
recurrir a la programación entera.

HIPÓTESIS 2 DE PROGRAMACIÓN
LINEAL:

CONDICIONES DE NO NEGATIVIDAD: Todas las
variables son no negativas

Esta hipótesis refleja la naturaleza de la
mayoría de ¡as actividades del mundo real; donde
rara vez tiene sentido, dentro de un contexto económico o
de ingeniería, hablar de niveles negativos de actividad.
Sin embargo, esta consideración no significa una
pérdida de generalidad. Cualquier número (positivo,
cero o negativo) puede expresarse como la diferencia algebraica
de dos números no negativos. Si una actividad puede
ocurrir tanto en niveles negativos como positivos (por ejemplo,
comprar o vender bonos), se introducen dos variables para esta
actividad, X+ para niveles no negativos, y X- para niveles no
positivos. Su diferencia X = X + – X- representa el nivel
real de la actividad. Mediante este artificio tanto X+ como X-
están restringidas a ser no negativas y son las llamadas
variables irrestrictas o libres. De hecho, el software de
optimización suele permitir al usuario definir
directamente este tipo de variables como libres e interpretando
que su rango de variación está entre menos y
más infinito.

b) Función objetivo

El objetivo de la gerencia consiste en maximizar la
producción de electricidad de la planta. Ya que la
electricidad se produce mediante vapor y existe una
relación directa entre la producción de vapor y la
de electricidad, el maximizar ¡a producción de vapor
es equivalente a maximizar la producción de electricidad.
Por lo tanto, puede replantearse el objetivo de la gerencia como
"encontrar la combinación de combustibles que maximice
¡a producción de vapor".

¿Cuánto vapor se produce para cualquier
cantidad arbitraria de carbón utilizada? Una forma simple
y sistemática de determinarlo se muestra en la tabla
2.2.

Tabla 2.2 Construcción de la Función
objetivo

Vamos a expresar la cantidad de vapor producido en miles
de libras. Por lo tanto, el carbón A produce 24 unidades y
el carbón B, 20 unidades de vapor por toneladas de
combustible. Entonces, la cantidad de vapor producida por hora
es:

• (1)  24 X1 + 20 X2 – Z

El primer miembro de (1) se denomina función
objetivo y Z es el valor de la función objetivo. Los
coeficientes de las variables se denominan coeficientes de la
función objetivo. El problema exige determinar los valores
de X1 y X2 que maximicen el valor de Z. En la figura 2.1 se
observa que (1) es una familia de rectas paralelas y que para
cada valor que demos a Z tendremos una recta, cuyos puntos
representan las posibles combinaciones de X1 y X2 que
proporcionan la misma cantidad de vapor y en definitiva de
energía. Por este motivo, se conocen como líneas de
isoproduccion (isobeneficio o isocoste, en el caso de que la
función objetivo fuera beneficio o costo respectivamente).
También podemos observar que la función objetiva es
lineal.

HITPOTESIS 3 DE PROGRAMACION LINEAL:

LINEALIDAD: Todas las relaciones entre variables
son lineales

En programación lineal esto implica:

• Proporcionalidad de las contribuciones. La
  contribución individual de cada variable es
  estrictamente proporcional a su valor; y el factor de
  proporcionalidad es constante para toda la gama de valores
  que la variable puede asumir.

• Actividad de las contribuciones. La
  contribución total de las variables es igual a la suma
  de las contribuciones individuales, sea cual sea el valor de
  las variables.

Figura 2.1. Función objetivo

Una relación tal corno Z= 5X1 + 3 X1 + 2 X2 o Z =
24 X1 + 20 X2 para X1 < = 5 y 10 + 22 X1 + 20 X2 para X1 >
5 violaría la condición de proporcionalidad;
mientras que Z = 24 X1 para X2 = 0, 20 X2 para X1 =0 y 22 X1
÷ 18 X2 para X1 > O y X2> O violarla la
actividad.

La hipótesis 3 implica beneficios constantes a
escala e impide economías y deseconomías de escala.
En la práctica esta condición posiblemente no se
cumpla con exactitud; en particular para valores muy
pequeños o muy grandes de actividad. Sin embargo, si se
cumple en forma aproximada dentro del intervalo normal de los
valores de solución, es posible emplear el modelo de
programación lineal como una buena aproximación.
Esta consideración también excluye el problema de
los costes fijos cuando se presentan para valores positivos de la
actividad, pero no para niveles cero.

Además de las condiciones de no negatividad, los
niveles de actividad deben de cumplir ciertas restricciones que
pueden ser de naturaleza física, económica o
legal.

c) Restricciones

C1. Restricción de la emisión de
partículas

La cantidad máxima de emisión de humo por
hora en una planta está limitada a 12 kg. De acuerdo con
la tabla 2.I, cada tonelada de carbón A produce 0.5 kg de
humo y cada tonelada de carbón B produce 1 kg de humo. Si
la planta quema X1 ton de carbón A y X2 de B2 la cantidad
de humo total emitida a partir de ambos tipos de carbón es
igual a su suma, que no puede exceder de 12 kg/h.

• (2) 0.5X1 + X2 <=12

Los coeficientes de las variables en las restricciones
se denominan coeficientes técnicos y al segundo miembro de
la desigualdad o término independiente se conoce como
coeficiente del segundo miembro o parámetro del lado
derecho de la restricción (en el software RHS -Right-Hand
Side).

C2 Restricción de las instalaciones de
carga.

El sistema de cinta transportadora que traslada el
carbón de los depósitos al pulverizador tiene una
capacidad de 20 ton/h. Por lo tanto, la restricción de
carga seria:

• (3) X1+X2<=2º

C3 Restricción de la capacidad del
pulverizador

La capacidad del pulverizador es de 16 ton/h para el
carbón A o de 24 ton/h para el carbón B. En otras
palabras, tarda 1116 h en pulverizar una tonelada de
carbón A y 1124 h en pulverizar una tonelada de
carbón B. Si la solución exige una
combinación de ambos tipos de carbón, el tiempo que
se tardará en pulverizar una mezcla de X1 ton de A y X2 de
B es (1/16) X1 + (1/24)X2. Son admisibles sólo aquellas
combinaciones de X1 y X2 que requieran cuando más 1h. Por
lo tanto la restricción del pulverizador es:

Obsérvese la forma en que se ha superado la
dificultad presentada por las diferentes tasas máximas.
Estas tasas se han traducido a tiempos necesarios por tonelada y
expresan la restricción en términos de tiempo en
vez de capacidad.

C4 Restricción de la emisión de
óxido de azufre

La emisión máxima de óxido de
azufre no debe exceder de 3000 PPM en ningún momento. Dado
que los dos tipos de carbón se queman en forma
simultánea, se considera que la combinación de X1
tan de carbón A, y X2 ton de carbón B por hora,
alimenta a la cámara de combustión corno una mezcla
homogénea.

El X1/(X1 + X2) de la mezcla es carbón A con una
tasa de emisión de óxido de azufre de 1800 PPM y
X2(X1 + X2) de dicha mezcla es carbón B, con una tasa de
emisión de 3800 PPM. La tasa de emisión de la
mezcla es igual al promedio ponderado de las tasas individuales
de emisión; en el que sirven como ponderaciones las
fracciones utilizadas de cada carbón. Este promedio
ponderado no puede exceder de 3000 PPM:

Multiplicando a ambos lados de la desigualdad por (X1 +
X2) y reordenando términos, se obtiene la
restricción:

(5) 1200X1 -300 X2 >=0

En la figura 2.2 se han representado las cuatro
restricciones.

Formación general de un programa
lineal

En resumen, el modelo matemático que hemos
formulado para representar el problema anterior es el
siguiente:

• Determinar los valores de las variables: X1 >= O
  y X2 >= O

• Que optimicen, maximicen en este caso (en otros
  puede ser minimizar) la función objetiva:

Max 24X1 + 20X2

• Y verifiquen las restricciones

0.5 X1 + X2 <= 12 (humo)

X1 +X2 <=20 (carga)

1.5 X1 + X2 <= 24 (pulverizador)

1200 X1 – 800 X2 >= O (azufre)

El planteamiento general de un programa lineal es el
siguiente:

Determinar los valares de as variables decisión
.XJ >= O; para, j = 1,2,..n que optimicen (maximicen o
minimicen a función objetivo:

Donde: n es el número de variables,

m es el número de restricciones y éstas
pueden ser igualdades o desigualdades del tipo <= o
>=.

Los Cj, aj y bj son los parámetros del
modelo.

HIPÓTESIS 4 DE PROGRAMACIÓN
LÍNEAL: CERTIDUMBRE

Se asume que todos los parámetros del modelo cj
aj y bj son constantes conocidas.

Región factible, solución
gráfica y variables holgura

Para que una solución sea admisible la
combinación de niveles de actividad debe satisfacer en
forma simultánea todas las restricciones, incluyendo las
condiciones de no negatividad. A tal solución se le
denomina solución factible para el problema. El conjunto
de todas las soluciones factibles forma la región factible
o conjunto de soluciones posibles. Obsérvese en la figura
2.2 que el conjunto de soluciones posibles no depende de la
función objetivo. Ésta es una interesante propiedad
de la mayoría de los modelos de Investigación
Operativa y tiene importantes consecuencias sobre el
método de resolución y las propiedades de la
solución óptima.

Si la frontera de una restricción no tiene puntos
en común con la región factible, entonces esta
restricción es redundante y puede eliminarse en
consideraciones posteriores, ya que nunca limitará los
valores de las variables. ¿Existe alguna
restricción redundante en nuestro problema?.

En la práctica, cuando un problema tiene cientos
de restricciones y cientos de variables rara vez es posible
identificar si una restricción es redundante o no. Por
fortuna, el algoritmo de resolución conocido como
método simplex funciona eficientemente, aunque el
planteamiento contenga restricciones redundantes.

Como el objetivo es maximizar fa producción de
vapor de la planta, tendremos que determinar la recta más
alta que contenga al menos una solución posible. Dicha
recta es la que corresponde a Z = 408 y los niveles de actividad
de las variables en la solución óptima son de X1 =
12 y X2 = 6 como puede observarse en la figura 2.3. Una
combinación de 12 toneladas de carbón A y 6
toneladas de carbón B por hora maximiza la
producción de vapor de la planta dentro de las
restricciones físicas y legales impuestas a las
variables.

Desde el punto de vista intuitivo, parece obvio que la
solución óptima siempre ocurrirá en fa
frontera de la región factible, ya sea en un punto extremo
o en un lado del polígono. Como se verá en el
análisis de sensibilidad, es la pendiente de la
función objetivo la que determina en qué parte de
la frontera estará situada la solución
óptima.

Si el problema exigiera la minimización de la
función objetivo ¿en que forma cambiaría el
procedimiento gráfico para encontrar la solución
óptima? Por ejemplo, se desea determinar la
solución de coste mínimo para obtener una
producción de vapor de, al menos, 216 unidades por hora y
que el coste por tonelada es de 24 $ para el carbón A y de
15 para el B. Plantea y resuelve este, problema de forma
gráfica.

En síntesis, podemos afirmar que una
solución óptima es una solución factible con
el mejor valor de la función objetivo. El mejor valor o el
valor más favorable de la función objetivo
será el más grande en los problemas de
maximización o el más pequeño en los
problemas de minimización.

No todos los problemas de programación lineal
tienen finales felices. Por una parte, puede ocurrir que las
restricciones sean inconsistentes en el sentido de que no exista
ninguna solución factible. Y por otra, la región
factible puede estar abierta en alguna dirección de manera
que la función objetivo pueda incrementarse de forma
indefinida y no exista solución finita (la solución
es no acotada). Estos casos son poco frecuentes en la
práctica. A menudo, tales soluciones son el resultado de
errores o de representaciones incorrectas en la
formulación matemática. Por tanto, al resolver un
programa lineal podemos encontrarnos con cuatro casos:

• Solución única.

• soluciones alternativas (infinitas soluciones). En
  un modelo con dos variables ocurre siempre que la
  función objetivo corta al conjunto factible en un lado
  del polígono, para el mejor valor de la misma. En la
  práctica veremos temas posteriores cómo es un
  caso mucho más frecuente de lo que a priori
  pudiéramos pensar.

• No hay solución, porque ninguna
  combinación de variables cumple todas las
  restricciones.

• Solución no acotada.

Para cualquier solución factible, la diferencia
entre el valor que toma la restricción y el coeficiente
del segundo miembro se denomina holgura (para desigualdades<=)
o exceso (para desigualdades >=). A menudo, resulta
conveniente mostrar de manera explícita esta diferencia,
introduciendo una variable adicional en cada restricción.
A estas variables se les denomina variables de holgura o de
exceso. Por conveniencia, se suele utilizar el término de
variables de holgura para ambas. Tales variables están
sujetas a las mismas consideraciones de divisibilidad y no
negatividad que las variables decisión. Entonces cada
restricción se convierte en una igualdad. Introduciendo
las variables de holgura en nuestro ejemplo:

Las variables de holgura pueden interpretaba a menudo
como recursos no utilizados o capacidad no utilizada para una
solución dada. Por ejemplo, x3 es la cantidad de capacidad
no utilizada de emisión de humo, y x4 la cantidad no
utilizada de capacidad de carga. ¿Cuál es la
interpretación correspondiente a x5? Debido a la forma en
que se obtuvo la restricción del azufre no existe una
interpretación simple para x6. Comprueba que x3 y x5 son
cero en nuestro ejemplo, mientras que x4 = 2 y x6 =
9600.

Análisis de sensibilidad de los segundos
miembros de las restricciones

Ahora vemos qué ocurre con la solución
óptima cuando varia al segundo miembro de una
restricción. Vamos a suponer que la gerencia está
considerando la instalación de un equipo que puede reducir
el humo en un 20%. Esto permitiría cumplir con las normas
legales con una emisión no controlada de humo a partir de
la cámara de combustión de hasta 15
Kg/h.

Figura 2.4. Función objetivo
alternativa

Consideraremos en primer lugar que la emisión
máxima permitida de humo se incrementó de 12 a 13
kg/h, permaneciendo iguales todos los otros coeficientes. Esto
provoca un cambio paralelo hacia arriba en la restricción
de humo. En la figura 2-5, puede verse como se agranda la
región factible. En la nueva región factible Z =
408 ya no es el valor óptimo de la función
objetivo, sino que su mejor valor se encuentra en el punto D. Por
tanto, la solución óptima cambia de A a D.
Esté cambio ocurre debido a que la restricción de
humo se cumple estrictamente en la solución óptima
del problema original. Ahora los nuevos niveles de actividad de
las variables son X1 = 11 y X2 = 7.5. Esta disminución en
X1 provoca una reducción en menos de 24 unidades en la
producción de vapor, mientras que el incremento de X2
aumenta la producción en 30 unidades. El incremento es de
6. Entonces el nuevo valor máximo de la función
objetivo será de z = 408 + 6 = 414.

La mejora en el valor óptimo de la función
objetivo debido a un incremento unitario en el segundo miembro de
una restricción se denomina coste de oportunidad o precio
sombra de la restricción. En este caso, el coste de
oportunidad de la restricción de humo es 6.

¿Qué sucedería si la emisión
máxima de humo fuera de 14,15, 16 y 17 kg/h? En la figura
2.5 se puede observar cómo el área de la
región factible se agranda por cada cambio hasta un
máximo de 16. Comprueba que por cada cambio la
función objetivo aumenta en 6.

Para un incremento superior a 16 la restricción
de humo se vuelve redundante. Ahora la solución
óptima estará restringida por las restricciones del
pulverizador y del azufre, así como por la de carga. Por
lo tanto, el coste de oportunidad de esta restricción es
cero para valores mayores de 16.

La pregunta original requería determinar el
incremento en la producción de vapor para un cambio en el
nivel permitido de humo de 12 a 15 kg/h. Este será de 3 x
6 = 18 unidades de vapor/h.

¿Cuál es el costo de oportunidad de una
restricción que no se verifique estrictamente en la
solución óptima? Resulta claro que si una parte del
recurso no se utiliza, esto es si la variable de holgura es
positiva, las cantidades adicionales de ese recurso no tienen
valor. Sólo aumentarían la cantidad de holgura. Por
lo tanto, el precio sombra de tal restricción es
cero.

Determina los precios sombra de las restricciones
restantes. Observar la interesante relación entre el coste
de oportunidad de una restricción y la variable de holgura
asociada a la misma. Cuando un recurso se utiliza completamente
su coste .de oportunidad es, por lo general, positivo (no
negativo para ser más exactos) y su variable de holgura
cero, mientras que cuando la variable de holgura es positiva el
precio sombra es cero.

Los precios sombra proporcionan a la gerencia una
valiosa información acerca de los beneficios que se pueden
obtener al suavizar las restricciones. Si estos beneficios
superan al coste que provoca suavizar una restricción
dada, entonces tales cambios son atractivos.

Figura 2.5. Análisis de sensibilidad de los
segundos miembros de las restricciones

Autor:

Universidad Peruana
Unión