MÉTODO SIMPLEX

MÉTODO SIMPLEX
Este método, desarrollado por
George Dantzigen 1947, permite
encontrar la solución óptima de
todo programa lineal, cualquiera
sea el número de variables y el
número de ecuaciones que lo
forman.
MÉTODO SIMPLEX
El algoritmo parte de una solución
básica inicial y a través de
sucesivas iteraciones, explora
.
sistemáticamente los vértices de la
Región Factible del Programa
Lineal hasta identificar la solución
óptima.
 El METODO SIMPLEX tiene en cuenta las siguientes
propiedades de los puntos extremos:
 Existesólo un número finito de puntos extremos
(soluciones básicas).
 Siexiste exactamente una solución óptima, entonces
debe ser una solución de punto extremo (vértice).
.
 Siexisten soluciones óptimas múltiples, entonces al
menos dos de ellas deben ser soluciones básicas en
puntos extremos adyacentes
 Siuna solución en un vértice es igual o mejor que todas
las soluciones en los vértices adyacentes a ella,
entonces es igual o mejor que todas las demás
soluciones en los vértices, es decir, es óptima.
 INSUMO C
3

INSUMO A
1

2
P
INSUMO B Q

O
S
 MÉTODO SIMPLEX
Como hace uso de la
propiedad de que la solución
óptima de un problema de
Programación Lineal (si es que
existe), se encuentra en un B

vértice o frontera de la región

factible, entonces el algoritmo
evalúa uno a uno esos vértices C
D
(adyacente al anterior) hasta A

encontrar el óptimo.
MÉTODO SIMPLEX
Incluye un procedimiento para iniciar
y un criterio para determinar cuando
detenerse.
Cada iteración contiene la solución
.

del sistema de ecuaciones de la que

se parte para obtener una nueva
solución a la que se le aplica la
prueba de optimidad.
PREPARACION PARA EL MÉTODO SIMPLEX

Es indispensable para aplicar el

método, contar con una SOLUCIÓN
BÁSICA INICIAL
El Método Simplex, trabaja únicamente
con restricciones del tipo <= (menor o
igual) y sus términos independientes
mayores o iguales a cero.
PREPARACION PARA EL MÉTODO SIMPLEX
Estandarizar las restricciones, se puede
resolver multiplicando ambos lados de la
restricción por (-1), pero se debe tener en
cuenta que cambia el sentido de la
desigualdad.
Si quedan restricciones del tipo >= o =, será
necesario emplear otros métodos de
resolución derivados del SIMPLEX (GRAN M
o 2 FASES).
PREPARACION PARA EL MÉTODO SIMPLEX

Convertir restricciones de desigualdad en

restricciones de igualdad equivalentes

VARIABLES DE HOLGURA
Problema:
Una empresa elabora dos productos I y II.
En la producción de 1 unidad del producto I se
requieren 10 unidades del insumo A, 8 del B y 20 del C.
En tanto que en una unidad del producto II emplea 9,
25 y 6 unidades de cada insumo respectivamente.
Se disponen diariamente 90 unidades del insumo A,
200 del B y 120 del C.
La utilidad de cada unidad del producto I es $4,50, y
$7,50 la del producto II.
¿Qué cantidad de productos I y II hay que producir
por día para obtener el mayor beneficio posible,
respetando las cantidades límites de cada insumo?
TABLA DE DATOS DEL PROBLEMA
PRODUCTO 1 PRODUCTO 2 Disponibilidad
(unidad) (unidad) diaria
Insumo A 10 9 90
(unidad)
Insumo B 8 25 200
(unidad)
Insumo C 20 6 120
(unidad)
Utilidad
4,5 7,5
($)
PREPARACION PARA EL MÉTODO SIMPLEX
Descripción del modelo
x1 = Cantidad a producir del PRODUCTO I por día
x2 = Cantidad a producir del PRODUCTO II por día
La función objetivo Z : calcula el Beneficio total diario
en la fabricación de PRODUCTO I y II
Max Z= 4,5 x1 + 7,5 x2
Sujeto a:
INSUMO A 10 x1 + 9 x2 <= 90
INSUMO B 8 x1 + 25 x2 <= 200 R. funcionales
INSUMO C 20 x1 + 6 x2 <= 120
x1; x2 >=0  R. de no negatividad
PREPARACION PARA EL MÉTODO SIMPLEX
Convertir las restricciones funcionales de “<=“ en “=“
agregando variables de holgura
Unid. Insumo A 10 x1 + 9 x2 <= 90
10 x1 + 9 x2 + S1 = 90
En donde S1 serán las unidades del INSUMO A no utilizadas
Unid. Insumo B 8 x1 + 25 x2 <= 200
8 x1 + 25 x2 + S2 = 200
En donde S2 serán las unidades del INSUMO B no utilizadas
Unid. Insumo C 20 x1 + 6 x2 <= 120
20 x1 + 6 x2 + S3 = 120
En donde S3 serán las unidades del INSUMO C no utilizadas
Habrá una variable de holgura por cada restricción del tipo <=
PREPARACION PARA EL MÉTODO SIMPLEX
Se incorporan las variables de holgura en la función
objetivo pero con coeficiente cero.
Max Z= 4,5 x1 + 7,5 x2 + 0.S1 + 0.S2 + 0.S3
Las variables de holgura también deben cumplir con
la condición de no negatividad ya que representarán
las cantidades no utilizadas de los diferentes recursos
y nunca podrán ser negativas.
x1; x2 ; S1 ; S2 ; S3 >=0
PREPARACION PARA EL MÉTODO SIMPLEX
Se agrega el resto de las variables de holgura en cada
restricción con coeficiente CERO.
Max Z = 4,5 x1 + 7,5 x2 + 0.S1 + 0.S2 + 0.S3
Unid. Insumo A 10 x1 + 9 x2 + 1S1 + 0.S2 + 0.S3 = 90
Unid. Insumo B 8 x1 + 25 x2 + 0.S1 + 1.S2 + 0.S3 = 200
Unid. Insumo C 20 x1 + 6 x2 + 0.S1 + 0.S2 + 1.S3 = 120
x1; x2 ; S1 ; S2 ; S3 >=0
Esta es la forma requerida para comenzar a aplicar el
MÉTODO SIMPLEX
 Método Simplex
PASO 1: se identifica una solución básica
inicial que sirva de punto de partida

PASO 2 o PASO ITERATIVO: se analiza dicha

solución, si es o no óptima, y si no lo es, a
partir de ella se encuentra una mejor
haciendo un cambio de variables en la base
mediante la aplicación de Gauss Jordan.
PASO 1 PARA ARMAR LA TABLA SIMPLEX…
F.O. MAX Z = 4,5 x1 + 7,5 x2 + 0.S1 + 0.S2 + 0.S3
Unid. Insumo A 10 x1 + 9 x2 + 1.S1 + 0.S2 + 0.S3 = 90
Unid. Insumo B 8 x1 + 25 x2 + 0.S1 + 1.S2 + 0.S3 = 200
Unid. Insumo C 20 x1 + 6 x2 + 0.S1 + 0.S2 + 1.S3 = 120
Para identificar una solución básica inicial, ya
que m<n, cuáles variables deberíamos anular?
Se deben anular x1 y x2, ya que las variables de
holgura conforman una matriz identidad, por lo
que brindan una solución básica inicial
 Recordemos que en una
SOLUCIÓN BÁSICA…
…las variables que se igualan a cero
son denominadas
VARIABLES NO BÁSICAS
…las variables que se utilizan para
resolver el sistema y que generalmente
tienen valor positivo, son denominadas
VARIABLES BÁSICAS
En la SOLUCIÓN BÁSICA
INICIAL del ejemplo:
S1 y S2 y S3 serán
VARIABLES BÁSICAS

x1 y x2 serán
VARIABLES NO BÁSICAS
 ARMANDO LA PRIMERA TABLA
MAX Z = 4,5 x1 + 7,5 x2 + 0.S1 + 0.S2 + 0.S3
(1) 10 x1 + 9 x2 + 1.S1 + 0.S2 + 0.S3 = 90
(2) 8 x1 + 25 x2 + 0.S1 + 1.S2 + 0.S3 = 200
(3) 20 x1 + 6 x2 + 0.S1 + 0.S2 + 1.S3 = 120

Max X1 X2 S1 S2 S3 Las variables

4,5 7,5 0 0 0 b básicas
como
R1 10 9 1 0 0 90 dijimos, serán
R2 8 25 0 1 0 200 S1, S2 y S3
R3 20 6 0 0 1 120
 ARMANDO LA PRIMERA TABLA
Las colocamos en la columna que llamaremos BASE
Vemos que la Solución Básica Inicial es
S1=90, S2=200, S3=120 y las variables no básicas X1 y X2 = 0
Agregamos la
MAX X1 X2 S1 S2 S3 columna Coef,
en donde se
Coef Base 4,5 7,5 0 0 0 b
colocan los
0 S1 10 9 1 0 0 90 coeficientes de
las variables
0 S2 8 25 0 1 0 200 básicas de la
0 S3 20 6 0 0 1 120 F.O. original
Continuamos con el armado de la tabla…
 ARMANDO LA PRIMERA TABLA
A la derecha se agrega la columna que llamamos Gama y
que por ahora está vacía.
Los datos que están en las dos primeras filas, pintadas de
negro, no varían nunca. Es la función objetivo original.

MAX X1 X2 S1 S2 S3 Se agregan
dos filas al
Coef Base 4,5 7,5 0 0 0 b Gama
final, la fila Zj y
0 S1 10 9 1 0 0 90 Cj – Zj
comenzando
0 S2 8 25 0 1 0 200
en la columna
0 S3 20 6 0 0 1 120 Base
Las incorporamos…
 ARMANDO LA PRIMERA TABLA
La fila Z es el resultado de la suma de los productos (fila por fila) de la
columna Coeficiente por los valores de cada columna.
Columna X1 será, 0x10 + 0x8 + 0x20 = 0
Columna X2 será, 0x9 + 0x25 + 0x6 = 0

MAX X1 X2 S1 S2 S3 Y de igual
Coef Base 4,5 7,5 0 0 0 b Gama manera para
todas las
0 S1 10 9 1 0 0 90 columnas de
0 S2 8 25 0 1 0 200 la tabla, salvo
Gama
0 S3 20 6 0 0 1 120
Z 0 0 0 0 0 0
 ARMANDO LA PRIMERA TABLA
Por último la fila Cj – Zj, es el resultado de restar al coeficiente de la
F.O. original el valor de Z que acabamos de calcular.
MAX X1 X2 S1 S2 S3 Cj-Zj mide el
incremento (o
Coef Base 4,5 7,5 0 0 0 b Gama disminución) de
0 S1 10 9 1 0 0 90
la F.O. ante un
aumento
0 S2 8 25 0 1 0 200 (disminución)
unitario en el
0 S3 20 6 0 0 1 120
valor de cada
Z 0 0 0 0 0 0 una de las
variables
Cj-Zj 4,5 7,5 0 0 0
NO básicas.
Cj-Zj incremento neto unitario de Z
 MAX X1 X2 S1 S2 S3
Coef Base 4,5 7,5 0 0 0 b Gama
0 S1 10 9 1 0 0 90
S.B. INICIAL 0 S2 8 25 0 1 0 200
0 S3 20 6 0 0 1 120
Z 0 0 0 0 0 0
Cj-Zj 4,5 7,5 0 0 0
No se produce nada, sobran 90 unid. del
insumo A, 200 unid. del insumo B, 120 unid.
del insumo C, ganancia $0
ANÁLISIS DE LA SOLUCIÓN:

 Si una variable NO BÁSICA cuyo Cj-Zj > 0 (sea

positivo) ingresa a la base, el valor de Z
aumentará.
 Si una variable NO BÁSICA cuyo Cj-Zj < 0 (sea
negativo) ingresa a la base, el valor de Z
disminuirá.
 Si una variable NO BÁSICA que tenga un valor
asociado Cj-Zj = 0 ingresa a la base, el valor de Z
no se modificará.
 Con la tabla lista, en donde
vemos claramente la SB INICIAL
y el valor de Z, podemos
comenzar a operar.
LA PRUEBA DE OPTIMIDAD dice:

MAXIMIZACIÓN, la solución es óptima si

todos los incrementos netos unitarios de Z
Cj-Zj son <= 0

MINIMIZACIÓN, la solución es óptima si

todos los incrementos netos unitarios de Z
Cj-Zj son >= 0
PASO 2: La SB INICIAL es óptima?

MAX X1 X2 S1 S2 S3 No lo es,
Coef Base 4,5 7,5 0 0 0 b Gama ya que
0 S1 10 9 1 0 0 90 todas las
0 S2 8 25 0 1 0 200 Cj-Zj
0 S3 20 6 0 0 1 120
debieran
Z 0 0 0 0 0 0
ser <=0
Cj-Zj 4,5 7,5 0 0 0
 Si la solución no es la
óptima, se debe buscar otra
SB haciendo un cambio de
variables en la base.
DETERMINAR VARIABLE QUE ENTRA A LA BASE:
Maximización: la que tenga mayor
incremento positivo, ya que ésta es la
variable que aumenta más rápidamente
el valor de la F.O.
Minimización: la que tenga mayor
incremento negativo, ya que ésta es la
variable que disminuye más
rápidamente el valor de la F.O.
PASO 2: Qué variable entra a la base?
Será X2, ya que es el Cj-Zj positivo de mayor valor absoluto

COLUMNA PIVOTE Decimos

entonces que
MAX X1 X2 S1 S2 S3 conviene
Coef Base 4,5 7,5 0 0 0 b Gama producir X2,
0 S1 10 9 1 0 0 90 ya que Z se
0 S2 8 25 0 1 0 200 incrementa en
0 S3 20 6 0 0 1 120 $7,5 por cada
Z 0 0 0 0 0 0
unidad
producida.
Cj-Zj 4,5 7,5 0 0 0
¿Cuántas unidades nos gustaría producir?
Todas las que podamos!
¿Qué deberíamos tener en cuenta para determinar
esa cantidad máxima?
No usar más de los recursos que tenemos.
Es decir cuidar que ninguna variable se vuelva
negativa!
Al valor máximo que puede asumir la variable
que se hará básica lo llamamos Gamai
Analicemos cómo calculamos Gama…
¿Hasta cuántas unidades de x2 podemos producir?
MAX X1 X2 S1 S2 S3
Coef Base 4,5 7,5 0 0 0 b Gama Para
0 S1 10 9 1 0 0 90 calcular esa
0 S2 8 25 0 1 0 200 cantidad
0 S3 20 6 0 0 1 120 Gamai
Z 0 0 0 0 0 0
Cj-Zj 4,5 7,5 0 0 0 planteamos:
Según la SB actual
9 * Gama1 <= 90; (90 es el sobrante actual de Insumo A)
25 * Gama2 <= 200; (200 es el sobrante actual de Insumo B)
6 * Gama3 <= 120; (120 es el sobrante actual de Insumo C)
Despejando Gama y reemplazando en la tabla…
Gama1 <= 90/9 <= 10 Como vemos, el único valor de
Gama2 <= 200/25 <= 8 Gamai que verifica el sistema de
Gama3 <= 120/6 <= 20 3 ecuaciones es Gama2 = 8

MAX X1 X2 S1 S2 S3
Coef Base 4,5 7,5 0 0 0 B Gama
0 S1 10 9 1 0 0 90 90/9 = 10
0 S2 8 25 0 1 0 200 200/25 = 8
0 S3 20 6 0 0 1 120 120/6 = 20
Z 0 0 0 0 0 0
Cj-Zj 4,5 7,5 0 0 0
PASO 2: Esto nos determina qué variable
sale de la base?
Es la que tenga menor Gama, es decir el menor cociente entre
su valor (b) en la solución actual y el coeficiente de la variable
que entra, siempre y cuando dicho coeficiente sea
estrictamente positivo. Gama es el
máximo valor
Max X2 X2 S1 S2 S3
que puede
Coef Base 4,5 7,5 0 0 0 b Gama tomar la
0 S1 10 9 1 0 0 90 90/9 = 10 variable
0 S2 8 25 0 1 0 200 200/25 = 8 entrante, sin
0 S3 20 6 0 0 1 120 120/6 = 20 violar las
Z 0 0 0 0 0 0 restricciones de
Cj-Zj 4,5 7,5 0 0 0 no negatividad.
Si todos los coeficientes de la
variable entrante son <= 0 la
SOLUCIÓN es NO ACOTADA
PASO 2: Qué variable sale de la base?
El menor cociente es 8, que corresponde a S2 y será la
variable que sale de la base, esa es la FILA PIVOTE.
La intersección es el ELEMENTO PIVOTE, que en este caso
vale 25
MAX X1 X2 S1 S2 S3
Coef Base 4,5 7,5 0 0 0 b Gama
0 S1 10 9 1 0 0 90 90/9 = 10
0 S2 8 25 0 1 0 200 200/25 = 8
0 S3 20 6 0 0 1 120 120/6 = 20
Z 0 0 0 0 0 0
Cj-Zj 4,5 7,5 0 0 0
 Se debe actualizar la tabla,
mediante operaciones
elementales en filas, es decir
con Gauss Jordan.
 MAX X1 X2 S1 S2 S3
Coef Base 4,5 7,5 0 0 0 b Gama
0 S1 10 9 1 0 0 90 -9 . R2 + R1  R1
0 S2 8 25 0 1 0 200 1/25 . R2  R2
0 S3 20 6 0 0 1 120 -6 . R2 + R3  R3
Z
Cj-Zj Cambiamos la
MAX X1 X2 S1 S2 S3 base,
Coef Base 4,5 7,5 0 0 0 b Gama introduciendo
0 1 -9/25 0 18 X2
0 S1 178/25
1 0 1/25 0 8
7,5 X2 8/25 Actualizamos
0 0 -6/25 1 72
0 S3 452/25 Z y Cj-Zj…
Z
Cj-Zj
 Con la BASE actualizada calculamos Z y Cj-Zj
MAX X1 X2 S1 S2 S3
Coef Base 4,5 7,5 0 0 0 b Gama
0 1 -9/25 0 18
0 S1 178/25
1 0 1/25 0 8
7,5 X2 8/25
0 0 -6/25 1 72
0 S3 452/25
Z 12/5 7,5 0 7,5/25 0 60
Cj-Zj 10,5/5 0 0 -7,5/25 0
Obtuvimos una nueva SB que es S1=18, x2 = 8 y S3 =72, X1 =0 y S2 =0,
significa que se fabricarán 0 unidades del PRODUCTO I y 8
unidades del PRODUCTO II y además sobrarán 18 unid. del Insumo
A y 72 del C, y se consumirá todo el Insumo B, con $60 de gcia
 CRITERIO DE DETENCIÓN
MAXIMIZACIÓN, cuando todas las
Cj-Zj son <= 0
MINIMIZACIÓN, cuando todas las
Cj-Zj son >= 0
Para alguna variable no básica que
pueda entrar a la base, se verifica que si
todos los coeficientes de su columna son
<=0, el “problema es no acotado”
 MAX X1 X2 S1 S2 S3

Coef Base 4,5 7,5 0 0 0 b Gama

0 1 -9/25 0 18
0 S1 178/25
1 0 1/25 0 8
7,5 X2 8/25
0 0 -6/25 1 72
0 S3 452/25

Z 12/5 7,5 0 7,5/25 0 60

Cj-Zj 10,5/5 0 0 -7,5/25 0

Vemos que no llegamos al óptimo ya que

hay un Cj-Zj>=0
X1 ingresa a la base, calculamos Gama…
 Calculamos Gama…
MAX X1 X2 S1 S2 S3

Coef Base 4,5 7,5 0 0 0 b Gama

0 1 -9/25 0 18
0 S1 178/25 18/(178/25) = 2,52
1 0 1/25 0 8
7,5 X2 8/25 8/(8/25) = 25
0 0 -6/25 1 72
0 S3 452/25 72/(452/25) = 158,40

Cj-Zj
El menor Gama positivo es 2,52
S1 será la variable que sale de la base
El elemento pivote es 178/25
Aplicamos Gauss Jordan.
 MAX X1 X2 S1 S2 S3
Coef Base 4,57,5 0 0 0 b Gama
0 S1 178/25 0 1 -9/25 0 18 (25/178) . R1  R1
7,5 X2 8/25 1 0 1/25 0 8 -8/25 . R1 + R2  R2
0 S3 452/25 0 0 -6/25 1 72 -452/25 . R1 + R3  R3
Z
Cj-Zj Cambiamos la
base,
MAX X1 X2 S1 S2 S3
introduciendo
Coef Base 4,5 7,5 0 0 0 b Gama X1
4,5 X1 1 0 25/178 -9/178 0 225/89
7,5 X2 0 1 -4/89 5/89 0 640/89
Actualizamos
0 S3 0 0 -226/89 60/89 1 2340/89
Z
Z y Cj-Zj…
Cj-Zj
 Con la BASE actualizada, calculamos Z y Cj-Zj
MAX X1 X2 S1 S2 S3
Coef Base 4,5 7,5 0 0 0 b Gama
0 25/178 -9/178 0 225/89
4,5 X1 1
1 -4/89 5/89 0 640/89
7,5 X2 0
0 -226/89 60/89 1 2340/89
0 S3 0
Z 4,5 7,5 52,5/178 34,5/178 0 5812,5/89
Cj-Zj 0 0 -52,5/178 -34,5/178 0
Llegamos al óptimo?
SI, ya que se cumple que
todos los Cj-Zj<=0
 MAX X1 X2 S1 S2 S3
Coef Base 4,5 7,5 0 0 0 b Gama
4,5 X1 1 0 25/178 -9/178 0 225/89
7,5 X2 0 1 -4/89 5/89 0 640/89
0 S3 0 0 -226/89 60/89 1 2340/89
Z 4,5 7,5 52,5/178 34,5/178 0 5812,5/89

Cj-Zj 0 0 -52,5/178 -34,5/178 0

Esta solución significa que produciendo

SOLUCIÓN OPTIMA
Z= 5812,5/89=65,31 2,53 unidades del PRODUCTO I
x1 = 225/89=2,53 7,19 unidades del PRODUCTO II
x2 = 640/89=7,19
S1 = 0 Queda un sobrante de 26,30 unid. del
S2 = 0 INSUMO C, mientras que no sobra nada de
S3 =2340/89=26,30 los INSUMOS A y B
Se obtiene un máximo beneficio de $ 65,31
 METODO SIMPLEX
Tipo Cambio en Cambio en Función Objetivo
Restricción restricción Maximización Minimización
<= (+ 1Si) Z = Z0riginal + [Link] Z = Z0riginal + [Link]
VARIABLE QUE ENTRA A El valor más positivo de El valor más negativo de
LA BASE la fila Cj-Zj la fila Cj-Zj

El óptimo se encuentra El óptimo se encuentra

PRUEBA DE cuando en la fila Cj-Zj cuando en la fila Cj-Zj ya
ya no quedan elementos no quedan elementos
OPTIMALIDAD positivos negativos
(CRITERIO DE Para cualquier variable no básica que pueda entrar
DETENCIÓN) a la base, si se verifica que todos los coeficientes
de su columna son <=0, entonces el PROBLEMA es