PROGRAMACIÓN ENTERA

Ejercicio
Ejemplo:

Max Z=3x1+4x2
s.a
2x1+x2<=6
2x1+3x2<=9
x1+x2 >=0 , enteras

SOLUCIÓN

P0
X1=2.25
X2=1.5
Z=12.75
X1<=2 X1>=3
Max Z=3X1+4X2 Max Z=3X1+4X2
s.a s.a
2X1+X2<=6 2X1+X2<=6
2X1+3X2<=9 2X1+3X2<=9
X1<=2 X1<=3
X1+X2 >=0 X1+X2 >=0

P1 P2
X1=2 X1=3
X2=1.67 X2=0 Solución Entero
Z=12.667
LP OPTIMUM FOUND AT STEP 2 LPZ=9
OPTIMUM FOUND AT STEP 2

OBJECTIVE FUNCTION VALUE OBJECTIVE FUNCTION VALUE

1) 12.66667 1) 9.000000

VARIABLE VALUE REDUCED COST VARIABLE VALUE REDUCED COST

X1 2.000000 0.000000 X1 3.000000 0.000000
X2 1.666667 0.000000 X2 0.000000 0.000000
 P1
X1=2
X2=1.67
X2<=1 X2>=2
Max Z=3x1+4| Z=12.667 Max Z=3x1+4x2
s.a s.a
2x1+x2<=6 2x1+x2<=6
2x1+3x2<=9 2x1+3x2<=9
X1<=2 X1<=2
X1<=1 X1<=1
x1+x2 >=0 x1+x2 >=0

P3 P4
Solución X1=2 X1=1.5
Entera X2=1 X2=2
Z=10 Z=12.5

P4
X1=1.5
X2=2
Z=12.5
X2<=1 X2>=2
Max Z=3x1+4x2 Max Z=3x1+4x2
s.a s.a
2x1+x2<=6 2x1+x2<=6
2x1+3x2<=9 < 2x1+3x2<=9
X1<=2 X1<=2
X1>=2 X1>=2
X1<=1 X1>=2
x1+x2 >=0 x1+x2 >=0

P5 P6
X1=1 X1=2
X2=2.33 X2=?
Z=12.33 Prob. Infactable

Investigación de Operaciones.
LP OPTIMUM FOUND AT STEP 1 LP OPTIMUM FOUND AT STEP 3

OBJECTIVE FUNCTION VALUE OBJECTIVE FUNCTION VALUE

P5
1) 11.00000 1) 12.00000
X1=1
VARIABLE VALUE REDUCED COST VARIABLE VALUE REDUCED COST
X1 1.000000 0.000000
X2=2.33 X1 0.000000 0.000000
X2 2.000000 0.000000 Z=12.33 X2 3.000000 0.000000

X2<=2 X2>=3
Max Z=3x1+4x2 Max Z=3x1+4x2
s.a s.a
2x1+x2<=6 2x1+x2<=6
2x1+3x2<=9 2x1+3x2<=9
X1<=2 X1<=2
X2>=2 X1>=2
X1<=1 X1<=1
X2<=2 X2>=3
x1+x2 >=0 x1+x2 >=0

P5 P5
X1=1 X1=0
X2=2 X2=3
Z=11 Z=12

SOLICION ENTERA SOLUCION FINAL

P1
Z=12.75

P1 P5
Z=12.667 Z=9

P3 P4
Z=10 Z=12.5

P5 P6
Z=12.333 INFACTIBLE

P7

Investigación de Operaciones.
 Z=11
P8
Z=12

Ejercicio #2

LP OPTIMUM FOUND AT STEP 2

Ejemplo:
OBJECTIVE FUNCTION VALUE
Max Z=5x1+2x2
s.a
1) 18.75000
2x1+2x2<=9
3x1+x2<=11
VARIABLE VALUE REDUCED COST
x1+x2 >=0 , enteras
X1 3.250000 0.000000
X2 1.250000 0.000000

SOLUCIÓN

P0
X1=3.25
X2=1.25
X2<=3 Z=18.75 X2>=4
Max Z=5x1+2x2 Max Z=5x1+2x2
s.a s.a
2x1+2x2<=9 2x1+2x2<=9
3x1+x2<=11 3x1+x2<=11
X1<=3 X1<=3
x1+x2 >=0 x1+x2 >=0

P1 P2
X1=3 X1=
X2=1.5 X2=
Z=18 Infactible

Investigación de Operaciones.
 LP OPTIMUM FOUND AT STEP 2

OBJECTIVE FUNCTION VALUE

1) 18.00000

VARIABLE VALUE REDUCED COST

X1 3.000000 0.000000
LP OPTIMUM FOUND AT STEP 1 X2 1.500000 0.000000
OBJECTIVE FUNCTION VALUE

1) 17.00000

VARIABLE VALUE REDUCED COST P1

X1 3.000000 0.000000
X2 1.000000 0.000000 X1=3
X2=1.25
X2<=3 X2>=4
Max Z=5x1+2x2 Z=18 Max Z=5x1+2x2
s.a s.a
2x1+2x2<=9 2x1+2x2<=9
3x1+x2<=11 3x1+x2<=11
X1<=3 X1<=3
X2<=1 X2<=1
x1+x2 >=0 x1+x2 >=0

P1 P1
X1=3 X1=2.5
X2=1 X2=2
Z=17 Z=16.5

P0
Z=18.75

P1 P2

Z=18 INFACTIBLE

Investigación de Operaciones.
 P3 P4
Z=17 Z=16.5

MÉTODO DE Transbordo

Ejercicio #1
Propuesto en el texto "Investigación de Operaciones de TAHA" que hace
referencia a una red de gasoductos en la que los distintos nodos representan
estaciones de bombeo y recepción, los costos se encuentran en las rutas de la
siguiente figura.
50000
60000 GALONES

1 3

20
3 9 30

2
7 4

6000 8 2 20000

6 4 5
VARIABLE DE DECICIONES :

X12 = Cantidad de galones enviados desde la estación 1, hacia la estación 2

X17 = Cantidad de galones enviados desde la estación 1, hacia la estación 7
X37 = Cantidad de galones enviados desde la estación 3, hacia la estación 7
X34 = Cantidad de galones enviados desde la estación 3, hacia la estación 4
X72 = Cantidad de galones enviados desde la estación 7, hacia la estación 2
X75 = Cantidad de galones enviados desde la estación 7, hacia la estación 5

Investigación de Operaciones.
X57 = Cantidad de galones enviados desde la estación 5, hacia la estación 7
X62 = Cantidad de galones enviados desde la estación 6, hacia la estación 2
X65 = Cantidad de galones enviados desde la estación 6, hacia la estación 5
X56 = Cantidad de galones enviados desde la estación 5, hacia la estación 6
X54 = Cantidad de galones enviados desde la estación 5, hacia la estación 4

RESTRICCIONES OFERTA :

X12 + X17 = 50000

X37 + X34 = 60000

RESTRICCIONES DE DEMANDA :

X12 + X72 + X62 = 90000

X34 + X54 =20000

RESTRICCIONES DE BALANCE :

X17 + X37 + X57 - X72 - X75 = 0

X56 - X65 - X62 = 0
X75 + X65 - X56 - X54 = 0

FUNCION OBJETIVO :

ZMIN = 20X12 + 3X17 + 9X37 + 30X34 + 40X72 + 10X75 + 10X57 + 8X62 + 4X65 + 4X56 +
2X54

Investigación de Operaciones.
 Ejercicio #2

Dos fabricas ha quedado de enviar en productos a Colombia , la entrada a la fabrica se

encuentra ubicada en el nodo R1, R2 , se conoce de antemano que el producto
permanece almacenado en los nodos 7, para llegar a dicho nodo hay que atravesar una
red de túneles que van conectados entre sí. El tiempo de vida que le queda al ala
empresa para la entrega es mínimo y se hace indispensable hallar la ruta de acceso al
nodo 7 más corta. Las distancias entre nodos de la mina se encuentran en la siguiente
gráfica dadas en cientos de metros. Formule un modelo de transbordo y resuelva
mediante cualquier paquete de herramientas de investigación operativa que permita
establecer la ruta más corta para poder así auxiliar al minero.

E 1500
3 0
6
900 A C 4
6
5
6 F 800
3 6
D
1120 B D D 3
4 D 7
Z G 700

RENOMBRAR CADA NODO DEFINIDOS:

XA,C = Cantidad de unidades enviadas desde P1 hacia T1

Investigación de Operaciones.
XA,D = Cantidad de unidades enviadas desde P1 hacia T2
XB,C = Cantidad de unidades enviadas desde P2 hacia T1
XB,D = Cantidad de unidades enviadas desde P2 hacia T2
XC,D = Cantidad de unidades enviadas desde T1 hacia T2
XC,E = Cantidad de unidades enviadas desde T1 hacia D1
XC,F = Cantidad de unidades enviadas desde T1 hacia D2
XD,F = Cantidad de unidades enviadas desde T2 hacia D2
XD,G = Cantidad de unidades enviadas desde T2 hacia D3
XE,F = Cantidad de unidades enviadas desde D1 hacia D2
XF,G = Cantidad de unidades enviadas desde D2 hacia D3

RESTRICCIONES:
XA,C + XA,D = 900
XB,C + XB,D = 1120

RESTRICCIONES DE DEMANDA:

XD,G + XF,G = 700

XD,F + XE,F = 800
XC,E = 1500

RESTRICCIONES DE BALANCEO PARA NODOS UNICAMENTE TRANSITORIAS:

XA,C + XB,C - XC,D - XC,E - XC,F = 0

XA,D + XB,D + XC,D - XD,F - XD,G = 0

RESTRICICIONES DE BALANCEO PARA NODOS TRANSITORIOS CON REQUERIMIENTO

XC,E - XE,F = 1500

XC,F + XD,F + XE,F - XF,G = 800

FUNCION OBJETIVA:

ZMIN = 6XA,C + 5XA,D + 3XB,C + 4XB,D + 6XC,D + 3XC,E + 6XC,F + 4XD,F + 6XD,G +
4XE,F + 3XF,G

Investigación de Operaciones.
Investigación de Operaciones.