lOMoARcPSD|65972990
3.3 y 3.4 - Resumen de programación entera subtemas 3.3 y
3.4
Investigación de operaciones (Instituto Tecnológico Superior de Occidente del Estado
de Hidalgo)
messages.pdf_cover_qr_code_label
messages.studocu_not_sponsored_or_endorsed_by_college
messages.downloaded_by
lOMoARcPSD|65972990
25-3-2020 Programación
Entera
Resumen
Instituto Tecnológico Superior del Occidente del
Estado de Hidalgo
3. Programación Entera
Investigación de Operaciones
M.A.C. Lilia Antonia Mendoza Sierra
Karen Martínez López | 18011103
4° B
Fecha de entrega: Miércoles 25 de marzo del 2020
messages.downloaded_by
lOMoARcPSD|65972990
3.3 Método gráfico en la programación entera.
El método gráfico se emplea para resolver problemas que presentan sólo 2 variables
de decisión. El procedimiento consiste en trazar las ecuaciones de las restricciones en
un eje de coordenadas X1, X2 para tratar de identificar el área de soluciones factibles
(soluciones que cumplen con todas las restricciones).
La solución óptima del problema se encuentra en uno de los vértices de esta área de
soluciones creada, por lo que se buscará en estos datos el valor mínimo o máximo del
problema.
Características del método grafico de la programación entera.
Ayuda al administrador a usar más eficientemente sus recursos, distribuyendo
eficazmente los elementos con los que cuenta para la actividad productiva.
Permiten tomar decisiones objetivas y dejar a un lado el modo de pensar o de
sentir.
Arroja soluciones posibles y prácticas y le dan un panorama al administrador
para la toma de decisiones;
En el método gráfico no puede haber más de tres incógnitas.
El trazo la función objetivo en el plano cartesiano y se dibujan líneas paralelas
a éste, hasta llegar al punto más distante en el área de soluciones factibles.
EJEMPLO:
Una compañía de auditores se especializa en preparar liquidaciones y auditorías de
empresas pequeñas. Tienen interés en saber cuántas auditorías y liquidaciones
pueden realizar mensualmente para maximizar sus ingresos. Se dispone de 800 horas
de trabajo directo y 320 horas para revisión. Una auditoría en promedio requiere de 40
horas de trabajo directo y 10 horas de revisión, además aporta un ingreso de 300 dls.
Una liquidación de impuesto requiere de 8 horas de trabajo directo y de 5 horas de
revisión, produce un ingreso de 100 dls. El máximo de liquidaciones mensuales
disponibles es de 60.
Maximizar
Sujeto a:
messages.downloaded_by
lOMoARcPSD|65972990
La solución óptima siempre se encuentra en uno de los vértices del conjunto de
soluciones factibles. Se analizan estos valores en la función objetivo. El vértice que
representa el mejor valor de la función objetivo será la solución óptima.
3.4 Método de ramificación y acotación
El método de ramificar y acotar ayuda a resolver problemas complejos de
programación a través de subprogramas, con la que se puede llegar a una solución.
Las "ramas" de este modelo irán "creciendo" o extendiéndose dependiendo de las
variables a resolver. Este método generalmente es utilizado en la resolución de
problemas de optimización, ya que resolver problemas NP-hard y obtener una solución
óptima requiere de demasiado esfuerzo computacional, y esta herramienta ayuda a
que el esfuerzo computacional no sea demasiado. También se utiliza para los
problemas de juegos.
messages.downloaded_by
lOMoARcPSD|65972990
El método genera nodos las cuales son soluciones de cada variable, que se sigue
extendiendo, estas ramificaciones de las soluciones dadas por el método continúan
creciendo siempre y cuando la siguiente solución este dentro de lo óptimo. El algoritmo
busca el espacio de soluciones dadas por la mejor solución.
El objetivo de este algoritmo será encontrar el valor mínimo de una función f(x) donde
el rango de x está determinado sobre un conjunto S de posibles soluciones. La
iteración tiene 3 componentes principales:
Selección del nodo para procesos
Calcular los límites
Ramificar
Para cada nodo que se genera en la ramificación tendremos:
Cota superior del beneficio óptimo que podemos alcanzar a partir del nodo i.
Cota inferior del beneficio óptimo que podemos alcanzar a partir del nodo i.
Beneficio estima óptima que se puede encontrar a partir del nodo i.
Las cotas deben ser fiables para poder determinar cuándo se hace una acota y el
beneficio estimado ayuda a decidir que parte del árbol evaluar primero.
messages.downloaded_by
lOMoARcPSD|65972990
Diagrama de flujo del método de ramificación y acotación.
Características del método de ramificación y acotización.
Emplea algoritmos para encontrar la solución óptima con variables enteras.
Puede ser usado para dos o más variables dependiendo del problema que se
presente.
Reduce mucho el número de combinaciones que se deben examinar.
Si ninguna solución es entera, se crean nuevas ramas y se resuelven nuevos
problemas.
La solución que se encuentra proporciona una cota para esa rama en el sentido
de que ninguna otra solución puede ser mejor.
messages.downloaded_by
lOMoARcPSD|65972990
EJEMPLO:
messages.downloaded_by
lOMoARcPSD|65972990
messages.downloaded_by
lOMoARcPSD|65972990
messages.downloaded_by
lOMoARcPSD|65972990
messages.downloaded_by