03

Método Simplex Maximización

Investigación de Forma estándar
operaciones en M Sc Ing. Laura Sofía Bazán Díaz

Ingeniería I
Objetivo de aprendizaje 1
Al término de la sesión, el estudiante resuelve problemas de
maximización en su forma estándar, utilizando el método simplex.
 El método simplex implica un procedimiento de cómputo que
Método simplex determina en forma algebraica los puntos esquina. Esto se logra
convirtiendo primero a todas las restricciones de desigualdad en
ecuaciones, para después manipular esas ecuaciones en forma
sistemática.

Una propiedad general del método simplex es que resuelve la

programación lineal en iteraciones. Cada iteración desplaza la
solución a un nuevo punto esquina que tiene potencial de mejorar el
valor de la función objetivo. El proceso termina cuando ya no se
pueden obtener mejoras.

El método simplex implica cálculos tediosos y voluminosos, lo que

hace que la computadora sea una herramienta esencial para resolver
los problemas de programación lineal.
CONVERSIÓN DE En las restricciones (≤), el lado derecho se puede imaginar como
DESIGUALDADES A representando el límite de disponibilidad de un recurso, y en ese
caso el lado izquierdo representaría el uso de ese recurso limitado
ECUACIONES por parte de las actividades (variables) del modelo. La diferencia
entre el lado derecho y el lado izquierdo de la restricción (≤)
representa por consiguiente, la cantidad no usada u HOLGURA del
recurso.
Para convertir una desigualdad (≤) en ecuación, se agrega
una variable de holgura al lado izquierdo de la restricción.

Ej. 6X1 + 4X2 ≤ 24 , se define S1 como la holgura, o cantidad

no usada de M1, la restricción se convierte a:
6X1 + 4X2 + S1 = 24 , S1≥0
CONVERSIÓN DE Una restricción (≥) establece normalmente un límite inferior para las
DESIGUALDADES A actividades del modelo de programación lineal. Como tal, la cantidad
por la que el lado izquierdo es mayor que el límite mínimo (lado
ECUACIONES derecho) representa un EXCEDENTE.

La conversión de (≥) a (=) se logra restando una variable de

excedencia del lado izquierdo de la desigualdad.

Dado M, un valor positivo suficientemente grande (M ∞) como

penalización. Se suma una variable artificial A1 a la parte izquierda.

Ej. X1 + X2 ≥ 800, si se define a S1 como una variable de excedencia

se puede convertir la restricción en la ecuación:

X1 + X2 –S1+ A1 = 800, S1, A1 ≥0

CONVERSIÓN DE El único requisito que queda es que el lado derecho de la ecuación
DESIGUALDADES A que resulte sea no negativo. Esta condición se puede satisfacer
siempre, si es necesario multiplicando ambos lados de la ecuación
ECUACIONES resultante por -1.

Ej. -X1 + X2 ≥ -3 equivale directamente a la ecuación:

-X1 + X2 - S1 +A1= -3 , S1, A1≥0

Ahora se multiplican ambos lados por -1, y se obtiene un lado

derecho no negativo, que es lo que se busca; esto es:

X1 - X2 + S1- A1= 3

Para la restricción (=), con el método de M, un valor positivo

suficientemente grande (M→∞) como penalización. Se suma una
variable artificial A1 a la parte izquierda.
CONVERSIÓN DE Manejo de variables irrestrictas
DESIGUALDADES A Hay casos en los que una variable puede asumir cualquier valor real
ECUACIONES (positivo, cero o negativo).

Ej. 0.25X1 + 0.2X2 + X3 = 200, X3 sin restricciones.

Se transforma de la siguiente manera:

X3 = X3’ - X3’’, donde X3’ , X3’’≥ 0

La restricción se escribiría:

0.25X1 + 0.2X2 + X3’ - X3’’ = 200

FUNCIÓN
OBJETIVO

A la función objetivo inicial Maximizar o Minimizar, se le suman las variables de

holgura y excedencia con coeficiente cero (o) y se le suma o resta las variables
artificiales con M de coeficiente.

Se resta M (-M) en problemas de Maximización y se

suma M (+M) en problemas de Minimización.

 Maximizar Z= 6X1 + 4X2
s.a.
FORMA ESTÁNDAR X1+X2 ≤10
2X1+ X2 ≥ 4
X1, X2 ≥ 0

Forma estándar:
Maximizar Z= 6X1 + 4X2 + 0S1 + 0S2 –MA1
s.a.
X1+X2 +S1=10
2X1+ X2 -S2+A1= 4
X1, X2, S1 ,S2, A1 ≥ 0
 CB VB X1 X2 X3 … Xn XB
TABLERO C1,B X1,B Y1,1 Y1,2 Y1,3 … Y1,n X1,B
EXTENDIDO C2,B X2,B Y2,1 Y2,2 Y2,3 … Y2,n X2,B
… … … … … … … …
Cm,B Xm,B Ym,1 Ym,2 Ym,3 … Ym,n Xm,B
Zj – Cj Z1-C1 Z2-C2 Z3-C3 … Zn-Cn Z
CB : Coeficientes de las variables básicas
VB : Variables básicas
Ym,n : Coeficientes tecnológicos
XB : Solución básica (Variables de disponibilidad)
Zj – Cj : Indicadores de fila (Optimalidad)
Xi :Variables del modelo
Z :valor de la formulación lineal (Función objetivo)
 TABLERO INICIAL 10

(ITERACIÓN 0)
Cj 6 4 0 0 -M

CB VB X1 X2 S1 S2 A1 XB
0 S1 1 1 1 0 0 10
-M A1 2 1 0 -1 1 4
Zj – Cj -2M-6 -M-4 0 M 0 -4M
• Las variables básicas son aquellas cuyos coeficientes
tecnológicos pertenecen a la matriz identidad. En este
caso la matriz identidad está dada por :
1 0
0 1
 TABLERO INICIAL 11

(ITERACIÓN 0)
Cj 6 4 0 0 -M

CB VB X1 X2 S1 S2 A1 XB
0 S1 1 1 1 0 0 10
-M A1 2 1 0 -1 1 4
Zj – Cj -2M-6 -M-4 0 M 0 -4M
1
• Los valores Zj-Cj = (0,-M) -6
2
10
Z= (0,-M) 4
Prueba de optimalidad: Zj-Cj ≥0 ?
• Sí: Solución óptima;
• No: Iterar hasta ubicar la solución óptima.
 TABLERO INICIAL
• VARIABLE ENTRANTE: Se elige el indicador de fila más
negativo y a su variable correspondiente identificando
la variable entrante.

• VARIABLE SALIENTE: Para elegirla se divide el vector

columna XB entre el vector columna de coeficientes
tecnológicos de la variable entrante. Se elige el
mínimo. No se consideran los valores 0 y negativos del
vector columna de la variable entrante.
 TABLERO INICIAL
(ITERACIÓN 0)
Cj 6 4 0 0 -M

CB VB X1 X2 S1 S2 A1 XB
0 S1 1 1 1 0 0 10
Variable
saliente -M A1 2 1 0 -1 1 4
Zj – Cj -2M-6 -M-4 0 M 0 -4M

Variable
entrante

• Variable entrante: Menor valor→ -2M-6, X1

• Variable saliente: Menor división: 10/1=10; 4/2=2 → A1
• PIVOT =2.
 (ITERACIÓN 1)
Cj 6 4 0 0 -M

CB VB X1 X2 S1 S2 A1 XB
0 S1 0 1/2 1 1/2 -1/2 8
6 X1 1 1/2 0 -1/2 1/2 2
Zj – Cj 0 -1 0 -3 3+M 12

• El elemento PIVOT en el tablero siguiente debe ser 1, entonces dividimos los coeficientes
tecnológicos de toda la fila entre 2, y obtenemos: 1, ½, 0, -1/2, ½, 2
• Para el otro valor de la columna del PIVOT buscamos la manera de llegar a cero utilizando
los valores recién hallados y los de la fila anterior, y para alcanzar el cero solo basta
restarlos: 1 , 1 , 1 , 0 , 0 , 10
(-)1 , ½ , 0 , -½, ½ , 2
= 0, ½ , 1 , ½, -½ , 8.
 (ITERACIÓN 1)
Cj 6 4 0 0 -M

CB VB X1 X2 S1 S2 A1 XB
0 S1 0 1/2 1 1/2 -1/2 8
6 X1 1 1/2 0 -1/2 1/2 2
Zj – Cj 0 -1 0 -3 3+M 12
• Variable entrante: Menor valor→ -3, S2
• Variable saliente: Menor división: 8/1 2=16; → S1. No se
consideran valores negativos de la columna.
• Prueba de optimalidad Zj – Cj ≥0? No, seguir iteración.
• PIVOT =1/2.
 (ITERACIÓN 2)
Cj 6 4 0 0 -M

CB VB X1 X2 S1 S2 A1 XB
0 S2 0 1 2 1 -1 16
6 X1 1 1 1 0 0 10
Zj – Cj 0 2 6 0 M 60

• El elemento PIVOT en el tablero siguiente debe ser 1, entonces multiplicamos los

coeficientes tecnológicos de toda la fila por 2, y obtenemos: 0,1,2,1,-1,16.

• Para el otro valor de la columna del PIVOT buscamos la manera de llegar a

cero utilizando los valores recién hallados y los de la fila anterior,y para alcanzar el
cero solo basta multiplicar los valores hallado para la fila S2 por ½= 0, ½,1, ½,-½,8 y
sumarle la fila X1 de la iteración anterior 1, ½,0,-½, ½,2, obtenemos: 1,1,1,0,0,10.
 (ITERACIÓN 2)
18

Cj 6 4 0 0 -M

CB VB X1 X2 S1 S2 A1 XB
0 S2 0 1 2 1 -1 16
6 X1 1 1 1 0 0 10
Zj – Cj 0 2 6 0 M 60

• Prueba de optimalidad: Son Zj – Cj ≥0 ? Sí, se ha hallado

la solución óptima.
X1*=10 X2*=0 S1*=0
S2*=16 A1*=0 Z*=60
➔ X1*=10; S2*=16 y Z*=60.
 VERIFICACIÓN
• Z= F.O. 6X1 + 4X2 + 0S1 + 0S2 –MA1
• 60=6(10) + 4(0) + (0) (0) + (0)(16) – M(0)
• 60 = 60 = Z*
Foro 3: Responder el siguiente enunciado:

De un ejemplo de la vida
real donde se aplique el
objetivo de maximización.
 Laboratorio 03 Ejercicios Método simplex maximización

Revolver los siguientes modelos de PL utilizando el método simplex