INSTITUTO TECNOLÓGICO SUPERIOR DEL OCCIDENTE DEL ESTADO DE

HIDALGO

INGENIERÍA INDUSTRIAL

PROGRAMACIÓN ENTERA

INVESTIGACIÓN DE OPERACIONES

Alumno:
 GARCÍA VICENTE JESÚS EDCEL 18011375

SEMESTRE: 4° GRUPO: “A”

PROFESOR: M.A.C. Lilia Antonia Mendoza Sierra

0

FECHA DE ENTREGA: 25-MARZO-2020

PROGRAMACIÓN ENTERA DEFINICIÓN

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. Los
creadores e investigadores de esta técnica fueron Wagner (1950) y Manne (1959),
quienes desarrollaron varios métodos de solución. 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.

A este tipo de resoluciones se les dio el nombre de métodos exactos. Por otro
lado, se desarrollaron otro tipo de técnicas que recibieron el nombre de métodos
heurísticos, los cuales hacen referencia a la intuición y conducen a una solución
próxima a la óptima en un tiempo razonable. Si se requiere que todas las variables
sean enteras 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 otro tipo de problemas sólo se permite
que las variables tomen un valor de cero o de uno; en estos casos se habla 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. En esta unidad se explicarán los algoritmos más
empleados.

1
ANÁLISIS DE TIPOS DE PROBLEMAS DE LA CLASIFICACIÓ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). A modo de ejemplo los siguientes artículos que
hemos abordado en el Blog dan cuenta de modelos de Programación Entera
Mixta:

Programación Entera Pura (PEP)

2
 En esta categoría encontramos aquellos modelos de Programación Entera que
consideran exclusivamente variables de decisión que adoptan valores enteros o
binarios. Un ejemplo de ello son las siguientes aplicaciones:

1. Problema de Asignación
2. Problema de Corte de Rollos
3. Selección de Invitados a una Boda
4. Programación de la Explotación Forestal
5. Problema de la Mochila
Notar que en los problemas anteriores (PEP) el conjunto de las soluciones
factibles (o dominio de soluciones factibles) es finito. Esto ocurrirá generalmente
con los problemas de Programación Entera (puros).

Adicionalmente resulta interesante hacer un contrastes entre las propiedades de

un modelo de Programación Lineal (PL) y uno de Programación Entera (PE). A
continuación se presentan 2 modelos de optimización que se diferencian
únicamente en que al segundo de ellos (PE) se le exige que las variables de
decisión adopten valores enteros.

Para los problemas propuestos realizamos una representación gráfica haciendo

uso del software Geogebra. El dominio de soluciones factibles del Problema Lineal
(PL) corresponde al área achurada de color verde. Por otro lado el dominio de
soluciones factibles del Problema Entero (PE) es enumerable y corresponde a las
coordenadas denotadas por A, E, F, B, G, H, I, J, K, C, L, M, D (que es
un subconjunto del dominio de factibilidad del PL). En este caso en particular la
solución óptima de ambos problemas coincide (en el vértice C), no obstante,
perfectamente podrían ser distintas (bastaría con modificar los parámetros del
problema).

3
En este contexto y dada la naturaleza de los problemas propuestos, el valor
óptimo del Problema Lineal (PL) será una cota superior del valor óptimo del
Problema Entero (PE). También se concluye que el dominio de soluciones
factibles de un modelo de Programación Lineal (cuando existe) representa un
conjunto convexo (los problemas de Programación Lineal son convexos) y en el
caso del problema de Programación Entera Pura su conjunto de soluciones
factibles es discreto.

Adicionalmente según tratamos en el artículo Por qué no aparece el Informe de

Confidencialidad (o Informe de Sensibilidad) en Solver de Excel se debe tener en
cuenta que en la utilización de software para la resolución computacional del
modelos de Programación Entera no tendremos acceso a los reportes de
sensibilidad como en el caso de la implementación de modelos de Programación
Lineal. De esta forma ante la necesidad de analizar el impacto en los resultados
ante la modificación de los parámetros del problema será necesario reoptimizar
ante la información que brinde el o los nuevos escenarios.
4
 PROGRAMACIÓN ENTERA
DEFINICIÓN:
Un modelo de programación entera es aquel que contiene restricciones y una
función objetivo idénticas a la formuladas en programación lineal , la única
diferencia en que una o más variables de decisión deben tomar valor entero en
la solución final.

CLASIFICACIÓN:
Existen tres tipos de modelos por programación entera

A) PURA : Son modelos similares a los de programación entera

Forma General :
Max (Min ) = A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn
Sujeto a : A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn >= (<=)(=) Bi
No negatividad : Xi >= 0 y ENTERO

B) BINARIA : Estos modelos lineales , las variables sólo toman valores 0 y 1 , son
usadas para uso probabilistico Donde 0 se rechaza la opción y 1 se acepta
la opción
Forma General :
Max (Min ) = A1Y1+A2Y2+A3Y3+A4Y4+A5Y5+..........+AnYn
Sujeto a : y1+y2+y3+y4+..........+yn >= (<=)(=) Bi
No negatividad : yi >= 0 v 1

C) MIXTA : En estos tipos de modelos , integra las variables puras y las mixtas
Max (Min )

5
= A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn+A1Y1+A2Y2+A3Y3+A4Y4+A5Y
5+..........+AnYn

Sujeto a :
A1X1+A2X2+A3X3+A4X4+A5X5+..........+AnXn >= (<=)(=) Bi
y1+y2+y3+y4+..........+yn >= (<=)(=) Bi
No negatividad :
Xi >= 0 y ENTERO
Xi >= 0 v 1

* Tipos de Restricciones Usadas en la Programación Entera Mixta :

1) Excluyentes : Solo sirve para elegir una alternativa de varias posibles
2) Pre-requisito : Cuando necesitas realizar una acción antes de proceder con la
siguiente
3) Incluyente : Dicha restricción se da para cuando realizas una acción "A"
entonces debes hacer la acción "B"
4) Costo Fijo : Cuando se nombra un costo fijo , es sinónimo de uso de variable
mixta

Ejemplo Aplicativo

Un problema que afronta todos los días un electricista consiste en decidir

qué generadores conectar. El electricista en cuestión tiene tres generadores con
las características que se muestran en la tabla 3. Hay dos periodos en el día. En el
primero se necesitan 2900 megawatts. En el segundo. 3900 megawatts. Un
generador que se conecte para el primer periodo puede ser usado en el segundo
sin causar un nuevo gasto de conexión. Todos los generadores principales (como
lo son A, B y C de la figura ) son apagados al término del día. Si se usa el
6
generador A también puede usarse el generador C,no se usa generador B si se
usa generador A. Formule este problema como un PLEM.

GENERADOR COSTO FIJO DE COSTO POR CAPACIDAD

PERIODO POR MAXIMA EN CADA
CONEXIÓN
MEGAWATT PERIODO ( MW )
USADO

A $ 3000 $5 2100

B 2000 4 1800

C 1000 7 3000

V.D.

Xij= Número de megawatts a usar del generador i(i=A,B,C) en el periódo j(j=1,2).

Yi= 0 No arranca el generador i(i=A,B,C)

1 Si arranca el generador i(i=A,B,C)

Restricciones:

Demanda en el periodo 1:

7
 xa1 +xb1+xc1 >= 2900

Demanda en el periodo 2:

xa2+xb2+xc2>= 3900

Capacidad de generador A:

xa1 <= 2100y1( enlace variable entera con variable binaria)

xa2<=2100y1( enlace variable entera con variable binaria)

Capacidad de generador B:

xb1<=1800y2( enlace variable entera con variable binaria)

xb2<=1800y2( enlace variable entera con variable binaria)

Capacidad de generador C:

xc1<=3000y3( enlace variable entera con variable binaria)

xc2<=3000y3( enlace variable entera con variable binaria)

Función Objetivo:

Minimizar(z)= 5(x11+x12) +4(x21+x22) + 7(x31+x32) +3000(y1)+2000(y2) +

1000(y3)

INVESTIGACIÓN DE OPERACIONES: APLICACIONES Y ALGORITMOS –

WAYNE L. WINSTON
8
La universidad estatal tiene que comprar 1100 computadoras de tres vendedores.
El vendedor 1 carga 500 dólares por computadora más un cargo por la entrega de
5000 dólares. El vendedor 2 carga 350 dólares por computadora más un cargo por
la entrega de 4000 dólares. El vendedor 3 carga 250 dólares por computadora
más un cargo por la entrega de 6000 dólares El vendedor 1 venderá a la
universidad a lo más 500 computadoras, el vendedor 2 cuando mucho 900 y el
vendedor 3 cuando más 400. Plantee un PE para minimizar el costo de la compra
de las computadoras necesarias
SOLUCIÓN:

Costo Cargo x
Proveedor Condiciones
Unitario Entrega
1 500 5000 A lo más 500
2 350 4000 Cuanto mucho
900
3 250 6000 A lo más 400

Variables de Decisión:
Xi = Cantidad de computadoras a comprar del proveedor i (i = 1, 2,3)
Yi = Decisión de compra de computadoras a comprar del proveedor i (i = 1, 2,3)
basándose en el costo fijo
Función Objetivo:
Min Z = 500X1 + 350X2 + 250X3 + 5000Y1 + 4000Y2 + 6000Y3
Restricciones:
X1 <= 500
X2 <= 900
X3 <= 400
X1 + X2 + X3 <= 1100
Xi >= 0 y ENTERO
Yi = 0, 1

9
Hallco tiene un turno diurno y un turno nocturno No importa cuantas unidades se
producen, el único costo de producción durante un turno es un costo de
preparación Cuesta 8000 dólares la corrida del día y 4500 dólares la corrida de la
noche. la demanda para los dos días siguientes es como se indica: Día 1, 2000;
noche 1, 3000; Día 2, 2000; noche 2, 3000. Cuesta un dólar por unidad conservar
una unidad en inventario durante un turno. Determine un programa de producción
que minimice la suma de los costos de preparación y de inventario. se debe
cumplir con la demanda justo a tiempo

SOLUCIÓN

Variables de Decisión:
Xi = Cantidad de productos a fabricar en el turno i (i = 1, 2) y en el día j (j=1,2)
Yi = Decisión de fabricación en el turno i (i = 1, 2,) y en el día j (j=1,2) basándose
en el costo fijo
Función Objetivo:
Min Z = X11 + X12 + X21 + X22 8000(Y11 + Y12) + 3500(Y21 + Y22)
Restricciones:
X11 <= 2000
X12 <= 3000
X21 <= 2000
X22 <= 3000
Xi >= 0 y ENTERO
Yi = 0, 1

10
11
 Método Gráfico

El método gráfico es una forma fácil y rápida para la solución de problemas de

Programación Lineal, siempre y cuando el modelo conste de dos
variables. Para modelos con tres o más variables, el método gráfico es
imposible.

Características

Consiste en representar geométricamente las restricciones, condiciones

técnicas y función objetivo objetivo.

Los pasos necesarios para realizar el método son:

1. hallar las restricciones del problema

2. Las restricciones de no negatividad Xi ≥ 0 confían todos los valores posibles.

3. sustituir ≥ y ≤ por (=) para cada restricción, con lo cual se produce la

ecuación de una línea recta.

4. trazar la línea recta correspondiente a cada restricción en el plano. La

región en cual se encuentra cada restricción, el área correspondiente a cada
restricción lo define el signo correspondiente a cada restricción (≥ ó ≤) se
evalúa un punto antes y después de la recta trazada, el punto que cumpla con
la inecuación indicara el área correspondiente

5. el espacio en el cual se satisfacen las tres restricciones es el área factible

Cada punto situado en la frontera del espacio del área factible, es decir que
satisfacen todas las restricciones, representa un punto factible.

6. Las líneas paralelas que representan la función objetivo se trazan mediante la

asignación de valores arbitrarios a fin de determinar la pendiente y la dirección en la
cual crece o decrece el valor de la función objetivo.

7. la solución óptima puede determinarse al observar la dirección en la cual

aumenta la función objetivo, se procede a graficar la función objetivo, si es un
problema de minimización la solución óptima es el primer punto factible que
toque la función Z, y si por lo contrario es un problema de maximización, será
entonces el último de los puntos factibles que toque la función Z

Hay principalmente cuatro tipos de problemas, de única solución, multiples

soluciones, solución no acotada y no factible, a continuación hay un ejemplo de
cada caso, en el cual se puede observar la comparación de la solución
obtenida con el método gráfico, y la solución obtenida con el método simplex.

El problema

La fábrica de Hilados y Tejidos «SALAZAR» requiere fabricar dos tejidos de

calidad diferente T y T‟; se dispone de 500 Kg de hilo a, 300 Kg de hilo b y 108
Kg de hilo c. Para obtener un metro de T diariamente se necesitan 125 gr de a,
150 gr de b y 72 gr de c; para producir un metro de T‟ por día se necesitan 200
gr de a, 100 gr de b y 27 gr de c. El T se vende a $4000 el metro y el T‟ se
vende a $5000 el metro. Si se debe obtener el máximo beneficio, ¿cuántos
metros de T y T‟ se deben fabricar?

Variables

XT: Cantidad de metros diarios de tejido tipo T a fabricar

XT‟: Cantidad de metros diarios de tejido tipo T‟ a fabricar

Restricciones

0,12XT + 0,2XT‟ <= 500 Hilo “a”

0,15XT + 0,1XT‟ <= 300 Hilo “b”

0,072XT + 0,027XT‟ <= 108 Hilo “c”

Las restricciones de no negatividad no son necesarias en este ejemplo dado
que se trata de un ejercicio de maximización, cuando el ejercicio sea de
minimización lo más recomendado es incluirlas.

Función objetivo

ZMAX = 4000XT + 5000XT‟

Solución mediante método gráfico

Paso 1: Graficar las restricciones

Para iniciar con el trazado de las restricciones es indispensable igualar las

restricciones a 0, de esta manera podemos mediante despeje de ecuaciones
iniciar con la tabulación que nos otorgará las coordenadas para esbozar cada
una de las gráficas. Además dado que se trabajará en el plano cartesiano sería
prudente renombrar las variables

XT = x

XT‟ = y

Igualamos las restricciones,

0,12X + 0,2y = 500

0,15X + 0,1y = 300

0,072X + 0,027y = 108

Acto seguido iniciamos con la primera restricción, hallamos las primeras dos
coordenadas. Para hallar las coordenadas regularmente llevamos una de las
variables a cero, para de esta manera despejar más fácilmente la segunda.

Por ejemplo, para un x = 0

0,12(0) + 0,2y = 500

0,2y = 500

500/0,2 = y

2500 = y

y para un y = 0

0,12x + 0,2(0) = 500

0,12x = 500

x = 500/0,12

x = 4167
Seguimos con la segunda restricción

Pasamos a la tercera restricción

En el siguiente gráfico se muestra el polígono solución de color gris, en este
conjunto es donde cada coordenada cumple con todas las restricciones, las
cuales se caracterizan por ser restricciones de menor o igual y esta
característica se representa con una flecha hacía abajo.
Una vez se llega a este punto es indispensable saber que las soluciones
óptimas se alojan en los vértices del polígono solución (color gris) y que
identificar a la solución óptima es cuestión de elegir la mejor alternativa
dependiendo de las herramientas disponibles (tecnológicas y conocimientos
matemáticos).
La primera opción es la geométrica, esta depende de trazar la ecuación que
representa a la función objetivo (este paso consiste en realizar el mismo
procedimiento de las restricciones).

Función objetivo,

ZMAX = 4000x + 5000y

luego igualamos a 0.
4000x + 5000y = 0
Luego tabulamos para obtener las coordenadas necesarias para esbozar la
gráfica correspondientes a la ecuación (en esta ocasión es recomendable más
de dos coordenadas, incluyendo la coordenada (x = 0, y = 0).
Una vez se ha esbozado la función objetivo (línea negra) sacamos replicas
paralelas a esta que se encuentren con cada vértice, y solo en el caso en que
la línea imaginaria paralela a la función objetivo no corte el polígono solución
se ha encontrado la solución óptima. En otras palabras trasladamos la función
objetivo por todo el polígono conservando su forma paralela con la original, la
detenemos en los vértices y evaluamos si esta corta o no el conjunto solución.

Claramente solo en el punto «B», es decir en el vértice formado por la

intersección de las ecuaciones 1 y 2, la línea imaginaria no corta el polígono
solución, entonces es este punto el correspondiente a la coordenada óptima.
Para hallar el valor de esta coordenada es indispensable recurrir a la resolución
de ecuaciones lineales 2×2, y se pueden considerar varios métodos de
solución entre ellos:
 Método por sustitución
 Método por igualación
 Método por reducción o Eliminación
 Método por eliminación Gauss
 Método por eliminación Gauss – Jordán
 Método por determinantes
Así entonces, se dispone de gran cantidad de métodos, uno de los más
utilizados es el método de reducción o eliminación, el cual es muy sencillo de
aplicar.
El método por reducción o eliminación consiste en igualar los coeficientes de
una de las variables multiplicando una o las dos ecuaciones, teniendo en
cuenta que estos coeficientes queden iguales pero con signos contrarios.

Ecuación 1 0,12x + 0,2y = 500

Ecuación 2 0,15x + 0,1y = 300 multiplicamos por (-2)
Ecuación 3 (2*(-2)) -0,30x – 0,2y = -600
Sumamos 1 y 3 -0,18x = -100
Despejamos «x» x = -100 / (-0,18)

x = 555,55

Luego reemplazamos x = 555,55 en cualquiera de las dos ecuaciones originales con

el objetivo de despejar «y».

Ecuación 1 0,12x + 0,2y = 500

Reemplazamos «x» 0,12(555,55) + 0,2y = 500

Despejamos «y» 66,666 + 0,2y = 500

0,2y = 500 – 66,666

0,2y = 433,334

y = 433,334 / 0,2

y = 2166,67

De esta forma hemos obtenido los valores para «x» y «y».

Recordemos que x y y fueron los nombres que recibieron las variables originales XT
y XT’
x = XT

y = XT’

XT =

555,55

XT’ = 2166,67

Y la contribución obtenida (reemplazando las variables en la función objetivo) es

de:

Zmax = 4000XT + 5000XT’

Zmax = 4000(555,55) + 5000(2166,67)

Zmax = 13.055.550

Ahora podemos cotejar los resultados con los obtenidos mediante resolución
por Solver – Excel, sin embargo recuerden que el método de búsqueda de la
solución óptima en el método gráfico que utilizamos es el geométrico y que
existe una posibilidad mucho más compleja pero igualmente efectiva, este es el
método de iteración por vértice, y que consiste en hallar todas las coordenadas
de los vértices y luego en cada coordenada se evalúa la función objetivo, (cada
coordenada nos proporciona un valor en «x» y otro en «y», luego
reemplazamos estos valores en la función objetivo «4000x + 5000y = ?» y
luego evaluamos los resultados seleccionando la mayor cantidad).

Variantes en el método gráfico

Como en la mayoría de los casos, el ejemplo con el que aquí se explicó el
método gráfico es el ideal, es decir un ejercicio de conjunto acotado con
solución óptima única, sin embargo existen una variedad de problemas
diferentes a los ideales y que vale la pena analizar:
 MÉTODO DE RAMIFICACIÓN Y ACOTACIÓN

Definición 5.4.1 (Problema relajado) Dado un problema lineal entero, se llama

problema relajado al mismo modelo lineal pero prescindiendo de la restricción
de que las variables sean enteras.

Problema entero: PE Problema relajado: PR

max z = cT x max z = cT x

sujeto a sujeto a
Ax ≤ b Ax ≤ b
x ≥ 0y entero x≥0

El problema relajado es una versión menos restringida del problema entero.

Esto significa que la región factible para cualquier problema entero esta´
contenida en la región factible del problema relajado correspondiente. Para el
caso de maximización de un problema entero se verifica que

∗ ∗

.
PR PE

Definición 5.4.2 (Solución candidata) Dado un problema entero, en cada

iteración del proceso de resolución llamamos solución candidata a la mejor
solución entera obtenida hasta el momento.

Dado que la solución candidata puede ser la solución óptima del problema
entero, una vez obtenida una solución candidata se debe mantener hasta
obtener otra mejor. El valor de la función objetivo para la solución candidata
fija una cota inferior zI para el problema entero. Esta cota sirve para cortar las
ramas donde la función objetivo sea menor o igual que zI porque indica que
en esas ramas no se encuentra la solución óptima del problema entero. Un
problema de ese tipo es llamado problema terminal. Además, también son
problemas terminales aquellos que tienen un valor objetivo mayor que la cota
inferior pero cuya solución es entera; en este caso esta solución pasa a ser
la candidata y se actualiza la cota inferior. Por último, un problema es terminal
si es infectable.

En el algoritmo denotamos por zS el valor óptimo de la función objetivo en

cada problema que, como hemos dicho, es una cota superior para el
problema entero en esa rama.
Algoritmo de ramificación y acotación

Objetivo maximizar.

Paso 1. Inicialización. Resolver el problema lineal relajado

asociado al problema entero.

Si la solución óptima es entera parar y esa solución es óptima también

para el problema entero.

En otro caso, fijar una cota inferior zI para el valor óptimo del problema
entero. Si no se conoce ninguna solución candidata para el
problema entero, hacer zI = −∞.

Paso 2. Ramificación. Seleccionar un problema no terminal. En dicho

problema elegir una variable xj que, teniendo que ser entera, tome un valor no
entero en la solución actual. Crear dos nuevos problemas añadiendo al
problema las restricciones xj ≤ [xj] , xj ≥ [xj] + 1.

Paso 3. Acotación. Resolver cada uno de los dos problemas recién creados
en el paso de ramificación.

Paso 4. Problemas terminales. Analizar los problemas que puedan con-

tener la solución óptima y considerar terminales los que cumplen una de las
siguientes condiciones:

(1) El problema es infectable.

(2) zS ≤ zI.

(3) zS > zI y la solución es entera. Se actualiza la cota inferior haciendo

zI = zS y esta solución entera es la solución candidata.

Si todos los problemas son terminales, la solución candidata es la solución

óptima. Si no hay solución candidata el problema entero es infectable.

Si hay problemas no terminales, volver al Paso 2 para continuar con el pro-

ceso de ramificación.
 [xj] indica la parte entera de la variable xj.
Para resolver estos problemas se utilizan las técnicas de ana´lisis de sensibilidad.
Concreta- mente el algoritmo que se utiliza para calcular la solución de los nuevos
problemas es el simplex dual pesar de que el proceso de búsqueda de la solución óptima
requiere gran cantidad de cálculos, éste es el algoritmo más utilizado para resolver
problemas enteros puros y mixtos.
Se pueden ahorrar iteraciones si en el Paso 2 se seleccionan el
problema para ramificar y la variable para acotar siguiendo
determinados criterios. Un criterio sencillo para elegir problema es el
de la mejor cota, es decir, elegir para ramificar el problema que tenga
mayor valor para la función objetivo. Los criterios de selección de
variables son más complicados y no se estudian es este tema,
elegiremos la variable para ramificar al azar.

Ejemplo. Resolver el problema de la paginá 147 utilizando el

algoritmo de ramificación y acotación.

Primera iteracio´n.

Paso 1. Inicialización. Resolver el problema relajado. La tabla óptima es

x1 x2 x3 x4
0 0 20 5 440
12 1
a2 0
7
a1 1

Inicializar la cota inferior: zI = −∞.

Paso 2. Ramificacio´n. La solución del problema relajado no es
entera. Elegi- mos para ramificar la variable x1 y se crean dos nuevos
problemas: el problema P2 y el problema P3 de la paginá 150.

Paso 3. Acotacio´n. Resolvemos cada uno de estos problemas

utilizando las técnicas de análisis de sensibilidad.

Solución del problema P2. En la tabla óptima del PR se introduce la

res- tracción x1 ≤ 3, sumando la correspondiente variable de holgura,
x5. Se tiene la siguiente tabla:

x1 x2 x3 x4 x5
0 0 20 5 0 440
12 −1 24
a2 0 1 7
0 7

a1 1 0 −5 1
7
0 25
7
a5 1 0 0 0 1 3
 Operación elemental en la fila 3 de la tabla: fila 3 − fila 2.

x1 x2 x3 x4 x5
0 0 20 5 0 440
a2 0 1 12
7 −17 0 24
7

a1 1 0 −57 1
7 0 25
7

a5 0 0 5 − 1 1 −4
7 7 7

Esta tabla no tiene factibilidad primal. Aplicando el algoritmo simplex dual se tiene la
siguiente tabla que es óptima para el problema P2.

x1 x2 x3 x4 x5
0 0 45 0 35 420
a2 0 1 1 0 −1 4
a1 1 0 0 0 1 3
a4 0 0 −5 1 −7 4

Solución del problema P3. Partiendo de la tabla óptima del PR, para añadir
la restricción x1 ≥ 4 se multiplica por −1, −x1 ≤ −4, para poder sumar una variable
de holgura x5 que permite ampliar la base. Se tiene la siguiente tabla:

x1 x2 x3 x4 x5
0 0 20 5 0 440
a2 0 1 12 −1 0 24
7
1 25
a1 1 0 −5 7
0 7
a5 −1 0 0 0 1 −4

Hacer la siguiente operación elemental: fila 3 + fila 2.

 x1 x2 x3 x4 x5
0 0 20 5 0 440
a2 0 1 12
7 −17 0 24
7

a1 1 0 −57 1
7 0 25
7

a5 0 0 −5 1 1 −3
7 7 7

La tabla no tiene factibilidad primal. Aplicando el simplex dual se tiene la

tabla que es óptima para el problema P3.

x1 x2 x3 x4 x5
0 0 0 9 28 428
1 12 12
a2 0 1 0 5 5 5
a1 1 0 0 0 −1 4

Tenemos así las soluciones del problema P2 y del problema P3 del

diagrama de la Figura 5.4.
Paso 4. Problemas terminales. El problema P2 es terminal porque zS =
420 > zI y, además, la solución es entera, xS = (3, 4). Esta solución es
candidata y actualizamos zI = zS = 420. El problema P3 no es terminal
porque no cumple ninguno de los criterios del Paso 4.
Hay problemas no terminales y volvemos al Paso 2.

Segunda iteración.

Paso 2. Ramificación. Seleccionamos un problema no terminal. En este

caso solo tenemos un problema no terminal, el problema P3.
Seleccionamos en dicho problema una variable; en este caso
seleccionamos la variable x2 que es la u „nica variable no entera.
Ramificamos añadiendo al problema P3 la restricción x2 ≤ 2 para crear el
problema P4 y x2 ≥ 3 para crear el P5 (ver paginá 152).
Paso 3. Acotación. Resolver los dos problemas recién creados. Para ello
procedemos como en la iteración anterior siendo en este caso la tabla de
partida la tabla óptima para el problema P3. Se obtienen las soluciones
recogidas en el diagrama de la Figura 5.4.
Paso 4. Problemas terminales.
El problema P5 es terminal por ser infactible. El problema P4 tiene un valor zS
= 422.8 > zI = 420 y la solución no es entera. Por tanto, no es terminal. Volver al
Paso 2.

Tercera iteración.

Paso 2. Ramificación. Elegimos para ramificar el problema P4 que es el único

no terminal. Seleccionamos la variable x1 por ser la única no entera. Se crean
así dos nuevos problemas, el problema P6 y el problema P7 (ver paginá 153).

Paso 3. Acotación. Resolver los dos problemas recién creados. Para ello
procedemos como en la primera iteración siendo en este caso la tabla de
partida la tabla óptima para el problema P4. Se obtienen las soluciones
recogidas en el diagrama de la Figura 5.4.

Paso 4. Problemas terminales.

El problema P6 es terminal porque zS = 410 < zI = 420. El problema P7 es terminal

porque zS = 400 < zI = 420.
Todos los problemas son terminales. La solucio´n candidata es la
solución óptima del problema entero

x∗ = 3, x∗ = 4, z∗ = z = 420.
1 2 PE I

0
 Definición y características del método heurístico para problemas binarios

Los métodos descritos en este libro reciben el nombre de algoritmos heurísticos,

metaheurísticos o sencillamente heurísticos. Este término deriva de la palabra griega
heuriskein que significa encontrar o descubrir y se usa en el ámbito de la
optimización para describir una clase de algoritmos de resolución de problemas.

En el lenguaje coloquial, optimizar significa poco más que mejorar; sin embargo, en
el contexto científico la optimización es el proceso de tratar de encontrar la mejor
solución posible para un determinado problema. En un problema de optimización
existen diferentes soluciones, un criterio para discriminar entre ellas y el objetivo es
encontrar la mejor. De forma más precisa, estos problemas se pueden expresar
como encontrar el valor de unas variables de decisión para los que una determinada
función objetivo alcanza su valor máximo o mínimo. El valor de las variables en
ocasiones está sujeto a unas restricciones.

Podemos encontrar una gran cantidad de problemas de optimización, tanto en la

industria como en la ciencia. Desde los clásicos problemas de diseño de redes de
telecomunicación u organización de la producción hasta los más actuales en
ingeniería y re-íngeniería de software, existe una infinidad de problemas teóricos y
prácticos que involucran a la optimización.

Algunas clases de problemas de optimización son relativamente fáciles de resolver.

Este es el caso, por ejemplo, de los problemas lineales, en los que tanto la función
objetivo como las restricciones son expresiones lineales. Estos problemas pueden
ser resueltos con el conocido método Simplex; sin embargo, muchos otros tipos de
problemas de optimización son muy difíciles de resolver. De hecho, la mayor parte
de los que podemos encontrar en la práctica entran dentro de esta categoría.

La idea intuitiva de problema “difícil de resolver” queda reflejada en el término

científico NP-hard utilizado en el contexto de la complejidad algorítmica. En términos
coloquiales podemos decir que un problema de optimización difícil es aquel para el
que no podemos garantizar el encontrar la mejor solución posible en un tiempo
razonable. La existencia de una gran cantidad y variedad de problemas difíciles, que
aparecen en la práctica y que necesitan ser resueltos de forma eficiente, impulsó el
desarrollo de procedimientos eficientes para encontrar buenas soluciones aunque no
fueran óptimas. Estos métodos, en los que la rapidez del proceso es tan importante
cómo la calidad de la solución obtenida, se denominan heurísticos o aproximados.
En Díaz y otros (1996) se recogen hasta ocho definiciones diferentes de algoritmo
heurístico, entre las que destacamos la siguiente:

“Un método heurístico es un procedimiento para resolver un problema de

optimización bien definido mediante una aproximación intuitiva, en la que
la estructura del problema se utiliza de forma inteligente para obtener una
buena solución.”

En contraposición a los métodos exactos que proporcionan una solución óptima del
problema, los métodos heurísticos se limitan a proporcionar una buena solución del
problema no necesariamente óptima. Lógicamente, el tiempo invertido por un
método exacto para encontrar la solución óptima de un problema difícil, si es que
existe tal método, es de un orden de magnitud muy superior al del heurístico
(pudiendo llegar a ser tan grande en muchos casos, que sea inaplicable).

En este texto consideraremos los llamados problemas de Optimización

Combinatoria. En estos problemas el objetivo es encontrar el máximo (o el mínimo)
de una determinada función sobre un conjunto finito de soluciones que denotaremos
por S. No se exige ninguna condición o propiedad sobre la función objetivo o la
definición del conjunto S. Es importante notar que dada la finitud de S, las variables
han de ser discretas, restringiendo su dominio a una serie finita de valores.
Habitualmente, el número de elementos de S es muy elevado, haciendo
impracticable la evaluación de todas sus soluciones para determinar el óptimo.

En los últimos años ha habido un crecimiento espectacular en el desarrollo de

procedimientos heurísticos para resolver problemas de optimización. Este hecho
queda claramente reflejado en el gran número de artículos en publicados en revistas
especializadas. En 1995 se edita el primer número de la revista Journal of Heuristics
dedicada íntegramente a la difusión de los procedimientos heurísticos.

Aunque hemos mencionado el caso de la resolución de un problema difícil, existen

otras razones para utilizar métodos heurísticos, entre las que podemos destacar:
  El problema es de una naturaleza tal que no se conoce ningún método exacto
para su resolución.

 Aunque existe un método exacto para resolver el problema, su uso es

computacionalmente muy costoso.

 El método heurístico es más flexible que un método exacto, permitiendo, por

ejemplo, la incorporación de condiciones de difícil modelización.

 El método heurístico se utiliza como parte de un procedimiento global que

garantiza el óptimo de un problema. Existen dos posibilidades:

- El método heurístico proporciona una buena solución inicial de partida.

- El método heurístico participa en un paso intermedio del procedimiento,
como por ejemplo las reglas de selección de la variable a entrar en la base
en el método Simplex.

Al abordar el estudio de los algoritmos heurísticos podemos comprobar que

dependen en gran medida del problema concreto para el que se han diseñado. En
otros métodos de resolución de propósito general, como pueden ser los algoritmos
exactos de Ramificación y Acotación, existe un procedimiento conciso y
preestablecido, independiente en gran medida del problema abordado. En los
métodos heurísticos esto no es así. Las técnicas e ideas aplicadas a la resolución de
un problema son específicas de éste y aunque, en general, pueden ser trasladadas a
otros problemas, han de particularizarse en cada caso. Así pues, es necesario
referirse a un problema concreto para estudiar con detalle los procedimientos
heurísticos.

En los capítulos segundo y tercero se describen los métodos heurísticos. Hemos

seleccionado el Problema del Viajante para describir estos métodos por cumplir una
serie de propiedades que lo hacen especialmente indicado. Dicho problema puede
enunciarse del siguiente modo:

“Un viajante de comercio ha de visitar n ciudades, comenzando y finalizando en

su propia ciudad. Conociendo el coste de ir de cada ciudad a otra, determinar el
recorrido de coste mínimo.”

En la siguiente sección introducimos algunos otros problemas combinatorios que

también nos ayudaran a explicar e ilustrar algunas de las técnicas así como a
plantear ejercicios para el estudiante. Podemos citar las siguientes razones por las
que el problema del viajante ha recibido una especial atención.

 Resulta muy intuitivo y con un enunciado muy fácil de comprender.

 Es extremadamente difícil de resolver por lo que resulta un desafío constante para

los investigadores del área.

 Es uno de los que mas interés ha suscitado en Optimización Combinatoria y sobre

el que se ha publicado abundante material.

 Sus soluciones admiten una doble interpretación: mediante grafos y mediante

permutaciones, dos herramientas de representación muy habituales en problemas
combinatorios, por lo que las ideas y estrategias empleadas son, en gran medida,
generalizables a otros problemas.

 La gran mayoría de las técnicas que han ido apareciendo en el área de la

Optimización Combinatoria han sido probadas en él, puesto que su resolución es
de gran complejidad.

Existen muchos métodos heurísticos de naturaleza muy diferente, por lo que es

complicado dar una clasificación completa. Además, muchos de ellos han sido
diseñados para un problema específico sin posibilidad de generalización o aplicación
a otros problemas similares. El siguiente esquema trata de dar unas categorías
amplias, no excluyentes, en donde ubicar a los heurísticos mas conocidos:

Métodos de Descomposición
El problema original se descompone en subproblemas mas sencillos de resolver,
teniendo en cuenta, aunque sea de manera general, que ambos pertenecen al
mismo problema.

Métodos Inductivos
La idea de estos métodos es generalizar de versiones pequeñas o más sencillas al
caso completo. Propiedades o técnicas identificadas en estos casos más fáciles de
analizar pueden ser aplicadas al problema completo.
Métodos de Reducción
Consiste en identificar propiedades que se cumplen mayoritariamente por las buenas
soluciones e introducirlas como restricciones del problema. El objeto es restringir el
espacio de soluciones simplificando el problema. El riesgo obvio es dejar fuera las
soluciones óptimas del problema original.

Métodos Constructivos
Consisten en construir literalmente paso a paso una solución del problema.
Usualmente son métodos deterministas y suelen estar basados en la mejor elección
en cada iteración. Estos métodos han sido muy utilizados en problemas clásicos
como el del viajante.

Métodos de Búsqueda Local

A diferencia de los métodos anteriores, los procedimientos de búsqueda o mejora
local comienzan con una solución del problema y la mejoran progresivamente. El
procedimiento realiza en cada paso un movimiento de una solución a otra con mejor
valor. El método finaliza cuando, para una solución, no existe ninguna solución
accesible que la mejore.

Si bien todos estos métodos han contribuido a ampliar nuestro conocimiento para la
resolución de problemas reales, los métodos constructivos y los de búsqueda local
constituyen la base de los procedimientos metaheurísticos. Por ello, estudiaremos en
el capítulo segundo los métodos constructivos en el problema del viajante y en el
capítulo tercero los métodos de búsqueda local en este mismo problema. El lector
podrá encontrar alusiones a lo largo del texto a cualquiera de los métodos de
descomposición, inductivos o de reducción, pero no dedicaremos una sección
específica a su estudio. Alternativamente, prestaremos especial atención a los
métodos resultantes de combinar la construcción con la búsqueda local y sus
diferentes variantes en el capítulo tercero, puesto que puede considerarse un punto
de inicio en el desarrollo de método metaheurísticos.

En los últimos años han aparecido una serie de métodos bajo el nombre de
Metaheurísticos con el propósito de obtener mejores resultados que los alcanzados
por los heurísticos tradicionales. El término metaheurístico fue introducido por Fred
Glover en 1986. En este libro utilizaremos la acepción de heurísticos para referirnos
a los métodos clásicos en contraposición a la de metaheurísticos que reservamos
para los más recientes y complejos. En algunos textos podemos encontrar la
expresión “heurísticos modernos” refiriéndose a los meta-heurísticos (Reeves, 1995)
tal y como se menciona: "The modern-coin comes from ... the way they attempt to
simulate some naturally-occurring process.".. Los profesores Osman y Kelly (1995)
introducen la siguiente definición:

“Los procedimientos Metaheurísticos son una clase de métodos aproximados

que están diseñados para resolver problemas difíciles de optimización
combinatoria, en los que los heurísticos clásicos no son efectivos. Los
Metaheurísticos proporcionan un marco general para crear nuevos algoritmos
híbridos combinando diferentes conceptos derivados de la inteligencia artificial,
la evolución biológica y los mecanismos estadísticos”

Los procedimientos Meta-Heurísticos se sitúan conceptualmente “por encima” de los

heurísticos en el sentido que guían el diseño de éstos. Así, al enfrentarnos a un
problema de optimización, podemos escoger cualquiera de estos métodos para
diseñar un algoritmo específico que lo resuelva aproximadamente. En Glover (1986)
se introduce dicha idea según:

“A metaheuristic refers to a master strategy that guides and modifies other

heuristics to produce solutions beyond those that are normally generated in a
quest for local optimality. The heuristics guided by such a meta-strategy may be
high level procedures or may embody nothing more than a description of
available moves for transforming one solution into another, together with an
associated evaluation rule”.

Otras definiciones más recientes son:

“An iterative master process that guides and modifies the operations of
subordinate heuristics to efficiently produce high-quality solutions. It may
manipulate a complete (or incomplete) single solution or a collection of solutions
at each iteration. The subordinate heuristics may be high (or low) level
procedures, or a simple local search, or just a construction method." Voß et al
(1997)
 “It is a heuristic framework which combines a non-problem-specific control
procedure with a subordinate heuristic in order to commonly find better
solutions than the latter one would be able on its own. The control process
mentioned can be implemented for different problems without changing its
ingredients significantly.” Greistorfer (2000)

En estos momentos existe un gran desarrollo y crecimiento de estos métodos. En

este libro vamos a limitarnos a aquellos procedimientos relativamente consolidados y
que han probado su eficacia sobre una colección significativa de problemas.
Específicamente consideraremos en el capítulo quinto la Búsqueda Tabú, en el sexto
el Templado Simulado y en el séptimo los diferentes Métodos Evolutivos, incluyendo
los Algoritmos Genéticos y la Búsqueda Dispersa (Scatter Search). Los métodos
GRASP junto con los Multi-Arranque han sido incluidos en el capítulo cuarto de
Métodos Combinados que sirve de “puente” entre los métodos heurísticos y los
metaheurísticos.

Es importante notar que para la correcta compresión y asimilación de los métodos

descritos, resulta indispensable su puesta en práctica, para lo cual el lector deberá
programar en un ordenador los algoritmos descritos y resolver algún problema de
optimización combinatoria. Recomendamos utilizar algún lenguaje de programación
de relativo bajo nivel como el C que permita controlar los detalles de
implementación. La siguiente sección incluye una colección de problemas de entre
los que el lector puede escoger alguno e ir trabajando con él, aplicando los métodos
descritos a lo largo de todo el texto.

Al resolver un problema de forma heurística debemos de medir la calidad de los

resultados puesto que, como ya hemos mencionado, la optimalidad no está
garantizada. En la sección tercera de este capítulo se recogen los principales
métodos para medir la calidad y eficiencia de un algoritmo y poder determinar su
valía frente a otros.

1.1 Problemas Estructurados

El objeto de esta sección no es únicamente dar una colección de ejemplos reales,

sino el de establecer modelos que han sido muy estudiados. Así, al enfrentarse el
lector a un problema dado, tratará de reconocer las estructuras especiales que
aparecen en estos modelos y de esta forma se podrá aprovechar la extensa
literatura y experiencia computacional al respecto. Además, no debemos olvidar la
limitada, pero significativa, importancia práctica de estos modelos.

Problema de la Mochila

Se tienen n objetos donde cada objeto j tiene un peso wj y un valor vj. El problema
consiste en seleccionar los objetos a incluir en una mochila sin exceder el peso
máximo W, de modo que el valor total de los mismos sea máximo.

Para formular el problema se define una variable xi , por cada objeto i, de modo que
vale 1 si el objeto es seleccionado y 0 en caso contrario.

MAX
v1x1+v2x2+…+vnxn
s.a.:
w1x1+w2x2+…+wnxn W

x 0, entero

Este problema tiene numerosas aplicaciones tales como:

 La denominada Cutting Stock, en donde hay que cortar una plancha de acero en
diferentes piezas.
 Determinar los artículos que puede almacenar un depósito para maximizar su
valor total.
 Maximizar el beneficio en asignación de inversiones cuando sólo hay una
restricción.

Problema del Cubrimiento de Conjuntos

Este problema, también conocido como “Set Covering”, se puede enunciar del
siguiente modo: Sea un conjunto de objetos S={1,2,..,m} y una clase H de
subconjuntos de S, H={H1,H2,. .,Hn} donde cada Hi tiene un coste ci asociado. El
problema consiste en cubrir con coste mínimo todos los elementos de S con
subconjuntos Hi.
Para formular el problema se define una variable xi que vale 1 si Hi está en la
solución y 0 en otro caso. También se introduce una matriz A={a ij} en donde el aij
vale 1 si el elemento j de S está en Hi y 0 en otro caso.

MIN
c1x1+c2x2+…+cnxn
s.a.:
a1jx1+a2jx2+…+anjxn 1 j=1,…,m

xi = 1,0 i=1,…,n

Este problema tiene diferentes aplicaciones, entre las que podemos destacar la
localización de servicios, tales como hospitales, bomberos, etc. y, la asignación de
tripulaciones a vuelos.

El problema del Set Covering es relativamente fácil de resolver con métodos de

Ramificación y Acotación ya que la solución óptima del problema lineal coincide, en
ocasiones, con la del entero o está bastante cerca de él. La dificultad del problema
viene del número enorme de variables que suelen aparecer en problemas reales.

Problema del Empaquetado de Conjuntos

A este problema también se le conoce como Set Packing. Como en el problema

anterior se tienen los conjuntos S y H, pero ahora cada H i tiene un valor asociado.
El objetivo es empaquetar tantos elementos de S como sea posible de forma que el
beneficio obtenido sea máximo y no haya solapamientos (ningún elemento de S
puede aparecer mas de una vez).

En cierto modo, la relajación lineal del Set Covering y la del Set Packing son
problemas duales. Sin embargo esto no sirve para establecer una relación entre los
problemas enteros originales.

Uno de los ejemplos/aplicaciones es el problema del Acoplamiento Máximo o

Matching. Un acoplamiento es un subconjunto de las aristas de un grafo de manera
que cualquier vértice no sea incidente con más de una de esas aristas. El problema
del acoplamiento máximo consiste en encontrar un acoplamiento de máximo
cardinal.
Problema de la Partición de Conjuntos

Este problema también es conocido como Set Partitioning y, al igual que en los dos
anteriores, se tienen los conjuntos S y H. Así como en el Set Covering cada
elemento de S tiene que aparecer al menos en uno de H, en este problema cada
elemento de S tiene que aparecer exactamente en uno de H, por lo tanto la solución
representa una partición del conjunto S. La función objetivo puede ser maximizar o
minimizar, según la aplicación.

Aplicaciones:
 Asignación de tripulaciones en una versión más restringida que la anteriormente
mencionada.
 Creación de distritos Electorales: Asignación de electores a un colegio electoral.

Los tres problemas vistos pueden ser muy útiles para mostrar la transformación y
relaciones entre problemas. Así podemos ver que el Set Packing y el Set
Partitioning son equivalentes. Para pasar del primero al segundo basta con añadir
variables de holgura. La transformación inversa se realiza mediante variables
artificiales. Estos dos problemas son más “fáciles” de resolver de forma exacta que
el Set Covering ya que en ellos las restricciones lineales están más ajustadas
respecto al conjunto de soluciones enteras posibles, por lo que los óptimos de las
relajaciones lineales están más cerca de las soluciones enteras.

Problema del Viajante

Este problema, también conocido como Traveling Salesman Problem (TSP), ha sido
uno de los mas estudiados en Investigación Operativa, por lo que merece una
atención especial. Cuando la teoría de la Complejidad Algorítmica se desarrolló, el
TSP fue uno de los primeros problemas en estudiarse, probando Karp en 1972 que
pertenece a la clase de los problemas difíciles (NP-hard).

Desde los métodos de Ramificación y Acotación hasta los basados en la

Combinatoria Poliédrica, pasando por los procedimientos Metaheurísticos, todos han
sido inicialmente probados en el TSP, convirtiéndose éste en una prueba obligada
para “validar” cualquier técnica de resolución de problemas enteros o combinatorios.
La
librería TSPLIB (Reinelt, 1991) de domino público contiene un conjunto de ejemplos
del TSP con la mejor solución obtenida hasta la fecha y, en algunos casos, con la
solución óptima. A efectos de medir empíricamente la bondad de los algoritmos que
se describen en los capítulos segundo y tercero, consideraremos un conjunto de 30
ejemplos de la TSPLIB basados en problemas reales con óptimos conocidos.

El Problema del Viajante puede enunciarse del siguiente modo:

“Un viajante de comercio ha de visitar n ciudades, comenzando y finalizando en

su propia ciudad. Conociendo el coste de ir de cada ciudad a otra, determinar el
recorrido de coste mínimo.”

Para enunciar el problema formalmente introducimos la siguiente terminología: Sea

un grafo G=(V,A,C) donde V es el conjunto de vértices, A es el de aristas y C=(c ij) es
la matriz de costes. Esto es, cij es el coste o distancia de la arista (i, j).

 Un camino (o cadena) es una sucesión de aristas (e1, e2, …, ek) en donde el

vértice final de cada arista coincide con el inicial de la siguiente. También puede
representarse por la sucesión de vértices utilizados.

 Un camino es simple o elemental si no utiliza el mismo vértice mas de una vez.

 Un ciclo es un camino (e1, e2, …, ek) en el que el vértice final de ek coincide con el
inicial de e1.

 Un ciclo es simple si lo es el camino que lo define.

 Un subtour es un ciclo simple que no pasa por todos los vértices del grafo.

 Un tour o ciclo hamiltoniano es un ciclo simple que pasa por todos los vértices
del grafo.

El Problema del Viajante consiste en determinar un tour de coste mínimo. La figura 2

muestra un grafo de 8 vértices en el que aparece destacado un ciclo hamiltoniano.

8 5 4
1
6
4
3 6
5
4 3
10
2 5 6

8 10
6 7

4
4 8 4

3 8
 Figura 1. Ciclo Hamiltoniano

Consideraremos, sin pérdida de generalidad, que el grafo es completo; es decir, que

para cada par de vértices existe una arista que los une. Notar que, de no ser así,
siempre podemos añadir una arista ficticia entre dos vértices con el coste del camino
más corto que los une. Así por ejemplo, en el grafo de la figura 2 podemos añadir
una arista entre los vértices 1 y 6 con coste 9 correspondiente al camino 1-3-6.

Entre las aplicaciones más importantes del TSP podemos destacar:

 Fabricación de circuitos integrados
 Rutas de vehículos
 Recogida (robotizada) de material en almacenes
 Instalación de componentes en ordenadores
 Aparece como subproblema en otras aplicaciones

Este problema puede ser formulado mediante un modelo de programación lineal

entera con variables binarias. Para ello basta considerar las variables xij que valen 1
si el viajante va de la ciudad i a la j y 0 en otro caso y llamar c ij al coste de ir de la
ciudad i a la j:
Uso del software.
WinQSB es un sistema interactivo de ayuda a la toma de decisiones que contiene
herramientas muy útiles para resolver distintos tipos de problemas en el campo dela
investigación operativa. El sistema está formado por distintos módulos, uno para
cada tipo de modelo o problema.

TORA
El software TORA de optimización es un programa basado en Windows® que tiene
por objeto usarse con muchas de las técnicas presentadas en el libro
Investigaciónde Operaciones de TAHA. TORA es una aplicación muy simple, con
una interfaz gráfica de baja calidad. Una de las ventajas de TORA es que puede
utilizarse en procesadores de 32 y 64 bits, hoy por hoy su principal desventaja es
que deberá ajustarse la configuración de pantalla para adecuarse a sus ajustes de
presentación de 800 x 600 y 1024 x 768 pixeles.
DS for Windows
Software para la producción / gestión de operaciones, métodos cuantitativos,
ciencias de la gestión y la investigación de operaciones.

Ejemplos
2.1 El problema
Se consideró una situación hipotética en la que se necesita obtener un plan de
cortas para una unidad de producción forestal, tal que permita abastecer de madera
en forma continua a una planta de producción de pulpa y minimice los costos totales
de aprovechamiento. La unidad de producción forestal está conformada por seis
rodales de una misma especie (eucalipto), el período de planificación es de cinco
años y las necesidades anuales de materia prima de la planta son de 20.000
toneladas.
 CONCLUSIONES
Durante esta investigación llevada a cabo pude conocer los diferentes modelos de o
métodos de programación lineal, ya que 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. Es por esto que se vuelve una herramienta muy
importante para nosotros como ingenieros industriales. Es por esto la gran
importancia que este tiene para poder maximizar cualquier tipo de ingresos.
Un modelo de programación entera es aquel que contiene restricciones y una
función objetivo idénticas a la formuladas en programación lineal , la única diferencia
en que una o más variables de decisión deben tomar valor entero en
la solución final.