LA PROGRAMACIÓN LINEAL.

Introducción.
La “Programación Lineal” se puede considerar como uno de los
grandes logros, ya que es una de las herramientas bastante común en la
formulación de muchos tipos de problemas.
En concreto, el tipo más común de aplicación abarca el problema
general de asignar “recursos escasos entre actividades competitivas” de
la mejor manera posible(es decir, de forma óptima).
Este tipo de problemas surge cuando se quiere determinar el nivel
de las actividades que compiten por los recursos escasos que son
necesarios para que se puedan realizar.
Como ejemplos de la gran variedad de situaciones en las que se
puede aplicar esta descripción, tenemos entre otras, desde la asignación
de instalaciones productivas; la asignación de los recursos nacionales a
las necesidades de un país; la distribución de mercancías entre unos
orígenes y unos destinos; la asignación de personal para atender unas
máquinas; el diseño de carreteras entre diversas poblaciones; la mezcla
de productos, o por ejemplo, la planificación agrícola. En definitiva,
como característica común de todas estas situaciones es la necesidad de
asignar recursos a las necesidades.
La Programación Lineal utiliza un modelo matemático para
describir el problema.
El adjetivo lineal significa que todas las funciones matemáticas del
modelo deben de ser funciones lineales, es decir, las variables que
intervienen son de primer grado. En cuanto a la palabra programación,
esta no es sinónimo de programación en computadoras, sino que es
sinónimo de planificación.
Luego entonces, la “programación lineal” se entiende como “la
planificación de actividades para obtener el resultado, es decir, el mejor
resultado que alcance la meta (o función objetivo) según el modelo
matemático entre todas las alternativas de solución”.
 Aunque la asignación de recursos a las actividades es la aplicación
más frecuente, la P.L. tiene otras muchas aplicaciones. Así, cualquier
problema cuyo modelo matemático se ajuste al formato general del
modelo de P.L. es un problema de programación lineal.
También, otra causa del gran impacto de la P.L. es el eficiente
procedimiento para resolver los problemas de gran tamaño mediante el
denominado “método (algoritmo) simplex.”.

MODELO MATEMÁTICO DE LA P.L.

Un problema de programación lineal consiste en optimizar
(maximizar o minimizar, según el problema) una función objetivo lineal
sometida a una serie de restricciones también lineales, en forma de
desigualdades y/o igualdades.
Por ejemplo:

MAXIMIZAR(MINIMIZAR) : z = c1 x1 + ..  cjxj  ..  cn xn : Función objetivo

a11 x1 + ..........a1n xn   b1 

Sujeto a : ............................ Restricciones funcionales
am1 x1 + ..........amn xn  bm 
x1,.x2,...............xn  0, Restricción de " no negatividad".

El modelo matemático del ejemplo anterior, se puede considerar

como la modelización de un problema real, es decir, un modelo es la
representación del problema real en una forma más simplificada, donde se
consideran las variables más representativas (x 1 , x 2 ,.... x n ) que se pueden
controlar, también denominadas “variables de decisión” (diferentes
alternativas) que se quieren determinar.
En cuanto a las restricciones, se establecen las relaciones entre las
variables, que vienen a ser requerimientos o limitaciones. Así, en las
restricciones funcionales, aij, representa la cantidad utilizada (o
necesaria) de la cantidad del lado derecho b i , por cada unidad de la
actividad j. A los coeficientes a i j , se les denomina normalmente, como
“coeficientes tecnológicos”, ya que como se acaba de describir, es la
forma como se utiliza el lado derecho b i . (en problemas de asignación de
recursos, representa la cantidad del recurso i disponible) para obtener una
cantidad unidad de la variable (actividad) j.
En cuanto a la restricción de “no negatividad”, se considera que las
variables no son negativas ya que normalmente las mismas se refieren a
magnitudes físicas cuyo valor suele ser una cantidad nula o positiva (en
el supuesto de que alguna variable pueda tomar un valor negativo,
entonces se puede sustituir por una variable “no negativa”, haciendo un
cambio de variables y al obtener el resultado final, deshacer el cambio
efectuado para conocer el verdadero valor de la variable original).
El conjunto de restricciones nos da el cumplimiento simultáneo por
todas las variables, es decir, nos da el conjunto de todos puntos factibles
donde estará la solución, denominada región factible. Para elegir la
solución adoptamos un criterio o también denominada, función objetivo,
es decir, una función que establezca la eficiencia de la combinación de
los valores asignados a cada una de las variables. Cada parámetro c j
representa la ganancia unitaria por cada unidad de la variable (actividad)
j (o sea, para x j =1). Luego la función objetivo z = c 1 x 1 + c 2 x 2 +....+ c n x n
representa la ganancia total para una cierta combinación (x 1 , x 2 ,.... x n ).
(En cambio si el problema fuese de Minimización, c j , representará el
“coste unitario” por cada unidad de la variable j, y por lo tanto, z
representaría el costo total).
En resumen, el problema anterior se puede poner como:

n
MAXIMIZAR : z   cjxj
j=1
n
Sujeto a : a x  b ;
j=1
ij j i i = 1,2,...m

xj  0; j = 1,2,....n
n

a x
j=1
ij j representa “la cantidad total utilizada del lado derecho b i por

todas las variables (actividades)”.

En forma matricial:
 MAXIMIZAR: z = cx
Sujeto a: Ax  b
x0
donde:
c = (c 1 , c 2 ,....... c n ), es el vector de ganancias (o costos si es
MIN) unitarias
x1
x2
vector factible, o sea, el conjunto de valores de las variables
x= . ,
que verifican simultaneamente todas las restricciones.
.

xn

 a11. . . . . . . . . . . . . . . . . . a1n  a 1 
   
A (matriz de restricciones) =  .    a1, . . . . . . an  . 
 am1. . . . . . . . . . . . . . . . . amn   a m 

donde:
a1j 
aj (vector columna de A) = .  ; a i ( vector fila de A)  ai1,....., ain 
amj

Se puede considerar que la función y cada restricción representan la

ecuación de un hiperplano, que se puede definir como el producto de la
normal p por el vector de la variable x, es decir,

p.x = k
donde p es la normal, x el vector de las variables y k un escalar, luego
 x1 
z = (c 1 ,…c j ,….c n ) . 
 xn 

 x1   x1 
y una restricción i a .  =(a i 1 , a i j ,
i
a i n ) .  = b i
 xn   xn 

En el caso de” =,” se trata de una ecuación, mientras que si” <= “o” >=”
o sea una inecuación, se trata de uno de los semiespacios que divide el
hiperplano. En el caso de que el nº de variables sean 2 se trata de la
ecuación de una recta, si son tres de un plano, y si son más de 2 se trata
de un semiplano (con =), mientras que con <= o >= serían los
semiespacios que dividen los hiperplanos.

De cara a poder utilizar el método simplex, es necesario realizar

algunas manipulaciones en un problema de P.L, como se verá
posteriormente. Así, por ejemplo:
MAXIMIZAR cx = - MINIMIZAR (-c)x
MINIMIZAR cx = - MAXIMIZAR (-c)x
Ax  b  -Ax  -b
Ax  b  -Ax  -b
Ax  b
Ax = b   , o viceversa
Ax  b
También es necesario conocer que el conjunto de restricciones debe
transformarse en un sistema de ecuaciones (o sea, en forma de
igualdades). Luego:
Si se tiene Ax  b, entonces se hace Ax- Is =b
Si se tiene Ax  b, entonces se hace Ax+ Is =b
donde s es un vector de variables de holgura e I la matriz identidad. Las
variables de holgura son variables que sirven para conseguir que una
desigualdad se convierta en una igualdad (ecuación) y tienen un costo
unitario nulo, es decir, no tienen ningún costo por ser utilizadas.
En el caso de una variable x j sea no restringida, es decir, su valor pueda
ser positivo, negativo o nulo, se puede realizar el cambio de variables
siguiente:
x j = x j + -x j - , donde

xj si xj  0 0 si xj  0
xj+=  y xj-=  con x j + , x j - >= 0
0 si xj  0  xj si xj  0
Luego si x j + > 0, entonces x j - = 0, y viceversa, si si x j - > 0, entonces x j +
= 0, pudiendo ser x j + = x j - = 0.
Ejemplo: si tenemos el problema:
 Minimizar : z = x1 - 3x2
Sujeto a. x1 + 2x2  5
- 2x1 + 2x2  7
x1  0
Como no nos dicen nada sobre el signo de x 2 , suponemos que el valor
puede ser cualquiera, positivo, negativo o nulo, es decir, se trata de una
variable no restringida, entonces hacemos el cambio de x 2 = x 2 + -x 2 - , y el
problema será ahora:
Minimizar : z = - x1 - 3(x2   x2  )  Minimizar z  - x1 - 3x2   3x2 
Sujeto a. x1 + 2(x2   x2  )  5 Sujeto a x1 + 2x2   2 x2   5
- 2x1 + 2(x2   x2  )  7 - 2x1 + 2x2  - 2x2   7
x 1 , x 2  , x2   0 x 1 , x 2  , x2   0
Al final cuando se obtengan los valores de x 1 , x2  y x2  , entonces se
deshace el cambio, es decir, se calcula x 2 = x 2 + -x 2 -

RESOLUCION DE UN PROBLEMA DE P.L.

Vamos a utilizar para ello el ejemplo ilustrativo siguiente:
Minimizar: z = - x1 - 2x2
Sujeto a. x1 + x2  3 1
- x1 + 2x2  2 2
x1 , x2  0
gráficamente:

x2

x*=(x*1;x*2)=(4/3;5/3)
1

2
z0=c1x1+c2x2
z= c1x*1+c2x*2
x1

c
 Se puede observar que las restricciones 1 , 2 y las de “no
negatividad” x 1 , x 2  0, que definen semiespacios (al ser “ “ dividen
cada una de las restricciones en dos zonas), dan la zona subrayada, que se
denomina región factible, es decir, el conjunto de puntos (x 1 , x 2 ) que
verifican simultáneamente “todas” las restricciones. En un caso general
con n variables (las rectas serían hiperplanos) también definirían una
región factible donde las fronteras serían superficies planas. Luego, una
región factible se obtiene como la intersección de un número finito (al
serlo el número de restricciones) de semiespacios (conjunto poliédrico).
Consecuentemente, una solución del problema tendrá que ser
necesariamente un punto de la región factible.
Pero si se observa, la función objetivo z ,que se pretende
minimizar, es una recta (un hiperplano en el caso general, al ser más de
2 variables) cuyo gradiente(normal) c es perpendicular a ella, toma un
valor cada vez menor a medida que se aleja en el sentido -c, resultando
con el menor valor para z en los puntos más alejados de la región
factible, es decir, en un vértice x * de la figura, o sea, x * =(4/3;5/3).
(NOTA: Si en el ejemplo anterior, se tratase de MAXIMIZAR en vez de
Minimizar, la función objetivo z alcanza el mayor valor si el sentido es
en c, o sea, sería entonces en el origen).
Luego, se puede concluir, que la solución óptima de un problema
de programación lineal “siempre será” un vértice de la región factible, es
decir, el número de posibles soluciones es un número finito ya que se
obtienen por la intersección de un número finito restricciones, que
definen un conjunto llamado poliédrico (las restricciones en un problema
de programación lineal son conjuntos convexos donde para cualquier par
de puntos x 1 y x 2 , la combinación convexa  x 1 + (1- )x 2 con (0;o1o
es lo mismo, representa el segmento que une a dichos puntos que también
pertenece al conjunto poliédrico). Luego la región factible es un conjunto
poliédrico que es un conjunto convexo, zona común del cumplimiento
simultaneo de todas las restricciones (relaciones entre las variables), y
como hemos visto gráficamente, la solución va estar en un vértice de
dicha región factible.
Ahora teniendo en cuenta la forma de las restricciones así como del
vector c, existen los siguientes tipos de soluciones.

DIFERENTES TIPOS DE SOLUCIONES EN UN P.L.

(En MINIMIZACIÓN).
A) Solución única finita ( z es un valor finito)

x2
x2
x*
z* x*
x1
z* x1
c
c
A 1 ) Con región acotada. A 2 ) Con región “no acotada”
Nota: una región es acotada cuando con una esfera con centro en el origen
y de radio finito contiene a la región finita, y no acotada cuando el radio
es infinito.
B) Infinitas soluciones finitas (alternativas)( con igual valor finito z)

z* x2
x2
x*1
x*2
x*1
z*
x*2 x1
c x1
c
B 1 ) Con región acotada. B 2 ) Con región “no acotada”
En los dos casos B 1 y B 2 , existen dos puntos (vértices) x * 1 y x * 2 ya que el
gradiente c de la recta objetivo es perpendicular a una cara de la región
factible que tienen el mismo valor objetivo. Sin embargo ahora también
son soluciones óptimas, además de los puntos anteriores, los puntos
contenido en el segmento (que no son lógicamente vértices) que une
dichos vértices, o sea, la combinación convexa  x * 1 + (1- ) x * 2 con
(0;1). Es decir, cuando =0, se obtiene el punto x * 2 y con =1 el x * 1 ,
mientras que para un valor entre 0 y 1 se obtiene un punto del segmento
que da el mismo valor objetivo, en definitiva, el problema tendría 
soluciones alternativas.

C) Solución “NO ACOTADA” ( es decir, z -)

x2
x0*

d
x1
c
z0*

Con región “no acotada”

Como se puede observar, al desplazarse la recta que define la
función objetivo en el sentido -c, siempre existe región factible, con lo
cuál el valor objetivo se hace -, es decir, el valor objetivo en el punto
x * 0 es z * 0 que ya se puede tomar como solución óptima, pero sin embargo
se puede mejorar siempre que nos desplacemos a través del rayo con
vértice en x * 0 y con dirección d (definida por la cara extrema que
delimita la región factible, donde es un vector d  0), es decir:
z a lo largo del rayo  x * 0 + d; para todo   0 
O sea, si  = 0, la solución óptima está en el vértice x * 0 con valor
objetivo z * 0 (que ya se puede tomar como valor óptimo en la práctica),
aunque se puede mejorar la función objetivo a medida de que
incrementemos el valor de .
D) No existe solución (cuando la región factible es vacía).

x2

x1
Primer ejemplo prototipo.

Una cierta compañía posee una fábrica de pinturas que produce

colorantes para interiores y exteriores de casas. Se utilizan dos materiales
básicos, A y B para producir las pinturas. La disponibilidad máxima de A
y de B es de 6 y 8 toneladas diarias, respectivamente. Los requisitos de
materias primas por tonelada de pintura para interiores y exteriores se
resumen en el tabló siguiente:

Toneladas de materia prima por

tonelada de pintura
Exterior Interior Disponibilidad má-
xima(en toneladas)
Materia prima A 1 2 6
Materia prima B 2 1 8

Un estudio de mercado ha establecido que la demanda diaria de

pintura para interiores no puede ser mayor que la de pintura para
exteriores en más de una tonelada. El estudio señala asimismo, que la
demanda máxima de pintura para interiores está limitada a dos toneladas
diarias.
El precio por tonelada es de 3.000€ para la pintura de exteriores y
2.000€ para pintura de interiores.
Se desea saber cuanta pintura para exteriores e interiores debe
producir la compañía todos los días para maximizar el ingreso bruto.

CONSTRUCCIÓN DEL MODELO.

La construcción de un modelo matemático se puede iniciar
respondiendo a las tres siguientes preguntas.
1ª. ¿ Qué busca determinar el modelo?, o dicho de otra forma,
¿cuales son las variables (incógnitas) del problema?.
2ª. ¿Qué restricciones deben de imponerse a las variables a fin de
satisfacer las limitaciones del sistema representado por el modelo?.
 3ª. ¿Cuál es el objetivo (meta) que necesita alcanzar para
determinar la solución óptima (mejor) entre todos los valores factibles de
las variables?.
Una forma efectiva de responder a estas preguntas consiste en hacer
un resumen verbal del problema. En términos del ejemplo anterior, la
situación se describe en la forma siguiente.
La compañía busca determinar las cantidades (en toneladas) de
pintura para exteriores e interiores que se producirán para maximizar
(incrementar hasta donde sea posible) el ingreso bruto total (en miles de
unidades monetarias), a la vez que se satisfacen las restricciones de la
demanda y el uso de materias primas.
El punto capital del modelo matemático consiste en identificar en
primer término las variables y después expresar el objetivo y las
restricciones como funciones matemáticas de las variables. Por lo tanto,
en relación con el problema anterior, se tiene lo siguiente.
Variables. Como se desea determinar las cantidades de pintura para
exteriores e interiores que se producirán, las variables del modelo se
pueden definir como:

x E = toneladas de pintura para exteriores producidas diariamente

x E = toneladas de pintura para interiores producidas diariamente

Función objetivo. Como cada tonelada de pintura para exteriores se

vende en 3.000€, el ingreso bruto obtenido de la venta de x E toneladas es
de 3x E = miles de unidades monetarias. En forma análoga, el ingreso
bruto que se obtiene de vender x I tonelada de pintura para interiores es
2x I miles de unidades monetarias. Bajo la suposición de que las ventas de
pintura para exteriores e interiores son independientes, el ingreso bruto
total se convierte en la suma de los dos ingresos.
Si hacemos que z represente el ingreso bruto total (en miles de
unidades monetarias), la función objetiva se puede escribir
matemáticamente como:
 z = 3x E +2x I
La meta consiste en determinar los valores (factibles) de x E y x E
que maximizarán esta función objetivo (o criterio o ecomómica)

Restricciones. El problema anterior impone restricciones sobre el

uso de materias primas y sobre la demanda. La restricción del uso de
materias primas se puede expresar en forma verbal como.
(uso de materia primas
 (disponibilidad máxima de
en ambas pinturas) materias primas)

Esto nos lleva a las restricciones que siguen: según la tabla anterior, para
obtener una tonelada de pintura de exteriores se necesita una tonelada de
materia prima A, luego para optener x E toneladas se necesitan 1.x E
toneladas de materia prima A; mientras que para obtener 1 tonelada de
interiores se necesita 2 toneladas de A, luego para x I toneladas se
necesitan 2. x I toneladas de A, y donde la suma es la cantidad necesaria
de la materia prima A para repartir entre ambas tipos de pintura, y que
lógicamente es inferior a la cantidad disponible de 6 toneladas de A. Del
mismo modo se hace para la materia prima B, es decir,

x E +2x I  6 (materia prima A)

2x E + x I  8 (materia prima B)

las restricciones sobre la demanda se expresan en forma verbal como:

(cantidad en exceso de pinturas para  1 tonelada por día

interiores sobre exteriores)
(demanda de pintura para interiores)  2 toneladas por día

matemáticamente, éstos se expresan, respectivamente, como:

-x E + x I  1 (exceso de pintura para interiores sobre pintura para

exteriores)
 x I  2 (demanda máxima de pintura para interiores)

Una restricción implícita (o “sobreentendida”) es que la cantidad

que se produce de cada pintura no puede ser negativa (menor que cero).
Para evitar obtener una solución como ésta, se imponen las restricciones
de no negatividad,o sea:

x E 0 (pintura para exteriores)

x I 0 (pintura para interiores)
Los valores x E y x I son factibles si verifican todas las restricciones del
modelo.
Luego el modelo matemático completo para el problema planteado
se puede resumir de forma siguiente:

Detemínense las toneladas de pintura para exteriores e interiores que se

producirán para:
maximizar z = 3x E +2x I = - minimizar -z = -3x E -2x I
sujeto a x E +2x I  6
2x E + x I  8
-x E + x I  1 (restricciones)
x I 2
x E 0 , x I 0

¿Qué hace que este modelo sea un programa lineal?. Técnicamente,

es un programa lineal porque todas sus funciones (restricciones y la
función objetivo) son lineales. La linealidad supone que se cumplen las
propiedades de proporcionalidad, aditividad, divisibilidad y
certidumbre. (es decir, estos supuestos se cumplen, o se suponen
admisibles al haber formulado el modelo anterior).
Proporcionalidad se cumple si la contribución de cada variable al valor
objetivo (c j .x j ) o al lado derecho (a i j .x j ) es directamente proporcional al
nivel de la variable. Se supone que tanto c j como a i j no varían según el
nivel de la variable.
Aditividad se cumple cuando las contribuciones individuales representan
el valor total. Es decir, el valor que toma una variable no depende del que
tome otra, lo que supone que las variables tienen que ser independientes
entre si.
Divisibilidad se cumple cuando el valor de las variables puede ser
cualquiera, es decir, considerar a la variable como continua.
Certidumbre supone que los parámetros (c j , a i j y b i ) aunque sean valores
estimados, se toman como constantes.

La representación gráfica del modelo anterior es la siguiente:

xIxI

2 3

c
A
xE
6

z*
 Como se puede observar la solución óptima se produce en el punto
extremo (vértice) A con valor (x E , x I ) = ( 10/3, 4/3) y z  = 38/3

EL MÉTODO SIMPLEX.

El ejemplo prototipo anterior recoge los aspectos fundamentales de

un problema de P.L., tanto en formulación como en su resolución.
Sin embargo, en cuanto a su resolución, cuando el número de
variables de decisión es superior a tres, no es posible conocer la solución
optima de forma gráfica. Por ello, es necesario desarrollar un método que
permita obtener la solución de forma analítica. El método más eficiente
que permite resolver el problema de una forma eficiente, es el método
simplex, el cual es un algoritmo, es decir, un proceso iterativo, donde
parte de una solución inicial, para luego comprobar si la misma es
óptima o en caso contrario buscar otra solución, con la característica
esencial de que el valor objetivo de esta nueva solución se mejora, o al
menos no se empeora, y así hasta que se cumpla que la solución es la
óptima.
Pero antes de comenzar a describir el citado método, es
conveniente aclarar algunos conceptos necesarios para poder
desarrollarlo, aunque vamos a ver ahora lo mínimo del citado método,
dejando para un apéndice final, una justificación más exhaustiva si es que
se desea tener un conocimiento más profundo del método.
Vamos a ver la resolución del problema de programación lineal
bajo la forma que vamos a denominar, nuestra forma estándar, de cara a
fijar los criterios para su resolución (cuando el problema tenga otra
forma, se transformará de una forma fácil, como ya se indicó
anteriormente, a la forma estándar pero que no obstante, se verá a través
de diferentes problemas ilustrativos) es la siguiente:

MINIMIZAR: z = cx

Sujeto a: Ax = b
x0

Como se ha visto anteriormente de forma gráfica, las posibles

soluciones de un problema de P.L. son los vértices de la región factible.
Entonces el método simplex lo que va hacer es caracterizar el concepto
gráfico de vértice por el equivalente analítico de solución básica
factible.
Sea la matriz de restricciones A m n , donde m es el número de
restricciones y n el número de variables. Si suponemos que m  n y si el
rango A = m, entonces se dice que es de rango completo, entonces existe
una submatriz cuadrada con dimensión mm, denominada matriz básica
B, es decir, las filas (o columnas) son linealmente independientes, o lo
que es lo mismo, el determinante de B es diferente de 0, con lo cuál
existe la matriz inversa mientras que las restantes columnas de la matriz
A (una vez excluida la citada matriz B) conforman la matriz no básica
N, denominando a las variables correspondientes a los vectores que
constituyen las citadas matrices en variables básicas y variables no
básicas, respectivamente. Luego la ecuación de las restricciones queda de
la siguiente forma:
 xB 
Ax=b = B,N.   =Bx B + Nx N
 xN 
Si multiplicamos la ecuación anterior por la matriz inversa B - 1 , se
obtiene:
B - 1 b = B - 1 Bx B + B - 1 Nx N =I x B + B - 1 Nx N = x B + B - 1 Nx N
Luego se pueden poner las variables básicas en función de las no
básicas, es decir:
x B = B - 1 b - B - 1 N x N (1)
Como supusimos m  n, entonces para cada asignación de valores a
las variables no básicas, se obtiene unos valores para las variables
básicas, pero si hacemos que todas las variables no básicas tomen el
valor 0, entonces se obtiene una única solución para las variables
básicas, O sea, la ecuación (1) queda entonces como:

Si x N = 0  xB= B-1b (2)

 xB  B -1b
entonces , x =  es una solución básica
 xN   0 
  xB  B -1b  0
Si además x  =     es entonces una solución básica
 xN   0  0
factible
Si tenemos en cuenta el problema:
Minimizar: z = - x1 - 2x2
Sujeto a. x1 + x2  3
- x1 + 2x2  2
x1 , x2  0
Si lo ponemos en forma estándar (restricciones en forma de igualdad)
Minimizar : z = - x1 - 2x2  0x3  0x4
Sujeto a. x1 + x2  x3 3
- x1 + 2x2  x4  2
x 1 , x4  0

 111 0 
A = a1, a2, a3, a4    
-1 2 0 1 
 1 1  2/3 - 1/3 
Sea B=(a 1 ,a 2 )    , donde B - 1    , entonces
 -1 2  1/3 1/3 
 x1   2/3 - 1/3   3   4/3   x3   0 
xB     B -1 b         ; x N =   =  
 x2   1/3 1/3   2   5/3   x4   0 
 xB   0 
Como x=      , se trata de una solución básica factible, y entonces
 xN   0 
se obtiene las coordenadas del vértice (4/3, 5/3).
 1 0
Si se toma ahora B  (a3, a4)     I  B -1 ,luego
 0 1
 xB1   x3  3  x1   0 
xB        B -1 b  Ib  b    y xN       , luego también se
 xB2   x4   2  x2   0 
trata de una solución básica factible. En este caso se obtiene el vértice
(0,0), o sea el origen. Otras soluciones básicas factibles nos darían los
otros vértices de la región factible.

Conclusión: Se puede demostrar (lo hemos visto gráficamente) que

“toda solución básica factible es equivalente a un vértice de la región
factible”.
 El método simplex va a partir siempre de una solución básica
factible inicial, donde la matriz básica inicial va ser la matriz
identidad (o sea, tiene rango m y está formada por unos la diagonal
principal y ceros los restantes componentes; además la matriz inversa de
la matriz identidad es la misma matriz identidad), con lo cuál la ecuación
(2), queda (como b0, si no hay que multiplicar la restricción por -1 para
que lo sea):
x B = B - 1 b= Ib=b , o sea,
 xB   b   0 
x          solución básica factible inicial
 xN   0   0 

NOTA: En el caso de que matriz A no tenga la matriz I de rango m,

entonces se obtendrá de forma artificial, añadiendo las variables
artificiales necesarias, y tomando como coste de cada variable artificial
utilizada un coste M>>0 (en este caso se estará utilizando el método de
penalización, que transformará el problema P: principal en uno P(M),
penalizado).
Luego vamos a ver ahora el formato utilizado por el método
simplex para poder desarrollarlo. El formato es una tabla (cuadro) que
refleja por un lado la función objetivo y por otro las ecuaciones
(restricciones funcionales en forma de igualdad), donde las variables
básicas están en función de las variables no básicas (que valen cero
como vimos). Entonces:

z= cx (1)
Ax=b (2)

Si descomponemos el vector de costes c = (c B , c N ), es decir, en

costes correspondientes a las variables básicas y no básicas,
respectivamente, y desarrollamos las ecuaciones (1) y (2), de la forma
siguiente:
De la (2) como vimos antes, se obtenía: x B = B - 1 b - B - 1 N x N
 xB 
y de (1) se obtiene: z= cx= (c B , c N )   = c B x B + c N x N , sustituyendo en
 xN 
esta el x B anterior, se obtiene:
 z= c B (B - 1 b - B - 1 N x N )+ x N c N = c B B - 1 b - (c B B - 1 N- c N ) x N

Luego las ecuaciones anteriores (1) y (2), tanto la función objetivo

como las variables básicas quedan en función de las variables no
básicas de la forma siguiente:

z = cBB-1b - (cBB-1N - cN) xN (1)

xB= B-1b - B-1N xN (2)

Si x N = 0, entonces z 0 = c B B - 1 b y x B = B - 1 b, es decir, el valor objetivo de

 xB  B -1b 0 
la solución actual x0=   =   0 
 xN  0   
Si ahora las ecuación (1) y (2), las arreglamos de la forma siguiente, que
tanto en las ecuaciones (1) y (2), figuren en el lado izquierdo, la función
objetivo z (la vamos a considerar como una variable), las variables
básicas y las no básicas, mientras en el lado derecho el resto
:
z .1 + 0. x B + (c B B - 1 N - c N ) x N = c B B - 1 b (1)
z.0 + I. x B + B - 1 N x N = B-1b (2)

Observar que en la (1) no están variables básicas, luego como el vector de

variables básicas es un vector columna, multiplicamos por O (vector fila
con m ceros) el vector x B , mientras que la (2), que no figura z, entonces
la multiplicamos por 0, para que también figure, luego, los dos sistemas
(1) y (2), los podemos poner como:

z xB xN LD
z 1 0 cBB-1N - cN cBB-1b
xB 0 I B-1N B-1b

Como puede observarse, el cuadro anterior recoge las ecuaciones (1) y

(2), es decir, la fila correspondiente al valor objetivo y las filas
correspondientes a las variables básicas, ambas en función de las
variables no básicas. Luego, para una solución básica factible, es decir,
cuando las variables no básicas tienen un valor cero, las citadas
ecuaciones nos reflejan el valor de la función objetivo, así como el valor
de las variables básicas que se recoge, respectivamente en el lado derecho
(LD)(lado derecho) del cuadro. Si ahora desarrollamos en detalle el
cuadro anterior, es decir, para cada una de las variables, se obtiene:

xB xN

z x1 .... x r .... xm ..... xj .. xk . LD

z 1 0 .... 0 .... 0 .... z j -c j .. z k -c k . c B b
x 1 0 1 .... 0 ... 0 .... y1 j .. y1 k . b 1
. . ... . ... . .... . .. . . .
x r 0 0 .... 1 ... 0 ..... yr j yrk . b r
. . ... . .... . .... . . . .
x m 0 0 ... 0 .... 1 ... ym j ym k . b m

El desarrollo anterior (el detalle se puede ver, si el interesado lo

desea, en el apéndice final), se ha simplificado de la forma siguiente:
b = B - 1 b
zj = cBB-1aj
yk = B-1 aj
Se puede observar en el cuadro anterior, que las componentes de cada
columna de una variable básica son “siempre” todas 0, excepto una que
vale 1, en la posición que ocupa la citada variable básica en la columna
de la izquierda. Como se demuestra en el apéndice final, las ecuaciones
(1) y (2) anteriores se convierten en las expresiones siguientes:

z = cBb - (zk -ck) xk (1)

xB= b - ykxk (2)

Si se analiza ahora la ecuación (1), nos va servir de guía para mejorar el
valor actual de la variable z (no olvidemos que se está minimizando).
Para que se pueda mejorar la actual solución tendrá que variarse el valor
de alguna variable no básica, que actualmente tiene el valor 0.
Luego si (z k -c k )  0, la variable no básica x k que vale 0, interesaría
incrementarla desde su valor 0 ya que daría lugar a una disminución del
valor objetivo z al estar restando, pero sin embargo hay que tener en
cuenta la ecuación (2), dado que si el vector columna y k tiene alguna
componente positiva, al estar restando ocurrirá que habrá un límite en el
crecimiento de la variable no básica para que alguna variable básica no
se haga negativa, ya que ello no está permitido al tener que ser no
negativas cualquiera de las variables. En realidad, lo que se va a producir
es que si la solución básica factible actual no es la óptima, entonces se va
sustituir por otra solución básica factible, de tal manera, que la variable
no básica x k se va convertir en variable básica, mientras que una variable
básica va a ser sustituida por la anterior, convirtiendo entonces la básica
en no básica, al mismo tiempo que el valor objetivo se puede mejorar (o
al menos no empeora).
Luego, ya podemos poder describir el algoritmo simplex, que se
basa en los siguientes pasos.
Algoritmo simplex.
PASO INICIAL:
Partir de una solución básica inicial obtenida a través de una matriz
básica identidad, es decir, tomando como variables básicas iniciales las
variables que tengan los vectores asociados a una matriz identidad. O
sea, x B = B - 1 b =Ib=b, y x N =0.
PASO FUNDAMENTAL.
En los pasos siguientes se va a comprobar si la solución básica factible
anterior es óptima, o en caso contrario encontrar una nueva solución
básica factible que mejore el valor objetivo.
Paso 1. Se determina (z k -c k ) = máximo (z j -c j )  0, coeficientes en la
fila del valor objetivo, entre las variables “no básicas”.
 En el caso de que z k -c k  0, entonces la solución actual es la
óptima al no poder mejorarse el valor objetivo, y el problema ya está
resuelto. En caso contrario, paso 2.

Paso 2. Se observa la columna y k correspondiente a la variable x k .

Si el vector columna y k  0 (es decir, no tiene ninguna componente
positiva), entonces, el problema tiene una solución no acotada ( z - ),
ya que x k puede crecer indefinidamente según la ecuación (2), luego la
solución se encuentra en un rayo, es decir:

 xB   B -1b  yk  
x =    xk ; xk  0  .
 xN    0   ek  
Donde e k es un vector columna con ceros, excepto un 1 para la variable
“no básica” x k .
(Nota: la expresión anterior es válida también para expresar la solución
básica optima general, cuando el vector y k tiene al menos una
componente positiva. Existe una solución finita única, cuando z k -c k  0 y
entonces x k = 0: mientras que si z k -c k = 0, entonces x k crece hasta que
una variable básica se hace nula, como veremos en un ejemplo,
x k =( br/yrk ):
En caso contrario, si y k no es menor o igual que 0, es decir, si
existe alguna componente positiva, entonces se determina la variable
básica x  r que va a salir de la base, cuyo índice r se determina por la
siguiente relación mínima.
br  bi 
= mínimo  ; tal que yik  0 
yrk  yik 
Luego conocido el índice k (de la variable que entra en la base) y r (de la
variable que sale de la base), se realiza una operación llamada de pivoteo
sobre la componente y r k , lo que supone el dividir toda la fila r básica por
la citada componente y r k y reemplazar en la columna básica la variable
x  r por x k y a continuación efectuar operaciones elementales por filas
para conseguir que los restantes elementos de la nueva columna básica (
es decir, de la variable x k ) sean 0. Y a continuación volver al paso 2,
hasta que en una iteración, se pare en alguna de las situaciones
anteriores, ya que como se comentó anteriormente, el proceso tiene una
convergencia en un número de pasos finitos al ser el número de vértices
(o lo que es lo mismo, soluciones básicas factibles) un número finito.
Se puede demostrar que en la base anterior al sustituir el vector básico
a B r por el no básico a k , la nueva colección de vectores en una base, con lo
cual la solución alcanzada es una solución básica factible, es decir, un
nuevo vértice de la región factible pero con un valor objetivo mejorado
(si no existe degeneración).
Vamos resolver ahora algunos problemas que nos van a permitir
ilustrar lo anteriormente comentado, reflejando además todas las
situaciones posibles, en la resolución de un problema de programación
lineal, como ya dejamos apuntado en la ilustración gráfica, pero que
ahora lo haremos resolviéndolo analíticamente.
 Resolver los siguientes problemas utilizando para ello el método
simplex y expresando detalladamente las soluciones de los mismos:

a. Maximizar z = x1 + 2x2
Sujeto a : - x1 + 2x2  6 b. Maximizar z = - x1 + 2x2
- 2x1 + x2  2 Sujeto a : - x1 + 2x2  6
x 1 , x2  0 - 2x1 + x2  2
x 1 + x2  6
x1 , x 2  0
c. Minimizar z = - 2x1 + 3x2
Sujeto a : - x1 + 2x2  2
2x1 - x2  3 d. Minimizar z = - x1 + 3x2
x2  4 Sujeto a : - x1 + 2x2  6
x1 , x2  0 - 2x1 + x2  2
x 1 + x2  6
x1 , x 2  0

SO LUCIO NES

a)
Maximizar z  x1  2x2  - Minimizar z  - x1  2x2  0x3  0x4
sujeto a - x1  2x2  6 - x1  2x2  x3 6
- 2x1  x2  2 - 2x1  x2  x4  2
x1, x2  0 x1,.........x4  0

z x1 x2 x3 x4 LD
z 1 1 2 0 0 0
x3 0 -1 2 1 0 6
x4 0 -2 1 0 1 2

z x1 x2 x3 x4 LD
z 1 5 0 0 -2 -4
x3 0 3 0 1 -2 4
x2 0 -2 1 0 1 2

z x1 x2 x3 x4 LD
z 1 0 0 -5/3 4/3 -22/3
x1 0 1 0 1/3 -2/3 2/3
x2 0 0 1 2/3 -1/3 10/3

SO LUCIÓ N NO ACO TADA z *  (  )  

 x1  2 / 3  2 / 3
 x  10 / 3 1 / 3 
En el ray o x =       x 4 con x4  0
* 2

 x 3  0  0 
     
 x4  0  1 

b)
Maximizar z  - x1  2x2  - Minimizar z  x1  2x2  0x3  0x4  0x5
sujeto a - x1  2x2  6 - x1  2x2  x3 6
- 2x1  x2  2 - 2x1  x2  x4 2
x 1  x2  6 x 1  x2  x5  6
x1, x2  0 x1,.........x5  0
 z x1 x2 x3 x4 x5 LD
z 1 -1 2 0 0 0 0
x3 0 -1 2 1 0 0 6
x4 0 -2 1 0 1 0 2
x5 0 1 1 0 0 1 6

z x1 x2 x3 x4 x5 LD
z 1 3 0 0 -2 0 -4
x3 0 3 0 1 -2 0 2
x2 0 -2 1 0 1 0 2
x5 0 3 0 0 -1 1 4

z x1 x2 x3 x4 x5 LD
z 1 0 0 -1 0 0 -6
x1 0 1 0 1/3 -2/3 0 2/3
x2 0 0 1 2/3 -1/3 0 10/3
x5 0 0 0 -1 1 1 2

Sol ucio nes alt erna tiv as fini tas z * = -( -6) =6

 x1  2 / 3  2 / 3
 x  10 / 3 1 / 3 
 2    
Co n la sol ució n x * =  x 3   0   0  x 4 donde 0  x4  2
     
 x4  0   1 
X5  2   1 

c)

Minimizar z  - 2x1  3x2  Minimizar z   2x1  3x2  0x3  0x4  0x5  Mx6
sujeto a - x1  2x2  2 - x1  2x2  x3 2
2x1  x2  3 2x1  x2  x4 3
x2  4 x2  x5  x6  4
x1,.x2  0 x1,.........x6  0
 z x1 x2 x3 x4 x5 x6 LD
z 1 2 -3 0 0 0 -M 0
x3 0 -1 2 1 0 0 0 2
x4 0 2 -1 0 1 0 0 3
x6 0 0 1 0 0 -1 1 4

z x1 x2 x3 x4 x5 x6 LD
z 1 2 -3+M 0 0 -M 0 4M
x3 0 -1 2 1 0 0 0 2
x4 0 2 -1 0 1 0 0 3
x6 0 0 1 0 0 -1 1 4

z x1 x2 x3 x4 x5 x6 LD
z 1/2+1/2
1 0 3/2-1/2M 0 -M 0 3-3M
M
x2 0 -1/2 1 1/2 0 0 0 1
x4 0 3/2 0 1/2 1 0 0 4
x6 0 1/2 0 -1/2 0 -1 1 3

z x1 x2 x3 x4 x5 x6 LD
z 0
1 0 4/3-1/2M 0 -M 0 -5/3-5/3M
x2 0 0 1 2/3 1/3 0 0 7/3
x1 0 1 0 1/3 2/3 0 0 8/3
x6 0 0 0 -2/3 -1/3 -1 1 5/3

Co mo x * 6 =5 /3 > 0, q ue es una va ria ble ar ti fici al, lue go el p robl ema P es

INFACTIB LE

d).

Minimizar z  - x1  3x2 Minimizar z  - x1  3x2  0x3  0x4  0x5

sujeto a - x1  2x2  6 - x1  2x2  x3 6
- 2x1  x2  2 - 2x1  x2  x4 2
x 1  x2  6 x 1  x2  x5  6
x1, x2  0 x1,.........x5  0
 z x1 x2 x3 x4 x5 LD
z 1 1 -3 0 0 0 0
x3 0 -1 2 1 0 0 6
x4 0 -2 1 0 1 0 2
x5 0 1 1 0 0 1 6

z x1 x2 x3 x4 x5 LD
z 1 0 -4 0 0 -1 -6
x3 0 0 3 1 0 1 12
x4 0 0 3 0 1 2 14
x1 0 1 1 0 0 1 6

Sol ució n Ó P TI M A ÚNI CA FI NITA z * = -6

 x1  6 
 x  0 
 2  
En e l punt o x =  x 3   12
*

   
 x4  14
X5  0 

APENDICE
Tal como se ha visto anteriormente, una vez obtenida las variables
básicas en función de las no básicas:

(2) x B = B - 1 b - B - 1 N x N

Entonces obteníamos el valor objetivo también en función de las

 xB 
variables no básicas, z= cx= (c B , c N )   = c B x B + c N x N , sustituyendo en
 xN 
esta el x B anterior, queda:

(1) z= c B (B - 1 b - B - 1 N x N )+ x N c N = c B B - 1 b - (c B B - 1 N x N - c N ) x N .

En realidad las ecuaciones anteriores expresan el valor de cualquier

solución y el correspondiente valor objetivo asociado, es decir, si
hacemos x N =0, entonces tenemos el valor de la solución básica actual,
que es un vértice de la región factible. Vamos a ver si el actual valor
objetivo, lo podemos mejorar (estamos suponiendo que el problema es de
MINIMIZACION). Para ello, tendrá que ser en otro vértice, es decir en
una solución básica factible. Pero para variar el punto actual, no habrá
más remedio que variar alguna variable no básica, que actualmente tiene
un valor nulo.
Consideremos en las ecuaciones anteriores las componentes de la matriz
no básica N=(a m + 1 , …..a j …….an) ( a efectos simplificativos, estamos
suponiendo que las primeras m columnas corresponde a la matriz básica
B, luego las restantes serán las de la no básica N). Luego las ecuaciones
(1) y (2), se pueden expresar como:

- n n
(1) z= c B B - 1 b - (c B B - 1 N - c N ) x N = cB b -  (cBB -1aj - cj)xj = z 0 -
j m 1
 (z - c )xj
j m 1
j j

z j =c B B - 1 a j

z 0 =c B B - 1 b

mientras que (2) es

n

B -1
ajxj n n
xB= B-1b - B-1N xN = xB= B-1b - j  m 1 = B-1b - 
j  m 1
yjxj = b - 
j  m 1
yjxj

Ahora se va incrementar sólo la variable no básica x k (tal que

zk - ck  mínimozj - cj, donde j es el subindice de las variables no basicas  .)

br  bi 
xk =  mínimo  , yik  0 
yrk  yik 
Luego las ecuaciones (1) y (2) quedan (ya que las otras variables no
básicas no varían de su valor actual que es 0)
br
(1 ) z= z 0 -(z k -c k ).x k = z 0 -(z k -c k )
yrk

br
(2 ) x B = b -y k
yrk
 Si z k -c k >0, entonces conviene incrementar x k para que z disminuya
(se está minimizando z ). ¿cuánto?. Habrá que ver el valor de y k , pueden
existir dos casos:
a) Que yk  0 , luego según la ecuación (2), al ser –y k , entonces x k
puede crecer indefinidamente y las variables básicas no se hacen
negativas, lo cual implica que la solución es NO ACOTADA
z  -  y la solución está en el rayo
 b    yk 
xB       xk , con xk  0
 0   ek 
br
b) Que  algún y i k >0, entonces x k crecerá hasta , y x B r =0, es decir
yrk
, entra en la base x k y sale x B r , luego es está en una nueva solución
básica factible, y habrá que comprobar si esta nueva solución es
óptima. Como el nº de vértices es un nº finito, al ser la intersección
de las restricciones, y estas son un nº finito, es decir, en un nº
finito de iteraciones (cada iteración es una solución) se conseguirá
la solución óptima, si zk - ck  0 , pero pueden ocurrir dos casos:
1º) Que zk - ck  0 ,entonces la solución es única, con valor objetivo el
de la solución actual. La solución óptima al ser x k =0, es

 xB   b 
x *      
 xN   0 
2º ) Que z k -c k =0 entonces existen soluciones alternativas, con valor

objetivo de la solución actual. La solución óptima es ahora:

 xB   b    yk  bk
x *          xk , con 0  xk 
 xN   0   ek  yrk