Diseño, Simulación,

Optimización y Seguridad de
Procesos

MODELADO Y OPTIMIZACIÓN

Dr. Nicolás José Scenna

Dr. Néstor Hugo Rodríguez
Dr. Juan Ignacio Manassaldi

1
Contenido
El presente capítulo introduce al lector a los conceptos de Optimización con un breve repaso al
Modelado. Los temas están abordados desde la necesidad de Optimización (Introducción) que requiere a
su vez del empleo de Modelos Matemáticos del Proceso o sistema físico en General (Primera Parte) hasta
la aplicación de herramientas y algoritmos matemáticos necesarios para su resolución (Segunda Parte).
El tema en estudio está muy ligado a la posibilidad de emplear algoritmos informáticos cada vez
más rigurosos y extensos los, que a su vez, requieren de poderosos Hardware para poder resolverlos en
tiempos más o menos adecuados.
En consecuencia, el tema, lejos de agotarse, podría decirse que recién comienza, ya que las
computadoras actuales y futuras permiten y lo seguirán haciendo, resolver problemas de optimización que
en el pasado ni siquiera podían plantearse.

2
Indice
Contenido ................................................................................................................................................. 2
Indice ........................................................................................................................................................ 3
Introducción ................................................................................................................................................. 5
Teoría de optimización. ............................................................................................................................ 5
Ejemplos de aplicación de optimización en la Industria Química. ........................................................... 5
Resultados prácticos: ................................................................................................................................ 6
Jerarquía de los niveles de optimización. ................................................................................................. 6
Requisitos para la aplicación de la teoría de optimización a problemas concretos de ingeniería ............. 7
Primera parte: Modelado .............................................................................................................................. 8
Clasificación de los modelos .................................................................................................................... 8
Modelado Matemático.............................................................................................................................. 9
Construcción del modelo. ..................................................................................................................... 9
Implementación de un modelo. ............................................................................................................ 9
Principales actividades en el desarrollo de un Modelo previo a su aplicación ....................................... 10
Clasificación de los métodos de simulación ........................................................................................... 10
Simulación cualitativa y cuantitativa.................................................................................................. 10
Modelos teóricos y experimentales .................................................................................................... 11
Modelos lineales y no lineales............................................................................................................ 11
Simulación estacionaria y dinámica. Parámetros globales o distribuidos .......................................... 11
Variables continuas o discretas .......................................................................................................... 11
Simuladores de procesos químicos complejos ....................................................................................... 11
Simuladores globales u orientados a ecuaciones ................................................................................ 12
Simuladores secuenciales modulares. ................................................................................................ 12
Segunda parte: Optimización. .................................................................................................................... 16
Estructura de un problema de optimización. .......................................................................................... 16
Región factible: .................................................................................................................................. 16
Tipo de problemas .................................................................................................................................. 16
Tamaño de los problemas. .................................................................................................................. 16
Algoritmos iterativos y convergencia. ................................................................................................ 17
Aspectos de la teoría de algoritmos iterativos. ................................................................................... 17
Procedimiento genérico para resolver problemas de optimización .................................................... 17
Programación lineal................................................................................................................................ 18
La formulación del modelo LP........................................................................................................... 18
Modelo LP del problema. ................................................................................................................... 19
Condiciones especiales en modelos LP. ............................................................................................. 22
Resumen para la resolución gráfica de problemas de programación lineal. ....................................... 24
Modelado y resolución de problemas LP con hojas de cálculos. ....................................................... 25
Método Simplex. ................................................................................................................................ 35
Programación lineal entera. .................................................................................................................... 37

3
 Relajación........................................................................................................................................... 37
Resolviendo el problema de relajamiento. ......................................................................................... 37
Variables binarias. .................................................................................................................................. 42
Programación de objetivos ..................................................................................................................... 43
Definición de la variables de decisión. ............................................................................................... 43
Definición de los objetivos. ................................................................................................................ 43
Definición de las restricciones. .......................................................................................................... 43
Funciones objetivo GP. ...................................................................................................................... 43
Implementación del problema: ........................................................................................................... 44
Resumen de la programación de objetivos o GP. ............................................................................... 48
Método MINIMAX. ........................................................................................................................... 48
Optimización de objetivos múltiples ...................................................................................................... 48
Definición de las variables de decisión. ............................................................................................. 49
Definición de objetivos. ..................................................................................................................... 49
Definición de las restricciones. .......................................................................................................... 49
Implementación del modelo. .............................................................................................................. 49
Determinación de los valores de los objetivos. .................................................................................. 49
Determinación de los objetivos GP. .................................................................................................. 53
Implementación del modelo revisado................................................................................................. 53
Resumen de la optimización de multliples objetivos. ........................................................................ 55
Programación no lineal........................................................................................................................... 56
Estrategia de resolución de problemas NLP. ...................................................................................... 57
Soluciones Globales versus soluciones locales. ................................................................................. 57
Modelos de cantidad económica de orden.......................................................................................... 58
Implementando el modelo. ................................................................................................................. 60
Opciones del Solver. .......................................................................................................................... 62
Tercera parte: Condiciones de optimalidad ................................................................................................ 64
Método Simplex ..................................................................................................................................... 64
Etapa inicial:....................................................................................................................................... 65
Etapa principal: .................................................................................................................................. 65
Teoría Clásica de la programación No Lineal ........................................................................................ 68
Programas Matemáticos no Condicionados. ...................................................................................... 69
Programas Matemáticos Condicionados por Igualdades. ................................................................... 69
Problemas Matemáticos Condicionados por Desigualdades. ............................................................. 70
Cuarta Parte: Y más allá... .......................................................................................................................... 75

4
Introducción
En ocasiones es necesario optimizar un proceso, esto es, elegir la mejor opción entre varias. El
concepto de "mejor opción" es relativo. Algunos ejemplos son:
1. Aumentar la producción de productos valiosos y/o reducir los productos contaminantes,
2. Reducir el consumo energético y/o los costos operativos.
3. Incrementar las ganancias.
4. Prolongar los periodos entre paradas.
5. Aumentar la confiabilidad del sistema.
6. Reducir los costos de mantenimiento o la utilización de determinados equipos.
7. Mejorar la utilización del "Staff".

Un problema simple requiere una toma de decisión intuitiva, mientras que un problema complejo
puede tener infinitas soluciones lo que requiere la aplicación de la teoría de optimización.

Teoría de optimización

Procedimientos numéricos de cálculos

Ejemplos de aplicación de optimización en la Industria Química

1. Determinación de los mejores lugares para la ubicación de la planta.
2. Itinerario para la distribución del crudo y de los productos.
3. Dimensionamiento de tubería y layout.
4. Diseño de plantas enteras y de equipos.
5. Organigrama de mantenimiento y reemplazo de equipos.
6. Planificación y análisis de operaciones existentes.
7. Evaluación de datos de planta para construir un modelo del proceso.
8. Control de sistemas dinámicos.
Un ejemplo típico, es la elección del diámetro económico de una tubería. Es bien sabido que a

Figura 1
5
 mayor diámetro mayor es el costo fijo (contiene más material) pero disminuyen los costos
operativos (potencia de bombeo). A menores diámetros, disminuyen los costos fijos pero aumentan los
operativos. La solución óptima será aquella que minimice la suma de ambos costos, es decir el costo total.
En algunos nomogramas se puede hallar este diámetro económico sabiendo el gasto de fluido y su
densidad.
En la figura 1 se aprecia lo anterior. La línea vertical indica el diámetro de costo total más bajo,
esto es el diámetro económico.

Resultados prácticos:

Adaptación de platos de alimentación

Ahorros 980.000 $/año

Inversión de capital: 40.000 $/año

Optimización de una planta de gas

Ahorros 500.000 $/año

Inversión de capital 0 $/año

Eliminación de cuellos de botella en una

unidad de alquilación

Ahorros 1.500.000 $/año

Se incrementó la capacidad

Optimización de una refinería

Ahorros 4.000.000 $/año

Se maximizó el beneficio de la planta.
Se logró la distribución de producto óptima.

Jerarquía de los niveles de optimización.

6
 Dirección y administración

Diseño de procesos
Especificación de equipos

Operación de planta

Equipos individuales
Figura 2

Requisitos para la aplicación de la teoría de optimización a problemas

concretos de ingeniería
1. Definir los límites del sistema.
2. Elegir un criterio cuantitativo para medir la perfomance del sistema, índice que permita identificar el
mejor diseño.
Factor económico: Capital total, costo anual, retorno sobre la inversión, relación costo-beneficio, etc.
Factor tecnológico: Tiempo de producción mínimo, velocidad de producción máxima, utilización
de energía mínima
3. Seleccionar las variables del sistema que servirán para caracterizar y/o identificar a las alternativas
candidatas.
Variables independientes del sistema.
Parámetros del sistema.
4. Definir un modelo matemático que exprese la forma en que las variables están relacionadas.
Modelo matemático: Es una representación matemática de los aspectos esenciales de un sistema y
que presenta conocimiento del mismo en una manera útil (Eykhoff, 1974).
Aspectos a considerar en el modelado:
a) Ecuaciones de balances de materia y de energía.
b) Relaciones de diseño.
c) Ecuaciones que describen el fenómeno físico.
d) Inecuaciones que definen los rangos de operación permitidos, especifican los requerimientos de
perfomance máxima o mínima y/o fijan los límites en las disponibilidades de los recursos.
Los puntos 1,2,3 y 4 constituyen la formulación del problema de optimización

7
 Primera parte: Modelado
Modelar significa simular. Esto es, que la "caja negra" que representa al sistema debe dar
resultados acordes a él. En otras palabras, cuando estimulamos al modelo con una señal, esperamos que
los resultados del mismo sean similares a los que daría el sistema real.
Los principales problemas que se plantean son:
a) Encontrar la solución de un sistema de ecuaciones algebraicas no lineales (que usualmente
se efectúa mediante un método iterativo).
b) Encontrar la integración numérica de ecuaciones diferenciales ordinarias y en derivadas
parciales mediante ecuaciones discretizadas en diferencias finitas que aproximan a las
soluciones de las ecuaciones diferenciales continuas.
Con el fin de que el modelo se aproxime más a la realidad, éste se torna complejo en su
formulación y difícil en su resolución. De ahí la necesidad de emplear métodos numéricos ya sean
programados por el usuario o “enlatados”. Incluso éstos últimos requieren conocimientos teóricos para
facilitar su manejo y, en ocasiones, en especial para problemas muy específicos, es más conveniente
programar por sí mismo el modelo en una computadora.

Clasificación de los modelos

Los modelos pueden clasificarse en:

Teóricos vs. Empíricos

Lineal vs. No lineal
Estacionario vs. No estacionario
Parámetros globales vs. Parámetros Distribuidos
Variables continuas vs. Variables discretas

Figura 3

La forma matemática típica de los modelos es:

Ecuaciones
Algebraicas Ecuaciones Ecuaciones Ecuaciones
(estado integrales diferenciales diferenciales
estacionario,

Ecuaciones diferenciales Ecuaciones diferenciales ordinarias

Estado estacionario Estado no-estacionario Estado estacionario Estado no-estacionario

(parámetros (parámetros (un parámetro
distribuidos) distribuidos) distribuido) (parámetros globales)

Estado estacionario Estado no-estacionario

(conexión
multidimensional de (unidimensional)
parámetros globales)

Figura 4

8
Modelado Matemático
El principal problema consiste en identificar e incluir los principales fenómenos físicos y
químicos que son relevantes para la situación que se desea modelar.
• No existe un único modelo para un sistema.
• Jerarquía de modelos de variada complejidad y detalles ajustados a objetivos y necesidades
específicos.
• No existe ningún método de cómo construir un modelo matemático, solo lineamientos generales.

Construcción del modelo

1. Formulación del modelo.
2. Transformación en una forma adecuada para la solución.
3. Solución y análisis.
La formulación involucra a la Física, a la Química y a la Ingeniería, mientras que la
transformación y solución,a las Matemáticas y a los cálculos numéricos.
Como regla de oro para la formulación correcta del modelo conviene escribir todas las
ecuaciones sin anticipar procedimientos de solución.

Implementación de un modelo
a) Reformulación de ecuaciones y variables.
b) Elección del método de solución.
c) Elección del método numérico.
d) Generación de estimaciones iniciales de las variables.
e) Diseño de la arquitectura del programa.
f) Programación.
g) Ensayos del programa.

En todo problema de optimización y modelado hay dos objetivos en conflicto:

1- Construir un modelo suficientemente complejo que describa exactamente al sistema.
2- Construir un modelo tratable, que se pueda resolver mediante alguna técnica de resolución.
Este último problema va siendo minimizado más, cada día, con la aparición de
computadoras y programas cada vez más poderosos. Al respecto, a luego se verán algunos tipos
de simuladores, que como hemos dicho, no son otra cosa, que “resolvedores de modelos”.

9
 Principales actividades en el desarrollo de un Modelo previo a su
aplicación

Formular
Objetivos
Objetivos del modelo
Experiencia y realidad de
Criterio de evaluación
dirección
Costos de desarrollo

Seleccionar Fase de
Variables claves definición
Principio físicos

Simulación en computadora Observación

Desarrollo del modelo
Desarrollo de software Datos

Fase de
Estimar parámetros diseño

Evaluar y verificar el modelo

Aplicar el modelo

Figura 5

Clasificación de los métodos de simulación

Consideramos simulador a algún algoritmo tal que una vez ingresados ciertos valores de
entradas, entregue como resultado, el comportamiento que tendría el sistema real.

Simulación cualitativa y cuantitativa.

La simulación cualitativa tiene por objeto el estudio de las relaciones causales y las tendencias
temporales cualitativas de un sistema, como así también la propagación la propagación de perturbaciones
a través de un sistema dado.
Los valores que puede tomar una variable se llama valor cualitativo (a diferencia de los valores
numéricos cuantitativos) pudiendo ser absolutos o relativos a un valor de referencia dado. Sus valores
pueden ser tales como +,-,0. Entre los campos de aplicación de estos simuladores cualitativos se
encuentran los análisis de tendencias, supervisión y diagnóstico de fallas, análisis e interpretación de
alarmas, control estadístico de procesos, etc.
La simulación cuantitativa, en cambio, es la que describe el comportamiento de un proceso, a
través de un modelo matemático del mismo. Para ello resuelve los balances de materia, energía y cantidad
de movimiento, junto a las ecuaciones de restricción que imponen aspectos funcionales del sistema.

10
Modelos teóricos y experimentales
Obviamente son teóricos, todos aquellos basados en consideraciones que traten de predecir el
comportamiento del sistema a través de la aplicación de principios físicos u químicos.
Sistemas como las redes neuronales, permiten también predecir valores de salidas en función de
las entradas, pero para entrenar dicha red (o cualquier correlación numérica) requiere gran cantidad de
información experimental, y su validez queda enmarcada dentro de los involucrados en dichos datos. Pero
estos sistemas solo hacen tratamientos matemáticos sin considerar los fenómenos que involucran.

Modelos lineales y no lineales

En casos de programación lineal, la función objetivo es una combinación lineal y su
representación es una recta.
En los casos de programación no-lineal, la función objetivo o las restricciones o ambas no son
lineales. Este tema se tratara con más detalles en la segunda parte de este capítulo.

Simulación estacionaria y dinámica. Parámetros globales o distribuidos

La simulación estacionaria resuelve el sistema con independencia de la variable tiempo, lo que
transforma al problema en un sistema de ecuaciones algebraicas, si el modelo es a parámetros globales.
Esto último implica, que los valores de las variables son promediados, en el caso de parámetros
distribuidos, entonces serán necesarias ecuaciones diferenciales a derivadas parcial, para reflejar la
variación de dicha variable con la posición.
En la simulación dinámica, se pretende reflejar el comportamiento del sistema en su evolución
transitorio entre dos estados estacionarios cualesquiera (por ejemplo: puestas en marcha o paradas). Si los
parámetros son globales solo se requieren ecuaciones diferenciales respecto del tiempo, en los casos de
parámetros distribuidos, se requieren además ecuaciones diferenciales parciales respectos de la posición.

Variables continuas o discretas

Los modelos en los que las variables son continuas resultan más frecuentes, pero en ocasiones
pueden presentarse casos en los que es necesaria la simulación de eventos discretos. Existen numerosos
procesos en que solo pueden simularse desde este punto de vista. Por ejemplo, la simulación o diseño de
plantas batch multiproducto o multipropósito, o ambas simultáneamente, poseen características que
impone un modelo discreto para contemplar ciertos eventos de interés. En estos casos se requiere utilizar
modelos especiales.

Simuladores de procesos químicos complejos

No es lo mismo modelar un equipo individual o un proceso. En efecto, en el primer caso, solo se
plantea calcular las salidas en función de las variables de entrada de acuerdo a los modelos antes citados.
Para el caso de un proceso, se deberá tener una biblioteca de módulos individuales para poder
simular cada equipo u operación. Luego deberá considerarse la interacción entre los mismos, de acuerdo
al diagrama de flujo que establece la conexión entre ellos. La situación se torna más compleja cuando
existen reciclos ya que se requerirán técnicas de rasgado, particionado y ordenamiento, que permitan
establecer el mínimo número de corrientes de corte, en las cuales iniciar el cálculo. En general, se
emplean métodos numéricos iterativos, tanto para sistemas de ecuaciones algebraicas como de ecuaciones
diferenciales.
Además, deberá disponerse de una importante biblioteca de propiedades fisicoquímicas tanto de
sustancias puras como de mezclas.

Los simuladores más empleados son:

• Simuladores globales u orientados a ecuaciones.
• Simuladores secuenciales modulares.
• Simuladores híbridos o modular secuencial-simultáneo.

11
Simuladores globales u orientados a ecuaciones
Bajo este enfoque, las ecuaciones que rigen cada equipo se integran entre sí, dando origen a un
gran sistema de ecuaciones algebraicas que representan a todo el conjunto o planta a simular. La solución
del problema consiste en resolver un gran sistema de ecuaciones algebraicas, por lo general, altamente no
lineal.
El inconveniente de esta filosofía consiste en problemas de convergencia, para lo cual, las
variables deben ser inicializadas cerca de la solución. El otro problema consiste en la existencia de varias
soluciones matemáticamente factibles, por ser el sistema fuertemente no lineal.
Además debe citarse la pérdida de la asociación entre la ecuación y el equipo correspondiente,
por lo que de haber inconvenientes, es difícil identificar el lugar correspondiente al mismo (en otras
palabras a que equipo corresponde una ecuación en particular).
Como gran ventaja, cabe citar el hecho de que la velocidad de convergencia es cuadrática es
decir mayor que en los modulares secuenciales. Además, el sistema basado en ecuaciones, permite adosar
ecuaciones de restricción y funciones objetivos, por lo que la tarea de optimización (tema a tratar en el
presente estudio) se puede realizar en forma directa. Esta flexibilidad es imposible en los simuladores
secuenciales modulares, debido a que los módulos están orientados y definidos en forma rígida, por lo
que no admiten la incorporación de restricciones y/o variables.

Simuladores globales u orientados a ecuaciones.

o Cada equipo se representa por las ecuaciones que lo modelan.

El modelo es la integración de todos los subsistemas.
o Desaparece la distinción entre variables de proceso y
parámetros operativos, por lo tanto se simplifican los
problemas de diseño.
o Resolución simultánea del sistema de ecuaciones algebraicas
(no lineales) resultante
o Mayor velocidad de convergencia
o Necesita una mejor inicialización (mejor cuanto mayor sea el
problema a resolver).
o A mayor complejidad, menor confiabilidad en los resultados y
más problemas de convergencia (soluciones sin sentido físico).
o Más difícil de usar por “no especialistas “.

Simuladores secuenciales modulares

Estos simuladores resuelven cada tipo de equipo por separado usando las técnicas que son
adecuadas para el mismo. El flujo de información coincide con el “flujo físico” de la planta.
Conceptualmente, bajo esta filosofía, para cada módulo de simulación (equipos) deberá
plantearse su modelo matemático. Deberá considerarse, además, los grados de libertad, a fin de que la
solución sea única. El enfoque en la teoría secuencial modular impone conocer las condiciones de las
corrientes de entradas y por su parte, calculan las condiciones de las corrientes de salida y los
correspondientes parámetros de operación si correspondiera. Esto impone cierta rigidez, que sacrifica,
según el caso, la posibilidad de encontrar asignaciones tales que minimicen el tiempo de cómputo. Sin
embargo esto resulta conveniente desde otro punto de vista, ya que de esta manera se impone una
dirección al flujo de información entre módulos.
Para ciertos equipos, algunos parámetros deben ser ingresados por el operador. Por ejemplo, en
un intercambiador de calor, son datos las condiciones de entrada pero U se deberá calcular por algún
método específico o será incorporado como dato por el usuario (como U.A).

12
Características de un simulador modular secuencial
Para comprender el desempeño de un simulador secuencial es necesario estudiar la estructura y
la arquitectura del mismo. Básicamente podríamos diferenciar en principio tres funciones o secciones
perfectamente diferenciadas.
1) La lógica central o lógica general del simulador
2) Sección encargada de la estimación de las propiedades fisicoquímicas.
3) La biblioteca de módulos de equipos, es decir cada uno de los módulos que representan al
comportamiento de válvulas, intercambiadores, sistema de destilación, sumadores, divisores,
flash, compresores, etc.
La primer sección, es decir la lógica general o central o de administración a su vez comprende
principalmente las siguientes subsecciones:
• La sección de entrada
• La sección de salida de resultados
• La lógica general de administración
La lógica general de administración propiamente dicha es la que está encargada de administrar
los distintos procesos que deben ejecutarse para lograr la simulación de un proceso dado. Es decir deberá
procesar el diagrama de flujos, decidir si puede resolverse en una secuencia lineal o si existen reciclos,
seleccionar sobre cuáles variables deberá iterarse, determinar en función de las corrientes de corte el
orden en el cual serán resueltos los equipos, etc. Esto es, deberá manipular un banco de algoritmos que
permitan, dado el DFI (diagrama de flujo de información) de la planta, realizar el rasgado, particionado y
ordenamiento o secuencia de resolución.
Por otra parte, al finalizar el proceso iterativo de acuerdo al criterio de convergencia definido por
el usuario, procederá a detener el proceso de simulación, retener los resultados, es decir almacenar todos
los valores convergidos de las corrientes de proceso, los valores y parámetros internos de los equipos, por
ejemplo los perfiles internos de torres, composiciones, caudales, temperaturas y presiones de cada etapa,
etc. Si no se lograra convergencia luego de una cantidad de iteraciones propiamente estipulada, la lógica
central del simulador detendrá el proceso iterativo e informará al usuario por medio del mensaje de error
que corresponda.
También, para facilitar la tarea del usuario, existirá un sistema de almacenamiento de
información (por ejemplo un Administrador de Base de Datos), en el cual pueden almacenarse resultados
de las diversas simulaciones para una misma planta, a los efectos de facilitar la presentación en forma
gráfica de los resultados obtenidos, por comparación entre las distintas alternativas simuladas, si fuere
necesario.
Por último esta lógica general de administración, que es el verdadero cerebro del simulador,
podrá o no tener en cuenta interacciones con otros utilitarios o con otros programas. Por ejemplo, estos
datos podrían ser empleados por algún programa de diseño. En general, los simuladores comerciales
disponibles tienden cada vez más a incorporar programas específicos de cálculo a los efectos de facilitar
la integración de tareas (simulación y Pre-diseño) por ejemplo.
A los efectos de la integrabilidad de la información, se procura que las herramientas del
simulador sean compatibles con otras de uso comercial como procesadores de textos, planillas de cálculo,
bases de datos, a fin de dar la máxima utilidad a la información.
En cuanto al sistema de entrada/salida de datos, es una parte fundamental de todo simulador de
uso general. Se procurará que sea lo más amigable posible con el usuario, en general emplean entornos
compatibles con Windows, donde cada equipo puede abrirse como una ventana para incorporarse o
modificarse los parámetros del mismo. Esto permite al usuario inexperto o poco conocedor del tema
pueda hacer uso del sistema.

13
Desarrollo de módulos generales para un simulador modular
En general, los items a tener en cuenta para abordar el desarrollo de módulos de simulación con
el objeto de utilizarlos acoplados a la estructura de un simulador de procesos de propósitos generales son
los siguientes:
• Esquema de funcionamiento de un módulo generalizado:
Se deben considerar las posibles variantes acerca de los distintos tipos de datos
conocidos (corrientes de entradas, de salidas, etc.), los grados de libertad, parámetros,
filosofía de cálculo, relación con el sistema general, etc.
• Interrelación módulo de equipo -base de datos:
Aquí se analiza la descripción de la estructura general de conexión (intercambio de
datos) entre el módulo de simulación (equipo) y el sistema de almacenamiento de datos
del simulador (constantes fisicoquímicos, parámetros de equipos, sistema de entrada-
salida, etc.).
• Selección de parámetros de equipos:
En este punto se describe la estructuración del módulo de acuerdo a las necesidades de
la operación a simular. Esto es, definir los grados de libertad del sistema, los parámetros
a fijar según los mismos, etc.
• Niveles de cálculo:
En este punto se identifica la rigurosidad del cálculo que se desea (grados de
simplificación).
• Interrelación módulo de equipo-fisicoquímica:
Describe el esquema que relaciona los módulos de equipos con los programas de
estimación de propiedades fisicoquímicas.
Arquitectura típica de un simulador genérico, modular secuencial

Programas de
Propiedades estimación de Constantes
fisicoquímicas propiedades fisicoquímicas
Parámetros fisicoquímicas

Base de datos
fisicoquímicos

Variables Variables
de las MODELO DE EQUIPO de las
corrientes corrientes
de entrada de salida

Variables de retención interna

Resultados
(parámetros y resultados del equipo)
calculados

HISTORIA
Base de datos
Del Simulador
Figura 6: Arquitectura típica de un simulador modular secuencial

14
 PRINCIPIO

Ubicación del equipo Base de datos

en la Base de Datos del simulador

Dimensionamiento variable
del arreglo de trabajo

Recuperación de datos Base de datos

de entrada y del simulador
parámetros del equipo

Programas Resolución Subrutinas

fisicoquímicos del equipo
accesorias

Archivos de constantes Almacena los datos de

Base de datos
fisicoquímicas las corrientes de salida y
del simulador
los resultados de equipo

Base de Datos Cierre de la

Base de Datos
Fisicoquímica

FIN

Figura 7: Esquema de cálculo de cada módulo o equipo del simulador

Un punto importante en la nueva generación de simuladores orientados al manejo de grandes

cantidades de información es la administración y almacenamiento de la misma. En general debe definirse
algún tipo de administrador de base de datos para lograr una integración entre los módulos de la lógica
central, de ejecución, programas fisicoquímicos, entrada/salida de información, y almacenamiento de los
datos en sí.
Finalmente, no se debe perder de vista, que el más potente algoritmo de cálculo, se torna inútil si
las propiedades fisicoquímicas son pocos conocidas o si su calculo involucra errores muy importantes.
En ocasiones, para cálculos preliminares, conviene emplear métodos semirigurosos en los que el
error introducido es pequeño (en comparación con aquellos que involucren a las propiedades
fisicoquímicas) y que por otro lado se ejecutan más rápidamente. Esto no quita el hecho de que deban
aplicarse métodos más rigurosos, pero los limita al cálculo final.

15
Segunda parte: Optimización
Como ya habíamos mencionado, en los problemas de optimización existen dos objetivos en
conflicto:
1. Construir un modelo suficientemente preciso que describa apropiadamente el problema.
2. Construir un modelo tratable, que se pueda resolver mediante alguna técnica de resolución.

Estructura de un problema de optimización

Se buscará maximizar o minimizar una función llamada objetivo cuyas variables deber estar
regidas, además, por cierto número de restricciones que pueden ser de igualdad o desigualdad.
Maximizar o minimizar ƒ(x) Función objetivo
Sujeto a:
Hk(x) =0 , k=1,2,...,K Restricciones de igualdad
Gj(x) ≥ 0 , j=1,2,...,J Restricciones de desigualdad
xil ≤ xi ≤ xiv , i=1,2,...,N Restricciones de desigualdad

Región factible:
Es el conjunto de valores de las variables independientes que satisfacen simultáneamente las
restricciones de igualdad y de desigualdad. Así por ejemplo, las condiciones de igualdad solo se
satisfacen en una curva, en el caso de que se traten de solamente dos variables y, obviamente, pueda
representarse en el plano. Para el mismo caso una condición de desigualdad, separa al plano en 2 zonas,
una de valores factibles y la otra de valores no factibles.
Región factible de un problema de optimización que involucra a 2 variables.

Tipo de problemas
1. Problemas no restringidos.
2. Problemas restringidos.

Tamaño de los problemas

1. Problemas de pequeña escala.
Menos de 5 variables incógnitas.

16
 Menos de 5 restricciones.
Enfoque de resolución: Solución numérica computacional basada en conceptos de la teoría de
optimización multiplicadores de Lagrange, teoremas de Kuhn-Tucker, etc.

2. Problemas de escala intermedia.

Número de variables incógnitas: 5 a 100.
Número de restricciones: 5 a 100.
Enfoque de resolución: Técnicas de búsqueda computacional a través del espacio de
soluciones factibles y para cada punto mejorado.
PNL (programación no lineal): 100 a 200 variables.
PL (programación lineal): 400 restricciones y 1000 variables.

3. Problemas de gran escala.

Del orden de 1000 variables y restricciones.
Enfoque de resolución: Técnicas de resolución que utilizan estructuras especiales del
problema de programación en gran escala.

Algoritmos iterativos y convergencia.

Las computadoras digitales de alta velocidad permiten una alta capacidad para resolver en forma
eficiente operaciones repetitivas, esto es, son ideales para ejecutar algoritmos iterativos.
Objeto del algoritmo:
Es la búsqueda de un vector óptimo x* (solución).
1) Selecciona un vector inicial x0.
2) A partir de x0 genera un vector mejorado x1.
3) A partir de x1 genera un vector mejorado x2 y así sucesivamente encuentra una secuencia de
puntos cada vez mejores,
x0, x1, x2, ... , xk, ... , xn,
que se aproximan a un punto solución x*
Programación lineal:
La secuencia generada permite encontrar la solución después de un número finito de pasos.
Programación no lineal:
Generalmente, la secuencia no alcanza en forma exacta a la solución del problema, pero
converge hacia ella.

Aspectos de la teoría de algoritmos iterativos.

1- Concepción del algoritmo.
2- Análisis de la convergencia global.
3- Análisis de la convergencia local.

Procedimiento genérico para resolver problemas de optimización

1- Analizar el proceso y definir las variables y características específicas de interés. Preparar una
lista de todas las variables.
2- Determinar el criterio de optimización y especificar la función objetivo en términos de las
variables listadas en 1), conjuntamente con los coeficientes.
3- Desarrollar, vía expresiones matemáticas, un modelo de proceso o equipo que relaciones las
variables de entrada-salida de un proceso con los coeficientes asociados.

17
4- Si la formulación del problema es demasiado grande:
a) Dividirlo en partes manejables.
b) Simplificar la función objetivo.
5- Aplicar una técnica de optimización adecuada respecto a la formulación matemática del
problema
6- Verificar las respuestas y examinar la sensibilidad de los resultados a cambios en los coeficientes
e hipótesis del problema.

Programación lineal
El modelo de programación lineal (LP) es extensamente utilizado en casi todas las áreas del
conocimiento. La relación lineal entre variables le confiere la particularidad de ser un modelo fácil de
generar y simple de resolver y analizar. Esto permite automatizar el proceso de generación del modelo,
por lo que es posible generar grandes modelos LP. Publicaciones recientes han reportado trabajo con
modelos LP de más de cien mil variables.
Para casos de 2 variables, puede emplearse el método gráfico. Para modelos de 2 a más
variables, se emplea un algoritmo llamado SIMPLEX diseñado por Dantzig en la década del cincuenta.
En la década del ochenta, se ha publicado el método de Karmarkar, pero aun, el simplex es más
empleado.
En los casos de programación lineal, tanto la función objetivo, como las restricciones, son
combinaciones lineales de las variables de interés:

Maximizar o minimizar: ƒ0(X1 , X2 , ... , Xn)

Sujeto a: ƒ1(X1 , X2 , ... , Xn) ≤ b1
ƒ2(X1 , X2 , ... , Xn) < b2
..............................
ƒk(X1 , X2 , ... , Xn) ≥ bk
...............................
ƒn(X1 , X2 , ... , Xn) = bn
Para interpretar mejor el uso de éstas técnicas, recurriremos a un ejemplo. La empresa Blue
Ridge Hot Tubs, fabrica y vende dos modelos de baños calientes: Aqua-Spa y la Hydro-Lux. Su
propietario y gerente, Howie Jones, necesita decidir cuanto de cada tipo producir durante el ciclo
siguiente de producción. El baño en sí y las bombas, la compra prefabricadas, a las cuales le adiciona la
tubería, para confeccionar dichos baños. Howie instala el mismo tipo de bombas a ambos baños. Su
disposición de las mismas es de 200 en cada ciclo. Ambos baños tienen diferentes requerimientos de
material y mano de obra. Así, cada Aqua-Spa requieren 9 horas de mano de obra y 12 pies de tubería
mientras que cada Hydro-Lux requiere 6 horas de mano de obra y 16 pies de tubería. Howie, espera
disponer de 1566 horas de mano de obra y 2880 pies de tubería en cada ciclo de producción. Cada Aqua-
Spa provee de una ganancia de 350$ mientras que cada Hydro-Lux vendido reporta 300$. Su propietario
confía en vender toda su producción. La pregunta es, ¿Cuántos Aqua-Spa y cuántos Hydro-Lux producir
para maximizar las ganancias en cada ciclo?

La formulación del modelo LP

Los pasos generales a seguir en la formulación de un modelo LP, son:
1. Comprender el problema.
A pesar de la obviedad del mismo, este paso debe ser previo al de formulación de la función
objetivo, para que ésta enfoque realmente a la resolución de dicho problema.

En nuestro Caso implica, determinar el número a producir de cada tipo de baño caliente para
obtener la máxima ganancia, disponiendo de 200 bombas, 1566 horas de mano de obra y 2880
pies de tubería.

18
2. Identificar las variables de decisión.
Así, en nuestro ejemplo, X1 será la cantidad de Aqua-Spa y X2 los de Hydro-Lux a producir.

3. Formular la función objetivo como combinación lineal de las variables de decisión.

Esta función expresa la relación matemática entre las variables que debe ser maximizada o
minimizada.
En nuestro ejemplo: por cada Aqua-Spa vendido (X1), ingresan 350 $ y por cada Hydro-Lux (X2),
en cambio, 300 $. La ganancia total será:
350 X1 + 300 X2 valor que se desea maximizar.

4. Formular las restricciones como combinación lineal de la variables de decisión.

Estos son valores que restringen las variables en el problema a resolver.
En nuestro ejemplo: tenemos tres restricciones. La primera en que el número de bombas
disponibles es de 200, valor que no puede superarse. Esto se expresaría:
1X1 + 1 X2 ≤ 200
La segunda restricción es el número de horas disponibles: 1566. Cada baño requiere un numero
diferente de horas, y juntas no deben superar el límite permitido:
9 X1 + 6 X2 ≤ 1566
La tercera y última restricción es sobre los pies de tuberías disponibles. La cantidad total requerida
deberá ser menor o igual que 2880:
12 X1 + 16 X2 ≤ 2880

5. Identificar los límites superiores e inferiores de las variables.

En nuestro ejemplo, se asume que ni X1 ni X2 deben ser negativos o ceros, lo que se expresa en
forma matemática, como:
X1 ≥ 0
X2 ≥ 0

Modelo LP del problema

En resumen, el modelo planteado para el problema será:

MAX 350 Xl + 300 X2

Sujeto a: 1 X1 + 1 X2 ≤ 200
9 X1 + 6 X2 ≤ 1566
12 X1 + 16 X2 ≤ 2880
1 X1 ≥ 0
1 X2 ≥ 0

Resolución intuitiva del modelo de LP

Esta se basa en un método gráfico. En primer lugar, dibujar un sistema de coordenadas
cartesianas en las dos variables del problema. Cada restricción representada por una desigualdad, divide
al espacio en dos zonas: una factible y la otra, no. Las igualdades, solo se cumplen en una recta. Una vez
introducidas todas las restricciones quedará una zona en la que las variables asumen todas las
restricciones.

Zona factible a las restricciones del problema:

19
 Figura 8

Figura 9

En algún punto de la zona pintada, las variables, maximizan la función objetivo. Ver que las condiciones
de no-negatividad de las variables están incluidas en los ejes coordenados. Para seguir Supongamos un
valor para la función objetivo (por ejemplo 35000 $) y grafiquemos su línea.
Supongamos ahora una ganancia de 52500 $ y grafiquemos este nuevo objetivo.

20
 Figura 10

Vemos que la nueva solución es paralela a la anterior. Para hallar la óptima, se debe trazar una
paralela que pase por el punto más alejado de la zona factible.

Figura 11

El punto óptimo se encuentra para X1= 122 y X2= 78. Esto significa que deberán producirse 122
Aqua-Spa y 78 Hydro-Lux para que la ganancia sea máxima, esto es:
350 $ * 122 + 300 $ * 78 = 66100 $
Cualquier otro punto que caiga en la zona factible, dará una menor ganancia, mientras que no
puede haber otro punto de mayor ganancia y a la vez cumpla las restricciones del problema. De hecho, la
solución óptima, siempre caerá sobre uno de los vértices generados por las rectas que representan las
restricciones. En nuestro caso son cinco los vértices:

21
 Nº X1 X2 Ganancia
1 0 0 0$
2 0 180 54000 $
3 80 120 64000 $
4 122 78 66100 $
5 174 0 60900 $

El punto 4 es el óptimo.

Condiciones especiales en modelos LP

Soluciones óptimas alternativas
Hemos visto que en nuestro ejemplo, la solución era única. Se debe a que la curva de nivel de
máxima ganancia solo intercepta en un punto a la zona factible, precisamente en el vértice formado por
las restricciones dadas por las bombas (línea verde, v) y por la disponibilidad de horas (línea roja, r),
como se aprecia en una ampliación de dicha zona:

Figura 12

Vemos que si la curva de nivel representativa del objetivo fuera paralela algunas de las
restricciones todos los puntos de intersección serían igualmente factibles e igualmente óptimos. Esto no es
una dificultad, de hecho en casos de programación y optimización de múltiples objetivos, esto es muy
deseable.

22
 Figura 13
El caso se presentó al modificar las condiciones de la función objetivo. Si cada Aqua-Spa reporta
450 $ (en lugar de los 350 $) todos los puntos de intersección darán la misma ganancia de 78300 $.
Restricciones redundantes
Se presenta, cuando una restricción no determina, en sí, a la zona factible:

Figura 14

23
 El modelo es el mismo al anterior, solo que se aumentó la disponibilidad de bombas de 200 a
225. Por lo tanto la condición redundante corresponde a las bombas. Esto significa que aunque se dispone
de más bombas la solución óptima no mejora. En éste caso, el modelo podría resolverse sin ésta
restricción.
Soluciones ilimitadas
Hemos visto, que las restricciones imponen un área cerrada, pero podría darse el caso, que el área sea
infinita y, por lo tanto, siempre habrá una solución mayor hasta tender al infinito. Se dice, entonces, que
la zona factible es ilimitada, por lo que el método de identificar la solución óptima a través de los vértices
no puede aplicarse.

Figura 15

Solución Infactible
Se produce cuando las regiones factibles de cada restricción no se interceptan en ningún punto.
En otras palabras habrá puntos que cumplan una o varias restricciones pero no todas. En éste caso el
problema no tiene solución.

Figura 16

24
Resumen para la resolución gráfica de problemas de programación lineal
1. Dibujar las rectas correspondientes a cada restricción
2.
3. Identificar la zona factible, esto es, los puntos del gráfico que satisfacen simultáneamente a todas las
restricciones.
4. Localizar la solución óptima por uno de los siguientes métodos:
a. Dibujar una o más curvas de nivel para función objetivo y determinar la dirección en la
cual la función objetivo logra su resultado deseado (máximo o mínimo). Trasladar en
forma paralela una recta a dichas curvas de nivel en la dirección determinada hasta que
la misma intercepte al punto más lejano. Determinar las coordenadas de dicho punto, el
cual será el óptimo
b. Identificar todos los puntos extremos de la región factible (vértices) y determinar el
valor de la función objetivo en cada uno de ellos. Si la zona factible es limitada, el
punto con el mejor resultado será el óptimo.

Modelado y resolución de problemas LP con hojas de cálculos.

La resolución de éste tipo de problemas se ha vuelto tan importante que numerosos software de
hoja de cálculos, como Excel, Quattro Pro y Lotus 1-2-3, han incorporado una herramienta llamada
Solver que permite encontrar objetivos en funciones incorporadas en dichas planillas. El objetivo puede
ser encontrar máximo, mínimo o simplemente un número determinado.
Además de la flexibilidad de los sistemas informáticos respecto de los gráficos, éstos últimos se
vuelven inútiles cuando el problema incluye más de 2 variables. Como veremos a continuación, no solo
los resultados son evaluados por el programa sino también los límites y sensibilidad de dichas soluciones.
A manera de ejemplo, resolveremos el mismo problema anterior aplicando el Solver de Excel, el
cual puede encontrarse en herramientas, en caso de que no haya sido instalado.
Pasos a seguir en la implementación de un problema LP en hoja de cálculo.
1. Organizar los datos del modelo en la hoja.
El objetivo es que el reporte final sea lo más claro a la hora de leerlo. Para ello, cada restricción,
la función objetivo y las variables serán identificadas por etiquetas.
2. Reservar celdas separadas en la planilla para representar cada variable de decisión en el modelo
algebraico
3. Crear una fórmula en una celda de la hoja para representar la función objetivo.
4. Para cada una de las restricciones, crear una fórmula en celdas apartes de la planilla que
represente el miembro izquierdo de dichas fórmulas. Los valores que pueden tomar las
restricciones se colocaran en celdas contiguas para facilitar su identificación con el valor que
finalmente tomaran dichas restricciones.
Implementado el modelo.
Las celdas B5 y C5 contienen los valores que deseamos hallar (se inicializan con ceros). Las
celdas B6 y C6 contienen las ganancia que provee cada baño vendido. La ganancia total será pues:
B5*B6 + C5*C6
Esta fórmula puede apreciarse en la figura 17, donde el valor es cero debido a que la variables
fueron inicializadas así. La fórmula de la restricción por bombas disponibles está en la celda D9,
B5*B9 + C5*C9
Que deberá ser menor o igual al que figura en E9. La restricción por horas de operación
disponibles está formulada en D10, y es,
B5*B10 + C5*C10
Cuyo valor deberá ser menor o igual que el que figura en E10. La fórmula de restricción por pies
de tuberías disponibles está en la celda D11,y es,
B5*B11 + C5*C11

25
 Que debe valer igual o menos que el que figura en la celda E11.
La hoja completa queda como la que se observa en la figura 17. Para resolver el problema se
busca en herramientas el comando Solver. Aparecerá una pantalla como el de la figura 18. En la misma
puede apreciarse donde se debe introducir la función objetivo, las celdas cambiantes (las variables que
deseamos encontrar) y las restricciones. Esta última tiene un cuadro de diálogo que permite introducir
igualdades, desigualdades o funciones lógicas como se aprecia en la figura 19.

Figura 17

Figura 18

26
 En nuestro caso nos interesa que los valores necesarios sean menores o iguales a los disponibles. A
través del cuadro de diálogo de la figura 19, introducimos todas las restricciones incluso la de no
negatividad de las variables de interés. La pantalla del Solver quedará como el de la figura 20.

Figura 19

Figura 20

Al presionar en el botón Resolver, el Solver encuentra la solución y agrega en la planilla. Una

vez resuelta, el Solver, suministra 3 informes: Respuestas, Sensibilidad y Límites.
Por lo pronto vemos que la solución buscada es igual al del método gráfico, esto es, que
produciendo 122 Aqua-Spas y 78 Hydro-Luxes, se obtiene la máxima ganancia. En la figura 20 se
aprecia que el objetivo buscado era el máximo, pero podría ser el mínimo o cualquier otro valor. La
ganancia óptima será de 66.100 $. Se emplean todas las bombas, todas las horas, pero solo 2712 pies
de tubería de los 2880 pies que se disponían.
Vemos lo sencillo que sería modificar algunas de las restricciones y encontrar una nueva
solución.

27
 Figura 21
Reporte de resultados
En la figura 22 se aprecian los resultados. En la celda objetivo se lee $0 que es el valor inicial y
$66.100 que es el valor final u óptimo. En celdas cambiantes, los valores iniciales y finales. En
restricciones aparecen los valores necesarios y los disponibles y su diferencia (Divergencia). Cuando
la divergencia es 0, la restricción es de cumplimiento obligatorio, en otros casos se dice que es
opcional. Este tipo de informes (y los que se discutirán luego) son propicios para ser presentados
puesto que son claros en su reporte de la solución.

28
 Figura 22

Reporte de sensibilidad
Facilita información acerca de la sensibilidad de la solución a que se realicen pequeños cambios
en la fórmula definida en el cuadro Definir celda objetivo del cuadro de diálogo Parámetros de Solver o
de las restricciones. No se genera este informe para los modelos que tengan restricciones enteras. En
modelos no lineales, el informe facilita los valores para las gradientes y los multiplicadores de Lagrange.
En los modelos lineales, el informe incluye costos reducidos, otros precios, coeficiente de objetivos (con
aumentos y disminuciones permitidos) y rangos de restricciones hacia la derecha.
En la figura 23 se aprecia dicho informe. El multiplicador de Lagrange dá una buena medida del
mejoramiento de la función objetivo al aumentar la restricción correspondiente en un valor unitario. Así,
en la restricción correspondiente a Bombas, el multiplicador de Lagrange es igual a 200, esto quiere decir
que si aumentamos el número de bombas disponibles de 200 a 201, la ganancia aumentará en 200 $, lo
que daría un valor total de 66.300 $. En cambio si aumentamos en una hora las disponibles para mano de
obra, el aumento es de solo 16.66666, lo que llevaría la ganancia total a 66.116 $ con 67 centavos. Por
último, si aumentáramos en un pie la longitud de tuberías disponibles, la ganancia no varía.
Este tipo de reporte, nos indica claramente sobre cual restricción deberíamos trabajar para
mejorar la ganancia. Es claro que los pies de tuberías disponibles no son críticos, en cambio, sobre las
otras dos restricciones, conviene mejorar la correspondientes a las bombas, que reditúan más que en el
caso de las horas de mano de obra.
El gradiente reducido es igual a la ganancia unitaria menos los valores unitarios de los recursos
consumidos. Por ejemplo:
Gradiente reducido del Aqua-Spa = 350 - 200 * 1 - 16.67 * 9 - 0 * 12 = 0
Gradiente reducido del Hydro-Lux= 300 - 200 * 1 - 16.67 * 6 - 0 * 16 = 0
En aquellos casos en los que la ganancia marginal es menor que el valor marginal de bienes
requeridos para su producción, no producen una solución óptima.

29
 Figura 23

Como demostración de lo anterior veamos que pasa si la empresa piensa en producir otro tipo de
baño caliente llamado Typhoon-Lagoon. La ganancia unitaria del mismo es de 320 $, requiere 1 bomba, 8
horas de mano de obra y 13 pies de tubería. Introduzcamos estos datos en la planilla.

Figura 24
30
 Ahora busquemos Solver en Herramientas y completémoslo como en el caso anterior. El cuadreo
de diálogo del Solver queda:

Figura 25

Figura 25

31
Se aprecia que la producción de los Typhoon-Lagoons no contribuyen en nada al mejoramiento del
problema.
Gradiente reducido del Typhoon-Lagoons= 320 - 200 * 1 - 16.67 * 8 - 0 * 13 = -13.33
Esto significa, que se debería incrementar en 13.33 $ la ganancia marginal de dicho producto
para que la solución varíe. En efecto, si se aumenta a 334 $, se obtiene el resultado de la figura 27. Vemos
que ahora sí ha cambiado la solución, pero por el contrario no convendría producir los Aqua-Spas por los
mismos motivos de antes.

32
 El

Figura 26
reporte de sensibilidad será, ahora:

Figura 27

33
 Los valores óptimos de los gradientes reducidos para cada caso son:

Tipo de problema Valor óptimo de la Valor óptimos del

variable de decisión gradiente reducido

límite inferior simple ≤ 0

Maximización entre los límites = 0
Límite superior simple ≥ 0

límite inferior simple ≥ 0

Minimización entre los límites = 0
Límite superior simple ≤ 0

Reportes de límites
Muestra una lista con la celda objetivo y las celdas ajustables con sus valores correspondientes,
los límites inferior y superior así como los valores del objetivo. No se genera este informe para los
modelos que tengan restricciones enteras. El límite inferior es el valor mínimo que puede tomar la celda
ajustable mientras se mantienen todas las demás celdas ajustables fijas y se continúa satisfaciendo las
restricciones. El límite superior es el valor máximo.

34
 Figura 28

Método Simplex.
En el caso de Blue Ridge Hot Tubs, el problema contenía dos variables de interés, sin embargo,
el Solver, emplea cinco variables. En la página 19 veíamos que las restricciones definían cinco puntos (de
los cuales el cuatro era el óptimo). Estos puntos no son otra cosa, sino, el adoptar los valores que igualan
a las resticciones.

35
 El método Simplex hace esto, transforma el sistema de inecuaciones en un sistema de igualdades
mediante el uso de variables auxiliares llamadas Slacks (débiles). Por ejemplo, la siguiente desigualdad se
transforma en igualdad por el empleo de una variable slack S.
ak1 * X1 + ak2 * X2 + .... + akn * Xn ≤ bk
ak1 * X1 + ak2 * X2 + .... + akn * Xn + Sk = bk
En el problema-ejemplo que venimos siguiendo, el sistema quedaría:
Max 350 * X1 + 300* X2 } Ganancia
1 * X1 + 1 * X2 + S1 } Restricción por bombas
9 * X1 + 6 * X2 + S2 } Restricción por horas de trabajo
12 * X1 + 16 * X2 + S3 } Restricción por tuberías
X1, X2, S1, S2, S3 ≥ 0 } Condiciones de no negatividad
Si el número de variables supera al de restricciones, se deben tomar cierto número de
ellas y ser consideradas como variables básicas, mientras que las restantes (variable no-básicas) se fijan
en el límite inferior. Con el sistema obtenido, se resuelven sus incógnitas las cuales dan una solución
básica factible que corresponde a uno de los vértices de intersección de las restricciones.
Al haber 3 restricciones y 5 variables, debemos tomar 3 variables básicas y 2 no-básicas, lo que
da diez formas distintas de posibles soluciones básicas factibles, que son:

Variables Variables
Solución Valor función objetivo
básicas mo-básica

X1=0 , X2=0
1 S1, S2, S3 X1, X2 0
S1,=200, S2=1566,S3=2880

X1=0 , X2=180
2 X2, S1, S2 X1, S3 54.000
S1=20, S2=486, S3=0

X1=80 , X2=120
3 X1, X2, S2 S2, S3 64.000
S1=0 ,S2=126, S3=0

X1=122, X2=78
4 X1, X2, S3 S1, S2 66.100
S1=0 , S2=0, S3=168

X1=74 , X2=0
5 X1, S1, S3 X2, S2 60.900
S1=26, S2=0 , S3=792

X1=108, X2=99
6* X1, X2, S1 S2, S3 67.500
S1=-7 , S2=0, S3=0

X1=240 , X2=0
7* X1 ,S1, S2 X2, S3 87.400
S1=-40 , S2=-594, S3=0

X1=200 , X2=0
8* X1, S2, S3 X2, S1 70.000
S1=0 , S2=-234, S3=480

X1=0 , X2=200
9* X2, S2, S3 X1, S1 60.000
S1=0 , S2=366, S3=-320

X1=0 , X2=261
10* X2, S1, S3 X1, S2 78.300
S1=-61 , S2=0, S3=-1296

Los puntos marcados por * son infactibles debido a que no cumplen la condición de no-
negatividad. Los puntos 1 a 5 son los que delimitan la zona factible, como se ilustra en la figura 30.

36
 Figura 29

El método Simplex identifica una de las soluciones básicas factibles y compara el valor de la
función objetivo con la correspondiente con los puntos adyacentes. Si ningún punto adyacente al de
estudio es mejor, dicho punto es el óptimo.

Programación lineal entera.

En ocasiones, la variable de interés, solo puede asumir valores enteros. Este problema no es tan
simple como parecería a simple vista, y constituye un problema de programación lineal entera, o ILP (por
su sigla en inglés).
En el ejemplo que seguimos de Blue Ridge Hot Tubs, las variables son enteras, ya que resulta
evidente que solo pueden venderse unidades discretas y no fracciones.

Relajación.
Un problema ILP, puede resolverse como LP, considerando que las variables no son enteras.
Esta es una relajación del problema ILP a LP. A priori, la zona factible para ambas formas de plantear el
problema son dramáticamente distintas. Mientras que el caso ILP, la zona factible está determinada por
una serie finita de puntos, en los problemas LP la cantidad de puntos que forman dicha zona factible es
infinita. Por otro lado todas las soluciones para ILP, lo son también para LP pero no así a la inversa.

Resolviendo el problema de relajamiento.

En el ejemplo de estudio, la solución factible fue que había que producir 122 Aqua-Spas y 78
Hydro-Lux, es decir que dieron valores enteros. No siempre así, como lo demostraremos con el mismo
ejemplo, pero modificado. Así, supongamoes que son 1520 las horas de mano de obra disponible (en
lugar de 1566) y 2650 los pies de tubería que se pueden emplear (en vez de 2880). Con ésta información,
acudiremos al Solver de Excel para hallar la solución óptima.

37
 Figura 30

La solución óptima no es entera, por lo que viola la condición correspondiente. Un punto

interesante a considerar es que la solución del problema ILP nunca puede ser mejor que el de LP.
Una tentación sería, la de redondear las cifras hasta un entero. Pero en éste caso, la solución sería 117 y
78 , lo que viola la restricción de las horas de mano de obra disponibles (1521).

38
 Figura 31

Pero con el redondeo, no hay garantía de que la solución encontrada sea la óptima. Así por
ejemplo, podríamos reducir los Aqua-Spa de 117 a 116, lo que daría:

La solución es factible ya que satisface todas las restricciones, pero ¿Es la óptima?. Para
Figura 32
39
averiguarlo vamos a hacer uso de la herramienta Solver de Excel.
Para ello debemos introducir una nueva condición, esto es que las variables de interés sean
enteras. El cuadro de diálogo de restricciones para variables entera queda:

Figura 33

Y el cuadro de diálogos del Solver queda:

Haciendo click en el botón Resolver del Solver, se obtiene la solución.

Figura 34

Figura 35 40
 Que es mejor que la obtenida por el simple redondeo de los resultados del LP que se ven en la
figura 33. Ahora veamos que nos ofrece Solver como opciones. Haciendo click en el boton Opciones del
cuadro de diálogo de Solver se obtiene:

Figura 36

Como vemos, el Solver, emplea una tolerancia del 5% por lo que una vez hallada una solución,
abandona la búsqueda de una solución mejor. Para ello modificaremos la tolerancia llevando del 5% al
0%. Y volveremos a resolver el problema. El resultado puede verse en la figura 39.

Figura 37

Que es la mejor solución para éste problema.

41
 Figura 38

Variables binarias.
Como vimos, los problemas de LP involucran a los ILP como caso especial. Así también,
existen casos especiales en los que las variables de interés no solo es entera sino que además son binarias.
Esto significa que las variables solo pueden asumir dos estados 0 o l. Para resolver casos semejantes es

necesario especificarlo en el cuadro de diálogo correspondiente a restricciones introduciendo la condición

de entero. Esto se ilustra en la figura 40.

Figura 39

42
Programación de objetivos
Hasta el momento hemos visto casos en los que la función a optimizar era única y las
restricciones eran estrictas. Ahora veremos que en programación de objetivos o GP (del inglés Goal
Programming) las restricciones son blandas, esto es que pueden ser violadas. Esta metodología es
iterativa, o sea que a diferencia de los casos estudiados, la solución obtenida podría no ser la mejor por lo
que habría que iterar. Como explicación del método, vaya un ejemplo.
Con el objeto de aumentar las ganancias durante el período fuera de temporada, Davis McKeown, propietario
de un resort hotel y centro de convenciones, decide consultar a una empresa de investigación de mercado. El resultado
del estudio fue que se debía construir 5 salones de convención pequeños (400 pies cuadrados), 10 medianos (750 pies
cuadrados) y 15 grandes (1050 pies cuadrados). El total de superficie a cubrir es de 25000 pies cuadrados. El costo por
cada salón pequeño es de 18000 $, por cada salón mediano, 33000 $ y por cada salón grande 45150 $. Davis desea
que su inversión total no supere 1.000.000 $.

Definición de la variables de decisión

Evidentemente son la cantidad de salones pequeños (X1) , medianos (X2) y grandes (X3).

Definición de los objetivos

Estos son (sin importar el orden):
1. La expansión debe incluir aproximadamente 5 salones de conferencia pequeños.
2. La expansión debe incluir aproximadamente 10 salones de conferencia medianos.
3. La expansión debe incluir aproximadamente 15 salones de conferencia grandes.
4. La expansión debe consistir de aproximadamente 25000 pies cuadrados.
5. La expansión debe costar aproximadamente 1.000.000 $.
El término "aproximadamente" es esencial, ya que una inversión de 1.001.000 $ evidentemente
supera en 1.000 $ al previsto, pero podría ser una solución sumamente deseable o aceptable.

Definición de las restricciones

Estas no son estrictas como lo habíamos definido, pero ¿cómo programarlo matemáticamente?.
Se sabe que el concepto de aproximación no es matemáticamente aceptable, por lo que se afecta a las
restricciones de una serie de variables llamadas derivacionales, pues indican en cuanto sé desvía el valor
real del deseado. En forma de ecuaciones algebraicas sería:
X1 + d1- - d1+ = 5 } salones pequeños
X2 + d2- - d2+ = 10 } salones medianos
X3 + d3- - d3+ = 15 } salones grandes
Donde di-, di+ ≥ 0

Los valores a la derecha son los valores de las restricciones, los di- son los valores en que fue
sub-valorada la restricción y los di+ los valores en que fue sobre-valorada. Estas variables son nulas si la
restricción se cumple exactamente. Por ejemplo si la solución es, X1=3, X2=13 y X3= 15, diremos que la
primera fue sub-valorada en 2 (d1-=2, d1+= 0) y que la segunda fue sobre-valorada en 3 (d2-=0, d2+=3) y
que la tercera fue exactamente valorada (d3-=d3+ = 0).
Las otras restricciones concernientes a los pies cuadrados de construcción y la inversión en $,
serían, usando la misma técnica:
400 X1 + 750 X2 + 1050 X3 + d4- - d4+ = 25.000 pies cuadrados
18000 X1 + 3300 X2 + 45150 X3 + d5- - d5+ = 1.000.000 $ de inversión
En general, un problema GP podría incluir no solo restricciones-objetivos sino también las
típicas restricciones estrictas, por ejemplo, si el monto a invertir no deba superar al millón de dólares.

Funciones objetivo GP
Es evidente que la solución ideal sea la que calcule exactamente todas las restricciones-objetivo.
Una forma de hallarla sería la minimización de la suma de las variables derivacionales, esto es:

43
 Objetivo: MIN: ∑ (d
i
-
i + d i+ )

El objetivo ideal sería aquel que anula dicho valor. Pero por otro lado, es inconsistentes sumar
objetos tan dispares como número de salones, de pies cuadrados y dólares de inversión, por lo que se
prefiere trabajar con porcentajes. Sería:
1
Objetivo: MIN: ∑t
i
(d i- + d i+ )
i

Además no debemos dejar pasar por alto que no todas las restricciones implican la misma
importancia, por lo que sería deseable que cada uno actúe por su propio "peso". Esto se consigue
asignándoles un valor relativo a cada una (o un peso), wi. Las funciones objetivos quedarían

Objetivo: MIN: ∑ (w
i
-
i • di- + w i+ • di+ )

O bien,
1
Objetivo: MIN: ∑ t (w
i i
-
i • d i- + w i+ • d i+ )

En nuestro caso la función objetivo sería indeseable sub-valorar los valores de las 3 primeras
restricciones (las referentes a los número de salones) pero indiferente si se sobre-valoran, por lo que las
di+ se anulan en los 3 primeros casos. Por otro lado se considera indeseable tanto la sub como la sobre-
valoración en el caso de los pies cuadrados de edificación. Para el caso de la inversión se considera
indeseable la sobre-valoración pero no así la sub-valoración, por lo que d5- = 0. La función objetivo
quedaría:

w1− - w -2 - w 3- - w -4 w 4+ w 5+
MIN: d1 + d2 + d3 + d -4 + d +4 + d 5+
5 10 15 25000 25000 1.000.000
El problema es ahora el valorar el valor relativo de los pesos para las distintas restricciones. Se
comienza con un valor (por ejemplo l) se resuelve, si es necesario se retocan y se vuelven a calcular.

Implementación del problema:

w1− - w -2 - w 3- - w -4 w +4 w 5+
MIN: d1 + d2 + d3 + d -4 + d +4 + d 5+
5 10 15 25000 25000 1.000.000

Sujeto a:
X1 + d1- - d1+ = 5
X2 + d2- - d2+ = 10
X3 + d3- - d3+ = 15
400 X1 + 750 X2 + 1050 X3 + d4- - d4+ = 25.000
18000 X1 + 33000 X2 + 45150 X3 + d5- - d5+ = 1.000.000
di-, di+ ≥ 0 para todo i
Xi ≥0 para todo i
Xi deben ser enteros
w1- = w2- = w3- = w4- = w4+ = w5+ = 1 el resto es igual a 0

Para implementarlo en el Solver de Excel debemos hacer una planilla como la de la figura 43.
Las fórmulas que debemos insertar son:

44
 Celda Fórmula Copiada a
B12 =B9 + B10 - B 11 C12:F12
B16 =B10/b$13 B16:F17
E9 =SUMAPRODUCTO (B9:D9,B5:D5) -----------
F9 =SUMAPRODUCTO (B9:D9,B6:D6) -----------
B23 =SUMAPRODUCTO (B16:F17,B20:F21) -----------

El cuadro de diálogo del Solver resulta:

Figura 40

Vemos que el objetivo es el de minimizar la función objetivo. El cuadro de opciones se debe completar de
tal modo que quede:

Figura 41

Y los resultados del problema,

45
 Figura 42

Donde vemos que el objetivo se cumple en cuanto al número de salones (5, 10 y 15

respectivamente) aunque excede el número de pies cuadrados en 250 y los costos en 97.250 $
Para evitar excedernos en el costo podemos aumentar el peso correspondiente en un orden de
magnitud haciendo a w5+= 10 (celda F21). Al resolver se obtiene el resultado de la figura 44. En ella
vemos que el costo aún es mayor, pero ahora en 6.950 $ y se necesitan 1.850 pies cuadrados menos.
Para ajustar el número de salones grandes (que se sub-valoraron en 2) podemos ajustar su peso
correspondiente en un orden de magnitud (de 1 a 10) por lo tanto, w3-= 10 (celda D20). Una vez
modificado y resuelto el problema se obtiene la solución de la figura 45. En esta solución debería
construirse 5 salones pequeños, 7 medianos y 15 grandes, con una ocupación de 23.000 pies cuadrados
(2.000 menos del esperado) y una inversión de 998.250 $ (1.750 $ menos del previsto). Esta es una
solución, pero ¿és la mejor?. Una nueva interación podrá decirlo, pero no sabiendo los valores "correctos"
de los pesos, éstos deben estimarse, por lo que consideraremos ésta solución como óptima.

46
Figura 43

Figura 44

47
Resumen de la programación de objetivos o GP
1. Identificar las variables de decisión del problema.
2. Identificar las restricciones estrictas en el problema y formularlas en la forma usual.
3. Situar los objetivos del problema a través de sus valores objetivos (los permitidos por el problema).
4. Crear las restricciones usando las variables de decisión que podría alcanzarse exactamente.
5. Transformar las restricciones arriba creadas para obtener restricciones-objetivo a través de las
variables derivacionales.
6. Determinar que variables derivacionales representan desviaciones indeseables a los objetivos.
7. Formular un objetivo para penalizar las desviaciones indeseables.
8. Identificar apropiadamente los pesos para el objetivo.
9. Resolver el problema.
10. Inspeccionar la solución del problema. Si la solución es inaceptable, retornar al paso 8 y revisar los
pesos que sean necesario.

Método MINIMAX
Este es un método muy útil para minimizar la máxima desviación de cualquier objetivo. Para
implementar el objetivo MINIMAX, debemos crear una restricción adicional para cada variable
derivacional como sigue, donde Q es la variable MINIMAX.
d1- ≤ Q
d1+ ≤ Q
d2- ≤ Q
..............
donde el objetivo es: MIN: Q
Puesto que Q debe ser mayor o igual que los valores de la variables derivacionales, al minimizar
a la misma, limitamos el valor máximo de dichas variables derivacionales. La técnica se explicará en el
siguiente tema.

Optimización de objetivos múltiples

Mientras que los problemas LP e ILP tienen una sola función objetivo existen otros que tienen
varios y son problemas de optimización con múltiples objetivos o MOLP (del inglés, multiple objective
linear programming).Y para explicarlo recurriremos a otro ejemplo, más adecuado, quizás, a la industria
química.
Lee Blackstone es propietario de la Blackstone Mining Company y opera dos diferentes minas de carbón, en
los condados de Wythe y Giles en el sudoeste de Virginia. Debido al incremento de la actividad comercial y residencial
del lugar, Lee anticipa un incremento en la demanda de carbón para los años siguientes. Su proyección de la demanda
es de 48 toneladas más de carbón de alta calidad (HD), 28 toneladas más de calidad media (MG) y 100 toneladas más
de carbón de baja calidad (LG). Para ello debe incrementar el personal, cosa que le cuesta 40.000 $ por envío de
trabajadores extra a la mina de Whyte mientras que el costo para la mina de Giles es de 32.000 $. Solo puede hacer un
envío por mes a cada mina. La producción de cada mina, para cada calidad de carbón es:

Tipo de carbon Mina Whyte Mina Giles

Alta calidad 12 tons. 4 tons.

Calidad media 4 tons. 4 tons

Baja calidad 10 tons. 20 tons.

Desafortunadamente, los métodos de extracción de carbón generan agua contaminada de tóxicos que se
vierten a las napas locales. La mina Whyte genera 800 galones de agua contaminada por mes mientras que la Giles
vierte 1.250 galones por mes. Por otro lado los riesgos de accidentes de trabajo con consecuencias fatales son de 0.20
y 0.45 respectivamente para cada mina por mes.

48
 El deseo de Lee es hacer frente a esa demanda minimizando los costos pero además desea disminuir la
emisión de agua contaminada y los riesgos de vida de sus trabajadores y desea saber cuantos meses deben trabajar
cada mina por año para enfrentar dicho aumento de demanda.

Definición de las variables de decisión

Estas son;
X1= número de meses extras para la mina Whytes.
X2= número de meses extras para la mina Giles.

Definición de objetivos
Este problema de LP, a diferencia de los anteriores, tiene 3 objetivos:
Minimizar: $40 X1 + $32 X2 }costo de producción en miles de dólares
Minimizar: 800 X1 + 1250 X2 } agua contaminada producida en galones
Minimizar: 0.20 X1 + 0.45 X2 } accidentes con riesgo de vida
En un modelo LP convencional se nos fuerza a elegir uno de los objetivos como más importante,
pero en el método MOLP todos los objetivos serán considerados.

Definición de las restricciones

Se formulan en la misma manera que los anteriores, esto es:
12 X1 + 4 X2 ≥ 48 } carbón de alta calidad requerido (HG)
4 X 1 + 4 X2 ≥ 28 } carbón de calidad media requerida (MG)
10 X1 + 20 X2 ≥ 100 } carbón de baja calidad requerido (LG)

Implementación del modelo

Minimizar: $40 X1 + $32 X2 }costo de producción en miles de dólares
Minimizar: 800 X1 + 1250 X2 } agua contaminada producida en galones
Minimizar: 0.20 X1 + 0.45 X2 } accidentes con riesgo de vida

Sujetos a: 12 X1 + 4 X2 ≥ 48 } carbón de alta calidad requerido (HG)

4 X 1 + 4 X2 ≥ 28 } carbón de calidad media requerida (MG)
10 X1 + 20 X2 ≥ 100 } carbón de baja calidad requerido (LG)

Todos los datos del modelo se implementarán en una hoja de cálculo en la forma usual.
Las fórmulas a agregar son:

D8 = SUMAPRODUCTO(B8:C8,$B$5:$C$5) copiada D9:D10 y D13:D15

Determinación de los valores de los objetivos

Los problemas LP solo tienen una función objetivo. ¿Cómo implementar varios objetivos?
Podríamos asumir los valores aproximados de cada objetivo como blanco a encontrar como t1, t2 y t3.
Objetivo 1: el costo total de producción deberá ser aproximadamente igual a t1
Objetivo 2: los galones totales de agua contaminada producida deberán ser aproximadamente igual a t2
Objetivo 3: el número de accidentes con riesgo de vida deberá ser de aproximadamente t3

49
 Por desgracia, no disponemos de éstos valores, pero podemos calcular los mejores para cada
objetivo. Así, comenzamos a minimizar el primer objetivo, esto es, minimizar el costo de producción.
Para ello introducimos los datos en la pantalla del Solver como se aprecia en las figuras siguientes.

Figura 45

Figura 46

Al resolverlo se obtiene la solución de la figura 48, esto es 2.50 meses para la mina White y 4.50
meses para la mina Giles. En éste caso, el costo total será de 244.000 $, por lo que t1 podría ser igual a
244, sabiendo que en ningún caso será menor. Para hallar t2 debemos minimizar el segundo objetivo
(galones de agua contaminada) que se encuentra en la celda D9. Al resolver el problema se obtiene la
nueva solución (figura 49) en la que los meses de cada mina son, 4.00 y 3.00 respectivamente, con una
emisión total de 6.950,0 galones de agua. En consecuencia 6.950 será el valor de t2. Por último, se
minimiza el tercer objetivo (número de accidentes con riesgo de vida) de la celda D10. Se obtienen los
resultados de la figura 50. Aquí, el número de accidentes por mes es de 2.00 lo que determina a t3. Los
meses de operación son 10.00 y 0.00 para cada mina, pero con notable aumento del costo y de emisión de
agua contaminada.
Estos puntos son vértices de la zona factible como queda definida en la figura 51. En los casos ya
estudiados, efectivamente la solución óptima ocurría en uno de dichos vértices. Para hallar la solución
óptima en un punto que no sea vértice se debe recurrir a otra técnica.

50
Figura 47

Figura 48

51
Figura 49

Figura 50

52
Determinación de los objetivos GP
Rescatemos los objetivos deseados con los valores calculados anteriormente,

Objetivo 1: el costo total de producción deberá ser aproximadamente igual a $244

Objetivo 2: los galones totales de agua contaminada producida deberá ser aproximadamente igual a 6.950
Objetivo 3: el número de accidentes con riesgo de vida deberá ser de aproximadamente 2.0
La derivación porcentual de las variables las definimos como:
Valor actual - Valor blanco
Valor blanco
Para los distintos objetivos, son:

(40 X 1 + 32 X 2 ) − 244 (800 X 1 + 1250 X 2 ) − 6950 (0.20 X 1 + 0.45 X 2 ) − 2.00

244 6950 2.00

Si afectamos a cada término con un peso w y sumamos obtenemos una función lineal:

(40 X 1 + 32 X 2 ) − 244 (800 X 1 + 1250 X 2 ) − 6950 (0.20 X 1 + 0.45 X 2 ) − 2.00

w1 + w2 + w3
244 6950 2.00

Función que se desea minimizar. Pero ahora sabemos que la solución podría no estar en uno de
los vértices por lo que debemos emplear otro método como el MINIMAX. Para ello hacemos uso de la
variable MINIMAX Q de tal modo que:
MIN: Q
(40 X 1 + 32 X 2 ) − 244
w1 ≤ Q
244
(800 X 1 + 1250 X 2 ) − 6950
w2 ≤ Q
6950
(0.20 X 1 + 0.45 X 2 ) − 2.00
w3 ≤ Q
2.00

Implementación del modelo revisado

12 X1 + 4 X2 ≥ 48 } carbón de alta calidad requerido (HG)
4 X1 + 4 X2 ≥ 28 } carbón de calidad media requerida (MG)
10 X1 + 20 X2 ≥ 100 } carbón de baja calidad requerido (LG)
w1( 40 X1 + 32 X2 - 244)/240 ≤Q } 1º restricción-objetivo MINIMAX
w2(800 X1 + 1250 X2 - 6590)/6950 ≤ Q } 2º restricción-objetivo MINIMAX
w3(0.20 X1 + 0.45 X2 - 2)/2 ≤Q } 3º restricción-objetivo MINIMAX
X1, X2 ≥ 0
w1, w2 y w3 son constantes positivas.

53
 Con la misma hoja de cálculo anterior, es fácil modificarla para que acepte el nuevo modelo. Se
agregarán los puntos de la figura 52 con las siguiente fórmulas:

Celda Fórmula Copiada a

D8 =SUMAPRODUCTO(B8:C8,$B$5:$C$5) D9:D10 y D13:D15
F8 =(D8 - E8)/E8 F9:F10
H8 = F8 * G8 H9:H10

Figura 51

Figura 52

54
 El cuadro de opciones es el mismo de la figura 47. Una vez resuelto a través de la herramienta
Solver del Excel, se obtiene la solución de la figura 54. Vemos que la solución obtenida (X1= 4.23; X2=
2.88) no corresponde a ninguno de los vértices de la zona factible. Las desviaciones de los objetivos son
de 7% para el primero y el tercero y menos de 1% para el segundo, lo que hace que ésta solución sea más
atractiva que las que ocurrían en los vértices. Además dicha solución estará tanto más cerca de algún
vértice cuanto mayor peso relativo tenga el objetivo correspondiente a dicho objetivo. Notar además, que
la variable Q es objetivo y a la vez celda cambiante.

Figura 53

Resumen de la optimización de multliples objetivos

1. Identificar las variables de decisión del problema
2. Identificar los objetivos en el problema y formularlos en la forma usual.
3. Identificar las restricciones del problema y formularlos en el modo usual.
4. Resolver el problema para cada objetivo identificado en el paso 2 para determinar el valor óptimo de
cada uno de ellos.
5. Establecer los objetivos como metas usando los valores identificados en el paso 4 como valor Blanco.
6. Para cada objetivo, crear una función derivacional que mida el valor en que cada solución dada falla
en alcanzar la meta (ej. en porcentajes).
7. Para cada una de las funciones derivacionales identificadas en el paso 6, asignarle un peso a dichas
funciones y crear una restricción que requiera el valor de la función derivacional pesada que deberá
ser menor que la variable MINIMAX, Q.
8. Resolver el problema de tal manera que minimice a Q.
9. Inspeccionar la solución del problema. Si la solución es inaceptable, ajustar los pesos en el paso 7 y
volver al paso 8.

55
Programación no lineal
Hasta en momento, hemos visto problemas en los que la función objetivo y las restricciones son
lineales, pero hay casos que no responden a ésta categoría y se llaman problemas de programación no
lineal o NLP (del inglés nonlinear programming).
La principal diferencia entre los problemas NLP y LP es que en los primeros, la función objetivo
y/o una o todas las restricciones son no lineales. Así pueden darse los siguientes casos:
En la figura 55 (a), la función objetivo es lineal, pero el borde de la zona factible, no. Significa
que por lo menos una de las restricciones es no lineal.
En la figura 55 (b), el borde de la zona factible (por lo tanto las restricciones) es lineal, pero las
curvas de nivel de la función objetivo no lo son. La que está graficada representa la solución óptima.
En la figura 55 (c), tanto la función objetivo como una de las restricciones son curvas, solo la
solución óptima fue dibujada.
Por último, la figura 55 (d) presenta el caso en que la zona factible está limitada por líneas rectas
y las curvas de nivel se concentran sobre la solución óptima "dentro" de la zona factible a diferencia del
segundo caso en donde el óptimo estaba en el mismo borde.

Figura 54

Aquí puede verse bien la diferencia entre los problemas LP en donde la solución factible estaba
siempre en un vértice mientras que en los casos NLP pueden estar sobre un borde curvo, recto o dentro de
la zona factible.
El método Simplex, como vimos, explora los vértices, por lo que el mismo no sirve para éste tipo
de problemas y aunque la resolución con Solver es similar, el método matemático varía como lo veremos
a continuación de un modo intuitivo.

56
Estrategia de resolución de problemas NLP
El procedimiento de resolución del Solver para problemas NLP es el de los gradientes reducidos
generalizados o GRG (del inglés generalized reduced gradient). La matemática involucrada es compleja,
pero intuitivamente podemos apreciarlo en la figura 56.
Se parte del punto A y siguiendo la dirección de mayor velocidad de crecimiento de la función
objetivo (gradiente), se busca el punto más extremo que resulta ser el B. Luego va explorando a través del
borde de la zona factible hasta encontrar el punto de solución factible, tan cerca del mismo como se
desee. Sin embargo, se aprecia que no es el camino más directo entre el punto de inicio y la solución
óptima. Esto significa, que no siempre es conveniente elegir la dirección en la que la función varía más
rápido. El algoritmo GRG del Solver no solo determina la dirección sino la longitud del paso a realizar. El
algoritmo GRG usual, no puede moverse directamente desde el punto de arranque hasta la solución
óptima, por lo que se requieren métodos más refinados.

Figura 55
Soluciones Globales versus soluciones locales
Los algoritmos para solucionar problemas NLP terminan cuando no hay más zona factible en la
dirección en que la función objetivo varía en el orden deseado (ya sea que aumente o disminuya) o
cuando está lo suficientemente cerca en valores arbitrarios. El tal caso, dicho punto se considera el
óptimo. El inconveniente es que dicho punto podría no ser el mejor como se visualiza en la figura 57.

Figura 56

57
 Todo método NLP requiere un punto de arranque y como se aprecia, la solución depende de
dicho punto. En la figura 56 era obvio que la solución encontrada era la mejor, pero, en la figura 57, si
partimos del punto A llegamos al C que es lo que se llama solución óptima local, en contraposición con la
solución óptima global que se alcanza partiendo desde D.
En el caso de ILP, encontramos un caso de óptimo que logró mejorarse al disminuirse la
tolerancia en el método matemático. Lamentablemente, en los casos NLP, no es fácil saber si cierta
solución óptima es global o local. Debido a lo anterior, es una buena idea, el resolver el mismo problema
partiendo desde diferentes puntos de arranque para ver si hay óptimos locales y determinar el mayor
como óptimo global. De todos modos, la herramienta Solver del Excel tiene algunos problemas cuando se
parte del origen, por lo que conviene que los valores de arranque sean no-nulos.

Una nota sobre las soluciones óptimas del Solver.

Cuando un problema NLP es resuelto, puede aparecer uno de los siguientes mensajes:
1. "Solver found a solution. All constraints and optimality conditions are satisfied."
Esto significa que el Solver ha encontrado una solución óptima local, pero no garantiza que sea la
solución óptima local. A menos que se sepa que es la única solución, se deberá correr el Solver con
otros valores de arranque.
2. "Solver has converged to the current solution. All constraints are satisfied."
Significa que el valor de la función objetivo cambia muy poco en las últimas iteraciones. En Excel
8.0, se dispone de la opción convergencia en el cuadro de diálogos de opciones (ver Fig. 47 pag 43)
que evita la convergencia hacia una solución subóptima.
3. "Solver cannot improve the current solution. All constraints are satisfied."
Este raro mensaje significa que el modelo es degenerado y el Solver esta en un circulo vicioso. Esto
puede frecuentemente eliminarse, removiendo las restricciones redundantes en el modelo.

Modelos de cantidad económica de orden

O EOQ (del inglés economic order quantity), es un problema muy común en negocios y que puede
servir como ejemplo de optimización no-lineal. Cuando se desea comprar algún artículo se desea saber
cual es el valor óptimo a ordenar. El modelo básico responde a:
1- La demanda del producto es constante a través del año
2- Cada nueva orden es enviada completa cuando el inventario llega a 0.
En la figura 58 se aprecia un caso en el que el consumo anual es de 150 y se efectúan 3 órdenes de
50 artículos.

Figura 57

58
 En la figura 60 se advierte otra forma de lograr 150 artículos por año pero en éste caso con 6
órdenes de 25 artículos. En ambos casos se aprecia que cuando el inventario es nulo se ingresa una nueva
orden, por lo que el inventario aumenta súbitamente desde cero hasta dicho número.
Así en el primer caso se requieren menos órdenes pero de mayor tamaño mientras que en el
segundo las órdenes son más pequeñas, pero mas frecuentes. Así en un caso es mayor el costo de
almacenamiento mientras que en el otro es mayor el costo de transporte. En general, éste tipo de
situaciones dan lugar a problemas con objetivos encontrados como se aprecia en la figura 59. Vemos que
para el costo total hay un mínimo que es el EOQ que se busca.
En el modelo básico EOQ el costo total puede referirse a:
D Q
Costo total anual = D ∗ C + ∗S + ∗C∗i
C 2
Donde:
D= demanda anual del artículo
C= valor de compra unitario del artículo
S= costo fijo de cada orden
i= costo de almacenamiento de inventario por unidad (como porcentaje de C)
Q= cantidad ordenada por vez

Figura 58

El primer término de la fórmula (D*C) representa el valor de compra anual del producto. El
segundo término (S*D/Q) representa el costo anual de las órdenes (D/Q= número de órdenes). El tercer
término C*i*Q/2) representa el costo anual de almacenamiento.
Para aclarar este tipo de problemas, sea el siguiente ejemplo.
Alan Wang es responsable de la compra de papel para todas las copiadoras e impresoras láser del la
corporación MetroBank en su casa central. Alan proyecta que en el año entrante deberá comprar 24000 cajas de papel
el cual será utilizado a ritmo constante a través de todo el año. Cada caja de papel cuesta 35$. Alan estima en 50$
cada orden emitida (incluye transporte). MetroBank asigna un costo de 18% en los concerniente al almacenamiento e
inventario. La empresa piensa que serán necesarias 4 compras. Se desea saber cual es la cantidad más económica a
ordenar (o EOQ) en la compra de papel.

59
Implementando el modelo
Los datos del problema se llevan a una hoja de cálculo como la de la figura 61. Las fórmulas
incluidas son:

Celda Fórmula Copiar a

D11 = D5*D4

D12 =D4/D9*D6

D13
=D9/2*D5*D7

D14 =SUMA(D11:D13)

La figura 62 representan las opciones del Solver a ser ingresadas para el presente problema.
Notar que la opción de asumir modelo linear no debe ser seleccionado, en caso contrario, el Solver lo
resuelve como LP empleando para ello el método Simplex, con lo que el problema sería incorrectamente
resuelto. Los resultados de la operación se aprecian en la figura 63. El número de arranque (6000)
corresponde al debido a 4 compras anuales. El resultado dio aproximadamente 617 cajas en 39 órdenes
(24000/617=38.89), o 1.333 órdenes semanales (52/39). Como práctica conviene una orden semanal de
461 cajas. Esto incrementa los costos en solo 167$ llevándolo a 844.055 $, pero le significa al banco un
ahorro de 15.000 $ por año.

Figura 59

60
 Figura 60

Por medio del cálculo se llega a la misma conclusión, esto es, que el óptimo es:

2∗D∗S
Q* =
C∗i

2 * 24000 * 50 2400000
Q* = = = 617.214
35 * 0.18 6.3

61
 Figura 61

Si partimos con otro valor de arranque (menor que el esperado, por ejemplo 1), la solución, al
emplear el Solver, es la misma, por lo que supondremos que es el óptimo global.
Los problemas de localización. Son no lineales debido a que la distancia entre 2 puntos es la raíz
cuadrada de la suma de los cuadrados de las diferencias de las coordenadas homólogas por lo que deben
ser resueltos por algoritmos NLP.

Opciones del Solver.

En el cuadro de diálogos de opciones del Solver podemos apreciar otras opciones dignas de
mención. En la figura 63 se aprecia en detalle.

62
 Figura 62

En estimación pude hacerse por técnicas de extrapolación lineal o cuadrática (por defecto es
lineal). En derivadas, la estimación pude hacerse con el siguiente punto (progresivas) o con el siguiente y
el anterior (centrales), por defecto se opta por progresivas. En hallar, puede hacerse por el método de
Newton o por gradiente conjugado, siendo el primero la opción por defecto.

63
Tercera parte: Condiciones de optimalidad
Hasta el momento, hemos pasado por alto las consideraciones de orden matemático de los
métodos anteriores. Para estudiar las condiciones de factibilidad y optimalidad estudiaremos con más
detalle cómo opera el Simplex y cuales son las condiciones en problemas no lineales.

Método Simplex
Veremos con otro ejemplo, como el método Simplex discrimina los puntos factibles y como
determina si un determinado valor es el óptimo. Sea,
Maximizar: x0 = 2 X1 + 4 X2
Sujeto a:
- X1 + X2 ≤ 3 (a)
X1 + X2 ≤ 5 (b)
X1, X2 ≥ 0 (c), (d)
Como hemos hecho antes, graficaremos la región factible, determinada por ambas restricciones.
El resultado es la figura 64. Están incluidas las curvas de nivel de la función objetivo de la cuales, una es
la solución óptima.

Figura 63

Con objeto de transformar las desigualdades en igualdades, haremos uso de las variables débiles
(slacks) o auxiliares, como vimos anteriormente. El sistema a resolver queda.
Maximizar: X0= 2 X1 + 4 X2 + 0 X3 + 0 X4 Sujeto a:
- X1 + X2 + X3 = 3
X1 + X2 + X4 = 5
X1, X2, X3, X4 ≥ 0
El sistema posee 4 variables y 2 ecuaciones (las restricciones) por lo que 2 de sus variables serán
básicas y 2 no básicas. A continuación veremos los fundamentos matemáticos de que hace uso el método
para evaluar las condiciones de factibilidad y eventualmente de optimacidad de los distintos puntos.
Los puntos que corresponden a los vértices (en uno de los cuales se encuentra la solución
óptima) tienen por lo menos 2 de sus variables con valor 0, éstos son:

64
 Xa = (0;0;3;5)
Xb = (0;3,0,2)
Xc = (1;4;0;0)
Xd = (5;0;8;0)

El sistema quedará definido por los siguientes arreglos:

Maximizar: X0 = Ct X
Sujeto a:
AX = b
X ≥ 0
Siendo A la matriz de coeficientes, b el vector de términos independientes, C el vector de
coeficientes de la función objetivo. La matriz A se conformará por otras dos, una B, correspondiente a las
variables básicas y otra matriz N de variables no básica, en nuestro caso:

− 1 1 1 0
A=  b = [3 5] C = [2 4 0 0]
 1 1 0 1
A=(B,N)
Las variables de la matriz B, serán XB, y las de la matriz N, serán XN, donde B es no singular. El
sistema LP queda como (B,N).(XB,XN)t = b , (XB,XN) ≥ 0 o bien [Link] + [Link] = b , XN ≥ 0, XB ≥ 0. Y
siendo B una matriz no singular, existe B-1, luego, XB = B-1 .b - B-1 .[Link]
Para hallar las diferentes soluciones factibles hay que igualar a cero n-m variables, donde n es el
numero de variables y m el número de restricciones. Como XN= 0, las variables básicas pueden
calcularse:
XB = B-1 . b
Si XB ≥ 0, será una solución básica factible del LP y si XB > 0 dicha solución se denomina no
degenerada. El método Simplex se basa en dos condiciones fundamentales:
Condición de factibilidad: esta condición asegura que partiendo de una solución básica factible
inicial sólo se analicen nuevas soluciones básicas factibles.
Condición de optimicidad: esta condición asegura que sólo se evaluarán soluciones básicas
factibles, no inferiores. Esto es, soluciones básicas factibles que asignan a la función objetivo un valor no
inferior al asignado por la solución actual.
Convergencia del método: Si la región factible de un LP es no vacía y acotada tiene un número
finito de puntos extremos (vértices), luego, dado que el método solo evalúa vértices no inferiores,
necesariamente (en ausencia de degeneración) el método alcanzará un óptimo en un número finito de
iteraciones.
El algoritmo Simplex

Etapa inicial:
Se puede definir a la región factible del LP como el conjunto de puntos S= {x/A.x=b, x ≥ 0}.
Luego, el vector no básico asociado a dicha solución será XN=0 y el vector básico asociado será,
XB = B-1 . b - [Link] = B-1 . b >0.

Etapa principal:
Dada una solución básica factible X∈ S, si dicha solución es no óptima, el método genera una nueva
solución básica factible eligiendo una variable no básica XNj (con valor actual cero) y la convierte en
básica (incrementando su valor), en reemplazo de una variable básica XBi (con valor actual mayor que
cero) la que pasa a no básica (tomando valor cero).

65
 La variable XNj que pasa a XBi se denomina variable ingresante a la base.
La variable XBi que pasa a XNj se denomina variable saliente de la base.
Condición de optimicidad
El valor actual de la función objetivo vendrá dado por
X0 = [Link] + [Link] = CB.(B-1 .b - B-1 .[Link]) + [Link] = CB.B-1.b -(CB.B-1.N - CN).XN o bien

X 0 = C B .B −1.b − ∑ (C
j∈J
B .B
−1
.a j − c j ).X j

Siendo J el conjunto de subíndices de las variables no básicas y aj la columna asociada a la variable

Xj. Un análisis del valor ([Link] - cj) permite deducir (para problemas de maximización):
♦ Si ([Link] - cj) ≥ 0 œ j ∈ J cualquier Xj no básica que ingrese a la base no mejorará el valor de
la función objetivo, luego el punto actual es óptimo (condición de parada del algoritmo).
♦ Si ([Link] - cj) < 0 para algún valor j ∈ J, XJ será candidata a ingresar a la base puesto que al
aumentar el valor de Xj puede mejorar el valor de la función objetivo. De todas las Xj/ j ∈ J con
valor ([Link] - cj) <0 se elige como variable ingresante aquella cuyo valor ([Link] - cj) sea
menor.
En nuestro ejemplo, elegimos como solución básica factible inicial al vértice Xa, por o que:
XB=(X3,X4) y XN=(X1,X2)
 1 0 − 1 1 1 0
B=  N=   B −1 =   CB=(0;0) CN=(2;4) b(3;5)
0 1  1 1 0 1
XN=(X1, X2) = (0,0) XB = B-1 . b
 1 0
XB =   × (3 5 ) = (3 5 ) XB=(3,5)
0 1
Se evalúa la función objetivo X0 = CB. XB + [Link]
X 0 = (0 0) × (3 5 ) + (2 4 ) × (0 0 ) = 0
Ahora vamos a determinar cual será la variable ingresante, para ello vamos a evaluar ([Link] - cj)
1 0
(0 0) ×   × (− 1 1) − 2 = −2
j=1 0 1

 1 0
j=2 (0 0) ×   × (1 1) − 2 = −4
0 1
El punto en estudio no verifica la condición de óptimo. Se elige como variable ingresante la que
potencialmente incrementa más la función objetivo, esto es j=2, por lo tanto ingresa X2.

Condición de factibilidad
Selecciona la variable saliente en base a satisfacer,
(1) La condición de no negatividad, X ≥ 0.
(2) La condición de solución básica, esto es que la variable saliente debe tomar valor cero.

66
 Luego, siendo Xj / j ∈ J la variable ingresante (su valor aumentará desde el actual cero). Con lo
cual el nuevo valor del vector de variables básicas vendrá dado por XB= B-1 .b - B-1 .[Link] .Las
restantes variables no básicas se mantendrán con valor cero.
Sea XBi el i-ésimo elemento del vector de variables básicas XB(m). Luego, la condición (1)
establece que XBi =(B-1 .b)-(B-1 .aj), Xj ≥ 0 œ i= 1....m.
Por otra parte, la condición (2) exige que la variable saliente XBr debe tomar valor cero.
Estas condiciones se satisfacen eligiendo el valor de Xj (variable ingresante) como:
Xj= Min. {(B-1 .b)i/(B-1 .aj)i œ (B-1 .aj)i >0 } = (B-1 .b)r/(B-1 .aj)r
Luego, la variable no básica Xj ingresa a la base con valor = (B-1 .b)r/(B-1 .aj)r y la variable básica
XBr sale de la base y toma valor cero (pasa a no básica).
Se habrá generado así una nueva solución básica factible no inferior a la anterior. El
procedimiento vuelve a la condición de optimicidad.
Siguiendo el ejemplo anterior, determinaremos la variable saliente, esto es,
Xj= Min. {(B-1 .b)i/(B-1 .aj)i œ (B-1 .aj)i >0 } entre X3 y X4.

(1 0) × 
3  1
i=3  / (1 0 ) ×   = 3
5 0

(0 1) × 
3 0
i=4  / (0 1) ×   = 5
5
   1
Como X3 dio el mínimo valor, dicha variable será la saliente.
Ahora, nos queda:
XB =(X2, X4) XN=(X1, X3)
CB=(4;0) CN=(2;0) XN=(0,0)
1 0 − 1 1  1 0
B=  N=  B −1 =  
1 1  1 0 − 1 1

 1 0  3
XB =   ×   = (3 2) XB =(3,2)
− 1 11  4 
Se evalúa nuevamente la función objetivo: X0 = CB. XB + [Link]

3 0
(4 0 ) ÷   + (2 0 ) ×   = 12
 2 0
Lo que mejora la solución. Ahora evaluaremos la nueva variable ingresante entre X1 y X3.
 1 0  − 1
J=1 (4 0) ×   ×   − 2 = −6
− 1 1  1 

 1 0  1 
J=3 (4 0) ×   ×   − 0 = 4
− 1 1  0 

La variable X1 ocasiona una mejora, mientras que la X3 la empeora. Por lo tanto la variable
ingresante será X1. A continuación se evalúa cual es la variable saliente entre X2 y X4

67
 3  1
i=2 (1 0 ) ×   / (1 0 ) ×   = 3
5  1

(− 1 1) × 
3 0
 / (− 1 1) ×   = 2
i=4 5
   1

Por lo tanto sale X4. Ahora el problema queda:

XB=(X1, X2) XN=(X3, X4)
CB=(2;4) CN=(0;0) XN=(0,0)

− 1 1 1 0 − 1 1 
B=  N=  B −1 =  2 2
 1 1 0 1  1 1 
 2 2

− 1 1  3
XB =  2 2  ×   = (1 4 ) entonces XB=(1,4)
 1 1   5 
 2 2

La función objetivo X0 = CB. XB + [Link] dará:

 1
X 0 = (2 4 ) ×   = 18 Como el término CN es nulo, se puede omitir.
 4
La solución es mejor que antes, ahora veremos si es la óptima. Para ello evaluaremos las variables
candidatas a ingresar, las que son X3 y X4.

− 1 1   1
j=3 (2 4) ×  2 2 ×   − 0 = 1
1   0 
 1
 2 2

− 1 1  0
(2 4) ×  2 2 ×   − 0 = 3
1   1 
j=4  1
 2 2

Por lo tanto es el óptimo. Efectivamente, hemos visto por el método gráfico que el punto
Xc=(1,4,0,0) es el óptimo y el valor de la función objetivo es efectivamente 18.

Teoría Clásica de la programación No Lineal

A efectos de presentar los resultados teóricos, los NLP son clasificados en NLP No
Condicionados (sin restricciones), NLP condicionados por igualdades y NLP condicionados por
desigualdades. Los postulados teóricos son presentados a través del enunciado de teoremas sin
demostración.

68
Programas Matemáticos no Condicionados
Teorema 1: Condición necesaria de Óptimo Local No Condicionado
Sea f:Rn→R1 continua y diferenciable en todo x∈Rn. Luego si X* es un punto (finito) donde la
función alcanza un óptimo local, se verifica ∇f(X*)=0. En particular, se dice que X* es un óptimo local no
condicionado.

Teorema 2: Condición suficiente de Óptimo Local No Condicionado

Sea f:Rn→R1 continua y diferenciable dos veces en todo x∈Rn. Si todas las primeras derivadas
de f(x) se anulan en X*, y si la matriz Hessiana evaluada en X* es negativa (positiva) definida, luego X*
es un máximo (mínimo) local de f.
Extensión: Si X* es un máximo (mínimo) local no condicionado de f(x), luego la matriz Hessiana en X*
es negativa (positiva) definida o semidefinida.

Teorema 3: Condición Suficiente de Óptimo Global No Condicionado

Sea f:Rn→R1 continua y diferenciable dos veces y convexa œ x∈Rn. Luego todo mínimo
(máximo) local de f(x) es global.

Programas Matemáticos Condicionados por Igualdades

Este tipo de NLP es representado a través de la siguiente estructura general:
Opt f8x) sa: { x∈Rn, gi(x)=bi, œ i=1,...,m} siendo f:Rn →R1 y gi:Rn →R1 œ i=1,...,m donde m <n.
Sea X*∈Rn un óptimo local de este NLP, se define a la matriz (n*m) Jacobiana J(X*) como

 ϑg1 ( X*) ϑg1 ( X*) 

 ϑX .......
 1 ϑX m 
J( X*) =  ....... ....... ....... 
 ϑg m ( X*) ....... ϑg m ( X*) 
 ϑX ϑX m 
 1 

Teorema 4: Condición necesaria de óptimo local restringido por igualdades

Sea X* ∈Rn un óptimo local de f(x) sujeto a las restricciones de igualdad gi(X*)=bi, œ i=1,...,m
donde m <n. Si es posible elegir m variables tal que la matriz Jacobiana J(X*) sea no singular, › un único
conjunto de escalares 81*,...,8m* satisfaciendo: ∇f(X*)- Σœi 8i* ∇gi(X*)= 0

La función Lagrangiana: Este sistema de ecuaciones puede obtenerse como condición necesaria de
óptimo local del NLP no condicionado:
Opt L(x, 8) = f(X*) - Σœi 8i* (gi(X*)-bi)
Sea (X*, 8*) óptimo local de L(x, 8). Luego debe verificar la condición necesaria de óptimo
local no condicionado (Teorema 1) ∇ L(X*, 8*) =0. Esto es:
∇x L(X*, 8*)= ∇f(X*)- Σœi 8i* ∇gi(X*) = 0
∂ L(X*, 8*)/∂8i = (gi(X*)-bi)=0 œ i=1,...,m

69
 Donde ∇x L(X*, 8*) es un vector que contiene las derivadas parciales de L(x, 8) respecto a Xj
œ j=1,...,n.
Luego se puede decir que este problema irrestricto es equivalente al problema anterior en cuanto
a que toda solución óptima de ambos problemas satisface el mismo conjunto de ecuaciones. L(x, 8) se
denomina función Lagrangiana y los 8i œ i=1,...,m se denominan multiplicadores de Lagrange.

Teorema 5: Condición suficiente de óptimo local restringido por igualdades

Sea f(x) :Rn→R1 y gi (x):Rn→R1 œ i=1,...,m continua y diferenciable dos veces en todo
x∈Nδ(X*) (entorno del punto X* de radio δ). Sean X* ∈Rm/ ∇ L(X*, 8*) =0 Si existe z ∈En no nulo
cumpliendo zT ∇gi(X*)=0 œ i=1,...,m, el cual satisface zT Hx L(X*, 8*) z >0 →X* es un mínimo local
estricto del problema: opt f(x) sa: { x∈Rn, gi(x)=bi, œ i=1,...,m}. Si zT Hx L(X*, 8*) z < 0 → X* es un
máximo local estricto del problema: opt f(x) sa: { x∈Rn, gi(x)=bi, œ i=1,...,m}

Problemas Matemáticos Condicionados por Desigualdades

Este tipo de problemas NLP puede ser representado a través de la siguiente estructura general:
Max f(x)
Sa: { x∈Rn, gi(x)≤bi, œ i=1,...,m} siendo f(x) :Rn→R1 y gi (x):Rn→R1 œ i=1,...,m. Todo
NLP puede ser llevado a esta estructura, por lo tanto los teoremas siguientes son de aplicación general.

Teorema 6: Condición necesaria de Óptimo Local de Kuhn Tucker

Sea X* un máximo local restringido de f(x) sobre la región factible definida por gi(x) ≤bi, œ
i=1,...,m donde f(x) y gi(x) œ i=1,...,m son linealmente independientes, luego existe 8*=(81*,...,82*) tal
que:
∇f(X*)- Σœi 8i* ∇gi(X*) = 0
8i*(gi(X*)-bi) = 0 œ i=1,...,m
8i ≥ 0 œ i=1,...,m

Teorema 7: Condición Suficiente de óptimo global

Sea f(x) :Rn→R1 una función cóncava a ser maximizada sobre una región factible convexa, luego
todo X*∈Rn que satisfaga las condiciones necesarias de óptimo de Kuhn-Tucker es un máximo global de
NLP.
Sea f(x): Rn→R1 una función convexa a ser minimizada sobre una región factible convexa, luego
todo X*∈Rn que satisfaga las condiciones necesarias de óptimo de Kuhn-Tucker es un mínimo global de
NLP.

Ejemplos:
Veremos, como haciendo uso de los teoremas anteriores, podemos resolver problemas de
Optimización con Programación No Lineal.

Ejemplo 1: Programas Matemáticos no Condicionados

Dado el NLP:
Opt f(x) X14 - 4 X13 + 4 X12 + X24 - X23 - 6 X22

70
 Encontrar máximos y mínimos.
Resolución: Por condición necesaria de óptimo local no condicionado (Teorema 1), se tiene:
 ϑf ( X*) 
 ϑX   4 X 3 − 12 X 2 + 8 X  0
∇f ( X*) =  1  =
 3
1 1 1
= 
 ϑf ( X*)  4 X 2 − 3 X 2 − 12 X 2  0
2

 ϑX 2 

Se obtiene el siguiente sistema de ecuaciones:

4 X 1 ( X 12 − 3 X 1 + 2) = 0
X 2 (4 X 22 − 3 X 2 − 12) = 0
Resolviendo el sistema de ecuaciones resultante se obtienen las siguientes soluciones:
X1*=(0;0) X2*=(0;2,147) X3*=(0;-1,397) X4*=(2;0) X5*=(2;2,147)
X6*=(2;-1,397) X7*=(1;0) X8*=(1;2,147) X9*=(1;-1,397)
Luego, existen nueve puntos del dominio de la función que verifican las condiciones necesarias
de óptimo local no condicionado.
A continuación se analiza si verifican la condición suficiente de óptimo local no condicionado
(Teorema 2), la cual requiere evaluar, en cada uno de los puntos anteriores, la matriz Hessiana.

 ϑ 2 f ( X*) ϑ 2 f ( X*) 
 
ϑX1 X 2  12 X 1 − 24 X1 + 8 
2
ϑX X 0
Hf ( X*) =  2 1 1 =  
 ϑ f ( X*) ϑ f ( X*)  
2
0 2
12 X 2 − 6 X 2 − 12
 
 ϑX 2 X 1 ϑX 2 X 2 

8 0 
H ↓ X1 * =   h11 > 0 H = −96 < 0 → no verifica condición
0 − 12
Luego , X1*=(0;0) no verifica condición suficiente de óptimo local no condicionado.
8 0 
H ↓ X2 * =   h11 > 0 H = 243.4 > 0 → H es positiva definida
0 30.43
Luego, X2*=(0;2,147) es un mínimo local
8 0 
H ↓ X3 * =   h11 > 0 H = 158.4 > 0 → H es definida positiva
0 19 .80

Luego, X3*=(0;-1,397) es un mínimo local.

8 0
H ↓ X4 * =   h11 > 0 H = 0 → H es positiva semidefini da
0 0
Luego, X4*=(2;0) no verifica condición suficiente. No obstante, por extensión del Teorema 2, es
posible que X4* sea un óptimo local.
8 0 
H ↓ X5 * =   h11 > 0 H = 243.4 > 0 → H es definida positiva
0 30 .43

Luego, X5*=(2;2,147) es un mínimo local.

8 0 
H ↓ X6 * =   h11 > 0 H = 158.4 > 0 → H es definida positiva
0 19.80
Luego, X6*=(2;-1,397) es un mínimo local.
− 4 0 
H ↓ X7 * =   h11 < 0 H = 48 > 0 → H es definida negativa
 0 − 12

71
 Luego, X7*=(1;0), es un máximo local
− 4 0 
H ↓ X7 * =   h11 < 0 H = −122 < 0 → H no verifica condición
 0 30.43
Luego, X8*=(1;2,147) no verifica condición suficiente.

− 4 0 
H ↓ X 8* =   h11 < 0 H = −79.2 < 0 → H no verifica condición
 0 19.80
Luego, X9*=(1;-1,397), no verifica condición suficiente.
Como la función no es cóncava ni convexa, no verifica la condición suficiente de Óptimo Global
no condicionado.

Ejemplo 2: Programas Matemáticos Condicionados por Igualdades

Dado el NLP: Opt f(x) = (5 - X1)2 + X22
s.a.: (1 - X1)2 + X22 = 9
se buscan máximos y mínimos.
Resolución: Por condición necesaria de óptimo local condicionado por igualdades (Teorema 4), la
derivada a través del problema equivalente, se tiene:
L(x,λ)=(5-X1)2 + X22 - λ[(1-X1)2 + X22 - 9]
∇L(X*)=0 → -2(5-X1) + 2λ(1-X1)= 0
2 X2 - 2 λ X2 = 0
(1-X1)2 + X22 - 9 = 0

Resolviendo el sistema de ecuaciones resultante se obtienen las siguientes soluciones:

X1*=(4;0; -1/3) X2*=(-2;0; 7/3)
Luego, existen dos puntos que verifican las condiciones necesarias de óptimo local restringido
por igualdades.
A continuación se analiza si dichos puntos verifican la condición suficiente de óptimo local
restringido por igualdades (Teorema 5).

− 2(1 − X1 
Debe∃ z ∈ R 2 no nulo / z T ∇g( X*) = 0 ⇒ (z 1, z 2 ) =0
 2X 2 

 ϑ 2L( X*) ϑ 2 L( X*) 

 
2 − 2λ
[z1, z 2 ]H x L( X*) 1  = [z1, z 2 ] ϑ2X1X1 ϑX1 X 2   z 1  0   z1 
z
2    = [z 1, z 2 ]  
z 2  ϑ L( X*) ϑ L( X*)  2 z  0 2 − 2λ  z 2 
 
 ϑX 2 X1 ϑX 2 X 2 

Para X1*=(4;0; -1/3)

6 
( z 1 ; z 2 )  = 0 ⇒ se verifica ∀ z no nulo z 1 = 0 z 2 ≠ 0
0

[z1; z 2 ]H x L( X*)zz 1  = [z1; z 2 ]80/ 3 0   z1  2

 z  = 8 / 3 z 2 > 0 ∀ z 2 ≠ 0
8 / 3  2 
 2 
Por lo tanto, X1*=(4;0; -1/3) es un mínimo local estricto del problema.
Para Z2*=(-2;0; 7/3)

72
 − 6
( z 1 ; z 2 )  = 0 ⇒ se verifica ∀ z no nulo z 1 = 0 z 2 ≠ 0
0 
Luego:

[z1; z 2 ]H x L( X*)zz 1  = [z1; z 2 ]− 80/ 3 0   z1  2

 z  = −8 / 3 z 2 < 0 ∀ z 2 ≠ 0
− 8 / 3  2 
 2 
Por lo tanto, Z2*=(-2;0; 7/3) es un máximo local estricto del problema.

Ejemplo 3: Problemas Condicionados por Desigualdades

Dado el NLP:
Min: f(x) = X12 + X2
s.a.: X12 + X22 ≤ 9
X1 + X2 ≤ 1

Se resuelve el mismo usando condición necesaria y suficiente de óptimo.

Resolución: Se aplica condición necesaria de óptimo local (Teorema 6), para lo cual es necesario primero
llevar el NLP a la estructura general en base a la cual se planteó el teorema 6, esto requiere en este caso:
max-f(x). Luego se obtiene:

∇f(x) - λ1 ∇g1(x) -λ2∇ g2(x) = 0

λ1[g1(x) - 9] = 0
λ2[g2(x) - 1] = 0
λ1 ≥ 0
λ2 ≥ 0
X12 + X22 ≤ 9
X1 + X2 ≤1

Se genera así el siguiente sistema de ecuaciones e inecuaciones

1. -2 X1 - λ1 2 X1 -λ2 =0
2. -1 -2 λ1 X2 -λ2 =0
3. λ1 (X12 + X22 - 9) =0
4. λ2 (X1 + X2 - 1) =0
5. λ1 ≥ 0
6. λ2 ≥ 0
7. X12 + X22 ≤ 9
8. X1 + X2 ≤1
Resolviendo el sistema de ecuaciones e inecuaciones se obtienen el punto (X*,λ*)=(0;-3;1/6;0)
que verifican las condiciones necesarias de óptimo local.

73
 Se analiza a continuación la condición suficiente de óptimo (Teorema 7) obteniendo:
Función objetivo: f(x)= X12 + X2 es una función convexa.
X12
Región factible: las funciones g1= + X22 y g2= X1 + X2 son convexas y el signo de la
restricción correspondiente es de ≤ → la región factible es convexa. Por lo tanto, todo X* que satisface la
condición necesaria de óptimo local Teorema 7, es mínimo global.

74
Cuarta Parte: Y más allá...
Muchas veces los valores de la celdas de una hoja de cálculo representan variables aleatorias que
no pueden ser determinadas con certidumbre. Cualquier valor incierto en una celda de entrada fluye a
través de toda la planilla modelada creando valores inciertos que involucran algunos grados de riesgo.
Existen varios métodos de análisis de riesgo posibles los que incluyen mejor-caso/peor-caso,
"¿Qué pasa, si...? y la simulación. De los tres métodos, la simulación es la única que provee sólidas
evidencias (hechos y figuras) que pueden ser usadas en la toma de decisiones. Al simular un modelo es
usa RNG (generadores de números al azar) para seleccionar valores representativos de cada variable
independiente incierta en el modelo. Este proceso se repite una y otra vez para generar una muestra
representativa de valores de las variables independientes las cuales luego pueden ser analizadas. Una de
las herramientas que puede incluirse en una hoja de cálculo como Excel es el @Risk.

Bibliografía:
1) Modelado, Simulación y Optimzación de Procesos Químicos, capítulos XIyXII,Dr. Nicolás Scenna y
colaboradores, 1999. [Link]
2) Manual del Ingeniero Químico Perry, Don W. Green et al, 9º edición sección 3.
3) Introduction to Linear Optimization Dimitris Bertsimas John N. Tsitsiklis -Massachusetts Institute of
Technology
4) NONLINEAR PROGRAMMING ANALYSIS AND METHODS MORDECAI AVRIEL Teclznion-
Israel- Institute of Technology Haifa, Israel
5) Numerical Optimization, Second Edition- Editors: Thomas V. Mikosch Sidney I. Resnick Stephen M.
Robinson
6) OPTIMIZATION OF CHEMICAL PROCESSES: Eduardo D. Glandt, Professor of Chemical
Engineering, University of Pennsylvania, Michael T. Klein, Professor of Chemical Engineering, Rutgers
University, Thomas E Edgar, Professor of Chemical Engineering, University of Texas at Austin

75