1
Universidad Nacional Mayor de San MarcosFacultad de Ingeniería de Sistemas e Informática
Investigación Operativa I
ProgramaciónLineal Entera
y Binariay
Docente : Lic. Gabriel Solari Carbajal
ProgramaciónLineal Entera
2
2
PROBLEMA 01.-La compañía Mauser fabricante de fusiles automáticos
Programación Lineal Entera
Requerimientos unitarios de tiempo (en horas)
H di iblM d lM d l
La compañía Mauser, fabricante de fusiles automáticos,tiene 3 departamentos en los cuales se manufacturansus modelos S-1000 y S-2000, las capacidadesmensuales son las siguientes:
3
Departamento 1 4 2 1,600Departamento 2 2.5 1 1,200Departamento 3 4.5 1.5 1,600
DepartamentosHoras disponibles
en el siguiente mesModelo S-2000
Modelo S-1000
La utilidad del modelo S-1000 es de 40 dólares porunidad y la del modelo S-2000 es de 10 dólares por
Programación Lineal Entera
y punidad; suponiendo que la compañía puede vendercualquier cantidad de estos productos, debido acondiciones favorables de mercado.
Determinar el número de unidades de cada modelo quese debe de fabricar de manera que se maximice lautilidad total.
4
utilidad total.
3
SOLUCION.-Variables de decisión
Programación Lineal Entera
Variables de decisiónx1 : número de fusiles S-1000 que la compañía
Mauser va ha fabricar.x2 : número de fusiles S-2000 que la compañía
Mauser va ha fabricar.
5
Restricción por horas disponibles del Departamento 1:Restricciones
Programación Lineal Entera
Restricción por horas disponibles del Departamento 1:1600x2x4 21 ≤+
1200xx5.2 21 ≤+Restricción por horas disponibles del Departamento 2:
Restricción por horas disponibles del Departamento 3:
6
1600x5.1x5.4 21 ≤+Restricciones de no negatividad:
0x,x 21 ≥
Restricción por horas disponibles del Departamento 3:
4
Función objetivo
Programación Lineal Entera
21 x10x40ZMax +=
7
El programa queda:
Programación Lineal Entera
sujeto a21 x10x40ZMax +=
1600x2x4 21 ≤+1200xx5.2 21 ≤+1600x51x54 ≤+
8
1600x5.1x5.4 21 ≤+0x,x 21 ≥
5
Resolviendo el programa:
Programación Lineal Entera
9
DEFINICIÓN 1.-Un Problema de Programación Lineal Entera (PPLE) es
Programación Lineal Entera
Un Problema de Programación Lineal Entera (PPLE) esaquel que presenta el siguiente formato:
∑=
=n
1iii xcZOptimizar
sujeto a
10
m,,2,1j K=
0enterosxi ≥
( ) j
n
1iiij b,,xa ≥=≤∑
=
6
DEFINICIÓN 2.-Definimos el “equivalente continuo” de un PPLE como:
Programación Lineal Entera
Definimos el equivalente continuo de un PPLE como:
∑=
=n
1iii xcZOptimizar
sujeto a
11
m,,2,1j K=
0xi ≥
( ) j
n
1iiij b,,xa ≥=≤∑
=
Decimos que el equivalente continuo es el relajamientodel PPLE.
Programación Lineal Entera
Un PPLE y su equivalente continuo tienen la mismaestructura, sólo los diferencia el hecho de que en elsegundo, las variables no están sujetas a valoresenteros.
12
7
¿CÓMO RESOLVER UN PPLE?Dado un PPLE resolvemos su equivalente continuo si
Programación Lineal Entera
Dado un PPLE, resolvemos su equivalente continuo, sila solución óptima resulta entera, entonces estasolución del equivalente continuo será también lasolución óptima del PPLE.Si la solución óptima del equivalente continuo tiene porlo menos una variable cuyo valor no es entero,entonces debemos utilizar técnicas de Programación
13
entonces debemos utilizar técnicas de ProgramaciónEntera.
INTERPRETACIÓN GRÁFICA DEL ESPACIO DESOLUCIONES DE UN PPLE
Programación Lineal Entera
Consideremos el siguiente PPLE:
y5x4ZMax +=sujeto a
8yx ≤+
14
10yx2 ≤+0enterosy,x ≥
8
10
yGrafiquemos
Programación Lineal Entera
4567
89
10 qla primerarestricción
151 2 3 4 5 6 7 8
123
4
xx + y = 8
10
yGrafiquemos
Programación Lineal Entera
4567
89
102x + y = 10
qla segundarestricción
161 2 3 4 5 6 7 8
123
4
xx + y = 8
9
10
yEspacio de
Programación Lineal Entera
4567
89
10 psoluciones
factibles del equivalente
continuo
171 2 3 4 5 6 7 8
123
4
x
10
yBuscando la
Programación Lineal Entera
4567
89
10solución
óptima del equivalente
continuo
181 2 3 4 5 6 7 8
123
4
x
Z = 20
10
10
y
Programación Lineal Entera
4567
89
10
191 2 3 4 5 6 7 8
123
4
x
Z = 30
10
ySolución
Programación Lineal Entera
4567
89
10
Z = 40
óptima del equivalente
continuox = 0y = 8
Z = 40
201 2 3 4 5 6 7 8
123
4
x
11
10
yEl espacio de
Programación Lineal Entera
4567
89
10 psoluciones
factibles del equivalentecontinuo es un conjunto
convexo
211 2 3 4 5 6 7 8
123
4
x
10
yEspacio de
Programación Lineal Entera
4567
89
10 psoluciones
factibles del PPLE
no es un conjunto convexo
221 2 3 4 5 6 7 8
123
4
x
12
10
ySolución
Programación Lineal Entera
4567
89
10
Z = 40
óptima del PPLEx = 0y = 8
Z = 40
231 2 3 4 5 6 7 8
123
4
x
OBSERVACIONES:
1) El espacio de soluciones factibles de un PPLE está
Programación Lineal Entera
1) El espacio de soluciones factibles de un PPLE estáformado por puntos aislados.
2) El espacio de soluciones factibles de un PPLE no esun conjunto convexo.
3) Ya no se puede hablar de puntos extremos.
4) En el ejemplo presentado la solución óptima del
24
4) En el ejemplo presentado, la solución óptima delequivalente continuo es ( x, y ) = ( 0, 8 ). Como estasolución es entera, será también solución del PPLE.
13
¿QUÉ DIFICULTADES SE PRESENTAN SI SEREDONDEA LA SOLUCIÓN DE UN PPLE?
Programación Lineal Entera
Si al resolver el equivalente continuo de un PPLE lasolución no resulta entera y procedemos a redondeardicha solución se pueden presentar las siguientesdificultades:1) La solución redondeada es no factible.
2) L l ió d d d f tibl
25
2) La solución redondeada es factible, pero no esóptima.
1) La solución redondeada es no factible.Consideremos el siguiente PPLE:
Programación Lineal Entera
Consideremos el siguiente PPLE:
yxZMax +=sujeto a
6yx2 ≤+4y2x ≤+
26
4y2x ≤+0enterosy,x ≥
14
yGrafiquemos
Programación Lineal Entera
345
62x + y = 6
qla primerarestricción
271 2 3 4
1
2
x
yGrafiquemos
Programación Lineal Entera
345
62x + y = 6
qla segundarestricción
281 2 3 4
1
2
x
x + 2y = 4
15
y
Programación Lineal Entera
345
62x + y = 6
291 2 3 4
1
2
x
x + 2y = 4
Espacio de
Programación Lineal Entera
1
2
yp
soluciones factibles del equivalente
continuo
30
1 2 3
1
x
16
Buscando la
Programación Lineal Entera
1
2
y
Z 1
solución óptima del equivalente
continuo
31
1 2 3
1
x
Z = 1
Programación Lineal Entera
1
2
y
32
1 2 3
1
xZ = 2
17
Solución óptima del
Programación Lineal Entera
12
y
Z = 3.333
pequivalente
continuox = 2.6666y = 0.6666Z = 3.3333
33
1 2 3 x
Solución
Programación Lineal Entera
1
2
y redondeadax = 3y = 1Z = 4
solución nofactible
34
1 2 3
1
x
18
Espacio de
Programación Lineal Entera
1
2
yp
soluciones factibles del
PPLE
35
1 2 3
1
x
Solución
Programación Lineal Entera
1
2
y
Z = 3
óptima del PPLE
x = 3, y = 0ó
x = 2, y = 1Z = 3
36
1 2 3
1
x
19
2) La solución redondeada es factible, pero no esóptima
Programación Lineal Entera
pConsideremos el siguiente PPLE:
yx10ZMax +=sujeto a
12y4x3 ≤+
37
18yx8 ≤+0enterosy,x ≥
y
17
18
Grafiquemos
Programación Lineal Entera
8x + y = 18
78
910111213
141516
qlas
restricciones
381 2 3 4
1234
56
x
7
3x + 4y = 12
20
Espacio de
Programación Lineal Entera
23
yp
soluciones factibles del equivalente
continuo
391 2 3
1
x
Solución
Programación Lineal Entera
2
3
y óptima del equivalente
continuox = 2.25y = 0.00Z = 22.5
401 2 3
1
x
21
Solución
Programación Lineal Entera
23
y redondeadax = 2y = 0
Z = 20solución no
óptima
411 2 3
1
x
Espacio de
Programación Lineal Entera
23
yp
soluciones factibles del
PPLE
421 2 3
1
x
22
Solución
Programación Lineal Entera
2
3
y óptima del PPLEx = 2y = 1
Z = 21
431 2 3
1
x
SOLUCION DE UN PPLETECNICA DE RAMIFICACION Y ACOTAMIENTO
Programación Lineal Entera
TECNICA DE RAMIFICACION Y ACOTAMIENTOEsta técnica consiste en insertar restricciones en elproblema original (ACOTAMIENTO) y resolviendo por elmétodo SIMPLEX se obtienen soluciones óptimas, conlas cuales se construye un árbol de decisión(RAMIFICACION) siguiendo la dirección del árbol con elmejor valor óptimo obtenido hasta el momento
44
mejor valor óptimo obtenido hasta el momento.
23
PROCEDIMIENTO.-1) Resolver el equivalente continuo del PPLE esto
Programación Lineal Entera
1) Resolver el equivalente continuo del PPLE, estopuede dar lugar a las siguientes posibilidades:
a) Si la solución óptima obtenida es enteraentonces fin del proceso, esta será la solucióndel PPLE.
45
b) En caso contrario tomamos una de lasvariables cuyo valor no es entero y generamos
Programación Lineal Entera
y y gdos restricciones.
Por ejemplo, supongamos que
)r(rx Ζ∉=r
46
[ ]rx ≤ [ ] 1rx +≥donde [r] es el máximo entero de r.
24
2) Resolver el equivalente continuo insertando larestricción x ≤ [r] y ubicamos el resultado en una de
Programación Lineal Entera
ylas ramificaciones.
Luego resolvemos el equivalente continuoconsiderando sólo la segunda restricción x ≥ [r] + 1y ubicamos el resultado en la otra ramificación.
3) Si alguna solución obtenida es entera y no existeramificación con algún valor óptimo mejor entonces
47
ramificación con algún valor óptimo mejor, entoncesfin del proceso.
En caso contrario continuar con el paso 1 en laramificación que tenga el mejor valor óptimo hastael momento.
Ejemplo.-
Resolver el siguiente PPLE
Programación Lineal Entera
Resolver el siguiente PPLE
y4x3ZMax +=sujeto a
18y3x2 ≤+56y7x8 ≤+
48
56y7x8 ≤+0enterosy,x ≥
25
y
Programación Lineal Entera
Acotando y ramificando x
3
4
5
6
x = 4.2
y = 3.2
Z = 25.4
491 2 43 5 6 7
1
2
x
Programación Lineal Entera
x = 4.2
y = 3.2
x = 4
y = 3.333
Z = 25.33
4x ≤
50
y
Z = 25.4
x = 5
y = 2.286
Z = 24.145x ≥
26
y
Programación Lineal Entera
Acotando y ramificando y
3
4
5
6 x = 4
y = 3.333
Z = 25.33
x = 5
y = 2.286
Z 24 14
desde el mejor valor
óptimo
511 2 43 5 6 7
1
2
x
Z = 24.14
x = 4
y = 3
Z 24
3y ≤
Programación Lineal Entera
x = 4.2
y = 3.2
x = 4
y = 3.333
Z = 25.33
Z = 24
x = 3
y = 4
Z = 25
4x ≤
4y ≥
52
y
Z = 25.4
x = 5
y = 2.286
Z = 24.145x ≥
27
y
Programación Lineal Entera
x = 3
El mejor valor óptimo
3
4
5
6
x = 5
y = 4
Z = 25
x = 4
y = 3
Z = 24
resulta Z=25
531 2 43 5 6 7
1
2
x
y = 2.286
Z = 24.14
Observación.-1) La solución óptima es: x = 3, y = 4, Z = 25.
Programación Lineal Entera
y4x3ZMax +=sujeto a
18y3x2 ≤+
1) La solución óptima es: x 3, y 4, Z 25.2) A medida que aumentamos de nivel, el valor de la
F.O. no mejora.3) El problema resuelto con el método simplex fue:
54
18y3x2 ≤+56y7x8 ≤+
0y,x ≥
4x ≤4y ≥
28
PROBLEMA 02.-Una compañía de transportes tiene 10 camiones
Programación Lineal Entera
Una compañía de transportes tiene 10 camionesgrandes con capacidad de 40000 libras cada uno y 5camiones pequeños con capacidad de 30000 librascada uno.
Los camiones grandes tienen un costo de operación de$30/milla y los pequeños $25/milla.
55
Para la próxima semana la compañía debe transportar400000 libras de malta en un recorrido de 800 millas.
La posibilidad de otros compromisos significa que porcada 2 camiones pequeños mantenidos en reserva,
Programación Lineal Entera
p qdebe quedarse por lo menos uno de los grandes.
Determine el número óptimo de camiones a utilizar.
56
29
SOLUCION.-Variables de decisión
Programación Lineal Entera
Variables de decisiónG : número de camiones GRANDES a utilizar en el
transporte.P : número de camiones PEQUEÑOS a utilizar en el
transporte.
57
Restricción por cantidad a transportar:Restricciones
Programación Lineal Entera
Restricción por cantidad a transportar:4003040 ≥+ PG
10≤GRestricción por número de camiones grandes:
Restricción por número de camiones pequeños:
58
5≤PRestricción por número de camiones pequeños:
30
RestriccionesRestricciones de camiones en reserva:
Programación Lineal Entera
Restricciones de camiones en reserva:
2105
≤−−
GP
GP 2205 −≤−
152 ≤− PG
59
0, ≥enterosPG
Restricción por no negatividad
Función objetivo
Programación Lineal Entera
PGZMin )800(25)800(30 +=
60
31
El programa queda:
Programación Lineal Entera
sujeto a
PGZMin 2000024000 +=
4003040 ≥+ PG10≤G
61
5≤P152 ≤− PG
0, ≥enterosPG
NOFACTIBLE
2≤P
Programación Lineal Entera
G = 8.5
P = 2
G = 8
P = 2.666
Z = 245333.3G = 7.75
P = 3
Z = 246000
G = 7
P = 4
Z = 248000
8≤G
3≥P
7≤G
62
Z = 24400
G = 9
P = 3
Z = 276000
G = 8
P = 3
Z = 252000
9≥G
8≥G
32
Observación.-1) La solución óptima es: G = 7, P = 4, Z = 24800
Programación Lineal Entera
sujeto a
1) La solución óptima es: G 7, P 4, Z 248002) El problema resuelto con el método simplex fue:
PGZMin 2000024000 +=
4003040 ≥+ PG 8≤G
63
10≤G5≤P
152 ≤− PG0, ≥PG
7≤G3≥P
ProgramaciónLineal Binaria
64
33
PROBLEMA 03.-Una compañía tiene que escoger un conjunto de
Programación Lineal Binaria
Una compañía tiene que escoger un conjunto deproyectos de la siguiente lista para un horizonte deplaneación de 3 años.
Su objetivo es maximizar el Valor Presente Neto Total,pero sin gastar más de lo presupuestado en cualquierade los 3 años.
65
Unidad monetaria: $ 1000.
AÑO 1 AÑO 2 AÑO 3PROYECTO
REINVERSIONES VALOR PRESENTE
NETO
Programación Lineal Binaria
1 30 80 10 80
2 40 70 50 96
3 50 60 70 88
4 60 60 10 92
5 70 40 10 76
6 20 30 90 87
66
7 20 50 20 78
8 25 80 60 81
9 40 20 15 94
PRESUPUESTO 300 320 220
34
Unidad monetaria: $ 1000.
Además se dan las siguientes condiciones:
Programación Lineal Binaria
Además se dan las siguientes condiciones:
a) La compañía debe escoger de todas maneras unode los proyectos 1 o 9, (o ambos).
b) Si el proyecto 6 es seleccionado, entonces elproyecto 8 también debe ser seleccionado.
c) Los proyectos 1 y 3 no deben ser seleccionados a
67
c) Los proyectos 1 y 3 no deben ser seleccionados ala vez.
SOLUCION:Variables de decisión:
Programación Lineal Binaria
Variables de decisión:
⎩⎨⎧= 01Pi si el Proyecto i es seleccionado
en caso contrario
i = 1, 2, 3, ...., 9
68
35
Restricciones:
Por presupuesto
Programación Lineal Binaria
Por presupuesto30 P1 + 40 P2 + 50 P3 + 60 P4 + 70 P5 + 20 P6 + 20 P7 + 25 P8 + 40 P9 ≤ 300
80 P1 + 70 P2 + 60 P3 + 60 P4 + 40 P5 + 30 P6 + 50 P7 + 80 P8 + 20 P9 ≤ 320
10 P1 + 50 P2 + 70 P3 + 10 P4 + 10 P5 + 90 P6 + 20 P7 + 60 P8 + 15 P9 ≤ 220
Por selección del proyecto 1 o 9P1 + P9 ≥ 1
69
Por posible selección de los proyectos 6 y 8P6 - P8 ≤ 0
Por la no selección de los proyectos 1 y 3 a la vezP1 + P3 ≤ 1
Programación Lineal Binaria
Por binariosP1, P2, P3, P4, P5, P6, P7, P8, P9 binarios {0,1}
Función objetivo:Maximizamos el Valor presente Neto
70
Max Z = 80 P1 + 96 P2 + 88 P3 + 92 P4 + 76 P5 + 87 P6 + 78 P7 + 81 P8 + 94P9
36
Programación Lineal Binaria
SOLUCION DE UN PROBLEMA DEPROGRAMACION LINEAL BINARIA (PPLB).-( )Los Problemas de Programación Lineal Binaria (PPLB)tiene la forma general de los PPL pero las variablessólo pueden tomar valores binarios (0,1).Para resolver un PPLB se puede utilizar los siguientesmétodos:
71
1) Método de la Revisión Exhaustiva2) Método Aditivo de Egon Balas
Programación Lineal Binaria
MÉTODO DE LA REVISÓN EXHAUSTIVAEste no es un método propiamente dicho Dado que lasEste no es un método propiamente dicho. Dado que lasvariables sólo toman valores {0,1} pueden revisarsetodas las soluciones y determinar la solución óptima porcomparación. El número de soluciones posibles estadado por 2n donde n es el número de variables.
72
37
Programación Lineal Binaria
Ejemplo:Min Z = 5 x1 + 7 x2 + 10 x3 + 3 x4 + x5Min Z 5 x1 7 x2 10 x3 3 x4 x5
Sujeto a- x1 + 3 x2 + 5 x3 - x4 + 4 x5 ≤ 4
2 x1 - 6 x2 + 3 x3 + 2 x4 - 2 x5 ≤ 0
x2 - 2 x3 + x4 + x5 ≥ 1
xi = {0,1} i = 1, 2, 3, 4, 5
P t ti 25 32 l i ibl
73
Para este caso se tiene 25 = 32 soluciones posibles,algunas soluciones serán no factibles, pero en estemétodo se deben revisar la totalidad de soluciones. Lassoluciones factibles serán evaluadas en la funciónobjetivo.
Programación Lineal Binaria
Soluciones posibles:SOLUCIONESSOLUCIONES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
x1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
x2 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
x3 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
x4 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
x5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Factible No Si No Si No No No No Si No Si No No No No No No Si No No No No No No Si No Si No No No No No
Z - 1 - 4 - - - - 7 - 10 - - - - - - 6 - - - - - - 12 - 15 - - - - -
74
La solución es x1 = 0, x2 = 0, x3 = 0, x4 = 0, x5 = 1 y Z = 1.
38
Programación Lineal Binaria
Min Z = 8 x + 7 x + 6 x + 5 x + x
Ejemplo:
Min Z = 8 x1 + 7 x2 + 6 x3 + 5 x4 + x5Sujeto a
- 6 x1 - 3 x2 + 2 x3 - 4 x4 - x5 ≤ - 3
- 4 x1 - 5 x2 - 4 x3 - 3 x4 + 3 x5 ≤ -7
xi = {0,1} i = 1, 2, 3, 4, 5
75
Programación Lineal Binaria
SOLUCIONES
Soluciones posibles:SOLUCIONES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
x1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
x2 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
x3 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
x4 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
x5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Factible No No No No No No No No No No Si No No No Si Si No No Si No Si No Si Si Si No Si Si Si Si Si Si
Z - - - - - - - - - - 12 - - - 18 19 - - 13 - 14 - 19 20 15 - 20 21 21 22 26 27
76
La solución es x1 = 0, x2 = 1, x3 = 0, x4 = 1, x5 = 0 y Z = 12.
39
Programación Lineal Binaria
Max Z = 3 x + 2 x 5 x 2 x + 3 x
Ejemplo:
Max Z = 3 x1 + 2 x2 - 5 x3 - 2 x4 + 3 x5Sujeto a
x1 + x2 + x3 + 2 x4 + x5 ≤ 4
7 x1 + 3 x3 - 4 x4 + 3 x5 ≤ 8
11 x1 - 6 x2 + 3 x4 - 3 x5 ≥ 3
xi = {0,1} i = 1, 2, 3, 4, 5
77
Programación Lineal Binaria
SOLUCIONES
Soluciones posibles:SOLUCIONES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
x1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
x2 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
x3 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
x4 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
x5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Factible No No Si No No No Si No No No No No No No No No Si No Si Si No No Si No Si No Si No No No No No
Z - - -2 - - - -7 - - - - - - - - - 3 - 1 4 - - -4 - 5 - 3 - - - - -
78
La solución es x1 = 1, x2 = 1, x3 = 0, x4 = 0, x5 = 0 y Z = 5.
40
Programación Lineal Binaria
MÉTODO ADITIVO DE EGON BALASEl método se basa en resolver un modelo deEl método se basa en resolver un modelo deminimización con coeficientes positivos en la funciónobjetivo, de manera que se utilice el menor número devariables a fín de minimizar el valor óptimo de la funciónobjetivo.
INFACTIBILIDAD.-
79
Llamaremos infactibilidad al intervalo que produce unasolución aplicada sobre una restricción, o un conjuntode éstas, y mide la distancia de la solución sobre unresultado factible.
Programación Lineal Binaria
Ejemplo.-Dado el siguiente conjunto de restricciones:Dado el siguiente conjunto de restricciones:
1xx3x2 321 ≤+−1x2xx 321 ≥−+−
La solución x1 = 0, x2 = 1 y x3 = 0, produce:0312 ≤−⇒≤−
0011 I f tibilid d 0Infactibilidad 0 Infactibilidad = 0+0 = 0
80
0011 ≤⇒≥ Infactibilidad 0
La solución x1 = 1, x2 = 0 y x3 = 0, produce:0112 ≤⇒≤0211 ≤⇒≥−
act b dad 0 0 0
Infactibilidad 1Infactibilidad 2 Infactibilidad = 1+2 = 3
41
PROCEDIMIENTO:
1) La función objetivo debe ser de Minimización en
Programación Lineal Binaria
1) La función objetivo debe ser de Minimización, encaso de Maximización, usar la regla de equivalencia:Maximizar ( Z ) = Minimizar ( W = -Z )Ejemplo:
21 x10x40ZMax −=
81
21 x10x40WMin +−=
Una vez determinada la solución debe restablecersela función objetivo original.
Programación Lineal Binaria
2) Los coeficientes de la función objetivo deben ser nonegativos, si algún ci es negativo, entonces seg g i gcambia xi por su complemento:
ii x1x −=El cambio de la variable por su complemento,también debe efectuarse en todas las restriccionesdonde participa la variable.
82
21 x10x40WMin +−=
21 x10)x1(40WMin +−−=40x10x40WMin 21 −+=
21 x10x40WMin +=
42
Programación Lineal Binaria
Una vez determinada la solución debenrestablecerse las variables originales.g
3) Evaluar las restricciones tomando las variables elvalor cero. Evaluar la infactibilidad, si resulta cero,es la solución óptima.
4) Añadir una variable xi = 1 al conjunto solución yevaluar la infactibilidad.
) Si l i f ibilid d l l l ió
83
5) Si algunas infactibilidades resultan cero, la soluciónóptima será la solución que tenga menor valoróptimo y fin del proceso. En caso contrarioseleccionar la de menor infactibilidad y regresar alpaso 4.
Programación Lineal Binaria
Ejemplo:Min Z = 5 x1 + 7 x2 + 10 x3 + 3 x4 + x5Min Z 5 x1 7 x2 10 x3 3 x4 x5
Sujeto a- x1 + 3 x2 + 5 x3 - x4 + 4 x5 ≤ 4
2 x1 - 6 x2 + 3 x3 + 2 x4 - 2 x5 ≤ 0
x2 - 2 x3 + x4 + x5 ≥ 1
xi = {0,1} i = 1, 2, 3, 4, 5
84
43
– x1 + 3 x2 + 5 x3 – x4 + 4 x5 – 4 ≤ 0
2 x1 – 6 x2 + 3 x3 + 2 x4 – 2 x5 ≤ 0
– x2 + 2 x3 – x4 – x5 + 1 ≤ 0
1a) x1 = 0, x2 = 0, x3 = 0, x4 = 0, x5 = 0
04 ≤− Infactibilidad 0
00 ≤ Infactibilidad 0 Infactibilidad = 0+0+1 = 101≤ Infactibilidad 1
2a) x1 = 1, x2 = 0, x3 = 0, x4 = 0, x5 = 0
05 ≤−02 ≤ Infactibilidad 2
Infactibilidad 0
Infactibilidad = 0+2+1 = 301≤ Infactibilidad 1
85
01≤ Infactibilidad 1
2b) x1 = 0, x2 = 1, x3 = 0, x4 = 0, x5 = 0
01≤−06 ≤− Infactibilidad 0
Infactibilidad 0
Infactibilidad = 0+0+0 = 000 ≤ Infactibilidad 0 Z = 7
2c) x1 = 0, x2 = 0, x3 = 1, x4 = 0, x5 = 0
01≤03 ≤ Infactibilidad 3
Infactibilidad 1
Infactibilidad = 1+3+3 = 703 ≤ Infactibilidad 3
2d) x1 = 0, x2 = 0, x3 = 0, x4 = 1, x5 = 0d) 1 0, 2 0, 3 0, 4 , 5 0
05 ≤−02 ≤ Infactibilidad 2
Infactibilidad 0
Infactibilidad = 0+2+0 = 200 ≤ Infactibilidad 0
2e) x1 = 0, x2 = 0, x3 = 0, x4 = 0, x5 = 1
00 ≤ Infactibilidad 0
86
02 ≤− Infactibilidad 0 Infactibilidad = 0+0+0 = 000 ≤ Infactibilidad 0 Z = 1
Solución óptima x1 = 0, x2 = 0, x3 = 0, x4 = 0 y x5 = 1 paraZ = 1. Se revisaron 6 soluciones. (Menor que 32).