PROGRAMACION ENTERA BINARIA (CASOS ESPECIALES)

[pic 2]

[pic 3]

[pic 4]

[pic 5]

[pic 6]

PROGRAMACION BINARIA

(CASOS ESPECIALES)

PROGRAMACION ENTERA BINARIA[pic 7]

❑        CASOS ESPECIALES: USOS INNOVADORES DE VARIABLES BINARIAS

• RETRICCIONES UNA U OTRA

Situación en la que se debe elegir entre dos restricciones, de manera que solamente una de ellas debe cumplirse.

Por ejemplo, sean las restricciones siguientes entre las que solamente una debe tomarse en cuenta en el modelo:

5x11 + 3x21 + 6x31 + 4x41 < 6000        (1)

4x11 + 6x21 + 3x31 + 5x41 < 5000        (2)

Reformular las restricciones considerando un número positivo muy grande (M) al lado derecho de éstas y se obtendrá el efecto de eliminar una de ellas, de la siguiente manera:

5x11 + 3x21 + 6x31 + 4x41 < 6000 + My        (1)

4x11 + 6x21 + 3x31 + 5x41 < 5000 + M(1 - y)        (2)

y es binaria, siendo M un número muy grande

Note que si la variable y toma el valor de cero, la primera restricción queda con <= 6000 en su lado derecho, pero en la segunda se tendría <= 5000 + M, al sumarse un número tan grande al 5000, el lado derecho es como si quedara: <= INFINITO dejando así de ser una restricción. La restricción que prevalecería sería la primera. La situación es totalmente contraria si es que la variable y hubiera tomado el valor de 1; en tal caso, la restricción que se mantendría sería la segunda.

• DEBEN CUMPLIRSE K  DE N  RESTRICCIONES

En este tipo de problema que consta de N restricciones, solamente deben cumplirse K de ellas. Lo que sucede realmente es que las N – K restricciones que no se eligen son eliminadas del problema. Observe que esta situación es una generalización del caso anterior que tenía K=1 y N=2.

Sean las siguientes restricciones:

5x1 + 3x2 + 3x3   - x4   < 10

2x1 + 5x2   - x3 + 3x4   < 82

- x1 + 3x2 +5x3 + 3x4 < 15 3x1 - x2 + 3x3 + 5x4    < 20

Aplicando la misma lógica que en caso anterior y considerando; por ejemplo, que al menos tres de las restricciones se cumplan; se tendría lo siguiente:

5x1 + 3x2 + 3x3   - x4    < 10 + My1

2x1 + 5x2   - x3 + 3x4    < 82 + My2

- x1 + 3x2 +5x3 + 3x4   < 15 + My3

3x1 - x2 + 3x3 + 5x4        < 20 + My4

y1 + y2 + y3 + y4   < 1

yi binarias, (i=1,2,3,4)

• RESTRICCIONES CON N VALORES POSIBLES

Situación en la que se requiere que una restricción tome cualquiera de N valores dados. Siendo por ejemplo para la siguiente restricción que se pueda adoptar en su lado derecho el valor de 15, 18 ó 20:

7x1 + 2x2   < 15 ó 18 ó 20

La restricción se transformaría en:

7x1 + 2x2   < 15y1 + 18 y2 + 20 y3 y1 + y2 + y3 = 1

yi binarias, (i=1,2,3)

• CONSIDERACION DE COSTO FIJO

Al iniciar una actividad o proceso normalmente se incurren en costos inherentes al inicio de dicha actividad que no se relacionan directamente con la cantidad a producir. Este costo no es proporcional al nivel de producción como normalmente lo suele ser el costo variable.

En el siguiente modelo matemático se puede apreciar la consideración del costo fijo:

xi = cantidad de unidades a producir del artículo i, (i=1, 2, 3)  yi = se lleva a cabo o no la producción del artículo i, (i=1, 2, 3)

[pic 8]

Max Z = 5x1 + 4x2 + 2x3   - 170y1 - 180y2 - 150y3

Sujeto a:

x1 + x2 + x3    > 250

x1 < 220 y1[pic 9]

x2 < 200 y2 x3 < 205 y3[pic 10]

xi > 0 (i=1,2,3)

Los niveles de producción tendrán valores solamente si se ha aceptado llevar a cabo la fabricación de sus respectivos productos.

yi binarias (i=1,2,3)

Lectura sugerida:

INTRODUCCION A LA INVESTIGACION DE OPERACIONES

Hillier – Lieberman

McGraw –Hill (Octava edición) 2006

“Usos innovadores de variables binarias en la formulación de modelos”

Capítulo 11 Programación Entera Pág 487

❑        EJEMPLOS

PROBLEMA 1 (RESTRICCIONES UNA U OTRA)

Una empresa ha diseñado 3 nuevos productos y dispone de dos plantas que los pueden producir. Sin embargo, para evitar una diversificación excesiva de la línea de productos de la empresa, la administración ha dispuesto en primer lugar que deben producirse como máximo dos de estos tres nuevos productos posibles. Y, en segundo lugar, que solo una de las plantas debe asignarse para la fabricación de los nuevos productos.

Se considera que el costo unitario de fabricación de cada producto sería el mismo en las dos plantas, pero por diferencia de instalaciones, el número de horas de producción por unidad de cada producto puede diferir entre ellas. Estos datos se dan en la tabla adjunta junto con la información del departamento de mercadotecnia del número de unidades de cada producto que se pueden vender a la semana si se producen. El objetivo es seleccionar los productos, la planta y las tasas de producción de los nuevos productos de manera que se maximice la ganancia total. Considerar que las tasas de producción pueden adoptar valores decimales

...