Tema 2:

Optimizacin lineal
Ezequiel Lpez Rubio
Departamento de Lenguajes y
Ciencias de la Computacin
Universidad de Mlaga

Sumario
El

modelo de programacin lineal

Formulacin de modelos
Mtodo grfico
Mtodo del simplex

Casos anmalos
Mtodo de las dos fases

Dualidad

El modelo de
programacin lineal

Introduccin

Definicin: Se dice que una funcin f: RnR es lineal sii

para algn conjunto de constantes {c1,c2,...,cn} se tiene
que:
f x1 , x 2 ,..., x n c1 x1 c2 x 2 ... cn x n
Ejemplos: f(x,y)=x2y es lineal, pero f(x,y)=x2+2y no es
lineal.
Definicin: Sea f: RnR una funcin lineal, y bR una
constante. Entonces se dice que las desigualdades
f(x1,...,xn)b, f(x1,...,xn)b, son desigualdades lineales, y
que la igualdad f(x1,...,xn)=b es una igualdad lineal. En
general nos referiremos a las tres con el nombre de
restricciones lineales

Concepto de problema de
programacin lineal

Definicin: Un problema de programacin lineal es

un problema de optimizacin en el que:

Se debe maximizar (o minimizar) una funcin lineal de las

variables de decisin que se llama funcin objetivo
Los valores de las variables deben satisfacer un conjunto
de restricciones lineales

Frecuentemente nos encontraremos que en el

problema de programacin lineal aparecen tambin
restricciones de signo para las variables, del tipo
xi0. En realidad estas restricciones son un tipo de
restricciones lineales.

Forma general de un problema

de programacin lineal

La forma ms general de un problema de

programacin lineal ser:
Maximizar (o minimizar) c1 x1 ... cn x n
Sujeto a :
a11 x1 ... a1n x n ~ b1
...
am1 x1 ... amn xn ~ bm
x1 ,..., xn 0 (que pueden aparecer o no)

donde el smbolo ~ puede denotar a , o =.

Forma matricial

A los coeficientes de la funcin objetivo (ci) se les llama

costes. A los trminos independientes de las
restricciones (bi), recursos. A los elementos de la matriz
de coeficientes que define las restricciones (aij),
coeficientes tcnicos. Para simplificar la notacin, si
llamamos c al vector de costes, b al vector de recursos,
y A a la matriz de coeficientes tcnicos, podemos
escribir el problema en la llamada forma
T matricial:
Maximizar (o minimizar) c x

Sujeto a :
Ax ~ b
x 0 (puede aparecer o no)

Regin factible

Mientras no se indique lo contrario, consideraremos que

las restricciones del tipo xi0 se incluyen (si aparecen en
el problema) dentro del conjunto de restricciones Ax ~ b,
con lo cual el problema quedara:
Maximizar (o minimizar) cT x

Sujeto a Ax ~ b
Definicin: Dado un problema de programacin lineal,
llamaremos regin factible del problema y la
denotaremos por S al conjunto de puntos que cumplen
todas las restricciones del problema, es decir:
S {x R n | Ax ~ b}

Soluciones ptimas

Definicin: Dado un problema de programacin lineal,

diremos que un punto x0S es una solucin ptima sii
se cumple que f(x0)f(x) xS (para el caso de
minimizar) o bien f(x0)f(x) xS (para el caso de
maximizar). En tal caso, a f(x0) se le llamar valor
ptimo de la funcin objetivo.
Si existe una sola solucin ptima, diremos que el
problema tiene solucin nica. Si no existe solucin
ptima, pero S, diremos que el problema tiene
solucin ilimitada. Si S=, diremos que el problema no
tiene solucin.

Formulacin de
modelos

Introduccin
Cuando

se desea resolver un problema del

mundo real, se formula en primer lugar un
modelo
Un modelo es una simplificacin de la
realidad que se intenta que sea lo
suficientemente exacta como para poder
extraer de l conclusiones tiles
En particular nos interesan los modelos
cuantitativos, en los que la realidad es
modelada mediante nmeros

Modelos cuantitativos

En los modelos cuantitativos para problemas de

optimizacin intervienen:

Variables de decisin, cuyos valores numricos

finales nos proporcionan la solucin
La funcin objetivo, que es una cantidad que se
desea maximizar (beneficio, rendimiento, etc.) o
minimizar (coste, tiempo,...). En el caso de minimizar
costes, hay que tener en cuenta que los costos fijos
no se incluyen, ya que no dependen de la decisin
que se tome
Un conjunto de restricciones, las cuales definen qu
soluciones son posibles (factibles)

Gua para la formulacin de

modelos

Seguiremos estos pasos:

Expresar cada restriccin verbalmente, poniendo especial

cuidado en distinguir entre requerimientos (), limitaciones
() o exigencias de igualdad (=).
Expresar el objetivo verbalmente
Identificar verbalmente las variables de decisin
Expresar las restricciones mediante smbolos, es decir, en
trminos de las variables de decisin
Expresar la funcin objetivo simblicamente
Comprobar la coherencia de las unidades en las
restricciones y la funcin objetivo

Ejemplo
Ejemplo:

Una empresa dedicada a la

fabricacin de juguetes de madera produce
dos tipos de juguetes: coches y trenes

Los coches se venden a 27 y usan 10 de

materiales. Por cada coche hay un coste de
mano de obra de 14
Los trenes se venden a 21 , usan 9 de
material y el coste de mano de obra es 10

Ejemplo

La produccin de ambos juguetes necesita dos

tipos de trabajo: carpintera y acabado

Coche: 2 horas acabado, 1 hora carpintera

Tren: 1 hora acabado, 1 hora carpintera

La empresa dispone de un mximo de 80 horas

semanales de carpintera y 100 horas semanales de
acabado.
La demanda de trenes es ilimitada, pero la de
coches est limitada a 40 unidades a la semana
La empresa desea maximizar el beneficio

Ejemplo

Solucin:
Variables de decisin (deben describir las
decisiones que se van a tomar):

xC=n de coches producidos cada semana

xT=n de trenes producidos cada semana

Funcin objetivo:

Ganancias semanales: 27xC+21xT

Costes semanales:
Materiales:
Mano

10xC+9xT

de obra: 14xC+10xT

Ejemplo

Funcin objetivo (hay que maximizarla):

f xC , xT 27 xC 21xT 10 xC 9 xT 14 xC 10 xT
f xC , xT 3xC 2 xT

Restricciones:

Cada semana no se pueden usar ms de 100 horas de

acabado: 2xC+xT100

Cada semana no se pueden usar ms de 80 horas de

carpintera: xC+xT80

La demanda de coches est limitada: xC40

La produccin no puede ser negativa: xC0, xT0

Ejemplo
Coherencia

de unidades:

Las variables de decisin xc, xT estn en

horas/semana
La funcin objetivo est en /semana
Las restricciones estn expresadas en horas
Se observa que estamos usando coherentemente
las unidades

Mtodo grfico

Introduccin

Un primer intento de resolucin de los problemas de

programacin lineal es el mtodo grfico. Su inters
es limitado, ya que con l slo podemos resolver
problemas de dos variables (a lo sumo tres)
Definicin: Sea una funcin f: RnR. Llamamos
contorno k-simo de f y denotamos Ck al conjunto
de puntos tales que f(x)=k, donde kR
Para el caso de una funcin lineal de dos variables,
los contornos que se generan variando k forman un
haz de rectas paralelas

Algoritmo

El mtodo grfico consta de los siguientes pasos:

Dibujar la regin factible, S

Dibujar un contorno de la funcin objetivo
Determinar la direccin de crecimiento de los contornos

Una vez determinada la direccin de crecimiento de

los contornos, la solucin estar en el ltimo punto
de la regin factible que toquen los contornos antes
de abandonarla, siguiendo la direccin y sentido de
crecimiento o decrecimiento segn si nuestro
objetivo es maximizar o minimizar, respectivamente

Determinacin del crecimiento

Para

determinar la direccin de crecimiento

de los contornos, lo podemos hacer de dos
formas:

Dibujando dos contornos

Dibujando el vector gradiente, que como
sabemos marca siempre la direccin y sentido de
crecimiento de la funcin:
f f
grad f
,
x y

Ejemplo
Vamos

a resolver este problema:

Maximizar f(x,y)=x + 6y sujeto a:
2 x+ y 6
-x+ y

x, y 0
Si dibujamos la regin factible S, el contorno
0 y la direccin de crecimiento de la funcin
objetivo obtenemos la siguiente grfica

Ejemplo
y
5
4
3
(2,2)

2
grad f
1

C0
0

5 x

Ejemplo

En la grfica podemos ver que la funcin objetivo

aumenta su valor hacia arriba. La solucin del
problema de minimizar estar en el primer punto de
S que toquen los contornos al aumentar el valor (en
este caso, el origen de coordenadas), mientras que
la solucin del problema de maximizar estar en el
ltimo punto que toquen, en este caso el (2,2).
Por tanto, la solucin ptima de este problema es el
punto (2,2) y el valor ptimo de la funcin objetivo
es f(2,2)=14. En este caso la solucin ptima es
nica y adems S tiene rea finita (est acotado),
pero hay otros casos, como se ve a continuacin

Solucin ilimitada, S no
acotado

Solucin nica, S no acotado

Infinitas soluciones, S no
acotado

Infinitas soluciones, S
acotado

Sin solucin (S=)

Ejemplo
Problema:

Maximizar x1 + 2x2 sujeto a:

-1/2 x1 + x2
x1

+ x2 2

x1, x2 0

Representacin grfica
x2
5
4
3
2
1

E
C

A
0
0

D
2

x1

Puntos extremos
Punto

x1

x2

S1

S2

0.0

0.0

1.0

2.0

0.0

inf

inf

0.0

-inf

inf

0.0

1.0

0.0

1.0

2.0

2.0

0.0

2.0

0.0

2.0

0.0

2.0

-1.0

0.0

4.0

0.7

1.3

0.0

0.0

3.3

Ejemplo
Problema:

Maximizar x1 + 6x2 sujeto a:

-2x1 + x2 4
-x1 + x2 1
2x1 + x2 6
x1, x2 0

Representacin grfica
x2
10
9
8
7
G
6
I
5
4 C
3
J
2E
1
A
F
0
x1
0 1 2 3 4 5 6 7 8 9 10

Puntos extremos
Punto

x1

x2

S1

S2

S3

0.0

0.0

4.0

1.0

6.0

0.0

inf

inf

0.0

-inf

-inf

inf

0.0

4.0

0.0

-3.0

2.0

24.0

inf

inf

inf

0.0

-inf

inf

0.0

1.0

3.0

0.0

5.0

6.0

3.0

0.0

10.0

4.0

0.0

3.0

0.0

6.0

-2.0

-5.0

0.0

36.0

-3.0

-2.0

0.0

0.0

14.0

-15.0

0.5

5.0

0.0

-3.5

0.0

30.5

1.7

2.7

4.7

0.0

0.0

17.7

Ejemplo
Problema:

Maximizar 5x1 + 4x2 sujeto a:

3x1 + 3x2 10
12x1 + 6x2 24
x1, x2 0

Representacin grfica
x2
5
4

E
C

2
1
A
0
0

D
2

B
3

x1

Puntos extremos
Punto

x1

x2

S1

S2

0.0

0.0

10.0

24.0

0.0

3.3

0.0

0.0

-16.0

16.7

0.0

3.3

0.0

4.0

13.3

2.0

0.0

4.0

0.0

10.0

0.0

4.0

-2.0

0.0

16.0

0.7

2.7

0.0

0.0

14.0

Ejemplo
Problema:

Maximizar 20x1 + 24x2 sujeto a:

3x1 + 6x2 60
4x1 + 2x2 32
x1

+ 2x2 16

x1, x2 0

Representacin grfica
x2
20
18
E
16
14
12
C
10
G
H
8
J
6
4
2
A
D
F
B
0
x1
0 2 4 6 8 10 12 14 16 18 20

Puntos extremos
Punto

x1

x2

S1

S2

S3

0.0

0.0

60.0

32.0

16.0

0.0

20.0

0.0

0.0

-48.0

-4.0

400.0

0.0

10.0

0.0

12.0

-4.0

240.0

8.0

0.0

36.0

0.0

8.0

160.0

0.0

16.0

-36.0

0.0

-16.0

384.0

16.0

0.0

12.0

-32.0

0.0

320.0

0.0

8.0

12.0

16.0

0.0

192.0

4.0

8.0

0.0

0.0

-4.0

272.0

inf

-inf

inf

-inf

inf

-inf

5.3

5.3

12.0

0.0

0.0

234.7

Ejemplo
Problema:

Maximizar 6x1 + 3x2 sujeto a:

-x1 + x2 1
2x1 + x2 6
x1, x2 0

Representacin grfica
x2
10
9
8
7
E
6
5
4
F
3
2 C
1
A
D
0
x1
0 1 2 3 4 5 6 7 8 9 10

Puntos extremos
Punto

x1

x2

S1

S2

0.0

0.0

1.0

6.0

0.0

inf

inf

0.0

-inf

inf

0.0

1.0

0.0

5.0

3.0

3.0

0.0

4.0

0.0

18.0

0.0

6.0

-5.0

0.0

18.0

1.7

2.7

0.0

0.0

18.0

Ejemplo
Problema:

Maximizar x1 + x2 sujeto a:
5x1 - x2 0
x1

- 4 x2 0

x1, x2 0

Representacin grfica
x2
10
9
8
7
6
5
4
3
2
1 A=B=D=F
0
x1
0 1 2 3 4 5 6 7 8 9 10

Puntos extremos
Punto

x1

x2

S1

S2

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

inf

inf

0.0

inf

inf

0.0

0.0

0.0

0.0

0.0

inf

inf

inf

0.0

inf

0.0

0.0

0.0

0.0

0.0

Ejemplo
Problema:

Maximizar 6x1 + x2 sujeto a:

-x1 + x2 1
2x1 + x2 6
x1, x2 0

Representacin grfica
x2
10
9
8
7
E
6
5
4
F
3
2
1 C
A
D
0
x1
0 1 2 3 4 5 6 7 8 9 10

Puntos extremos
Punto

x1

x2

S1

S2

0.0

0.0

-1.0

6.0

0.0

inf

inf

0.0

-inf

inf

0.0

1.0

0.0

5.0

1.0

3.0

0.0

-4.0

0.0

18.0

0.0

6.0

5.0

0.0

6.0

1.7

2.7

0.0

0.0

12.7

Ejemplo
Problema:

Maximizar x1 + x2 sujeto a:
x1

- x2 6

2x1 - 2 x2 10
x1, x2 0

Representacin grfica
x2
10
9
8
7
6
5
4
3
2
1
A
D
B
0
x1
0 1 2 3 4 5 6 7 8 9 10

Puntos extremos
Punto

x1

x2

S1

S2

0.0

0.0

-6.0

10.0

0.0

6.0

0.0

0.0

-2.0

6.0

inf

inf

0.0

-2.0

inf

5.0

0.0

-1.0

0.0

5.0

inf

inf

-1.0

0.0

inf

inf

inf

-6.0

10.0

inf

Mtodo del simplex

Introduccin
El

mtodo del simplex es un algoritmo

general para resolver cualquier problema de
programacin lineal

Admite cualquier nmero de variables

Es un mtodo iterativo que nos conduce
progresivamente hasta la solucin final
En cada iteracin examina un punto extremo de
la regin factible S
Antes de usarlo es preciso pasar el problema a la
llamada forma estndar, que estudiaremos a
continuacin

Forma estndar

Definicin: Un problema de programacin lineal

est en forma estndar sii est expresado
como:Notacin escalar
Notacin matricial
Maximizar c1 x1 ... cn x n
Sujeto a :
a11 x1 ... a1n x n b1
...
am1 x1 ... amn x n bm
x1 ,..., x n 0

Maximizar c T x
Sujeto a :
Ax b
x0

Paso a la forma estndar

Las

dificultades que podemos encontrar para

pasar un problema a forma estndar, y las
soluciones correspondientes son:

Aparece una inecuacin del tipo aiTxbi. En tal

caso, aadimos una nueva variable, llamada
variable de exceso, si, con la restriccin si 0, de
tal manera que la inecuacin se convierte en la
ecuacin aiTxsi=bi. La nueva variable aparece
con coeficiente cero en la funcin objetivo.

Paso a la forma estndar

Aparece una inecuacin del tipo aiTxbi. En tal caso,

aadimos una nueva variable, llamada variable de
holgura, si, con la restriccin si0, de tal manera que
la inecuacin se convierte en la ecuacin aiTx+si=bi.
La nueva variable aparece con coeficiente cero en la
funcin objetivo.
Aparece una variable xi que no tiene restriccin de no
negatividad. En este caso, sustituimos xi en todas las
restricciones y en la funcin objetivo por la diferencia
de dos variables nuevas xn+1 y xn+2, que s tienen
restriccin de no negatividad: xn+10, xn+20.

Paso a la forma estndar

El problema es de minimizar, y no de maximizar. En

este caso, tendremos en cuenta que minimizar una
funcin objetivo F es lo mismo que maximizar la
funcin objetivo F. Por tanto, basta con multiplicar
por 1 la funcin objetivo.

Siguiendo estas guas podemos pasar cualquier

problema de programacin lineal a la forma
estndar. Debemos tener en cuenta que las nuevas
variables que se insertan para resolver un
inconveniente no pueden reutilizarse para resolver
otro

Ejemplos de paso a la forma

estndar
Maximizar x1 + 2x2

Maximizar x1 + 2x2 + 0x3

Sujeto a:
1/2 x1 + x2 1

Sujeto a:
1/2 x1 + x2 +x3 = 1

x1

+ x2 2

x1, x2 0

x1 + x2 2
x1, x2 , x3 0

Maximizar x1 + 2x2 + 0x3 + 0x4

Sujeto a:
1/2 x1 + x2 +x3
x1 + x2

+x4 = 2

x1, x2 , x3 , x4 0

=1

Ejemplos de paso a la forma

estndar
Maximizar 7x1 9x2

Maximizar 7x1 9x2 + 0x3

Sujeto a:
4 x1 + 8x2 2

Sujeto a:
4 x1 + 8x2 x3

3x1 + x2

3x1 + x2

x1, x2 0

x1, x2 , x3 0

Maximizar 7x1 9x2 + 0x3 + 0x4

Sujeto a:
4 x1 + 8x2 x3
3x1

+ x2

=2
+x4 = 8

x1, x2 , x3 , x4 0

=2

Ejemplos de paso a la forma

estndar
Maximizar 3x1 5x2

Maximizar 3x1 5x3 + 5x4

Sujeto a:
10 x1 + 18x2 = 7

Sujeto a:
10 x1 +18x3 18x4 = 2

4x1 + 5x3 5x4 9

4x1 + 5x2
x1 0

x1, x3 , x4 0

Maximizar 3x1 5x3 + 5x4 + 0x5

Sujeto a:
10 x1 +18x3 18x4
4x1 + 5x3 5x4
x1, x3 , x4 , x5 0

=2
+x5 = 9

Ejemplos de paso a la forma

estndar
Minimizar 7x1 4x2

Maximizar 7x1 + 4x2

Sujeto a:
8 x1 + 2x2 1

Sujeto a:
8 x1 + 2x2 1

x1 + 5x2 = 6

x1 + 5x2 = 6

x1, x2 0

x1, x2 0

Maximizar 7x1 + 4x2 + 0x3

Sujeto a:
8 x1 + 2x2 + x3 = 1
x1 + 5x2
x1, x2 , x3 0

=6

Situacin inicial para aplicar el

mtodo simplex

Partimos de un problema de programacin lineal, con m

ecuaciones y n incgnitas (o variables de decisin)
expresado en forma estndar:
Maximizar c1 x1 ... cn x n
Sujeto a :
a11 x1 ... a1n x n b1
...
am1 x1 ... amn x n bm
x1 ,..., x n 0
Adems el mtodo simplex exige que bi0 i{1, ..., m}

Versin bsica del algoritmo

simplex
1.

Construir la primera tabla

2. Mientras CondicinParada=Falso hacer

3.

2.1. Elegir variable que sale

2.2. Elegir variable que entra
2.3. Actualizar tabla

Dar resultado

Construccin de la primera
tabla

Dado el problema tal como se explica en Situacin

inicial, lo primero que hay que hacer es localizar un
conjunto de m variables de tal manera que si
eliminramos las dems y reorganizsemos las
ecuaciones, nos quedara la matriz de coeficientes
del sistema de ecuaciones convertida en la matriz
identidad. Estas m variables formarn la primera
base, y la solucin del sistema de ecuaciones se
que obtendra con esos cambios es una solucin
bsica factible (SBF).

Construccin de la primera
tabla

Llamaremos i1, i2,..., im a los ndices de las m

variables de la base, de tal manera que la variable ij
es la que tiene un uno de coeficiente en la ecuacin
nmero j.
En las tablas aparecen los valores zi, que pueden
calcularse mediante la siguiente ecuacin: zj=cBTPj,
donde T indica trasposicin de vectores.
Construimos la primera tabla de esta manera (lo
que va en negrita son rtulos que se ponen tal
cual):

Modelo de tabla
c1

c2

...

cn

Base

cB

P0

P1

P2

Pn

Pi1

ci1

bi1

a11

a12

a1n

Pi2

ci2

bi2

a21

a22

a2n

...

Pim

cim

bim

am1

am2

amn

z0

z 1 c 1

z2 c2

zn cn

Condicin de parada. Criterio

de entrada

Condicin de parada: El bucle se detiene cuando

la tabla actual es tal que en su ltima fila no
aparece ningn valor estrictamente negativo
Eleccin de la variable que entra: En caso de que
el algoritmo no se haya detenido, hay que elegir qu
variable, de entre las que no estn en la base, va a
entrar en dicha base. Para ello nos fijamos en los
valores estrictamente negativos que haya en la
ltima fila. Escogeremos la variable j
correspondiente al ms negativo (es decir, mayor
valor absoluto) de estos valores.

Criterio de salida

Eleccin de la variable que sale: Una vez elegida

la variable j que entra, nos fijamos en la columna
cuyo ttulo es Pj. Dividimos el vector P0 entre el Pj,
componente a componente. De entre las fracciones
con denominador estrictamente positivo que
resulten (es decir, las correspondientes a
componentes estrictamente positivas de Pj),
escogemos la mnima. La fila donde hemos
obtenido este valor mnimo es la de la variable de la
base que sale.

Actualizacin de la tabla

Construimos una tabla nueva, en la que las dos primeras filas

son las mismas que en la antigua (son los ci y los rtulos).
Las columnas con ttulos cB y Base slo se ven alteradas en
un elemento cada una: el elemento de la fila correspondiente
a la variable que ha cambiado en la base.
La subtabla formada por los ajk y los biz debe ser alterada de
tal modo que en cada una de sus filas haya un uno en el
elemento de la columna de la variable de la base que
corresponde a esa fila, y un cero en los elementos de las
columnas de las dems variables de la base. Esto debe
hacerse usando siempre transformaciones elementales (es
decir, las que se usan para resolver sistemas de ecuaciones
lineales por Gauss-Jordan).

Actualizacin de la tabla
Tras

haber hecho esto, la ltima fila de la

tabla global se actualiza recalculando sus
valores con las frmulas que se usaron para
la construccin de la primera tabla.
Ntese que, como lo nico que hacemos son
transformaciones elementales, en realidad lo
que estamos haciendo en cada iteracin del
mtodo simplex es expresar el sistema de
ecuaciones de otra manera.

Resultado del mtodo

Los

valores ptimos de las variables que

forman la base vienen dados por la columna
P0 de la ltima tabla. El resto de las variables
tienen valor ptimo cero.
El valor ptimo de la funcin objetivo (funcin
que estbamos maximizando) es el z0 de la
ltima tabla.

Ejemplos
Problema:

Maximizar x1 + 2x2 sujeto a:

-1/2 x1 + x2
x1

+ x2 2

x1, x2 0

Ejemplos
Tabla 1
1

XB

cB

bi

X1

X2

S1

S2

S1

-1/2

S2

-1

-2

ZJ -CJ

Criterio de entrada: mn { -1, -2 } = -2, luego entra x2

Criterio de salida: mn { 1, 2 } = 1, luego sale S1

Ejemplos
Tabla 2
1

XB

cB

bi

X1

X2

S1

S2

X2

-1/2

S2

3/2

-1

-2

ZJ -CJ

Criterio de entrada: mn { -2 } = -2, luego entra x1

Criterio de salida: mn { 2/3 } = 2/3, luego sale S2

Ejemplos
Tabla 3
1

XB

cB

bi

X1

X2

S1

S2

X2

4/3

2/3

1/3

X1

2/3

-2/3

2/3

10/3

2/3

4/3

ZJ -CJ

Se cumple la condicin de parada. Valor ptimo: 10/3

Solucin ptima: (2/3, 4/3, 0, 0)T

Ejemplos
Problema:

Maximizar x1 + 6x2 sujeto a:

-2x1 + x2 4
-x1 + x2 1
2x1 + x2 6
x1, x2 0

Ejemplos
Tabla 1
1

XB

cB

bi

X1

X2

S1

S2

S3

S1

-2

S2

-1

S3

ZJ -CJ
0
-1
-6
0
0
0
Criterio de entrada: mn { -1, -6 } = -6, luego entra x2
Criterio de salida: mn { 4, 1, 6 } = 1, luego sale S 2

Ejemplos
Tabla 2
1

XB

cB

bi

X1

X2

S1

S2

S3

S1

-1

-1

X2

-1

S3

-1

ZJ -CJ
6
-7
0
0
6
Criterio de entrada: mn { -7 } = -7, luego entra x1
Criterio de salida: mn { 5/3 } = 5/3, luego sale S3

Ejemplos
Tabla 3
1

XB

cB

bi

X1

X2

S1

S2

S3

S1

14/3

-4/3

1/3

X2

8/3

2/3

1/3

X1

5/3

-1/3

1/3

ZJ -CJ
53/3
0
0
0
11/3 7/3
Se cumple la condicin de parada. Valor ptimo: 53/3
Solucin ptima: (5/3, 8/3, 14/3, 0, 0) T

Ejemplos
Problema:

Maximizar 5x1 + 4x2 sujeto a:

3x1 + 3x2 10
12x1 + 6x2 24
x1, x2 0

Ejemplos
Tabla 1
5

XB

cB

bi

X1

X2

S1

S2

S1

10

S2

24

12

-5

-4

Criterio de entrada: mn { -5, -4 } = -5, luego entra x1

Criterio de salida: mn { 10/3, 2 } = 2, luego sale S2

Ejemplos
Tabla 2
5

XB

cB

bi

X1

X2

S1

S2

S1

3/2

-1/4

X1

1/2

1/12

10

-3/2

5/12

ZJ -CJ

Criterio de entrada: mn { -3/2 } = -3/2, luego entra x2

Criterio de salida: mn { 8/3, 4 } = 8/3, luego sale S 1

Ejemplos
Tabla 3
5

XB

cB

bi

X1

X2

S1

S2

X2

8/3

2/3

-1/6

X1

2/3

-1/3

1/6

14

1/6

Se cumple la condicin de parada. Valor ptimo: 14

Solucin ptima: (2/3, 8/3, 0, 0)T

Ejemplos
Problema:

Maximizar 20x1 + 24x2 sujeto a:

3x1 + 6x2 60
4x1 + 2x2 32
x1

+ 2x2 16

x1, x2 0

Ejemplos
Tabla 1
20

24

XB

cB

bi

X1

X2

S1

S2

S3

S1

60

S2

32

S3

16

0
-20
-24
0
0
0
Criterio de entrada: mn { -20, -24 } = -24, luego entra x2
Criterio de salida: mn { 10, 16, 8 } = 8, luego sale S3

Ejemplos
Tabla 2
20

24

XB

cB

bi

X1

X2

S1

S2

S3

S1

12

-3

S2

16

-1

X2

24

1/2

1/2

192
-8
0
0
0
12
Criterio de entrada: mn { -8 } = -8, luego entra x1
Criterio de salida: mn { 16/3, 16 } = 16/3, luego sale S 2

Ejemplos
Tabla 3
20

24

Base

cB

P0

X1

X2

S1

S2

S3

S1

12

-3

X1

20

16/3

1/3

-1/3

X2

24

16/3

-1/6

2/3

704/3
0
0
0
8/3 28/3
Se cumple la condicin de parada. Valor ptimo: 704/3
Solucin ptima: (16/3, 16/3, 12, 0, 0)T

Casos anmalos

Problemas con infinitas

soluciones

En la tabla final hay algn valor nulo en la ltima fila, que

corresponde a una variable que no est en la base. En
tal caso, podramos introducir dicha variable en la base,
y nos saldra otra base que dara tambin el valor
ptimo. Esto quiere decir que el problema tiene infinitas
soluciones, todas ellas con el mismo valor ptimo de la
funcin objetivo. Sea K el nmero de vectores solucin
obtenidos de esta manera (habiendo K1 ceros extra), y
sean dichos vectores x1, x2, ..., xK. Entonces las infinitas
soluciones del problema sern:
K

i 1

i 1

i x i , donde i 0,1, i 1

Ejemplos
Problema:

Maximizar 6x1 + 3x2 sujeto a:

-x1 + x2 1
2x1 + x2 6
x1, x2 0

Ejemplos
Tabla 1
6

XB

cB

bi

X1

X2

S1

S2

S1

-1

S2

-6

-3

Criterio de entrada: mn { -6, -3 } = -6, luego entra x1

Criterio de salida: mn { 3 } = 3, luego sale S2

Ejemplos
Tabla 2
6

XB

cB

bi

X1

X2

S1

S2

S1

3/2

1/2

X1

1/2

1/2

18

Se cumple la condicin de parada. Valor ptimo: 18.

Primera solucin ptima: xA=(3, 0, 4, 0)T
En la ltima fila, el cero que no est en la base indica otra
solucin ptima. Para hallarla, hacemos entrar a x2

Ejemplos
Tabla 3
6

XB

cB

bi

X1

X2

S1

S2

X2

8/3

2/3

1/3

X1

5/3

-1/3

1/3

18

Segunda solucin ptima: xB=(5/3, 8/3, 0, 0)T. Tambin

son soluciones ptimas todos los puntos del segmento
AxA+BxB, con A , B 0, A + B = 1.

Problemas con solucin

ilimitada
Al

intentar elegir la variable que sale, nos

podemos encontrar con que la columna Pj de
la variable j que tena que entrar tiene todos
sus elementos negativos o nulos. En tal caso
el problema tiene solucin ilimitada, es decir,
se puede hacer crecer el valor de la funcin
objetivo tanto como se quiera sin violar
ninguna restriccin. Para ello, bastara con
hacer crecer ilimitadamente la variable que
tena que entrar en la base.

Ejemplos
Problema:

Maximizar x1 + x2 sujeto a:
5x1 - x2 0
x1

- 4 x2 0

x1, x2 0

Ejemplos
Tabla 1
1

XB

cB

bi

X1

X2

S1

S2

S1

-5

S2

-4

-1

-1

Criterio de entrada: mn { -1, -1 } = -1, y elegimos que

entre x1
Criterio de salida: mn { 0/1 } = 0, luego sale S2

Ejemplos
Tabla 2
1

XB

cB

bi

X1

X2

S1

S2

S1

-19

X1

-4

-5

Criterio de entrada: mn { -5 } = -5, luego entra x2

Criterio de salida: No hay fracciones con denominador
estrictamente positivo, luego el problema tiene
solucin ilimitada

Mtodo de las dos

fases

Introduccin
Si

al intentar aplicar el mtodo simplex nos

encontramos con que no es posible
encontrar una solucin bsica factible (SBF)
inicial, es preciso usar el mtodo de las dos
fases.
Para ello, usamos el siguiente algoritmo:

1. Aadir variables artificiales al problema

2. Fase I.
3. Fase II.

Adicin de variables
artificiales
Se

trata de aadir al problema tantas

variables como sean necesarias para
construir una SBF. Sus coeficientes en las
ecuaciones sern los que convengan para
nuestro propsito.
Por consiguiente, tendremos que cada
variable artificial tendr coeficiente 1 en una
ecuacin y coeficiente 0 en todas las dems

Fase I

Se trata de aplicar el mtodo simplex para resolver un

problema auxiliar que consiste en minimizar la suma de
las variables artificiales. Para que la tabla ptima
aparezca lo antes posible conviene que, en caso de
empate en el criterio de salida y que una de las variables
empatadas sea artificial, saquemos la artificial.
Una vez resuelto este problema auxiliar, caben dos
posibilidades

El valor ptimo de la funcin objetivo es distinto de cero. En tal

caso el problema original no tena solucin.
El valor ptimo de la funcin objetivo es cero. En tal caso
podemos pasar a la Fase II.

Fase II
Consiste

en aplicar el mtodo simplex,

usando la funcin objetivo del problema
original, pero empezando con una primera
tabla que se obtiene quitando de la ltima
tabla de la Fase I las columnas de las
variables artificiales
La solucin obtenida en la Fase II ser la
solucin del problema original (tngase en
cuenta que en la Fase II no aparecen
variables artificiales)

Ejemplos
Problema:

Maximizar 6x1 + x2 sujeto a:

-x1 + x2 1
2x1 + x2 6
x1, x2 0

Ejemplos
Tabla 1 de la Fase I
0

-1

Base

cB

P0

P1

P2

P3

P4

P5

P5

-1

-1

-1

P4

-1
1
-1
1
0
Criterio de entrada: mn { -1 } = -1, luego entra x2
Criterio de salida: mn { 1, 6 } = 1, luego sale x5

Ejemplos
Tabla 2 de la Fase I
0

-1

Base

cB

P0

P1

P2

P3

P4

P5

P2

-1

-1

P4

-1

0
0
0
0
0
1
Se cumple la condicin de parada. Valor ptimo: 0 (el
problema tiene solucin).
Construimos la primera tabla de la Fase II quitando la
variable artificial x5

Ejemplos
Tabla 1 de la Fase II
6

Base

cB

P0

P1

P2

P3

P4

P2

-1

-1

P4

-7

-1

Criterio de entrada: mn { -7, -1 } = -7, luego entra x1

Criterio de salida: mn { 5/3 } = 5/3, luego sale x4

Ejemplos
Tabla 2 de la Fase II
6

Base

cB

P0

P1

P2

P3

P4

P2

8/3

-2/3

1/3

P1

5/3

1/3

1/3

38/3

4/3

7/3

Se cumple la condicin de parada. Valor ptimo: 38/3

Solucin ptima: (5/3, 8/3, 0, 0)T

Ejemplos
Problema:

Maximizar 4x1 + x2 + 6x3 sujeto a:

-2x1 - x2 + 2x3

x1

+ x2 + x3

x1, x2 , x3 0

Ejemplos
Tabla 1 de la Fase I
0

-1

-1

Base

cB

P0

P1

P2

P3

P4

P5

P6

P7

P6

-1

-2

-1

-1

P7

-1

-1

-7 1
0
-3
1
1
0
Criterio de entrada: mn { -3 } = -3, luego entra x3

Criterio de salida: mn { 1/2, 6 } = 1/2, luego sale x6

Ejemplos
Tabla 2 de la Fase I
0

-1

-1

P2

P3

P4

P5

P6

P7

Base

cB

P0

P1

P3

1/2

-1 -1/2

-1/2

1/2

P7

-1 11/2

1/2

-1

-1/2

3/2

-11/2 -2 -3/2 0 -1/2 1

3/2
0
Criterio de entrada: mn { -2, -3/2, -1/2 } = -2, luego
entra x1
Criterio de salida: mn { 11/3 } = 11/3, luego sale x7

Ejemplos
Tabla 3 de la Fase I

Base cB

-1

-1

P0

P1

P2

P3

P4

P5

P6

P7
1/2

P3

13/4

1/4

-1/4 -1/2 1/4

P1

11/4

3/4

1/4 -1/2 -1/4 1/2

Se cumple la condicin de parada. Valor ptimo: 0 (el

problema tiene solucin).
Construimos la primera tabla de la Fase II quitando las
variables artificiales x6 y x7

Ejemplos
Tabla 1 de la Fase II
4

Base

cB

P0

P1

P2

P3

P4

P5

P3

13/4

1/4

-1/4

-1/2

P1

11/4

3/4

1/4

-1/2

61/2

7/2

-1/2

-5

Criterio de entrada: mn { -1/2, -5 } = -5, luego entra x5

Criterio de salida: No hay fracciones con denominador
estrictamente positivo, luego el problema tiene solucin
ilimitada

Ejemplos
Problema:

Maximizar x1 + x2 sujeto a:
x1

- x2 6

2x1 - 2 x2 10
x1, x2 0

Ejemplos
Tabla 1 de la Fase I
0

-1

Base

cB

P0

P1

P2

P3

P4

P5

P5

-1

-1

-1

P4

10

-2

-6

-1

Criterio de entrada: mn { -1 } = -1, luego entra x1

Criterio de salida: mn { 6, 5 } = 5, luego sale x4

Ejemplos
Tabla 2 de la Fase I
0

-1

Base

cB

P0

P1

P2

P3

P4

P5

P5

-1

-1

-1/2

P1

-1

1/2

-1

1/2

Se cumple la condicin de parada. Valor ptimo: -1.

Como no resulta valor ptimo 0, el problema original
no tiene solucin.

Dualidad

Problemas primal y dual

Sea un problema de programacin lineal, que

llamaremos problema primal:
Maximizar cT x

Sujeto a :
Ax b, x 0

El correspondiente problema dual es:

Minimizar bT y
Sujeto a :
AT y c, y 0

Ntese que el dual del dual coincide con el primal

Resultados
Teorema dbil de dualidad: El valor de la
funcin objetivo del dual para cualquier solucin
factible es siempre mayor o igual que el valor de
la funcin objetivo del primal para cualquier
solucin factible.
Teorema fuerte de dualidad: Si el primal tiene
una solucin ptima x*, entonces el dual
tambin tiene una solucin ptima y*, tal que
cTx*=bTy*.

Comentarios

El teorema dbil de dualidad implica que si el primal

tiene solucin ilimitada, entonces el dual no tiene
solucin.
Del mismo modo, si el dual tiene solucin ilimitada,
entonces el primal no tiene solucin.
No obstante, es posible que ni el primal ni el dual
tengan solucin.
Cada componente de x se corresponde con una
variable de exceso del dual.
Cada componente de y se corresponde con una
variable de holgura del primal.

Complementariedad

Teorema de complementariedad: Sean x = (x1,

x2, ..., xn), y = (y1, y2, ..., ym) soluciones factibles
del primal y el dual, respectivamente. Sean (w1,
w2, ..., wm) las variables de holgura
correspondientes del primal, y sean (z1, z2, ...,
zn) las variables de exceso correspondientes del
dual. Entonces x e y son ptimas para sus
respectivos problemas si y slo si xjzj = 0, j =
1, 2, . . . , n, y adems wiyi = 0, i = 1, 2, ..., m.

Complementariedad

El teorema de complementariedad nos permite

obtener rpidamente una solucin ptima del
problema dual si conocemos una solucin ptima
del problema primal.
Para ello, si tenemos que en una solucin ptima
del primal xj>0, entonces en el dual zj=0. Adems si
en la solucin ptima del primal wi>0, entonces en
el dual yi=0.
De esta manera slo quedarn por determinar los
valores ptimos de unas pocas variables del
problema dual.