1IND47 Modelos Determinísticos

1IND47 Modelos Determinísticos

Unidad 3:
Método Simplex
 Método Simplex Parte 3

ÍNDICE
1. Variables artificiales y coeficientes de castigo
2. Método simplex de las grandes M´s

3
 Introducción

El Método Simplex usado hasta ahora implica

resolver problemas con restricciones menor- igual, que
sólo requierian variables de holgura.

¿Qué pasa si tenemos restricciones mayor-

igual?
¿El método funciona igual con las variables
de exceso?

4
 Introducción
EJERCICIO: Resolver el siguiente PPL

¿Qué pasa con el

Forma estándar
X1 : número de unidades del producto 1
X2: número de unidades del producto 2
método simplex ?
Maximizar Z = 10X1 + 20X2
Maximizar Z = 10X1 +20X2
Sujeto a: Sujeto a:
1X1 +1X2 ≤ 70 (1) 1X1 + 1X2 + 1S1= 70 (1)
2X1 +4X2 ≥ 80 (2) 2X1 + 4X2 – 1S2= 80 (2)
2X1 +1X2 = 100 (3) 2X1 + 1X2 = 100 (3)
Con X1; X2 ≥ 0
Con X1; X2; S1; S2 ≥ 0

No podemos tener directamente

una solución básica factible! 5
 1. Variables artificiales y coeficientes de castigo

Variable artificial: Es una variable adicional que se le colocará a las

ecuaciones de la forma estándar para obtener una solución básica
factible y poder escribir la tabla simplex inicial.
Las variables artificiales se usan en las ecuaciones que provienen de
restricciones [Link] (≥) e igual (=).
La variable artificial se introduce para iniciar el método simplex, pero
se espera que sea cero (variable no básica) en el tablero óptimo final

Coeficientes de castigo: Se usan para asegurar que las variables

. artificiales introducidas para iniciar el método simplex, se
conviertan en variables no básicas en el tablero final.
Se usa un valor de castigo, M grande (big M) para colocarlo como
coeficiente a cada variable artificial en la función objetivo.
6
.
 2. Método simplex de las grandes M´s
Para aplicar el algoritmo simplex de las grandes M´s o de coeficientes de
castigo se debe tener al menos una restricción mayor-igual y/o una restricción
de igualdad.
El algoritmo consiste en seguir los siguientes pasos:
Paso 1: Convertir el problema de programación lineal a la forma estándar de
programación lineal
Paso 2: Agregar variables artificiales a las ecuaciones que provienen de
restricciones mayor-igual o restricciones de igualdad
Paso 3: Las variables artificiales se colocan en la función objetivo con un valor
de coeficiente M grande (big M), este valor actúa como un costo alto y para
que no intervenga la variable artificial debe ser cero (no básica), en la solución
óptima final.
Paso 4: Use como solución básica inicial, aquella que contiene a las variables
artificiales, elimine las variables artificiales de la función objetivo y lleve al
tablero simplex inicial.
Paso 5: Use el algoritmo simplex tabular para resolver el problema y verifique
que en el tablero final las variables artificiales sean no básicas. Este tablero
nos dará la solución optima.
7
 2. Método simplex de las grandes M´s
EJERCICIO: Resolver el siguiente PPL

X1 : número de unidades del producto 1

X2: número de unidades del producto 2
Maximizar Z = 10X1 + 20X2
– MA1 – MA2
Maximizar Z = 10X1 +20X2 Sujeto a:
Sujeto a: 1X1 +1X2 + 1S1 = 70 (1)
1X1 +1X2 ≤ 70 (1)
2X1 +4X2 – 1S2 + 1A1 = 80 (2)
2X1 +4X2 ≥ 80 (2)
2X1 +1X2 = 100 (3) 2X1 +1X2 + 1A2 = 100 (3)

Con X1; X2 ≥ 0
Con X1; X2; S1; S2; A1; A2 ≥ 0

8
 2. Método simplex de las grandes M´s
Maximizar Z = 10X1 + 20X2 – MA1 – MA2 Solución básica inicial
Sujeto a: Variables no básicas
1X1 +1X2 + 1S1 = 70 (1) X1=0; X2=0; S2=0
2X1 +4X2 – 1S2 + 1A1 = 80 (2) Variables básicas
2X1 +1X2 + 1A2 = 100 (3) S1=70; A1=80; A2=100

Z= 10X1+20X2-M(80-2X1-4X2+1S2)-M(100-2X1-1X2)
Z=(4M+10)X1+(5M+20)X2-MS2-180M
Z-(4M+10)X1-(5M+20)X2+MS2= -180M ; M grande
Tablero inicial

Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 -4M-10 -5M-20 0 M 0 0 -180M
S1 0 1 1 1 0 0 0 70
A1 0 2 4 0 -1 1 0 80
A2 0 2 1 0 0 0 1 100

9
 2. Método simplex de las grandes M´s
Tablero inicial
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 -4M-10 -5M-20 0 M 0 0 -180M
S1 0 1 1 1 0 0 0 70 70/1=70
A1 0 2 4 0 -1 1 0 80 80/4=20
A2 0 2 1 0 0 0 1 100 100/1=100
Entra: X2
Sale: A1 1 -4M-10 -5M-20 0 M 0 0 -180M
(5M+20) 0 0,5 1 0 -0,25 0,25 0 20
1 -1.5M 0 0 -0.25M-5 1.25M+5 0 -80M+400

Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 -1.5M 0 0 -0.25M-5 1.25M+5 0 -80M+400
S1
X2 0 0,5 1 0 -0,25 0,25 0 20
A2
10
 2. Método simplex de las grandes M´s
Tablero inicial
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 -4M-10 -5M-20 0 M 0 0 -180M
S1 0 1 1 1 0 0 0 70 70/1=70
A1 0 2 4 0 -1 1 0 80 80/4=20
A2 0 2 1 0 0 0 1 100 100/1=100
Entra: X2
Sale: A1 0 1 1 1 0 0 0 70
(-1) 0 0,5 1 0 -0,25 0,25 0 20
0 0,5 0 1 0,25 -0,25 0 50

Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 -1.5M 0 0 -0.25M-5 1.25M+5 0 -80M+400
S1 0 0,5 0 1 0,25 -0,25 0 50
X2 0 0,5 1 0 -0,25 0,25 0 20
A2
11
 2. Método simplex de las grandes M´s
Tablero inicial
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 -4M-10 -5M-20 0 M 0 0 -180M
S1 0 1 1 1 0 0 0 70 70/1=70
A1 0 2 4 0 -1 1 0 80 80/4=20
A2 0 2 1 0 0 0 1 100 100/1=100
Entra: X2
Sale: A1 0 2 1 0 0 0 1 100
(-1) 0 0,5 1 0 -0,25 0,25 0 20
0 1,5 0 0 0,25 -0,25 1 80
Tablero 2
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 -1.5M 0 0 -0.25M-5 1.25M+5 0 -80M+400
S1 0 0,5 0 1 0,25 -0,25 0 50
X2 0 0,5 1 0 -0,25 0,25 0 20
A2 0 1,5 0 0 0,25 -0,25 1 80
12
 2. Método simplex de las grandes M´s
Tablero 2
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 -1.5M 0 0 -0.25M-5 1.25M+5 0 -80M+400
S1 0 0,5 0 1 0,25 -0,25 0 50 50/0,5=100
X2 0 0,5 1 0 -0,25 0,25 0 20 20/0,5=40
A2 0 1,5 0 0 0,25 -0,25 1 80 80/1,5=53,33
Entra: X1
Sale: X2 1 -1.5M 0 0 -0.25M-5 1.25M+5 0 -80M+400
(1.5M) 0 1 2 0 -0,5 0,5 0 40
1 0 3M 0 -M-5 2M+5 0 -20M+400

Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 0 3M 0 -M-5 2M+5 0 -20M+400
S1
X1 0 1 2 0 -0,5 0,5 0 40
A2
13
 2. Método simplex de las grandes M´s
Tablero 2
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 -1.5M 0 0 -0.25M-5 1.25M+5 0 -80M+400
S1 0 0,5 0 1 0,25 -0,25 0 50 50/0,5=100
X2 0 0,5 1 0 -0,25 0,25 0 20 20/0,5=40
A2 0 1,5 0 0 0,25 -0,25 1 80 80/1,5=53,33
Entra: X1
Sale: X2 0 0,5 0 1 0,25 -0,25 0 50
(-0,5) 0 1 2 0 -0,5 0,5 0 40
0 0 -1 1 0,5 -0,5 0 30

Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 0 3M 0 -M-5 2M+5 0 -20M+400
S1 0 0 -1 1 0,5 -0,5 0 30
X1 0 1 2 0 -0,5 0,5 0 40
A2 14
 2. Método simplex de las grandes M´s
Tablero 2
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 -1.5M 0 0 -0.25M-5 1.25M+5 0 -80M+400
S1 0 0,5 0 1 0,25 -0,25 0 50 50/0,5=100
X2 0 0,5 1 0 -0,25 0,25 0 20 20/0,5=40
A2 0 1,5 0 0 0,25 -0,25 1 80 80/1,5=53,33
Entra: X1
Sale: X2 0 1,5 0 0 0,25 -0,25 1 80
(-1,5) 0 1 2 0 -0,5 0,5 0 40
0 0 -3 0 1 -1 1 20
Tablero 3
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 0 3M 0 -M-5 2M+5 0 -20M+400
S1 0 0 -1 1 0,5 -0,5 0 30
X1 0 1 2 0 -0,5 0,5 0 40
A2 0 0 -3 0 1 -1 1 20
15
 2. Método simplex de las grandes M´s
Tablero 3
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 0 3M 0 -M-5 2M+5 0 -20M+400
S1 0 0 -1 1 0,5 -0,5 0 30 30/0,5=60
X1 0 1 2 0 -0,5 0,5 0 40 40/-0,5=-80
A2 0 0 -3 0 1 -1 1 20 20/1=20
Entra: S2
Sale: A2 1 0 3M 0 -M-5 2M+5 0 -20M+400
(M+5) 0 0 -3 0 1 -1 1 20
1 0 -15 0 0 M M+5 500

Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 0 -15 0 0 M M+5 500
S1
X1
S2 0 0 -3 0 1 -1 1 20
16
 2. Método simplex de las grandes M´s
Tablero 3
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 0 3M 0 -M-5 2M+5 0 -20M+400
S1 0 0 -1 1 0,5 -0,5 0 30 30/0,5=60
X1 0 1 2 0 -0,5 0,5 0 40 40/-0,5=-80
A2 0 0 -3 0 1 -1 1 20 20/1=20
Entra: S2
Sale: A2 0 0 -1 1 0,5 -0,5 0 30
(-0,5) 0 0 -3 0 1 -1 1 20
0 0 0,5 1 0 0 -0,5 20

Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 0 -15 0 0 M M+5 500
S1 0 0 0,5 1 0 0 -0,5 20
X1
S2 0 0 -3 0 1 -1 1 20
17
 2. Método simplex de las grandes M´s
Tablero 3
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 0 3M 0 -M-5 2M+5 0 -20M+400
S1 0 0 -1 1 0,5 -0,5 0 30 30/0,5=60
X1 0 1 2 0 -0,5 0,5 0 40 40/-0,5=-80
A2 0 0 -3 0 1 -1 1 20 20/1=20
Entra: S2
Sale: A2 0 1 2 0 -0,5 0,5 0 40
(+0,5) 0 0 -3 0 1 -1 1 20
0 1 0,5 0 0 0 0,5 50
Tablero 4
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 0 -15 0 0 M M+5 500
S1 0 0 0,5 1 0 0 -0,5 20
X1 0 1 0,5 0 0 0 0,5 50
S2 0 0 -3 0 1 -1 1 20
18
 2. Método simplex de las grandes M´s
Tablero 4
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 0 -15 0 0 M M+5 500
S1 0 0 0,5 1 0 0 -0,5 20 20/0,5=40
X1 0 1 0,5 0 0 0 0,5 50 50/0,5=100
S2 0 0 -3 0 1 -1 1 20 20/-3=-6,67
Entra: X2
Sale: S1 1 0 -15 0 0 M M+5 500
(+15) 0 0 1 2 0 0 -1 40
1 0 0 30 0 M M-10 1100

Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 0 0 30 0 M M-10 1100
X2 0 0 1 2 0 0 -1 40
X1
S2
19
 2. Método simplex de las grandes M´s
Tablero 4
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 0 -15 0 0 M M+5 500
S1 0 0 0,5 1 0 0 -0,5 20 20/0,5=40
X1 0 1 0,5 0 0 0 0,5 50 50/0,5=100
S2 0 0 -3 0 1 -1 1 20 20/-3=-6,67
Entra: X2
Sale: S1 0 1 0,5 0 0 0 0,5 50
(-0,5) 0 0 1 2 0 0 -1 40
0 1 0 -1 0 0 1 30

Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 0 0 30 0 M M-10 1100
X2 0 0 1 2 0 0 -1 40
X1 0 1 0 -1 0 0 1 30
S2
20
 2. Método simplex de las grandes M´s
Tablero 4
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 0 -15 0 0 M M+5 500
S1 0 0 0,5 1 0 0 -0,5 20 20/0,5=40
X1 0 1 0,5 0 0 0 0,5 50 50/0,5=100
S2 0 0 -3 0 1 -1 1 20 20/-3=-6,67
Entra: X2
Sale: S1 0 0 -3 0 1 -1 1 20
(+3) 0 0 1 2 0 0 -1 40
0 0 0 6 1 -1 -2 140
Tablero Final
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 0 0 30 0 M M-10 1100
X2 0 0 1 2 0 0 -1 40
X1 0 1 0 -1 0 0 1 30
S2 0 0 0 6 1 -1 -2 140
21
 2. Método simplex de las grandes M´s
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 -4M-10 -5M-20 0 M 0 0 -180M
Tablero S1 0 1 1 1 0 0 0 70
Inicial 0 2 4 0 -1 1 0 80
A1
A2 0 2 1 0 0 0 1 100
Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Básicas 1 Z
-1.5M X10 X20 S1
-0.25M-5 S2
1.25M+5 A10 A2 VALORES
-80M+400
Variables
S1 0
Básicas 10,5 Z0 0 3M1
X1 X20,25
0 -0,25
-M-5
S1 S2 0
2M+5 A10 50 -20M+400
A2 VALORES
Tableros X2 S10 00,5
Variables
10 1 0-10 1
-0,25
-15 00,5
0,25 -0,5
0 0 0 20 30
Básicas M M+5 500
Intermedios A2 X10 01,5
S1 01 0 02 0 0,50
0,25 -0,5
1-0,25 00,51 00 80 -0,540 20
A2 0
X1 00 1-3 0,50 01 0-1 01 0,520 50
S2 0 0 -3 0 1 -1 1 20

Z X1 X2 S1 S2 A1 A2 VALORES
Tablero Variables
1 0 0 30 0 M M-10 1100
Básicas
Final
X2 0 0 1 2 0 0 -1 40
X1 0 1 0 -1 0 0 1 30
S2 0 0 0 6 1 -1 -2 140 22
 2. Método simplex de las grandes M´s
Tablero Z X1 X2 S1 S2 A1 A2 VALORES
Variables
Final Básicas 1 0 0 30 0 M M-10 1100
X2 0 0 1 2 0 0 -1 40
X1 0 1 0 -1 0 0 1 30
S2 0 0 0 6 1 -1 -2 140

Solución básica
Variables no básicas
S1=0; A1=0; A2=0
Variables básicas
X1=30; X2=40; S2=140

Z=1100

23
 RESUMEN

Los problemas de programación lineal, se pueden

resolver usando el método simplex tabular.
Si las restricciones son:
Menor-igual solamente se emplearán variables de holgura
Mayor-igual se emplearán variables de exceso, artificial y coeficiente de
castigo
Igual se emplean artificial y coeficiente de castigo

El método simplex es una herramienta para resolver

problemas de programación lineal de cualquier tipo.

24
 FIN
Método Simplex

25