PROGRAMACIÓN ENTERA

MATERIA. Investigación de operaciones

FECHA : 07 DE DICIEMBRE DEL 2024
INTEGRANTES: Daniela Rodriguez, Banexel Campos, Rey Orozco,
Jonathan Rascón .
Mtra. Fiama Carolina Chavarría.
En el mundo de la industria y los negocios hay numerosas situaciones en
las cuales se presentan problemas de programación lineal para los cuales
las variables de decisión sólo pueden tener valores de Números enteros y
no fraccionarios. Esto debido a alguna razón física, por ejemplo si las
variables de Decisión son números de personas, de artículos terminados,
etc., será obvio que no podrán ser números Fraccionarios, pues esto no
tendría ningún sentido.
En el mundo de la industria y los negocios hay numerosas situaciones en las cuales se
presentan problemas de programación lineal para los cuales las variables de decisión sólo
pueden tener valores de números enteros y nofraccionarios. Esto debido a alguna razón
física, por ejemplo si las variables de decisión son números de personas, de artículos
terminados, etc., será obvio que no podrán ser números fraccionarios, pues esto no tendría
ningún sentido. Sus pioneros 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 solo 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, lo que nos ha
llevado hacer una selección considerando aquellos que creemos más interesantes y que
aparecen con mayor frecuencia en la realidad. No siempre es admisible que las variables de
un PL tomen valores continuos, existen:  Decisiones dicotómicas (si-no) Decisiones que
deben tomarse en unidades discretas. Si se requiere que todas las variables sean enteras, se
dice que se habla de programación lineal entera pura; si se necesita que algunas de las
variables de decisión sean números enteros, se tiene un problema de Programación Lineal
Entera Mixta.
En algunas aplicaciones, solo se permite que todas las variables tomen
valores de cero o uno, hablamos 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. La programación entera es un
término para los modelos de programación matemática que presentan
condiciones de integridad (condiciones que estipulan que algunas o todas
las variables de decisión deben tener valores enteros). Ya hemos apuntado e
investigado que los modelos de programación lineal entera son modelos de
programación lineal que tienen característica adicional de que las variables
de decisión deben tener valores enteros. Existe una clasificación en estos
modelos: Los modelos de programación entera mixta son aquellos en los que
algunas variables toman valores enteros y otros valores continuos. Los
modelos de programación entera pura son aquellos en los que todas las
variables toman valores enteros.
 Casos de aplicación

a) Todos los problemas de programación lineal, donde las actividades, por su

estructura deben ser no divisibles, son programas enteros. b) Todos los
problemas de transporte, asignación y redes de optimización. Este tipo de
problemas son enteros y dada la estructura tan especial que tienen estos
problemas, tienen métodos de solución propios. c) Problemas de
secuenciación. Este tipo de problemas aunque son fáciles de formular,
resultan bastantes difíciles de resolver. d) Problema tipo mochila. Este tipo de
problemas de optimización de carácter entero puede darse en dos versiones.
1. En la primera se proporciona un cierto espacio con determinado volumen o
capacidad, y este debe ser llenado con objetos de valor y volumen o
capacidades especificado, sin exceder los límites físicos de dicho espacio. 2.
La segunda versión consiste en dividir a un objeto en varias porciones de
diferente valor, el problema consiste en encontrar la división de mayor valor.
 MÉTODO GOMERY

Método de Gomory. Gomory fue el primer creador del algoritmo para resolver métodos
de programación entera, el algoritmo de Gomory consiste en resolver el problema sin
considerar las restricciones del carácter entero de las variables y si la solución no es
entera añade restricciones que reduce el conjunto de soluciones del problema lineal
continuo asociado, sin excluir ninguna solución entera. En matemática, y más en
concreto en optimización, el método de los planos de corte es un procedimiento para
encontrar soluciones enteras de un problema lineal. Fue introducido por Gomory.
Funciona resolviendo un programa lineal no entero, después comprobando si la
optimización encontrada es también una solución entera. Si no es así, es añadida una
nueva restricción que corta la solución no entera pero no corta ningún otro punto de la
región factible. Esto se repite hasta que se encuentra la solución entera óptima.
Interpretación geométrica, una restricción es equivalente a un hiperplano, permitiendo
solo soluciones en uno de los lados del plano. Método fraccional de Gomor
 Este método solo resuelve modelos enteros puros y consta de los siguientes pasos:
1. Se resuelve el modelo sin tomar en cuenta la restricción de que las variables
sean enteras.
15
TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de Tapachula
2. Si la solución óptima cumple la condición de ser entera, ésta es la solución del
modelo. Si no, se toma uno de los renglones de la tabla simplex óptimo con lado
derecho no entero. A este renglón le llamamos renglón fuente.
3. Escribimos los coeficientes del renglón fuente como una combinación de un
número entero y una parte fraccionaria positiva entre cero y uno.
4. Pasamos todos los coeficientes fraccionarios del lado izquierdo, los enteros los
pasamos al lado derecho. Ahora hacemos que el lado izquierdo sea mayor o
igual a cero.
5. Escribimos esta desigualdad en forma de igualdad al sumar la variable de
superávit y la añadimos a nuestra tabla simplex óptimo. Resolvemos por el
método dual simplex. Regresamos al paso 2
MÉTODO DE RAMIFICACIÓN Y ACOTACIÓN

En 1960, Ailsa H. Land y Alison G. Doig, presentan el algoritmo Land-Doig. El

nombre de bifurcación y acotamiento (o bien, ramificación y acotamiento y en
inglés “Branch and Bound”) se lo dan posteriormente Little, Murty, Sweeney, Karel.
Más tarde, el algoritmo fue modificado por Dakin, haciéndolo de manera más
general. Al resolver un modelo de P. L. E., la primera idea que surge es la de
resolver el modelo como un problema de P. L. estándar. Una vez que se tienen la
solución, si ésta cumple con las condiciones de que todas las variables de decisión
sean enteras, entonces el problema está resuelto. Si no, entonces podemos
redondear los valores y aplicar el proceso hacia la solución del modelo de P. L. E
Que satisface la condición de que las variables sean enteras. El método de ramifica y acota
toma la idea anterior, sólo que ahora analiza todas las posibilidades de redondeo. Para ello va
formando un árbol de combinaciones, como los utilizados en probabilidad. A continuación
describimos los pasos del algoritmo del método: 1. Se resuelve el modelo utilizando el método
simplex, sin tomar en cuenta las restricciones de que las variables deben tomar valores
enteros. Si la solución óptima del problema satisface la condición de ser entera, el modelo está
resuelto. Parar. Si no, continuar con el algoritmo. 2. Se toma una de las variables que no es
entera y se toma el valor del entero próximo mayor y el valor del entero próximo menor. Se
plantean dos nuevas restricciones: que la variable sea mayor al entero mayor y que la variable
sea menor al entero menor. 3. Una vez hecho esto se plantean dos nuevos modelos de P. L. que
se deben resolver. Cada uno de ellos se obtiene al agregar una de las dos restricciones del
punto anterior. 4. Se resuelve cada uno de los modelos utilizando el método simplex. Si la
solución óptima es entera se anota el valor de la función objetivo. Si la solución óptima de
todos los modelos ya es entera se pasa al punto 5, si no, se aplica nuevamente el método
desde el punto 2, para cada uno de los modelos que tiene solución no entera. 5. Se comparan
los valores de Z y se toma el máximo, la solución asociada a este valor es la solución óptima
del modelo.
USO DE SOFTWARE

WIN QSB. WinQSB es un paquete de herramientas muy versátil que

permite el análisis y resolución de modelos matemáticos, problemas
administrativos, de producción, proyectos, inventarios, transporte, entre
muchos otros. Ofrece una interfaz básica pero 20 TECNOLÓGICO
NACIONAL DE MÉXICO Instituto Tecnológico de Tapachula amigable, y es
la aplicación por excelencia utilizada por profesionales de Ingeniería
Industrial y áreas administrativas para la resolución de sus modelos de
programación lineal, continua o entera
El acceso al WINQSB se puede hacer a través del botón INICIO del
sistema operativo WINDOWS, en el menú PROGRAMAS en la carpeta
WINQSB. WINQSB es una herramienta poderosa para el manejo de
métodos cuantitativos, el cual está conformado por 19 módulos: 1.
Análisis de muestreo de aceptación (Acceptance Sampling Analysis) 2.
Planeación agregada (Aggregate Planning) 3. Análisis de decisiones
(Decision Analysis) 4. Programación dinámica (Dynamic Programming)
5. Diseño y localización de plantas (Facility Location and Layout) 6.
Pronósticos (Forecasting) 7. Programación por objetivos (Goal
Programming) 8. Teoría y sistemas de inventarios (Inventory Theory and
System) 9. Programación de jornadas de trabajo (Job Scheduling)
[Link]ón lineal y entera (Linear and integer programming)
[Link] de Harkov [Link]ón de Requerimiento de Materiales
conclusión: 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. La programación entera es
una herramienta muy útil para las personas que tienen empresas, ya
que permite la administración de mejor manera de los recursos con los
que cuenta la empresa para poder aprovecharlos al máximo y así
aumentar las ganancias al máximo y poder reducir los costos. En la
actualidad es común que se disponga de paquetes de computadora para
algoritmos de programación entera en el software de programación
matemática. Estos algoritmos casi siempre se basan en la técnica de
ramificación y acotamiento o en alguna variación de ésta