programacion no lineal



REPÚBLICA ARGENTINA


PROGRAMACIÓN NO LINEAL

Puede reproducirse libremente. Se agradecerá citar la fuente.



Claudio L. R. Sturla

  Bibliografía:
Winston, Wayne L., Investigación de Operaciones, Grupo Editorial Iberoamérica, S. A. De C. V., México, 1.994, ISBN 970-625-029-8.
Chiang, Alpha C., Métodos Fundamentales de Economía Matemática, McGraw Hill/Interamericana deMéxico, S. A. De C. V., 1.998, ISBN 968-422-193-2.

Conceptos introductorios

DEFINICIÓN
Se puede expresar un problema de programación no lineal (PNL)de la siguiente manera:
Encuentre los valores de las variables
x1 , x2 , , xn
que


z f x1 , x2 ,, xn
máximo (o mínimo)

sujeto a:(1)

g1 x1 , x2 ,, xn
g 2 x1 , x2 ,, xn
; ; b1
; ; b2
………………………….
………………………….
g n x1 , x2 ,, xn
; ; bn


Como en la programación lineal z es el funcional del problema de programación no lineal y

g1 x1 , x2 ,, xn
; ; b1 ; g 2
x1 , x2 ,, xn
; ; b2
;… ; g n
x1 , x2 ,, xn
; ; bn

son las restricciones del problema deprogramación no lineal.
Un problema de programación no lineal es un problema de programación no lineal no restringido.
El conjunto de puntos
x1 , x2 ,, xn
, tal que xi
es un número real, es R n
R1 , entonces, es el conjunto de los números reales.
Los siguientes subconjuntos de
R1 (llamados intervalos) serán de particular interés:

a , b
las x que satisfacen a x b
a, b) las x quesatisfacen a x b

(a, b
a, b
las x que satisfacen a x b
las x que satisfacen a x b
a, )
( , b
las x que satisfacen x a
las x que satisfacen x b


Y en forma análoga a las definiciones de la programación lineal.


DEFINICIÓN
La región factible para el problema de programación no lineal es el conjunto de puntos que satisfacen las m restricciones de (1).Supóngase que (1) es un problema de maximización.

x1 , x2 ,, xn


DEFINICIÓN
Cualquier punto X en la región factible, para el cual se tiene que f X


f X para todos los puntos
X de la región factible, es una solución óptima para el problema de programación no lineal.
(Para un problema de minimización, X es la solución óptima si f X
f X para toda X factible.


Por supuesto, siz , g1 , g 2 , , g n
son funciones lineales, entonces (1) será un problema de programa-
ción lineal y puede resolverse mediante el algoritmo simplex.

Ejemplos de Programación No Lineal

Ejemplo N° 1
A una compañía le cuesta c UM por unidad fabricar un producto. Si la compañía cobra p UM por uni-
dad de producto, los clientes pedirán D p
que poner la compañía?

Solución
unidades.Para maximizar las ganancias, ¿qué precio tendría
La variable de decisión de la empresa es p
Dado que la ganancia de la empresa es p
maximización sin restricción:
c D p
, la empresa querrá resolver el siguiente problema de



Ejemplo N° 2
p c D p
máximo
Si se utilizan K unidades de capital y L unidades de trabajo, una compañía puede producir KL unidades de un bien manufacturado. Sepuede conseguir el capital a 4 UM/unidad y el trabajo a 1 UM/unidad. Se dispone de un total de 8 UM para contratar capital y trabajo. ¿Cómo puede la compañía maximizar la cantidad de bienes que se pueden fabricar?

Solución
Sea

K = unidades de capital contratadas y
L = unidades de trabajo compradas

entonces K y L deben satisfacer 4K
L 8 ; K
0 ; L 0
Por lo tanto, la compañía quiereresolver el siguiente problema de maximización restringido:

z KL
máximo
sujeto a
4K L 8
K , L 0

Diferencias entre Programación No Lineal y Programación Lineal
La solución para el problema de programación lineal es un conjunto convexo.
También sabemos que la solución de programación lineal se encuentra en un punto extremo de un conjunto convexo.
Pronto veremos, sin...