Programación no lineal, investigación de operaciones avanzada

Investigacion de operaciones avanzada

1. Programación No
Lineal: Modelos no
restringidos.

2. Programación No Lineal
Losproblemasdeprogramaciónnolineal(PNL)sepresentanconfrecuenciaenlapráctica.Porejemplo:modelosde
producción,carterasdeinversionesriesgosas,modelosdeinventarios,etc.
Entérminossimplessepuedenclasificaren:
•Norestringidos:
Max/Min z = f(x)
-Dondef(x)esnolineal.
•Restringidos:
Max/Min z = f(x)
Sujeto a:
gj(x) ≤, =, ≥ bj
Para j = 1, 2,…, m
-Dondef(x)y/olasrestriccionesgj(x)sonnolineales.

3. Programación No Lineal
AligualqueenPL,laregiónfactibleparaelPNLrestringido,esunconjuntodepuntos(x1,x2,…,xn)quesatisfacen
lasmrestricciones.Porloqueunpuntoqueestáenlaregiónfactibleesunpuntofactible,yelpuntoquenoestá
enlaregiónfactibleesunpuntonofactible
Porlotanto,
•Paraunproblemademaximización,x*esunasoluciónóptimasiparatodoslospuntosfactiblesxsecumple
que:
f(x*)≥ f(x)
•Paraunproblemademinimización,x*esunasoluciónóptimasiparatodoslospuntosfactiblesxsecumple
que:
f(x*)≤ f(x)

4. Puntos Estacionarios
Lospuntosestacionariospuedenserunmínimo,unmáximoopuntodeinflexión(puntosilla).
Paraquef(x)tengapuntosestacionariossesuponequelaprimeraysegundaderivadasparcialesdef(x)son
continuaparatodaslasx.
00)(0 =
¶
¶
Û=Ñ
ix
f
xf
Seaf(x)unafuncióndenvariables,unacondiciónnecesariaparaqueelpuntox0seaunpuntoestacionariode
f(x),esque:
Algunasconcusiones…
•Debidoalasdiversasformasquepuedentomarlosproblemas
deprogramaciónnolinealesquesurgelasiguiente
complicación:unmáximolocalnonecesariamenteesun
máximoglobal.
•Engeneral,losalgoritmosdeprogramaciónnolinealno
puedendistinguirentreunmáximolocalymáximoglobal.
•Escrucialconocerlascondicionesenlasquesegarantizaque
unmáximolocalesunmáximoglobalenlaregiónfactible.

5. •f(x)esconvexasi,paracadapardepuntosdelagráficadef(x)elsegmentodelíneaquelosuneseencuentra
completamenteporencimadelagráfica.
•f(x)escóncavasi,paracadapardepuntosdelagráficadef(x)elsegmentodelíneaquelosuneseencuentra
completamentepordebajodelagráfica.
Funciones cóncavas y convexas de una variable

6. Funciones cóncavas y convexas de una variable
Condicióndeconcavidadyconvexidadenfuncionesdeunavariable.Considerandoque:!∈[0,1]
•()esunafunciónconvexasiparacualquierpardepuntos)!,)!!∈*:
(1−!)′+!)′′≤1−!()!+!()!!
•()esunafunciónestrictamenteconvexaenSsiparacualquierpardepuntos),0∈*
(1−!)′+!)′′<1−!()′+!(()′′)
•()esunafuncióncóncavaenSsiparacualquierpardepuntos),0∈*yparacualquier4∈[0,1]
(1−!)′+!)′′≥1−!()!+!(()′′)
•()esunafunciónestrictamentecóncavaenSsiparacualquierpardepuntos),0∈*
(1−!)′+!)′′>1−!()′+!(()′′)

7. •Lasumadedosfuncionesconvexasesunafunciónconvexaylasumadedosfuncionescóncavasesuna
funcióncóncava.
•Unafunciónpuedesernicóncavaniconvexayaseaporsumadefuncionescóncavasconconvexasopor
naturalezamultimodal.
•Unafunciónlinealesconvexaycóncavaalavez.
Funciones cóncavas y convexas de una variable

8. Pruebasdeconvexidadconf(x)deunavariable:
Considerecualquierfuncióndeunavariablef(x)quetieneunasegundaderivadaparatodoslosvaloresposiblesde
x.Entoncesf(x)es:
•Convexasiysolosi"!#(%)
"%!≥0paratodoslosvaloresposiblesdex.
•Estrictamenteconvexasiysolosi"!#(%)
"%!>0paratodoslosvaloresposiblesdex.
•Cóncavasiysolosi"!#(%)
"%!≤0paratodoslosvaloresposiblesdex.
•Estrictamentecóncavasiysolosi"!#(%)
"%!<0paratodoslosvaloresposiblesdex.

9. TEOREMA1:
•Considereunproblemadeprogramaciónnolinealdemaximización.Sif(x)escóncava,entoncescualquier
máximolocalparaelproblemaesunasoluciónóptima.
TEOREMA1’:
•Considereunproblemadeprogramaciónnolinealdeminimización.Sif(x)esconvexa,entoncescualquier
mínimolocalparaelproblemaesunasoluciónóptima.
TEOREMA1’’:
•Sif(x)noesconvexanicóncava,entoncessusmáximosomínimoslocalesnosepuedendefinircomo
óptimosglobales.
Optimización No Lineal

10. Enelcasodefuncionesdenvariables,lassegundasderivadasparcialespuedenemplearseparaelvaluarla
concavidadoconvexidaddefuncionesdevariasvariables.
Definición:LamatrizHessianaasociadaaunafunciónf(x)=(x1,x2,…,xn)esunamatrizcuadrada,Hnxn,talque
suselementoshijsondelaforma:
ℎ!"=##$
#%!#%"
PorEjemplo:Paraunafunciónf(x1,x2,x3)lamatrizHessianacorrespondientesería:
ú
ú
ú
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ê
ê
ê
ë
é
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
=
2
3
2
23
2
13
2
32
2
2
2
2
12
2
31
2
21
2
2
1
2
),,( 321
x
f
xx
f
xx
f
xx
f
x
f
xx
f
xx
f
xx
f
x
f
xxxH
Pruebasdeconvexidadconf(xn)denvariables:

11. Considerelasiguientedefiniciónparalosmenoresprincipalesdeunafuncióndemúltiplesvariables:
§Losk-ésimosmenoresprincipalesdeunamatrizdenxnsoneldeterminantedelamatrizkxk
obtenidaaleliminarlasn–kfilasylasn–kcolumnascorrespondientesdelamatriz
§Paracualquiermatriz,losprimerosmenoresprincipalessonloselementosdiagonalesdeH.
Entonces,elhessianoasociadoaunafunciónf(x1,x2,x3)detresvariables,tendrá:
1osmenoresprincipales(k=1)
2osmenoresprincipales(k=2)
3ermenorprincipal(k=3).
Prueba de Concavidad y Convexidad
ú
ú
ú
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ê
ê
ê
ë
é
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
=
2
3
2
23
2
13
2
32
2
2
2
2
12
2
31
2
21
2
2
1
2
),,( 321
x
f
xx
f
xx
f
xx
f
x
f
xx
f
xx
f
xx
f
x
f
xxxH

12. Programación no lineal
TEOREMA 2:
•Supongaquelafunciónf(x1,x2,…,xn)tienederivadasparcialescontinuasdesegundoordenpara
cualquierpuntox=(x1,x2,…,x3)∈S.Entoncesf(x1,x2,…,xn)esunafunciónconvexadeSsiysolosipara
cada%∈',losmenoresprincipalesdeHsonnonegativos.
•Siunpuntoesmínimolocal,debesermínimoglobal.

13. Programación no lineal
TEOREMA2’:
•Supongaquelafunciónf(x1,x2,…,xn)tienederivadasparcialescontinuasdesegundoordenpara
cualquierpuntox=(x1,x2,…,xn)∈S.Entoncesf(x1,x2,…,xn)esunafuncióncóncavaenSsiysolosipara
cada%∈'yk=1,2,…,n,losmenoresprincipalesdistintosdecero,tienenelmismosignoque(-1)k.
Con k = 1, 2,…, n
•Siunpuntoesmáximolocal,debesermáximoglobal.

14. Programación no lineal
TEOREMA2’’:
§Silosmenoresprincipalesdistintosdecero,nocumplenconlascondicionesdelteorema2ni2’.Nose
puedeaseguraroptimoglobal.

15. •Unamonopolistaqueproduceunsoloproductotienedostiposdeclientes.Siseproducen7'unidadesparael
cliente1,entonceselcliente1estádispuestoapagarunpreciode70−47'dólares.Siseproducen7(unidadesparaelcliente2,entonceselcliente2estadispuestoapagarunpreciode150−157(dólares.Para
7>0,elcostodefabricarqunidadeses100+15qdólares.Paramaximizarlaganancia,¿cuántodebevenderel
monopolistaacadacliente?
Solución:
(7',7(=7'70−47'+7(150−157(−100−157'−157(
A fin de encontrar los puntos estacionarios para (7',7(, se establece:
"#
")"=70−87'−15=0
"#
")!=150−307(−15=0
7'=55
8;7(=9
2
Ejemplo 1:

16. Así,elúnicopuntoestacionariode!"!,""$%##
$,%
".Acontinuaciónsedeterminalamatrizhessiana
para!"!,"":
'"!,""=−80
0−30
•PuestoquelosprimerosmenoresprincipalesdeHson−8<0.−30<0,yelsegundomenor
principaldeHes−8−30−0=240>0,elteorema2´muestraque##
$,%
"esunafunción
cóncava.Loqueimplicaque##
$,%
"maximizalasgananciasentretodaslasposibilidadesde
producción.
Entonces"!,""=##
$,%
"daunagananciade:
!"!,""=##
$70−""&
$+%
"150−15%
"−100−15##
$+%
"=$392.81
Ejemplo 1:

17. Otros candidatos a óptimos en PNL
Sea:
MaxoMin(())
S.a. )∈[G,4]
Hay3tiposdecandidatosaextremosdondeelproblemapuedetenerunmáximoomínimolocal.
üCandidatos tipo 1: Puntos donde (!)=0
üCandidatos tipo 2: Puntos donde (′())no existe.
üCandidatos tipo 3: Puntos finales G04del intervalo G,4.
Algunosposiblesescenarios:
•Si (!)*=0y (!!()*)<0, entonces )*es un máximo local.
•Si (!)*=0y (′!)*>0, entonces )*es un mínimo local.

18. Candidatostipo1:
Otros candidatos a óptimos en PNL

19. Candidatostipo2:
Ej:Descuentosporcantidad,cambiosdetecnología.
Otros candidatos a óptimos en PNL

20. Candidatostipo3:
Otros candidatos a óptimos en PNL

21. Ejemplo 2:
•Aunmonopolistalecuesta$5/unidadproducirunproducto,siproducexunidadesdelproducto,
entoncescadaunosepuedevenderen10–xdólares0≤9≤10.¿cuántodebeproducirel
monopolistaparamaximizarsuganancia?
Solución:
Sea P(x) la ganancia del monopolista si produce 9unidades. Entonces:
:;=;<=−;−>;=>;−;'=≤;≤<=
Así, el monopolista quiere resolver el siguiente PNL:
?@AB;
Sujeto a:
=≤;≤<=

22. Ejemplo 2:
Ahora se clasifican los candidatos extremos:
•Candidato tipo 1:I´)=5−2), I´)=0, se cumple para )=2,5. Debido a que I´´)=−2,)=2,5es un
máximo local que produce una ganancia de I2,5=6.25.
•Candidato tipo 2: I!)existe para los puntos [0, 10], así que no hay candidatos de tipo 2
•Candidato tipo 3: G=0tieneI´0=5>0, de modo que G=0es un mínimo local; 4=10tiene I´10=
−15<0, entonces 4=10es un mínimo local.
Porlotanto,)=2,5eselúnicomáximolocal.Estosignificaquelasgananciasdelmonopolistasemaximizanalelegir
)=2,5.
ObservequeG’’=-2paratodoslosvaloresdex.EstomuestraqueG(x)esunafuncióncóncava.Cualquiermáximo
localparaG(x)debeserlasoluciónóptimaparaelPNL.Así,elteorema1implicaqueunavezdeterminadoquela
solución)=2,5esunmáximolocal,sesabequeeslasoluciónóptimaparaPNL.

23. Funciones por tramos
LasfuncionesportramamospresentanlosmencionadosCandidatostipo2.Estosproblemaspuedensurgirenla
prácticacuandoenlosprocesosproductivossepresentan,porejemplo:
•Economías de escala:Hasta cierto punto se puede disminuir el costo por unidad producida, a medida que se
aumenta el volumen de producción.
•Poder de negociación:Las empresas grandes suelen tener mayor poder de negociación con proveedores, lo que
les permite obtener mejores precios y mejores márgenes.
•Costos de mantenimiento:Si se supera una cierta capacidad de producción, es necesario realizar un
mantenimiento más frecuente de las máquinas, lo que incrementa los costos.
•Costos de energía:El costo de la energía puede variar según el horario en que se produce.

24. Ejemplo 3
Unaempresadeproduccióndeenergíarenovableestáexperimentandoconunnuevotipodepanelsolar.La
eficienciadeestospanelesvaríasegúnlaintensidaddelaluzsolaralolargodeldía.Sehadesarrolladounmodelo
matemáticoparaestimarlaproduccióndeenergíaporhora,elcualserepresentamediantelasiguientefunción
portramos:
Donde:
•x representa las horas transcurridas desde el amanecer (0 ≤ x ≤ 6).
•f(x) representa la producción de energía en megawattspor hora.
Sea:
()=2−)−1(LGMG0≤)<3
()=−3+)−4(LGMG3≤)≤6
Encuentre:
max(())
s.a. 0≤)≤6

25. Ejemplo 3
En búsqueda de la solución:
Candidatostipo1:
•Para0≤)<3,(´)=−2)−10(´´)=−2.(´)=0,secumplepara)=1.Como(´´1<0,)=1
esunmáximolocal.
•Para3<)≤6,(´)=2)−40(´´)=2.(´)=0,secumplepara)=4.Como(´´4>0,)=4es
unmínimolocal.
•Candidatotipo2:Delafigura,seveque(())notienederivadaen)=3.Evaluandoenf(x)tenemosque
(2.9=−1.61,(3=−2,0(3.1=−2.19.Porlotanto,)=3noesunextremolocal.
•Alternativamentesepuedeverqueparaxligeramentemenorque3,(´)estácercade-4,yparaxunpoco
mayorque3,(´())estácercade-2.Porlotanto,)=3noesunextremolocal.

26. Ejemplo 3
•Candidato tipo 3:Debido a que (´0=2>0,)=0es un mínimo local.
•Debido a que (!6=4>0,)=6es un máximo local.
•Porlotanto,en[0,6],()tieneunmáximolocalpara)=10)=6.Debidoaque(1=2y(6=1,se
encuentraquelasoluciónóptimaparaelPNLocurrepara)=1.

27. Programación No
Lineal: Modelos no
restringidos.