Programación entera

UNIDAD 3

PROGRAMACIÓN ENTERA

OBJETIVO
Formulación de modelos de optimización y aplicación de programación lineal
con variables de valores enteros; a partir de problemas en donde las empresas
buscan optimizar la función objetivo.

TEMARIO
3.1 VARIABLES ENTERAS
3.2 ALGORITMO BRANCH AND BOUND
3.3 VARIABLES BINARIAS
3.4. APLICACIÓN DE VARIABLES ENTERAS

MAPA CONCEPTUAL

Variablesenteras

Aplicaciones
de variables
enteras

Programación
entera

Variables
binarias

Algoritmo
Branch and
Bound

INTRODUCCIÓN

Programación entera es el nombre que recibe un conjunto de técnicas que
pueden usarse para encontrar la mejor solución entera posible para un
problema de programación lineal. Se utiliza para resolver problemas en que las
variables deben ser enterasy para problemas enteros mixtos, es decir, los que
tienen algunas variables enteras y algunas continuas. Es una técnica de
optimización en el sentido de que lleva a la mejor solución entera posible.
En la unidad anterior se desarrolló el método simplex de programación
lineal, el cual supone que todas las variables son continuas y generalmente da
soluciones no enteras. Cuando las variables dedecisión, como personas,
mesas o unidades de producción, no pueden subdividirse, la solución del
simplex no puede usarse en forma directa.
El redondeo de una solución óptima es peligroso, ya que no es obvio el
hecho de que la solución que resulte sea óptima o siquiera posible. Por tanto,
se tienen que emplear otros métodos cuantitativos que permitan sólo el uso de
variables enteras y quegeneren soluciones enteras. En ese sentido los
estudiosos de la investigación de operaciones han desarrollado varias técnicas
que cumplen con dichas características, entre las que se pueden citar: el
algoritmo Branch and Bound, el método de variables binarias, entre otras.
En este apartado se explican con detalle los métodos señalados, se
muestra un ejemplo desarrollado así como lascaracterísticas que lo diferencian
de otras técnicas de programación

3.1 VARIABLES ENTERAS

Objetivo

Conocer que son las variables enteras.

Las variables estudiadas en una empresa pueden ser representadas mediante
un símbolo (X, Y o cualquier letra) que puede representar a cualquier elemento
dentro de la organización. Por ejemplo la variable X puede ser un producto de
la empresa o lostrabajadores de la misma. La programación entera, se
diferencia de la programación lineal, porque los valores de las variables de
decisión sólo pueden tomar valores enteros. Así pues, las variables enteras no
pueden tomar números fraccionarios o decimales. Como ejemplo de las
variables enteras podemos citar el número de productos al día, estos pueden
ser 50 ó 120, pero no pueden ser 50.23 ni 120.32productos.

ACTIVIDADES DE APRENDIZAJE

1. Mencione 10 ejemplos de variables enteras.
2. Mencione la importancia de emplear variables enteras.

3.2 ALGORITMO BRANCH AND BOUND.

Objetivo

Conocer en qué consiste el algoritmo de Branch and Bound.

Es una herramienta que emplea algoritmos para encontrar la solución óptima
con variables enteras. Al inicio, los problemas se deben resolverempleando la
programación lineal, atreves de la cual se obtienen fracciones, es de gran
ayuda emplear el algoritmo de Branch and Bound. Éste método denominado en
español ramificación y acotamiento forma parte de la programación entera.
Puede ser usado para 2 ó más variables dependiendo del problema que se
presente.
Ramificación y acotamiento es una estrategia de búsqueda sistemática
quereduce mucho el número de combinaciones que se deben examinar.
Comienza con la solución óptima del simplex

en donde se ignoraron las

restricciones de variables enteras. Se selecciona después una variable con
valor no entero y se crean dos ramas mutuamente excluyentes. Esto da lugar a
dos nuevos problemas de programación lineal que se deben resolver. Si
ninguna solución es entera, se...