mcdn-02.pdf

UNIVERSIDAD PERUANA LOS ANDESF lt d d Ci i Ad i i t ti C t blFacultad de Ciencias Administrativas y Contables

METODOS CUANTITATIVOS DE NEGOCIOScaptulo 2 modelos de captulo 2. modelos de

optimizacin: programacin lineal y entera

Objetivos de Aprendizaje:

Formular y resolver modelos de optimizacin: programacin lineal y/o entera e Interpretar los resultados de un problema deresultados de un problema de programacin lineal y/o entera mediante el anlisis demediante el anlisis de sensibilidad.

[email protected]

Contenido: El arte de formular modelos de programacin lineal..2.1

Solucin grfica de un modelo de programacin lineal.2.2

Solucin algebraica de un modelo de programacin Solucin algebraica de un modelo de programacin lineal.2.3

Mtodos simplex.2.4

2 5 Anlisis de sensibilidad.2.5

Programacin con enteros Solucin de problemas2 [email protected]

Programacin con enteros. Solucin de problemas.2.6

El arte de formular modelos de programacin lineal.programacin lineal.

En problemas reales de planificacin y toma de decisiones, las mayores dificultades no surgen en la y gresolucin del modelo, sino en su propia formulacin. No siempre es fcil obtener una formalizacin matemtica del sistema que queremos representar, especialmente porque es necesario adaptarse a unos modelos estndar para que puedan resolverse mediantemodelos estndar para que puedan resolverse mediante algoritmos de uso general. Esto se debe a que si los algoritmos son conocidosEsto se debe a que, si los algoritmos son conocidos, seguramente se dispondr de un software capaz de resolver el modelo de forma eficiente.

[email protected] 4

El arte de formular modelos de programacin lineal.programacin lineal.

La modelizacin tiene ms de arte que deLa modelizacin tiene ms de arte que de ciencia. No existe un conjunto de reglas fijas o teoras que permitan aprendero teoras que permitan aprender mecnicamente a formular modelos. Como la pintura o la escultura este arte seComo la pintura o la escultura, este arte se aprende sobre todo con la prctica, aunque es conveniente utilizar una formaaunque es conveniente utilizar una forma sistemtica de disear los modelos.

[email protected] 5

Metodologa dede Modelizacin de Problemasde Problemas de ProgramacinProgramacin Lineal

[email protected] 6

Metodologa de Modelizacin de Problemas de Programacin LinealProblemas de Programacin Lineal

Descripcin del problema. En el campo puramente acadmico se diraEn el campo puramente acadmico, se dira que la descripcin del problema debe llevarla a cabo la institucin (empresa administracina cabo la institucin (empresa, administracin pblica, ONG, ) que encarga el sistema de decisindecisin. Posiblemente se considerar que la i tit i i t d l i f iinstitucin proporcionar toda la informacin necesaria y definir de forma clara el

bl l f tproblema al que se enfrenta. [email protected] 7


Descripcin del problema. En la prctica esto no es as por dos razones:En la prctica esto no es as por dos razones:

Los decisores generalmente no son plenamente conscientes ni tienen por qu serlo de lasconscientes, ni tienen por qu serlo, de las capacidades y limitaciones de las tcnicas disponibles. Por tanto, y en general, no podrn p y g pexpresar el problema de decisin de una forma clara y completa.Frecuentemente, nuestro interlocutor en este tipo de proyectos no estar entrenado para exponer sus ideas de forma analtica y estructuradasus ideas de forma analtica y estructurada.

[email protected] 8


Descripcin del problema. P t d ll l li t d b ti iPor todo ello, el analista debe participar en la fase de descripcin del problema. El producto final de esta fase debe ser un documento claro y conciso que describa el planteamiento del problema y las decisiones que el sistema debe ayudar a tomar, el o los algoritmos que deben aplicarse y el entorno informtico en el que va a aplicarse.

[email protected] 9


Definicin de variables. Puede afirmarse que una adecuadaPuede afirmarse que una adecuada definicin de las variables supone un paso fundamental en el planteamiento delfundamental en el planteamiento del problema. E h d i blEn muchos casos, cada variable se corresponde con una de las decisiones

l i t d b t P t tque el sistema debe tomar. Por tanto, definir las variables del problema equivale a

t bl d i i d b d testablecer qu decisiones deben [email protected] 10


Definicin de variables. A no ser que se tenga experiencia o que elA no ser que se tenga experiencia, o que el problema sea sencillo, no es fcil definir correctamente todas las variables de uncorrectamente todas las variables de un modelo, por lo menos al principio. El i i t d l d b dEl seguimiento del proceso, debe ayudamos a rehacer la definicin de variables de la forma

i t t t t d lms conveniente para contestar a todas las cuestiones que plantea el sistema real y que nos di t t tid dicta nuestro sentido comn.

[email protected] 11


D fi i i d i blDefinicin de variables. Debe sealarse tambin la importancia de:escribir explcitamente, no simplemente retener en nuestra memoria, la definicin ,conceptual de cada variable o grupo de variables y restricciones, as como definir y ,en qu unidades estn medidas.



Definicin de restricciones. T d l d d i iTodos los procesos de decisin se ven afectados por mltiples limitaciones. En algunos casos, stas se deben a la disponibilidad de recursos en otrosdisponibilidad de recursos, en otros proceden de obligaciones contractuales y legalescontractuales y legales.



Definicin de restricciones.Definicin de restricciones. Muy a menudo, las restricciones se derivan del hecho de que se est modelando undel hecho de que se est modelando un subsistema limitado, inscrito en el contexto de un sistema mayorde un sistema mayor. Muchas de las decisiones adoptadas en otras partes de ese sistema afectarn aotras partes de ese sistema afectarn a nuestro modelo en forma de restricciones.



Definicin de restricciones. Sea cual sea el origen de las restriccionesSea cual sea el origen de las restricciones, su definicin correcta es muy importante, ya que si se define un exceso deya que, si se define un exceso de restricciones, las soluciones que se obtengan no sern necesariamente las mejoresno sern necesariamente las mejores, mientras que, si se omite una restriccin relevante el sistema de decisin ofrecer arelevante, el sistema de decisin ofrecer a menudo respuestas impracticables o simplemente absurdassimplemente absurdas.



Definicin de restricciones. Frecuentemente en los modelos formuladosFrecuentemente, en los modelos formulados por principiantes, las variables representan cosas distintas en cada restriccin o soncosas distintas en cada restriccin o son incoherentes en cuanto a sus unidades de medida A menudo estos errores semedida. A menudo, estos errores se producen porque no se ha hecho explcita la definicin de las variables y restricciones deldefinicin de las variables y restricciones del modelo.



Definicin de restricciones. R t i i d d i ld dRestricciones de desigualdad.En problemas econmicos, las restricciones de desigualdad suelen indicar relaciones tales como disponibilidad de recursos, obligacin de satisfacer la demanda, etc.En algunos casos, estas restricciones estn g ,referidas exclusivamente a una sola de las variables del problema. p



Definicin de restricciones. R t i i d d i ld dRestricciones de desigualdad.Este tipo de restricciones son conocidas como cotas, l it b d E id t t l t dlmites o bounds. Evidentemente, las cotas pueden tratarse de la misma forma que cualquier otra restriccinrestriccin. Sin embargo, es mucho ms eficiente, desde un punto de vista computacional, darles un tratamiento pu o de s a co pu ac o a , da es u a a e oespecial. Todos los paquetes profesionales de PL dan un tratamiento especial a las cotas.



Definicin de restricciones. Las restricciones de igualdad as est cc o es de gua dadObedecen a lo que se conoce como ecuaciones de balance. Estas ecuaciones se emplean para modelizarsituaciones en las que, por ejemplo, la energa que entra en un nodo de distribucin debe ser igual a la energa que sale de este mismo nodo; las existencias de caja al principio del perodo ms lasexistencias de caja al principio del perodo ms las entradas deben ser iguales a las salidas ms las existencias finales, etc.existencias finales, etc.



Definicin de restricciones. Las restricciones de igualdad as est cc o es de gua dadA menudo, es posible eliminar por sustitucin algunas de estas restricciones de igualdad. La g gsupresin de estas restricciones y variables suele dificultar la interpretacin de resultados, por lo que, si l d i d di i i t tla reduccin de dimensiones no es importante, suelen mantenerse en la formulacin final.



Definicin de la funcin objetivo. Deben establecerse cules son los criteriosque permitirn evaluar las distintas soluciones posibles, esto es, debe definirse la funcin objetivo del modelo. En muchos casos este proceso da lugar a una reformulacin del modelo, aadiendo o eliminando restricciones y variables.



Definicin de la funcin objetivo. Al enfrentarse a un problema real hay que analizar si es posible definir unque analizar si es posible definir un objetivo nico. C d t ibl blCuando esto es posible, en problemas empresariales, ste suele ser del tipo: maximizar beneficios, minimizar costes, maximizar ventas, etc.,



Definicin de la funcin objetivo. La funcin objetivo debe incluir tan slo beneficios o costes variables, nunca los fijos. Como es bien sabido, las componentes fijas de ingresos y/o costes no modifican la solucin ptima del problema. Ms adelante, veremos que los ingresos o , q gcostes fijos se pueden tratar en Programacin Entera y Mixta.g y



Definicin de la funcin objetivo. En ocasiones es imposible seleccionar unEn ocasiones, es imposible seleccionar un solo objetivo a optimizar y, necesariamente, debemos tratar varios a la vezdebemos tratar varios a la vez. En la mayor parte de los casos, estos bj ti t t t di t iobjetivos son mutuamente contradictorios.

En este caso es necesario analizar la posibilidad de convertir algunos objetivos en restricciones.



Anlisis de la solucin. Una vez planteado y resuelto el problema de optimizacin, es necesario p panalizar de varias formas la solucin obtenidaobtenida.



Anlisis de la solucin. Al ti l t lAlgunas cuestiones ms relevantes que suelen plantearse en esta fase son:

es sensata la solucin obtenida?, pueden llevarse a la prctica sus

d i ?recomendaciones?, se obtiene mejores resultados que con los mtodos de decisin que se usaban antes de optimizar?de decisin que se usaban antes de optimizar?, cabra considerar alguna mejora o refinamiento adicional? etcadicional?, etc.


Fabricante de CamisasUn fabricante de camisas est tratando de decidir cuantas camisas debe

EJEMPLO1Un fabricante de camisas est tratando de decidir cuantas camisas debe producir durante el prximo mes. Pueden fabricar siete estilos. Los estilos varan en las horas de mano de obra que requieren, en margen unitario y

l t t i l l d t t d i li i tien las ventas potenciales que el departamento de comercializacin estima. Los datos son los siguientes:

Estilo HorashombreVentas

(unidades)

MargenUnitario

(u.m./unidad)

Se dispone de untotal de 7.500 horasde mano de obra

1 0,50 3 1,002 1,00 1 2,003 0 25 5 1 00

de mano de obra.Se desea calcularqu cantidad debefabricarse de cada 3 0,25 5 1,00

4 1,50 2 1,505 0,70 1.5 1,25

fabricarse de cadatipo, de forma que semaximice el margent t l b t l

[email protected] 0,90 1.5 1,107 1,20 1.6 1,20 27

total bruto para elfabricante.

EJEMPLO1

Variables:x indica el nmero de camisas a producir delxi indica el nmero de camisas a producir del estilo i.

i = {1 = camisas del estilo 1, 2 = camisas del estilo 2, 3 = camisas del estilo 3, 4 = camisas del estilo 4, 5 = camisas del estilo 5, 6 = camisas del estilo 6, 7 = camisas del estilo 7}


EJEMPLO1

Restricciones:Cantidad de mano de obra disponibleCantidad de mano de obra disponible.

Se dispone de una cantidad de horas hombre que se debe repartir entre los diferentes estilosque se debe repartir entre los diferentes estilos. Para la produccin de cada una de las camisas de cada estilo se necesita una cantidad determinada de horas.

0,5x1 + x2 + 0,25x3 + 1,5x4 + 0,7x5 + 0,9x6 + 1,2x7 7.500, 7


EJEMPLO1

Demanda mxima de producto X1 3 000de producto. X1 3.000

X2 1.000X3 000Slo se puede

vender una X3 5.000X4 2.000

determinada cantidad mxima

X5 1.500X6 1 500estimada de cada

producto.

X6 1.500X7 1.600


EJEMPLO1

No negatividad de las variables:

x1 , x2 , x3 , x4 , x5 , x6 , x7 01 , 2 , 3 , 4 , 5 , 6 , 7


EJEMPLO1

Funcin Objetivo:

Se debe maximizar el margen total o la gsuma de los mrgenes de cada estilo.

Max ( z ) = x1 + 2x2 + x3 + 1 5x4 + 1 25x5Max ( z ) = x1 + 2x2 + x3 + 1.5x4 + 1.25x5+ 1.1x6 + 1.2x7


EJEMPLO1


[email protected]

Documents

mcdn-02.pdf