IO-Clase 2
9
Modelo de programación Lineal con dos variables En esta sección se explica la solución gráfica de una programación lineal con dos variables. Aunque en la práctica casi no existen problemas con dos variables, la presentación aportará ideas concretas para el desarrollo del algoritmo de solución general que se presentará más adelante. Reddy Mikks produce pinturas para interiores y exteriores, M1 y M2. La tabla siguiente proporciona los datos básicos del problema. Ton de materia prima de Pinturas para exteriores Pinturas para Interiores Disponibilidad máxima (ton) Materia Prima, M1 6 4 24 Materia Prima, M2 1 2 6 Unidades por ton (miles de $) 5 4 Una encuesta de mercado indica que la demanda diaria de pintura para interiores no puede ser mayor que 1 tonelada más que la de pintura para exteriores. También, que la demanda máxima diaria de pintura para interiores es de 2 toneladas. Reddy Mikks desea determinar la mezcla óptima (la mejor) de productos para exteriores y para interiores que maximice la utilidad diaria total. El modelo de programación lineal, como en cualquier modelo de investigación de operaciones, tiene tres componentes básicos: 1. Las variables de decisión que se trata de determinar. 2. El objetivo (la meta) que se trata de optimizar. 3. Las restricciones que se deben satisfacer. La definición correcta de las variables de decisión es un primer paso esencial en el desarrollo del modelo. Una vez hecha, la tarea de construir la función objetivo y las restricciones se hace en forma más directa. Para el problema de Reddy Mikks, se necesita determinar las cantidades a producir de pinturas para exteriores e interiores. Así, las variables del modelo se definen como sigue: x 1 = Toneladas producidas diariamente, de pintura para exteriores x 2 = Toneladas producidas diariamente, de pintura para interiores Para formar la función objetivo, la empresa desea aumentar sus utilidades todo lo posible. Si z representa la utilidad diaria total (en miles de dólares), el objetivo de la empresa se expresa así: Maximizar z = 5x 1 + 4x 2 A continuación se definen las restricciones que limitan el uso de las materias primas y la demanda. Las restricciones en materias primas se expresan verbalmente como sigue: (Uso de una materia prima para ambas pinturas b) ≤ (Disponibilidad máxima de materia prima) Según los datos del problema, Uso de la materia prima M1, por día ൌ 6x 1 4x 2 toneladas Uso de la materia prima M2, por día = 1x 1 + 2x 2 toneladas Ya que la disponibilidad de las materias primas M1 y M2 se limita a 24 y 6 toneladas, respectivamente, las restricciones correspondientes se expresan como sigue: 6x 1 + 4x 2 24 (Materia prima M1) Clase 2 martes, 5 de febrero de 2013 09:24 a.m. Página 1
description
INVESTIGACIÓN DE OPERACIONES
Transcript of IO-Clase 2
-
ModelodeprogramacinLinealcondosvariables
Enestaseccinseexplicalasolucingrficadeunaprogramacinlinealcondosvariables.Aunqueenlaprcticacasinoexistenproblemascondosvariables,lapresentacinaportarideasconcretasparaeldesarrollodelalgoritmodesolucingeneralquesepresentarmsadelante.
ReddyMikksproducepinturasparainterioresyexteriores,M1yM2.Latablasiguienteproporcionalosdatosbsicosdelproblema.
TondemateriaprimadePinturasparaexteriores
PinturasparaInteriores
Disponibilidadmxima(ton)
MateriaPrima,M1 6 4 24
MateriaPrima,M2 1 2 6
Unidadesporton(milesde$) 5 4
Unaencuestademercadoindicaquelademandadiariadepinturaparainterioresnopuedesermayorque1toneladamsqueladepinturaparaexteriores.Tambin,quelademandamximadiariadepinturaparainterioresesde2toneladas.ReddyMikksdeseadeterminarlamezclaptima(lamejor)deproductosparaexterioresyparainterioresquemaximicelautilidaddiariatotal.Elmodelodeprogramacinlineal,comoencualquiermodelodeinvestigacindeoperaciones,tienetrescomponentesbsicos:1.Lasvariablesdedecisinquesetratadedeterminar.2.Elobjetivo(lameta)quesetratadeoptimizar.3.Lasrestriccionesquesedebensatisfacer.
Ladefinicincorrectadelasvariablesdedecisinesunprimerpasoesencialeneldesarrollodelmodelo.Unavezhecha,latareadeconstruirlafuncinobjetivoylasrestriccionessehaceenformamsdirecta.ParaelproblemadeReddyMikks,senecesitadeterminarlascantidadesaproducirdepinturasparaexterioreseinteriores.As,lasvariablesdelmodelosedefinencomosigue:x1 =Toneladasproducidasdiariamente,depinturaparaexterioresx2 =Toneladasproducidasdiariamente,depinturaparainterioresParaformarlafuncinobjetivo,laempresadeseaaumentarsusutilidadestodoloposible.Sizrepresentalautilidaddiariatotal(enmilesdedlares),elobjetivodelaempresaseexpresaas:
Maximizarz=5x1 +4x2
Acontinuacinsedefinenlasrestriccionesquelimitanelusodelasmateriasprimasylademanda.Lasrestriccionesenmateriasprimasseexpresanverbalmentecomosigue:
(Usodeunamateriaprimaparaambaspinturasb) (Disponibilidadmximademateriaprima)
Segnlosdatosdelproblema,
Uso de la materia prima M1,por da 6x1 4x2 toneladasUsodelamateriaprimaM2,porda=1x1 +2x2 toneladas
YaqueladisponibilidaddelasmateriasprimasM1yM2selimitaa24y6toneladas,respectivamente,lasrestriccionescorrespondientesseexpresancomosigue:
6x1 +4x2 24(MateriaprimaM1)
Clase2martes,5defebrerode2013 09:24a.m.
Pgina 1
-
x1 +2x2 6(MateriaprimaM2)
Laprimerarestriccindelademandaindicaqueladiferenciaentrelaproduccindiariadepinturasparainterioresyexteriores,x2x1 ,nodebesermayorque1tonelada,yesosetraduceen 1.Lasegundarestriccindelademandaestipulaquelademandamximadiariadepinturaparainterioresselimitaa2toneladas,yesosetraducecomox2 2.Unarestriccinimplcita(oquesesobreentiende)esquelasvariablesx1 yx2 nopuedenasumirvaloresnegativos.Lasrestriccionesdenonegatividad,x1 0,x2 0,expresaneserequisito.
ResumiendoelmodelodeReddyMikks:
F.O.Maximizarz=5x1+4x2
Sujetaa:
6x1+4x2 24x1+2x2 6x1+x2 1x2 2x1,x2 0
Cualquiervalordey quesatisfagatodaslasrestriccionesdelmodeloesunasolucinfactible.Porejemplo,lasolucinx1=3toneladasdiariasyx2=1toneladadiariaesfactible,porquenoviolaalgunadelasrestricciones,incluyendolasdenonegatividad.
Enesteejemplo,lasfuncionesobjetivoytodaslasrestriccionessonlineales.Lalinealidadimplicaquelaprogramacinlinealdebesatisfacerdospropiedades:proporcionalidad yaditividad.
1.Laproporcionalidad requierequelacontribucindecadavariablededecisinenlafuncinobjetivo,ysusrequerimientosenlasrestricciones,seadirectamenteproporcionalalvalordelavariable.Porejemplo,enelmodelodeReddyMikks,lascantidades5x1y4x2expresanlasutilidadesporproducirx1yx2toneladasdepinturaparaexterioresyparainteriores,respectivamente,ylasutilidadesunitariasportoneladason5y4,quedefinenlasconstantesdeproporcionalidad.Si,porotraparte,ReddyMikksofrecealgunaclasededescuentosporcantidadcuandolasventassonmayoresqueciertascantidades,lautilidadyanoserproporcionalalascantidadesproducidasx1yx2.
2.Laaditividad estipulaquelacontribucintotaldetodaslasvariablesenlafuncinobjetivoysusrequerimientosenlasrestricciones,seanlasumadirectadelascontribucionesorequerimientosindividualesdecadavariable.EnelmodelodeReddyMikks,lautilidadtotalesigualalasumadedoscomponentesindividualesdeutilidad.Sinembargo,silosdosproductoscompitenporlamismapartedemercadoenformatalqueunaumentodeventasdeunoafectenegativamentealotro,yanosesatisfacelapropiedaddeaditividad.
Pasosparalasolucindeunmodelodemaximizacin(MtodoGrficohttp://bit.ly/WMDIAO )
Primero,setendrnencuentalasrestriccionesdenonegatividadx1 0 yx2 0(ejeshorizonatalyvertical.Paratenerencuentalasotrascuatrorestricciones,primerosesustituyecadadesigualdadconunaecuacin,yacontinuacinsegraficalarectaresultante,ubicandodospuntosdiferentesdeella.
Acontinuacinconsideraremoselefectodeladesigualdad.Todoloquehaceladesigualdadesdividiralplano(x1,x2)endossemiespaciosqueenestecasosonsemiplanos,unoacadaladodelalneagraficada.Slounadeesasdosmitadessatisfaceladesigualdad.
Paradeterminarculeselladocorrecto,seeligecualquierpuntodereferenciaenelprimercuadrante.Sisatisfaceladesigualdad,elladoenelqueesteselsemiplanofactible.Encasocontrario,quieredecirqueeselotrolado.
Paso1.Determinacindelespaciodesolucionesfactibles:
/
Pgina 2
-
Elespaciofactibledelafigura2.1estdelimitadoporlossegmentosderectaqueunenalosvrticesA,B,C,D,EyF.TodopuntodentrooenlafronteradelespacioABCDEFesfactible,porquesatisfacetodaslasrestricciones.YaqueelespaciofactibleABCDEFestformadoporunacantidadinfinitadepuntos,esobvioquesenecesitaunprocedimientosistemticoparaidentificarlasolucinptima.
Paraidentificarlasolucinptimaserequiereidentificarladireccinenlaqueaumentalafuncinutilidad 54 (Seestmaximizandoz).Parahacerloseasignanvaloresarbitrarioscrecientesaz.Porejemplo,siz=10yz=15,equivaleagraficarlasrectas5 4 10 y5 4 15
Paso2.Determinacindelasolucinptima:
Pgina 3
-
Alanalizarlagrficaresultante,sepuedeobservarqueelpuntoCofrecelasolucinptima,pueseselpuntoenelespaciodesolucionesfactiblesquelimitalafuncinz,(cuandoz=21),puescualquiervalordezmayoralpuntoC,seencuentrafueradelasfronteras.
6x1+4x2=24x1+2x2=6
Porlotanto,paraencontrarelpuntoC,seresuelvenlasdosecuacionesasociadasalasrectas1y2esdecir:
Lasolucinnosdaquex1=3yx2=1.5yportanto,z=5(3)+4(1.5)=21($21,000).
Noesporaccidentequelasolucinptimaseencuentreenunpuntodeesquinadelespaciodesoluciones,dondesecruzandoslneas.Enrealidad,sisecambialapendientedelafuncinutilidadz(cambiandosuscoeficientes),severquelasolucinptimasiempreseencuentraenesospuntosdeesquina.Estaobservacinesclaveparadesarrollarelalgoritmosmplex
Solucindeunmodelodeminimizacin(MtodoGrfico)
Ejemplo2.22(Problemadeladieta)EnGranjasModelo seusadiariamenteunmnimode800libras(lb)deunalimentoespecial,queesunamezclademazysoya,conlascomposicionessiguientes:
Lasnecesidadesdietticasdelalimentoespecialsonunmnimode30%deprotenasyunmximode5%defibras.GranjasModelodeseadeterminarlasproporcionesdealimentoqueproduzcanuncostodiariomnimo.Comolamezcladealimentosconsisteenmazysoya,lasvariablesdedecisindelmodelosedefinencomosigue:
x1 =lbdemazenlamezcladiariax2 =lbdesoyaenlamezcladiaria
Lafuncinobjetivotratademinimizarelcosto(endlares)diariototaldelamezcladealimentos,yenconsecuenciaseexpresacomosigue:minimizarz=0.3x1 +0.9x2 Lasrestriccionesdelmodeloreflejanlacantidaddiarianecesariaylosrequerimientosdietticos.ComoGranjasModelonecesitaunmnimode800lbdiariasdealimento,larestriccincorrespondientesepuedeexpresarcomosigue:
x1 +x2 800
Encuantoalarestriccindietticadenecesidadesdeprotena,lacantidaddeprotenaquecontienenx1 lbdemazyx2 lbdesoyaes(0.09x1 +0.6x2)lb.Estacantidaddebesercuandomenosigualal30%delamezclatotaldealimentos,(x1 +x2)lb;estoes:0.09x1 +0.6x2 0.3(x1 +x2).
Demanerasimilar,larestriccindelafibrasedefinecomo
0.02x1 +0.06x2 0.05(x1 +x2)
Lasrestriccionessesimplificanagrupandotodoslostrminosenx1 yx2 ypasndolosalladoizquierdodecadadesigualdad,paraquesloquedeunaconstanteenelladoderecho.As,elmodelocompletovieneaser:
Pgina 4
-
minimizar z=0.3x1 +0.9x2
x1 +x2 8000.21x1 0.30x2 00.03x1 0.01x2 0x1,x2 0
sujetaa
Yaqueenestemodelosebuscaminimizarlafuncinobjetivo,necesitamosreducirtodoloposibleelvalordez,enladireccinquemuestralafigura2.3.Lasolucinptimaeslainterseccindelasdosrectas,x1 +x2 =800y0.21x1 0.3x2 = 0;asseobtienenx1 =470.6lbyx2 =329.4lb.Elcostomnimocorrespondiente,delamezcladealimentos,esz=0.3(470.6)+0.9(329.4)=$437.64diarios.
MtodoSimplex(http://bit.ly/TFNbd2 ,http://bit.ly/YRjp87 )Elmtodogrficoindicaquelasolucinptimadeunprogramalinealsiempreestasociadaconunpuntoesquinadelespaciodesoluciones.Esteresultadoeslaclavedelmtodosmplexalgebraicoygeneralpararesolvercualquiermodelodeprogramacinlineal.
Inicialmentehayqueconvertirtodaslasrestriccionesdedesigualdadenecuaciones,paradespusmanipularesasecuacionesenunaformasistemtica.
Unapropiedadgeneraldelmtodosmplexesqueresuelvelaprogramacinlinealeniteraciones.Cadaiteracindesplazalasolucinaunnuevopuntoesquinaquetienepotencialdemejorarelvalordelafuncinobjetivo.Elprocesoterminacuandoyanosepuedenobtenermejoras.
Cuandousarvariablesdeholgura:Enlasrestricciones( ):elladoderechosepuedeimaginarcomorepresentandoellmitededisponibilidaddeunrecurso,yenesecasoelladoizquierdorepresentaraelusodeeserecurso.Ladiferenciaentreelladoderechoyelladoizquierdode larestriccinrepresenta,porconsiguiente,lacantidadnousadauholguradelrecurso.
Pgina 5
-
6x1 +4x2 24
Paraconvertirunadesigualdad( )enecuacin,seagregaunavariabledeholguraalladoizquierdodelarestriccin.Porejemplo,enelmodelodeReddyMikks(Ejemplo2.11),larestriccinasociadaconelusodelamateriaprimaM1estdadacomo
6x1 +4x2 +s1 =24,s1 0Sisedefines1comolaholgura,ocantidadnousada,deM1,larestriccinsepuedeconvertirenlasiguienteecuacin:
Cuandousarvariablesdeexcedencia:
Enlasrestricciones( )lacantidadporlaqueelladoizquierdoesmayorqueellmitemnimo(ladoderecho)representaunexcedente.Laconversinde( )a(=)selograrestandounavariabledeexcedencia,delladoizquierdo
x1 +x2 800
deladesigualdad.Porejemplo,enelmodelodeladieta(Ejemplo2.22),larestriccinquerepresentalosrequisitosmnimosdealimentoestdadacomo
x1 +x2 S1 =800,S1 0SisedefineaS1comounavariabledeexcedenciasepuedeconvertirlarestriccinenlaecuacinsiguiente:
x1 +x2 3 x1 +x2 +s1 =3,s1 0
Elnicorequisitoquequedaesqueelladoderechodelaecuacinqueresulteseanonegativo.Estacondicinsepuedesatisfacersiempre,siesnecesariomultiplicandoambosladosdelaecuacinresultantepor1.Porejemplo,larestriccin
x1 x2 s1 =3Ahorasemultiplicanambosladospor1,yseobtieneunladoderechononegativo,queeslo quesebusca;estoes,
Algoritmo(p.83)
Maximizarz=5x1 +4x2 +0s1 +0s2 +0s3 +0s4
UsaremoselmodelodeReddyMikks(Ejemplo2.11)paraexplicarlosdetallesdelmtodosmplex.Elproblemaseexpresaenformadeecuacionescomosigue:
6x1 +4x2 +s1=24(materiaprimaM1)x1 +2x2+s2=6(materiaprimaM2)x1 +x2+s3=1(lmitededemanda)
x1,x2,s1,s2,s3,s4 0x2+s4 =2(lmitededemanda)
sujetaa
Lasvariabless1,s2,s3 ys4 sonlasholgurasasociadasconlasrestriccionesrespectivas.
Acontinuacinseexpresarlafuncinobjetivocomosigue:
z 5x1 4x2=0
Deestamanera,latablainicialsmplexsepuederepresentarcomosigue:
Pgina 6
-
Lasvariablesnobsicas(lasquenoaparecenenlalistaBsica)siempresonigualacero.
En una funcin objetivo de maximizacin,seseleccionalavariablenobsicaparaentraralasolucinbsica,utilizandolaquetengaelcoeficiente ms negativo,enestecasosonx1=5yx2=4,porloqueseseleccionax5.
Determinarvariabledeentrada:
Sedeterminadividiendolacolumnasolucinentrelacolumnadelavariableseleccionadaparaentrar(x1),Se descartan las divisiones entre 0 y los negativos.Seseleccionalavariablebsicaconelcocientemenor s1
Determinarvariabledesalida:
Nuevorenglnpivote=Renglnpivoteactual/Elementopivote1.
Nuevorengln=(Renglnactual) (Sucoeficienteenlacolumnapivote) *(Nuevorenglnpivote)1.Nuevorenglnpivotex1=Renglnpivotes1actual62.Nuevorenglnz=Renglnzactual (5)* Nuevorenglnpivote3.Nuevorenglns2=Renglns2actual (1)* Nuevorenglnpivote4.Nuevorenglns3=Renglns3actual (1)* Nuevorenglnpivote5.Nuevorenglns4=Renglns4actual (0)* Nuevorenglnpivote
Todoslosdemsrenglones,incluyendoz:2.
Nuevasolucinbsica:
Pgina 7
-
Paralasiguienteiteracinserealizanuevamentelabsquedadelreglnpivote,ylavariablenobsicaconelcoeficientenegativomayoresx2,porloqueestaeslavariablequeentra.Luegosebuscalavariablebsicaquesale,alrealizarlarazndelacolumnasolucinentrelacolumnaqueentra,seleccionandolaquetengaelvalorpositivomenor,enestecasoseras2.
Luegoserealizanlasoperacionesparaefectuarelcambiodevariables:1.Nuevorenglnpivotex2=Renglnpivotes2actual4/32.Nuevorenglnz=Renglnactualz (2/3) *Nuevorenglnpivote3.Nuevorenglnx1=Renglnx1 actual (2/3)* Nuevorenglnpivote4.Nuevorenglns3=Renglns3 actual (5/3)* Nuevorenglnpivote5.Nuevorenglns4=Renglns4 actual (1)* Nuevorenglnpivote
Comoningunodeloscoeficientesdelrenglnzasociadosconlasvariablesnobsicass1ys2sonnegativos,estaltimatablaesptima.
Sepuedeleerlasolucinptimaenlatablasmplexcomosigue:losvaloresptimosdelasvariablesenlacolumnaBsicasevenenlacolumnaSolucindelladoderecho,ysepuedeninterpretardelsiguientemodo:
Pgina 8
-
Pgina 9
