fascículo 4

1

Semestre 6

Fascculo

4

Investigacin de

Operaciones

Semestre 6

Investigacin de operaciones


Semestre 6

Tabla de contenido Pgina

Introduccin 1

Conceptos previos 1

Mapa conceptual Fascculo 4 2

Logros 3

Programacin no lineal 3

Forma general 4

Funcin convexa y cncava 5

Teoremas 6

Optimizacin en una variable 7

ptimos locales y globales 8

Teoremas 8

Casos 8

Optimizacin multivariable 11

Mtodo grfico 12

Multiplicadores de Lagrange 13

Programacin cuadrtica 14

Aplicaciones 15

Actividad de trabajo colaborativo 20

Resumen 20

Bibliografa recomendada 21

Nexo 21

Seguimiento al autoaprendizaje 23

Crditos: 3

Tipo de asignatura: Terico Prctica

Semestre 6


Copyright2008 FUNDICIN UNIVERSITARIA SAN MARTN

Facultad de Universidad Abierta y a Distancia,

Educacin a Travs de Escenarios Mltiples

Bogot, D.C.

Prohibida la reproduccin total o parcial sin autorizacin

por escrito del Presidente de la Fundacin.

La redaccin de este fascculo estuvo a cargo de

JUAN CASTRO ORDOEZ

Docente tutor Programa de Ingeniera de Sistemas a Distancia.

Sede Bogot, D.C.

Correccin de estilo

Adriana Valencia Rodrguez

Diseo grfico y diagramacin a cargo de

SANTIAGO BECERRA SENZ

ORLANDO DAZ CRDENAS

Impreso en: GRFICAS SAN MARTN

Calle 61A No. 14-18 - Tels.: 2350298 - 2359825

Bogot, D.C., Marzo de 2012

1

Fascculo No. 4

Semestre 6


Investigacion de

operaciones

En un problema de Progra-macin No Lineal (PNL), las variables de decisin estn

expresadas como funciones

no lineales en la funcin

objetivo en las restricciones

del modelo.

Introduccin

En el anterior semestre, se abord el tema de Programacin Lineal (PL).

Una suposicin importante de la PL, es que las variables de decisin se

expresan en forma lineal (Funcin objetivo y funciones de restriccin); es

decir, en la PL, su objetivo es optimizar (maximizar o minimizar) una fun-

cin objetivo sujeta a ciertas restricciones lineales. Por lo general, esta su-

posicin se cumple en la vida real para muchos problemas prcticos; pero

tambin es frecuente que no sea de esta forma. Un caso en particular se

ve, en los problemas de planeacin econmica donde es necesario mane-

jar algoritmos de programacin no lineal.

En un modelo de Programacin No Lineal (PNL), sus variables de deci-

sin estn expresadas como funciones no lineales tanto en la funcin obje-

tivo como en las restricciones del modelo de optimizacin.

Aunque no hay un mtodo especfico para la solucin de problemas de

PNL, se han aplicado algunos algoritmos directos o indirectos como el del

gradiente para los primeros y la programacin cuadrtica para los segun-

dos.

Conceptos previos

Para el buen desarrollo de este fascculo y aprendizaje de la Programacin

Lineal, se debe tener en cuenta lo aprendido en los siguientes temas:

Programacin lineal.

Clculo diferencial.

Para esto, responda las siguientes preguntas y resuelva los ejercicios pro-

puestos:

1.- Qu es programacin lineal?

2.- Qu es una variable de decisin?

2


Investigacin de

operaciones

Fascculo No. 4

Semestre 6

3.- Cul es la estructura de un modelo de PL?

4.- Cul es la metodologa para desarrollar un problema de PL?

5.- Defina funcin continua y funcin discontinua.

6.- Cul es el concepto de derivada?

7.- Cul es el concepto de la segunda derivada?

8-. Qu es una derivada parcial?

9.- Qu es un mximo local?

10.- Qu es un mnimo global?

11.- Cules son los criterios de la primera y segunda derivada?

Mapa conceptual Fascculo 4

3


Fascculo No. 4

Semestre 6

Investigacion de

operaciones

Al finalizar el estudio de este fascculo, el estudiante:

Define una funcin convexa.

Soluciona un problema de programacin no lineal.

Encuentra la solucin a un problema de programacin cuadrtica.

Programacin no lineal

La Programacin no Lineal (PNL), es una parte de la Investigacin Operati-

va cuya misin es proporcionar una serie de resultados y tcnicas tenden-

tes a la determinacin de puntos ptimos para una funcin (funcin objeti-

vo) en un determinado conjunto (conjunto de oportunidades), donde tanto

la funcin objetivo, como las que intervienen en las restricciones que de-

terminan el conjunto de oportunidades pueden ser no lineales. Evidente-

mente, la estructura del problema puede ser muy variada, segn las fun-

ciones que en l intervengan (a diferencia de la Programacin Lineal (PL),

donde la forma especial del conjunto de oportunidades y de la funcin ob-

jetivo permite obtener resultados generales sobre las posibles soluciones

y facilitan los tratamientos algortmicos de los problemas). Ello ocasiona

una mayor dificultad en la obtencin de resultados, que se refleja tambin

en la dificultad de la obtencin numrica de las soluciones. En este senti-

do, hay que distinguir entre las diversas caracterizaciones de ptimo, que

slo se emplean como tcnicas de resolucin en problemas sencillos, y los

mtodos numricos iterativos, cuyo funcionamiento se basa en estas ca-

racterizaciones, para la resolucin de problemas ms generales.1

En general, la PNL responde a la necesidad de solucionar problemas ex-

presados en trminos de funciones no lineales, modelados en situaciones

de la vida real.

1 Tomado de: http://jorgesosasanchez.wordpress.com/unidad-3/ .

LogrosLogrosLogros

http://jorgesosasanchez.wordpress.com/unidad-3/

4


Investigacin de

operaciones

Fascculo No. 4

Semestre 6

Un problema de PNL que no

tenga restricciones, es un

PNL irrestricto.

Forma general

Es decir, en el problema de PNL se buscan los valores de las variables de

decisin; para:

De igual manera que en el modelo de PL, es la funcin objetivo y

son las funciones de las restricciones del modelo de PNL (funciones

no lineales). Si un problema de este estilo no tiene restricciones, es un

modelo de PNL irrestricto.

De otra parte, el conjunto de los es (conjunto de los nmeros reales) y

particularmente con los siguientes subconjuntos (intervalos):

5


Fascculo No. 4

Semestre 6

Investigacion de

operaciones

, es una funcin con-

vexa s y slo s es

una funcin cncava y vice-

versa.

En forma similar que la PL, la regin factible en un problema de PNL, es

el conjunto de los puntos que satisfacen todas las restricciones. Un punto

en esta regin, es un punto factible y el punto que no est es un punto no

factible.

Por otra parte, en un caso de maximizacin, cualquier punto en la regin

factible para la cual , es una solucin ptima del PNL.

De manera anloga, en un caso de minimizacin, cualquier punto en la

regin factible para la cual , es una solucin ptima del PNL.

Funcin convexa y cncava

Una funcin es convexa en un conjunto convexo S, si todo segmento que

une dos puntos de la grfica est por encima de la grfica, figura 4.1 a).

Una funcin es cncava en un conjunto convexo S, si todo segmento que

une dos puntos de la grfica est por debajo de la grfica, figura 4.1 b).

En otras palabras, es una funcin convexa s y slo s

es una funcin cncava y viceversa.

Tambin se pueden encontrar funciones cncavas y convexas, figura 4.1

c), de igual modo, funciones que no son ni cncavas ni convexas, figura

4.1 d).

6


Investigacin de

operaciones

Fascculo No. 4

Semestre 6

Figura 4.1. Funcin convexa y cncava.

Fuente. El autor

En el estudio de problemas de PNL, las funciones convexas y cncavas

juegan un papel muy importante. Por ejemplo, la suma de dos funciones

convexas es una funcin convexa, de igual forma, que la suma de dos fun-

ciones cncavas da como resultado una funcin cncava.

Teoremas

1. Supngase que existe para las x de un conjunto convexo S. Enton-

ces f(x) es una funcin convexa en S s y slo s para toda x en

S.

2. Supngase que existe para las x de un conjunto convexo S. Enton-

ces f(x) es una funcin cncava en S s y slo s para toda x en

S.

4.1.

Diga si las siguientes funciones son convexas o cncavas:

a) b) c)

7


Fascculo No. 4

Semestre 6

Investigacion de

operaciones

Optimizacin en una variable

Un programa de PNL en una variable con restricciones y en un subinterva-

lo finito [a, b] tiene la forma:

Recordando que f(x) es una funcin no lineal de la variable nica x. El valor

ptimo (mximo o mnimo) se encuentra sobre el subintervalo finito [a, b],

figura 4.2.

Figura 4.2. Ejemplos de puntos extremos para una funcin de una sola variable.

Fuente. Modificado de: HAMDY A. Taha, INVESTIGACIN DE OPERACIONES, 7a. edicin, Ed. PEARSON, Mxico 2004, p. 702.

En dado caso que no tenga restricciones, es un programas de PNL irres-

tricto y el punto ptimo se encuentra en un intervalo infinito (-, ). La fi-

gura 4.1, muestra ejemplos de funciones de una sola variable en un inter-

valo infinito.

Para encontrar la solucin ptima a los programas de PNL con una varia-

ble y con restricciones, se hallan los mximos o mnimos locales.

8


Investigacin de

operaciones

Fascculo No. 4

Semestre 6

ptimos locales y globales

En una funcin objetivo f(x) hay un mnimo local (relativo) en xo, si existe

un intervalo pequeo con centro en xo tal que para toda x en

ese intervalo en la cual la funcin est definida. Si adems, para

toda x en la cual la funcin est definida entonces el mnimo en xo tam-

bin es un mnimo global (absoluto). Ver figura 4.2.

Similarmente, en una funcin objetivo f(x) hay un mximo local (relativo)

en xo, si existe un intervalo pequeo con centro en x

o tal que

para toda x en ese intervalo en la cual la funcin est definida. Si adems,

para toda x en la cual la funcin est definida, entonces el

mximo en xo tambin es un mximo global (absoluto). Ver figura 4.2.

Teoremas

1. Si f(x) es continua en un intervalo continuo y acotado [a, b], entonces

f(x) tiene ptimos globales en ese intervalo. Es decir, un mximo global

y un mnimo global.

2. Si f(x) tiene un ptimo local en xo y si f(x) es diferenciable en un pequeo

intervalo con centro en xo, entonces f (x

o)=0.

3. Si f(x) tiene diferencial en un pequeo intervalo con centro en xo y si

f(xo)=0 y f(x

o)>0, entonces f(x) tiene un mnimo local en x

o. En caso

contrario, si f(xo)=0 y f(x

o)

9


Fascculo No. 4

Semestre 6

Investigacion de

operaciones

3. Puntos finales a y b del intervalo [a, b]. Ver figura 4.5.

La figura 4.5, muestra como se determinan los ptimos locales para este

caso.

Figura 4.3. Ejemplos de ptimos locales cuando f(x) existe. Caso 1.

Fuente. WINSTON Wayne L., Investigacin de operaciones: Aplicaciones y algoritmos, 4 edicin, Ed. Thomson, Mxico 2005, pg.

638.

10


Investigacin de

operaciones

Fascculo No. 4

Semestre 6

Figura 4.4. Ejemplos de ptimos locales cuando f(x) no existe. Caso 2.


639.

11


Fascculo No. 4

Semestre 6

Investigacion de

operaciones

Figura 4.5. Ejemplos de ptimos locales cuando x

o es un punto final. Caso 3.


640.

Las figuras 4.6 y 4.7, muestran un ejemplo de aplicacin para los casos

vistos anteriormente y de la determinacin de los puntos extremos, respec-

tivamente, para una funcin con una sola variable de decisin.

Optimizacin multivariable

Para los programas de PNL multivariable, se presentan dos casos: a) sin

restricciones y b) con restricciones.

12


Investigacin de

operaciones

Fascculo No. 4

Semestre 6

El mtodo grfico, es una

excelente herramienta en la

solucin de problemas de

PNL y sigue la misma meto-

dologa de la PL.

Para el primer caso, el modelo es el siguiente:

Ahora bien, se supone las derivadas parciales de , tan-

to primera como segunda, existen y son continuas en todos los puntos. Es

decir:

Si la anterior derivada parcial es igual a cero, es un extremo local.

Para el segundo caso, PNL con restricciones, tambin se presentan dos

casos: con restricciones de igualdad y con restricciones de desigualdad.

Para las primeras, se utilizan los multiplicadores de Lagrange para su solu-

cin y para la segunda, una extensin de stos multiplicadores y las con-

diciones generales de Karush-Kuhn-Tucker (KKT). Aunque a veces el

mtodo grfico puede dar una solucin preliminar exitosa. El modelo gene-

ral de un programa de PNL con restricciones es:

Mtodo grfico

Hay algunos problemas de PNL que se pueden resolver exitosamente me-

diante el mtodo grfico; sin embargo, slo aquellos cuyas caractersticas

particulares lo admiten, en consecuencia, se requiere eso s de cierta ex-

periencia y un buen software de graficacin de ecuaciones.

13


Fascculo No. 4

Semestre 6

Investigacion de

operaciones

Por lo general y facilidad se utilizan funciones con mximo dos variables de

decisin y se pueden presentar los siguientes casos:

1.- Funcin objetivo lineal con una o ms restricciones no lineales. Ver

ejemplo en la figura 4.8 a).

2.- Funcin objetivo no lineal con restricciones lineales. Ver ejemplos en la

figura 4.8 b) y c). Si la funcin objetivo es cuadrtica, es decir, con ex-

ponente dos, es un problema de programacin cuadrtica.

3.- Funcin objetivo no lineal con una o ms restricciones no lineales.

Para la solucin de estos casos bsicamente se sigue el procedimiento de

solucin grfica de programacin lineal. En la figura 4.8, se muestran

ejemplos de aplicacin del mtodo grfico.

Multiplicadores de Lagrange

Generalmente los multiplicadores de Lagrange (en honor a Joseph Louis

Lagrange 1736 1813), se usan para solucionar problemas de PNL en

donde las restricciones son una igualdad. El modelo es el siguiente:

Las caractersticas que debe tener este modelo son:

No hay condicin de no negatividad.

Las funciones deben ser continuas y tener derivada al menos en segun-

do orden.

14


Investigacin de

operaciones

Fascculo No. 4

Semestre 6

Las restricciones deben ser ecuaciones, o sea igualdades con holgura

cero (0).

El nmero de restricciones debe ser menor que el nmero de variables

de decisin, es decir, m

15


Fascculo No. 4

Semestre 6

Investigacion de

operaciones

Un problema de programa-

cin cuadrtica (PPC) es un

modelo de PNL, en donde

la funcin objetivo, es

cuadrtica y las restriccio-

nes son lineales.

objetivo y en las restricciones tienen grado 1 o 0. Es decir, la funcin obje-

tivo es cuadrtica y las restricciones son lineales.

Las caractersticas que debe tener este modelo son:

La funcin objetivo debe ser cuadrtica.

Las restricciones deben ser lineales.

Se diferencia de la PL porque en la funcin objetivo tambin incluyen

trminos como X2

j y X

jX

k.

El modelo general del programa es encontrar X1, X

2, , X

n tales que:

Donde los y son constantes.

La figura 4.10, es un ejemplo de aplicacin de la programacin cuadrtica.

Aplicaciones

La figura 4.6, muestra un ejemplo de aplicacin de los casos vistos en la

solucin para un problema de PNL con una variable.

16


Investigacin de

operaciones

Fascculo No. 4

Semestre 6

Figura 4.6. Ejemplo de aplicacin de solucin para un problema de PNL con una variable.


641.

17


Fascculo No. 4

Semestre 6

Investigacion de

operaciones

Figura 4.7. Ejemplos de puntos extremos para una funcin de una sola variable

Fuente. Modificado de: HAMDY A. Taha, INVESTIGACIN DE OPERACIONES, 7a. edicin, Ed. PEARSON, Mxico 2004, p. 705.

18


Investigacin de

operaciones

Fascculo No. 4

Semestre 6

Figura 4.8. Ejemplos de aplicacin del mtodo grfico.

Fuente. Modificado de: http://chikareven.wordpress.com/ilustracion-grafica-de-problemas-de-programacion-no-lineal/

http://chikareven.wordpress.com/ilustracion-grafica-de-problemas-de-programacion-no-lineal/

19


Fascculo No. 4

Semestre 6

Investigacion de

operaciones

Figura 4.9. Ejemplos de aplicacin de los multiplicadores de Lagrange.


667.

20


Investigacin de

operaciones

Fascculo No. 4

Semestre 6

Figura 4.10. Ejemplo de aplicacin de la programacin cuadrtica.


680.

Investigue en diferentes medios y entregue un informe sobre los siguientes te-

mas:

1.- Algoritmo de Philip Wolfe.

2.- Matriz Hessiana.

3.- Seccin urea.

4.- Condiciones de Karush-Kuhn-Tucker (KKT).

5.- Matriz Jacobiana.

Para los temas o casos anteriores d un ejemplo de aplicacin.

En este fascculo, se hizo un breve anlisis de la programacin no lineal

(PNL) tanto en una variable como en varias variables de decisin. Lo ante-

rior, en razn a que en la vida real no siempre se encuentran casos o pro-

blemas lineales, a nivel econmico. Pese a las buenas bases que se nece-

sitan de clculo multivariado y vectorial el tratamiento y desarrollo del se

21


Fascculo No. 4

Semestre 6

Investigacion de

operaciones

hizo lo ms sencillo posible. Gracias a estos mtodos de solucin de PNL,

se han podido resolver muchos problemas que con la programacin lineal

no se haba logrado. Cabe anotar que, el mtodo grfico es el de ms fcil

aplicacin, aunque requiere de una buena herramienta de graficacin y

para ello estn los ingenieros de sistemas; para crear cada vez ms y me-

jores elementos de software que ayuden eficientemente a la toma de deci-

siones por parte de los gerentes de las organizaciones.

BRONSON Richard, INVESTIGACIN DE OPERACIONES, Ed. Mc Graw

Hill, Mxico 1983.

CHEDIAK PINZON Francisco, VERA MENDEZ Flaminio, Investigacin de

operaciones, 1 edicin, volumen 2, Ed. El Poira, Colombia 2005.

HAMDY A. Taha, INVESTIGACIN DE OPERACIONES, 7a. edicin, Ed.

PEARSON, Mxico 2004. Texto gua.

HILLIER Frederick, LIEBERMAN Gerarld J., Introduccin a la Investigacin

de Operaciones, 3a. edicin, Ed. Mc Graw Hill, Mxico l982.

WINSTON Wayne L., Investigacin de operaciones: Aplicaciones y algorit-

mos, 4 edicin, Ed. Thomson, Mxico 2005. Texto gua.

Despus de aprender y resolver diferentes modelos de investigacin de

operaciones, se ver una aplicacin de la misma en el rea de la logstica,

se trata de los modelos de inventarios. Para un director de una empresa es

importante saber cul es la cantidad econmica de pedido ptima y sus

respectivos costos, y stos sern los temas que se vern en el siguiente

fascculo.

22


Investigacin de

operaciones

Fascculo No. 4

Semestre 6

23


Fascculo No. 4

Semestre 6

Investigacion de

operaciones

Seguimiento al autoaprendizajeSeguimiento al autoaprendizajeSeguimiento al autoaprendizaje

Investigacin de operaciones - Fascculo No. 4

Nombre_______________________________________________________

Apellidos ________________________________ Fecha: _________________

Ciudad___________________________________Semestre: _______________

Resuelva las siguientes preguntas con el fin de evaluar su proceso de auto-

aprendizaje:

1.- Encuentre la solucin ptima para:

a)

b)

Tomado de: Winston, problemas 5 y 6 de la pgina 648.

2.- Resuelva mediante el mtodo grfico el siguiente problema:

Investigue en diferentes medios y d un ejemplo de aplicacin para:

3.- Solucin por los multiplicadores de Lagrange.

4.- Solucin del modelo de programacin cuadrtica.

fascículo 4

Documents