tema_08

Tema 8. Programacin lineal y mtodos de op7mizacin

Estads7ca

Mara Dolores Fras Domnguez Jess Fernndez Fernndez

Carmen Mara Sordo

Departamento de Matem.ca Aplicada y Ciencias de la Computacin

Este tema se publica bajo Licencia: Crea.ve Commons BY-NC-SA 3.0

Esta unidad est basada en material elaborado por ngel Cobo Ortega, Universidad de Cantabria

MaraDoloresFras,JessFernndezyCarmenMaraSordo

TEMA8:Programacinlinealymtodosdeoptimizacin

EstematerialestbasadoenmaterialelaboradoporngelCoboOrtega,UniversidaddeCantabria

Introduccinalaoptimizacin

Problemasdeoptimizacin

Elvectorgradiente.Anlisisgeomtrico.

Programacinlineal Caractersticas Resolucingeomtrica Resolucinmediantesoftwareespecializado:LINGO


Objetivosdeltema Reconocerlaimportanciadelaoptimizacinenlosdistintoscamposdelaingeniera.

Identificar las componentes principales de unproblemadeoptimizacin.

Analizar el caso particular de la programacinlineal.

Saber utilizar software de apoyo a la toma dedecisiones.


OptimizacinenlaingenieraIngeniera:

Crear sistemas de ingeniera competitivos no slo entrminos de funcionamiento sino tambin en trminos deproductividad,servicio,ciclodevida,...

Necesidades: Uso de metodologas de diseo rigurosas y de carcter

cuantitativo que puedan complementar a la intuicin y lafacetacreativanocuantitativadelprocesodediseo.

OPTIMIZACIN:Bsquedadelamejorsolucinaunproblemadado.

Minimizacinymaximizacin Ejemplos:Problemasdelocalizacin,asignacin,confeccin

decalendarios,rutasdevehculos,


Metodologa

Desarrollodeunmodelomatemtico

Definicindelproblema

Resolucindelmodelomatemtico

Implementacin:Tomadedecisiones

Validacindelasolucin

Algoritmosexactos:producenlasolucinexactadelproblema Algoritmos aproximados: producen la solucin aproximadad del

problemamediantealgnprocesoiterativo. Heursticas:obtienenbuenassolucionesentiemposrazonables.



Minimizarcostes,tiempodeproduccin,riesgodela

inversin,plazodeentrega,...

Maximizarlosbeneficios,niveldeventas,satisfaccindelcliente,resistenciadelos

materiales,...

- f ( x )

f ( x )

Dp u n t om x i m o

v a l o rm x i m o

D

p u n t om n i m o

v a l o rm n i m o

Elpuntoenelqueunafuncinalcanzasumximoesel

mismoenelquesufuncinopuesta

alcanzaelmnimo,siendolosvaloresptimosrespectivos

opuestos.

Programasmatemticos

Ambosproblemassonenelfondoequivalentes:Maxf(x)=Min(f(x))


Elementosdetodoproblemaoptimizacin

Variablesdedecisinx=(x1,x

2,...,x

n)

Variablesreales,enteras,binariasobooleanas

Funcinobjetivof(x)=f(x1,x

2,...,x

n)

Regin factible o espacio de soluciones factiblesdelimitadoporlasrestricciones:DconjuntoenRn

La programacin matemtica consiste por tanto en el clculo demximosymnimosde funcionesdevariasvariablessometidasaunconjuntoderestricciones.


Restricciones Lasrestriccionesdelimitanlareginfactible.

Escasezderecursos,limitacionestecnolgicas,restriccionesdediseo

Tiposderestricciones Problemasnorestringidos Restriccionesdeigualdad

h(x)=0

Lagrange

Restriccionesdedesigualdad g(x)0

aixibi KarushKuhnTucker

Programacinlineal

Optimizacinclsica

Programacinmatemtica


RestriccionesEjemplo


RestriccionesEjemplo

pi:nmerodebarriles

producidosenelprocesoi


TcnicasclsicasdeoptimizacinAnlisisdecondicionesdeoptimalidad:

Condiciones necesarias: Permiten seleccionar los posiblesmximos y mnimos, (pueden existir puntos que las verifican sin sermximosomnimos).

Condicionessuficientes:Permiten asegurar con total certezaquesehaencontradounextremo.

Lamayora de las tcnicas estn basadas en elclculodiferencial:

Noaplicablesamuchostiposdeproblemas Dificultad de obtencin de soluciones exactas enmuchoscasos Mtodosnumricos

Problemticadelosptimoslocales


Espreferibleunptimoglobalaunolocal,perodesgraciadamente,lamayoradelastcnicasdeoptimizacinlocalizanptimoslocales

ytienendificultadesparareconocerlaglobalidad.

x0

f(x0)

mnimo local estricto

valor mnimo

local

x0

mnimo local no estricto

x0

mnimo global estricto

valor mnimo global

Elproblemadelosptimoslocales


Cond.deoptimalidadconf.diferenciables

Condicionesnecesarias: Problemassinrestricciones:

Todoptimotieneasociadounvectorgradientenulo

Problemasrestringidos:

Condicionessuficientes: Clasificacindematrizhessianas


Candidatoaptimo

Lamatrizhessianaesdef.pos.,porloqueelpuntoesunmnimo.

Ejemplo


Candidatoaptimo

Lamatrizhessianaesdef.pos.,porloqueelpuntoesunmnimo.

f=inline('2*x.^2+y.^2+2*x.*y+xy+2')dens=50;x=y=linspace(5,5,dens);[xx,yy]=meshgrid(x,y);zz=f(xx,yy);surf(xx,yy,zz,'EdgeColor','none');xlabel('x');ylabel('y')holdoncontour3(xx,yy,zz,'w')scatter3(1,3/2,f(1,3/2),'w')

Matlabtip

Ejemplo


Ejemplo

Candidatoaptimo

Lamatrizhessianaesdefinidapositivaparatodo(x,y)y,porloqueelpuntoesunmnimo.

Siaadimosunarestriccin


AnlisisgeomtricoEncasosmuysencillos ydepocasdimensiones(1 2), se puede resolver el problema deoptimizacindeformagrfica.

Representandolareginfactible Representando las curvas de nivel y el vectorgradiente.

Localizandoelptimodentro(oenlosbordes)delareginfactible.


-1 -0.5 0 0.5 1

-1

-0.5

0

0.5

1Los vectores gradientes son ortogonalescon lascurvasdenivel (curvas f(x,y)=cte, quepermitenrepresentarfuncionesdedosvariablesenelplano).

Siempre sealan sobre el dominio ladireccin dems rpido crecimiento de lafuncin.

"Huyen" de los mnimos y se sienten"atrados"porlosmximos.

Elpapeldelvectorgradiente


Ejemplo

Elpapeldelvectorgradiente

Ejercicio


Introduccinalaoptimizacin


Elvectorgradiente.Anlisisgeomtrico.

Programacinlineal Caractersticas Resolucingeomtrica Resolucinmediantesoftwareespecializado:LINGO

Contenidos


ProgramacinLinealLa programacin lineal es instrumento habitual enempresas.

UnadelasramasdelaOptimizacinmsdesarrolladayconmayornmerodeaplicacionesprcticas

Orgenesdelaprogramacinlineal: Economistas de la URSS: modelos lineales paraaumentar la eficiencia en la organizacin yplanificacindelaproduccin

Segunda Guerra Mundial: Proyecto SCOOP(ScientificComputationofOptimalPrograms)

Dantzig:mtodoSimplexhttp://www.ormstoday.org/orms1207/history.html


Programaslineales

Caractersticas: Todoptimoesglobal. Lascondicionesnecesariasdeprimerordensonsuficientes. Si hay dos soluciones distintas, tambin lo es cualquier

combinacinlinealconvexa.

Funcin objetivo

Restricciones lineales


Programaslineales

Ventajas: Fcilesdedefiniryformular. Se trabajade formaeficiente conunnmeroelevadodevariables

dedecisin. Se adaptan mejor al tratamiento algortmico con computadores

(rpidezdeclculo).

Funcin objetivo

Restricciones lineales


Anlisisgeomtrico

El espacio D de soluciones factibles es un poltopo con un nmero finito de vrtices. Es recomendable que sea acotado para garantizar la existencia de un ptimo.

En programacin lineal habitualmente no se consideran restricciones estrictas

20 40 60 80 100

20

40

60

80

100

A

B

C

D


Casoa=20,b=60

20 40 60 80 100

20

40

60

80

100

A

B

C

D

Elgradientemarcaladireccinde crecimiento, y por tanto debsquedadelmximo

ElmximosealcanzaenelvrticeA=(0,80)

Valormximodelafuncinf(0,80)=4800


Casoa=30,b=60

El mximo se alcanza en los vrtices A=(0,80) y B=(40,60) y en todos lospuntosqueestnentodoelladoquedeterminan.

Elvalordelafuncinentodoselloses4800

Elproblematieneportantoinfinitassoluciones

20 40 60 80 100

20

40

60

80

100

A

B

C

D


Casoa=50,b=60

ElmximosealcanzaenelvrticeB=(40,60)

Valormximodelafuncinf(40,60)=5600

20 40 60 80 100

20

40

60

80

100

A

B

C

D


Deduccin de propiedades: Todo ptimo es global y siempre se alcanza en la frontera de D

(alguna restriccin se satura). Si existe ptimo, ste se alcanza, al menos, en un vrtice de D. Si varios puntos son ptimos, tambin lo es cualquier

combinacin lineal convexa.

Resolucin: Localizar los vrtices de D. Calcular la funcin objetivo sobre todos los vrtices Elegir aqul sobre el que la funcin alcance el menor o el mayor

valor.

Anlisisgeomtrico

Noaconsejableparaproblemasdegrandesdimensiones.

Ejercicio


Formulacinestndardeprogramaslineales:

Objetivo: encontrar el vrtice ptimo sin tener que calcularlos todos.

MtodoSimplex

Separtedeunvrticeinicial. Sinoesptimo,encontrarunvrtice

adyacentequedisminuyaelvalordelafuncinobjetivooque,porlomenos,noaumente.

Repetirelprocesohastaencontrarunvrticequenopuedasermejorado.

Vrticeinicial

D

Vrticeptimo


ElproblemadeltransporteUnaempresadisponedemfbricasparaproducirunnicoproductoquehadedistribuirseanmercadosdiferentes,siendoCijelcoste,porunidaddeproducto,desdelafbricaFialmercadoMj

Fbricas Mercados

F1C11

Cmn

M1

F2

Fm

M2

Mn

Objetivosdelaempresa:1.Disearpolticadesuministrosqueminimicecostesdetransporte(cij).2.Nosobrepasarloslmitesdeproduccindecadaunadesusfbricas(pi).3.Atenderlademandadecadaunodelosmercados(dj).


ElproblemadeltransporteUnaempresadisponedemfbricasparaproducirunnicoproductoquehadedistribuirseanmercadosdiferentes,siendoCijelcoste,porunidaddeproducto,desdelafbricaFialmercadoMj.

Fbricas Mercados

F1C11

Cmn

M1

F2

Fm

M2

Mn

Variablesdedecisin:unidadestransportadasdesdecadafbricaacadamercado(xij)

Funcinobjetivo:minimizarelcostetotaldeltransporteRestricciones:Atenderlademandadecadamercado(dj)

Nosobrepasarlascapacidadesdeproduccindecadafbrica(pi)


Unaempresamultinacionaldedicadaa la fabricacindeelectrodomsticosrecibeunpedidode8.000hornosy12.000cocinas.

Para hacer frente al pedido en un plazo de un mes debe producir loselectrodomsticosencuatrofbricasdiferentes.

El objetivo que se plantea la empresa es la planificacin ptima de laproduccindelpedido.

Fbrica 1 Fbrica 2 Fbrica 3 Fbrica 4

Capacidad de produccin mensual de hornos

0 5000 7000 3000

Capacidad de produccin mensual de cocinas

4000 6000 0 8000

Coste de produccin por unidad de horno

- 25 30 20

Coste de produccin por unidad de cocina

20 20 - 25

Coste por unidad de electrodomstico del envo hasta el destino

10 13 12 9

EjemploElproblemadeltransporte


Planteamientodelproblema

FUNCINOBJETIVO(COSTESTOTALES):

Prod=20X1C+25X2H+20X2C+30X3H+20X4H+25X4CTrans=10X1C+13(X2H+X2C)+12X3H+9(X4H+X4C)COSTETOTAL=30X1C+38X2H+33X2C+42X3H+29X4H+34X4CLIMITACIONESORESTRICCIONES:

Capacidadesdeproduccinencadafbrica:X1C


Resolucindeprogramaslinealesconsoftwaredeinvestigacinoperativa

UsodelprogramaLingohttp://www.lindo.com


ResolucindelproblemaanteriorconunsoftwaredeInvestigacinoperativa:Lingo

(http://www.lindo.com)

Lingo es un software especfico para resolver problemas de optimizacin, tanto lineales como no lineales

Ejemplo


Optimal solution found at step: 2 Objective value: 663000.0 Variable Value Reduced CostX1C 4000.000 0.0000000E+00X2H 5000.000 0.0000000E+00X2C 6000.000 0.0000000E+00X3H 0.00000E+00 4.000000X4H 3000.000 0.0000000E+00X4C 2000.000 0.0000000E+00 Row Slack or Surplus Dual Price1 663000.0 1.000000R1 0.0000000E+00 4.000000R2 0.0000000E+00 0.0000000E+00R3 0.0000000E+00 1.000000R4 7000.000 0.0000000E+00R5 0.0000000E+00 9.000000R6 6000.000 0.0000000E+00PEDIDO_HORNOS 0.0000000E+00 -38.00000PEDIDO_COCINAS 0.0000000E+00 -34.00000

Valor ptimo

Valores de las

variables de

decisin

Costes reducidos: indican la

modificacin a aplicar a los

coeficientes de la funcin objetivo

para que la variable pase a ser no nula

Holguras en las restricciones

Precios duales: miden la

sensibilidad del valor ptimo ante

cambios en los trminos de la derecha de las restricciones

Solucin:

Ejemplo

PROGRAMACIN LINEAL Y MTODOS DE OPTIMIZACINObjetivos del temaOptimizacin en la ingenieraMetodologaProblemas de optimizacinElementos de todo problema de optimizacinRestriccionesSlide 8Slide 9Tcnicas clsicas de optimizacinSlide 11Condiciones de optimalidad con funciones diferenciablesEjemploSlide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Programacin LinealProgramas linealesSlide 23Anlisis detallado de un programa lineal con 2 variablesCaso a=20, b=60Slide 26Slide 27Anlisis grfico de los problemas linealesSlide 29Mtodo SimplexEl problema del transporteSlide 32Slide 33Slide 34Slide 35Slide 36Slide 37

Documents

tema_08