INSTITUTO TECNOLOGICO DE SAN LUIS POTOSÍ
PROFESOR: VICTOR ANSELMO CORDOVA VALERO
INTEGRANTES DE EQUIPO
• GARCIA REYES JIMENA ESMERALDA
• ARELY JACQUELINE PADRÓN SIERRA
• JESUS DARIO SUAREZ SANTILLAN
• LOREDO TORRES ANTONIO DE JESÚS
• RAMOS FLORES SAUL ISRAEL
INVESTIGACION DE
HORA: 13:00-14:00 HORAS
OPERACIONES I
UNIDAD 3
UNIDAD 3 PROGRAMACIÓN ENTERA
3.1 Introducción y casos de aplicación
3.2 Definición y modelos de programación entera
3.3 Método grafico de programación entera
3.4 Método de ramificación y acotación
3.5 Método heurístico para problemas binarios
3.6 Uso de software (WIN QSB, TORA, DS for Windows, LINGO, LINDO Y
OTROS)
3.1 Introducción y casos de aplicación
Hasta ahora solo se han estudiado problemas de programación lineal en los cuales
la solución satisface las restricciones dadas. Estas restricciones incluyen aditividad
proporcional, divisibilidad y no negatividad. La divisibilidad implica que son
permitidas las soluciones fraccionarias para los problemas lineales. Sin embargo,
algunos modelos requieren que la solución, además de cumplir con todas las
restricciones, sea solo de números enteros.
Se considera que los pioneros de la programación entera fueron Wagner (1950) y
Manne (1959). Tradicionalmente estos modelos se han considerado como
subclases de la programación lineal, sin embargo, las variables de decisión que
aparecen en ellos sólo toman valores enteros, por lo que realmente deben
considerarse como problemas de programación entera. El número de modelos
lineales enteros y sus métodos de solución es en la actualidad bastante extenso.
No siempre es admisible que las variables de un PL tomen valores continuos,
pudiendo presentarse dos casos
• Decisiones dicotómicas (si- no)
• Decisiones que deben tomarse en unidades discretas.
Si se requiere que todas las variables sean enteras, se habla de Programación
Lineal Entera Pura; si se necesita que solo algunas de las variables de decisión
sean números enteros, se tiene un problema de Programación Lineal Entera Mixta.
En algunas aplicaciones, sólo se permite que todas las variables tomen valores de
cero o uno; se trata en estos casos de Programación Lineal Entera Binaria (Digital).
Si se requiere que solamente algunas de las variables tomen valores de cero o
uno, se tiene un problema de Programación Lineal Entera Binaria Mixta.
Un ejemplo típico de este modelo se tiene en cualquier línea de producción
enserie, en la cual todas las variables (piezas) son números enteros (no se puede
hablar de medias piezas o de ¾ de pieza), y la solución óptima debe estar formada
con números enteros.
3.2 Definición y modelos de programación entera
La programación entera es el método empleado para resolver problemas que
tienen
variables de decisión enteras. Estos modelos se han considerado submodelos de
la
programación lineal con la característica de enteridad. Uno de los primeros
enfoques de solución al tipo de problemas que plantea la programación entera, fue
el de evaluación de cada posible solución, es decir, cada una de las combinaciones
de valores enteros para las variables del problema, conduciendo a una solución
óptima exacta.
Un modelo de programación entera es aquel cuya solución óptima tiene sentido
solamente si una parte o todas las variables de decisión toman valores restringidos
a números enteros, permitiendo incorporar en el modelamiento matemático
algunos
aspectos que quedan fuera del alcance de los modelos de programación lineal.
En este sentido los algoritmos de resolución de los modelos de programación
entera
difieren a los utilizados en los modelos de programación lineal, destacándose entre
ellos el Algoritmo de Ramificación y Acotamiento (o Branch & Bound), Branch &
Cut,
Planos cortantes, Relajación Lagrangeana, entre otros.
Los modelos de programación entera se pueden clasificar en: programación entera
mixta (PEM), programación entera pura (PEP) y programación entera binaria
(PEB).
Programación entera mixta (PEM). A esta categoría pertenecen aquellos
problemas
de optimización que consideran variables de decisión enteras o binarias pero no
de
forma exclusiva. De esta forma un problema de PEM puede considerarse como un
híbrido entre distintas categorías de modelamiento, siendo un caso típico aquel
que
considera la mezcla de variables enteras y variables continuas (estas últimas
características de los modelos de programación lineal).
Por ejemplo:
• Incorporación de costos fijos
• Problemas de localización y transporte
• Problemas de generación eléctrica
Programación Entera Pura (PEP). En esta categoría encontramos aquellos
modelos
de programación entera que consideran exclusivamente variables de decisión que
adoptan valores enteros o binarios.
Por ejemplo:
• Problemas de asignación
• Problemas de corte de rollos
• Selección de invitados de una boda
• Problema de mochila
Programación entera binaria (PEB). Es un método perteneciente a la programación
lineal, por lo que su base es un algoritmo matemático que tiene como
finalidad
resolver un problema indeterminado formulado a través de ecuaciones
lineales,
optimizando así una función objetivo también lineal que generalmente se refiere a
costo o a tiempo.
Se utiliza en problemas de asignación o de toma de decisiones enfocadas a hacer
o no una tarea, entre sus campos de aplicación más comunes se encuentran:
• Despacho de envíos
• Diseño de redes
• Programación de actividades
Las aplicaciones de la programación entera no reemplaza la versatilidad que ofrece
el disponer de modelos de programación lineal. Más aún, se puede considerar
estas
categorías de modelamiento matemático como complementarias en el ámbito de
la
investigación de operaciones.
Algunas aplicaciones típicas son problemas de localización de instalaciones,
inclusión de costos fijos, problemas de asignación, de ruteo vehicular, etc.
3.3 Método grafico de programación entera
Un método grafico de programación entera consiste en representar en unos ejes
cartesianos, o sistema de coordenadas, ambas rectas y comprobar si se cortan y,
si es así, dónde. Esta última afirmación contiene la filosofía del proceso de
discusión de un sistema por el método gráfico.
Que es un método grafico?
Es el método que permite la solución de problemas de programación lineal, el cual
se encuentra limitado a problemas de dos variables de decisión, debido a que no
es posible una representación gráfica de más de tres dimensiones.
Algoritmos de programación entera
Para resolver problemas de programación lineal entera, se utilizan
varios algoritmos como son: ralph gomory, ramificación y acotamiento,
enumeración exhaustiva o enumeración explícita, enumeración implícita, aditivo de
egon balas y algoritmos heurísticos.
3.4 Método de ramificación y acotación
Pasos:
Ramificación: Variables
Acotación: Valor de la función objetivo
A partir de la solución del PLA:
La ramificación consiste en dividir cada problema en dos nuevos
subproblemas, obtenidos mediante la imposición de restricciones excluyentes
que dividen el conjunto de oportunidades del problema original en dos partes,
pero eliminando en ambas partes la solución no entera del problema original.
Si xbi no entero, entonces se generan a partir de dicho valor dos restricciones x i
[xbi y xi [xbi +1 (siendo [xbi la parte entera por defecto de xbi ), que
añadidas cada uno por separado al problema original, da lugar a dos nuevos
subproblemas.
Por ejemplo la variable x1 tiene que ser entera, pero en la solución anterior
(PLA u otro), la variable vale: x1 = 6.8. Esta solución no es valida, ya que no es
admisible un valor fraccional, por tanto se introduciran las siguientes
restricciones: x1 6 y x1 7, de forma que se ha eliminado una porción del
conjunto donde no hay soluciones enteras, pero se mantienen las enteras:
Así se prosigue con todas las variables hasta que sean enteras.
Si al proceso de ramificación no se mejora de alguna forma, llegaríamos
a analizar TODAS las soluciones enteras (Enumeración Total). Por eso, se
añade la fase de Acotación, esta tiene que ver con el valor de la función objetivo.
A medida que se va ramificando se obtienen soluciones enteras y otras
que no lo
son.
No podemos asegurar que la primera solución entera obtenida sea la solución
optima, sino que es necesario comprobar si existen otras soluciones enteras o no.
El análisis del PLA: Ramificación se realiza siempre a partir de aquel problema
que tiene el mejor valor de la función objetivo, y siempre que exista alguna
solución (no entera) con un valor de la función objetivo
Ejemplo: (Maximización)
* Solución del PLA: FO: 5487,33 (Solución no entera)
Primera Ramificación:
Problema 1: FO: 5340, 75 (solución no
entera) Problema 2: FO: 5425.10
(solución no entera).
Segunda Ramificación:
A partir del problema 2, por tener un mejor valor de la función
objetivo: Problema 21: FO: 5405, 30 (solución no entera)
Problema 22: FO: Infectable.
Como no hay solución entera hemos de seguir ramificando: Por donde?.
Problema 22 tiene mejor valor que problema 1.
Tercera ramificación:
A partir del problema 21
Problema 211:FO = 5350 (solución entera)
Problema 212 F= = 5385.25 (solución no
entera).
La solución del problema 211 (5350) es la optima?
NO, ya que ramificando por el problema 212 se podrían encontrar mejores
soluciones. Pero lo que es seguro que a partir del Problema 1: FO: 5340, 75 no
vamos a encontrar ninguna solución entera mejor que la que hemos encotrado,
por tanto ese valor de 5350 es la COTA a partir de la cual no analizaremos ningún
problema que tenga un valor de FO menor o igual.
Cuarta Ramificación:
Problema 2121: FO = 2360 (solución entera)
Problema 2122 FO = 2366.25 (solución no
entera).
Que hacer: a) La cota ha mejorado, ahora no analizaremos ninguna solución
con un valor de FO menor o igual que 2360. Pero aun no podemos afirmar que
la solución del problema 2121 sea la optima, hemos de seguir ramificando:
Quinta Ramificación:
Problema 21221: FO = 2355 (solución entera)
Problema 21222 FO = 2358.75 (solución no
entera).
¿Hemos de ramificar el problema 21222?: NO, ya que tenemos una solución
entera 2360 mejor que cualquier valor de una función objetivo de un problema no
ramificado.
Esquema del algoritmo de ramificación y acotación.
RESOLVER EL
P.L.A.
SI NO
ELEGIR UNA
¿ES VARIABLE ENTERA Xi
OPTIMA CUYO VALOR EN LA
ENTERA? SOLUCION DEL P.L.A.
SEA FRACCIONAL
STOP
RESOLVER DOS
PROBLEMAS
LINEALES IGUALES AL
ANTERIOR CON LAS
RESTRICCIONES
ADICIONALES: UNO
CON LA RESTRICCIÓN
Xi<[Xi] Y EL OTRO
CON LA RESTRICCION
Xi > [Xi]+1
ANALIZAR
ELEGIR EL
SOLAMENTE EL
PROBLEMA
PROBLEMA CON
QUE TENGA
MEJOR SOLUCION
EL MEJOR
QUE CUALQUIERA
VALOR DE LA
DE LAS SOLUCIONES
FUNCION
OBJETIVO
ENTERAS
CONOCIDAS
Ejemplo
Max F(X) = 8x1 + 10x2
s.a. 4x1 + 6x2 24
8x1 + 3x2 24
x1 0,x2 0,
x1,x2 Z+
Resolviendo en primer lugar el PLA, es decir
Max F(X) = 8x1 + 10x2
s.a. 4x1 + 6x2 24
8x1 + 3x2
24
x1 0,x2 0
x1 = 2, x2 = 8/3, f(x) = 128/3
Primera Ramificación:
Solución: x1 = 2, x2 = 8/3, f(x) =
128/3
subproblema 1 subproblema 2
Max F(X) = 8x1 + 10x2 . Max F(X) = 8x1 + 10x2
s.a. 4x1 + 6x2 s.a. 4x1 + 6x2
24 24
8x1 + 3x2 24 8x1 + 3x2
24
x2 3 x2 2
x1 0,x2 0 x1 0,x2 0
solución x1=1,5, x2=3, F(x)=42 solución x1=2,5, x2=2, F(x)=38
Segunda ramificación:
Solución anterior mejor: x1=1,5, x2=3, F(x)=42
subproblema 1.1 subproblema 1.2
Max F(X) = 8x1 + 10x2 . Max F(X) = 8x1 + 10x2
s.a. 4x1 + 6x2 s.a. 4x1 + 6x2
24 24
8x1 + 3x2 24 8x1 + 3x2
24
x2 3 x2 3
x1 1 x1 2
x1 0,x2 0 x1 0,x2 0
solución x1=1, x2=10/3,F(x)=124/3 solución infactible.
Tercera ramificación
Solución anterior mejor: x1=1, x2=10/3,F(x)=124/3
subproblema 1.1.1 subproblema 1.1.2
Max F(X) = 8x1 + 10x2 . Max F(X) = 8x1 + 10x2
s.a. 4x1 + 6x2 24 s.a. 4x1 + 6x2 24
8x1 + 3x2 24 8x1 + 3x2 24
x2 3 x2 3
x1 1 x1 2
x2 3 x2 4
x1 0,x2 0 x1 0,x2 0
solución x1=1, x2=3,F(x)=38 solución x1=0, x2=4,F(x)=40
Solución OPTIMA x1 = 0, x2 = 4, F(x) = 40
el árbol del problema resuelto es el siguiente:
X1=2,5,X2=2,F=3 X1=1,X2=3,F=3
1.1.1
X2<2 X2<3
X1=2,X2=8/3,F=128/3 X1=1,X2=10/3,F=124/
PLA 1.1
X2>3 X1< X2>4
X1=1,5,X2=3,F=4 X1=0,X2=4,F=4
1.1.2
X1>2
INFACTIBLE
1.2
3.5 Método heurístico para problemas binarios
Se basa en la utilización de reglas empíricas para llegar a una solución. El
método heurístico conocido como “IDEAL”, formulado por Bransford y Stein
(1984), incluye cinco pasos: Identificar el problema; definir y presentar el
problema; explorar las estrategias viables; avanzar en las estrategias; y lograr
la solución y volver para evaluar los efectos de las actividades (Bransford &
Stein, 1984).
El matemático Polya (1957) también formuló un método heurístico para
resolver problemas que se aproxima mucho al ciclo utilizado para programar
computadores. A lo largo de este curso se utilizará este método propuesto por
Polya.
Según Polya (1957), cuando se resuelven problemas,
intervienen cuatro operaciones mentales:
1. Comprender el problema.
Leer el problema varias veces
Establecer los datos del problema
Aclarar lo que se va a resolver (¿Cuál es la pregunta?)
Precisar el resultado que se desea lograr
Determinar la incógnita del problema
Organizar la información
Agrupar los datos en categorías
Trazar una figura o diagrama.
2. Hacer el plan.
Escoger y decidir las operaciones a efectuar.
Eliminar los datos inútiles.
Descomponer el problema en otros más pequeños.
3. Ejecutar el plan (Resolver).
Ejecutar en detalle cada operación.
Simplificar antes de calcular.
Realizar un dibujo o diagrama.
4. Analizar la solución (Revisar).
Dar una respuesta completa
Hallar el mismo resultado de otra manera.
Verificar por apreciación que la respuesta es adecuada.
Como se aplica:
Como disciplina científica, la heurística es aplicable a cualquier ciencia e
incluye la elaboración de medios auxiliares, principios, reglas, estrategias y
programas que faciliten la búsqueda de vías de solución a problemas; o sea,
para resolver tareas de cualquier tipo para las que no se cuente con un
procedimiento algorítmico de solución. Según Horst Müler: Los Procedimientos
Heurísticos son formas de trabajo y de pensamiento que apoyan la realización
consciente de actividades mentales exigentes. Los Procedimientos Heurísticos
como Método científico pueden dividirse en principios, reglas y estrategias.
Principios Heurísticos: constituyen sugerencias para encontrar (directamente)
la idea de solución; posibilita determinar, por tanto, a la vez, los medios y la vía
de solución. Dentro de estos principios se destacan la analogía y la reducción.
Reglas Heurísticas: actúan como impulsos generales dentro del proceso de
búsqueda y ayudan a encontrar, especialmente, los medios para resolver los
problemas. Las Reglas Heurísticas que más se emplean son:
* Separar lo dado de lo buscado.
* Representar magnitudes dadas y buscadas con variables.
* Determinar si se tienen fórmulas adecuadas.
* Utilizar números (estructuras más simples) en lugar de datos.
* Reformular el problema.
Estrategias Heurísticas: se comportan como recursos organizativos del proceso
de resolución, que contribuyen especialmente a determinar la vía de solución
del problema abordado. Existen dos estrategias:
o El trabajo hacia adelante: se parte de lo dado para realizar las reflexiones que
han de conducir a la solución del problema.
o El trabajo hacia atrás: se examina primeramente lo que se busca y,
apoyándose de los conocimientos que se tienen, se analizan posibles
resultados intermedios de lo que se puede deducir lo buscado, hasta llegar a
los dados.
3.6 Uso de software (WIN QSB, TORA, DS for Windows,
LINGO, LINDO Y OTROS)
Programa Caracteristicas Tipo de modelo
-Paquete de herramientas muy versátil que
permite el análisis.
-Mixto
– Resolución de modelos matemáticos,
-Entero
problemas administrativos, de producción,
proyectos, inventarios, transporte, entre
muchos otros. puro
– Ofrece una interfaz básica pero amigable, - -Binario
Resolución de sus modelos de programación
lineal, continua o entera.
WINQSB
-Herramienta que forma parte de una serie de
comandos a veces denominados de «análisis Y
si». -Entero puro
-Con Solver, puede buscarse el valor óptimo -Binario
para una fórmula de celda, denominada celda
objetivo, en una hoja de cálculo. -Mixto
SOLVER
-Solver funciona en un grupo de celdas que
estén relacionadas, directa o indirectamente,
con la fórmula de la celda objetivo.
– herramienta adecuada para solucionar
problemas de programación lineal, y
programación lineal entera.
Herramienta simple para formular problemas
lineales y no lineales, programación entera,
resolverlos y analizar su solución.
-El resultado que LINGO nos proporciona es la
optimización
-Uno de los rasgos más poderosos de LINGO es
su aplicación en el lenguaje de modelo
matemático.
-Mixto
-Entero
– Otro aspecto es la sección de los datos, que le
permite aislar los datos de la formulación del
modelo. De hecho LINGO puede leer datos puro
incluso de una hoja de cálculo separada, base
de datos, o archivo de texto
LINGO
Herramienta computacional de optimización es
un programa basado en Windows
-Aplicación muy simple, con una interfaz
gráfica de baja calidad.
-Se puede utilizarse en procesadores de 32 y 64 -Mixto
bits -Entero
-La configuración de pantalla para adecuarse puro
a sus ajustes de presentación de 800 x 600 y
1024 x 768 pixeles.
TORA
-Se presenta una herramienta para resolver -Mixto
modelos de programación lineal entera. - -Entero
función objetivo para variables de decisión
enteras. -Es
puro
una función llamada nbintprog (non binary
integer programming) creada por los autores
en el asistente matemático
MATLAB MATLAB. – Nbintprog tiene como base
matemática una técnica de ramificación y
acotación (branch and bound) que junto a
estrategias de programación utilizadas
presenta características favorables para la
solución de dichos modelo.
-Solucionador mediante programación
matemática de alto rendimiento
Soluciona problemas de programación lineal,
IBM ILOG programación entera mixta y programación
CPLEX cuadrática
Optimizer -Mixtos
LINDO es un intuitivo programa para resolver
problemas de optimización matemática
Programación lineal (continuos, enteros y
binarios).
-300 variables continuas, 30 variables discretas -Entero puro
(enteras o binarias) y 150 restricciones. -Binario
Lindo
CONCLUSION:
Los problemas de programación entera surgen con frecuencia cuando
los valores de algunas o todas las variables de decisión deben
restringirse a valores enteros. Existen también muchas a plicaciones
que necesitan decisiones de sí o no - incluyendo las relaciones
combinatorias que se puedan expresar en términos de tales
decisiones - que se pueden representar por variables binarias (0 -1).
Estos problemas son más difíciles de lo que serían sin la restricción
de valores enteros, de manera que los algoritmos disponibles para
programación entera, en general, son mucho menos eficientes que el
método simplex. Los factores que determinan el tiempo de cálculo
son el número de variables enteras y la es tructura del problema.
