PROGRAMACIÓN

ENTERA

Carlos A. Bruno Romero

1
CONTENIDO
• PROGRAMACIÓN ENTERA
• RAMIFICACIÓN Y ACOTAMIENTO
• PLANO DE CORTE GOMORY
• Método de Enumeración Exhaustiva o Explícita
• SOFTWARE’S: WinQSB y EXCEL (Solver)

2
 PROGRAMACIÓN ENTERA
Muchos de los problemas reales las variables sólo
pueden tomar valores enteros
Ejemplo:

* Compras, personas, decisiones de inversión, etc.

Método Simplex?

• Cómo saber si tenemos una solución?

• Soluciones no están en los vértices
3
 • Problema entero puro:
min c Tx
s.a Ax = b
x0
xi entera i

Tipos de PE. • Problema entero mixto:

min Cx + dy
s.a Ax + Ey ≤ 𝑏
x0
y0
y∈0

• Problema entero binario:

min Z=CX
s.a AX <= b
x ∈ {0,1}
4
Podemos aceptar una solución aproximada?

Consideremos el siguiente problema de programación lineal

entera

Min Z = X1 – 11X2

S.a:
-X1 + 10X2 ≤ 40
10X1 + 10X2 ≤ 205
X1, X2 ≥ 0 y enteras

Solución optima sin considerar las condiciones de integridad:

X1 = 15 y X2 = 5.5
5
 Región Factible del modelo

8
(15,5.5)

(15,6)
6

(10,5) (15,5)
4

2 4 6 8 10 12 14 16 18 20 22

Posibles redondeos:
X1 = 15 y X2 = 6; no verifica la primera restricción

X1 = 15 y X2 = 5; es factible y Z = -40
6
La región factible del modelo es:

8
(15,5.5)

(15,6)
6

(10,5) (15,5)
4

2 4 6 8 10 12 14 16 18 20 22

La solución: X1 = 10 y X2 = 5, es factible y Z = -45

7
METODO DE “BRANCH AND BOUND”

8
Esquema de algoritmo de ramificación y acotación

9
PROBLEMA PLP con B&B

Una empresa fabrica dos modelos de lápiz de grafito, el modelo HB Y 2B,

con un beneficio de 1 sol y 1.2 sol respectivamente.
El modelo HB es el más largo, especial para estudiantes, para su
fabricación requiere 1 gr de grafito y 9m3 de madera de enebro.
Por otro lado, el modelo 2B, más pequeño y un trazo más condensado,
especial para dibujar, requiere de 5gr de grafito y 6m3 de enebro.
Sabiendo que se cuenta 25 gr de grafito y 49.5m3 de madera de enebro.
¿Cuántos lápices de modelos HB y 2B se deben fabricar, sabiendo que se
pretende maximizar los benéficos?

10
Modelo
Variables de decisión
x1: Cantidad de lápices del modelo HB a fabricar.
x2: Cantidad de lápices del modelo 2B a fabricar.
Función objetivo:
Max Z = x1 + 1.2x2
Restricciones
x1 + 5x2 <= 25 (Cantidad de grafito en gramos)
9x1 + 6x2 <= 49.5 (Cantidad de madera de enebro en m3)
x1, x2 >= 0, enteros

11
Gráfico 01 Debido a que las dos variables son no enteras,
cogemos arbitrariamente una de ellas, en este
caso, cogemos al 4.5.
Cogemos solo la parte entera (4) y le sumamos
6
1. Tendríamos la recta 4 y 5 para X2.
X1 = 2.5 Estas rectas conformarán nuevas
5
X2 = 4.5 restricciones para el modelo, formando así un
Z= 7.9 nuevo problema (sub problema), en este caso
4 serían:
X2>=5 (para un sub problema)
X2<=4 (para otro sub problema)
3
X2
Identificamos la intersección con la
región factible del problema relajado,
2
en caso no exista intersección
diremos que no es factible.
1

0
0 1 2 3 4 5 6
X1 12
 P0

Max Z = x1 + 1.2x2
Sujeto a:
x1 + 5x2 <= 25
9x1 + 6x2 <= 49.5
X1= 2.5, X2= 4.5, Z=7.9
Solución no entera, X2<=4 X2>=5
pero entera
superior a la cota
entera P1 P2
encontrada. Hay 1ra Cota
que obtenida.
x1 + 5x2 <= 25 x1 + 5x2 <= 25
seguir ramificando. No seguimos
9x1 + 6x2 <= 49.5 9x1 + 6x2 <= 49.5 ramificando.
X2<=4 X2>=5
X1=2.833, X2=4, Z=7.633 X1=0, X2=5, Z=6

13
Gráfico 02
6
Cogemos X1 y operamos.
X1>=3 (para un sub problema)
X1<=2 (para otro sub problema)
5
Identificamos la intersección con la
región factible.
4
X1 = 2.833
X2 = 4
3
X2 Z= 7.633

0
0 1 2 3 4 5 6
X1 14
 Max Z = x1 + 1.2x2
P0 Sujeto a:
x1 + 5x2 <= 25
9x1 + 6x2 <= 49.5
X1= 2.5, X2= 4.5, Z=7.9

X2<=4 X2>=5 1ra Cota

x1 + 5x2 <= 25 x1 + 5x2 <= 25 obtenida.
2da Cota 9x1 + 6x2 <= 49.5 9x1 + 6x2 <= 49.5
obtenida. P1 X2<=4 X2>=5 P2
No seguimos
ramificando. X1=2.833, X2=4, Z=7.633 X1=0, X2=5, Z=6

x1 + 5x2 <= 25
9x1 + 6x2 <= 49.5 X1<=2 x1 + 5x2 <= 25
P11 X1>=3 9x1 + 6x2 <= 49.5
X2<=4
X2<=4 P12
X1<=2
X1>=3
Solución no
X1=2, X2=4, entera, mejor
X1=3, X2=3.75,
Z=6.8 que la cota 2.
Z=7.5
Seguimos
ramificando.
15
Gráfico 03
6

Cogemos X2 y operamos.
5
INFACTIBLE X2<=3 (para un sub problema)
X2>=4 (para otro sub problema)
4
X1 = 3 , X2 = 3.75, Z= 7.5
3
X2 Identificamos la
intersección con
2
la región
factible.
1

0
0 1 2 3 4 5 6
X1 16
 Max Z = x1 + 1.2x2
P0 Sujeto a:
x1 + 5x2 <= 25
9x1 + 6x2 <= 49.5
X1= 2.5, X2= 4.5, Z=7.9
X2<=4 X2>=5
1ra Cota
P1
obtenida.
x1 + 5x2 <= 25 x1 + 5x2 <= 25
9x1 + 6x2 <= 49.5 9x1 + 6x2 <= 49.5 P2
X1<=2 X2<=4 X2>=5
X1=2.833, X2=4, Z=7.633 X1=0, X2=5, Z=6
2da Cota x1 + 5x2 <= 25
obtenida. 9x1 + 6x2 <= 49.5 X1>=3
X2<=4
P11 X1<=2 x1 + 5x2 <= 25
9x1 + 6x2 <= 49.5
P12 No se halló
X1=2, X2=4, X2<=4
Z=6.8 X1>=3 P122 solución para
X1=3, X2=3.75, éstas
x1 + 5x2 <= 25
Solución no Z=7.5 restricciones.
9x1 + 6x2 <= 49.5
x1 + 5x2 <= 25
entera. Mejor X2<=4
que la 2da P121 9x1 + 6x2 <= 49.5
X2>=4 X1>=3
X2<=4 , X1>=3
cota. X2<=3 X2>=4
X2<=3
Continuamos… INFACTIBLE 17
X1=3.5, X2=3, Z=7.1
Gráfico 04
Cogemos X1 y operamos.
6
X1<=3 (para un sub problema)
X1>=4 (para otro sub problema)
5

X1 = 3.5 , X2 = 3, Z= 7.1
3
X2 Identificamos la
intersección con
2
la región
factible.
1

0
0 1 2 3 4 5 6
X1 18
 Max Z = x1 + 1.2x2
P0
Sujeto a:
x1 + 5x2 <= 25
9x1 + 6x2 <= 49.5
X1= 2.5, X2= 4.5, Z=7.9
P11
X1<=2 X2<=4 X2>=5
x1 + 5x2 <= 25 P1 x1 + 5x2 <= 25 x1 + 5x2 <= 25 P2 1ra Cota
2da Cota 9x1 + 6x2 <= 9x1 + 6x2 <= 49.5 9x1 + 6x2 <= 49.5 obtenida
obtenida 49.5 X2<=4 X2>=5
X2<=4 X1=2.833, X2=4, Z=7.633 X1=0, X2=5, Z=6
X1<=2
X1>=3
X1=2, X2=4,
x1 + 5x2 <= 25
P1211 Z=6.8
9x1 + 6x2 <= 49.5 P12
x1 + 5x2 <= 25
3ra cota X2<=4 P122
9x1 + 6x2 <= 49.5 P121
Obtenida. X1>=3
X2<=4 , X1>=3 X1<=3 x1 + 5x2 <= 25 x1 + 5x2 <= 25
X2<=3, X1<=3 X1=3, X2=3.75, Z=7.5 9x1 + 6x2 <= 49.5
9x1 + 6x2 <=
X1=3, X2=3, Z=6.6 49.5 X2<=4
X2<=4 , X1>=3 X2<=3 X2>=4 X1>=3
x1 + 5x2 <= 25 X2<=3 X2>=4
9x1 + 6x2 <= 49.5 X1=3.5, X2=3, Z=7.1 INFACTIBLE
P1212 X2<=4 , X1>=3
X1>=4 Solución no entera,
X2<=3, X1>=4
peor que 2da Cota. TERMINAMOS!
X1=4, X2=2.25, Z=6.7 19
Podamos.
 Finalizando el proceso de ramificación y poda,
para el e
La solución óptima entera corresponde al sub problema P11
Max Z = x1 + 1.2x2
x1 + 5x2 <= 25
9x1 + 6x2 <= 49.5
X2<=4
X1<=2

La solución óptima es:

Fabricar 2 lápices del modelo HB y 4 lápices del
modelo 2B.
Obteniendo un ingreso total de 6.8 Soles.
20
PROGRAMACIÓN ENTERA BINARIA

Es un método muy parecido al de ramificación y

acotamiento para modelos mixtos y puros. Sin embargo
las variables solo pueden tomar el valor de x ∈ 0,1

Ejemplo:
• Asignación
• Tipo mochila
• Casamentero
• Método Aditivo de Egón Balas

21
 Ejemplo aplicativo

Un excursionista planea salir de campamento. Hay cinco artículos

que desea llevar consigo, pero entre todos sobrepasan las 60 kilos
que considera puede cargar. Para ayudarse en la selección ha
asignado un valor a cada artículo en orden ascendente de
importancia.

ARTICULO 1 2 3 4 5
PESO 42 23 21 15 7
VALOR 100 60 70 15 15

22
MAX Z= 100 X1 + 60 X2 + 70 X3 + 15 X4 + 15 X5

S.A

42 X1 + 23 X2 + 21 X3 + 15 X4 + 7 X6 <= 60

Calculamos los ci/ai

OBJETO Ci/ai
1 100/42 = 2,38

2 60/23 = 2,61
3 70/21 = 3,33
4 15/15 = 1
5 15/7 = 2,14
23
Llenamos la mochila con el mayor cociente.

b = valor de la variable sustituido en las restricciones

Z = valor de la variable sustituido en la función objetivo

VARIABLE b Z
X3 = 1 39 70
X2=1 16 130
X1=8/21 0 168,09
X4=0 0 168,09
X5=0 0 168,09
24
 Variable b Z
X1= 0 60 0
X3=1 39 100
X2=1 16 130
Variable b Z X1=0
X5=1 9 145
X3 = 1 39 70
X4=3/5 0 145,6
X2=1 16 130
X1=8/21 0 168,09
X4=0 0 168,09 Variable b Z
X5=0 0 168,09 X1 = 1 18 100
X1=1 X3=6/7 0 100,86
X2=0 0 100,86
X4=0 0 100,86
X5=0 0 100,86

25
 Variable b Z
X4= 0 60 0
X1=0 60 0
X3=1 39 70
Variable b Z X4=0 X2=1 16 130
X1= 0 60 0 X5=1 9 145
X3=1 39 100
X2=1 16 130
X5=1 9 145 Variable B Z
X4=3/5 0 145,6 X4 = 1 45 15
X4=1
X3=0 45 15
X2=1 24 85
X1 =0 1 145
X5=1/7 0 145,14

26
 Variable b Z
X5= 0 60 0
X1=0 60 0
X4=1 45 15
Variable b Z X5=0 X3=1 24 85
X4 = 1 45 15 X2=1 1 145
X3=0 45 15
X2=1 24 85 Variable B Z
X1 =0 1 145 X5 = 1 53 15
X5=1/7 0 145,14 X5=1
X1=0 53 15
X4=1 38 30
X3 =1 17 100
X2=17/23 0 100,74

27
 Solución Optima

X1= 0
X2= 1
X3= 1
X4= 0
X5= 1
Z=145

Se llevara en la mochila los objetos 2, 3 y 5. Con

un valor de 145 y un peso de 51 kilos

28
 Variable b Z
ÁRBOL FINAL
X4= 0 60 0
X1=0 60 0

Variable b Z X4=0 X3=1 39 70 Variable b Z

X1= 0 60 0 X2=1 16 130 X5= 0 60 0
X3=1 39 100 X5=1 9 145 X1=0 60 0
X2=1 16 130 X4=1 45 15
X1=0 X5=0
X5=1 9 145 Variable B Z X3=1 24 85
Variable b Z X4=3/5 0 145,6 X2=1 1 145
X4 = 1 45 15
X3 = 1 39 70 X4=1
X3=0 45 15
X2=1 16 130
X2=1 24 85 Variable B Z
X1=8/21 0 168,09
X1 =0 1 145 X5 = 1 53 15
X4=0 0 168,09 Variable b Z
X5=1/7 0 145,14 X1=0 53 15
X5=0 0 168,09 X1 = 1 18 100 X5=1
X1=1 X4=1 38 30
X3=6/7 0 100,86
X3 =1 17 100
X2=0 0 100,86
X2=17/23 0 100,74
X4=0 0 100,86
X5=0 0 100,86
29
 Problema PLB con B&B
La empresa Spirit dedicada a la construcción de soluciones con tecnología de
información, tiene para los 5 primeros meses del 2017, los siguientes proyectos:

PROYECTO PRECIO VENTA COSTO

configurador I (1) 15000 10100
configurador II (2) 10000 6000
configurador III (3) 11500 7000
web app sunat (4) 25000 18000
web desk redondos (5) 18000 13700
web services sunat (6) 13000 6500
PRESUPUESTO 35000

Pero tiene las siguientes dos restricciones:

1. Tiene que desarrollar mínimamente un configurador.
2. No puede desarrollar las dos web (app sunat, desk redondos), solo puede realizar
una de ellas o ninguna, por motivos de tiempo.
¿Qué proyectos debe realizar, de tal manera que maximice su ingreso?
30
 Modelo
Variables de decisión
xi 1: Sí el proyecto i se debe realizar.
0: No debe realizarse el proyecto i.
i= {1,2,3,4,5,6}
Función objetivo:
Max Z = 15000x1+10000x2+11500x3+25000x4+18000x5+13000x6
Restricciones
10100x1+6000x2+7000x3+18000x4+13700x5+6500x6 <= 35000 (presupuesto)

X1 + X2 + X3 >= 1 Mínimamente un configurador

x4 + x5 <=1 Una de las web (app sunat, desk redondos) o ninguna, pero no las dos

x1, x2, x3, x4, x5, x6 : {0,1}

31
 p0
EMPEZANDO DE P0 (RAÍZ) P11: Z = 49500
X1 1 X3 1 X5 0
X2 1 X4 0.3 X6 1
Z=57000

X4 = 0 X4 = 1

p1 p2
X1 1 X3 1 X5 0.39 X1 0 X3 0.64 X5 0
X2 1 X4 0 X6 1 X2 1 X4 1 X6 1
Z=56594.89 Z=55392.86

X5 = 0
X5 = 1 X3 = 0 X3 = 1

p21 p22
p11 P12
X1 0.45 X3 0 X5 0 X1 0 X3 1 X5 0
X1 1 X3 1 X5 0 X1 0.18 X3 1 X5 1
X2 1 X4 1 X6 1 X2 0.58 X4 1 X6 1
X2 1 X4 0 X6 1 X2 1 X4 0 X6 1
Z=54683.17 Z=55333.30
Z=49500 Z=55173.77

32
RAMIFICANDO POR P21 p21 P11: Z = 49500
X1 0.45 X3 0 X5 0
X2 1 X4 1 X6 1 P211: Z = 48000
Z=54683.17
P2121: Z = 53000
X1 = 0 X1 = 1
P2121: Z = 53000
p211 p212
X1 0 X3 0 X5 0 X1 1 X3 0 X5 0
X2 1 X4 1 X6 1 X2 0.66 X4 1 X6 1
Z=48000 Z=53666.67

X2 = 0 X2 = 1

p2121 p2122
X1 1 X3 0 X5 0 X1 1 X3 0 X5 0
X2 0 X4 1 X6 1 X2 1 X4 1 X6 0.13
Z=53000 Z=51800

33
RAMIFICANDO POR P22 p22 P11: Z = 49500
X1 0 X3 1 X5 0
X2 0.58 X4 1 X6 1 P211: Z = 48000
Z=55333.30 P2121: Z = 53000
X2 = 0 X2 = 1
P2211: Z = 49500
p221 p222
X1 0.35 X3 1 X5 0 X1 0 X3 1 X5 0
X2 0 X4 1 X6 1 X2 1 X4 1 X6 0.62
Z=54698.02 Z=54500

X1 = 0 X1 = 1 X3 = 0 X3 = 1

p2211 P2212 p2221 p2222

X1 0 X3 1 X5 0 X1 X3 X5 X1 0.4 X3 1 X5 0 X1 X3 X5
X2 0 X4 1 X6 1 X2 X4 X6 X2 1 X4 1 X6 0 X2 X4 X6
Z=49500 INFACTIBLE Z=52440.59 INFACTIBLE

34
RAMIFICANDO POR P12 p12 P11: Z = 49500
X1 0.18 X3 1 X5 1
X2 1 X4 0 X6 1 P211: Z = 48000
Z=55173.77 P2121: Z = 53000
X1 = 0 X1 = 1
P2211: Z = 49500
p121 p122
P121: Z = 52500
X1 0 X3 1 X5 1 X1 1 X3 0 X5 1
X2 1 X4 0 X6 1 X2 0.78 X4 0 X6 1
Z=52500 Z=53833

X2 = 0 X2 = 1

p1221 p1222
X1 1 X3 0.6 X5 1 X1 1 X3 0 X5 1
X2 0 X4 0 X6 1 X2 1 X4 0 X6 0.8
Z=53721.43 Z=53400

35
RAMIFICANDO POR 1221 P11: Z = 49500

P211: Z = 48000
p1221
X1 1 X3 0.6 X5 1 P2121: Z = 53000
X2 0 X4 0 X6 1
P2211: Z = 49500
Z=53721.43
P121: Z = 52500
X3 = 0 X3 = 1
P12211: Z = 46000

p12211 p12212
X1 1 X3 0 X5 1 X1 1 X3 1 X5 1
X2 0 X4 0 X6 1 X2 0 X4 0 X6 0.65
Z=46000 Z=52900

36
RAMIFICANDO POR 1222 P11: Z = 49500

P211: Z = 48000
p1222 P2121: Z = 53000
X1 1 X3 0 X5 1
X2 1 X4 0 X6 0.8 P2211: Z = 49500
Z=53400
P121: Z = 52500

X6 = 0 X6 = 1
P12211: Z = 46000

p12221 p12222
X1 1 X3 0.74 X5 1 X1 X3 X5
X2 1 X4 0 X6 0 X2 X4 X6
Z=51542.86 INFACTIBLE

TERMINAMOS!!!

37
VISTA DE LA RAMIFICACIÓN

p21
21

38
Finalizando el proceso de ramificación y poda, para el problema
de tipo PLB.

La solución óptima entera corresponde al sub problema P2121

Max Z = 15000x1+10000x2+11500x3+25000x4+18000x5+13000x6
SUJETO A:
10100x1+6000x2+7000x3+18000x4+13700x5+6500x6 <= 35000
X1 + X2 + X3 >= 1
x4 + x5 <=1
DONDE: X1=1, X2=0, X3=0, X4=1, X5=0, X6=1

La solución óptima es:

Desarrollar los proyectos:
• Configurador I
• Web App Sunat
• Web Services Sunat
Obteniendo un ingreso de 53000 soles. 39
 MÉTODOS DE PLANOS DE CORTE O ALGORITMO DE
GOMORY
➢Un método para resolver problemas de Programación Lineal Entera Mixta y Pura es el
procedimiento del Plano Cortante de Gomory.

➢Este procedimiento que produce la mejor solución cuando las variables deben ser expresadas
en números enteros; inicia resolviendo el problema por el método Simplex sin considerar el
requerimiento de enteros.

➢Después de que la solución óptima no entera es obtenida a través del Simplex, una nueva
restricción Lineal es desarrollada para satisfacer los requerimientos de enteros.

➢La nueva ecuación restrictiva es añadida a la tabla del Simplex y una nueva variable entra en
solución. Cuando la nueva variable entra en solución, causa que al menos una de las variables
básicas tome un valor entero. El proceso continuo hasta que todas las variables básicas sean
enteras. 40
 ALGORITMO FRACCIONAL DE GOMORY
• Paso 1: Obtenga la solución optima usando el método simplex

• Paso 2: ¿Si son todas las variables básicas enteras? Pase al último paso, lo
contrario continúe con el paso 3.

• Paso 3: Seleccione la restricción con la mayor parte fraccional en su

solución

• Paso 4: De tal selección se separan la parte entera, es decir, quedarse

solamente con la parte fraccionaria.

• Paso 5: Y de ello tendremos únicamente a las variables de holgura sin

multiplicar por (-1) ,siendo esta ecuación menor igual a “0”.(ecuación 1)

• Paso 6: Se toman las restricciones al inicio del problema estandarizadas, a

continuación deberá de despejar las variables no básicas, con el objetivo de
tener ecuaciones en función a las variables básicas.
41
ALGORITMO FRACCIONAL DE GOMORY

• Paso 7: Deberá de reemplazar estas variables en la ecuación

anterior (ecuación 1), teniendo una nueva restricción en función a
las variables básicas.

• Paso 8: Ahora se tendrá un nuevo problema agregando la nueva

restricción, aplicando el método simplex.

• Paso 9: Si son todas las variables básicas enteras, vaya al último

paso, caso contrario, vaya al paso 3.

▪ Paso 10: Se ha obtenido la solución óptima entera

42
 Algoritmo Fraccional de Gomory
Ejemplo:

Función Objetivo: Maximizar Z = 7x1 + 10x2

S. a:
-x1 + 3x2 ≤ 6
7x1 + x2 ≤ 35
Criterio de no negatividad: x1, x2 ≥ 0 y entero

Estandarizando:
Maximizar Z = 7x1 + 10x2 + 0x3 + 0x4

Sujeto a:
-x1 + 3x2 + x3 = 6
7x1 + x2 + x4 = 35

x1, x2, x3, x4 ≥ 0 y entero

43
 Algoritmo Fraccional de Gomory
PRIMERA TABLA SIMPLEX
Cj 7 10 0 0
Ck Xk bi X1 X2 X3 X4 b
0 X3 6 -1 3 1 0 2 Elemento Pivote
0 X4 35 7 1 0 1 35
Zj 0 0 0 0 0
Zj- Cj -7 -10 0 0
SEGUNDA TABLA SIMPLEX

Cj 7 10 0 0
Ck Xk bi X1 X2 X3 X4 b
10 X2 2 -1/3 1 1/3 0 -6
Elemento Pivote 0 X4 33 22/3 0 -1/3 1 99/2
Zj 20 -10/3 10 10/3 0
Zj- Cj -31/3 0 -10/3 0
44
 Algoritmo Fraccional de Gomory
TERCERA TABLA SIMPLEX

Cj 7 10 0 0
Ck Xk bi X1 X2 X3 X4
10 X2 7/2 0 1 7/22 1/22
7 X1 9/2 1 0 -1/22 3/22
Zj 133/2 7 10 63/22 31/22
Zj- Cj 0 0 63/22 31/22
La solución óptima es: X1 = 9 / 2
X2 = 7 / 2
X3 = 0
X4 = 0
Z = 133 / 2
45
 Información de la tabla Simplex Óptima

Ecuación X2: X2 + 7/22 X3 + 1/22 X4 = 7/2

Ecuación X1: X1 – 1/22 X3 + 3/22 X4 = 9/2

En la primera iteración del algoritmo del plano de corte se puede usar cualquiera de los cortes .
Cálculo de la nueva restricción, a partir de la Ecuación 1

X2 + 7/22 X3 + 1/22 X4 = 7/2

Remplazamos cada coeficiente de la ecuación, por la suma de un número entero de cualquier
signo y una fracción no negativa menor que uno (1).

(1+0)X2 + (0+7/22)X3 + (0+1/22)X4 = (3+1/2)

Trasladamos los términos con coeficiente entero, al lado izquierdo.

X2 - 3 = 1/2 - 7/22X3 - 1/22X4

Entera Fraccionaria 46
Tomamos la parte fraccional, en la cual tiene q ser (<=0)
1/2 - 7/22X3 - 1/22X4 <= 0
-7/22X3 - 1/22X4 <= -1/2
Adicionando una variable de holgura (s1)
-7/22X3 - 1/22X4 + s1= -1/2 , s1=>0 ………………………CORTE I

Esta restricción se añade como una restricción secundaria a la tabla simplex óptima.

Cj 7 10 0 0 0
Ck Xk bi X1 X2 X3 X4 S1
10 X2 7/2 0 1 7/22 1/22 0
7 X1 9/2 1 0 -1/22 3/22 0
0 S1 -1/2 0 0 -7/22 -1/22 1
Zj 133/2 7 10 63/22 31/22 0
Zj- Cj 0 0 63/22 31/22 0

La tabla símplex es óptima, pero no factible. Aplicamos el método simplex dual para recuperar la
factibilidad, lo que nos da: 47
TABLA SIMPLEX (RESULTADO DEL PRIMER CORTE)

Cj 7 10 0 0 0
Ck Xk Bi X1 X2 X3 X4 S1
10 X2 3 0 1 0 0 1
7 X1 32/7 1 0 0 1/7 -1/7
0 X3 11/7 0 0 1 1/7 -22/7
Zj 62 7 10 0 1 9
Zj- Cj 0 0 0 1 9

Restricción para el segundo corte

48
 Algoritmo Fraccional de Gomory
Solución obtenida:
X2 = 3
X1 = 32/7
X3 = 11/7
Z = 62
La última solución todavía es de no enteros en X1 Y X3.
Entonces seleccionamos X1 como el renglón fuente

X1 + 1/7 X4 – 1/7 S1 = 32/7

X1 + (0 + 1/7) X4 – (-1 + 6/7) S1 = (4 + 4/7)

El corte asociado es:

-1/7 X4 – 6/7 S1 + 4/7 ≤ 0

-1/7 X4 – 6/7 S1 ≤ -4/7
-1/7 X4 – 6/7 S1 + S2 = -4/7 , s2=>0 .............(CORTE II)
Ahora agregamos la nueva restricción a nuestra última tabla simplex dual.
49
 Algoritmo Fraccional de Gomory
PRIMERA TABLA SIMPLEX DUAL

Cj 7 10 0 0 0 0
Ck Xk Bi X1 X2 X3 X4 S1 S2 d
10 X2 3 0 1 0 0 1 0 3
7 X1 32/7 1 0 0 1/7 -1/7 0 -32
0 X3 11/7 0 0 1 1/7 -22/7 0 -½
0 S2 -4/7 0 0 0 -1/7 -6/7 1 2/3
Zj 62 7 10 0 1 9 0
Zj-Cj 0 0 0 1 9 0
(Zj-Cj)/arj - - - -7 -63/7 -

El menos
negativo Elemento pivote

50
 Algoritmo Fraccional de
Gomory
ULTIMA TABLA SIMPLEX(RESULTADO DEL SEGUNDO CORTE)

Cj 7 10 0 0 0 0
Ck Xk bi X1 X2 X3 X4 S1 S2
10 X2 3 0 1 0 0 1 0
7 X1 4 1 0 0 0 -1 1
0 X3 1 0 0 1 0 -4 1
0 X4 4 0 0 0 1 6 -7
Zj 58 7 10 0 0 3 7
Zj-Cj 0 0 0 0 3 -7

51
 Algoritmo Fraccional de Gomory

La Solución Optima Entera es Cuando:

X2=3 S1=0
X1=4 S2=0
X3=1
X4=4
Z=58

52
EJERCICIO 02

La función Objetivo:
ZMIN = 35X1 + 48X2
Las restricciones:
23X1 + 32X2 ≥120
15X1 + 29X2 ≥ 50

x1, x2 ≥ 0 y entero

53
Paso 1: Dualizamos el problema

ZMAX = 120X1 + 50X2

s.a.
23X1 + 15X2 ≤ 35
32X1 + 29X2 ≤ 48

Paso 2: Convertir las inecuaciones en ecuaciones

23X1 + 15X2 + 1X3 + 0X4 = 35

32X1 + 29X2 + 0X3 + 1X4 = 48

54
Paso 3: Resolvemos el problema mediante el método simplex

Cj 120 50 0 0
Ck Xk Bi X1 X2 X3 X4
0 X3 1/2 0 -5.84 1 -0.72
120 X1 48/32 1 0.91 0 0.03
Zj 180 120 108.75 0 3.75
Zj- Cj 0 58.75 0 3.75

55
Paso 4: Obtenemos la fila de la variable que queremos convertir

X1 + 0.91X2 + 0X3 + 0.03X4 = 48/32

Paso 5: Convertimos las fracciones mayores que 1 en menores que 1

X1 + 0.91X2 + 0.03X4 = 1 + 0.5

Paso 6: Separamos los enteros de los fraccionarios o decimales

X1 - 1 = - 0.91X2 - 0.03X4 + 0.5

56
Paso 7: Tomamos la parte fraccional, en la cual tiene que ser (≤ 0)

- 0.91X2 - 0.03X4 + 0.5 ≤ 0

- 0.91X2 - 0.03X4 ≤ - 0.5

Paso 8: Agregamos una variable de holgura

- 0.91X2 - 0.03X4 + X5 ≤ - 0.5

57
Paso 9: Agregamos la ecuación en el simplex y resolvemos

Cj 120 50 0 0 0
Ck Xk Bi X1 X2 X3 X4 X5
0 X3 1/2 0 -5.84 1 -0.72 0
120 X1 48/32 1 0.91 0 0.03 0
0 X5 -0.5 0 -0.91 0 -0.03 1
Zj 180 120 108.75 0 3.75
Zj- Cj 0 58.75 0 3.75

58
Paso 10: Si las variables reales son enteras acaba el problema, sino
aplicamos de nuevo gomory (paso 4)

Cj 120 50 0 0 0
Ck Xk Bi X1 X2 X3 X4 X5
0 X3 675/182 0 0 1 -48/91 -584/91

120 X1 1 1 0 0 0 0
50 X2 50/91 0 1 0 3/91 -100/91

Zj 13420/91 120 50 0 150/91 -5000/91

Zj- Cj 0 0 0 150/91 -5000/91

59
X2 + (3/91)X4 – (100/91)X5 = 50/91

X2 + (3/91)X4 - 2+ (82/91)X5 = 50/91

X2 – 2 = -(3/91) X4 – (82/91) X5 + (50/91)

-(3/91) X4 – (82/91) X5 + X6 ≤ -(50/91)

60
 Cj 120 50 0 0 0 0
Ck Xk Bi X1 X2 X3 X4 X5 X6
0 X3 675/182 0 0 1 -48/91 -584/91 0

120 X1 1 1 0 0 0 0 0

3/91 -100/91 0
50 X2 50/91 0 1 0
-3/91 -82/91 1
0 X6 -50/91 0 0 0
Zj 13420/91 120 50 0 150/91 -5000/91 0

Zj- Cj 0 0 0 150/91 -5000/91 0

61
 Cj 120 50 0 0 0 0
Ck Xk Bi X1 X2 X3 X4 X5 X6

0 X3 75/2275 0 0 1 0 1312/91 -2040/91

120 X1 1 1 0 0 0 0 0
1
50 X2 0 0 1 0 0 -82/91
-91/3
0 X4 0 0 0 1 82/3
50/3

Zj 120 120 50 0 0 -4000/91 50

Zj- Cj 0 0 0 0 -4000/91 50

X1 = 1 X2 = 0 Z = 120

62
 Método de Enumeración Exhaustiva o
Explicita
➢ Consiste en enumerar todas las soluciones posibles, a partir de los
valores tomados para las variables enteras y realizar todas las
combinaciones posibles hasta encontrar una combinación que nos
proporcione el valor óptimo de la función objetivo y que cumpla con
todas las restricciones del problema.

Principal Desventaja:

❖Es el número de variables, ya que se presentan demasiadas

combinaciones antes de encontrar la solución óptima.

63
Ejemplos: Problema “PEB”

➢ Una empresa esta estudiando la posibilidad de expansión mediante la

construcción de una nueva fábrica ya sea en la Ciudad 1 o en la Ciudad 2 o
en ambas ciudades. Si se construye una fábrica en la ciudad X, se puede
construir un almacén en dicha ciudad, pero solo se construiría uno. La
siguiente tabla muestra el beneficio aportado por la inversión y costes.
Sabiendo que el capital total disponible es de 10.
Decisión ¿Sí o No? Beneficio Coste
1 Fábrica en la Ciudad 1 9 6
2 Fábrica en la Ciudad 2 5 3
3 Almacén en la Ciudad 1 6 5
4 Almacén en la Ciudad 2 4 2

✓ Se pide encontrar la solución que maximiza el beneficio total

64
Ejemplos: Problema “PEB”

Solución

[Link] de Decisión: 𝑋 , 𝑋 , 𝑋 , 𝑋 Variables Binarias(0 o 1)

1 2 3 4
𝑋𝑖 = 1 → Afirmación
𝑋1 : Construir fábrica en ciudad 1 𝑋3 : Construir almacén en ciudad 1 𝑋𝑖 = 0 → Negación
𝑋2 : Construir fábrica en ciudad 2 𝑋4 : Construir almacén en ciudad 2

[Link]ón Objetiva:
Max Z = 9𝑋1 + 5𝑋2 + 6𝑋3 + 4𝑋4

[Link] a: 6𝑋 + 3𝑋 + 5𝑋 + 2𝑋 ≤ 10 [Link] de No-Negatividad :

1 2 3 4
𝑋3 ≤ 𝑋1 𝑋1 , 𝑋2 , 𝑋3 , 𝑋4 ∈ {0,1}
𝑋4 ≤ 𝑋2
𝑋3 + 𝑋4 ≤ 1
65
❖ Hallando posibles soluciones: Casos Fab1 Fab2 Alm1 Alm2 Beneficio Coste Si/No
1 SI SI SI SI
2 SI SI SI NO
3 SI SI NO SI
4 SI NO SI SI
5 NO SI SI SI
𝑛 4 6 SI SI NO NO
2 2 = 16 7 SI NO SI NO
8 NO SI SI NO
9 SI NO NO SI
10 NO SI NO SI
11 NO NO SI SI
12 SI NO NO NO
13 NO SI NO NO
14 NO NO SI NO
15 NO NO NO SI
16 NO NO NO NO 66
Casos Fab1 Fab2 Alm1 Alm2 Beneficio Coste Si/No
1 SI SI SI SI --- ---
2 SI SI SI NO 20 14
3 SI SI NO SI 18 11
4 SI NO SI SI --- ---
Decisión ¿Sí o No? Beneficio Coste
5 NO SI SI SI --- ---
1 Fábrica en la 9 6
6 SI SI NO NO 14 9 Ciudad 1
7 SI NO SI NO 15 11 2 Fábrica en la 5 3
Ciudad 2
8 NO SI SI NO --- ---
3 Almacén en 6 5
9 SI NO NO SI --- --- la Ciudad 1
10 NO SI NO SI 9 5 4 Almacén en 4 2
11 la Ciudad 2
NO NO SI SI --- ---
12 SI NO NO NO 9 6
13 NO SI NO NO 5 3
14 NO NO SI NO --- ---
15 NO NO NO SI --- ---
16 NO NO NO NO 0 0
67
Casos Fab1 Fab2 Alm1 Alm2 Beneficio Coste Si/No
1 SI SI SI SI --- --- ---
2 SI SI SI NO 20 14 NO
3 SI SI NO SI 18 11 NO
4 SI NO SI SI --- --- --- Decisión ¿Sí o No? Beneficio Coste
5 NO SI SI SI --- --- --- 1 Fábrica en la 9 6
6 SI SI NO NO 14 9 SI Ciudad 1
7 SI NO SI NO 15 11 NO 2 Fábrica en la 5 3
Ciudad 2
8 NO SI SI NO --- --- ---
3 Almacén en 6 5
9 SI NO NO SI --- --- ---
la Ciudad 1
10 NO SI NO SI 9 5 SI
4 Almacén en 4 2
11 NO NO SI SI --- --- --- la Ciudad 2
12 SI NO NO NO 9 6 SI
13 NO SI NO NO 5 3 SI
14 NO NO SI NO --- --- ---
15 NO NO NO SI --- --- ---
16 NO NO NO NO 0 0 SI
68
Casos Fab1 Fab2 Alm1 Alm2 Beneficio Coste Si/No
1 SI SI SI SI --- --- ---
2 SI SI SI NO 20 14 NO
3 SI SI NO SI 18 11 NO
4 SI NO SI SI --- --- ---
Decisión ¿Sí o No? Beneficio Coste
5 NO SI SI SI --- --- ---
9 SI 1 Fábrica en la 9 6
6 SI SI NO NO 14
Ciudad 1
7 SI NO SI NO 15 11 NO
2 Fábrica en la 5 3
8 NO SI SI NO --- --- --- Ciudad 2
9 SI NO NO SI --- --- --- 3 Almacén en la 6 5
10 NO SI NO SI 9 5 SI Ciudad 1
11 NO NO SI SI --- --- --- 4 Almacén en la 4 2
6 SI Ciudad 2
12 SI NO NO NO 9
13 NO SI NO NO 5 3 SI
14 NO NO SI NO --- --- ---
15 NO NO NO SI --- --- ---
16 NO NO NO NO 0 0 SI
69
Casos Fab1 Fab2 Alm1 Alm2 Beneficio Coste Si/No
1 SI SI SI SI --- --- ---
2 SI SI SI NO 20 14 NO
3 SI SI NO SI 18 11 NO
DONDE:
4 SI NO SI SI --- --- --- 𝑋1 = 1
5 NO SI SI SI --- --- --- 𝑋2 = 1
6 SI SI NO NO 14 9 SI 𝑋3 = 0
7
𝑋4 = 0
SI NO SI NO 15 11 NO
8 NO SI SI NO --- --- ---
9 SI NO NO SI --- --- ---
10 NO SI NO SI 9 5 SI
11 NO NO SI SI --- --- ---
12 SI NO NO NO 9 6 SI Max Z = 9𝑋1 + 5𝑋2 + 6𝑋3 + 4𝑋4
13 NO SI NO NO 5 3 SI
14 NO NO SI NO --- --- ---
15 NO NO NO SI --- --- ---
16 NO NO NO NO 0 0 SI Max Z = 14
70
 Ejemplos: Problema “PEB”
Solución
1. Función Objetiva: A. Hallando posibles valores de 𝑋1
A.1. Según la restricción “a”
MAX Z = 3𝑋1 + 5𝑋2
𝑋1 = 0,1,2,3,4,5,6,7,8
A.2. Según la restricción “b”
2. Sujeta a :
𝑋1 = 0,1,2

a) 𝑋1 + 𝑋2 ≤ 8 𝐸𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑋1 = 0,1,2
b) 3𝑋1 + 2𝑋2 ≤ 7 B. Hallando posibles valores de 𝑋2
B.1. Según la restricción “a”
𝑋2 = 0,1,2,3,4,5,6,7,8
3. Criterio de No-Negatividad: B.2. Según la restricción “b”
𝑋1 = 0,1,2,3
𝑋𝑖 ≥ 0 𝑖 = 1,2
𝐸𝑛𝑡𝑜𝑛𝑐𝑒𝑠 𝑋2 = 0,1,2,3
71
 Ejemplos: Problema “PEB”

C. Hallando posibles soluciones aplicando los valores 𝑋1 y 𝑋2

𝑿𝟏 𝑿𝟐 𝑹𝟏 𝑹𝟐 Z Admisible
𝐒𝟏 0 0
𝐒𝟐 0 1
𝐒𝟑 0 2
𝐒𝟒 0 3
𝐒𝟓 1 0
𝐒𝟔 1 1
𝐒𝟕 1 2
𝐒𝟖 1 3
𝐒𝟗 2 0
𝐒𝟏𝟎 2 1
𝐒𝟏𝟏 2 2
𝐒𝟏𝟐 2 3 72
 Ejemplos: Problema “PEB”

C. Hallando posibles soluciones aplicando los valores 𝑋1 y 𝑋2

𝑿𝟏 𝑿𝟐 𝑹𝟏 𝑹𝟐 Z Admisible
𝐒𝟏 0 0 0
𝐒𝟐 0 1 1
𝐒𝟑 0 2 2
𝐒𝟒 0 3 3
𝐒𝟓 1 0 1
𝐒𝟔 1 1 2
𝐒𝟕 1 2 3
𝐒𝟖 1 3 4
𝐒𝟗 2 0 2
𝐒𝟏𝟎 2 1 3
𝐒𝟏𝟏 2 2 4
𝐒𝟏𝟐 2 3 5 73
 Ejemplos: Problema “PEB”

C. Hallando posibles soluciones aplicando los valores 𝑋1 y 𝑋2

𝑿𝟏 𝑿𝟐 𝑹𝟏 𝑹𝟐 Z Admisible
𝐒𝟏 0 0 0 0
𝐒𝟐 0 1 1 2
𝐒𝟑 0 2 2 4
𝐒𝟒 0 3 3 6
𝐒𝟓 1 0 1 3
𝐒𝟔 1 1 2 5
𝐒𝟕 1 2 3 7
𝐒𝟖 1 3 4 9
𝐒𝟗 2 0 2 6
𝐒𝟏𝟎 2 1 3 8
𝐒𝟏𝟏 2 2 4 10
𝐒𝟏𝟐 2 3 5 12 74
 Ejemplos: Problema “PEB”

C. Hallando posibles soluciones aplicando los valores 𝑋1 y 𝑋2

𝑿𝟏 𝑿𝟐 𝑹𝟏 𝑹𝟐 Z Admisible
𝐒𝟏 0 0 0 0 0
𝐒𝟐 0 1 1 2 5
𝐒𝟑 0 2 2 4 10
𝐒𝟒 0 3 3 6 15
𝐒𝟓 1 0 1 3 3
𝐒𝟔 1 1 2 5 8
𝐒𝟕 1 2 3 7 13
𝐒𝟖 1 3 4 9 18
𝐒𝟗 2 0 2 6 6
𝐒𝟏𝟎 2 1 3 8 11
𝐒𝟏𝟏 2 2 4 10 16
𝐒𝟏𝟐 2 3 5 12 21 75
 Ejemplos: Problema “PEB”

C. Hallando posibles soluciones aplicando los valores 𝑋1 y 𝑋2

𝑿𝟏 𝑿𝟐 𝑹𝟏 𝑹𝟐 Z Admisible
𝐒𝟏 0 0 0 0 0
𝐒𝟐 0 1 1 2 5
𝐒𝟑 0 2 2 4 10
𝐒𝟒 0 3 3 6 15
𝐒𝟓 1 0 1 3 3
𝐒𝟔 1 1 2 5 8
𝐒𝟕 1 2 3 7 13
𝐒𝟖 1 3 4 9 18
𝐒𝟗 2 0 2 6 6
𝐒𝟏𝟎 2 1 3 8 11
𝐒𝟏𝟏 2 2 4 10 16
𝐒𝟏𝟐 2 3 5 12 21 76
 Ejemplos: Problema “PEB”

C. Hallando posibles soluciones aplicando los valores 𝑋1 y 𝑋2

𝑿𝟏 𝑿𝟐 𝑹𝟏 𝑹𝟐 Z Admisible
𝐒𝟏 0 0 0 0 0 SI
𝐒𝟐 0 1 1 2 5 SI
𝐒𝟑 0 2 2 4 10 SI
𝐒𝟒 0 3 3 6 15 SI
𝐒𝟓 1 0 1 3 3 SI
𝐒𝟔 1 1 2 5 8 SI
𝐒𝟕 1 2 3 7 13 SI
𝐒𝟖 1 3 4 9 18 NO
𝐒𝟗 2 0 2 6 6 SI
𝐒𝟏𝟎 2 1 3 8 11 NO
𝐒𝟏𝟏 2 2 4 10 16 NO
𝐒𝟏𝟐 2 3 5 12 21 NO 77
 Ejemplos: Problema “PEB”

C. Hallando posibles soluciones aplicando los valores 𝑋1 y 𝑋2

𝑿𝟏 𝑿𝟐 𝑹𝟏 𝑹𝟐 Z Admisible
𝐒𝟏 0 0 0 0 0 SI
𝐒𝟐 0 1 1 2 5 SI
𝐒𝟑 0 2 2 4 10 SI
𝐒𝟒 0 3 3 6 15 SI
𝐒𝟓 1 0 1 3 3 SI
𝐒𝟔 1 1 2 5 8 SI
𝐒𝟕 1 2 3 7 13 SI
𝐒𝟖 1 3 4 9 18 NO
𝐒𝟗 2 0 2 6 6 SI
𝐒𝟏𝟎 2 1 3 8 11 NO
𝐒𝟏𝟏 2 2 4 10 16 NO
𝐒𝟏𝟐 2 3 5 12 21 NO 78
 Ejemplos: Problema “PEB”

C. Hallando posibles soluciones aplicando los valores 𝑋1 y 𝑋2

𝑿𝟏 𝑿𝟐 𝑹𝟏 𝑹𝟐 Z Admisible
𝐒𝟏 0 0 0 0 0 SI
𝐒𝟐 0 1 1 2 5 SI
𝐒𝟑 0 2 2 4 10 SI
𝐒𝟒 0 3 3 6 15 SI
𝐒𝟓 1 0 1 3 3 SI
𝐒𝟔 1 1 2 5 8 SI
𝐒𝟕 1 2 3 7 13 SI
𝐒𝟖 1 3 4 9 18 NO
𝐒𝟗 2 0 2 6 6 SI
𝐒𝟏𝟎 2 1 3 8 11 NO
𝐒𝟏𝟏 2 2 4 10 16 NO
𝐒𝟏𝟐 2 3 5 12 21 NO 79
Ejemplos: Problema “PEB”

D. Concluyendo:

MAX Z = 3𝑿𝟏 + 5𝑿𝟐

Donde:
𝑿𝟏 = 𝟎
𝑿𝟐 = 𝟑
Z = 15

80