PROGRAMACION ENTERA: METODO DE BIFURCACIÓN Y ACOTAMIENTO

La mayor parte de los PE se resuelven en la práctica mediante la técnica de ramificación y

acotamiento. En este método se encuentra la solución óptima del PE mediante la

enumeración exhaustiva de los puntos en una región factible de un subproblema.

OBSERVACIÓN: si se resuelve la relajación del PL de un PE puro y se obtiene una solución en

la cual las todas las variables son números enteros, entonces la solución óptima para la

relajación del PL es también la solución óptima para el PE.

Ejemplo:

La Telfa Corporatión fabrica mesas y sillas. Una mesa requiere 1 hora de mano de obra y 9

pies de tablón de madera, en tanto que para una silla se necesita 1 hora de mano de obra

y 5 pies de tablón de madera. En la actualidad están a la disposición 6 horas de mano de

obra y 45 pies de tablón de madera. Cada mesa contribuye con 8 dólares a las utilidades y

cada silla con 5 dólares. Formule y resuelva un PE para maximizar las utilidades de Telfa.

X1 = número de mesas fabricadas X2 = número de sillas de fabricación

Max z = 8X1 + 5X2

Sujeto a:

X1 + X2 <= 6 Restricción de la mano de obra

9X1 + 5X2 <= 45 Restricción de la madera

X1, X2 >= 0 X1, X2 enteros

Primeros se realiza la solución de la relajación del PL del PE, es decir la solución del PL sin la

restricción de ser números enteros.

Se obtiene entonces: z = 41.25 X1 = 3.75 X2 = 2.25

Como NO son números enteros, entonces se debe proceder a la ramificación. Se debe

considerar que el valor de óptimo de Z para el PE es <= que el valor de Z óptimo para la

relajación del PL. Es decir Z para el PE debe ser menor de 165/4. Por lo tanto el valor de z de

la relación del PL es un límite o acotamiento superior para las utilidades.

Se traza la solución gráfica del problema:

Consideramos ahora la solución del PL relajado como subproblema 1.

Para empezar el método de ramificación, tomamos de modo arbitrario una variable que es

fraccionaria en la solución óptima de la relajación del PL. En este caso se decide por X1 y

se dice que dichos subproblemas se crearon por ramificación sobre X1.

El valor de X1 = 3.75 por lo tanto se establecen nuevas restricciones a partir de esta

variable. Considerando valores para la misma que no coincidan con la solución inicial, pero

que se derivan a partir de la misma. Es decir ahora se consideraran 2 opciones para X1:

X1 <=3 o X1 >=4 ninguna coincide con X1 = 3.75

Se plantean ahora dos subproblemas a partir del primero:

Subproblema 2 = subproblema 1 + restricción X1 >= 4

Subproblema 3 = subproblema 1 + restricción X1 <= 3

Se representa gráficamente el nuevo planteamiento

Resolviendo los nuevos PL planteados se obtiene la solución de las ramificaciones y se

realiza el diagrama para las ramificaciones: figura 13

En la figura anterior t significa el orden cronológico en el cual se resuelve el problema.

Las ramificaciones se pueden resolver mediante el método grafico o usando LINDO.

Solución del subproblema 2

Como la solución del subproblema 2 nos da un valor de X2 = 1.8 (9/5) se deben de seguir

realizando más ramificaciones hasta encontrar un valor entero para todas las variables,

teniendo un valor de Z lo más cercano al valor del Z del PL relajado, que es de 41.25.

De este modo se van realizando diferentes ramificaciones. Creando nuevos subproblemas.

Se deben trabajar los más subproblemas posibles a modo de comprobar que se tiene la

respuesta óptima del PE.

Se generan ahora los subproblemas 4 y 5

Subpproblema 4 = Subproblema 1 + restricción X1 >= 4 y X2 >=2 que nos queda como:

Subproblema 2 + restricción X2 >= 2.

Subproblema 5 = Subproblema 1 + restricción X1 >= 4 y X2 < = 1 que nos queda como:

Subproblema 2 + restricción X2 <= 1.

REGIÓN FACTIBLE:

La solución del subproblema 4 es no factible por lo tanto se le coloca un X para indicar este

hecho.

Subproblemas 6 y 7

Subproblema 6 = subproblema 5 + restricción X1 >= 5

Subproblema 7 = subproblema 5 + restricción X1 <= 4

Una solución que se obtiene al resolver un subproblema en el cual todas las variables tienen

valores enteros, se denominan solución probable. Como esta solución podría ser óptima, se

debe considerar como solución probable hasta que no se encuentre una solución factible

mejor para el PE. Es decir se debe seguir probando hasta que se concluya que es la mejor.

Por lo tanto el valor de Z para la solución probable es un acotamiento inferior (LB) sobre el

valor óptimo de Z para el PL original.

La representación de todos los subproblemas que se originan se llama árbol. Cada

subproblema recibe el nombre de nodo del árbol y cada línea que une dos nodos del árbol

se denomina arco.

EJERCICIO EN CLASE: Resolver los subproblemas del 3 al 7 en LINDO y entregar pantallas

impresas. Los resultados deben ser los que aparecen en los árboles.

EJERCICIO DE EXAMEN: Utilizar el método grafico para indicar la región factible para cada

subproblema. Y cada subproblema resolverlo por LINDO, así como la relajación del PL.

Realizar también los diferentes diagramas de árbol.

Resolver por ramificación y acotamiento el siguiente PE

Max z = 5X1 + 2X2

Sujeto a:

3X1 + X2 < = 12

X1 + X2 < = 5

X1, X2 > = 0; X1, X2 enteros

TRANSPORTE DE ASIGNACION

TABLEAU DE TRANSPORTE

TRANSPORTE DE ASIGNACION: METODO VOGUEL

EJEMPLO:

Partimos del siguiente tableu

Realizamos penalizaciones, restando cada valor por columna y por renglón. Notamos que

las penalizaciones más grande es 73 y la más pequeña = 1.

Entonces se fija X 12 = min (10, 5) = 5 entonces se cancela la columna 2 y se reduce S1=10 -5 = 5.

Se calculan nuevas penalizaciones:

La penalización más grande es ahora 70 con 2, entonces X13 = min (5,5) y se reduce S1

haciendo S1 = 5 – 5 = 0.

Debido a que cada renglón tiene solo una celda que no está cancelada, no hay

penalizaciones de renglón. Ahora solo la columna 1 tiene penalización.

Entonces X11 = min (0, 15) = 0, se cancela el renglón 1 y se cambia d1 = 15 – 0 = 15

Después de esto no se puede calcular ninguna penalización más. Se observa que la única

celda que se encuentra en un renglón o columna NO cancelado es la celada X21= 15,

entonces se cancela el renglón 2 y la columna 1, haciendo en ambos: 15 – 15 = 0.

Obteniendo la solución básica factible como:

X11 = 0 X12 = 5 X13 = 5 X21 = 15 X22 = X23 = 0

EJERCICIO PARA ENTREGAR:

Un banco tiene dos sitios en los que se procesan los cheques. El sitio (1) procesa 10, 000

cheques por día y el sitio de cheques (2) 6 000 cheques por día. El banco procesa tres tipos

de cheques: vendedor, salario y personal. El costo de procesamiento por cheque depende

del sitio (ver tabla). Por día deben procesarse 5 000 cheques de cada tipo. Formule un

problema de transporte equilibrado para minimizar el costo diario de procesar los cheques.