UNIDAD 3:

PROGRAMACION ENTERA.
Criterios de Evaluación U3:
 Unidad 3: Programación Entera
3.1. Introducción y casos de aplicación.

¿Qué es la Programación Entera?

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.
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
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 ex-
tenso, lo que nos ha llevado a hacer una selección considerando aquellos que creemos más interesantes y
que aparecen con mayor frecuencia en la realidad.

En algunas aplicaciones, sólo 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.

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.2. Definición y modelos de programación entera.

Los modelos de Programación Entera se pueden clasificar en 2 grandes áreas: Programación Entera Mixta
(PEM) y Programación Entera Pura (PEP).
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).

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.
3.3. Método gráfico de programación entera.
El método gráfico para resolver este tipo de sistemas 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. Hay que tener en cuenta, que, en el plano, dos rectas sólo
pueden tener tres posiciones relativas (entre sí): se cortan en un punto, son paralelas o son coincidentes (la misma
recta). Si las dos rectas se cortan en un punto, las coordenadas de éste son el par (x, y) que conforman la única
solución del sistema, ya que son los únicos valores de ambas incógnitas que satisfacen las dos ecuaciones del sistema,
por lo tanto, el mismo es compatible determinado. Si las dos rectas son paralelas, no tienen ningún punto en común,
por lo que no hay ningún par de números que representen a un punto que esté en ambas rectas, es decir, que
satisfaga las dos ecuaciones del sistema a la vez, por lo que éste será incompatible, o sea sin solución. Por último, si
ambas rectas son coincidentes, hay infinitos puntos que pertenecen a ambas, lo cual nos indica que hay infinitas
soluciones del sistema (todos los puntos de las rectas), luego éste será compatible indeterminado.
3.4. Método de ramificación y acotación.

Los métodos de ramificación y acotamiento pretenden hacer lo mismo que los métodos de corte con la
diferencia de que estos utilizan la estrategia de "Dividir y Vencerás" . Esto consiste en dividir la región
factible de tal manera que la solución optima no entera no se incluya en la nueva región, dando como
resultado nuevos subproblemas a los cuales también se les llama "Métodos de Lang - Doig" y
"Métodos de bifurcación de y acotamiento" .

El proceso consta de dividir el problema y subdividir los subproblemas hasta que se pueda demostrar
que ninguno de los subproblemas tiene solución óptima mejores a una solución entera calculable.
3.5 Método heurístico para problemas binarios.

El método heurístico conocido como “IDEAL”, formulado por Bransford y Stein (1984), incluye cinco
pasos:
1. Identificar el problema;
2. Definir y presentar el problema;
3. Explorar las estrategias viables;
4. Avanzar en las estrategias;
5. Lograr la solución y volver para evaluar los efectos de las actividades.

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.
 Unidad 4
Transporte y Asignación
4.1. Definición del problema de transporte.

El problema del transporte o distribución, es un

problema de redes especial en programación lineal
que se funda en la necesidad de llevar unidades de un
punto específico llamado fuente u origen hacia otro
punto específico llamado destino. Los principales
objetivos de un modelo de transporte son la
satisfacción de todos los requerimientos establecidos
por los destinos, y claro está, la minimización de los
costos relacionados con el plan determinado por las
rutas escogidas.
 4.2. Algoritmo de transporte.

El algoritmo de transporte se basa en la hipótesis que el modelo esta balanceado y eso quiere decir que la
demanda total es igual que a la oferta total. Si el método esta desbalanceado siempre se podrá aumentar
con una fuente ficticia o destino ficticio para restaurar el equilibrio o balance.

Problema de transporte: Consiste en decidir cuántas

unidades trasladar desde ciertos puntos de origen
(platas, ciudades, etc) a ciertos puntos de destino
(centros de distribución, ciudades, etc) de modo de
minimizar los costos de transporte, dada la oferta y
demanda en dichos puntos. Se suponen conocidos los
costos unitarios de transporte, los requerimientos de
demanda y la oferta disponible.
Los principales objetivos de un modelo de transporte son la satisfacción de todos los requerimientos
establecidos por los destinos y claro está la minimización de los costos relacionados con el plan determinado
por las rutas escogidas.
El contexto en el que se aplica el modelo de transporte es amplio y puede generar soluciones atinentes al
área de operaciones, inventario y asignación de elementos.

Lo primero que se debe hacer es formular el problema en términos de programación lineal para esto se
necesita identificar las actividades y los requerimientos del problema para de esta forma formularlo como
un problema de programación lineal.

Después de formular el problema, el siguiente paso es obtener una solución básica factible, la cual se puede
obtener a partir de cualquiera de los 3 criterios siguientes:

• Método de la esquina noroeste.

• Método de la ruta preferente.
• Método de aproximación de Vogel.
4.3. Método de la Esquina Noroeste.

El método de la esquina Noroeste es un algoritmo heurístico capaz de solucionar problemas de transporte

o distribución, mediante la consecución de una solución básica inicial que satisfaga todas las restricciones
existentes, sin que esto implique que se alcance el costo óptimo total.

Este método tiene como ventaja frente a sus similares, la rapidez de su ejecución, y es utilizado con mayor
frecuencia en ejercicios donde el número de fuentes y destinos sea muy elevado.

Su nombre se debe al génesis del algoritmo, el cual

inicia en la ruta, celda o esquina Noroeste. Es
común encontrar gran variedad de métodos que se
basen en la misma metodología de la esquina
Noroeste, dado que podemos encontrar de igual
manera el método e la esquina Noreste, Sureste o
Suroeste.
4.4. Método de Costo Mínimo

El método del costo mínimo o método de los mínimos costos es un algoritmo desarrollado con el objetivo
de resolver problemas de transporte o distribución, arrojando mejores resultados que métodos como el
de la esquina noroeste, dado que se enfoca en las rutas que presentan menores costos.

Este algoritmo es mucho más sencillo que los anteriores, dado que se trata simplemente de la asignación
de la mayor cantidad de unidades posibles (sujeta a las restricciones de oferta y/o demanda) a la celda
menos costosa de toda la matriz hasta finalizar el método.
 4.5. Método de aproximación de Vogel.
El método de aproximación de Vogel es un método heurístico de resolución de problemas de
transporte, capaz de alcanzar una solución básica no artificial de inicio. Este modelo requiere de la
realización de un número generalmente mayor de iteraciones que los demás métodos heurísticos
existentes con este fin, sin embargo produce mejores resultados iniciales que los mismos.
El método consiste en la realización de un algoritmo que consta de 3 pasos fundamentales y 1 más que
asegura el ciclo hasta la culminación del método.

• Paso 1:
Determinar para cada fila y columna una medida de penalización restando los dos costos menores
en filas y columnas.

• Paso 2:
Escoger la fila o columna con la mayor penalización, es decir que de la resta realizada en el «Paso
1» se debe escoger el número mayor. En caso de haber empate, se debe escoger arbitrariamente (a
juicio personal).

• Paso 3:
De la fila o columna de mayor penalización determinada en el paso anterior debemos de escoger la
celda con el menor costo, y en esta asignar la mayor cantidad posible de unidades. Una vez se
realiza este paso una oferta o demanda quedará satisfecha por ende se tachará la fila o columna, en
caso de empate solo se tachará 1, la restante quedará con oferta o demanda igual a cero (0).
4.6. Definición del problema de asignación.

El problema de asignación consiste en encontrar la forma de asignar ciertos recursos disponibles

(máquinas o personas) para la realización de determinadas tareas al menor coste, suponiendo que cada
recurso se destina a una sola tarea, y que cada tarea es ejecutada por uno solo de los recursos. Es uno de
los problemas fundamentales de optimización combinatoria de la rama de optimización o investigación
operativa en matemática. El modelo se puede aplicar a la asignación de empleados a tareas, de fábricas a
productos, de vendedores a territorios, de postores a contratos, etc.
Con una sencilla manipulación, el método también se puede aplicar al caso en el que se pretende
maximizar cierta cantidad.

Formalmente, el problema de la asignación consiste en encontrar un emparejamiento de peso óptimo en

un grafo bipartito ponderado. El problema de asignación es un caso particular del problema de
transporte, en el que la oferta en cada origen y la demanda en cada destino son ambas de valor 1.
4.7. El Método Húngaro.

El método Húngaro es un método de optimización de problemas de asignación, conocido como tal gracias
a que los primeros aportes al método clásico definitivo fueron de Dénes König y Jenő Egerváry dos
matemáticos húngaros. El algoritmo tal como se detallará a continuación está diseñado para la
resolución de problemas de minimización únicamente, será entonces cuestión de agregar un paso
adicional para abordar ejercicios de maximización.