Facultad de Ciencias.

Universidad de Zaragoza

Programación Lineal
2021-2022

Pedro Mateo
mateo@[Link]

4 de octubre de 2021
 Contenido I
1

Introducción

Formulación de un problema de programación lineal (PPL)

Resolución gráfica de PPL de 2 variables

Conceptos básicos y teoremas fundamentales

El algoritmo del Simplex

Inicialización.
Prueba de optimalidad.
Selección de variable que entra en la base.
Selección de variable que abandona la base
Aplicación del algoritmo simplex
Finalización del algoritmo del simplex
Modificación del algoritmo para el problema de mı́nimo.
Finitud del simplex.

Cálculo de SFB iniciales

Pedro Mateo | Programación Lineal
 Introducción
2

Programación Lineal
1. Las variables de decisión implicadas en el problema son no negativas.
2. El criterio de selección, Función Objetivo, función lineal de las
variables.
3. Las reglas de funcionamiento del sistema pueden expresarse como un
conjunto de igualdades o desigualdades lineales.
4. Los valores de las variables de decisión que verifican estas
desigualdades se denominan Soluciones Factibles del problema.
5. La región de R n asociada a los puntos factibles del problema se
denomina Región de Factibilidad del problema.

Pedro Mateo | Programación Lineal

 Introducción
3

Programación Lineal
Las condiciones anteriores implican:
I Proporcionalidad: La contribución de cada actividad al valor que
mide el logro del criterio establecido es proporcional al nivel que se
asigna a dicha actividad.
I Aditividad: Cada función en un modelo de programación lineal, tanto
la que representa el criterio como las que representan el
funcionamiento del sistema, se obtienen como la suma de las
contribuciones individuales por parte de cada una de las actividades.
I Divisibilidad: En un principio, las variables de decisión en un modelo
de programación lineal pueden tomar cualquier valor no negativo.
I Certeza: Se supone que los valores asociados a cada parámetro de
un problema de programación lineal son constantes conocidas.

Pedro Mateo | Programación Lineal

 Introducción
4

Programación Lineal
Programación Lineal es una técnica muy utilizada:
1. Gran cantidad de problemas pueden aproximarse mediante un
modelado lineal (campo militar, económico, industrial, social, etc).
2. Existen técnicas eficientes para la resolución de estos modelos.
3. La facilidad que presentan para la realización de estudios de variación
de los parámetros del problema sin abandonar el ámbito lineal.

Pedro Mateo | Programación Lineal

 Introducción
5

Programación Lineal. Ejemplo

I Una taller artesanal se dedica a la fabricación de sillas y de mesas,
para dicha elaboración dispone de dos materias primas, roble y pino
y de un departamento en el que se realiza el montaje.
I Semanalmente se dispone de 150 unidades de roble y 100 unidades
de pino y se puede trabajar a lo sumo 80 horas en la fabricación de
las mesas y sillas.
I Se sabe que cada mesa consume 5 unidades de roble, 2 de pino y 4
horas de trabajo, y cada silla consume 2 unidades de roble y 3 de
pino, y necesita 2 horas de proceso.
I La venta de las mesas y sillas proporcionan un beneficio neto de 12 y
8 unidades monetarias, respectivamente.
I ¿Plantear un problema que permita determinar el número de mesas
y sillas que hay que elaborar con objeto de maximizar el beneficio
del taller?

Pedro Mateo | Programación Lineal

 Introducción
6

Programación Lineal. Ejemplo

I Definimos las variables del problema, x1 número de mesas y x2
número de sillas a elaborara .
I Determinamos la función objetivo, maximizar el beneficio acumulado
por la venta de las mesas y sillas elaboradas:
máx Z = 12x1 + 8x2 .
I Definimos las restricciones,
I Disponibilidad de Roble −→ 5x1 + 2x2 ≤ 150.
I Disponibilidad de Pino −→ 2x1 + 3x2 ≤ 100.
I Disponibilidad de horas de trabajo −→ 4x1 + 2x2 ≤ 80.
I Número de unidades no negativo −→ x1 ≥ 0, x2 ≥ 0.
a Aunque no sea correcto nos olvidamos del hecho de que las sillas y las mesas

deban ser cantidades enteras y trabajamos con variables reales.

Pedro Mateo | Programación Lineal

 Formulación de un problema de programación lineal
7

Forma general


 Maximizar (Minimizar) Z (x1 , . . . , xn ) = c1 x1 + c2 x2 + · · · + cn xn



 sujeto a:



 a11 x1 + a12 x2 + · · · + a1n xn (=, ≤, ≥) b1


a21 x1 + a22 x2 + · · · + a2n xn (=, ≤, ≥) b2

 ..

 .





 am1 x1 + am2 x2 + · · · + amn xn (=, ≤, ≥) bm


xj ≥ 0, j = 1, . . . , n

Pedro Mateo | Programación Lineal

 Formulación de un problema de programación lineal
8

Forma estándar de un PPL



 Maximizar Z (x1 , . . . , xn ) = c1 x1 + c2 x2 + · · · + cn xn



 s.a:



 a11 x1 + a12 x2 + · · · + a1n xn = b1


a21 x1 + a22 x2 + · · · + a2n xn = b2 (1)

 ..

 .





 a m1 x1 + am2 x2 + · · · + amn xn = bm


xj ≥ 0, j = 1, . . . , n

Forma matricial de un PPL estándar



 máx Z = cx
s. a: Ax = b (2)


x≥0
Pedro Mateo | Programación Lineal
 Formulación de un problema de programación lineal
9

Notaciones para forma matricial

I c = (c1 , c2 , . . . , cn ) Vector de costosa .
I x0 = (x1 , x2 , . . . , xn ) Vector de variables de decisión.
I b0 = (b1 , b2 , . . . , bm ) Vector de recursos.
 
a11 a12 . . . a1n
 a21 a22 . . . a2n 
I A=  ..

 Matriz de coeficientes tecnológicos
 ... ... . ... 
am1 am2 . . . amn
a Se define por comodidad como un vector fila.

Pedro Mateo | Programación Lineal

 Formulación de un problema de programación lineal
10

Transformación a forma estándar

I Si el problema es de mı́nimo: máx Z ≡ mı́n (−Z ).
I Si existe xj ≤ 0. Definir x̄i = −xi , y sustituir.
 

máx Z = x1 + x2 
máx Z = x1 − x̄2
s.a: x1 + 3x2 ≥ 5 =⇒ s.a: x1 − 3x̄2 ≥ 5

 

x1 ≥ 0, x2 ≤ 0 x1 ≥ 0, x̄2 ≥ 0

I Si xi ∈ R, no restringida. xi = xi1 − xi2 con xi1 ≥ 0, xi2 ≥ 0 y sustituir.

 

máx Z = x1 + x2 
máx Z = x1 + x11 − x12
s.a: x1 + 3x2 ≤ 5 =⇒ s.a: x1 + 3x11 − 3x12 ≤ 5

 

x1 ≥ 0, x2 ∈ R x1 ≥ 0, x11 ≥ 0, x12 ≥ 0

Pedro Mateo | Programación Lineal

 Formulación de un problema de programación lineal
11

Transformación a forma estándar

Para cada restricción de desigualdad se define xn+1 ≥ 0 con cn+1 = 0
Variable de Holgura y:
I Si ai1 x1 + ai2 x2 + · · · + ain xn ≤ bi ,
transformamos la restricción anterior en

ai1 x1 + ai2 x2 + · · · + ain xn + xn+1 = bi .

donde xn+1 absorbe sin costo la holgura existente entre

ai1 x1 + ai2 x2 + · · · + ain xn y bi .
I Si ai1 x1 + ai2 x2 + · · · + ain xn ≥ bi ,
xn+1 ≥ 0 se introduce absorbiendo el exceso respecto a bi .

ai1 x1 + ai2 x2 + · · · + ain xn − xn+1 = bi .

En ambos casos en la función objetivo xn+1 aparece con coeficiente cero.

Pedro Mateo | Programación Lineal

 Formulación de un problema de programación lineal
12

Transformación a forma estándar. Ejemplo

El problema de las mesas y las sillas en forma estándar queda:


máx Z = 12x1 + 8x2 +0x3 + 0x4 + 0x5



s.a: 5x1 + 2x2 +x3 =150

2x1 + 3x2 +x4 =100



 4x1 + 2x2 +x5 =80


 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0.

Pedro Mateo | Programación Lineal

 Resolución gráfica de PPL de 2 variables
13

Sólo para problemas con dos variables de decisión.

Ejemplo
x2
z=300


máx Z = 12x1 + 8x2
(5,30)



s.a: 5x1 + 2x2 ≤ 150

2x1 + 3x2 ≤ 100



 4x1 + 2x2 ≤ 80


 x1 ≥ 0, x2 ≥ 0.
x1

z=0 z=120

Pedro Mateo | Programación Lineal

 Resolución gráfica de PPL de 2 variables
14

Solución óptima única

x2


mı́n Z = 40x1 + 36x2



 x1 ≤ 8
 s.a:
x2 ≤ 10



 5x1 + 3x2 ≥ 45
z=380


 x1 ≥ 0, x2 ≥ 0
(8,5/3) z=680

x1

Pedro Mateo | Programación Lineal

 Resolución gráfica de PPL de 2 variables
15

Solución múltiple
x2


(0,6) 
máx Z = 3x1 + 2x2

s.a: 6x1 + 4x2 ≤ 24

 10x1 + 3x2 ≤ 30


x1 ≥ 0, x2 ≥ 0
(24/11,30/11)

x1
Z=6 Z=12
Z=0

Pedro Mateo | Programación Lineal

 Resolución gráfica de PPL de 2 variables
16

Problema no acotado
x2



máx Z = 2x1 + 3x2

s.a:
Z=20
x1 + x2 ≥ 3

 x1 − 2x2 ≤ 4


x1 ≥ 0, x2 ≥ 0

x1

Z=12

Pedro Mateo | Programación Lineal

 Resolución gráfica de PPL de 2 variables
17

Problema no factible
x2



máx Z = 4x1 + 3x2



 x1 + x2 ≤ 3
s.a:
2x1 − x2 ≤ 3



 x1 ≥ 4


 x1 ≥ 0, x2 ≥ 0

x1

Pedro Mateo | Programación Lineal

 Condiciones de optimalidad en PL
18

Teorema 1 (Condiciones de optimalidad en PL)

Considerar el PPL en forma estándar


 máx Z = cx
s. a: Ax = b


x≥0

suponer que la región de factibilidad {Ax = b, x ≥ 0} es no vacı́a y sean

x1 , x2 , . . . , xk y d1 , d2 , . . . , dl sus puntos extremos y direcciones extremas
(si existen).
Una condición necesaria y suficiente para que exista una solución óptima
finita del problema es que
cdj ≤ 0, j = 1, . . . , l.
En este caso existe un punto extremo que es solución óptima del
problema.
Pedro Mateo | Programación Lineal
 Condiciones de optimalidad en PL
19

Ejemplo
Resolver:
 

 máx Z = 15x1 + 10x2 
máx Z = 15x1 + 10x2

 


 2x1 + x2 ≤ 1500 

s.a: s.a: 2x1 + x2 + x3 = 1500
x1 + x2 ≤ 1200 =⇒ x1 + x2 + x4 = 1200

 


 x1 ≤ 500 
 x1 + x5 = 500

 

 x1 , x2 ≥ 0  x1 , x2 , x3 , x4 , x5 ≥ 0



máx Z = 3x1 + 4x2



 x1 + x2 ≤ 7
 s.a:
6x1 + 8x2 ≤ 48 =⇒



 −x1 + 4x2 ≤ 8


 x1 , x2 ≥ 0.
Pedro Mateo | Programación Lineal
 El algoritmo del Simplex
20

Simplex
I El método del simplex es un procedimiento sistemático para resolver
PPL moviéndose desde un punto extremo a otro con una mejora (o
al menos no empeoramiento) de la función objetivo.
I El algoritmo calcula puntos extremos cumpliendo lo anterior hasta
que se alcanza el punto extremo óptimo o hasta que se detecta una
dirección extrema de no acotación (con cd > 0).
I Consideraremos inicialmente el PPL en la forma


 máx Z = cx
s. a: Ax = b


x≥0

Suponiendo que al menos existe un punto en la región de factibilidad

y además el rango de A es igual a m, el número de filas (m < n).

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
21

Definición 2
Solución factible, cualquier punto x verificando Ax = b, x ≥ 0.

Definición 3
Solución básica, SB, es cualquier punto verificando Ax = b en el cual al
menos n − m variables toman valor 0 y cuyas columnas en A son
linealmente independientes.

Definición 4
Solución factible básica, SFB, es una solución básica verificando las
condiciones de no negatividad. Es decir una solución básica que además
es solución factible.

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
22

Definición 5
Base, colección de variables con valor no obligatoriamente nulo en un
cierto orden que forman una SB/SFB. Las variables de ésta se denominan
variables básicas.

Definición 6
SFB no degenerada, es una SFB que tiene exactamente m valores no
nulos, y es degenerada en caso contrario.

Definición 7
Una SB/SFB x es adyacente a otra SB/SFB y si coinciden todas las
variables de la base excepto una.

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
23

Ejemplo


máx Z = 15x1 + 10x2




s.a: 2x1 + x2 + x3 = 1500
x1 + x2 + x4 = 1200



 x1 + x5 = 500


 xi ≥ 0, i = 1, . . . , 5

I x4 = x5 = 0 =⇒ x1 = 500 x2 = 700 x3 = −200 SB. Base (x1 , x2 , x3 )

I x1 = x2 = 0 =⇒ x3 = 1500 x4 = 1200 x5 = 500 SFB. Base (x3 , x4 , x5 )
I x2 = x5 = 0 =⇒ x1 = 500 x3 = 500 x4 = 700 SFB. Base (x1 , x3 , x4 )
I Etc.
Todas son no degeneradas. Además (x3 , x4 , x5 ) y (x1 , x3 , x4 ) son bases
adyacentes.

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
24

Etapas
1. Inicialización.
2. Prueba de optimalidad.
3. Paso de una SFB a otra SFB:
3.1 Selección de una variable para la nueva SFB.
3.2 Selección de una variable de la antigua SFB para que abandone la
base.
3.3 Operación de cambio de base.

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Inicialización. 25

Inicialización
I Para iniciar el algoritmo es necesario una SFB inicial que será
siempre un punto extremo.
I Dicha SFB debe ser tal que su matriz B asociada sea la matriz
identidada . Por ejemplo, problemas en los que se ha introducido una
variable de holgura sumando en cada una de sus restricciones.
Dado el problema


máx Z = −x1 + 3x2

 s.a: −x1 + 2x2 + x3 = 6

 x1 + x2 + x4 = 5


xj ≥ 0, j = 1, . . . , 4
SFB inicial, x1 = x2 = 0, x3 = 6 y x4 = 5, B = I2 y la base es (x3 , x4 ).
a El caso en el que no existe de forma directa una matriz B igual a la identidad se

pospone.

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Prueba de optimalidad
26

Prueba de optimalidad
Sea x̄ el punto extremo actual (SFB), sea A = [B, N] entonces
   −1 
x̄ B b
x̄ = B =
x̄N 0

con B −1 b ≥ 0. El valor de la función objetivo es

cx̄ = cB x̄B + cN x̄N = cB B −1 b + cN 0 = cB B −1 b.

Base= (x1 , . . . , xm ) con ı́ndices J = {1, . . . , m}.

Ejemplo
     
−1 2
1 0 x x
A= , x̄B = 3 , x̄N = 1 , J = {3, 4},
0 11 1    x4 x2
−1 −1 6 6
x̄B = B b = I2 = .
5 5
Pedro Mateo | Programación Lineal
 El algoritmo del Simplex
Prueba de optimalidad
27

Prueba de optimalidad
Sea x una solución factible cualquiera:
 
x
x = B y Ax = BxB + NxN = b ⇒ xB = B −1 b − B −1 NxN
xN
El valor de la función objetivo en x:

cx =cB xB + cN xN = cB (B −1 b − B −1 NxN ) + cN xN =
cB B −1 b + (cN − cB B −1 N)xN = cx̄ + (cN − cB B −1 N)xN

Resumiendo

cx = cx̄ + (cN − cB B −1 N)xN = cx̄ + ∑ (cj − cB B −1 Aj )xj

j6∈J

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Prueba de optimalidad
28

Prueba de optimalidad
Dado x̄ SFB actual y x una solución factible cualquiera tenemos:

cx = cx̄ + ∑ (cj − cB B −1 Aj )xj

j6∈J

I Si cj − cB B −1 Aj ≤ 0 ∀j 6∈ J como xN ≥ 0 entonces

cx ≤ cx̄
y por tanto x̄ es la solución óptima del problema.
I Si cj − cB B −1 Aj > 0 para uno o más j 6∈ J . Si somos capaces de
construir x a partir de x̄ haciendo que una o más de las variables
asociadas a estas componentes j tomen valor positivo entonces:

cx = cx̄ + ∑ (cj − cB B −1 Aj )xj > cx̄

j6∈J
y por tanto la solución x será mejor que x̄.
Pedro Mateo | Programación Lineal
 El algoritmo del Simplex
Prueba de optimalidad
29

Ejemplo
   
I J = {3, 4}, xB = x3 , xN = x1 .
x4 x2
I cB = (0, 0), cN = (−1, 3).
   
I N = −1 2 , B = 1 0 .
1 1 0 1
 −1  
−1
I cN − cB B N = (−1, 3) − (0, 0) 1 0 −1 2
= (−1, 3) no
0 1 1 1
son ambas menores o iguales que cero, por tanto la SFB actual no
es óptima.
I Si podemos construir otra solución factible en la que x2 > 0 será
mejor que la actual.

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Selección de variable que entra en la base
30

Selección de variable que entra en la base

I Existen j 6∈ J tales que

cj − cB B −1 Aj > 0

sean j1 , . . . , jr sus ı́ndices.

I El algoritmo del simplex pasa de una SFB x̄ a otra SFB
ADYACENTE, x. Tendrán las mismas variables básicas excepto una.
I Seleccionamos xjh , h = 1, . . . , r para entrar en la nueva BASE.

xjs tal que cjs − cB B −1 Ajs = máxj =j1 ,...,jr {cj − cB B −1 Aj },

Se selecciona la variable no básica que tiene una mayor incremento

por unidad de variable.

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Selección de variable que entra en la base
31

Definición 8
Dada una SFB con x̄ = (x̄B , x̄N )0 = (B −1 b, 0)0 las cantidades
cj − cB B −1 Aj se denominan costos marginales (reducidos, relativos)
asociados a las variables xj y representan la cantidad en la que la FO
varı́a por cada una unidad que tome la variable xj .
La cantidad cB B −1 Aj se denota mediante zj , con lo que los costos
marginales toman la forma cj − zj .

Observación
Los costos marginales de las variables básicas son cero siempre.

Ejemplo
En nuestro ejemplo la única variable en la que cj − zj > 0 es x2 ,
c2 − z2 = 3, por tanto x2 deberá tomar valor. La nueva base será (x2 , x4 )
o (x3 , x2 ) (SFB adyacentes). Construirlas y comprobarlas!
Pedro Mateo | Programación Lineal
 El algoritmo del Simplex
Selección de variable que abandona la base
32

Selección de variable que abandona la base

I Tenemos x̄ SFB no óptima y xj0 con j0 6∈ J con cj0 − zj0 > 0.
I Construimos x ¿SFB adyacente a? x̄, con xj0 = λ :
   −1   
xB B b − B −1 NxN x̄ − B −1 Aj0 λ
x= = = B =
xN xN x̄N + λ ej0
 
−B −1 Aj0
=x̄ + λ = x̄ + λ dj0 = x.
ej0

con ej0 = (0, . . . , 1, . . . , 0)0 (1 en la posición j0 -ésima)

I Observad que
 
−B −1 Aj0
Adj0 = [B, N] = −BB −1 Aj0 + Aj0 = 0
ej0
y por tanto el nueveo x cumple Ax = b.
I ¿Es x ≥ 0? Esto determinará quien abandona la base.
Pedro Mateo | Programación Lineal
 El algoritmo del Simplex
Selección de variable que abandona la base
33

Selección de variable que abandona la base

Observar que si λ > 0 =⇒ xj0 = λ > 0. Se plantean dos situaciones:
1. Si B −1 Aj0 ≤ 0 entonces −B −1 Aj0 ≥ 0 y λ (−B −1 Aj0 ) ≥ 0 ∀λ ≥ 0. Y
x es factible ∀λ ≥ 0. ¿Qué pasa con dj0 ?
2. Si B −1 Aj0 6≤ 0
 −1 
B b + λ (−B −1 Aj0 )
¿x = ≥ 0?,
λ ej0

hay que elegir λ de manera x ≥ 0.

3. Usamos la siguiente notación

0
0
B −1 b = b̄ = b̄1 , . . . , b̄m B −1 Aj0 = Yj0 = y1j0 , . . . , ymj0

4. Ası́:  
b̄ − λ Yj0
x=
λ ej0
Pedro Mateo | Programación Lineal
 El algoritmo del Simplex
Selección de variable que abandona la base
34

Selección de variable que abandona la base

I Componente a componente:  
b̄1 − λ y1j0
 : 
 
b̄m − λ ymj 
   0
b̄ − λ Yj0  0 
x= =



λ ej0  : 
 λ 
 
 : 
0
I Para que x ≥ 0 basta con que b̄i − λ yij0 ≥ 0, i = 1, . . . , m.
b̄i
Equivalentemente basta con λ ≤ yij0 ∀i tal que yij0 > 0.
I Cómo xj0 = λ tomamos el mayor λ posible: (¿Por qué?)
 
b̄s b̄i
λ= = mı́n1≤i≤m |yij > 0 , (3)
ysj0 yij0 0
Pedro Mateo | Programación Lineal
 El algoritmo del Simplex
Selección de variable que abandona la base
35

Selección de variable que abandona la base

I x queda:
 
b̄1 − yb̄s y1j0 >0
sj0
 
 :  :
 
 b̄s − b̄s ysj  xs = 0
 ysj0 0 
 
 :  :
 
b̄m − yb̄s ymj0  >0
x= sj0 
 0 
  0
 : 
  :
 b̄s 
  xj0 > 0
 ysj0 
 :  :
0 0
I x es una SFB adyacente a x̄, en la que xj0 sustituye a xs en la base.

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Selección de variable que abandona la base
36

Ejemplo
I Base inicial (x3 , x4 ), x̄ = (x̄3 , x̄4 , x̄1 , x̄2 )0 = (6, 5, 0, 0)0 , B = I 2 ,
c1 − cB B −1 A1 = −1 y c2 − cB B −1 A2 = 3 con lo que j0 = 2, entra x2
en la nueva SFB.

0
B −1 A2 = A2 = 2 1
     
6 −2 6 − 2λ
5 −1  5 − λ 
x = x̄ + λ dj0 =     
0 + λ  0  =  0 


0 1 λ

I x ≥ 0 ⇒ λ ∈ [0, 3]. Tomando λ = 3 se obtiene:

   
x3 0
x4  2
x =   
x1  = 0 Base (x2 , x4 ) adyacente a (x3 , x4 )
x2 3
Pedro Mateo | Programación Lineal
 El algoritmo del Simplex
Selección de variable que abandona la base
37

Ejemplo
I Como j0 = 2, Y2 = B −1 A2 = (2, 1)0 > 0, B −1 b = (6, 5)0 la
expresión (3) queda:
 
b̄i
λ = mı́n1≤i≤2 |yi2 > 0
yi2
6 5
λ = 3 = mı́n{ , } = 3
2 1
I Sale de la base la variable que define el valor de λ , la primera de la
base, x3 . ¿Orden?
I Se pasa de la base (x3 , x4 ) a (x2 , x4 ). x = (x2 , x4 , x1 , x3 )0 :
     
2 0 −1 1 x2 x
A= , x̄B = , x̄N = 1 , J = {2, 4},
1 1 1 0 x4 x3
   −1    
2 0 2 0 6 3
B= x̄B = B −1 b = = , xN = 0.
1 1 1 1 5 2

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Selección de variable que abandona la base
38

Resumen
I xj0 entra en nueva base, sale xs en la que se alcanza el mı́nimo:
 
b̄s b̄i
λ= = mı́n1≤i≤m |yij0 > 0 ,
ysj0 yij0
b̄s
Nuevo punto es x = x̄ + λ dj0 y xj0 = λ = ysj0 .
I El VFO en x es:
 
j0 −B −1 Aj0
cx = cx̄ + c(λ d ) =cx̄ + λ (cB , cN ) =
ej0
cx̄ + xj0 (−cB B −1 Aj0 + cj0 )

I Si B −1 Aj0 ≤ 0, x factible para λ ∈ (0, ∞) ⇒ Problema No Acotado

VFO → ∞. dj0 es una dirección extrema de no acotación.
I Observad B −1 Aj0 ≤ 0 ⇒ yij0 ≤ 0 i = 1, . . . , m, no se puede calcular λ .

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Aplicación del algoritmo simplex
39

Tablas para algoritmo simplex

Toda la información necesaria para realizar los cálculos anteriores se
almacena en:

c1 c2 . . . cn
x1 x2 . . . xn
       
c1 x1 y11 .. yn1 b̄1
 c2   x2   y12 .. 
yn2   b̄2 
      
cB = .  xB = .  Y = B −1 A = ..  b̄ = B −1 b =  . 
 ..   ..   .   .. 
cm xm y1m .. ynm b̄m
c − cB B −1 A

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Aplicación del algoritmo simplex
40

Organigrama
Algoritmo
Simplex

Cálculo de SFB
inicial

cj − cB B −1 Aj ≤ 0 Fin
Solución
Óptima
Selecciona j0 que
Cálculo de SFB
maximiza
Adyacente
cj − cB B −1Aj

Yj0 = B −1Aj0 ≤ 0 Fin

Problema no
Acotado
Seleccionar i que
minimiza

b̄i /Yij0 |Yij0 > 0

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Aplicación del algoritmo simplex
41

Ejemplo. Mesas y sillas



máx Z = 12x1 + 8x2 + 0x3 + 0x4 + 0x5



s.a: 5x1 + 2x2 + x3 = 150

2x1 + 3x2 + x4 = 100



 4x1 + 2x2 + x5 = 80


 xj ≥ 0, j = 1, . . . , 5

12 8 0 0 0
x1 x2 x3 x4 x5 b̄
0 x3 5 2 1 0 0 150
0 x4 2 3 0 1 0 100
0 x5 4 2 0 0 1 80
12 8 0 0 0 6≤ 0

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Aplicación del algoritmo simplex
42

Ejemplo. Mesas y sillas

12 8 0 0 0
x1 x2 x3 x4 x5 b̄
0 x3 5 2 1 0 0 150
0 x4 2 3 0 1 0 100
0 x5 4 2 0 0 1 80
12 8 0 0 0 6≤ 0

x1 x2 x3 x4 x5 b̄
0 x3 0 -1/2 1 0 -5/4 50
0 x4 0 2 0 1 -1/2 60
12 x1 1 1/2 0 0 1/4 20
240 0 2 0 0 -3 6≤ 0

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Aplicación del algoritmo simplex
43

Ejemplo. Mesas y sillas

x1 x2 x3 x4 x5 b̄
0 x3 0 -1/2 1 0 -5/4 50
0 x4 0 2 0 1 -1/2 60
12 x1 1 1/2 0 0 1/4 20
240 0 2 0 0 -3 6≤ 0

x1 x2 x3 x4 x5 b̄
0 x3 0 0 1 1/4 -11/8 65
8 x2 0 1 0 1/2 -1/4 30
12 x1 1 0 0 -1/4 3/8 5
300 0 0 0 -1 -5/2 ≤0

Se elaboran 5 mesas y 30 sillas, el beneficio 12 × 5 + 8 × 30 = 300u.m. se

gasta toda la materia prima excepto 65 unidades de Roble.

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Aplicación del algoritmo simplex
44

Observaciones
x1 x2 x3 x4 x5 b̄
0 x3 0 0 1 1/4 -11/8 65
8 x2 0 1 0 1/2 -1/4 30
12 x1 1 0 0 -1/4 3/8 5
300 0 0 0 -1 -5/2 ≤0

I Observar que las variables básicas siempre tienen columnas unitarias.

I Calcular la matriz B −1 correspondiente a la base final:
   
1 2 5 1 1/4 −11/8
B = 0 3 2 B −1 = 0 1/2 −1/4 
0 2 4 0 −1/4 3/8

B −1 correspondiente a la base actual coincide con las columnas de la

base inicial en dicha tabla.
Pedro Mateo | Programación Lineal
 El algoritmo del Simplex
Aplicación del algoritmo simplex
45

Ejemplo


má Z = 15x1 + 10x2




 s.a: 2x1 + x2 + x3 = 1500
x1 + x2 + x4 = 1200



 x1 + x5 = 500


 xj ≥ 0, j = 1, . . . , 5
Tabla inicial:
15 10 0 0 0
0 x3 2 1 1 0 0 1500
0 x4 1 1 0 1 0 1200
0 x5 1 0 0 0 1 500
15 10 0 0 0

Entra x1 sale x5 .
Pedro Mateo | Programación Lineal
 El algoritmo del Simplex
Aplicación del algoritmo simplex
46

Ejemplo
0 x3 0 1 1 0 -2 500
0 x4 0 1 0 1 -1 700
15 x1 1 0 0 0 1 500
0 10 0 0 -15

Entra x2 sale x3 .

10 x2 0 1 1 0 -2 500
0 x4 0 0 -1 1 1 200
15 x1 1 0 0 0 1 500
0 0 -10 0 5

Entra x5 sale x4 .

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Aplicación del algoritmo simplex
47

Ejemplo
10 x2 0 1 -1 2 0 900
0 x5 0 0 -1 1 1 200
15 x1 1 0 1 -1 0 300
0 0 -5 -5 0
Solución óptima, x1 = 300, x2 = 200, VFO = 13500
(x3 = x4 = 0, x5 = 500).

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Finalización del algoritmo del simplex
48

Finalización del algoritmo del simplex

1. Solución óptima única, ∀j no básico se cumple que cj − zj < 0.
2. Solución no acotada, existe j no básico cumpliendo que cj − zj > 0 y
tal que Yj ≤ 0, ya comentamos que en este caso podı́amos construir
una solución de la forma x = x̄ + λ (−B −1 Aj0 , ej0 )0 que era factible
∀λ y cuya función objetivo tendı́a a ∞ cuando λ → ∞.
3. Múltiples soluciones, existe j no básico cumpliendo que cj − zj = 0,
por lo parte teórica vista sabemos que esta variable puede entrar en
la base dando lugar a otra SFB de igual valor. Además cualquier
punto que pertenezca a la combinación lineal convexa de las dos
soluciones será un punto factible de igual valor. (demostración:
ejercicio)

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Finalización del algoritmo del simplex
49

Solución óptima única



máx Z = 5x1 + 10x2



 2x1 + x2 ≤ 500
 s.a:
2x1 + 5x2 ≤ 1000



 2x1 + 3x2 ≤ 900


 x1 , x2 ≥ 0

5 x1 1 0 5/8 -1/8 0 187.5

10 x2 0 1 -1/4 1/4 0 125
0 x5 0 0 -1/2 -1/2 1 150
0 0 -5/8 -15/8 0

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Finalización del algoritmo del simplex
50

Solución óptima múltiple



máx Z = 4x1 + 10x2



 2x1 + x2 ≤ 500
 s.a:
2x1 + 5x2 ≤ 1000



 2x1 + 3x2 ≤ 900


 x1 , x2 ≥ 0

0 x3 8/5 0 1 -1/5 0 300

10 x2 2/5 1 0 1/5 0 200
0 x5 4/5 0 0 -3/5 1 300
0 0 0 -2 0
VFO= 2000

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Finalización del algoritmo del simplex
51

Solución óptima múltiple

0 x3 8/5 0 1 -1/5 0 300
10 x2 2/5 1 0 1/5 0 200
0 x5 4/5 0 0 -3/5 1 300
0 0 0 -2 0

4 x1 1 0 5/8 -1/8 0 187.5

10 x2 0 1 -1/4 1/4 0 125
0 x5 0 0 -1/2 -1/2 1 150
0 0 0 -2 0

x1 = (0, 200, 300, 0, 300)0 y x2 = (187,5, 125, 0, 0, 150)0

x = λ x1 + (1 − λ )x2 = ((1 − λ )187,5, 75λ + 125, 300λ , 0, 150λ + 150)
Ax = (500, 1000, 900)0 y cx = 2000 ∀λ ∈ (0, 1).

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Finalización del algoritmo del simplex
52

Problema no acotado


máx Z = x1 + 2x2

s.a: −x1 + x2 ≤ 4

 −2x1 + 3x2 ≤ 13


x1 , x2 ≥ 0

0 x3 -1 1 1 0 4 2 x2 -1 1 1 0 4
0 x4 -2 3 0 1 13 0 x4 1 0 -3 1 1
1 2 0 0 3 0 -2 0

2 x2 0 1 -2 1 5
1 x1 1 0 -3 1 1
0 0 7 -3

Entrarı́a x3 pero Y3 = (−2, −3)0 ≤ 0.

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Finalización del algoritmo del simplex
53

Problema no acotado
I Construimos:
 
−B −1 Aj0
x = x̄ + λ ,λ ≥0
ej0
       
x1 1 3 1 + 3λ
x2  5    
  =   + λ 2 = 5 + 2λ  ≥ 0,
x3  0 1  λ 
x4 0 0 0

I −x1 + x2 = −1 − 3λ + 5 + 2λ = 4 − λ ≤ 4 ∀λ ≥ 0
I −2x1 + 3x2 = −2 − 6λ + 15 + 6λ = 13 ∀λ ≥ 0
I VFO = 11 + 7λ → ∞ si λ → ∞.

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Modificación del algoritmo para el problema de mı́nimo.
54

Problema de mı́nimo
I Optimalidad: cj − cB B −1 Aj = cj − zj ≥ 0, ∀j 6∈ J .
I Entrará en la nueva base: xj0 tal que
cj0 − zj0 = mı́n{cj − zj |cj − zj < 0}.
I Saldrá de la base: Igual que para máximo (es un criterio de
factibilidad).
I Finalización:
I cj − zj > 0 para todo j no básica, solución óptima única.
I cj − zj ≥ 0 para todo j no básica y existe alguna variable no básica
con cj − zj = 0, entonces tenemos solución óptima múltiple, se
procede de la misma forma que en el caso de máximo.
I cj − zj < 0 para algún j no básico y Yj ≤ 0, problema no acotado, se
procede de la misma forma que en el caso de máximo.

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Modificación del algoritmo para el problema de mı́nimo.
55

Ejemplo


mı́n Z = −2x1 + x2 − x3



s.a: 3x1 + x2 + x3 ≤ 6

x1 − x2 + 2x3 ≤ 1



 x1 + x2 − x3 ≤ 2


 xj ≥ 0, j = 1, . . . , 3

-2 1 -1 0 0 0
0 x4 3 1 1 1 0 0 6
0 x5 1 -1 2 0 1 0 1
0 x6 1 1 -1 0 0 1 2
-2 1 -1 0 0 0

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Modificación del algoritmo para el problema de mı́nimo.
56

Ejemplo
Entra x1 sale x5 .
0 x4 0 4 -5 1 -3 0 3
-2 x1 1 -1 2 0 1 0 1
0 x6 0 2 -3 0 -1 1 1
0 -1 3 0 2 0
Entra x2 sale x6 .
0 x4 0 0 1 1 -1 -2 1
-2 x1 1 0 1/2 0 1/2 1/2 3/2
1 x2 0 1 -3/2 0 -1/2 1/2 1/2
0 0 3/2 0 3/2 1/2

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Finitud del simplex.
57

Finitud del simplex

I Si en cada iteración B −1 b > 0 (no existe degeneración) entonces el
valor de la función objetivo se mejora estrictamente y el nuevo punto
tiene que ser distinto del anterior, como el número de puntos
extremos es finito el algoritmo del simplex finalizará.
I Si existen SFB degeneradas (variables básicas con valor nulo) el
algoritmo puede funcionar peor (hacerse menos eficiente) e incluso
no converger.
0 0 0 2 0 3/2 máx
0 x1 1 0 0 1 -1 0 2→
0 x2 0 1 0 2 0 1 4→
0 x3 0 0 1 1 1 1 3
0 0 0 2 0 3/2 Z =0

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Finitud del simplex.
58

Finitud del simplex. Perdida de eficiencia.

Entra x4 sale x1 . Entra x5 sale x2 .
2 x4 1 0 0 1 -1 0 2 2 x4 0 1/2 0 1 0 1/2 2
0 x2 -2 1 0 0 2 1 0 0 x5 -1 1/2 0 0 1 1/2 0
0 x3 -1 0 1 0 2 1 1 0 x3 1 -1 1 0 0 0 1
-2 0 0 0 2 3/2 4 0 -1 0 0 0 1/2 4

Entra x6 sale x5 . Entra x1 sale x3 .

2 x4 1 0 0 1 -1 0 2 2 x4 0 1 -1 1 -1 0 1
3/2 x6 -2 1 0 0 2 1 0 3/2 x6 0 -1 2 0 2 1 2
0 x3 1 -1 1 0 0 0 1 0 x1 1 -1 1 0 0 0 1
1 -3/2 0 0 -1 0 4 0 -1/2 -1 0 -1 0 5

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Finitud del simplex.
59

No convergencia por existencia de ciclos.



máx Z = 3/4x1 − 20x2 + 1/2x3 − 6x4



 1/4x1 − 8x2 − x3 + 9x4 ≤ 0
s.a:
1/2x1 − 12x2 − 1/2x3 + 3x4 ≤ 0



 x3 ≤ 1


 x≥0

x1 x2 x3 x4 x5 x6 x7
x5 1/4 -8 -1 9 1 0 0 0
x6 1/2 -12 -1/2 3 0 1 0 0
x7 0 0 1 0 0 0 1 1
3/4 -20 1/2 -6 0 0 0

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Finitud del simplex.
60

No convergencia por existencia de ciclos.

x1 x2 x3 x4 x5 x6 x7 x1 x2 x3 x4 x5 x6 x7
x1 1 -32 -4 36 4 0 0 0 x1 1 0 8 -84 -12 8 0 0
x6 0 4 3/2 -15 -2 1 0 0 x2 0 1 3/8 -15/4 -1/2 1/4 0 0
x7 0 0 1 0 0 0 1 1 x7 0 0 1 0 0 0 1 1
0 4 7/2 -33 -3 0 0 0 0 2 -18 -1 -1 0

x1 x2 x3 x4 x5 x6 x7 x1 x2 x3 x4 x5 x6 x7
x3 1/8 0 1 -21/2 -3/2 1 0 0 x3 -5/2 56 1 0 2 -6 0 0
x2 -3/64 1 0 3/16 1/16 -1/8 0 0 x4 -1/4 16/3 0 1 1/3 -2/3 0 0
x7 -1/8 0 0 21/2 3/2 -1 1 1 x7 5/2 -56 0 0 -2 6 1 1
-1/4 0 0 3 2 -3 0 1/2 -16 0 0 1 -1 0

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Finitud del simplex.
61

No convergencia por existencia de ciclos.

x1 x2 x3 x4 x5 x6 x7 x1 x2 x3 x4 x5 x6 x7
x5 -5/4 28 1/2 0 1 -3 0 0 x5 1/4 -8 -1 9 1 0 0 0
x4 1/6 -4 -1/6 1 0 1/3 0 0 x6 1/2 -12 -1/2 3 0 1 0 0
x7 0 0 1 0 0 0 1 1 x7 0 0 1 0 0 0 1 1
7/4 -44 -1/2 0 0 2 0 3/4 -20 1/2 -6 0 0 0

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Finitud del simplex.
62

Herramientas para evitar ciclos.

I Regla de Bland: Seleccionar para entrar la variable con
cj − zj > 0(máx) con menor ı́ndice j. Si hay empate en el criterio de
salida seleccionar también la de menor ı́ndice.
I Técnica lexicográfica/perturbaciones.

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Construcción de SFB iniciales. 63

Construcción de SFB iniciales.

¿Qué hacer cuando no podemos construir una matriz B = I n de forma
automática?
Si no existen variables cuyas columnas forman I n las creamos. Estas se
denominan Variables Artificiales.


 mı́n Z = x1 − 2x2 

  s.a: x1 + x2 − x3 = 2

 

s.a: x1 + x2 ≥ 2  −x1 + x2 − x4 = 1
−x1 + x2 ≥ 1

 
 x2 + x5 = 3

 x2 ≤ 3 


 x≥0
 x≥0

 s.a: x1 + x2 − x3 + a1 = 2

1 1 −1 0 0   −x1 + x2 − x4 + a2 = 1
A = −1 1 0 −1 0
 x2 + x5 = 3
0 1 0 0 1  

x ≥ 0, a1 ≥ 0, a2 ≥ 0
Pedro Mateo | Programación Lineal
 El algoritmo del Simplex
Construcción de SFB iniciales. 64

Construcción de SFB iniciales.

I Método de la Gran M.
I Método de las Dos Fases.
El Método de la Gran M, asigna a la variables artificiales un coeficiente
en la función objetivo muy malo. Si el problema es de máximo caj = −M
y si es de mı́nimo caj = M donde M es una cantidad positiva mayor que
cualquier valor que aparezca en el proceso de resolución.


 mı́n Z = x1 − 2x2 + Ma1 + Ma2



 x1 + x2 − x3 + a1 = 2
s. a:
−x1 + x2 − x4 + a2 = 1



 x2 + x5 = 3


 x ≥ 0, a1 ≥ 0, a2 ≥ 0
Se aplica el algoritmo del simplex teniendo en cuenta que M es mayor
que cualquier número o expresión en la tabla.
Pedro Mateo | Programación Lineal
 El algoritmo del Simplex
Construcción de SFB iniciales. 65

Método de Gran M.
1 -2 0 0 0 M M
x1 x2 x3 x4 x5 a1 a2
M a1 1 1 -1 0 0 1 0 2
M a2 -1 1 0 -1 0 0 1 1
0 x5 0 1 0 0 1 0 0 3
1 -2 0 0 0 0 0
-2M M M

1 -2 0 0 0 M M
x1 x2 x3 x4 x5 a1 a2
M a1 2 0 -1 1 0 1 -1 1
-2 x2 -1 1 0 -1 0 0 1 1
0 x5 1 0 0 1 1 0 -1 2
-1 0 0 -2 0 0 2
-2M 0 M -M 0 0 2M
Pedro Mateo | Programación Lineal
 El algoritmo del Simplex
Construcción de SFB iniciales. 66

Método de Gran M.
1 -2 0 0 0 M M
x1 x2 x3 x4 x5 a1 a2
1 x1 1 0 -1/2 1/2 0 1/2 -1/2 1/2
-2 x2 0 1 -1/2 -1/2 0 1/2 1/2 3/2
0 x5 0 0 1/2 1/2 1 -1/2 -1/2 3/2
0 0 -1/2 -3/2 0 1/2 3/2
M M

Esta tabla constituye una SFB inicial para el problema original (no el
artificial). Si no se necesita la información de las columnas de las
variables artificiales, éstas pueden eliminarse de la tabla.

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Construcción de SFB iniciales. 67

Método de Gran M.
1 -2 0 0 0 M M
x1 x2 x3 x4 x5 a1 a2
0 x4 2 0 -1 1 0 1 -1 1
-2 x2 1 1 -1 0 0 1 0 2
0 x5 -1 0 1 0 1 -1 0 1
3 0 -2 0 0 2 0
M M

1 -2 0 0 0 M M
x1 x2 x3 x4 x5 a1 a2
0 x4 1 0 0 1 1 0 -1 2
-2 x2 0 1 0 0 1 0 0 3
0 x3 -1 0 1 0 1 -1 0 1
1 0 0 0 2 M M

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Construcción de SFB iniciales. 68

Método de la dos fases.

En una primera fase hace cero los costos de las variables reales del
problema, cj = 0∀j y asigna costo 1 a las variables artificiales, caj = 1∀j.
Entonces se aplica el simplex para resuolver el problema de mı́nimo en el
que se trata de minimizar la suma de las variables artificiales.


 mı́n Z = a1 + a2



 x1 + x2 − x3 + a1 = 2
s. a:
−x1 + x2 − x4 + a2 = 1



 x2 + x5 = 3


 x ≥ 0, a1 ≥ 0, a2 ≥ 0

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Construcción de SFB iniciales. 69

Método de la dos fases.

0 0 0 0 0 1 1
x1 x2 x3 x4 x5 a1 a2
1 a1 1 1 -1 0 0 1 0 2
1 a2 -1 1 0 -1 0 0 1 1
0 x5 0 1 0 0 1 0 0 3
0 -2 1 1 0 0 0

0 0 0 0 0 1 1
x1 x2 x3 x4 x5 a1 a2
1 a1 2 0 -1 1 0 1 -1 1
0 x2 -1 1 0 -1 0 0 1 1
0 x5 1 0 0 1 1 0 -1 2
-2 0 1 -1 0 0 2

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Construcción de SFB iniciales. 70

Método de la dos fases.

0 0 0 0 0 1 1
x1 x2 x3 x4 x5 a1 a2
0 x1 1 0 -1/2 1/2 0 1/2 -1/2 1/2
0 x2 0 1 -1/2 -1/2 0 1/2 1/2 3/2
0 x5 0 0 1/2 1/2 1 -1/2 -1/2 3/2
0 0 0 0 0 0 0

Esta tabla constituye una SFB inicial para el problema original (no el
artificial). Las columnas de las variables artificiales se eliminan, se
introducen los costos originales y se recalculan los costos marginales.

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Construcción de SFB iniciales. 71

Método de la dos fases.

1 -2 0 0 0
x1 x2 x3 x4 x5
1 x1 1 0 -1/2 1/2 0 1/2
-2 x2 0 1 -1/2 -1/2 0 3/2
0 x5 0 0 1/2 1/2 1 3/2
0 0 -1/2 -3/2 0

1 -2 0 0 0
x1 x2 x3 x4 x5
0 x4 2 0 -1 1 0 1
-2 x2 1 1 -1 0 0 2
0 x5 -1 0 1 0 1 1
3 0 -2 0 0

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Construcción de SFB iniciales. 72

Método de la dos fases.

1 -2 0 0 0
x1 x2 x3 x4 x5
0 x4 1 0 0 1 1 2
-2 x2 0 1 0 0 1 3
0 x3 -1 0 1 0 1 1
1 0 0 0 2

Nota sobre factibilidad.

En cualquiera de los dos métodos si el algoritmo del simplex detecta una
solución óptima en la que alguna de las variables artificiales es básica,
tomando un valor estrictamente positivo, entonces el problema que se
trata de resolver es No Factible.

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Construcción de SFB iniciales. 73

Construcción de SFB iniciales. Ejemplo de problema no factible

 

máx Z = 4x1 + 3x2 
mı́n Z̄ = a1

 


s.a: x1 + x2 ≤ 3 

 s.a: x1 + x2 + x3 = 3
2x1 − x2 ≤ 3 ⇒ 2x1 − x2 + x4 = 3

 


 x1 ≥ 4 
 x1 − x5 + a1 = 4

 

 x1 ≥ 0, x2 ≥ 0  x ≥ 0, a1 ≥ 0

0 0 0 0 0 1 0 0 0 0 0 1
x1 x2 x3 x4 x5 a1 x1 x2 x3 x4 x5 a1
x3 1 1 1 0 0 0 3 x3 0 3/2 1 -1/2 0 0 3/2
x4 2 -1 0 1 0 0 3 x1 1 -1/2 0 1/2 0 0 3/2
a1 1 0 0 0 -1 1 4 a1 0 1/2 0 -1/2 -1 1 5/2
-1 0 0 0 1 0 0 -1/2 0 1/2 1 0

Pedro Mateo | Programación Lineal

 El algoritmo del Simplex
Construcción de SFB iniciales. 74

Construcción de SFB iniciales. Ejemplo de problema no factible



mı́n Z̄ = a1



s.a: x1 + x2 + x3 = 3

2x1 − x2 + x4 = 3



 x1 − x5 + a1 = 4


 x ≥ 0, a1 ≥ 0

0 0 0 0 0 1
x1 x2 x3 x4 x5 a1
x2 0 1 2/3 -1/3 0 0 1
x1 1 0 1/3 1/3 0 0 2
a1 0 0 -1/3 -1/3 -1 1 2
0 0 1/3 1/3 1 0
x1 + x2 ≤ 3 y x1 ≥ 4 son incompatibles.

Pedro Mateo | Programación Lineal

 Aplicación teorema condiciones de optimalidad en PL
75

Columnas Pto. extremo VFO Columnas Pto. extremo VFO

1. (3, 4, 5) (0, 0, 1500, 1200, 500) 0 2. (1, 3, 4) (500, 0, 500, 700, 0) 7500
3. (1, 2, 4) (500, 500, 0, 200, 0) 12500 4. (1, 2, 5) (300, 900, 0, 0, 200) 13500
5. (2, 3, 5) (0, 1200, 300, 0, 500) 12000
   
1 0 0 1500
1. B = 0 1 0 = B −1 =⇒ xB = B −1 b = 1200 ≥ 0
0 0 1 500
     
2 1 0 0 0 1 500
2. B = 1 0 1 B −1 = 1 0 −2 =⇒ xB = B −1 b = 500 ≥ 0
1 0 0 0 1 −1 700
     
2 1 0 0 0 1 500
3. B = 1 1 1  −1
B = 1  0 −2 =⇒ xB = B b = 500 ≥ 0
 −1 
1 0 0 −1 1 −1 200
     
2 1 0 1 −1 0 300
4. B = 1 1 0  −1
B = −1  2 0 =⇒ xB = B b = 900 ≥ 0
 −1 
1 0 1 −1 1 1 200
     
1 1 0 0 1 0 1200
5. B = 1 0 0 B −1 = 1 −1 0 =⇒ xB = B −1 b =  300  ≥ 0
0 0 1 0 0 1 500
6. . . . (el resto o no son factibles B −1 b 6≥ 0 o 6 ∃B −1 )

Pedro Mateo | Programación Lineal