I.

INTRODUCCIÓN

Los problemas de programación lineal son muy comunes y cubren un

amplio rango de aplicaciones, pues se cumple para problemas prácticos; sin
embargo, en la vida real existen muchos problemas que no pueden ser
representados adecuadamente como un programa lineal debido a la naturaleza
no lineal de sus variables de decisión.

Los problemas de optimización no lineal son más difíciles de resolver que

los lineales. Estas dificultades aparecen incluso en el caso más simple como el
de optimizar una función de una variable en R sin restricciones.

La optimización no lineal proporciona información fundamental para el

análisis matemático, y se usa extensamente en las ciencias aplicadas y en
diversos campos como la ingeniería, análisis de regresión, control de
inventario, exploración geofísica, …

En el siguiente trabajo se presentan las diferentes técnicas para resolver los

problemas matemáticos y los resultados de los algoritmos de optimización,
tomando en cuenta que estos dependen de la naturaleza de la función objetivo
y de las restricciones.

1
 II. PROGRAMACIÓN NO LINEAL

Un modelo de Programación No Lineal (PNL) es aquel donde las variables

de decisión se expresan como funciones no lineales ya sea en la función
objetivo, restricciones o ambas, de un modelo de optimización.

Cuando un problema de programación no lineal tiene una o dos variables,

esta se puede representar gráficamente. El área que delimita las soluciones
factibles en un gráfico se representa de forma curva.

La función objetivo puede ser de tipo cóncavo o convexo. Es cóncavo,

cuando se trata de maximizar utilidades, contribuciones, etc. Y convexo,
cuando se trata de minimizar recursos, costos, etc.

No siempre la solución óptima se encuentra en un punto extremo de la región

de factibilidad.

Hay casos donde el punto óptimo está en el interior de la región factible.

Existen dos tipos de algoritmos: restringidos y sin restricción

II.1.  ALGORITMOS SIN RESTRICCIÓN

A continuación, voy a presentar dos algoritmos para un problema no
restringido: el algoritmo de búsqueda directa y el algoritmo de gradiente.

a) Método de Búsqueda Directa

El procedimiento localiza el óptimo estrechando en forma progresiva el

intervalo de incertidumbre hasta cualquier grado de exactitud que se desee.
Existen dos algoritmos estrechamente relacionados: el método de búsqueda
dicótomo y el método de sección dorada (o áurea). Ambos buscan la
maximización de una función unimodal f(x) en el intervalo a ≤ f(x) ≤ b, que se
sabe que incluye el punto óptimo x *. Los dos métodos comienzan con I 0 = (a,b)
que representa el intervalo inicial de incertidumbre.

2
Paso general i. Sea Ii−1 = (XL,XR) el intervalo actual de incertidumbre (en la
iteración 0, XL=a y XR=b). A continuación, se definen X1 y X2 tales que

 El siguiente intervalo de incertidumbre I i, se define como sigue:

La manera en que se determinan X 1 y X2 garantiza que Ii  Ii-1.El algoritmo

termina con la iteración k si Ik ≤ ∆, donde ∆ es el grado de exactitud definido por
el usuario.
La diferencia entre los métodos dicótomo y de sección dorada estriba en la
forma en que se calculan X1 y X2. La tabla siguiente presenta las fórmulas.
 

En el método dicótomo los valores X1 y X2 se encuentran simétricos respecto

del punto medio del actual intervalo de incertidumbre. Esto significa que
 

La aplicación repetida del algoritmo garantiza que la longitud del intervalo de

incertidumbre se acercará al nivel de exactitud deseado, ∆.
 En el método de la sección dorada la idea es de mayor involucramiento. Se
puede apreciar que cada iteración del método dicótomo requiere calcular los
dos valores f(X1) y f(X2), pero termina por descartar alguno de ellos. Lo que
propone el método de la sección dorada es ahorrar cálculos mediante el reúso
del valor descartado en la iteración inmediata siguiente.
 

3
Cuando el intervalo de incertidumbre I i en la iteración i es igual a (XL,XR) o a
(X1,XR).Considere el caso en que Ii es igual a (XL,X2), lo cual significa que
X1 está incluido en Ii. En la iteración i+1, seleccione X2 = X1 de la iteración i, lo
cual lleva a la siguiente ecuación:

El diseño de los cálculos del método de la sección dorada garantiza una

reducción α en los intervalos de incertidumbre sucesivos; esto es:

 Comparado con el método dicótomo, el método de la

sección dorada converge más rápidamente hacia el nivel deseado de exactitud.

b) Método del gradiente

Este método se utiliza para optimizar funciones que son dobles continuamente
diferenciables. La idea es generar puntos sucesivos en la dirección del
gradiente de la función. El final del método del gradiente se encuentra en el
punto donde el vector gradiente se anula. Esta sólo es una condición necesaria
para la optimalidad. La optimalidad no se puede comprobar a menos que a
priori se sepa que f(x) es cóncava o convexa.
Supongamos que se busca el máximo de f(X). Sea X 0 el punto inicial donde se
inicia el procedimiento, y se define

∇f(Xk) como el gradiente de f en el punto Xk. Se trata de determinar una

trayectoria particular p a lo largo de la cual se maximice en un punto
dado.

4
Esto se logra si se seleccionan los puntos sucesivos X k y Xk+1 de tal modo que:

Donde rk es el tamaño de paso óptimo en Xk.

El tamaño de paso Xk se determina de tal modo que el siguiente punto, X k+1,
conduzca al mayor mejoramiento de f. Esto equivale a determinar r=r k que
maximice la función

 Como ℎ(r) es una función de una variable, con el método de búsqueda que se
expuso arriba se puede determinar el punto óptimo, siempre que ℎ(r) sea
estrictamente unimodal. El procedimiento propuesto termina cuando dos puntos
sucesivos de prueba, Xk y Xk+1, son aproximadamente iguales. Esto
equivale que

Ya que rk ≠ 0, la condición necesaria ∇f(Xk) = 0

 se satisface en Xk.

II.2. OPTIMIZACIÓN RESTRINGIDA

Como ejemplo considere el siguiente problema de programación no lineal.

Minimizar f(x)
sujeta a
g¡(x) ≤ 0 i = 1, 2, …, m
hj(x) = 0 j = 1, 2, …, l

donde f, g1, g2, …, gm. h1, h2,...., hl, son funciones definidas en E n, el espacio
euclidiano de n dimensiones. X es un subconjunto de En. y x es un vector de
componentes x1, x2,...,xn.
El problema anterior puede ser resuelto para los valores de las variables
x1,x2,...,xn que satisfacen las restricciones y que minimicen la función f.

5
La función f es llamada usualmente la función objetivo. Cada una de las
restricciones gi(x) para i=1,2, …, m es llamada restricción de desigualdad y
cada una de las restricciones h j(x) para j=1,2,...,l es llamada restricción de
igualdad.
Un vector x que satisface todas las restricciones es llamado una solución
factible al problema.

Para comenzar con la resolución de un problema no lineal se representa la

restricción en un gráfico, para ello, se utiliza el mismo procedimiento empleado
en el método gráfico de programación lineal.

Y=0 --- X ≤ 68.19

X=0 --- Y ≤ 83.51

De acuerdo con el procedimiento por el método grafico de programación lineal,

se debe dibujar en un plano cartesiano cada una de las restricciones
formuladas matemáticamente.

6
La restricción se representa por una curva convexa, por lo que la función
objetivo es cóncava. Para graficar la función objetivo, se asigna un valor
cualquiera a la variable X y a la contribución; para este ejemplo, se asignó un
valor a X=40 y una contribución de $1,000.

Una vez obtenidos los valores de X, Y para la función objetivo, se pueden

representar en un gráfico y prolongarlo hasta tocar el punto más lejano del área
de soluciones factibles, para hallar la solución óptima.

La solución óptima para este ejemplo es X=30 y Y=75; sin embargo, puede
calcularse matemáticamente. Para ello, se debe encontrar la derivada de la
función objetivo, como se muestra a continuación:

7
Una vez encontrada la derivada de la función objetivo, se procede a encontrar
la derivada de la restricción:

Se igualan los resultados de la derivada de la restricción con la derivada de la

función objetivo:

Se sustituye la ecuación Y resultante en la ecuación original de restricción:

8
Como se observa en el gráfico anterior, la solución óptima es X =30, por lo que
sustituiremos ese valor en la ecuación resultante:

Como X=30 satisface la ecuación, se puede considerar como un valor óptimo

para el problema. Ese mismo valor puede sustituirse en la ecuación de
restricción original, para encontrar el valor óptimo de la variable Y.

Se tienen los valores óptimos de X e Y, por lo que ahora se procede a calcular

la contribución óptima, sustituyendo los valores en la función objetivo:

Se puede concluir que la empresa necesita producir 30 unidades del producto

X y 75 unidades del producto Y para tener una contribución máxima de $984.

a) Programación Separable

9
La programación separable es un caso especial de programación convexa.
Todas las funciones f(x) y g(x) son funciones separables.
Una función separable es una función en la que cada término incluye una sola
variable, por lo que la función se puede separar en una suma de funciones de
variables individuales. Por ejemplo, si  f(x) es una función separable, se puede
expresar como

EJEMPLO

Dividimos la función según las variables

Se hace una tabla para encontrar los valores por la forma de λ mediante el
intervalo de 0 a 2

Formamos un nuevo modelo usando el método Lamda

10
Estandarizamos agregando una variable de holgura

Usando el método simplex, se obtuvo:

Entonces, la aproximación sería (1,4375 ;2)

Reemplazando x1 y x2 en la función:

Da como resultado el valor mínimo

-5.4375

Es importante distinguir estos problemas de otros de programación convexa,

pues cualquier problema de programación separable se puede aproximar muy
de cerca mediante uno de programación lineal y, entonces, se puede aplicar el
eficiente método símplex.

b) Programación Cuadrática

Un problema de Programación Cuadrática es aquél que contiene una función

objetivo cuadrática y restricciones lineales

Una función cuadrática, en notación matricial, es una función de la forma

11
EJEMPLO

Aplicando los multiplicadores de Lagrange tenemos:

Las primeras derivadas parciales son:

El problema de programación lineal equivalente al original de acuerdo al

método de Wolfees:

Con las siguientes restricciones de holgura:

Utilizando los métodos simplex se tiene que la solución básica inicial es:

12
La solución que corresponde al óptimo es:

c) Programación Estocástica

La Programación Estocástica reúne aquellos modelos de optimización en

donde uno o más parámetros del problema son modelados a través
de variables aleatorias.

13
Es la herramienta matemática que ofrece soluciones a los problemas
formulados en sistemas estocásticos, donde el problema resultante es un
problema matemático de optimización de dimensión no trivial.

Se formula de la siguiente forma:

Donde el conjunto de soluciones factibles X está definido por sus limitaciones y

restricciones de la siguiente forma :

Las funciones son funciones reales y es un conjunto

de condiciones específicas.

La función Z es llamada función objetivo. Todas las funciones que intervienen

pueden depender de parámetros, lo que dará lugar a programas estocásticos si
algunos de los parámetros son aleatorios.

d) Programación Geométrica

Un programa geométrico es un problema de optimización de la forma

14
donde  son posinomios:

Y son monomios:

Tiene múltiples aplicaciones, como el dimensionamiento de circuitos y la estima
ción paramétrica vía regresión logística en estadística.

EJEMPLO
Encontrar las dimensiones de una caja rectangular sin tapa con un área fija de
superficie So que tenga volumen máximo.

Entonces, nos piden resolver:

15
El valor de V está acotado y esa cota (máxima) es alcanzada cuando hay igualdad en
la desigualdad. Supongamos que V es maximizado cuando

Resolviendo se tiene que las dimensiones son:

Y el máximo volumen de la caja será:

III. CONCLUSIONES

16
- En general, estos algoritmos convergen solamente hacia un óptimo
local. Es importante ejecutar estos algoritmos con el fin de
seleccionar la mejor solución entre todas las encontradas.

- Un problema de programación no lineal puede convertirse en un

problema sin restricciones; introduciendo variables de holgura y un
coste que aumenta cuando la desviación disminuye, en la función
objetivo.

- Cuando las funciones son convexas, los algoritmos de descensos

convergen hacia un óptimo local.

- Al contrario del caso del método símplex para la programación lineal,

no existe un algoritmo eficiente que se pueda utilizar para resolver
todos los problemas de programación no lineal.

- Se dispone de gran variedad de algoritmos de alta eficiencia para la

optimización no restringida, y algunos emplean una sucesión de
aproximación lineales y cuadráticas al problema original.

- Los métodos directos de programación lineal son los algoritmos del

gradiente, donde el máximo (mínimo) de un problema se busca
siguiendo la tasa de incremento (disminución) más rápida de la
función objetivo en un punto.

- En los métodos indirectos, el problema original se transforma

primero en un problema auxiliar del cual se determina el óptimo.
Algunos ejemplos son la programación cuadrática, separable y
estocástica.

17