SOLUCIÓN A PROBLEMAS DE PLE

Se refiere a los casos de asignar personas, vehículos, máquinas, etc.,

cuyas soluciones sólo tienen sentido practico si sus valores son enteros,
para buscar una solución que satisfaga tal condición, se tiene:
❑ Método Gráfico (zona de soluciones factibles no es continua)
❑ Algoritmo Símplex
El algoritmo símplex, dependiendo del problema se complementa
con métodos:
Gomory
* Todas las Variables son Enteras
Branch & Bound
* Algunas Variables Decisión Enteras Branch & Bound
y otras No-Enteras.
Balas EGON
* Variables Decisión Binarias (0 ó 1)
Branch & Bound
 MÉTODO GRÁFICO P/PROBLEMAS DE PLE
Muebles “Las 3B”, debe resolver cuantas sillas (X1) y mesas (X2)
producir en el próximo ciclo productivo. En tal sentido, estructuró un
modelo matemático que da cuenta del problema.
Max Z = 60X1 + 80X2 ($) Gráfico clásico → Zona Factible
Sujeto a: es un Espacio Continuo.
3X1 + 2X2  18 h-h Zo=240=60X1+80X2
X1 + 2X2  9 u.m.p
X1;X2  0 Entero
Solución NO CUMPLE las
condiciones enteras.
Corregir el análisis gráfico,
discretizando las Xj.

La solución entera óptima es: X1 = 3 ; X 2 = 3 & ZE = 420

* * *
 MÉTODO GRÁFICO P/PROBLEMAS DE PLE…
La solución óptima es: Única, No Degenerada, el 1º recurso
es sobrante en 3 h-h → 1ª restricción es inactiva y el 2º
recurso es escaso → 2ª restricción es activa.
Si hubiese aplicado el Algoritmo Símplex, la tabla solución
sin considerar la condición entera sería:
9
Cj → 60 80 0 0 Sol. X 1* = = 4 1 2
Cb Vb X1 X2 X3 X4 Xb 2
9
60 X1 1 0 ½ -½ 9/2 X 2 = = 2 14
*
80 X2 0 1 -¼ ¾ 9/4 4
(Zj-Cj) 0 0 10 30 450 Z * = 450
Al igual que en método gráfico (espacio solución continuo),
la solución NO CUMPLE las condiciones enteras.
Se aplican los procedimientos complementarios al Símplex,
tal que, se encuentre la solución entera óptima buscada.
 MÉTODO GOMORY P/PROBLEMAS DE PLE
n
Sea : Max Z =  C j * X j
n j =1

Sujeto a : a X
j=1
ij j  bi (Xh i )  i = 1,2,.., m

Xj 0
aij = eij + f ij donde: e = entero inferior de a ij
bi = ei' + f i ' f = fracción complementaria de a ij
Se establece la siguiente “Restricción GOMORY”
n n

 f
j=1
ij X j  f i
'
(-g i )  g i −  f ij X j = − f i '
j =1

Lo anterior también es valido, en cualquier tabla solución símplex:

Yij = eij + f ij donde: e = entero inferior de Yij
X bi = ei' + f i ' f = fracción complementaria de Yij
Procedimiento
1º Encontrar solución
Procedimiento GOMORY:optima No-Entera. O sea, sin considerar
restricciones
1º Encontrar entera →
solución Método
optima Símplex O
No-Entera. Relajado.
sea, sin considerar
2º restricciones
Sobre TABLEU → Método Símplex
entera ÓPTIMO SIMPLEX, Relajado.
se busca la mayor
fracción
2º Sobre Xb queÓPTIMO
TABLEU da origenSIMPLEX,
a la restricción “GOMORY”.
se busca la mayor fracción
'
 Max f i
Xbi que da origen
' a la restricción “GOMORY”. O sea: Max f i
De haber empate, elegir Xbi que más aporta al objetivo.
3º Agregar la restricción GOMORY en TABLEU
3º Agregar la de
→ Análisis restricción GOMORY en TABLEU → Análisis de
Sensibilidad
Sensibilidad
4º
4º Sacar ggde
Sacar delalabase
base usando
usando Pivote
Pivote DualDual y entra
y entra variable
variable No-Básica No
aBásica a la Base.
la Base.
5º
5º Obtener Nuevo
Obtener NuevoTABLEU
TABLEU ÓPTIMO
ÓPTIMO SIMPLEX
SIMPLEX.
Si X bi Entero  i → Solución Óptima Entera
Si  i  X bi  Entero ; Volver a paso 2º y agregar otra
restricción de GOMORY
Obs: El máximo de restricciones GOMORY es igual al Nº de
Obs: El máximodede
Variables restricciones
Decisión. GOMORY
De lo contrario, seráesnecesario
igual alefectuar
Nº de
demasiadas
Variables derestricciones
Decisión. DeGOMORY, resultando
lo contrario, impráctico
será el
necesario
método para
efectuar buscar unarestricciones
demasiadas solución entera.
GOMORY, resultando
 EJEMPLO DE APLICACIÓN
0 0 Sol.
1º) Max Z = 5X1 + 2X2
Sujeto a: Cb Vb X4 X3 Xb
X1 + X2  8 (X3) 2 X2 -1/3 4/3 20/3
4X1 + X2  12 (X4) 5 X1 1/3 -1/3 4/3
X1;X2  0 Entero (Zs - Cs) 1 1 20
2º) Xbi X4 X3 Xb
6 23  Max f’i → −1
3 1 13 6 23
1 13 -1 1 6 →e
2
3
1
3
2
3 →f
 g1 − 23 X 4 − 13 X 3 = − 23
 EJEMPLO DE APLICACIÓN…

3º)

ÓPTIMO: Z = 19
*

X * = (1;7;0;1)
Solo fue necesaria una (1) restricción GOMORY
 MÉTODO BRANCH & BOUND P/PROBLEMAS DE PLE
(RAMIFICAR Y ACOTAR)
Procedimiento:
Procedimiento:
Procedimiento: Se
SeSepuede
puedepuede aplicar
aplicar
aplicar a problemas
a aproblemas
problemas donde donde
donde todas todas
todas laslaslas
variables
variables
variables pueden
pueden
pueden ser ser serenteras
enterasenteras oo variables
variables
o variables mixtas.
mixtas.
mixtas.
1º 1º Resolver
1º Resolver
Resolver PL
PL sinPL restricción
sin restricción
restricción entera,
entera, entera,
OOsea, O Método
sea,sea, Método
Método Símplex
Símplex
Símplex
Relajado
Relajado
Relajado → → Solución
→Solución
Solución Óptima
ÓptimaÓptima
No-Entera.No-Entera.
No-Entera.
2º Verificación
2º Verificación de
2º Verificaciónde variables
variables No-Enteras
de variables No-Enteras
No-Enteras en Solución:
en Solución:
en Solución:¿Cuáles
¿Cuáles dede de
¿Cuáles
ellas
ellasdeben
ellas ser
ser enteras?
debendeben ser enteras?
enteras?
3º Variables No-Enteras
3º Variables que deben
No-Enteras que deben ser ser
enteras, seleccione
enteras, seleccionela X
3º Variables No-Enteras que deben ser enteras, seleccione la Xjla j Xj
cuya cuya
fracción (decimal)
fracción este este
(decimal) más más cercacercade la mitad
demitad entre
la mitad entresu su
cuya fracción
enteroentero
inferior
(decimal)
y superior.
este más cerca de la
De existir empate, seleccionar Xj que
entre su
entero inferior
inferior y superior.
y superior.
más aporta al objetivo.
Entero inferior → e j =
Entero inferior → e j = INT ( X j ) INT* ( X *j )

Entero superior
Entero superior → j e +
→ 1 =
e j + 1
INT =( X * (X *) +1
j ) +1 j
INT

4º 4º Genere
4º Genere
Genere dos
dos (2) dos
(2) (2) nuevas
nuevas
nuevas restricciones
restricciones
restricciones
Xj X j ( X
INT * ( X *j ) = e j
j ) = ej
INT
X  INT
X
j
 * ( X *) +1 = e +1
j ( X ) +1 =
INT j j e +1 j
j
 BRANCH & BOUND (B&B)…
Conlas
Con las dos
nuevas restricciones,
nuevas se generan
restricciones, dos nuevos
se generan problemas:
dos nuevos problemas:
a b
Max Z = CTX Max Z = CTX
X *j
AX  b AX  b
Xj  ej Xj  ej+1 INT ( X *j ) INT ( X *j ) + 1
ej +1
ej
X0 X0
De esta forma, se va dividiendo el problema cuya solución no satisface
De condiciones
las esta forma,enteras
se va ydividiendo el problema
se debe ir acotando, cuya
según lassolución
reglas: no
satisface las condiciones
a) Solución enterassey acota.
es Infactible, se debe ir acotando, según las
siguientes reglas:
b) Solución Entera ( Z e ) se acota. Cuando es mayor que la
a) Solución es Infactible, se acota.
ultima ( Z e  Z e anterior ) se anota como potencial Z e* .
*

c) Cuando solución No-Entera Z  Z e* anterior

Nota: Cada rama que se agrega, añade una restricción adicional al
problema anterior → las restricciones se van acumulando. De existir
más de una rama por abrir, elegir la de mejor Z.
REPRESENTACIÓN GRÁFICA DEL MÉTODO B&B
PPL1 No Entero

PPL2 PPL3 No Entero

(Infactible)
(Se Acota)
No Entero
PPL4 PPL5 Z5 > Ze4
Entero
(Se Acota)
PPL6 PPL7
No Entero Entero
Z  Ze Ze7 > Ze4
(Se Acota) ¡¡OPTIMO!!
Ventajas: 1.- Siempre llega a la solución
2.- Se puede aplicar para PLE mixta
 CASO DE APLICACIÓN MÉTODO B&B

Sea: Max Z = 20X1 + 30X2 PPL1 Z = 372

X1 = 91111 Z = 372 11
8
PPL1 11 8

Sujeto a: XX12 == 694 11

X 2 = 6X11
11
4
3X1 + 2X2  40 (X3) X2
6 2 7
2X1 + 5X2  50 (X4) PPL2 Z = 3662 3 PPL3 Z = 360
X1;X2  0 Entero X1 = 913 Z = 366 2 3 XPPL3
PPL2 1 = 712 Z = 360
XX1 =2 =961 3 XX2 =1 =7 7 1 2
STOP
0 0 Sol. X1
X92 = 6 X
1 1
0 X2=7
Aplicando Método Símplex: STOP
Cb Vb X3 X4 Xb PPL4 Z = 360 PPL5 Z = 350
X1 = 9 X1 =10
20 X1 5/11 -2/11 9 111 PPL4 = 360 XPPL5
X2 = 6 ZSTOP 2 =5 Z = 350
30 X2 -2/11 3/11 6 4 11 X 1 = 9 ¡¡ÓPTIMO!! X 1 = 10STOP
(Zs - Cs) 3 7 11 6 6 11 372 8 11 X 2 = 6 STOP X2=5
STOP
¡¡ÓPTIMO!!
 CASO DE APLICACIÓN MÉTODO B&B…
X X2 2 6 6 00 00 Sol.
Sol. XX2 2 7 7 00 00 Sol.
Sol.
CbCb Vb Vb XX33 XX55 Xb
Xb CbCb Vb Vb XX55 XX44 Xb
Xb
2020 XX1 1 1/3 -2/3
1/3 -2/3 991 31 3 2020 XX 11 2½2½ ½½ 7½
7½
3030 XX2 2 00 11 66 3030 XX 22 -1-1 00 77
00 XX4 4 -2/3 -11/3
-2/3 -11/3 111 31 3 00 XX 33 -5½ -1½
-5½ -1½ 3½
3½
(Z(Zs -s -CC
s)s) 662 32 3 16 3662 32 3
162 32 3 366 (Z(Z -C
s -s Cs)s) 2020 1010 360
360

X X1 1 9 9 00 00 Sol.
Sol. XX1 1 1010 00 00 Sol.
Sol.
CbCb Vb Vb XX 66 XX55 Xb
Xb CbCb Vb Vb XX 33 XX66 XbXb
2020 XX1 1 11 00 99 2020 XX 11 00 -1-1 1010
3030 XX2 2 00 11 66 3030 XX 22 ½½ 1½ 1½ 55
00 XX4 4 -2-2 -5-5 22 00 XX 44 -2½ -5½
-2½ -5½ 55
00 XX3 3 -3-3 -2-2 11 00 XX 55 -½-½ -1½
-1½ 11
(Z(Zs -s -CC
s)s) 20
20 3030 360
360 (Z(Z -C
s -s Cs)s) 1515 2525 350
350