Investigación de operaciones

Algoritmo SIMPLEX

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

Logros de la sesión
Al finalizar este MTA, estarás preparado para:

 Solucionar modelos con restricciones del

tipo menor o igual (<=).
 Solucionar modelos de maximización y
minimización.
 Solucionar problemas con variables del tipo:
• X >= 0 (variables positivas )
• X <= 0 (variables negativas)
• Xnr (no restringidas en signo).

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 2

Temario

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 3

 Modelos de maximización con variables positivas

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 4

MODELO DE MAXIMIZACIÓN - VARIABLES POSITIVAS
PROBLEMA:
Una empresa produce pintura para interiores y exteriores
y se tiene la siguiente información.

Los datos corresponden a una tonelada de pintura

Tipo de Cantidad Materia Utilidad (en miles
Pintura Operarios Prima (ton) de soles)
Interior 1 2 2
Exterior 2 1 3
Disponibilidad 6 8

¿cuánto y qué tipo de pintura se debe producir para

maximizar la utilidad?

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 5

Formulación

• Definición de variables:
X 1: Cantidad de toneladas de pintura para interiores

X 2: Cantidad de toneladas de pintura para exteriores

MAX Z  2 X 13 X 2 Maximizar utilidad

S .a.
1X 1  2 X 2  6 Disponibilidad de operarios

2 X 1  1X 2  8 Disponibilidad de materia prima

X1, X 2  0

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 6

Pasando el modelo a su forma estándar

Dado el siguiente modelo:

MAX Z  2 X 13 X 2 El método SIMPLEX se

aplica sólo a modelos que
S .a.
1X 1  2 X 2  6 tienen restricciones del
tipo menor o igual
2 X 1  1X 2  8
X1, X 2  0

Estandarizando:

MAX Z  2 X 13 X 20S1  0S 2  0

S .a.
1X 1  2 X 2  1S1  0S 2  6
2 X 1  1X 2  0S1  1S 2  8
X 1 , X 2 , S1 , S 2  0

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 7

Tablero inicial del SIMPLEX

X1 X2 S1 S2 Solución
BASE -2 -3 0 0 0 Tablero
inicial
S1 1 2 1 0 6 del SIMPLEX
S2 2 1 0 1 8
BASE
Como se está maximizando, debemos
seleccionar el coeficiente reducido más
negativo, es decir el valor -3, para
definir nuestra columna PIVOT
BASE

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

Desarrollo del algoritmo SIMPLEX

X1 X2 S1 S2 Solución Cociente
mínimo
BASE -2 -3 0 0 0
6/2 = 3
S1 1 2 1 0 6
8/1 = 8
2 S2 2 1 0 1 8
BASE
BASE
X2 1/2 1 1/2 0 3

BASE

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Desarrollo del algoritmo SIMPLEX

X1 X2 S1 S2 Solución
+
BASE -2 -3 0 0 0
S1 1 2 1 0 6
= S2 2 1 0 1 8
BASE -(1/2) 0 3/2 0 9
1*3+(-3) BASE
X2 1/2 1 1/2 0 3

BASE

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Desarrollo del algoritmo SIMPLEX

X1 X2 S1 S2 Solución
BASE -2 -3 0 0 0
S1 1 2 1 0 6
+
S2 2 1 0 1 8
BASE -(1/2) 0 3/2 0 9
1*(-1)+ 1
BASE -(1/2) 0 3/2 0 9
X2 1/2 1 1/2 0 3
= X2 1/2 1 1/2 0 3
S2 3/2 0 -(1/2) 1 5

BASE

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

Desarrollo del algoritmo SIMPLEX

X1 X2 S1 S2 Solución
BASE -2 -3 0 0 0
S1 1 2 1 0 6
S2 2 1 0 1 8 Cociente
mínimo
BASE -(1/2) 0 3/2 0 9
3/(1/2) = 6
X2 1/2 1 1/2 0 3
5/(3/2) = 10/3
S2 3/2 0 -(1/2) 1 5
BASE

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Desarrollo del algoritmo SIMPLEX

X1 X2 S1 S2 Solución
BASE -2 -3 0 0 0
S1 1 2 1 0 6
S2 2 1 0 1 8 Cociente
mínimo
BASE -(1/2) 0 3/2 0 9
3/(1/2) = 6
X2 1/2 1 1/2 0 3
5/(3/2) = 10/3
S2 3/2 0 -(1/2) 1 5
 3/2
BASE

X1 1 0 -(1/3) 2/3 10/3

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Desarrollo del algoritmo SIMPLEX

X1 X2 S1 S2 Solución
BASE -2 -3 0 0 0
S1 1 2 1 0 6
S2 2 1 0 1 8
+
BASE -(1/2) 0 3/2 0 9
X2 1/2 1 1/2 0 3
= S2 3/2 0 -(1/2) 1 5
BASE 0 0 4/3 1/3 32/3
BASE

X1 1 0 -(1/3) 2/3 10/3

1*(1/2)+(-1/2)

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Desarrollo del algoritmo SIMPLEX

X1 X2 S1 S2 Solución
BASE -2 -3 0 0 0
S1 1 2 1 0 6
S2 2 1 0 1 8
BASE -(1/2) 0 3/2 0 9
+
X2 1/2 1 1/2 0 3
S2 3/2 0 -(1/2) 1 5
BASE 0 0 4/3 1/3 32/3
= BASE 0 0 4/3 1/3 32/3
X2 0 1 2/3 -(1/3) 4/3
X1 1 0 -(1/3) 2/3 10/3
1*(-1/2)+ 1/2 X1 1 0 -(1/3) 2/3 10/3
No existen más costos reducidos negativos.
Por lo tanto, fin del algoritmo.
INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA
 Interpretación del tablero óptimo del SIMPLEX
Tablero óptimo

X1 X2 S1 S2 Solución
BASE 0 0 4/3 1/3 32/3
X2 0 1 2/3 -(1/3) 4/3
X1 1 0 -(1/3) 2/3 10/3

Vector solución:

MAX = 32/3
( X1 , X2 , S1 , S2 ) = ( 10/3 , 4/3 , 0, 0 )

Variables Variables Las variables no básicas siempre

Básicas No Básicas asumen valor cero.

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

Solución

Los resultados deben darse en función a las variables originales

Vector solución:

( X1 , X2 , S1 , S2 ) = ( 10/3 , 4/3 , 0, 0 )

SOLUCION FINAL

VARIABLES DE DECISION: FUNCION OBJETIVO

X1 = 10/3
MAX = 32/3
X2 = 4/3

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 No olvides que…

Para los problemas de maximización, el algoritmo

SIMPLEX considera siempre seleccionar como variable
que ingresa a la base, aquella variable que tiene el costo
reducido más negativo.
 La variable que sale de la base se obtiene aplicando el
calculo del cociente mínimo el cual divide los valores de
la columna solución de las variables que están en la
base, entre los valores positivos de la columna PIVOT
(no se considera la división para los valores negativos ó
ceros).

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Modelo de maximización con variables
no restringidas

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 19

Pasando el modelo a su forma estándar
Dado el siguiente modelo:
El método SIMPLEX se
aplica solo a modelos que
MAX Z  8 X  Y tienen restricciones del
S .a. tipo menor o igual
X Y  2
X  4Y  4
 X Y 1
X nr , Ynr
Estandarizando:
Hacemos el siguiente
reemplazo por estar MIN Z  8 X 18 X 21Y 11Y 20 S1  0 S 2  0 S 3  0
trabajando con una variable S .a.
no restringidas: 1X 1  1X 2  1Y1  1Y2  1S1  0S 2  0S3  2
1X 1  1X 2  4Y1  4Y2  0S1  1S 2  0S3  4
X  X1  X 2
 1X 1  1X 2  1Y1  1Y2  0S1  0S 2  1S3  1
Y Y 1Y 2
X 1 , X 2 , Y1 , Y2 , S1 , S 2 , S3  0

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 20

 Tablero inicial del SIMPLEX
X1 X2 Y1 Y2 S1 S2 S3 Solución
BASE 8 -8 -1 1 0 0 0 0
Tablero
S1 1 -1 1 -1 1 0 0 2 inicial
S2 1 -1 -4 4 0 1 0 4 del SIMPLEX

S3 -1 1 1 -1 0 0 1 1
BASE Como se esta maximizando debemos
seleccionar el coeficiente reducidos
más negativo, es decir el valor - 8, para
definir nuestra columna PIVOT

BASE

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Desarrollo del algoritmo SIMPLEX
X1 X2 Y1 Y2 S1 S2 S3 Solución Cociente
mínimo
BASE 8 -8 -1 1 0 0 0 0
S1 1 -1 1 -1 1 0 0 2 No existe

S2 1 -1 -4 4 0 1 0 4 No existe
1/1 = 1
S3 -1 1 1 -1 0 0 1 1
BASE
1

X2 -1 1 1 -1 0 0 1 1
BASE

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Desarrollo del algoritmo SIMPLEX
X1 X2 Y1 Y2 S1 S2 S3 Solución
+ BASE 8 -8 -1 1 0 0 0 0
S1 1 -1 1 -1 1 0 0 2
S2 1 -1 -4 4 0 1 0 4
S3 -1 1 1 -1 0 0 1 1
=
BASE 0 0 7 -7 0 0 8 8

1*8+(-8) X2 -1 1 1 -1 0 0 1 1
BASE

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Desarrollo del algoritmo SIMPLEX
X1 X2 Y1 Y2 S1 S2 S3 Solución
BASE 8 -8 -1 1 0 0 0 0
+ S1 1 -1 1 -1 1 0 0 2
S2 1 -1 -4 4 0 1 0 4
S3 -1 1 1 -1 0 0 1 1
BASE 0 0 7 -7 0 0 8 8
= S1 0 0 2 -2 1 0 1 3

1*1+(-1) X2 -1 1 1 -1 0 0 1 1
BASE

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Desarrollo del algoritmo SIMPLEX
X1 X2 Y1 Y2 S1 S2 S3 Solución
BASE 8 -8 -1 1 0 0 0 0
S1 1 -1 1 -1 1 0 0 2
+ S2 1 -1 -4 4 0 1 0 4
S3 -1 1 1 -1 0 0 1 1
BASE 0 0 7 -7 0 0 8 8
S1 0 0 2 -2 1 0 1 3
= S2 0 0 -3 3 0 1 1 5
1*1+(-1)
X2 -1 1 1 -1 0 0 1 1
BASE

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

Desarrollo del algoritmo SIMPLEX
X1 X2 Y1 Y2 S1 S2 S3 Solución
BASE 8 -8 -1 1 0 0 0 0
S1 1 -1 1 -1 1 0 0 2
S2 1 -1 -4 4 0 1 0 4
S3 -1 1 1 -1 0 0 1 1 Cociente
mínimo
BASE 0 0 7 -7 0 0 8 8
No existe
S1 0 0 2 -2 1 0 1 3
5/3
S2 0 0 -3 3 0 1 1 5
No existe
3 X2 -1 1 1 -1 0 0 1 1
BASE

Y2 0 0 -1 1 0 1/3 1/3 5/3

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Desarrollo del algoritmo SIMPLEX
X1 X2 Y1 Y2 S1 S2 S3 Solución
BASE 8 -8 -1 1 0 0 0 0
S1 1 -1 1 -1 1 0 0 2
S2 1 -1 -4 4 0 1 0 4
S3 -1 1 1 -1 0 0 1 1
+
BASE 0 0 7 -7 0 0 8 8
S1 0 0 2 -2 1 0 1 3
S2 0 0 -3 3 0 1 1 5
= X2 -1
0 10 10 -1
0 0
0 0 31/3
7/3 1 1
59/3
BASE
1*7+(-7)
Y2 0 0 -1 1 0 1/3 1/3 5/3

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Desarrollo del algoritmo SIMPLEX
X1 X2 Y1 Y2 S1 S2 S3 Solución
BASE 8 -8 -1 1 0 0 0 0
S1 1 -1 1 -1 1 0 0 2
S2 1 -1 -4 4 0 1 0 4
S3 -1 1 1 -1 0 0 1 1
BASE 0 0 7 -7 0 0 8 8
+
S1 0 0 2 -2 1 0 1 3
S2 0 0 -3 3 0 1 1 5
X2 -1 1 1 -1 0 0 1 1
= BASE
S1 0 0 0 0 0 7/3 31/3 59/3
0 0 0 0 1 2/3 5/3 19/3
1*2+(-2)
Y2 0 0 -1 1 0 1/3 1/3 5/3

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Desarrollo del algoritmo SIMPLEX
X1 X2 Y1 Y2 S1 S2 S3 Solución
BASE 8 -8 -1 1 0 0 0 0
S1 1 -1 1 -1 1 0 0 2
S2 1 -1 -4 4 0 1 0 4
S3 -1 1 No
1 existen
-1 0más 0costos1 reducidos 1 negativos.
Por lo tanto, fin del algoritmo
BASE 0 0 7 -7 0 0 8 8
S1 0 0 2 -2 1 0 1 3
S2 0 0 -3 3 0 1 1 5
+
X2 -1 1 1 -1 0 0 1 1
BASE 0 0 0 0 0 7/3 31/3 59/3
1*1+(-1) S1 0 0 0 0 1 2/3 5/3 19/3

= YX2 0
-1 01 -1
0 10 0
0 1/3
1/3 1/3
4/3 5/3
8/3
2

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

Interpretación del tablero óptimo del SIMPLEX

Tablero óptimo

X1 X2 Y1 Y2 S1 S2 S3 Solución
BASE 0 0 0 0 0 7/3 31/3 59/3
S1 0 0 0 0 1 2/3 5/3 19/3
Y2 0 0 -1 1 0 1/3 1/3 5/3
X2 -1 1 0 0 0 1/3 4/3 8/3
Vector solución:
MAX = 59/3
Variables Básicas

( X1, X2 , Y1 , Y2, S1 , S2 ) = ( 0 , 8/3 , 0 , 5/3 , 19/3 , 0 )

Variables No Básicas Las variables no básicas siempre

asumen valor cero.

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

Solución

Los resultados deben darse en función a las variables originales

Vector solución:
( X1 , X2 , Y1 , Y2 , S1 , S2 ) = ( 0 , 8/3 , 0 , 5/3 , 19/3 , 0)

SOLUCION FINAL

VARIABLES DE DECISION: FUNCION OBJETIVO

X = X1 - X2 = (0) - (8/3) = - 8/3

MAX = 59/3
Y = Y1 - Y2 = (0) - (5/3) = - 5/3

Recordar que al inicio hicimos un cambio de variables por

estar trabajando con variables no restringidas
INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA
 No olvides que…

Para los problemas que usan variables no restringidas,

debemos reemplazar por la diferencia de una variable
de exceso menos una variable de defecto: X = X1 – X2,
luego se procede con el algoritmo SIMPLEX según sea el
caso para maximizar ó minimizar.

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Modelos de minimización con variables positivas

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 33

MODELO DE MINIMIZACIÓN - VARIABLES POSITIVAS
PROBLEMA:
Harina tipo I para uso interno y harina tipo II para venta.

Área ventas: diferencia entre la harina tipo I y II debe ser

a lo mas 6 toneladas.

Harina tipo I (1 ton), Harina tipo II (1 ton),

Costo de S/. 2 mil Ganancia de S/. 3 mil
Requiere 1 operario Requiere 2 operario

¿cuánto y qué tipo de harina se debe producir para

minimizar los costos?

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 34

Formulación

• Definición de variables: Minimizar: -3X2

implica
X 1: Cantidad de toneladas de harina tipo I para maximizar
uso interno
la utilidad de la
X 2: Cantidad de toneladas de harina tipo II paraharina
venta tipo II

MIN Z  2 X 13 X 2 Minimizar costos

S .a.
1X 1  1X 2  4 Disponibilidad de operarios

1X 1  1X 2  6 Condición de demanda

X1, X 2  0

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 35

Pasando el modelo a su forma estándar
Dado el siguiente modelo:

MIN Z  2 X 13 X 2 El método SIMPLEX se

aplica sólo a modelos que
S .a.
1X 1  1X 2  4 tienen restricciones del
tipo menor o igual
1X 1  1X 2  6
X1, X 2  0

Estandarizando:

MIN Z  2 X 13 X 20S1  0S 2  0

S .a.
1X 1  1X 2  1S1  0 S 2  4
1X 1  1X 2  0S1  1S 2  6
X 1 , X 2 , S1 , S 2  0

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 36

Tablero inicial del SIMPLEX

X1 X2 S1 S2 Solución
BASE -2 3 0 0 0 Tablero
inicial
S1 1 1 1 0 4 del SIMPLEX
S2 1 -1 0 1 6
BASE
Como se está minimizando debemos
seleccionar el coeficiente reducidos
más positivo, es decir el valor 3, para
definir nuestra columna PIVOT

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

Desarrollo del algoritmo SIMPLEX

X1 X2 S1 S2 Solución Cociente
mínimo
BASE -2 3 0 0 0
4/1 = 1
S1 1 1 1 0 4
No existe
1 S2 1 -1 0 1 6
BASE
BASE
X2 1 1 1 0 4

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Desarrollo del algoritmo SIMPLEX

X1 X2 S1 S2 Solución
+
BASE -2 3 0 0 0
S1 1 1 1 0 4
= S2 1 -1 0 1 6
BASE -5 0 -3 0 -12
1*(-3)+3 BASE
X2 1 1 1 0 4

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Desarrollo del algoritmo SIMPLEX

X1 X2 S1 S2 Solución
BASE -2 3 0 0 0
S1 1 1 1 0 4
+
S2 1 -1 0 1 6

1*1+(- 1)
BASE -5 0 -3 0 -12
= X2 1 1 1 0 4
S2 2 0 1 1 10

No existen más costos reducidos positivos.

Por lo tanto, fin del algoritmo

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

Interpretación del tablero óptimo del SIMPLEX

Tablero óptimo

X1 X2 S1 S2 Solución
BASE -5 0 -3 0 -12
X2 1 1 1 0 4
S2 2 0 1 1 10
Vector solución:
Variables Básicas

( X1 , X2 , S1 , S2 ) = ( 0 , 4 , 0 , 10 ) MIN = -12

Variables No Básicas Las variables no básicas siempre

asumen valor cero.

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

Solución

Los resultados deben darse en función a las variables originales

Vector solución:

( X1 , X2 , S1 , S2 ) = ( 0 , 4 , 0 , 10 )

SOLUCION FINAL

VARIABLES DE DECISION: FUNCION OBJETIVO

X1 = 0
MIN = -12
X2 = 4

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 No olvides que…

Para los problemas de minimización, el algoritmo

SIMPLEX considera siempre seleccionar como variable que
ingresa a la base, aquella variable que tiene el costo
reducido más positivo.
 La variable que sale de la base se obtiene aplicando el
cociente mínimo, el cual se obtiene dividiendo los valores
de la columna solución de las variables que están en la
base, entre los valores positivos de la columna PIVOT (no
se considera la división para los valores negativos ó ceros).

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Modelo de minimización con variables negativas

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 44

MODELO DE MINIMIZACIÓN - VARIABLES NEGATIVAS
Dado el siguiente modelo:
El método SIMPLEX se
MIN Z  X Y aplica solo a modelos que
S .a. tienen restricciones del
X Y  2
tipo menor o igual
X Y  4
X 1  0, Y  0

Hacemos el siguiente Estandarizando:

reemplazo por estar
trabajando con una variable MIN Z  X Y 10 S1  0 S 2  0
negativa: S .a.
1X  1Y1  1S1  0 S 2  2
Y  Y 1 1X  1Y1  0S1  1S 2  4
X , Y1  0

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 45

Tablero inicial del SIMPLEX

X Y1 S1 S2 Solución
BASE -1 1 0 0 0 Tablero
inicial
S1 1 -1 1 0 2 del SIMPLEX
S2 1 1 0 1 4
BASE
Como se está minimizando, debemos
seleccionar el coeficiente reducido más
positivo, es decir, el valor 1, para definir
nuestra columna PIVOT

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

Desarrollo del algoritmo SIMPLEX

X Y1 S1 S2 Solución
Cociente
BASE -1 1 0 0 0 mínimo

S1 1 -1 1 0 2 No existe
4/1 = 4
S2 1 1 0 1 4
BASE
1 BASE

Y1 1 1 0 1 4

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Desarrollo del algoritmo SIMPLEX

X Y1 S1 S2 Solución
+ BASE -1 1 0 0 0
S1 1 -1 1 0 2
S2 1 1 0 1 4
=
BASE -2 0 0 -1 -4
BASE
1*(-1)+1
Y1 1 1 0 1 4

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

 Desarrollo del algoritmo SIMPLEX

X Y1 S1 S2 Solución
BASE -1 1 0 0 0
+ S1 1 -1 1 0 2
S2 1 -1 0 1 4
BASE -2 0 0 -1 -4
= S1 2 0 1 1 6
1*1+(- 1)
Y1 1 1 0 1 4

No existen más costos reducidos positivos.

Por lo tanto, fin del algoritmo.

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

Interpretación del tablero óptimo del SIMPLEX

Tablero óptimo

X Y1 S1 S2 Solución
BASE -2 0 0 -1 -4
S1 2 0 1 1 6
Y1 1 1 0 1 4
Vector solución:
Variables Básicas

( X , Y1 , S1 , S2 ) = ( 0 , 4 , 0, 6 ) MIN = -4

Variables No Básicas Las variables no básicas siempre

asumen valor cero.

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

Solución

Los resultados deben darse en función a las variables originales

Vector solución:
( X , Y1 , S1 , S2 ) = ( 0 , 4 , 0, 6 )

SOLUCION FINAL

VARIABLES DE DECISION: FUNCION OBJETIVO

X=0
MIN = -4
Y = - Y1 = - (4) = -4

Recordar que al inicio hicimos un cambio de variable por

estar trabajando con una variable negativa
INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA
 No olvides que…

Para los problemas que usan variables negativas,

debemos reemplazar la variable original por otra
variable con signo negativo: X = - X1 , luego se procede
con el algoritmo SIMPLEX según sea el caso para
maximizar ó minimizar.

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA

No olvides que…

• Para construir el tablero inicial del SIMPLEX debes

considerar las tres condiciones para pasar el modelo
a su forma estándar:

 Lado derecho de las restricciones deben ser

constantes mayores o iguales a cero.
 Las inecuaciones deben ser expresadas en forma
de igualdades, usando variables de holgura.
 Las variables deben ser positivas.

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 53

Reflexiona un momento…

• ¿Por qué es necesario realizar los cambios de

variables cuando se trabaja con variables negativas
y variables no restringidas?
• ¿Cómo reconocemos que ha finalizado el algoritmo
SIMPLEX para un problema de maximización?
• ¿Cómo reconocemos que ha finalizado el algoritmo
SIMPLEX para un problema de minimización?

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 54

 Ejercicios
Propuestos
Para cada ejercicio se pide:
1. Hallar su forma estándar
2. Hallar la solución por el método SIMPLEX
3. Obtener el vector solución del tablero óptimo
4. Dar la solución en función a las variables de decisión
INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 55
Ejercicio 1:

MAX Z  X1  X 2
S .a.
4 X 1  X 2  100
X 1  X 2  80
X 1  40
X1, X 2  0
INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 56
Ejercicio 2:

MIN Z  4 X 1  X 2
S .a.
2 X1  X 2  8
X2  5
X1  X 2  4
X1, X 2  0
INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 57
Ejercicio 3:

MAX Z  2X  Y
S .a.
3X  Y  6
X Y  4
X  0, Ynr

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 58

 Solución

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 59

Solución Ejercicio 1
Vector solución:

( X1 , X2 , S1 , S2 , S3 ) = ( 20/3 , 220/3 , 0 , 0 , 100/3 )

SOLUCION FINAL

VARIABLES DE DECISION: FUNCION OBJETIVO

X1 = 20/3
MAX = 80
X2 = 220/3

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 60

Solución Ejercicio 2

Vector solución:

( X1 , X2 , S1 , S2 , S3 ) = ( 0 , 5 , 3 , 0 , 9 )

SOLUCION FINAL

VARIABLES DE DECISION: FUNCION OBJETIVO

X1 = 0
MIN = - 5
X2 = 5

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 61

Solución Ejercicio 3

Vector solución:

( X , Y1 , Y2, S1 , S2 ) = ( 1 , 3 , 0 , 0 , 0 )

SOLUCION FINAL

VARIABLES DE DECISION: FUNCION OBJETIVO

X=1
MAX = 5
Y = Y1 – Y2 = (3) - ( 0) = 3

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 62

Conclusiones

El método SIMPLEX:

• Permite obtener soluciones óptimas a problemas de n

variables.
• Sólo es aplicable a problemas que tienen restricciones
del tipo menor o igual.

INVESTIGACIÓN DE OPERACIONES PROF. LUIS ULFE VEGA 63