Método SIMPLEX
Índice:
• Introducción.
• Transición de la Solución Gráfica a la Algebraica.
• Naturaleza iterativa del Método SIMPLEX.
• Detalles de Cálculo del Algoritmo SIMPLEX.
• Ejercicios Prácticos del M.S.
2
Objetivo
Analizar el Método SIMPLEX sobre la base de la
programación lineal, con el objetivo de optimizar la
toma de decisión.
3
INTRODUCCIÓN
• Este popular 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.
• SIMPLEX es considerado como uno de los algoritmos más importantes de
la historia, y hoy por hoy sigue siendo la base en la que se fundamentan la
mayor parte de solucionadores de modelos de programación lineal.
4
INTRODUCCIÓN
El Método SIMPLEX 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 y con una mayor capacidad de análisis de sensibilidad.
5
INTRODUCCIÓN
El Método SIMPLEX es un método iterativo que
permite ir mejorando la solución en cada paso.
La razón matemática de esta mejora radica en
que el método consiste en caminar del vértice de
un poliedro a un vértice vecino de manera que
aumente o disminuya (según el contexto de la
función objetivo, sea maximizar o minimizar).
Dado que el número de vértices que presenta un
poliedro solución es finito, en la medida en que
se pueda satisfacer el conjunto de restricciones,
siempre se hallará como mínimo una solución
óptima.
6
INTRODUCCIÓN
Para el desarrollo de los cálculos con el método SIMPLEX se imponen dos requerimientos a las
restricciones de programación lineal:
1. Todas las restricciones son ecuaciones con lado derecho no negativo.
Para convertir una desigualdad en ecuación se agrega una variable de holgura al lado izquierdo de la restricción.
Ejemplos:
• 𝟔𝟔𝒙𝒙𝟏𝟏 + 𝟒𝟒𝒙𝒙𝟐𝟐 ≤ 𝟐𝟐𝟐𝟐 → 𝟔𝟔𝒙𝒙𝟏𝟏 + 𝟒𝟒𝒙𝒙𝟐𝟐 + 𝒔𝒔𝟏𝟏 = 𝟐𝟐𝟐𝟐, 𝒔𝒔𝟏𝟏 ≥ 𝟎𝟎
• 𝒙𝒙𝟏𝟏 + 𝒙𝒙𝟐𝟐 ≥ 𝟖𝟖𝟖𝟖𝟖𝟖 → 𝒙𝒙𝟏𝟏 + 𝒙𝒙𝟐𝟐 − 𝒔𝒔𝟏𝟏 = 𝟖𝟖𝟖𝟖𝟖𝟖, 𝒔𝒔𝟏𝟏 ≥ 𝟎𝟎
2. Todas las variables son no negativas.
Si el lado derecho resulta negativo, el requerimiento se satisface multiplicando ambos lados de la ecuación por -1.
3. Manejo de variables irrestrictas.
7
TRANSICIÓN DE LA SOLUCIÓN GRÁFICA A LA ALGEBRAICA
8
TRANSICIÓN DE LA SOLUCIÓN GRÁFICA A LA ALGEBRAICA
En todas las PL no triviales, la cantidad de ecuaciones m siempre es menor que la de variables n, por
lo que se obtiene una cantidad infinita de soluciones (siempre que las ecuaciones sean consistentes).
𝒎𝒎 < 𝒏𝒏
9
Ejemplo M.S. 1
10
Ejemplo M.S. 1
11
Ejemplo M.S. 1
14
Ejemplo M.S. 2
RTA:
• 8
• 0
• 3
• 0
• 31
RTA : RTA:
• 4 • 0
• 0 • 2
• 0 • 0
• 0 • 0
• 4 • 4
16
Ejemplo M.S. 2
Variables cero Variables básicas Solución básica Factible Valor de Z RTA:
(X3, X4, S1, S2) (X1, X2) (0, 1/2) SI -2
• 8
(X2, X4, S1, S2) (X1, X3) (8, 3) SI 31 • 0
(X2, X3, S1, S2) (X1, X4) (0, 1/4) SI -3/2 • 3
(X2, X3, X4, S2) (X1, S1) (-1, 3) NO ----- • 0
• 31
(X2, X3, X4, S1) (X1, S2)
(X1, X4, S1, S2) (X2, X3)
(X1, X3, S1, S2) (X2, X4)
(X1, X3, X4, S2) (X2, S1)
(X1, X3, X4, S1) (X2, S2)
(X2, X1, S1, S2) (X3, X4)
(X2, X1, X4, S2) (X3, S1)
(X2, X1, X4, S1) (X3, S2)
(X2, X3, X1, S2) (X4, S1)
(X2, X3, X1, S1) (X4, S2)
(X2, X3, X1, X4) (S1, S2)
17
Ejemplo M.S. 2
RTA : RTA:
• 4 • 0
• 0 • 2
• 0 • 0
• 0 • 0
• 4 • 4
Variables cero Variables básicas Solución básica Factible Valor de Z
(X3, X4) (X1, X2) Infinito NO -----
(X2, X4) (X1, X3) (4, 0) SI 4
(X2, X3) (X1, X4) (4, 0) SI 4
(X1, X4) (X2, X3) (2, 0) SI 4
(X1, X3) (X2, X4) (2, 0) SI 4
(X1, X2) (X3, X4) (-4/7, 16/7) NO -----
18
Ejemplo M.S. 3
21
Ejemplo M.S. 4
Considere la siguiente programación lineal:
𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴 𝒛𝒛 = 𝒙𝒙𝟏𝟏 + 𝟑𝟑𝒙𝒙𝟐𝟐
𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑎𝑎
𝒙𝒙𝟏𝟏 + 𝒙𝒙𝟐𝟐 ≤ 𝟐𝟐
−𝒙𝒙𝟏𝟏 + 𝒙𝒙𝟐𝟐 ≤ 𝟒𝟒
Variables Solución Factible Valor de Z
𝒙𝒙𝟏𝟏 𝑛𝑛𝑛𝑛 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 básicas básica
𝒙𝒙𝟐𝟐 ≥ 𝟎𝟎
X1, X2 -1, 3 Factible 8
X1, X3 -4, 6 Factible -4
a) Determine todas las soluciones factibles básicas
X1, X4 2, 6 Factible 2
del problema.
X2, X3 4, -2 No Factible ----
b) Use la sustitución directa en la función objetivo
X2, X4 2, 2 Factible 6
para determinar la mejor solución básica.
X3, X4 2, 4 Factible 0
c) Resuelva el problema gráficamente, y verifique si la
solución obtenida en (c) es la óptima.
23
Ejemplo M.S. 5
Resuelva el siguiente problema:
25
MÉTODO SIMPLEX
En lugar de enumerar todas las soluciones básicas (puntos de esquina) del
problema de PL (como se hizo en los ejemplos anteriores), el método
simplex investiga sólo “algunas” de estas soluciones.
26
27
NATURALEZA
ITERATIVA DEL
MÉTODO SIMPLEX
La trayectoria del algoritmo simplex se
(𝟐𝟐. 𝟓𝟓, 𝟎𝟎) define como A B C. Cada punto de
esquina a lo largo de la trayectoria está
asociado con una iteración. Es importante
hacer notar que el método simplex se
mueve a lo largo de los bordes del
espacio de soluciones, lo cual significa
que el método no puede cruzarlo, es
decir, irse directamente de A a C.
(𝟎𝟎, 𝟎𝟎)
Ejemplo M.S. 6
Para la figura siguiente, suponga que la función objetivo es:
𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴 𝒛𝒛 = 𝟖𝟖𝒙𝒙𝟏𝟏 + 𝟒𝟒𝒙𝒙𝟐𝟐
Identifique la trayectoria del método simplex.
29
Ejemplo M.S. 7
Considere la figura siguiente. Identifique la trayectoria del método simplex.
31
DETALLES DE CÁLCULO DEL ALGORITMO SIMPLEX
A continuación se explican los detalles de cálculo de una iteración simplex por medio de un ejemplo numérico.
33
Ejemplo M.S. 8
El problema de PL es el siguiente:
34
Ejemplo M.S. 8
La tabla inicial simplex se representa como sigue:
36
Ejemplo M.S. 8
38
Ejemplo M.S. 8
Para seleccionar la variable de entrada se escoge el
coeficiente más negativo de las variables no básicas de la
fila Z de la tabla anterior.
40
Ejemplo M.S. 8
42
Ejemplo M.S. 8
45
Ejemplo M.S. 8
Para seleccionar la variable de entrada se escoge el coeficiente más
negativo de las variables no básicas de la fila Z de la tabla anterior.
Para seleccionar la variable de
salida se elige el valor de la
relación más pequeño, sin tener
en cuenta valores infinitos ni
tampoco cuando el denominador
sea negativo.
47
Ejemplo M.S. 8
Para seleccionar la variable de
salida se elige el valor de la
relación más pequeño, sin tener
en cuenta valores infinitos ni
tampoco cuando el denominador
sea negativo.
48
Ejemplo M.S. 8
La tabla con la solución al problema es cuando en la fila Z no
existen coeficientes de variables no básicas negativas.
51
Observaciones
57
Ejemplo M.S. 9
Considere el siguiente conjunto de restricciones:
Resuelva el problema para cada una de las siguientes funciones objetivo.
58
Ejemplo M.S. 10
61
Ejemplo M.S. 11
62
Ejemplo M.S. 11
Para seleccionar la variable de
Básica Entrante: X1 Solución Relación
salida se elige el valor de la
S1 1 10 10/1=10 relación más pequeño, sin tener
S2 2 6 6/2=3 en cuenta valores infinitos ni
tampoco cuando el denominador
S3 1 6 6/1=6
sea negativo.
Para seleccionar la variable de entrada se escoge el coeficiente más
positivo de las variables no básicas de la fila Z de la tabla anterior.
Básica Z X1 X2 S1 S2 S3 Solución
Z 1 15 -20 0 0 0 0
S1 0 1 2 -1 0 0 10
S2 0 2 -3 0 1 0 6
S3 0 1 1 0 0 -1 6
64
Ejemplo M.S. 11
Básica Z X1 X2 S1 S2 S3 Solución
Z 1 15 -20 0 0 0 0
S1 0 1 2 -1 0 0 10
S2 0 2 -3 0 1 0 6
S3 0 1 1 0 0 -1 6
Básica Entrante: X2 Solución Relación
S1 7/2 7 2
X1 -3/2 3 NO
S3 5/2 3 6/5=1.2
Básica Z X1 X2 S1 S2 S3 Solución
Z 1 0 5/2 0 -15/2 0 -45
S1 0 0 7/2 -1 -1/2 0 7
X1 0 1 -3/2 0 1/2 0 3
S3 0 0 5/2 0 -1/2 -1 3
65
Ejemplo M.S. 11
Básica Z X1 X2 S1 S2 S3 Solución
Z 1 0 5/2 0 -15/2 0 -45
S1 0 0 7/2 -1 -1/2 0 7
X1 0 1 -3/2 0 1/2 0 3
S3 0 0 5/2 0 -1/2 -1 3
Básica Entrante: S3 Solución Relación
S1 7/5 14/5 2
X1 -3/5 6/5 NO
X2 -2/5 6/5 NO
Básica Z X1 X2 S1 S2 S3 Solución
Z 1 0 0 0 -7 1 -48
S1 0 0 0 -1 1/5 7/5 14/5
X1 0 1 0 0 1/5 -3/5 24/5
X2 0 0 1 0 -1/5 -2/5 6/5
66
Ejemplo M.S. 11
Básica Z X1 X2 S1 S2 S3 Solución
Z 1 0 0 0 -7 1 -48
S1 0 0 0 -1 1/5 7/5 14/5
X1 0 1 0 0 1/5 -3/5 24/5
X2 0 0 1 0 -1/5 -2/5 6/5
Básica Entrante: S1 Solución Relación
S3 -5/7 2 NO
X1 -3/7 6 NO
X2 -2/7 2 NO
Básica Z X1 X2 S1 S2 S3 Solución
Z 1 0 0 5/7 -50/7 0 -50
S3 0 0 0 -5/7 1/7 1 2
X1 0 1 0 -3/7 2/7 0 6
X2 0 0 1 -2/7 -1/7 0 2
67
Ejemplo M.S. 12
Considere el siguiente conjunto de restricciones:
𝟓𝟓𝒙𝒙𝟏𝟏 ≤ 𝟒𝟒
𝟔𝟔𝒙𝒙𝟏𝟏 ≤ 𝟖𝟖
𝟑𝟑𝒙𝒙𝟏𝟏 ≤ 𝟑𝟑
𝒙𝒙𝟏𝟏 ≥ 𝟎𝟎
Resuelva el problema para cada una de las siguientes funciones objetivo.
a) 𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴 𝒛𝒛 = 𝒙𝒙𝟏𝟏
b) 𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴 𝒛𝒛 = 𝒙𝒙𝟏𝟏
68
Ejemplo M.S. 13
69
Referencias Bibliográficas
• Hamdy A. Taha. Investigación de operaciones. Novena edición.
• Frederick S. Hillier & Gerald J. Lieberman. Introducción a la investigación de
operaciones. Novena edición.
71
72
