MÉTODO SIMPLEX

El método simplex está basado en el algebra. Es un método analítico de solución de

problemas de programación lineal capaz de resolver modelos más complejos que los
resueltos mediante el método gráfico sin restricción en el número de variables. Es un
método iterativo que permite ir mejorando la solución en cada paso. Se lo emplea para
resolver problemas de programación lineal de maximización y de minimización. Es un
proceso numérico repetitivo que permite llegar a una solución óptima partiendo de un
punto extremo conocido. Por lo tanto, si esta no satisfice es necesario tomar otra solución
que nos depara el valor de Z, siendo esta mayor o menor y así sucesivamente hasta llegar
a la solución final.

Este método fue creado en el año de 1947 por el estadounidense George Bernard Dantzig
y el ruso Leonid Vitalievich Kantorovich, con el ánimo de crear un algoritmo capaz de
solucionar problemas de m restricciones y n variables.

1. Todas las limitaciones o restricciones deben estar establecidas como ecuaciones.

2. El Segundo miembro de una limitante debe ser positivo
3. Todas las variables están restringidas a valores no negativos

OBSERVACIONES IMPORTANTES

 VARIABLES DE HOLGURA Y EXCESO

Este método trabaja convirtiendo inecuaciones en ecuaciones utilizando unas

variables denominadas de holgura y exceso relacionadas con el recurso al cual
hace referencia la restricción, estas variables adquieren un gran valor en el análisis
de sensibilidad y juegan un rol fundamental en la creación de la matriz identidad
base del método.

Estas variables suelen estar representadas por la letra "S", se suman si la

restricción es de signo "<= " y se restan si la restricción es de signo ">=".

EJEMPLO:

Ecuaciones modeladas mediante programación lineal

2.5𝑥1 + 4𝑥2 ≤ 100

5𝑥1 + 4𝑥2 ≥ 120

Inecuaciones transformadas en ecuaciones

2.5𝑥1 + 4𝑥2 + 1𝑆1 + 0𝑆2 = 100

5𝑥1 + 4𝑥2 + 0𝑆1 − 1𝑆2 = 120

matriz identidad
  VARIABLE ARTIFICIAL
MÉTODO DE LA "M"

Variable artificial: Truco matemático para convertir inecuaciones en ecuaciones,

o en el caso de existir igualdades en el problema original.

La característica principal en el método de la M es que estas variables no forman

parte de la solución, dado que no representan recursos. El objetivo fundamental
de estas variables es la formación de la matriz identidad. Estas variables, siempre
se suman a las restricciones, su coeficiente es M (donde M significa un número
demasiado grande muy poco atractivo para la función objetivo).

El signo en la función objetivo va en contra del sentido de la misma, es decir, en

problemas de Maximización su signo es menos (-) y en problemas de
Minimización su signo es (+).

PROCEDIMIENTO

No es importante el numero de limitaciones (inecuaciones) y de incógnitas de un sistema

dado que el método simplex se ajusta a un tratamiento de identificación y a su solución.

En el caso en el que el sistema tenga un numero de ecuaciones inferior al numero de

incógnitas, existen muchas soluciones. Por lo tanto, se tiene la siguiente tabla para el caso
de maximización, minimización e igualdad, respectivamente:

Maximización Minización Igualdad

𝒙𝟏 + 𝒙𝟐 ≤ 𝟐𝟎𝟎 𝑥1 + 2𝑥2 ≥ 200 𝑥1 + 𝑥2 = 200
Variable de holgura= +S -V de holgura + V artificial=- +V artificial= +M
S+M
𝒙𝟏 + 𝒙𝟐 + 𝑺𝟏 = 𝟐𝟎𝟎 𝑥1 + 2𝑥2 − 𝑆1 + 𝑀1 = 200 𝑥1 + 𝑥2 + 𝑀1 = 200

EJERCICIO PASO A PASO

EL PROBLEMA

Una fabrica produce 2 tipos de camisas A y B, las camisas tipo A requieren 2,5 minutos
para cortarlas y 5 minutos para confeccionarlos; las de tipo B requieren 4 min para
cortarlas y 4 minutos para confeccionarlas. Si dispone de 1 hora y 40 min para corte y 2
horas para confección.

Confecciones Cortado
𝒙𝟏 5 2.5
𝒙𝟐 4 4
Disponibilidad 120 100
Paso 1: Modelación mediante programación lineal

Variables

𝑥1 : 𝐶𝑎𝑚𝑖𝑠𝑎𝑠 𝐴
𝑥2 : 𝐶𝑎𝑚𝑖𝑠𝑎𝑠 𝐵

Función Objetivo

𝑍(𝑚𝑎𝑥) = 2.5𝑥1 + 3𝑥2

Restricciones

Corte
2.5𝑥1 + 4𝑥2 ≤ 100
Confección
5𝑥1 + 4𝑥2 ≤ 120

Paso 2: Convertir las inecuaciones en ecuaciones

Abstracciones

Corte
2.5𝑥1 + 4𝑥2 + 𝑆1 + 0𝑆2 = 100
Confección
5𝑥1 + 4𝑥2 + 0𝑆1 + 𝑆2 = 120

Función Objetivo
𝑍(𝑚𝑎𝑥) = 2.5𝑥1 + 3𝑥2 + 0𝑆1 + 0𝑆2

𝑪𝒋 2.5 3 0 0
𝑿𝒋 𝒃𝒏 𝒙𝟏 𝒙𝟐 𝑺𝟏 𝑺𝟐
0 𝑺𝟏 100 5/2* 4 1 0
0 𝑺𝟐 120 5° 4 0 1
𝒁𝒋 0 0 0 0 0
𝒁𝒋 − 𝑪𝒋 - -2.5 -3 0 0

Pivote
𝑏𝑛 𝑏𝑛 100
⟹ ⟹ = 25 ∗
𝑋𝑗 𝑋2 4
Semipivote
𝑏𝑛 𝑏𝑛 120
⟹ ⟹ = 30°
𝑋𝑗 𝑋2 4

𝑪𝒋 2.5 3 0 0
𝑿𝒋 𝒃𝒏 𝒙𝟏 𝒙𝟐 𝑺𝟏 𝑺𝟐
3 𝒙𝟐 25 5/8° 1 1/4 0
0 𝑺𝟐 20 5/2* 0 -1 1
 𝒁𝒋 75 15/8 3 3/4 0
𝒁𝒋 − 𝑪𝒋 - -5/8 0 3/4 0

Pivote
𝑏𝑛 𝑏𝑛 20
⟹ ⟹ =8∗
𝑋𝑗 𝑋2 5
2
Semipivote
𝑏𝑛 𝑏𝑛 25
⟹ ⟹ = 40°
𝑋𝑗 𝑋2 5
8

Pivote Semipivote
𝟏𝟎𝟎 120 − 24(4) = 20
= 𝟐𝟓
𝟒
𝟐. 𝟓 𝟓 5 5
= 5 − (4) =
𝟒 𝟖 8 2
𝟒 4 − 1(4) = 0
=𝟏
𝟒
𝟏 𝟏 1
= 0 − (4) = −1
𝟒 𝟒 4
𝟎 1 − 0(4) = 1
=𝟎
𝟒

𝑪𝒋 2.5 3 0 0
𝑿𝒋 𝒃𝒏 𝒙𝟏 𝒙𝟐 𝑺𝟏 𝑺𝟐
3 𝒙𝟐 20 0 1 1/2 -1/4
2.5 𝒙𝟏 8 1 0 -2/5 2/5
𝒁𝒋 80 2.5 3 1/2 1/4
𝒁𝒋 − 𝑪𝒋 - 0 0 1/2 1/4

Pivote Semipivote
𝟐𝟎 5
=𝟖 25 − 8 ( ) = 20
𝟓 8
(𝟐)
𝟓 5 5
𝟐 =𝟏 − 1 ( )=0
8 8
𝟓
(𝟐)
𝟎 5
=𝟎 1 − 0( ) = 1
𝟓 8
(𝟐)
−𝟏 𝟐 1 2 5 1
=− − (− ) ( ) =
𝟓 𝟓 4 5 8 2
(𝟐 )
𝟏 𝟐 2 5 1
= 1− ( )=−
𝟓
(𝟐) 𝟓 5 8 4
INTERPRETACIÓN:

La empresa debe producir 20 camisas tipo A y 8 del tipo B para obtener su máxima
ganancia de 80$

EJERCICIO 1

Baba Furniture emplea a cuatro carpinteros durante 10 días para ensamblar sillas y mesas.
Se requiere 30 minutos para ensamblar una silla y 2 horas para ensamblar una mesa. Por
lo común, los clientes compran entre cuatro y seis sillas con cada mesa. Las utilidades
son de 13.5 dólares por mesa y 5 dólares por silla. La compañía opera un turno de 8 horas
al día. Determine la mezcla de producción óptima.

DEFINICION DE VARIABLES

Sillas A = X1
Mesas B = X2

FUNCIÓN OBJETIVO

Z(máx) 5𝑥1 + 13.5𝑥2 + 0𝑆1 + 0𝑆2 + 0𝑆3

RESTRICCIONES ABSTRACCIONES
1 1
Relación sillas/mesas: 2 𝑥1 + 2𝑥2 ≤ 320 𝑥 + 2𝑥2 + 𝑆1 + 0𝑆2 + 0𝑆3 = 320
2 1

Relación sillas/mesas: −𝑥1 + 4𝑥2 ≤ 0 −𝑥1 + 4𝑥2 + 0𝑆1 + 𝑆2 + 0𝑆3 = 0

𝑋1 − 6𝑥2 ≤ 0 𝑋1 − 6𝑥2 + 0𝑆1 + 0𝑆2 + 𝑆3 = 0

VARIABLES DE NO NEGATIVIDAD

X1, X2 ≥ 0

Cj 5 13.5 0 0 0
Xj bn 𝑿𝟏 𝑿𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑
0 𝑺𝟏 320 ½ 2° 1 0 0
0 𝑺𝟐 0 -1 4* 0 1 0
0 𝑺𝟑 0 1 -6° 0 0 1
Zj 0 0 0 0 0 0
Zj - Cj - -5 - 13.5 0 0 0
 𝑿𝟐 𝑺𝟏 𝑺𝟑
0/4 = 0 320 – (0*2) = 320 0 – (0*(-6)) =0
-1/4 = -1/4 ½ - (-1/4*2) = 1 1 – (-1/4*(-6)) = -1/2
4/4 = 1 2 – (1*2) =0 -6 – (1*(-6)) =0
0/4 = 0 1 – (0*2) =1 0 – (0*(-6)) =0
¼ = 1/4 0 – (1/4*2) = -1/2 0 – (1/4*(-6)) = 3/2
0/4 = 0 0 – (0*2) =0 1 – (0*(-6)) =1

Cj 5 13.5 0 0 0
Xj Bn 𝑿𝟏 𝑿𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑
0 𝑺𝟏 320 1* 0 1 -½ 0
13.5 𝒙𝟐 0 -¼° 1 0 ¼ 0
0 𝑺𝟑 0 -½° 0 0 3/2 1
Zj 0 -27/8 13.5 0 27/8 0
Zj – Cj - -67/8 0 0 29/8 0

𝑿𝟐 𝑿𝟏 𝑺𝟑
320/1 = 320 0 – (320*(-1/4)) = 320 0 – (320*(-1/2)) = 160
1/1 = 1 -1/4- (1*(-1/4)) = 1 -1/2 – (1/4*(-1/2)) =0
0/1 =0 1 – (0*(-1/4)) =0 0 – (0*(-1/2)) =0
1/1 =1 0 – (1*(-1/4)) =1 0 – (1*(-1/2)) = 1/2
-½ /1 = -½ 1/4 – (-½*(-1/4)) = -½ 3/2 – (-½*(-1/2)) = 5/4
0/1 =0 0 – (0*(-1/4)) =0 1 – (0*(-1/2)) =1

Cj 5 13.5 0 0 0
Xj bn 𝑿𝟏 𝑿𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑
5 𝒙𝟏 320 1 0 1 -½° 0
13.5 𝒙𝟐 80 0 1 ¼ 1/8 ° 0
0 𝑺𝟑 160 0 0 ½ 5/4 * 1
Zj 2680 5 13.5 67/8 -13/16 0
Zj - Cj - 0 0 67/8 -13/16 0

𝑺𝟐 𝑿𝟏 𝑿𝟐
160/5/4 = 128 320 – (128*(-1/2)) = 384 80 – (128*1/8) = 160
0/5/4 = 0 1- (0*(-1/2)) =1 0 – (0*1/8) =0
0/5/4 =0 0 – (0*(-1/2)) =0 1 – (0*1/8) =0
1/2/5/4 = 2/5 1 – (2/5*(-1/2)) = 6/5 1/4 – (2/5*1/8) = 1/2
5/4 /5/4 = 1 -1/2 – (1*(-1/2)) =0 1/8 – (1*1/8) = 5/4
1/5/4 = 4/5 0 – (4/5*(-1/2)) = 2/5 0 – (4/5*1/8) =1

Cj 5 13.5 0 0 0
Xj bn 𝑿𝟏 𝑿𝟐 𝑺𝟏 𝑺𝟐 𝑺𝟑
5 𝒙𝟏 384 1 0 6/5 0 2/5
13.5 𝒙𝟐 64 0 1 1/5 0 -1
0 𝑺𝟐 128 0 0 2/5 1 4/5
Zj 2784 5 13.5 87/10 0 13/20
Zj – Cj - 0 0 87/10 0 13/20
INTERPRETACIÓN:

La fábrica debe producir 384 sillas y 64 mesas para obtener una utilidad máxima de
$2784.00 dólares.

REFERENCIAS

Método Simplex (2003). Programación lineal.net Recuperado de:

http://www.programacionlineal.net/simplex.html

Método Simplex (2008). Herramientas para el Ingeniero Industrial. Recuperado de

http://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-
industrial/investigaci%C3%B3n-de-operaciones/m%C3%A9todo-simplex/

Collazo. A. (2013). Apuntes Sobre El Método Símplex De Programación Lineal.

Recuperado de http://cicia.uprrp.edu/publicaciones/docentes/metodosimplexdePL.pdf