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)

...