1

5.1 Introducción

La programación lineal entera se ocupa básicamente de programas lineales en los que algunas o todas las variables suponen valores enteros o discretos. Se dice que la PLE es mixta o pura si alguna o todas las variables están restringidas a tomar sólo valores enteros.

Aunque se han creado varios algoritmos para la programación entera, ninguno de ellos es totalmente confiable desde el punto de vista del cálculo, sobre todo, cuando el número de variables enteras se incrementa.

La dificultad de cálculo con los algoritmos disponibles para la programación entera ha conducido a los usuarios a buscar otros medios para resolver el problema. Uno de tales medios es resolver el modelo como un problema lineal continuo y luego redondear la solución óptima a los valores enteros factibles más cercanos. Sin embargo, en este caso no hay garantía de que la solución redondeada satisfaga las restricciones. Esto es siempre cierto si la programación entera original tiene una o más restricciones de igualdad.

Según la teoría de programación lineal, una solución redondeada en este caso no puede ser factible, ya que significa que la misma base (con todas las variables básicas a nivel cero) puede generar dos soluciones distintas.

La infactibilidad creada por redondeo puede tolerarse ya que, en general, los parámetros de los problemas no son exactos. Pero existen restricciones de igualdad características en los problemas enteros donde los parámetros son exactos.

La restricción de elección múltiple x1+ x2+…+ xn=1 , donde x j=(0,1) para toda j, no es sino un ejemplo. En tales condiciones el redondeo no puede utilizarse y será esencial contar con un algoritmo exacto.

Para destacar además lo inadecuado del redondeo, observe que aunque las variables enteras comúnmente se piensa que representan un número discreto de objetos (por ejemplo, máquinas, hombres, barcos), otros tipos representan cuantificaciones de algunos códigos. Por consiguiente, una decisión para financiar o no un proyecto puede representarse por una variable binaria x=0 si el proyecto se rechaza, x=1 si el proyecto se acepta. En este caso no tiene sentido tratar con valores fraccionarios de x, y el uso del redondeo como una aproximación lógicamente es inaceptable.

2

5.2 Definición y Modelos de Programación Entera (PE)

Un modelo de Programación Entera (PE) permite abordar aplicaciones donde la solución tiene sentido si una parte o todas las decisiones toman valores restringidos a números enteros. Por ejemplo, consideremos que tenemos el siguiente problema de programación lineal:

Max cT xs . a . Ax=bx≥ 0

Si todas las variables restringen sus valores a números enteros, entonces estamos frente a un modelo de PE pura; por el contrario si al menos algún conjunto de variables no está acotado a adoptar valores o número enteros, se trata de un PE mixta.

Parte del problema de la programación entera radica en la diferencia esencial que existe entre este y la programación lineal. En la programación lineal se maximiza o minimiza una función sobre una región de factibilidad convexa, mientras que en la programación entera se maximiza una función sobre una región de factibilidad que generalmente no es convexa. Por lo tanto, la solución de problemas enteros, es de muchos órdenes de magnitud más complicada que la programación lineal.

A continuación se presentan los tres problemas de estructura entera:

1. Problema entero (PE) Opt Z=cX

sujetoa AX ≤ bX ≥ 0 , entero

2. Problema entero – mixto (PEM)

Opt Z=cX+dYsujetoa AX+BY ⋛b

X ≥ 0Y ≥ 0 , entero

3

3. Problemas entero – cero – uno (PECU) o problema binario (PB)

Opt Z=cXsujetoa AX⋚b

X=0 ó1

Estos tres tipos de problemas requieren de técnicas especiales de solución, ya que los métodos de solución de los programas lineales (simplex, dual simplex, revisado, etc.), por lo general, no trabajan en estos casos.

En efecto, dado el siguiente problema entero:

Máx Z=X1+3 X2

sujetoa X1 ≤1.8722 X1+34 X 2≤ 105

X1 ≥ 0 , X2≥ 0X1 , X2 enteros

Si se resuelve por el método simplex, ignorando las restricciones enteras, se obtiene la solución X1=1.87 , X2=1.87 , Z=7.5. Redondeando al entero más cercano quedaría X1=2 , X 2=2 , Z=2. Sin embargo, esta solución viola las restricciones, porque:

X1=2≮+ 1.87

El tratar de redondear al entero inmediato menor o mayor crea el problema combinatorio, de que si hay n variables de decisión, se deben analizar las 2n diferentes posibilidades. Así, si hay 100 variables, el número de posibilidades a analizar es del orden de 1.26 ×10030. Por lo tanto se requieren técnicas más eficientes que el análisis exhaustivo de todas las alternativas posibles.

Se hace notar que si al resolver un PE, por medio de alguna técnica de programación lineal, el resultado óptimo del PL (generado por el PE, al ignorar las restricciones de integralidad de las variables del mismo) es entero, entonces, es también una solución óptima del problema entero original PE.

A continuación se ve qué variedad de problemas caen dentro de esta familia de Problemas Enteros:

a. Todos los problemas de programación lineal, donde las actividades, por su estructura deben se no – divisibles, son Programas Enteros. Por ejemplo, problemas de producción de automóviles, prendas de vestir, etc. ¿Qué significado tendría la producción de 577.83 automóviles?

4

b. Todos los problemas de transporte, asignación y redes de optimización, son Problemas Enteros. Sin embargo, dada la estructura tan especial de 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 bastante difíciles de resolver. Se supone, por ejemplo, el caso de un taller que puede efectuar un solo tipo de trabajo a la vez (orden i), el que se tiene contratado a entregar en gi días, a partir de una cierta fecha base, y que además tiene una duración de trabajo de d i(di>0) días y al cual se asocia una multa de pi pesos por día de retraso después de los gi días estipulados. Se supone que el taller recibe n órdenes diferentes de trabajo en la fecha base. ¿Cuál debe ser el orden de secuenciación de trabajos que minimice el costo penal total?

Sin entrar en mucho detalle en la formulación de este problema, se puede demostrar que el siguiente modelo del tipo cero – uno o binario, resuelve este problema de secuenciación. Sea Yi,t una variable de decisión definida de la siguiente manera:

Yi,t

Y sea:

T=∑i=1

n

d i

d. El problema del agente viajero. Este problema concierne a un agente viajero que, saliendo de una determinada ciudad, debe visitar una sola vez n-1 ciudades diferentes, y regresar al punto de partida. Si el costo de dirigirse a la ciudad j desde la ciudad i es cij (c ij ≠ c ji), se debe determinar la secuencia de visita de ciudades, tal que el costo total asociado sea mínimo.

Este problema se presentó por primera vez en 1960, en un artículo de Miller, Ticker y Zemlin, pero hay una variedad de métodos que resuelven el problema, dependiendo del tamaño de n, el número de ciudades. Una formulación de este problema es la siguiente: Sean:

Xij =

c ij= el costo asociado a la visita de la ciudad j después de visitar la ciudad iui= un número real arbitrario,

Entonces se requiere

1, si el trabajo i se completa al finalizar el periodo t, 0, si el trabajo i no se completa al finalizar el periodo t,

1, si se visita a la ciudad j después de visitar la ciudad i0, si no se visita a la ciudad j después de visitar la ciudad i.

5

Mín Z=∑i=0

n

❑∑j=0

n

cij X ij

sujetoa∑i=0

n

X ij=1 , j=0 ,1 ,2 , …, n ,

∑j=0

n

X ij=1 ,i=1 , 2 , …, n.

ui−u j+n X ij ≤ n−1 ,1 ≤ i≠ j ≤ n ,

X ij=0ó 1 paratoda i , j .

e. Problema tipo mochila. Este tipo de problemas de optimización de carácter entero puede darse en dos versiones. En la primera nos proporciona un cierto espacio con determinado volumen o capacidad, y este debe ser llenado con objetos de valor y volumen o capacidad especificados. El problema consiste en llenar ese espacio con el conjunto de objetos más valioso, sin exceder los límites físicos de dicho espacio. La segunda versión consiste en dividir a un objeto en porciones de diferente valor. El problema consiste en encontrar la división de mayor valor.

El problema se formula como:

Máx Z=∑i=0

n

v i X i

sujetoa∑i=0

n

k i X i ≤ K

X i ≥ 0 , entero , i=1 ,2 , …, n ,Donde: v i: es el valor del objeto i, i =1, 2,…, n,k i: es la capacidad o volumen del objeto i, i = 1, 2,…, n,K: es la capacidad o volumen del espacio

f. Dicotomías y problemas de aproximación. Una dicotomía ocurre en un programa matemático, cuando se tienen condiciones del tipo esta restricción o la otra

6

restricción, pero no ambas. Este tipo de condiciones se pueden representar por medio de una estructura entera.

Esta situación puede considerarse como sigue:

Sean las m restricciones de la forma: gi ( x1 , x2 , …, xn )≤ b i , i=1 , 2, …, m

Por definición

yi =

Por consiguiente, cualesquiera k de las m restricciones se garantiza que son activas si, para una M suficientemente grande:

gi ( x1 , x2 , …, xn )≤ b i+M y i ,i=1 ,2 , …, m Y y1+ y2+…+ ym=m−k

Donde y i=0 ó 1 para toda i. Esto demuestra que para m-k restricciones, su segundo miembro asociado será de la forma b j+M , lo cual hace la restricción redundante. Es importante notar que la formulación anterior elegirá el conjunto de restricciones activas que proporcionen el mejor valor de la función objetivo.

5.3 Método de Ramificar y Acotar

0, si la i-ésima restricción es activa1, si la i-ésima restricción es inactiva

7

En la PL, el método simplex se basa en aceptar que la solución óptima ocurre en un punto extremo del espacio de soluciones. Este poderoso resultado reduce la búsqueda dela solución óptima de un número infinito a un número finito de soluciones posibles. Por otra parte, la PE comienza con un número finito de puntos solución. Sin embargo, la naturaleza entera hace difícil diseñar un algoritmo eficaz que localice los puntos enteros factibles del espacio de soluciones.

En vista de esta dificultad, los investigadores han creado un espacio de solución que se basa en el gran éxito obtenido al resolver problemas de PL. La estrategia de este procedimiento se puede resumir en tres pasos:

1. Relajar el espacio de soluciones del problema entero, ignorado las restricciones enteras por completo. Este paso convierte el PE en un PL regular.

2. Resolver el modelo de PL “relajado” e identificar su punto óptimo (continuo).

3. Comenzando con el punto óptimo continuo, agregar restricciones especiales que fuercen iterativamente el punto extremo óptimo del modelo PL resultante, hacia las restricciones enteras deseadas.

La razón para comenzar la búsqueda del PE óptimo en el PL óptimo continuo es que existe la posibilidad de que ambas soluciones resulten cercanas entre sí, y que de esta manera aumente la posibilidad de localizar rápidamente la solución entera. La característica principal del procedimiento propuesto es que resuelve problemas sucesivos de PL, que son más accesibles desde el punto de vista del cálculo que los problemas de PE.

Existen dos métodos para generar las restricciones especiales que fuercen la solución óptima del problema PL relajado, hacia la solución entera deseada:

Método de Ramificar y Acotar Método del Plano de Corte

Método de Ramificar y Acotar

Considere el siguiente problema de PE: Máx Z=5x1+4 x2

Sujeto ax1+ x2 ≤5

10 x1+6 x2 ≤ 45x1 , x2≥ 0 y entero

El procedimiento R y A se basa en tratar sólo con el problema de PL. Como la solución óptima PL (x1=3.75 , x2=1.25 , z=23.75) no satisface la necesidad de valores enteros, el algoritmo de R y A exige modificar el espacio de soluciones PL en forma tal, que nos permita identificar, finalmente, la solución óptima de la PE.

En ausencia del espacio gráfico de soluciones, no tenemos manera de determinar dónde puede encontrarse la solución óptima, por lo que nuestra única opción es investigar ambos

8

problemas. Hacemos esto trabajando con un problema a la vez (PL1 o PL2). Supongamos que escogemos arbitrariamente al PL1. En efecto debemos resolver el siguiente problema:

Máx Z=5x1+4 x2

Sujeto a x1+ x2 ≤5

10 x1+6 x2 ≤ 45x1≤ 3

x1 , x2≥ 0

LP0x1=3.75 , x2=1.25 , z=23.75

Como se indicó antes, el PL1 es el mismo que el PL0 con la restricción adicional de acotamiento superior, x1≤ 3. Así, podemos aplicar el algoritmo primal de acotamiento superior para resolver el problema. Esto da la nueva solución: x1=3 , x2=2 y z=23.

Como esta solución satisface el requisito de valor entero, se dice que el PL1 está agotado, vacío, lo que significa que el PL1 no puede producir ninguna solución mejor del PE y no necesita investigarse más a fondo.

Determinar una solución factible entera en una etapa temprana de los cálculos es crucial para incrementar la eficiencia del algoritmo R y A. Tal solución fija una cota inferior al valor objetivo óptimo del problema PE, que a su vez, se puede usar para descartar automáticamente cualesquiera subproblemas no explorados que no dan una mejor solución entera. En términos de nuestro ejemplo, el PL1 produce una cota inferior z = 23. Esto significa que cualquier solución entera mejorada debe tener un valor de z mayor que 23. Sin embargo, como la solución de la función objetivo son enteros, se infiere que ningún subproblema que proceda del PL0 puede producir un valor de z mejor que 23. En consecuencia, sin ulterior investigación, podemos descartar al PL2. En este caso se dice que el PL2 está agotado porque no puede dar una mejor solución entera.

1

x1≥ 4 x1≤ 3

LP1LP2

3x1=3 , x2=2 , z=232

Cota inferior (óptima)

9

Del problema anterior vemos que un subproblema está agotado si satisface una de las siguientes condiciones:

1. El subproblema de una solución factible entera del problema PLE

2. El subproblema de puede dar una mejor solución que la mejor cota inferior disponible (valor de z) del problema PE.

En nuestro ejemplo, PL1 y PL2 están agotados por las condiciones 1 y 2, respectivamente. Como no hay más subproblemas por investigar, el procedimiento termina y la solución entera óptima del problema PE es la asociada con la cota inferior corriente, esto es, x1=3 , x2=2 , z=23.

Aunque existen muchos métodos heurísticos para aumentar la habilidad del algoritmo R y A de “ver adelante” y hacer una “buena conjetura”, respecto a si una rama dada conducirá a una solución mejorada del PE, no existe una teoría consistente que produzca resultados concretos uniformes para la solución del problema general de PE.

Resumiremos ahora los pasos del algoritmo R y A. Suponiendo un problema de maximización, definimos z como la cota inferior de la solución entera óptima del problema de PE. Hacemos inicialmente z=−∞ e i = 0.

Paso 1: Agotamiento y ramificación. Seleccione PLi como el próximo subproblema por investigarse. Resuelva el PLi y trate de agotarlo usando las condiciones apropiadas.

a. Si el PLi se declara agotado (solución inferior, infactible o entera), ponga al día la cota inferior z si se encuentra una mejor solución del PE; si no es así, seleccione un nuevo subproblema i y repita el paso 1. Si todos los subproblemas se han investigado, deténgase; la solución óptima del PE está asociada con la última cota inferior z, en caso de que ésta exista. Si no es así,

b. si el PLi no está agotado, siga con el paso 2 para efectuar la ramificación del PLi.

Paso 2: Ramificación. Seleccione una de las variables x j cuyo valor óptimo x j* en la solución del PLi no satisfaga la restricción de valor entero. Elimine la región ¿ (donde [ A ] define al mayor entero ≤ A), creando dos subproblemas PL que correspondan a las dos siguientes restricciones mutuamente excluyentes:

x j ≤ ¿ y x j ≥ ¿Vuelva al paso 1.

5.4 Método de Planos Cortantes

10

Un plano cortante (o cortadura) para un problema de Programación Entera es una nueva restricción funcional que reduce la región factible para la soltura de Programación Lineal sin eliminar soluciones factibles para el problema de Programación Entera original.

Estos algoritmos resuelven el siguiente tipo de problema entero

Opt Z=cXs . a .

AX ¿¿ b

X≤uX≥0 , entero

El desarrollo de métodos de planos de cortes primarios, basados en el método primal simplex. La gran ventaja de estos métodos es que generan una solución factible desde el principio. Su gran desventaja consiste en su muy lenta convergencia a la solución final.

Los algoritmos enteros de planos de corte primarios tienen su origen, muy rudimentario en el método de Ben – Israel y Charnes.

El algoritmo del plano de corte modifica el espacio de soluciones agregando cortes que producen un punto extremo entero óptimo.

PROCEDIMIENTO

1. Considere cualquier restricción funcional de la forma ≤ con sólo coeficientes no negativos.

2. Encuentre un grupo de variables (llamado cubierta mínima de la restricción) tales que a) la restricción se viola si todas las variables en el grupo son iguales a 1 y todas las

demás variables son iguales a 0b) pero la restricción se satisface si el valor de cualquiera de estas variables cambia

de 1 a 03. Si N denota el número de variables en el grupo, el plano cortante obtenido tiene la forma

Suma de variables en el grupo ≤ N – 1

EJEMPLO

Se tiene la siguiente programación lineal entero.

Maximizar Z=7 x1+10 x2

s .a.−x1+3 x2≤67 x1+x2≤35x1 , x2≥0 y enteras

Dadas las holguras x3 y x4 para las restricciones 1 y 2, el cuadro óptimo del problema lineal es

11

Básica x1 x2 x3 x4Solución

Z 0 0 6322

3122

6612

2x 0 1 722

122

312

x11 0

− 122

322

412

La solución optima es Z = 66

12 , x1 =

412 , 2x =

312 , x3 = 0 , x4 = 0

El corte se establece suponiendo que todas variables (incluyendo las holguras) son enteras. La información del cuadro óptimo se puede presentar en forma explícita como sigue:

z+6322

x3+3122

x4=6612

Ec .de z

x2+722

x3+122

x4=312

Ec .de x2

x1−122

x3+322

x 4=412

Ec . de x1

Un renglón se restricción se puede usar como renglón de fuete para generar un corte, siempre que su lado derecho sea fraccionario incluyendo z.

Primero se sacan todos los coeficientes de la ecuación como factor común, con un valor entero y un componente fraccionario, siempre y cuando el componente fraccionario que resulte sea estrictamente positivo, por ejemplo:

52

=2+12

−73

=−3+23

La factorización de la ecuación se z da como resultado

z+(2+1922 ) x3+(1+ 9

22 )x 4=(66+12 )

Al pasar los componentes enteros al lado izquierdo, y todos los componentes fraccionarios al lado derecho, se llega a

z+2x3+1x4−66=−1922

x3−9

22x4+

12 (1)

Como x3 y x4 son no negativas, y todas las fracciones originalmente son estrictamente positivas, el lado derecho debe satisfacer la siguiente desigualdad:

12

−19

22x3−

922

x 4+12≤1

2 (2)

Ahora, como z+2x3+1x4−66 , el lado izquierdo de la ecuación (1), por construcción tiene

valor entero −19

22x3−

922

x 4+12 también debe ser entero. Por consiguiente se puede reemplazar

la ecuación (2) por la desigualdad −19

22x3−

922

x 4+12≤0

Es el corte que se desea, y representa una condición necesaria para obtener una solución entera. También se le llama corte fraccionario, porque todos sus coeficientes son fracciones.

Como x3=x4=0 en la tabla óptima del programa lineal anterior, el óptimo continuo actual viola el corte. Así, si se suma este corte al cuadro óptimo, el punto extremo óptimo resultante mueve la solución hacia la satisfacción de los requisitos enteros.

Si en forma arbitraria se selecciona el corte generado a partir del renglón x2 , se puede escribir como sigue, en forma de ecuación

− 722

x3−1

22x 4+s1=−1

2, s1≥0 (Corte I )

Esta restricción se agrega como restricción secundaria al cuadro óptimo del programa lineal, como sigue:

Básica

x1 x2 x3 x4 s1Solución

Z 0 0 6322

3122

066

12

2x 0 1 722

122

03

12

x11 0

− 122

322

04

12

s10 0

− 722

− 122

1−1

2

La tabla es óptima, pero no factible. Se aplicará el método simplex dual para recuperar la factibilidad, y así se obtiene:

Básica x1 x2 x3 x4 s1Solución

Z 0 0 0 1 9 62

2x 0 1 0 0 1 3

x11 0 0 1

7−1

74

47

x30 0 1 1

7−22

71

47

13

La ultima solución todavía no es entera en x1 y x2 . Se selecciona a x1 , en forma arbitraria, como el siguiente renglón de fuente; esto es

x1+(0+ 17 ) x4+(−1+ 6

7 )s1=4+ 47

El corte asociado es

−17

x4−67

s1+s2=−47

, s2≥0 (Corte II )

Básica x1 x2 x3 x4 s1 s2Solución

Z 0 0 0 1 9 0 62

2x 0 1 0 0 1 0 3

x11 0 0 1

7−1

70

447

x30 0 1 1

7−22

70

147

s20 0 0

−17

−67

1−4

7

Con el método simplex dual se obtiene el siguiente cuadro:

Básica x1 x2 x3 x4 s1 s2Solución

Z 0 0 0 0 3 7 58

2x 0 1 0 0 1 0 3

x11 0 0 0 -1 1 4

x30 0 1 0 -4 1 1

x40 0 0 1 6 -7 4

La solución optima es x1 = 4 , x2 = 3 , z = 58, y es totalmente entera

14

5.5 Algoritmo Aditivo de Balas

Es debido originalmente a Egon Balas (1965). Se llama aditivo porque todas las operaciones matemáticas que se realizan consisten en sumar o restar.

El procedimiento consiste en generar una secuencia de soluciones parciales añadiendo en cada iteración una variable y considerando las soluciones complementarias (resto de soluciones posibles). De esta forma, podemos por enumeración implícita, eliminar conjuntos de soluciones sin necesidad de evaluarlos exhaustivamente.

La selección de la variable añadida se hace en función de reducir al máximo la infactibilidad en la solución actual y eliminar la redundancia.

El procedimiento matemático generalizado es:

Optimizar (Z )=∑j=1

a

c j x i

s . a .∑j=1

a

aij xj¿

¿bi , para i=1,2,3 , . .. , m

x j=0 si la actividad jno esrealizada

x j=1 si la actividad j esrealizada

Este método es un procedimiento de enumeración que encuentra el óptimo en forma más rápida; en el método de Balas, la eficacia consiste en la evaluación solo de unas soluciones. El método empieza poniendo todas las variables iguales a cero y luego por medio de un procedimiento sistemático de forma consecutiva se asigna a una por una de las variables el valor 1. Luego se reemplaza en cada una de las restricciones y se averigua la infactibilidad. Por esta razón el método es algunas veces llamado el algoritmo aditivo. Para describir el algoritmo, se considera la forma general siguiente de un problema de Programación Lineal con variables cero – uno:

PROCEDIMIENTO

Paso 1. La función objetivo debe ser del tipo minimización, con todos los coeficientes no negativos.

Paso 2. Todas las restricciones deben ser del tipo £, con los lados derechos negativos de ser necesario. Luego, estas restricciones se convierten a ecuaciones, usando las variables auxiliares en el lado izquierdo de las restricciones.

Ejemplo: MAX Z = 3 y1 + 2 y2 – 5 y3 – 2 y4 + 3 y5

15

MIN W = – 3 y1 – 2 y2 + 5 y3 + 2 y4 – 3 y5

Con sus restricciones:

Reemplazamos: y1 = 1 – x1 ; y2 = 1 – x2 ; y3 = x3 ; y4 = x4 ; y5 = 1 – x5

MIN W´ = 3 x1 + 2 x2 + 5 x3 + 2 x4 + 3 x5 – 8

Sujeta a:

Sustituimos W´ + 8 = W MIN W = 3 x1 + 2 x2 + 5 x3 + 2 x4 + 3 x5

Siempre el problema nuevo a resolver consiste en la minimización de la función objetivo, teniendo en cuenta la medida de la no factibilidad de la holgura. Cuando la infactibilidad da el menor valor, continuamos con el siguiente paso; en el caso de una infactibilidad cero, ésta corresponde a la solución óptima; si encontramos varias infactibilidades iguales a cero, reemplazamos en la función objetivo y la respuesta será la que haga esta función mínima.

• x1 = 0; x2 = 0; x3 = 0; x4 = 0; x5 = 0 0 1; 0 – 2; 0 – 1; Infactibilidad 3

• x1 = 0; x2 = 0; x3 = 0; x4 = 0; x5 = 0 0 2; 0 5; 0 – 12; Infactibilidad 12

• x1 = 0; x2 = 0; x3 = 0; x4 = 0; x5 = 0 0 2; 0 – 2; 0 5; Infactibilidad 2

• x1 = 0; x2 = 0; x3 = 0; x4 = 0; x5 = 0 0 0; 0 – 5; 0 – 1; Infactibilidad 6

• x1 = 0; x2 = 0; x3 = 0; x4 = 0; x5 = 0 0 – 1; 0 2; 0 2; Infactibilidad 1

• x1 = 0; x2 = 0; x3 = 0; x4 = 0; x5 = 0 0 2; 0 1; 0 2; Infactibilidad 0

Solución Óptima Única: x1= 0; x2 * = 0; x3 *= 0; x4 *= 0; x5 *= 1; W* = 3

Solución Optima Única para el problema original:

y1 *= 1; y2 *= 1; y3 *= 0; y4 *= 0; y5 *= 0; Z* = 5

Algunos autores emplean el algoritmo de Balas modificado, el cual consiste en introducirle al modelo una restricción denominada de filtro, la cual no es otra que la función objetivo con una cota inferior del valor óptimo. Históricamente es muy importante, ya que ha

16

demostrado que algoritmos eficaces de programación en números enteros podrían emplear la enumeración implícita.

Conclusiones

Como puede inferirse, el factor más importante que afecta los cálculos en programación entera es el número de variables. Esta situación se acentúa más en los métodos de ramificar y acotar. Consecuentemente, al formular un modelo entero es ventajoso reducir el número de variables enteras tanto como sea posible. Esto puede efectuarse en general:

Aproximando variables enteras con continuas

Restringiendo los intervalos factibles de las variables enteras

Eliminando el uso de variables binarias auxiliares ideando métodos de solución más directos

Evitando la no linealidad del modelo

La importancia del problema entero en la práctica todavía no se alcanza con el desarrollo de métodos de solución suficientes. Esto se refleja principalmente en la dificultad inherente al tratar con cálculos enteros en general. La investigación intensiva actual puede finalmente llevar a un adelanto significativo. Es más probable, sin embargo, que lo anterior se logre con la invención de computadoras digitales extremadamente poderosas y altamente exactas en lugar de crear más métodos teóricos.

Bibliografía

A. TAHA, Hamdy; Investigación de Operaciones; 5ª Edición, Alfaomega.

PRAWDA Witenberg, Juan: Métodos y Modelos de Investigación Vol. 1; Limusa.

S. HILLER, Frederick; J. LIBERMAN, Gerald; Investigación de Operaciones; 7ª Edición, McGraw Hill.