Operación De Investigaciones

Símplex Método M (penalizado)
MAX Z = CTX - M Xa donde M (muy grande) es la penalización.
Ejemplo: Max Z = 10X1 + 20X2
Sujeto a:
X1 + X2 = 150 + X 3
X1
≥ 20 - X4 +X 5
X2 ≤ 40 + X6
X1;X2 ≥ 0
10 20 0
Cb Vb X1 X2 X4
-M X 3 1 1 0
-M X 5 1 0 -1
0 X6 0 1 0
(Zs - Cs) -10 -20
-2M -M

M -170M

-M 0 0
Cb Vb X 5 X6 X4
-M X 3 -1 -1 1
10 X1 1 0 -1
20 X2 0 1 0
(Zs - Cs) 10 20 -10
2MM

Sol.
Xb
150
20
40

-M

Sol.
Xb
90
20
40
1000
-90M

-M 20 0
Cb Vb X 5 X2 X4
-M X 3 -1 1 1
10 X1 1 0 -1
0 X6 0 1 0
(Zs - Cs) 10 -20 -10
2M -M

*
X3 = 0
*
X5 = 0
X * = 40
X* = 0
2
6
La Solución es Óptima por 3 Razones
Solución es Factible (Xbi ≥ 0)
Solución es Inmejorable [(Zj - Cj) ≥ 0]
Variables Artificiales = 0
*
X 1 = 110

X * = 90
4

200
-M -130M-M 0 -M
Cb Vb X 5 X6 X 3
0 X4 -1 -1 1
10 X1 0 -1 1
20 X2 0 1 0
(Zs - Cs) 0 10 10
M

Sol.
Xb
130
20
40

Sol.
Xb
90
110
40
1900

M

Ζ∗ = 1900

Símplex Dos Fases
Formatear el P.L. (Max Z / s.a. ≤ b). Usar Xa si es preciso (≥ ó =).
Fase I:
Paso 1: Función Objetivo Fase I
a) Coeficientes de Xa = -1
b) Coeficientes de otras variables = 0
Paso 2: Usar símplex Tx ó Tc(primal)
STOP
si: a) Z = 0
ó b) (Zj - Cj) ≥ 0
∀j
i) Si hay Xa en la base > 0 Infactible
ii) Si las Xa son No Básicas Factible Fase II
iii) Si Xa son Básicas = 0 Siga a Fase II
Fase II:
Paso 3: Primera tabla Fase II, es última tabla de Fase I, excepto:
a) Las Xa No Básicas, sus columnas son extraídas de la
tabla símplex (eliminadas).
b) Las Xa Básicas = 0, sus coeficientes se asignan = 0.c) Las otras variables, toman sus coeficientes Cj originales
d) Se recalculan los: Indicadores (Zj - Cj) y la meta Z.
Paso 4: a) Si no hay Xa en la base, proceda según símplex usual.
b) De lo contrario vaya a Paso 5.
Paso 5: Si hay Xa = 0 en la base, cambie regla del Pivote.
a) Variable entrante (j’) tiene que ser (Zj - Cj) + negativo.
b) Variable saliente (i’) será Xa de fila k ∋ Ykj’ <0. De lo
contrario use regla tradicional del símplex (Ykj’ > 0).
Ejemplo:

M in Z = 3 X 1 + 2 X 2 + 4 X 3
Suj e t o a: X 1 + X 2 + X 3 ≥ 12
4X 1 – X 2
≥6
X 1 ;X 2 ;X 3 ≥ 0

Formatear el P.L.:
Max (-Z) = -3X1 - 2X2 - 4X3 + 0X4 - M X 5 + 0X6 - MX 7
Sujeto a:
1X1 + 1X2 + 1X3 - 1X4 + 1X 5 + 0X6 + 0 X 7 = 12
4X1 - 1X2 + 0X3 + 0X4 + 0 X 5 - 1X6 + 1X 7 = 6
X1; X2; X3; X4; X 5 ; X6; X 7 ≥ 0Fase I: F.O.: Max Zo = 0X1 + 0X2 + 0X3 + 0X4 - X 5 + 0X6 - X 7
0 0 0 0 0 Sol
-1 0 0 0 0 Sol
Cb Vb X1 X2 X3 X4 X6 Xb Cb Vb X 7 X2 X3 X4 X6 Xb
-1 X 5 1 1 1 -1 0 12
-1 X 5 −14 54 1 -1 14 212
-1 X 7 4 -1 0 0 -1 6
0 X 1 −1 0 0 −1 3
(Zs - Cs) -5

0

-1 1

1

1 -18

(Zs - Cs)

-1 -1 0 0 0 Sol
Cb Vb X 7 X 5 X3 X4 X6 Xb
0 X2 −15 45 45 −4 5 15 425
0 X1 15 15 15 −15 −15 185
(Zs -Cs) 1

1

0

0

0

4

4

5

4

−5

4

4

-1 1

−1

4

2

−21
2

STOP
FASE I

0

Fase II: F.O.: Max (-Z) = -3X1 - 2X2 - 4X3 + 0X4 + 0X6
-4
0
0
Sol.
Dado que:
Cb Vb X3 X4 X6 Xb
1
−4
42
(Zs - Cs) ≥ 0 Sol. Inmejorable
-2 X2 45
5
5
5
Xbi ≥ 0 Solución Factible
18
−1
−1
-3 X1 15
5
5
5
SOLUCIÓN ES ÓPTIMA
−138
9
11
1
(Zs - Cs)

5

55

5

Se cumplen todas las condiciones

Leer la solución e interpretar.

SIMPLEX REVISADO (planteamiento matricial)
Primero Revisaremos el Símplex

MAX Z = CTX + φTXh
Sujeto a:
A*X +Xh = b
X ≥ 0; Xh ≥ 0

M A X Z = C TX
Suje to a :
A *X ≤ b
X≥0

Sea una solución básica, esta cumple con:

BXb = b ⇒ Xb = B−1b

Según símplex:

AX + X h = b / • B -1
B −1 AX + B −1 X h = B−1b

Su tabla símplex será:
Cj
C1 … … Cn 0 … 0
Cb Vb X1 … … Xn Xn+1 … Xn+m
Cb1 Xb1
:
:
−1
−1
Cbi Xbi
:
:
Cbm Xbm

BA

(Zj - Cj)

T
Cb B−1A−C

O sea:

B

B−1b

B

T
Cb B−1

(Z −C) =

−1

Soluc.
Xb

T
Cb B−1b

T
Cb B −1 A − C (Xj)
T
Cb B −1
(Xh)

Xb = B −1b
T
Z = Cb B −1b

Y=

B −1 A

(Xj)

B −1

(Xh)

Las variables columnas de la...