Universidad Nacional Autónoma de México

Facultad de Estudios Superiores Acatlán

Actuaría
UNAM Investigación de Operaciones I

Método Simplex

Febrero 2019
 Conjunto convexo
Definición: Un conjunto S es convexo cuando:

∀ X, Y ∈ S y ∀ λ ∈ [ 0,1] se cumple:
λ X + (1− λ ) Y ∈ S

Por tanto, un conjunto es convexo cuando el segmento que une cualquier

par de puntos del conjunto está completamente contenido en el conjunto.

Conjunto no convexo:

1
 Ejemplos de conjuntos convexos

{( x1, x2 ); x12 + x22 ≤ 1}

{ x : Ax = b} donde A es una matriz de n × m y b es un m-vector

{ x : Ax = b, x ≥ 0} donde A es una matriz de n × m y b es un m-vector

{ x : Ax ≤ b, x ≥ 0} donde A es una matriz de n × m y b es un m-vector

+ $ 1 ' $ 1 ' $ −1 ' /

- & ) & ) & ) -
, x : x = λ1 & 0 ) + λ2 & 2 ) + λ3 & 2 ), λ1 + λ2 + λ3 = 1, λ1, λ2 , λ3 ≥ 00
- & 0 ) & 1 ) & −3 ) -
. % ( % ( % ( 1

2
 Puntos extremos
Definición: Un punto x de un conjunto convexo S es
extremo o vértice de S si no puede expresarse como
combinación lineal convexa de otros dos puntos de S.

Para una x perteneciente a un conjunto convexo X, x será un punto

extremo de X si no puede expresarse como una combinación lineal
estricta de dos puntos en X.

x = λ x1 + (1− λ ) x2 con λ ∈ [ 0,1] y ( x1, x2 ) ∈ X es punto extremo de X

si y sólo si:
x = x1 = x2 Extremo

No extremos

3
 Direcciones de un conjunto convexo
Definición: Un rayo es un conjunto convexo de la forma:
x = x 0 + ld; l ³ 0; d ¹ 0
Definición: Una dirección de un conjunto convexo es:
Dado un conjunto convexo, un vector d distinto de cero es una
dirección del conjunto si para cada x 0 en el conjunto, el rayo
{x 0 + λ d; λ ≥ 0} también pertenece al conjunto.

Una dirección extrema, al igual que un punto extremo, es aquella

que no puede expresarse como una combinación lineal positiva de
otras dos direcciones.

d = λ1d1 + λ2 d 2 ; λ1, λ2 > 0

4
 Funciones convexas
Definición: Una función es convexa cuando se cumple:
f ( λ x1 + (1− λ )x2 ) ≤ λ f ( x1 ) + (1− λ ) f ( x2 ) ∀λ ∈ [ 0,1]

Cóncava Convexa Ni cóncava ni convexa

5
 Puntos extremos y optimalidad
Considere el problema de Programación lineal:
Minimizar cx
s.a. Ax=b
x≥0
Sean x1, x2, …, xk los puntos extremos y d1, d2, …, dl las direcciones
extremas del conjunto de restricciones, de modo que Ax=b y x ≥ 0 se
puede expresar como:
Y el problema de programación lineal se
k l
x = å li x i + å µ j d j
i =1 j =1
podrá expresar como sigue:

å (cx )l + å (cd )µ
k k l

ål i =1 Minimizar i i j j
i =1 s.a. i =1 j =1

l ³0 i = 1, 2 , ..., k k

ål =1
i

µ ³0 j
j = 1, 2 , ..., l i =1
i

l ³0
i
i = 1, 2 , ..., k
µ ³0 j
j = 1, 2 , ..., l
6
 Ejemplo 1
Considerar el siguiente conjunto de restricciones:
-x1+ x2 ≤ 2
-x1+2x2 ≤ 6
x1, x2 ≥ 0

Minimizar x1 - 3x2
x3
Minimizar 4x1 - x2

x2
d2

x1 d1

7
 Solución básica factible
Definición: Considérese el sistema Ax=b y x≥0
= Supóngase que el rango (A, b) = rango (A) = m.
A x b
mx1 Después de un posible rearreglo de las columnas
mxn
nx1 de A, sea A = [B, N]:

x ≥
nx1
0
nx1
A

mxn
= B N

mxm mx(n-m)
En donde B es una
matriz invertible.

éxB ù x B = B -1b
El punto x = ê ú , en donde se conoce como solución básica
x
ë Nû xN = 0

Si además xB≥0, entonces x es una solución básica
factible.
nx1
x = xB mx1

Si xB>0, entonces x se llama solución básica factible

xN (n-m)x1
no degenerada.
B se llama matriz básica, N es la matriz no básica;
las componentes de xB son variables básicas y las de
xN son variables no básicas. 8
 Ejemplo 2
Considerar las é1 1ù
1 B = [a1 , a 2 ] = ê0 1ú
siguientes restricciones: ë û
éx ù é1 - 1ù é6ù é3ù é x ù é0 ù
x1+ x2 ≤ 6 X B = ê 1 ú = B -1b = ê úê ú = ê ú XN = ê 3 ú = ê ú
ë x2 û ë0 1 û ë3û ë3û ë x4 û ë0 û
x2 ≤ 3
é1 0ù
x1, x2 ≥ 0 2 B = [a1 , a 4 ] = ê0 1ú
ë û
éx ù é1 0ù é6ù é6ù é x ù é0 ù
X B = ê 1 ú = B -1b = ê úê ú = ê ú XN = ê 2 ú = ê ú
Agregando variables de holgura: ë x4 û ë0 1 û ë 3û ë 3û ë x3 û ë0û
x 1+ x 2 + x 3 =6 é1 1ù
3 B = [a 2 , a 3 ] = ê1 0ú
x2 + x4 = 3 ë û
x 1, x 2, x 3, x 4 ≥ 0 éx ù
X B = ê 2 ú = B -1b = ê
é0 1 ù é6ù é3ù é x ù é0 ù
XN = ê 1 ú = ê ú
x - ú ê3ú = ê3ú
ë 3û ë1 1ûë û ë û ë x4 û ë0 û
La matriz de restricciones es:
é1 1 1 0ù é1 0ù
B = [a 2 , a 4 ] = ê
A = [a1 , a 2 , a 3 , a 4 ] = ê ú
4 ú
ë1 1û
ë0 1 0 1 û
éx ù é 1 0 ù é6 ù é 6 ù é x ù é0 ù
X B = ê 2 ú = B -1b = ê ú ê3ú = ê- 3ú XN = ê 1 ú = ê ú
Opciones de base (2x2): x
ë 4û ë - 1 1 ûë û ë û ë x3 û ë0û
a1 , a 2 é1 0ù
a1 , a 4 5 B = [a 3 , a 4 ] = ê ú
ë0 1 û
a2 , a 3
a2 , a 4 éx ù é1 0ù é6ù é6ù é x ù é0 ù
X B = ê 3 ú = B -1b = ê úê ú = ê ú XN = ê 1 ú = ê ú
a3 , a 4 ë x4 û ë0 1 û ë 3û ë 3û ë x2 û ë0 û 9
 Ejemplo 2…
é 3ù é6 ù é0 ù é0 ù
ê 3ú ê0 ú ê 3ú ê0 ú
Soluciones x1 = ê ú, x 2 = ê ú, x 3 = ê ú, x 5 = ê ú,
ê0 ú ê0 ú ê 3ú ê6 ú
Básicas ê ú ê ú ê ú ê ú
factibles ë0 û ë 3û ë0 û ë 3û

x1=0

x4=0

é3ù
ê3ú x2=0
é0 ù ë û
ê 3ú
ë û

é0 ù é6 ù
ê0 ú ê0 ú
ë û ë û 10
 Ejemplo 3
Considerar las ! 1 1 0 $
# &
siguientes restricciones: B = [ a1, a 2 , a 4 ] = # 0 1 1 &
# 1 2 0 &
x1 + x2 ≤ 6 " %
! x $
x2 ≤ 3 # 1 &
! 2 0 −1 $! 6 $ ! 3 $
# &# & # & ! x $ ! $
x B = # x2 & = B−1b = # −1 0 1 &# 3 & = # 3 & ; xN = #
3
&=# 0 &
x1 + 2x2 ≤ 9 # & # 1 1 −1 &# 9 & # 0 & #" x5 &% " 0 %
#" x4 &% " %" % " %
x1, x2 ≥ 0

Agregando variables de holgura: ! 1 1 1 $

# &
x 1+ x 2 + x 3 =6 B = [ a1, a 2 , a 3 ] = # 0 1 0 &
# 1 2 0 &
x2 + x4 =3 " %
x1+2x2 + x5 = 9 ! x $
# 1 &
! 0 −2 1 $! 6 $ ! 3 $ ! x $ ! $
# &# & # &
x 1, x 2, x 3, x 4 ≥ 0 x B = # x2 & = B−1b = # 0 1 0 &# 3 & = # 3 & ; xN = #
4
&=# 0 &
# & # 1 1 −1 &%#" 9 &% #" 0 &% #" x5 &% " 0 %
La matriz de restricciones es: #" x3 &% "

A = [ a1, a 2 , a 3, a 4 , a 5 ] " x % " %

$ 1 ' $ 3 ' " x % "
0 %
! 1 1 1 0 0 $ B = [ a1, a 2 , a 5 ] ⇒ x B = $ x2 ' = $ 3 ' ; xN = $ 3
' =$ '
# & $ ' $ 0 ' $# x4 '& # 0 &
=# 0 1 0 1 0 & $# x5 '& # &
# 1 2 0 0 1 &
" %
Se tienen soluciones básicas factibles degeneradas,
pues una variable básica es igual a cero
11
 Ejemplo 3…
Se tienen soluciones básicas factibles degeneradas,
pues una variable básica es igual a cero

é3ù
ê3ú
é0 ù ë û
ê 3ú
ë û

é0 ù é6 ù
ê0 ú ê0 ú
ë û ë û

12
 Método Simplex
Problema en forma estándar
Minimizar

=
1xn 1xn 1x(n-m)

c c cB cN
nx1 mx1
x

=
xB
x
Sujeto a: mx1
(n-m)x1
xN
A
x
= b mxn mxm mx(n-m)

A = B N

x ≥ 0
mxn

A =
mx1

a1 a2 … an
… mx1

13
 Método Simplex, pivoteo
Considere el problema de Programación lineal:
Minimizar cx
s.a. Ax=b
x≥0
" −1 %
Sea una solución básica factible $$ B b '' con valor de la función
objetivo z0 dado por: # 0 &

" −1 % " −1 %
z0 = c $$ B b '' = ( c B , c N ) $$ B b '' = c B B−1b
# 0 & # 0 &
Para las variables básicas y no básicas se requiere que: xB≥0, xN≥0
y b=Ax=BxB+NxN. Multiplicamos por B-1 a la izquierda:

xB = B−1b − B−1Nx N
= B−1b − ∑ B−1a j x j
j∈R

= b − ∑ y jxj
j∈R

Donde R es el conjunto de índices de las variables no básicas

14
 Método Simplex, pivoteo…
Sea z el valor de la función objetivo:
z = cx
= cBxB + cN x N
$ '
= c B && B b − ∑ B a j x j )) + ∑ c j x j
−1 −1

% j∈R ( j∈R
= z0 − ∑ ( z j − c j ) x j
j∈R

Donde z j = c B B−1a j x j para cada variable no básica.

El problema se puede reescribir como:
Minimizar z = z0 − ∑ ( z j − c j ) x j
s.a.
j∈R

∑ (y ) xj j + xB = b
j∈R

x j ≥ 0, j ∈ R y x B ≥ 0
Obsérvese que xB juega las veces de variable de holgura, así que
se puede escribir el problema en forma canónica:
15
 Método Simplex, pivoteo…
Minimizar z = z0 − ∑ ( z j − c j ) x j
s.a.
j∈R

∑ (y ) x
j j ≤b
j∈R

x j ≥ 0, j ∈ R

El número de variables no básicas es p=(n-m). Los coeficientes

(cj-zj) son conocidos como precios reducidos y nótese que:

Si ( z j − c j ) ≤ 0 para toda j ∈ R entonces la solución básica factible

es óptima y xj=0 y x B = b .

En caso contrario hacemos (p-1) variables no básicas iguales a

cero e incrementamos la variable remanente xk. Se requiere que
zk-ck sea positivo, inclusive el mayor de todos los z j − c j , j ∈ R .

16
 Método Simplex, pivoteo…
Fijando todos los x j = 0, j ∈ R − {k } se obtiene:

z = z0 − ( zk − ck ) xk
y Si yik≤0, xBi se incrementa al incrementar
xk y se mantiene la no negatividad.
" xB1 % " %
b1 ' " y1k %
$ ' $ $ ' Si yik>0, xBi decrece al incrementar xk
$ xB2 ' $ b2 ' $ y2k ' hasta que xBi se vuelve cero.
$ ' $ ' $ '
$ ! ' $ ! ' $ ! '
= − xk
$ xBr ' $ br ' $ yrk ' br $b '
$ ' $ ' $ ' xk = ≡ Mínimo % ; yik ≥ 0(
i

$ ! ' $ ! ' $ ! ' yrk 1≤i≤m

& yik )
$ xBm ' $$ '
bm '& $# ymk '&
# & #
yik
xBi = bi − br i = 1, 2, ..., m
yrk xr se vuelve cero
b sale de la base y
xk = r xk positiva entra
yrk
en la base
El resto de las xj‘s es cero
17
 Método Simplex, tableau
Partiendo de una solución básica factible

Z xB1 ... xBr ... xBm ... xj ... xk ... L.D.

Z 1 0 0 0 zj − cj zk − ck cB b
xB1 0 1 0 0 y1 j y1k b1
:
xBr 0 0 1 0 yrj yrk br
:
xBm 0 0 0 1 ymj ymk bm
18
 Método Simplex, tableau…
!" = $% &'( a"
Z xB1 ... xBr ... xBm ... xj ... xk ... L.D.
Z 1 0 0 0 zj − cj zk − ck cB b
xB1 0 1 0 0 y1 j y1k b1
:
xBr 0 0 1 0 yrj yrk br
:
xBm 0 0 0 1 ymj ymk bm
-1
yj = B a j b=B b -1
19
 Método
Z x ...Simplex,
x ... x ... tableau…
B1 x Br Bm j

ck − zk yrj
Z 1 0
yrk
0 ( z j − c j ) − ( zk − ck )
yrk
Z xB1 ... xBr ... xBm ... Z xB1x j ... xBr ...... xxBkm ...... L.D.xyj
−y1k
ck − zk xB1 0 1 y 0 y1 j − rj y1k b
rj ckcy−rk zk yyrkrj r
Z 1 0 0 Z( j 1 j ) 0 ( k k )
z − c − z − z −
k 0 k c ( z jB− c j )(−k − c(kz)k − ck )
c b − z
yrk : yrk yrk yrk yrk
−y1k Z xB1 yrj... −y xBr ... xBm ... y
xyyj
xB1 0 1 0 xBk1 0 y1 j 0−1 y1k 11k y01k by11 j−− rj1krj byr1k
yrk yrk ck y−rkrkzk yyyrkrkrjrk
:
Z 1 0
yrk
0 ( z j − c j ) − ( zk − ck )
yrk
:
1 yrj −y1mk1k byyrrjrj
xk 0 0 0 xxBBkm1 0 10 y10rk yymj1 j − y1kmk
yrk yrk yrkrk yyrkyrkrk
: :
−ymk yrj −y1mk y yyrjmkrj
xBm 0 0 1 xxBkm 00ymj −00 ymk y0mk1 bymmj −− byrmk
yrk yrk yyrkrk yyrkrkrk
: 20