UNIVERSIDAD NACIONAL JORGE BASADRE GROHMANN
FACULTAD DE INGENIERA
ESCUELA PROFESIONAL DE INGENIERA EN INFORMTICA Y SISTEMAS
MONOGRAFA
PROGRAMACIN NO LINEAL: ALGORITMO RESTRINGIDO
AUTORES:
Mara Fernanda Zevallos Gmez (2015-119031)
Jakelyn Sintecala Mulluni (2015-119005)
AO: Tercero CICLO: V
CURSO: Investigacin Operativa II
DOCENTE: Ing. Mario Gauna Chino
TACNA PER
2017
INTRODUCCIN
La popularidad de la programacin lineal puede atribuirse a muchos factores,
incluyendo su habilidad para modelar problemas grandes y complejos, as como la de su
resolucin en un intervalo razonable de tiempo mediante el uso del mtodo Simplex,
entre otros. Sin embargo, muchos problemas reales no pueden ser adecuadamente
representados o aproximados como un programa lineal debido a la naturaleza de la no
linealidad de la funcin objetivo y/o la no linealidad de cualquiera de las restricciones.
Los esfuerzos por resolver tales problemas no lineales en forma eficiente provocaron un
rpido progreso durante las pasadas tres dcadas.
La programacin no lineal se ocupa del problema de optimizar una funcin objetivo con
la presencia de restricciones tipo de igualdad y/o desigualdad. Si todas las funciones son
lineales tenemos un programa lineal de lo contrario, el programa es no lineal y su
resolucin es el problema de estudio en esta monografa, el cual est contenido por dos
tipos: restringidos y no restringidos, enfocndonos en este ltimo mediante la aplicacin
de mtodos en la resolucin del ejercicio aplicativo.
2
NDICE GENERAL
INTRODUCCIN 2
NDICE GENERAL 3
CAPTULO I 4
1.1. TTULO 4
1.2. OBJETIVOS 4
1.3. DEFINICIONES DEL TEMA 4
CAPTULO II 13
2.1. PROBLEMA PLANTEADO DEL ALGORITMO RESTRINGIDO 13
CAPTULO III 16
3.1. CONCLUSIONES 16
CAPTULO IV 17
4.2. BIBLIOGRAFA 17
3
CAPTULO I
1.1. TTULO
Programacin no lineal: Algoritmo restringido
1.2. OBJETIVOS
Analizar el problema de programacin no lineal general restringido.
Proponer un problema de aplicacin del algoritmo restringido.
1.3. DEFINICIONES DEL TEMA
1.3.1. Programacin no lineal
Se considera como tal al conjunto de mtodos utilizados para optimizar una
funcin objetivo, sujeta a una serie de restricciones en los que una o ms de
las variables incluidas es no lineal.
1.3.2. Algoritmos restringidos
El problema de programacin no lineal general restringido se define como
( ) = ()
sujeto a:
() 0
Las condiciones de no negatividad 0, son parte de las restricciones.
Incluso, al menos una de las funciones () y () es no lineal, y todas las
funciones son continuamente diferenciables.
El comportamiento errtico de las funciones no lineales impide el desarrollo
de un solo algoritmo para el modelo no lineal general.
1.3.3. Mtodos empleados
Existen varios algoritmos que se pueden clasificar en general como mtodos
indirectos y directos.
4
Los mtodos indirectos resuelven el problema no lineal valindose de
uno o ms programas lineales derivados del programa original. Algunos
ejemplos de algoritmos directos incluyen el mtodo de combinacin
lineal y un breve anlisis del algoritmo SUMT, la tcnica de
maximizacin secuencial sin restricciones.
Los mtodos directos se valen del programa original. Algunos ejemplos
de algoritmos indirectos incluyen las programaciones separable,
cuadrtica y estocstica.
1.3.4. Programacin separable
La programacin convexa es abarca una amplia clase de problemas, sus
supuestos son:
1) f (x) es cncava.
2) Cada una de las () es convexa.
Si hablamos de PROGRAMACIN SEPARABLE, diremos que es un caso
especial de programacin convexa, en donde el supuesto adicional es:
3) Todas las funciones f (x) y () son separables.
Una funcin separable es una funcin en la que cada trmino incluye una
sola variable, por lo que la funcin se puede separar en una suma de
funciones de variables individuales. Por ejemplo, si f (x) es una funcin
separable, se puede expresar como:
() = ( )
=1
Entonces:
La programacin separable es un mtodo de optimizacin no lineal basado
5
en la aproximacin lineal. La idea de la programacin separable para
resolver un problema de P.N.L. es construir una aproximacin lineal del
problema.
Tomando en cuenta una funcin cualquiera no lineal
(1 , 2 , , )
1 (1 ) + 2 (2 ) + + ( )
En el cual el valor de debe encontrarse en el valor menor de i y el mayor
Maximizacin o minimizacin de f(x)la cual es no lineal al igual que sus
restricciones:
()
= 1,2
= (1 , 2 , , )
La programacin separable de manera general queda:
Maximizar o minimizar:
( )
=1
Sujeto a:
( ) ; = 1,2, ,
=1
Entonces el problema combinado equivalente e
Sujeto a:
6
Maximizar (o minimizar):
( )
=1 =1
Sujeto a:
( ) = 1,2, ,
=1 =1
0 1 1, = 1,2, ,
Considere el problema
Maximizar:
() = 1 + 2 4
Sujeto a:
31 + 222 9
1 , 2 0
Procederemos a dividir la funcin segn las variables:
1 (1 ) = 1 1 (1 ) = 31
2 (2 ) = 2 4 2 (2 ) = 222
7
Hacemos una tabla para encontrar los valores por la forma de mediante el
intervalo proporcionado arriba de 1 a 4:
La variable 1 no es aproximada porque las funciones 1 (1 ) y 1 (1 ) ya
son lineales. Considerando 2 (2 ) y 2 (2 ), suponemos cuatro puntos de
ruptura 2 = 0,1,2,3 para k=1,2,3 y 4 ,respectivamente. Dado que 2 3,
entonces :
K ( ) ( )
1 0 0 0
2 1 1 2
3 2 16 8
4 3 81 18
Para conseguir dichos valores se sustituye la x1 0 x2 de acuerdo a rango
(0,1,2) en las ecuaciones que se hallaron en los mismos, formamos un nuevo
modelo:
=1 =1
( ) .(1)
Entonces 2 (2 ) = 2 21 + 2 22 + 2 23 + 2 24
2 (2 ) = 021 + 2 22 + 1623 + 8124
2 (2 ) = 22 + 1623 + 8124
=1 =1
( ) .(2)
Entonces 2 (2 ) = 2 21 + 2 22 + 2 23 + 2 24
2 (2 ) = 021 + 222 + 823 + 1824
8
2 (2 ) = 222 + 823 + 1824
Sabemos que:
() = 1 (1 )+2 (2 )
() = 1 +2 (2 )
() = 1 + 22 + 1623 + 8124
Y tambin se sabe que segn la restriccin:
1 (1 )+2 (2 ) 9
31 +2 (2 ) 9
31 + 222 + 823 + 1824 9
Adems, que:
21 + 22 + 23 + 24 = 1
El problema de aproximacin sera
() = 1 + 22 + 1623 + 8124
Sujeto a
31 + 222 + 823 + 1824 9
21 + 22 + 23 + 24 = 1
Los valores de 2 deben satisfacer la condicin de base
restringida
9
Minimizar:
() = 12 41 2
Sujeto a:
212 + 822 30
0 1 2
0 2 2
Procederemos a dividir la funcin segn las variables:
1 (1 ) = 12 41 2 (2 ) = 2
1 (1 ) = 212 2 (2 ) = 812
Hacemos una tabla para encontrar los valores por la forma de mediante el
intervalo proporcionado arriba de cero a dos:
0 0 0 0 0 0 0
1 1 1 -3 -1 2 8
2 2 2 -4 -2 8 32
Para conseguir dichos valores se sustituye la x1 0 x2 de acuerdo a rango
(0,1,2) en las ecuaciones que se hallaron en los mismos, formamos un nuevo
modelo usando el mtodo de lambda
Minimizar
= 31 + 12 2
=1 =1
10
Aplicando el mtodo simplex:
Tabla 2
Tabla 3
11
Tabla 4
Finalmente se obtiene:
10 = 0
11 = 0
12 = 1
20 = 0
9
21 =
16
7
22 =
16
Para buscar los valores de 1 y 2 se sustituye de la siguiente manera
1 = 10 0 + 11 1 + 12 2 ; 1 = 00 + 01 + 12 = 2
9 7
2 = 20 0 + 21 1 + 22 2 ; 2 = 00 + 1 + = 1,4375
16 16 2
12
Entonces la aproximacin sera (1.4375,2)
El valor ptimo de la funcin se consigue sustituyendo 1 y 2 en
() = 12 41 2
Dando como resultado el valor mnimo -5,4375
CAPTULO II
2.1. PROBLEMA PLANTEADO DEL ALGORITMO RESTRINGIDO
La Wyndor Glass Co. recibi un pedido especial de artculos procesados a mano
que se debe elaborar en las plantas 1 y 2 durante los prximos cuatro meses. Para
cumplir con este pedido ser necesario asignar algunos empleados de las brigadas
de trabajo de los productos normales, por lo que el resto del personal tendr que
trabajar horas extra para utilizar toda la capacidad de produccin de la maquinaria y
equipo de la planta para elaborar estos productos. En particular, a fin de fabricar los
dos nuevos productos normales que se analizaron, el tiempo extra tendr que
utilizar el ltimo 25% de la capacidad disponible en la planta 1 para el producto 1 y
el ltimo 50% de la capacidad disponible en la planta 2 para el producto 2. El costo
adicional del tiempo extra reducir la ganancia de cada unidad del producto 1 de 3 a
2 dlares y del producto 2, de 5 dlares a 1 dlar, de lo que resultarn las curvas de
ganancia, las cuales se ajustan a la forma del caso 1. La administracin ha decidido
usar tiempo extra en lugar de contratar ms trabajadores durante esta situacin
temporal. Sin embargo, insiste en que se aprovechen por completo las brigadas de
trabajo de cada producto en tiempo normal antes de usar cualquier tiempo extra.
An ms, piensa que temporalmente se deben cambiar las tasas de produccin
actuales (x1 5 2 para el producto 1 y x2 5 6 para el producto 2), si esta medida
13
mejora el rendimiento total. Por todo ello, ha girado instrucciones al equipo de IO
para revisar los productos 1 y 2 y determinar la nueva mezcla de productos ms
redituable durante los prximos cuatro meses.
El modelo de programacin lineal del problema original de la Wyndor Glass Co.
Maximizar:
= 31 + 52
Sujeta a:
1 4
22 12
31 + 22 18
1 0 , 2 0
Se modific este modelo:
Sea 1 = 1 + 10 es la tasa de elaboracin del producto 1
En donde
1 es la tasa de produccin alcanzada con tiempos normales de trabajo
10 es la tasa de produccin incremental al usar tiempo extra
Sea 2 = 2 + 20 es la tasa de elaboracin del producto 2
En donde
2 es la tasa de produccin alcanzada con tiempos normales de trabajo
20 es la tasa de produccin incremental al usar tiempo extra
Al sustituir los datos la figura 1 (incluye las tasas mximas de produccin en
tiempo normal y tiempos extra) en este modelo general se obtiene el modelo
especfico.
14
El nuevo problema de programacin lnea trata de determinar los valores de
1 ,10 , 2 y 20
Maximizar:
= 31 + 210 + 22 + 20
Sujeta a:
1 + 10 4
2(2 + 20 ) 12
3(1 + 10 ) + 2(2 + 20 ) 18
1 3 , 10 1, 2 3, 20 3
1 0 , 10 0, 2 0, 20 0
Las restricciones de cota superior del penltimo rengln del modelo convierten
a las primeras dos restricciones funcionales en redundantes, de manera que
estas dos ecuaciones se pueden eliminar.
En efecto, se puede aplicar con seguridad el mtodo smplex a este modelo
para encontrar la mezcla de productos ms redituable.
De manera similar, la solucin ptima para este modelo resulta ser 1 = 3,
10 =1, 2 =3, 20 =0, que es una solucin factible aceptable.
15
CAPTULO III
3.1. CONCLUSIONES
Es frecuente que los problemas de optimizacin incluyan un comportamiento no
lineal que debe tomarse en cuenta. A veces es posible reformular las no
linealidades para que se ajusten al formato de programacin lineal, como en los
problemas de programacin separable. Sin embargo, muchas veces es necesario
usar formulaciones de programacin no lineal.
16
CAPTULO IV
4.2. BIBLIOGRAFA
Hillier F. y Lieberman G. (2010) INTRODUCCIN A LA INVESTIGACIN
DE OPERACIONES. Novena edicin. Espaa: Mc Gram Hill Educacin
Taha H. (2012). INVESTIGACIN DE OPERACIONES. Novena edicin.
Espaa: Pearson
[Link]
17
