Modelo PROTRAC
Max Z 5000 E 4000 F
s.a : 10 E 15F 150.............L1 ( A)
20 E 10 F 160.............L2 ( B)
30 E 10 F 135.............L3 (Calidad )
E 3F 0.................L4 ( Poltica )
E
F 5.................L5 ( Distribuid or )
16
L2 : 20E 10F 160
Max Z 5000E 4000F
14
12
Solucin Optima:
10
E = 4.5; F = 7.0
(0.9 , 9)
8
(4.5 , 7.0)
(6.857, 2.286)
L3 : 30E 10F 135
L4 : E 3F 0
L5 : E F 5
2.286
2
1.35
L1 : 10E 15F 150
(4.05 , 1.35)
0.75
E
2
10
12
14
16
Caso Protrac (Enunciado extra)
7.-Que tanto conviene si aumentamos la disponibilidad de las
horas del Departamento B .
16
L2 : 20E 10F 160
Max Z 5000E 4000F
14
Capacidad Dpto B= 161 Hrs
12
10
(0.9 , 9)
Solucin Optima:
8
E=
(4.5 , 7.0)
; F=
(6.857, 2.286)
L3 : 30E 10F 135
L4 : E 3F 0
L5 : E F 5
2.286
2
1.35
L1 : 10E 15F 150
(4.05 , 1.35)
0.75
E
2
10
12
14
16
16
L2 : 20E 10F 160
Max Z 5000E 4000F
14
Capacidad Dpto A= 151 Hrs
12
10
(0.9 , 9)
Solucin Optima:
(4.5 , 7.0)
E=
(6.857, 2.286)
L3 : 30E 10F 135
F=
L4 : E 3F 0
L5 : E F 5
2.286
2
1.35
L1 : 10E 15F 150
(4.05 , 1.35)
0.75
E
2
10
12
14
16
16
L2 : 20E 10F 160
Max Z 5000E 4000F
14
Capacidad Dpto Calidad 135 Hrs
12
10
(0.9 , 9)
Solucin Optima:
E = 4.5; F = 7.0
8
(4.5 , 7.0)
(6.857, 2.286)
L3 : 30E 10F 135
L4 : E 3F 0
L5 : E F 5
2.286
2
1.35
L1 : 10E 15F 150
(4.05 , 1.35)
0.75
E
2
10
12
14
16
16
Max Z 5000 E 4000 F
L2 : 20E 10F 160
14
5000
Z
F
E
4000
4000
12
10
(0.9 , 9)
8
(4.5 , 7.0)
Solucin Optima:
(6.857, 2.286)
E=
L3 : 30E 10F 135
F=
L4 : E 3F 0
L5 : E F 5
2.286
2
1.35
L1 : 10E 15F 150
(4.05 , 1.35)
0.75
E
2
10
12
14
16
Solucin Grfica
Solucin Factible
Regin Factible
Solucin ptima
Valor ptimo
Construccin de grficos:
Graficar c/restriccin, Regin Factible
Fijar Z, Graficar F.O, Desplazar y encontrar
Solucin Grfica; Casos Especiales
Soluciones Alternativas
Solucin no acotada
Sin solucin
Si existe Sol. ptima,
ella se encuentra en un
punto esquina
Y en el plano como se ven estos casos ESPECIALES?
Solucin Grfica
Ejercicio n 1
Max z 6 x1 2 x2
s.a
Ejercicio n 3
x1 x2 1
Max z 5 x1 6 x2
s.a
2 x1 3x2 2
3 x1 x2 6
x1 , x2 0
x1 , x2 0
Ejercicio n 2
Max z 3x1 2 x2
s.a
2 x1 x2 2
x1 2 x2 2
Ejercicio n 4
3 x1 4 x2 12
x1 , x2 0
Ejercicio n 5: Cambiar en Ejercicio n 3 Max Z por Min z
Max z 5 x1 2 x2
s.a
x1 x2 10
x1
x1 , x2 0
16
L2 : 20E 10F 160
Max Z 5000E 4000F
14
12
Solucin Optima:
10
E = 4.5; F = 7.0
(0.9 , 9)
8
(4.5 , 7.0)
(6.857, 2.286)
L3 : 30E 10F 135
L4 : E 3F 0
L5 : E F 5
2.286
2
1.35
L1 : 10E 15F 150
(4.05 , 1.35)
0.75
E
2
10
12
14
16
4.- Representacin Estndar de un PPL
(segn Mtodo de Solucin a Conocer)
F.O. es Max o Min
Restricciones como ecuaciones
Variables no negativas
Lado derecho, constantes no negativas
Modelo Estndar de un PPL
Desagregado (1)
Max( Min) z c1 x1 c2 x2 ... cn xn
s.a : a x a x ... a x b
11 1
12 2
1 n
1
a21x1 a22 x2 ... a2 xn b2
am1 x1 am 2 x2 ... amn xn bm
x1 0, x2 0,..., xn 0
b1 0, b2 0,..., bm 0,
Modelo Estndar de un PPL
Desagregado (2)
n
Max( Min ) z c j x j
j 1
s.a :
a
j 1
ij
x j bi
x j 0; bi 0
i 1,...m; j 1,...n
Modelo Estndar de un PPL MATRICIAL
Estndar
Max( Min) z cx
s.a :
Ax b
x0
b0
Matrices:
a11 ... a1n
A .
.
.
am1 ... amn
c c1 .... cn
x1
x .
xn
b1
b .
bm
A: Matriz de coeficientes Tecnolgicos
B: Vector de restricciones, vector lado derecho
c: Vector fila beneficios, costos o rendimientos
X: Vector de decisiones
SISTEMA DE ECUACIONES
Transformar a Forma Estndar
Lado derecho no negativo
Reducir Desigualdades
Variables negativas
Variables no restringidas en signo
Ejercitar los casos
Ejercicios Estandarizacin
Ejercicio n 1
Ejercicio n 2
Max z x1 2 x2 3x3
Max z 3x1 4 x2 2 x3 5 x4
s.a
x1 x2 x3 7
x1 x2 x3 2
x1 x2 3 x3 x4 14
3 x1 x2 2 x3 5
2 x1 3x2 x3 2 x4 2
x1 , x2 0, x3 0
Ejercicio n 3
4 x1 x2 2 x3 x4 2
s.a
x1 , x2 0, x3 0, x4 0
Max z x1 2 x2 3Minx2 , x3
s.a
x1 x2 x3 7
x1 x2 x3 2
3x1 x2 2 x3 5
x1 , x2 0, x3 0
Que pasa si en el N 3 cambiamos en la F.O a
3max{x2,x3}
Sistema de
Ecuaciones
Cualquiera
ESTANDAR
Resolviendo Sistemas de Ecuaciones
Lineales
Sistema de
Ecuaciones
Equivalente
Cannico
1:1
Solucin Factible
(Todas las Var >= 0)
1:1
5.-
Base, Solucin
Bsica
Solucin Infactible
(Algunas Var <= 0)
Variables Bsicas
Una variable xi se dice
bsica si le acompaa
un factor +1 en una
ecuacin y un cero en
las dems.
Solucin Bsica y
Factible: SB y factible
(XB0)
Solucin Bsica:
Solucin obtenida de un
sistema cannico,
haciendo las variables
NO bsicas cero.
En cada punto esquina
encontramos una SB
n
n!
m (n m)!m!
S1
x1 2 x 2 x3 4 x 4 2 x5 2
x1 x2 x3 3x4 x5 4
Encontrar las combinaciones de VB que conforman
todas las SB:
Factible, Infactible?
Generar nuevo sistema cannico equivalente y concluir.
Nuevo sistema cannico equivalente:
Operaciones Fila (Objetivo: Despejar Variables):
* una ecuacin. por un nmero + o Sumar a una ec. Un mltiplo de otra ec.
Evaluar sus variables
Objetivo: Despejar x1 y x2
S2
x1 2 x2 x3 4 x4 2 x5 2
x2 2 x3 x4 3x5 2
x1
S3
3x3 2 x4 4 x5 6
x2 2 x3 x4 3x5 2
S3: Sistema Cannico
Solucin Bsica: x1 y x2 son bsicas
6.- SIMPLEX
Principios del Mtodo Simplex
1. Comenzar con una solucin bsica inicial cannica
y factible. se podr mejorar?
2. Es factible, Mejorarla?
3. Determinar la siguiente
Cuando no es factible encontrar soluciones
mejores, la bsqueda termina
Ejemplo. Es factible mejorarla?
Max Z = 5X1 + 2X2 + 3X3 - X4 + X5
Sujeto a:
X1 +
2X2 +
2X3 + X4
=8
( 2.7 )
3X1 +
4X2 +
X3
=7
( 2.8 )
+ X5
Solucin bsica X1 = X2 = X3 = 0, X4 = 8, X5 = 7.
Z = 5*(0) + 2*(0) + 3*(0) - 1*(8) + 1*(7) = -1
Ve usted otras soluciones bsicas en este sistema equivalente, cuales?
Es factible mejorarla?
Debemos pensar en un cambio de base
conveniente
Calculemos
un
Indicador para esto:
Ganancia/Beneficio Relativo
cj
Ganancia Relativa de la Variable xj
Mejorando la Solucin
a) Primero se examina si la presente es ptima.
b) Si no la es. El Simplex examina una: Solucin
bsica factible Adyacente con un mejor valor
de Z.
Definicin.
Una Solucin bsica factible Adyacente difiere de la
solucin bsica factible actual, en solo una variable
bsica.
Solucin bsica factible Adyacente
1. Definir una variable bsica como no bsica.
2. Definir una no bsica de reemplazo de la bsica
saliente.
Siempre y Cuando mejore el valor de Z.
Observe que:
1. Variables bsicas asumen valores positivos y las no
bsicas cero.
2. Una no bsica se convierte en bsica aumentando
su valor de cero a una cantidad positiva.
Chequeo de optimalidad
Para la base actual, la optimalidad es chequeada calculando
los beneficios relativos de todas las variables no bsica y en
caso de no cumplirse; la nueva base se empieza a formar
eligiendo aquella de mejor aporte.
Beneficio Relativo: (Referido a una variable no bsica j).
z
cj
x j
Hacer estas operaciones calculando el indicador de optimalidad:
Resumen del Mtodo Simplex
Paso 1. Comenzar con una S. B. F. cannica
.
Paso 2. Optimalidad?
Paso 3 Seleccionar VNB que ingresa a la base
Paso 4 Determinar VB. Que abandona la base
Aplicar regla razn mnima
Paso 5 Generar nuevo sistema. Y volver a Paso 2.
Mtodo Simplex en Forma de Tableu
Max z 5 x1 2 x2 3x3 x4 x5
s.a.
x1 2 x2 2 x3 x4
3x1 4 x2 x3
(1)
(2)
(4)
(5)
8
x5 7
xj 0
(3)
Resumen de pasos. (Max z, Min z)
1. Expresar el problema en forma estndar.
2. Comenzar con una solucin factible bsica inicial en forma cannica y
plantear la Tabla inicial.
3. Usar producto interno para encontrar los beneficios relativos
cj
4. Si todos los
no aportan al objetivo la solucin actual es ptima. De otro
j
modo seleccionar la no bsica para que entre a la base.
5. Aplicar razn mnima para determinar la variable que deja la base.
6. Ejecutar operacin pivote para obtener la nueva tabla.
7. Calcular beneficios relativos. Retorne al paso 4.
Resolver por el mtodo Simplex
el siguiente problema (Caso 1):
Max z 3x1 2 x2
s.a. x1 2 x2 4
3x1 2 x2 14
x1 x2 3; x j 0
(1)
(2)
(3)
(4)
EJERCICIO
(Caso 2)
Max z 4 x1 3x2 6 x3
s.a
3x1 x2 3x3 30
2 x1 2 x2 3x3 40
x1 ; x2 ; x3 0
EJERCICIO (Caso 3)
Max z x1 2 x2 4 x3
s.a
3x1 x2 5 x3 10
x1 4 x2 x3 8
2 x1
2 x3 7
x1 ; x2 ; x3 0
7.-
Uso de Variables Artificiales en el SIMPLEX
Max Z = -3X1 + X2 + X3
X1 - 2X2 + X3
<=
-4X1 + X2 + 2X3 >= 3
2X1
- X3
=
11
-1
Convertir a forma estndar.
Max Z = -3X1 + X2 + X3
Sujeto a:
X1 - 2X2 + X3 + X4
-4X1 + X2 + 2X3
- X5
-2X1
+ X3
= 11
= 3
= 1
Xi >= 0 , i=1,5
Cul es la Base XB?
Que Hacemos, No tenemos una Solucin Bsica, Inmediata?
Agregamos Dos V. Artificiales, Variables que no son parte del Problema, esto
no es un cambio en la forma si no un cambio en el fondo. El modelo que
resulta representa una realidad que no es nuestro problema
Este es un Modelo Artificial
X1 - 2X2 + X3 + X4
- 4X1 + X2 + 2X3
- X5 + X6
-2X1
+ X3
+
XB = (X4 , X6 , X7 )
= 11
X7
Xi >= 0 , i=1,7
= 3
= 1
X6 y X7 son V. Artificiales
Cual es la Funcin Objetivo que se usar?
Podemos inventarla?
Qu se persigue que nos oriente para inventarla?
Mtodo de la M grande.
7.1.-
Se asigna un valor M muy grande a cada coeficiente de V.a.
presente en la funcin objetivo.
-M si es maximizacin y M si es minimizacin.
En el ejemplo anterior se asigna un valor M grande como costo a
la variables X6 y X7.
Luego Min W = -3X1 + X2 + X3 + MX6 + MX7
S.a
X1 - 2X2 + X3 + X4
- 4X1 + X2 + 2X3
- X 5 + X6
-2X1
+ X3
+
X7
Xi >= 0 , i=1,7
= 11
= 3
= 1
Min Z = -3X1 + X2 + X3 + MX6 + MX7
X1 - 2X2 + X3 + X4
- 4X1 + X2 + 2X3
- X5 + X6
-2X1
+ X3
+
X7
Xi >= 0 , i=1,7
= 11
= 3
= 1
XB
X
X
X
X1
X2
X3
X4
X5
X6
X7
Cte.
XB
X
X
X
X1
X2
X3
X4
X5
X6
X7
Cte.
cj
CB
cj
cj
CB
cj
cj
CB
XB
X
X
X
X1
X2
X3
X4
X5
X6
X7
Cte.
XB
X
X
X
X1
X2
X3
X4
X5
X6
X7
Cte.
cj
cj
CB
cj
7.2.-
El Mtodo de las Dos Fases.
Fase 1. Usando un modelo artificial, encontrar una solucin
bsica inicial al problema original.
Fase 2. La solucin bsica encontrada se optimiza con respecto a
la funcin objetivo original. La Tabla final de la fase 1 es la Tabla
inicial para la fase 2.
Min W = X6 + X7
S.a:
X1 - 2X2 + X3 + X4
- 4X1 + X2 + 2X3
- X5 + X6
-2X1
+ X3
+
X7
Xi >= 0 , i=1,7
= 11
= 3
= 1
Min W = X6 + X7
X1 - 2X2 + X3 + X4
- 4X1 + X2 + 2X3
- X 5 + X6
-2X1
+ X3
+
X7
Xi >= 0 , i=1,7
= 11
= 3
= 1
cj
CB
XB
X
X
X
X1
X2
X3
X4
X5
X6
X7
Cte.
XB
X
X
X
X1
X2
X3
X4
X5
X6
X7
Cte.
cj
cj
CB
cj
cj
CB
XB
X
X
X
X1
X2
X3
X4
X5
X6
X7
Cte.
XB
X
X
X
X1
X2
X3
X4
X5
X6
X7
Cte.
cj
cj
CB
cj
