Programacin No Lineal Lagrange, KKT y Lingo

Integrantes: Cristopher Alvear Norma Contreras Valentina Daz Nicols Oate

Profesora: Virna Ortiz

7 de noviembre, 2014

1

Introduccin.

En el presente informe, se expondr el desarrollo de 2 problemas de programacin no lineal

mediante diversos mtodos algortmicos, y adems, se realizar un anlisis consistente

conjunto a grficas para representar el problema.

Para realizar el proceso de bsqueda y obtencin de las soluciones, utilizamos las

herramientas introducidas en la asignatura Investigacin Operativa 2, ya sea software o

algoritmos matemticos que nos permitan obtener resultados correctos y rpidamente.

En preciso, utilizamos los algoritmos de Lagrange y el teorema de Karush Kuhn Tucker

como herramientas de modelado y resolucin matemticas, mientras que para el

procesamiento automatizado de los modelos utilizamos el software Lingo, diseado para

resolver todo tipo de problemas relacionado con optimizacin, ya sea lineales, enteros, no

lineales, etc., adems del software Maple para realizar los clculos matemticos, y, por ltimo

para el graficado y detallado de la funcin objetivo utilizamos MatLab y WolframAlpha.

La idea fundamental es lograr formular, analizar y entender el problema y los resultados

obtenidos, para poder luego saber cmo aplicar stos en una solucin.

En general, el procedimiento a seguir es, formular el modelo matemtico, resolverlo e

interpretarlo. Para esto se debe reconocer las variables de decisin que intervienen en el

problema, la funcin que se desea optimizar, ya sea minimizar o maximizar, y las restricciones

a las cuales est sujeta sta.

2

Problema de maximizacin petrolfera.

Una compaa petrolera debe determinar cuntos barriles de petrleo hay que extraer en

los prximos dos aos. Si la compaa extrae X1 millones de barriles durante un ao, se

podr vender cada barril a 30 - X1 euros. Si extrae X2 millones de barril durante el segundo

ao, se podr vender cada barril a 35 - X2 euros. El costo para extraer X1 millones de barriles

en el primer ao es de X12 millones de euros y el costo para extraer X2 millones de barriles

durante el segundo ao es de X22 millones de euros. Se puede obtener como mximo un

total de 20 millones de barriles de petrleo, y se puede gastar como mximo 250 millones

de euros en la extraccin. Formular el PNL para ayudar a la empresa a maximizar sus

ganancias para los dos primeros aos.

Variables de decisin:

X1: Millones de barriles extrados en el primer ao.

X2: Millones de barriles extrados en el segundo ao.

En general, se desea saber cunto debe extraer la empresa petrolfera en cada uno de los

siguientes 2 aos para maximizar sus utilidades, por lo tanto, la funcin objetivo son la

ganancia menos el costo de extraccin de cada barril de petrleo.

Modelo:

Max Z(X1, X2) = X1(30 X1) + X2(35 X2) X12 2X22

s.a. X12 + 2X22 250

X1+ X2 20

X1, X2 0

As, luego de la formulacin del problema, implementamos el modelo en Lingo, siendo

bsicamente el siguiente script:

Se puede observar que la funcin objetivo es la que nos entrega la utilidad de la empresa

en funcin de la cantidad (en millones) de barriles vendidos en el primer y segundo ao,

mientras que las restricciones son los lmites de presupuesto (250 millones) y cantidad de

barriles (20 millones) respectivamente.

Finalmente presionamos Solve para que Lingo nos entregara la solucin del problema, y

stos fueron los resultados:

3

Aqu se puede ver que, el ptimo encontrado por Lingo nos indica que para que la empresa

petrolfera pueda maximizar sus utilidades, debe extraer y vender 7.5 millones de barriles

el primer ao y 5.8 millones el segundo ao.

Tambin, Objetive value nos indica que en el ptimo, la empresa obtendr una utilidad de

214.5833 millones de euros por sus ventas.

Adems, en la columna Slack or Surplus, que en espaol significa Holgura o Exceso, nos dice que la empresa se ahorr 125.6944 millones de euros en gastos operacionales, y

quedaron 6.6 millones de barriles sin extraer del mximo permitido.

Ahora bien, interpretando los costos reducidos, que se pueden definir como lo que

empeorar la funcin objetivo por cada unidad que aumente el trmino, independiente de la

restriccin, se puede ver claramente que son casi 0 para las 2 variables, por lo tanto, existe

un equilibrio entre costo y utilidad. No obstante, como stos son negativos, las variables

4

estn en millones y adems es un problema de maximizacin, aumentar la actividad (venta de

barriles) perjudicara a la funcin objetivo, es decir la utilidad de la empresa disminuira,

aunque no en gran medida.

Finalmente, el precio dual, que se entiende como lo que mejorar la funcin objetivo por cada

unidad que aumente el trmino, independiente de la restriccin, y, en nuestro caso significa que por cada milln de euros gastado (de la restriccin de costos), la utilidad de la empresa

aumentara 1x10e-7 y por cada milln de barril extrado, sta aumentara 3x10e-6 millones

de euros aproximadamente.

Luego, graficamos la funcin objetivo, para analizar e interpretar su comportamiento, primero

en MatLab:

La grfica en 3D con MatLab, nos proporcion una idea de cmo se comporta en general la

funcin de utilidad que se necesita maximizar, adems, tambin utilizamos la herramienta

WolframAlpha para hacernos una mejor idea de la forma y sus curvas de nivel.

5

Cabe destacar que la variables X1 e X2 son X e Y respectivamente.

La grfica result ser un paraboloide, con un mximo de 482.5, cuando X1 tiene el valor de

29.5 y X2 es igual a 16.5.

Todo esto, claro, sin las restricciones, pero nos hace la idea que la grfica de por si posee una

cota superior, por lo tanto, a medida que la empresa venda ms barriles, aumentar su

utilidad, pero slo hasta ese lmite, ya que luego sta comenzar a disminuir.

6

Resolucin con KKT

() = 1(30 1) + 2(35 2) 12 22

2

. 12 + 22

2 250

1 + 2 20

Funcin Lagrangiana

(1, 2) = ((1(30 1) + 2(35 2) 12 22

2) + 1(12 + 22

2 250)

+ 2(1 + 2 20))

Condiciones KKT

1= 30 41 + 211 + 2 = 0

2= 35 62 + 412 + 2 = 0

Condicin de factibilidad

(12 + 222 250) 0

(1 + 2 20) 0

Condicin de holgura

11() = 1(12 + 22

2 250) = 0

22() = 2(1 + 2 20) = 0

Condicin de signo

1, 2 0

1, 2 0

7

8

Problema 2 de KKT

Un comerciante puede comprar hasta 17.25 onzas de un producto qumico A a 10 dlares

cada onza. Se puede convertir una onza del producto qumico A en una onza del producto

I a un costo de 3 dlares a onza.

Asimismo, una onza del qumico A se puede convertir en una onza del producto II a un costo

de 5 dlares la onza. Si se producen x1 onzas del producto I se vender a 30 x1 dlares la

onza, mientras que si se producen x2 onzas del producto II se vender a 50x2 dlares la

onza. Determine cmo el comerciante puede maximizar sus ganancias.

Solucin:

Variables de Decisin

x1 = Onzas del producto I producidas

x2 = Onzas del producto II producidas

Objetivo

Lo que debe hacerse es maximizar las ganancias que se obtiene restando a las ventas los

costos, tanto de

Materia prima como de produccin:

Max z = x1 (30 x1) + x2 (50 x2) 3 x1 5 x2 10 (x1 + x2)

s.a.

x1 + x2 17.25

0 x1

0 x2

Nos olvidaremos de las restricciones de no-negatividad para la x1 y x2 y posteriormente

filtramos las soluciones encontradas.

As:

f = x1 (30 x1) + x2 (50 x2) 3 x1 5 x2 10 (x1 + x2)

g1 = x1 + x2 17.25 0

g2 = x1 0

g3 = x2 0

9

Las condiciones de KKT que debe satisfacer el optimo son:

Resolviendo el sistema anterior con Maple obtenemos los siguientes puntos. En la tabla se

tabula cada una delas restricciones evaluada en el punto correspondiente. Recuerde que las

s deben ser positivas y las restricciones deben cumplirse (gi 0):

Los puntos correspondientes a los renglones 1, 2, 3, 4 y 6 se cancelan pues tienen al

menos un negativo. El rengln 5 se cancela pues una de las restricciones no se cumple:

g1 debe ser 0. Por consiguiente, el nico punto sobreviviente es el del rengln 7: x1 = 4.125

y x2 = 13.125 con una evaluacin de 340.21875.

10

Anlisis.

En general, los mtodos que utilizamos para resolver los problemas presentados en este

informe fueron 2; las condiciones de Karush Kuhn Tucker que bsicamente es un modelo y

algoritmo matemtico el cual retorna la solucin ptima del problema y Lingo, Maple y Solver

de Excel, que son software completamente automatizado, al cual se le ingresa la funcin a

optimizar y las restricciones y entrega la solucin de una manera mucho ms rpida, eficiente

y segura.

Respecto a los problemas resueltos, cabe destacar que es muy importante conocer y saber

cmo aplicar la investigacin operativa a ste tipo de situaciones, ya que son muy

comunes en la realidad, y que, al analizar, interpretar y aplicar correctamente las

soluciones pueden resultar en una ayuda inmensa para el ptimo desarrollo del proceso

que se est llevando a cabo, como en el caso de la extraccin petrolfera, dnde mediante la

solucin, la empresa puede saber cunto exactamente extraer y vender de millones de barriles

en cada ao.

Aqu es donde se genera otra gran utilidad de saber aplicar estos mtodos eficientemente, y

es que, al obtener cada uno de los resultados a stos problemas, podemos generar una

previsin de lo que suceder si tomamos tales acciones o no, con cierta probabilidad

(ajustndose a la exactitud del modelo matemtico), lo que nos ayuda a tomar ms acertadas

y rpidas decisiones en el presente, para llegar a ese futuro que deseamos.

Conclusin.

Debido a que en este informe estudiamos 2 problemas de programacin no lineal, en donde

se utilizaron diversos mtodos para encontrar las soluciones a estos problemas, tales como el

teorema del KKT (Karush Kuhn Tucker) y los algoritmos de Lagrange, adems de utilizar

algunos mtodos matemticos que no pueden faltar para encontrar la solucin ms ptima.

Tambin se aprendi a utilizar un software que sirve para realizar los procedimientos ms

rpidos y automatizados, este software se llama Lingo, aunque igual se utilizaron otras

herramientas como Matlab y y WolframAlpha.

En conclusin luego de haber realizado todo el procedimiento correspondiente obtuvieron los

siguientes resultados:

Para el primer problema se resolvi con el programa de Lingo y con el mtodo de KKT y

aunque al principio se concluy que estaba errneo al comparar ambos resultados

observamos que eran los mismos resultados por consiguiente concluimos que este

problema se poda resolver con los dos mtodos.

Por otra parte con respecto al segundo problema que consista en buscar un problema del tipo

KKT se resolvi en Maple, donde luego se tabularon las restricciones evaluadas y se

conserv como solucin la que cumpla con todas estas restricciones. Por lo cual se obtuvieron

los siguientes resultados: x1 = 4.125 y x2 = 13.125 con una evaluacin de 340.21875.